基于改進自適應黑洞機制的引力搜索算法

摘要：針對基本引力搜索算法（gravity search algorithm，GSA）易早熟、易陷入局部最優、缺少有效加速機制等缺點，提出了基于改進自適應黑洞機制的GSA（improved adaptive black hole gravity search algorithm，IABHGSA）。通過改進Tent映射對種群初始化，使得初始種群的分布更隨機、均勻、全面，增強算法的全局勘探能力；引入改進自適應黑洞機制，根據粒子進化情況選擇位置更新策略，使得位置更新更為合理，有效減小粒子陷入局部最優的可能性；通過基于學習思想的最優與最差粒子更新策略增強算法逃離局部最優的能力，并提高算法的尋優速度；引入群體遷徙，為算法提供有效的加速收斂機制。最后，選取八個基準測試函數對IABHGSA進行測試，并與相關算法的實驗結果進行了對比，結果證明IABHGSA有更好的尋優性能。

關鍵詞：引力搜索算法； 改進Tent映射； 自適應策略； 粒子位置更新； 群體遷徙

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001-3695（2022）10-025-3046-09

doi：10.19734/j.issn.1001-3695.2022.03.0096

Gravity search algorithm based on improved adaptive black hole mechanism

Xu Wenjun， Wang Xihuai， Xiao Jianmei， Gu Junyu

（College of Logistics Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：Aiming at the shortcomings of the basic GSA， such as prone to premature maturity， easy to fall into local optimum， and lack an effective acceleration mechanism， this paper proposed IABHGSA. The IABHGSA used the improved Tent mapping to initialize the population， which made the distribution of the initial population more random， uniform and comprehensive， and it enhanced the global exploration capability of the algorithm. IABHGSA introduced an improved adaptive black hole mechanism and selected the position update strategy according to the evolution of the particles， which made the position update more reasonable， to effectively reduce the possibility of particles falling into local optima. Through the optimal and worst particle update strategy based on learning ideas， it enhanced the algorithm’s ability to escape from local optima and improved the algorithm’s optimization speed. It introduced group migration to provide effective accelerated convergence mechanism for the algorithm. Finally， this paper selected 8 benchmark functions to test IABHGSA and compared with the experimental results of related algorithms. The results show that IABHGSA has better optimization performance.

Key words：gravity search algorithm; improved Tent mapping; adaptive strategy; particle position update; group migration

0引言

引力搜索算法（GSA）是Rashedi等人［1］受到物理學中萬有引力定律的啟發而提出的智能優化算法。GSA通過粒子間引力的相互作用來交流信息，其概念簡單，容易實現且算法收斂性好［2］。研究表明，GSA的尋優精度和收斂速度對比粒子群優化算法（particle swarm optimization，PSO）、遺傳算法（genetic algorithm，GA）等其他優化算法具有一定的優勢［1］，因此GSA在優化調度［3］、參數辨識［4］、函數優化［5］等領域得到廣泛的應用。GSA與常見的生物啟發式算法相似，都屬于群智能優化算法。在GSA中，每個粒子的位置表示問題的一個可行解，解的優劣與粒子的質量有關，質量最大的粒子占據最好的位置。在解空間內，粒子受到萬有引力的作用而相互吸引，質量小的粒子向質量最大的粒子移動，以此完成算法的迭代尋優。基本GSA與常見的生物啟發式算法一樣，都存在著易早熟收斂、局部搜索能力差、缺少有效加速機制等問題，仍需對其加以改進，進一步提高其尋優性能［6］。針對以上問題，國內外學者進行了大量研究，提出了諸多改進GSA。劉紫陽等人［7］在GSA的位置更新公式中引入Lévy飛行策略，改進后的GSA具有更好的尋優精度和穩定性，但是并未明顯提高GSA的收斂速度；Mirjalili等人［8］將“向全局最優移動”項加入GSA的速度更新公式，提高GSA的收斂速度和逃離局部最優的能力，然而GSA可能因為最優粒子的錯誤引導而早熟收斂；Su等人［9］在GSA的引力系數中加入基于粒子適應度值的反饋機制，并加入精英記憶保留策略，提高了GSA的收斂速度和魯棒性，但GSA的尋優精度對比改進前提升有限；張維平等人［10］在GSA中引入反向學習策略、精英策略和邊界變異策略，顯著地提高了GSA的全局探索能力和局部尋優能力，但以上改進策略會增加算法的計算量，從而增加算法的計算時間。Joshi等人［11］在GSA中引入非線性變化的引力系數，提高了GSA的尋優精度和搜索效率，但是沒有對GSA的收斂性能作出明顯改進。

綜上可知，目前已有許多GSA的改進和應用，但GSA的全局探索能力和局部尋優能力仍有較大的提升空間。為了更有效地改善GSA易早熟收斂的缺點，增強GSA的尋優性能，本文提出基于改進自適應黑洞機制的引力搜索算法（IABHGSA）。通過改進Tent映射生成初始種群，使得種群分布隨機、均勻、全面，增強算法的全局勘探能力；引入基于改進自適應策略的黑洞機制，使得粒子可以根據自身進化情況更為合理地選擇位置更新策略，有效降低算法陷入局部最優的可能性；引入基于學習思想的最優與最差粒子更新策略，增強算法的逃離局部最優的能力和尋優速度；引入群體遷徙，為算法提供有效的加速機制，提高算法的收斂速度。

1引力搜索算法

假設由N個粒子Xi構成種群，在d維引力系統中，定義粒子i的位置Xi=（X1i，X2i，…，Xdi，…，Xni），其中i=1，2，…，N。根據萬有引力定律，在d維空間中，第t次迭代時粒子i、j之間的引力Fdij（t）可以表示為

Fdij（t）=G（t）Mi（t）×Mj（t）Rij（t）+ε（Xdj（t）－Xdi（t））（1）

其中：G（t）為第t次迭代時的引力系數；Mi（t）與Mj（t）分別為粒子i、j在第t次迭代時的慣性質量；Rij（t）為第t次迭代時粒子i、j之間的歐氏距離；ε為很小的常量。

引力系數G（t）和歐氏距離Rij（t）的具體計算公式為

G（t）=G0×e（－αtT）（2）

Rij（t）=‖Xi（t），Xj（t）‖（3）

其中：G0為引力系數初始值；α為引力系數衰減因子；t、T分別為算法當前迭代次數和算法最大迭代次數；Xi（t）、Xj（t）分別為粒子i、j在第t次迭代時的位置。

粒子i的慣性質量Mi（t）根據適應度函數定義為

mi（t）=fiti（t）－min（fiti（t））max（fiti（t））－min（fiti（t））（4）

Mi（t）=mi（t）∑Ni=1mi（t）（5）

其中：fiti（t）為第t次迭代時粒子i的適應度值；max（fiti（t））、min（fiti（t））分別為第t次迭代中粒子i的最差、最優適應度值。

為了表示算法的隨機性，作用在維上粒子i所受合力Fdi（t）可以表示為

Fdi（t）=∑Nj=1，i≠jrandj×Fdij（t）（6）

其中：randj為［0，1］的隨機數。在GSA的每次迭代中，粒子的速度、位置和加速度更新為

vdi（t+1）=randj×vdi（t）+adi（t）（7）

xdi（t+1）=xdi（t）+vdi（t+1）（8）

adi（t）=Fdi（t）Mi（t）（9）

其中：vdi（t）、xdi（t）、adi（t）分別為粒子i在第t代時第d維空間的速度、位置及加速度。

2改進引力搜索算法

2.1改進Tent映射生成初始種群

基本GSA的初始種群是隨機生成的，可能導致個體分布不均、種群多樣性降低，影響算法后續的迭代尋優。混沌映射因其隨機性、遍歷性等特點，近年來已被應用于元啟發式算法中來提高種群多樣性［12］。本文選用Tent映射來初始化種群，Tent映射具有結構簡單、遍歷性好、隨機性好、混沌均勻性和迭代速度優于logistic映射的特點［13］。將Tent映射用于GSA的種群初始化，可以增加初始種群的多樣性，避免算法陷入局部最優，GSA可以獲得更好的尋優效果。Tent映射的表達式為

Et+1=2Et0lt;Etlt;0.5

2（1－Et）0.5≤Etlt;1（10）

其中：Et為Tent映射。分析Tent映射的迭代過程能夠發現映射中存在不穩定周期點，同時由于計算機的運行特性，使得Tent映射在經歷一定次數的迭代后總會落入不穩定周期點，導致Tent映射的遍歷性降低。為了避免Tent映射陷入不穩定周期點，提高Tent映射的均勻性和遍歷性，本文提出基于logistic映射改進的Tent映射，利用logistic映射的擾動效果消除Tent映射的不穩定周期點，使得Tent映射的分布更遍歷、均勻。本文提出的改進Tent映射的表達式為

Lt+1=4Lt（1－Lt）0lt;Ltlt;1（11）

E′t+1=min（2E′t+1N×rand×Lt，1）0lt;E′tlt;0.5

min（2（1－E′t）+1N×rand×Lt，1）0.5≤E′tlt;1（12）

其中：Lt為logistic映射；E′t為改進Tent映射。圖1、2分別為Tent映射分布直方圖和本文所提改進Tent映射分布直方圖。從圖1中可以看出Tent映射在［0，0.1］的取值概率遠高于其他各段的取值概率，這是因為Tent映射在迭代中陷入不穩定周期點，使得后續的映射值都為0，嚴重影響映射的均勻性和遍歷性。觀察圖2，改進Tent映射在各段的取值概率相對均勻，表明本文提出的改進Tent映射成功消除了使得Tent映射取值為0的點，改善了Tent映射分布不均勻的現象。

綜上，本文使用改進Tent映射生成初始種群，利用改進Tent映射產生均勻分布的混沌序列，減少初始種群分布不均勻對算法優化效果的影響，增強算法的全局探索能力。基于改進Tent映射的種群初始化的表達式為

xdi=xmin+（xmax－xmin）×E′t（13）

其中：xdi為第i個粒子在第d維中的位置；xmax、xmin分別為粒子位置的上、下限。

2.2改進自適應黑洞機制

Zhang等人［14］于2008年首次提出隨機黑洞粒子群優化算法（random black hole particle swarm optimization，RBHPSO），RBHPSO在PSO中引入黑洞機制，使得粒子快速移動至全局最優附近，提高了算法的收斂速度，明顯加速了算法的迭代過程。黑洞機制假設在解空間內存在一個黑洞，該黑洞以全局最優gbest為球心，R為半徑。粒子進入黑洞有一定的概率被吸引，黑洞的吸引概率由［0，1］的常數閾值P來表示。對于隨機數Y，如果Ylt;P，表明粒子被黑洞吸引，采用新的位置更新公式更新粒子位置；反之，表明粒子逃離黑洞，則使用原位置更新公式。經過黑洞機制改進后的位置更新公式為xdi（t+1）=xdi（t）+vdi（t+1）Y≥P

gbest+2R（r1－1）Ylt;P（14）

其中：gbest為全局最優；R為隨機黑洞的半徑；Y、r1為［0，1］的隨機數；P為黑洞吸引概率。黑洞機制具有加速粒子收斂進程、提高算法收斂速度的優點，所以基于黑洞機制的GSA（random black hole gravity search algorithm，RBHGSA）具有較強的全局探索能力，但黑洞機制很可能導致粒子過早到達當前全局最優附近，增加了粒子陷入局部最優的可能性，RBHGSA無法克服GSA易早熟收斂的缺點。為了改善黑洞機制易使算法早熟收斂的問題，本文提出改進自適應黑洞機制，具體表示為

δ2t=1N∑Ni=1fiti（t）－fit（t）f（15）

f=max（fiti（t）－fit（t），1）（16）

xdi（t+1）=xdi（t）+vdi（t+1）δ2tlt;c

gbest+（2×rand－1）×（gbest－rand×xdi（t））δ2t≥c（17）

其中：δ2t為第t代粒子的適應度方差；fit（t）為所有粒子在第t次迭代時適應度值的平均值；c為適應度方差閾值。

改進自適應黑洞機制引入適應度方差δ2t取代黑洞吸引概率P，通過當代粒子的進化情況選擇合適的位置更新策略，實現粒子位置更新策略的自適應選擇。同時改進原黑洞位置更新公式，使得粒子以更為隨機的步長向全局最優移動，降低粒子陷入局部最優的可能性。當δ2t≥c時，表明粒子較為分散，粒子陷入局部最優的可能性小，此時通過改進黑洞位置更新策略快速抵達全局最優附近，算法的收斂速度得到提高；當δ2tlt;c時，表明粒子較為集中，粒子已移動至全局最優附近，此時通過原位置更新策略在局部區域仔細尋優，尋優精度得到提高。綜上，相較于基本黑洞機制，改進自適應黑洞機制使得粒子的位置更新更為合理、有效，算法可以得到更好的優化效果。

2.3基于學習思想的最優粒子與最差粒子更新策略

教與學優化算法（teaching-learning-based optimization algorithm，TLBO）是Rao等人［15］于2012年提出的群智能優化算法，TLBO通過老師向學生教學和學生與學生之間相互學習兩個階段完成尋優。本文受到TLBO中教學與學習的啟發，將TLBO中的教學與學習融入到GSA的粒子更新策略中，提出了基于學習思想的最優粒子與最差粒子更新策略，通過最優粒子的自我學習和最差粒子向最優粒子的學習，提高GSA的尋優精度和收斂速度。

2.3.1基于自我學習的最優粒子更新

在TBLO的教學階段，每位學生根據自身成績向老師進行差異性學習，從而提高全班成績。但是隨著迭代次數的增加，老師與學生之間的差距越來越小，導致種群多樣性迅速喪失，降低了算法的局部勘探能力。為了提高算法的尋優性能，老師也需要提高自己的能力，從而得到更好的優化效果。在GSA中，最優粒子相當于TLBO中的老師，吸引其他粒子向其移動。基于以上分析，本文提出了基于自我學習的最優粒子更新策略，具體表示為

S=sintT×π2（18）

xnew=gbest+gbest·（（1－S）×C（0，1）+S×G（0，1））（19）

x′best=gbestf（gbest）lt;f（xnew）

xnewf（gbest）gt;f（xnew）（20）

其中：S為自適應權重系數；xnew為經過學習后的全局最優位置；C（0，1）為基于柯西分布的變異算子；G（0，1）為基于高斯分布的變異算子；f（gbest）、f（xnew）分別為最優粒子和經過學習后的最優粒子的適應度值；x′best為經過選擇后的全局最優位置。

基于自我學習的最優粒子更新策略通過式（19）對全局最優進行自我學習。在迭代初期，t值較小，此時柯西算子作用較大，通過柯西算子較大的變異尺度對全局最優進行擾動，避免算法落入局部最優，增強了算法的全局探索能力；在迭代后期，t值較大，此時高斯算子作用較大，通過高斯算子較小的變異尺度在局部范圍內進行搜索，算法的收斂精度得到提高；在迭代中期，柯西算子和高斯算子出力均勻，能夠更好地平衡算法的全局探索能力和局部尋優能力。最后根據式（20）選取學習前、后中的較優解作為新的全局最優，全局最優的適應度值水平得到提高，以達到最優粒子自我學習的目的。通過上述改進，可以有效降低GSA陷入局部最優的可能性，提高了算法的局部尋優能力，算法的收斂精度得到提高。

2.3.2最差粒子向最優粒子的學習

在TLBO的學習階段，所有學生都會隨機選擇一名同學相互學習，以提高自身學習成績。受到TLBO中學生相互學習的啟發，本文提出了最差粒子向最優粒子學習的策略，對于全局最差粒子的學習，具體表示為

xnew1=xworst+（gbest－xworst）⊕Levy（β）（21）

x′worst=xworstf（xworst）lt;f（xnew1）

xnew1f（xworst）gt;f（xnew1） （22）

其中：xnew1為經過學習后的最差粒子的位置；xworst為最差粒子的位置；⊕表示為點對點乘法；x′worst為經過選擇后的全局最差位置；f（xworst）、f（xnew1）分別為最差粒子和經過學習后的最差粒子的適應度值；Levy（β）表示服從參數為β的Lévy分布的隨機路徑。Levy（β）表示如下：

Levy（β）～u|v|1β（23）

u、v服從正態分布，分別表示為

u～N（0，σ2u）；v～N（0，σ2v）（24）

σu=Γ（1+β）+sinπ×β2Γ1+β2×β×2β－12；σv=1（25）

其中：Γ為伽馬函數。最差粒子向最優粒子的學習策略通過式（21）對全局最差粒子進行學習。利用Lévy飛行更新全局最差粒子的位置，加速全局最差粒子向全局最優粒子移動，減少了算法的迭代時間，提高了算法的收斂速度。同時，Lévy飛行的隨機步長可以產生更隨機的搜索過程，有利于保持種群多樣性，避免算法陷入局部最優。通過式（22）比較學習前、后的最差粒子的適應度值，選擇較優解作為新的全局最差，完成最差粒子向最優粒子的學習。通過上述改進提高了算法的收斂速度，增強了算法的全局探索能力。

2.4群體遷徙

在GSA尋優過程中，由于慣性質量的累積效應［16］，以及GSA缺少有效的加速機制，導致粒子的速度隨著迭代次數的增加而迅速減慢，削弱了GSA的全局勘探能力，使得GSA不能有效找到問題的最優解。為了增強GSA的收斂速度、提升算法的勘探性能，本文提出群體遷徙機制，加速種群向全局最優收斂，具體表示為

pxdi（t+1）=（1－ζ）×gbest+（1+ζ）×xdi（t+1）2+rand（26）

ζ=rand（－0.5，0.5）（27）

其中：pxdi（t+1）為經過群體遷徙后的粒子的位置；ζ為調控因子。

群體遷徙通過全局最優解和當前位置引導種群整體向全局最優靠近，增加了算法的收斂速度，有效改善GSA在迭代后期粒子移動速度慢的問題，為算法提供了一種有效的加速收斂機制。

3算法流程與時間復雜度分析

3.1算法流程

IABHGSA的流程如圖3所示。算法具體步驟如下：a）種群初始化，根據式（13）對種群進行初始化；b）根據適應度函數計算所有粒子的適應度值，選擇出全局最優gbest；c）按照式（5）（2）（6）（9）（7）更新慣性質量M、引力系數G、粒子所受合力F、粒子的加速度a和速度v；d）按照式（15）計算當代粒子適應度方差δ2t；e）根據δ2t的值選擇式（8）或者式（17）更新粒子位置x；f）按照式（26）對粒子進行群體遷徙；g）根據適應度函數更新所有粒子的適應度值；h） 根據式（19）（21）對最優粒子和最差粒子進行學習，并按照式（20）（22）更新全局最優和全局最差；i）判斷當前運算是否滿足停止條件，如果滿足，輸出最優結果，終止運算，若不滿足，則跳轉到步驟c）繼續運算。

3.2時間復雜度分析

設算法種群規模為N，維度為d，最大迭代次數為T。對于GSA，GSA初始化參數的時間復雜度為O（1），計算GSA中各個粒子的適應度值的時間復雜度為O（N），GSA完成T次尋優的時間復雜度為O（N×d×T）。綜上，GSA總的時間復雜度為O（1）+O（N）+O（N×d×T）=O（N×d×T）（28）

對于IABHGSA，增加改進Tent映射生成初始種群的時間復雜度為O（N×d）；增加改進自適應黑洞機制的時間復雜度為O（N×d×T）；增加基于學習思想的最優與最差粒子更新策略的時間復雜度為O（d×T）；增加群體遷徙機制的時間復雜度為O（N×d×T），則新增改進策略的總時間復雜度為

O（N×d）+O（N×d×T）+O（d×T）+O（N×d×T）=O（N×d×T）（29）

GSA的時間復雜度為O（N×d×T），本文所提改進策略的總時間復雜度為O（N×d×T），所以IABHGSA的時間復雜度為O（N×d×T）。與本文改進策略有相似之處的ITC-GSA［17］的時間復雜度為O（N×d×T）。綜上表明，相較于GSA和目前較新的ITC-GSA，IABHGSA都沒有增加計算負擔。

4實驗仿真與分析

為了驗證IABHGSA的優越性能，本文設置五個仿真實驗：a）將IABHGSA與四種近五年內改進的GSA進行比較；b）將IABHGSA與五種啟發式算法進行比較；c）將IABHGSA與兩種改進RBHGSA進行比較；d）將四種結合單策略的GSA與基本GSA進行比較；e）驗證GSA、四種改進GSA、兩種改進RBHGSA以及IABHGSA在高維測試函數上的性能。

4.1仿真實驗環境

本文在IntelCoreTMi7-5500U CPU@2.40 GHz，內存8.00 GB，Windows 10操作系統和MATLAB 2016a的環境下對本文算法進行仿真實驗。

4.2基準測試函數

實驗選取八個不同類型的基準測試函數，包括四個單峰基準測試函數、兩個多峰基準測試函數和兩個低維多峰基準測試函數。通過不同類型的基準測試函數全面驗證IABHGSA的優越性和本文所提改進策略的有效性。各個基準函數的相關信息如表1所示。

4.3算法參數設置

本文選取了四種近五年內的改進GSA（CAGSA-PSO［18］、SCGSA［19］、IGSA［20］、t-IGSA［21］）、五種啟發式算法（PSO［22］、FPA［23］、BOA［24］、MA［25］、GWO［26］）以及兩種改進RBHGSA（ABHGSA［27］、RBHPSO-GSA［28］）與IABHGSA進行對比實驗。為了使實驗結果客觀、可信，設本文所有實驗算法的種群規模N=30，算法最大迭代次數T=1 000，算法其他主要參數如表2所示。

算法主要參數

GSAG0=50，α=10

CAGSA-PSOγ=100，η=0.1，ωmax=0.9，ωmin=0.4，c1=1.5，c2=0.5，其余參數同GSA

SCGSAkmax=2，kmin=0，其余參數同GSA

IGSAωmax=0.9，ωmin=0.5，c1=0.5，c2=1.5，其余參數同GSA

t-IGSAc1=exp（－t/T），c1=1－t/T，c3=1.8×exp（－t/T），其余參數同GSA

PSOωmax=0.9，ωmin=0.4，c1=c1=2

FPAp=rand，α=0.01，λ=1.5

BOAp=0.6，c=0.01，a=0.1

MAa1=1，a2=1.5，a3=1.5，β=2，d=5，fl=1，L∈U（－1，1）

GWOamax=2，amin=0

ABHGSAc1=1.5，c2=0.5，n=2，p=0.1，R=0.01，其余參數同GSA

RBHPSO-GSAα1=1.5，α2=0.5，p=0.1，R=0.01，其余參數同GSA

IABHGSAc=1×10－6，β=1.5，其余參數同GSA

4.4IABHGSA與其他改進GSA的比較

為了驗證IABHGSA的優越性，本節選取GSA、CAGSA-PSO、SCGSA、IGSA、t-IGSA和IABHGSA對八個基準測試函數進行仿真實驗。為了使實驗結果更加客觀，每種算法在各個基準測試函數上獨立運行30次。比較各算法在獨立的30次運行中的平均值（mean）、最優值（best）和標準差（std），其中mean可以反映算法的尋優精度，best可以反映算法的求解質量，std可以反映算法的穩定性。不同算法尋優結果對比如表3所示。

在本文選取的基準測試函數中，f1～f4為單峰函數，f5～f8為多峰函數。從表3中可以看出，無論是求解單峰函數還是多峰函數，四種改進GSA和IABHGSA對比基本GSA的尋優精度都有一定的提升，其中IABHGSA的尋優結果是六種算法中最好的，驗證了IABHGSA較強的探索和開發能力。在f1～f6上，部分改進GSA并未起到較好的優化效果，提升程度不大。對于f3，GSA的尋優結果與理論最優相差較大，表明GSA在優化f3時存在固有缺陷；四種改進GSA對f3的優化結果也與理論最優出現了較大差距，表明四種改進GSA并未克服GSA在f3上存在的問題。而本文IABHGSA在f3上的尋優精度高出GSA和四種改進GSA約20個數量級，極大地提高了GSA在f3上的尋優性能，克服了基本GSA在f3上的固有缺陷。在f7、f8上，六種算法的尋優結果的平均值差距不大，體現了GSA這類算法在低維多峰函數上具有較好的尋優性能。

綜上，四種改進GSA在一定程度上提升了尋優性能，但是在面對GSA的固有缺陷時無法有效改善，本文IABHGSA可以有效提高算法的尋優精度并且能夠有效解決GSA存在的問題。所以從整體上看，IABHGSA具有較強的競爭優勢，這是由于本文所提改進策略的作用，IABHGSA通過改進自適應黑洞機制選擇合適的位置更新策略，使得粒子位置更新更為合理、有效。當算法陷入局部最優時，通過基于自我學習的最優粒子更新策略逃離局部最優，有效提高算法的尋優精度。

為了更直觀地展示不同算法的尋優過程，圖4～11列出了以上六種算法在f1～f8上的迭代進化曲線。從圖4～9可以看出IABHGSA具有不同于其他改進GSA的收斂特性，在f1～f6上，IABHGSA在迭代前期快速收斂，其收斂速度明顯快于其他五種算法，并且從圖中也可以更直觀地看出IABHGSA的收斂精度得到了較大提升。對于f7和f8，六種算法都以較快的速度收斂至全局最優附近，收斂速度基本相同。以上表明IABHGSA提升了算法的收斂速度，IABHGSA具有較快的收斂速度主要是因為最差粒子向最優粒子學習策略和群體遷徙的作用。通過最差粒子向最優粒子學習策略，使得最差粒子快速移動至最優粒子附近，加速算法的收斂；同時由于群體遷移的作用，使種群在位置更新后整體向全局最優移動一定的距離，增強了算法的全局尋優能力。從圖4、6、7、9可以看出，IABHGSA在迭代過程中多次跳出局部最優，在跳出局部最優后仍進行有效的收斂，該過程很好地證明了本文提出的改進策略可以幫助算法逃離局部最優，驗證了IABHGSA良好的尋優性能。綜上，IABHGSA提高了GSA的收斂速度，加強了GSA的全局尋優能力，并有效克服了GSA易早熟收斂的問題。

標準差可以檢驗算法的穩定性。從表3中可以看出，對于f1～f6，IABHGSA運行結果的標準差是六種算法中最小的，高出其他算法多個數量級;對于f7，IABHGSA的穩定性與其他五種算法基本持平;對于f8，IABHGSA的穩定性較差，表明本文提出的改進策略并未對GSA在f8上的運行產生明顯的優化效果。根據無免費午餐（no-free-lunch，NFL）定理，沒有任何一種算法或者改進策略能在所有問題上達到最優，所以，在f8上IABHGSA的穩定性較差是可以接受的。基于以上分析，相較于GSA和四種改進GSA，IABHGSA的穩定性得到了提升，算法的魯棒性增強。IABHGSA較強的穩定性得益于最優粒子的自我學習，使算法有能力逃離局部最優，在每次尋優中都可以得到精度更高的解，從而使算法的穩定性和魯棒性得到大幅度提升。

4.5IABHGSA與其他啟發式算法的比較

為了進一步驗證IABHGSA的優越性，本節采用五種啟發式算法與IABHGSA進行對比分析，通過不同類型的算法比較進一步驗證IABHGSA的優越性。所選用的啟發式算法包括PSO、FPA、BOA、MA以及GWO。選取以上五種算法對八個基準函數進行仿真實驗，并選取表3中IABHGSA的實驗結果與五種啟發式算法進行對比。為了使實驗結果更加客觀，每種算法在各個基準測試函數上獨立運行30次。比較各算法在獨立的30次運行中的平均值、最優值和標準差，不同算法尋優結果對比如表4所示。

PSO是一種經典的啟發式算法，通過群體中個體自身的認知和個體之間的信息交流完成尋優，PSO收斂性好，結構簡單，需要設置的參數少。FPA模擬自然界中顯花植物花朵傳粉過程，通過自花授粉、異花授粉完成尋優，具有收斂速度快等優點。BOA、MA、GWO是三種較新的基于種群的優化算法，其中BOA模擬蝴蝶的覓食行為，通過香味的強度完成全局搜索和局部搜索，BOA具有較高的收斂精度；MA模擬雄、雌蜉蝣的飛行行為和交配過程，通過交配產生下一代完成尋優，MA尋優能力強、收斂速度快；GWO模擬灰狼的領導層級和狩獵行為以此尋優最佳解決方案，GWO收斂速度快、尋優效果好。IABHGSA和上述五種啟發式算法都屬于群智能優化算法，其共同缺點為易早熟收斂、易陷入局部最優。從表4中可以看出，IABHGSA的尋優效果是六種算法中最好的。除IABHGSA在f1和f4上的尋優結果，IABHGSA在其他函數上都得到了六種算法中的最佳尋優精度。對于f2、f3、f5、f6，IABHGSA的尋優精度高出其他算法多個數量級，其尋優性能的優勢明顯。對于f1和f4，雖然IABHGSA的尋優結果不是六種算法中最佳的，但仍保持著較高的尋優精度。群智能優化算法通過最優個體的引導完成全局尋優，IABHGSA在此思想的基礎上引入了對最優個體的自我學習，使最優個體可以根據自身進化情況有效更新自身位置，避免由于最優個體的錯誤引導使算法陷入局部最優中，有效增強了IABHGSA的局部尋優能力，顯著提高了IABHGSA的尋優精度。

在穩定性方面，在f1～f6上IABHGSA的標準差是六種算法中最低的，穩定性最好；在f7上IABHGSA的穩定性略差于BOA，但IABHGSA的尋優精度優于BOA；在f8上IABHGSA的穩定性不及PSO和MA，但是在其他函數上IABHGSA的尋優精度和穩定性都優于PSO和MA。以上表明，雖然IABHGSA在部分函數上的穩定性不及其他算法，但是從總體上看，IABHGSA在每次尋優中都可以得到精度較高的結果，有效提高了IABHGSA優化成功的概率，使IABHGSA的穩定性更好、魯棒性更強。

圖12～14為六種算法在f1、f2、f5上的迭代進化曲線。從圖12、13中可以觀察到，PSO、FPA、BOA、MA因為收斂速度慢而得到較差的解。從圖14可以看出，雖然GWO的收斂速度很快，但是其陷入了局部最優。從圖12～14可以看出，IABHGSA具有較快的收斂速度，展示出了良好的收斂特性，并且在迭代后期具有較高的尋優精度。因此，與五種啟發式算法相比，IABHGSA的收斂性能較好，驗證了IABHGSA的優越性。

4.6IABHGSA與改進RBHGSA的比較

為了驗證IABHGSA在同類型算法中的優越性，選取兩種改進RBHGSA以及IABHGSA對f1～f8進行仿真對比。其中，兩種改進RBHGSA分別為ABHGSA和RBHPSO-GSA。ABHGSA和RBHPSO-GSA分別在f1～f8上獨行運行30次，得到兩種算法運行結果的平均值、最優值和標準差。將上述實驗結果與本文表3中IABHGSA的實驗結果進行對比，不同算法的尋優結果對比如表5所示。

ABHGSA、RBHPSO-GSA和IABHGSA都是在RBHGSA的基礎上做出的改進，基于同類型算法的改進算法之間的對比更能體現改進算法的優越性和所用改進策略的有效性。從表5可以看出，相較于ABHGSA和RBHPSO-GSA的尋優結果，IABHGSA在f1～f8上的尋優結果都是最好的，表明IABHGSA在同類型算法中競爭優勢明顯，驗證了IABHGSA具有較強的尋優性能。同時從表5可以看出，對于使用基本隨機黑洞的ABHGSA和RBHPSO-GSA，其尋優結果相較于表3中GSA的實驗結果提升程度有限，大概提高了1個數量級左右。這是因為基本隨機黑洞策略只能隨機地在兩種位置更新策略中進行選擇，這樣會導致算法過早抵達當前全局最優附近，從而早熟收斂，削弱了算法的局部勘探能力。IABHGSA不同于以上兩種改進RBHGSA、IABHGSA對基本隨機黑洞策略進行改進，根據當代粒子適應度方差選擇合適的位置更新策略，使粒子位置的更新更符合粒子的迭代情況，避免因隨機選擇位置更新策略而導致算法陷入局部最優，從而有效提高了算法的局部尋優能力。同時，基于自我學習的最優粒子更新策略可以避免算法陷入局部最優，也降低了算法陷入局部最優的可能性。兩種改進策略使IABHGSA的尋優精度得到較大的提升，驗證了IABHGSA在同類型算法中優異的尋優性能。在算法的穩定性方面，IABHGSA的綜合表現較好，僅在f8上的穩定性不如兩種改進RBHGSA。綜上表明，IABHGSA的穩定性在超過85%的測試函數上均有明顯的優勢，算法的尋優效果更為穩定，在面對各種優化問題時的穩定性和魯棒性更好。

4.7不同改進策略的比較

通過GSA與四種結合單策略改進的GSA進行比較來驗證本文所提改進策略的有效性。將結合改進Tent映射生成初始種群的GSA命名為GSA1；結合改進自適應黑洞機制的GSA命名為GSA2；結合基于學習思想的最優與最差粒子更新策略的GSA命名為GSA3；結合群體遷徙的GSA命名為GSA4。將GSA與四種結合單策略的GSA進行對比實驗，并給出GSA1、GSA2、GSA3、GSA4在f1～f8上獨立運行30次后得到的尋優結果的平均值、最優值和標準差，與表3中GSA的實驗結果進行對比，相關數據如表6所示。由于篇幅原因，為了更直觀地比較不同改進策略對GSA收斂速度的影響，圖15～18給出各算法對f1、f2、f5、f7的迭代進化曲線。

從表6可以看出，在f1～f6上四種結合單策略改進的GSA的尋優精度和穩定性都得到了提升，表明結合單策略改進的GSA的尋優性能和魯棒性更好。GSA2和GSA3在f1～f6上的尋優效果較好，驗證了改進自適應黑洞機制和基于自我學習的最優粒子更新策略可以有效改善算法易早熟收斂的缺點，提升了算法的尋優精度。對于f7和f8，GSA和四種結合單策略改進的GSA的尋優精度基本相同。在穩定性上，GSA2在f7和f8上表現不佳，但GSA2在其他函數上的收斂精度和穩定性都優于GSA，根據NFL定理，由此說明GSA2中的改進策略仍是有效的。

從圖15～18中可以看出，四種單策略改進的GSA的收斂速度優于GSA，表明本文所提的改進策略可以有效提高算法的收斂速度，增強了GSA的全局尋優能力。對于圖17，GSA1的收斂速度得到提升，驗證了改進Tent映射生成初始種群可以增強算法的全局探索能力。觀察圖17和18，GSA2和GSA3的曲線上存在多個轉折點，表明改進自適應黑洞機制和基于自我學習的最優粒子更新策略可以有效地幫助算法逃離局部最優，提升算法的尋優精度。同時，GSA4在f1、f5和f7上收斂速度提升明顯，表明群體遷徙策略可以加速算法收斂，為算法提供了有效的加速收斂機制，克服了GSA缺少加速機制的缺點。

總結而言，GSA3的尋優結果的有效性顯著，在尋優精度、收斂速度、穩定性上都有較大提升。GSA1的尋優結果是四種單策略改進的GSA中效果最差的，但其三個評價指標都略優于GSA。GSA2在f7和f8上表現較差，但在其他函數上的尋優精度、收斂速度、穩定性相較于GSA得到了較大提升。GSA4在f2上收斂速度與GSA持平，但在f1、f5、f7上收斂速度高于GSA，并且GSA4在f1～f8上有較高的尋優精度和穩定性。綜上，雖然部分改進策略在某些函數上表現不佳，但是從總體上看是有效的，驗證了本文所提改進策略的有效性。

4.8高維測試函數實驗結果及分析

本文IABHGSA在低維函數上有較好的尋優精度、收斂精度和穩定性，但是一般的改進策略在面對實際工程問題，特別是高維測試函數時極易失效。為了進一步驗證IABHGSA的優越性和本文所提改進策略的有效性，本節選取GSA、CAGSA-PSO、SCGSA、IGSA、t-IGSA、ABHGSA、RBHPSO-GSA以及IABHGSA對f1～f6進行高維測試函數的仿真實驗。高維維度設置為500維，關于其他參數的設置，已在4.3節中詳細闡述。為了使實驗結果更加客觀，每種算法在各個高維測試函數上獨立運行30次。比較各算法在獨立的30次運行中的平均值、最優值和標準差，不同算法尋優結果對比如表7所示。

從表7可以看出，在高維函數上，IABHGSA的收斂精度依舊較高，在f1～f6上都收斂至理論最優附近，表明IABHGSA在高維函數上依然有較好的尋優性能。對于GSA和六種改進GSA，其失效現象較為明顯，尤其在f2上。f2是連續平滑的單模態函數，當自變量趨近于無窮大時，函數會形成大量局部極值區域，易陷入局部最優且不易跳出，在高維測試函數下求解難度較大[29]。GSA、CAGSA-PSO、SCGSA、IGSA在f2上嚴重失效，幾乎未起到優化效果；雖然t-IGSA、ABHGSA和RBHPSO-GSA的尋優結果優于GSA、CAGSA-PSO、SCGSA、IGSA，但是失效現象依舊較為明顯，這也證明了一般的改進策略在高維函數上極易失效。IABHGSA在f2上的收斂精度高出GSA和六種改進GSA多個數量級，收斂精度遠高于GSA和六種改進GSA，這是因為基于自我學習的最優粒子更新策略可以幫助算法逃離局部最優，增強算法的局部尋優能力，提高算法的收斂精度。同時，IABHGSA在f1～f6尋優結果的標準差都低于其他七種算法，表明在高維函數上IABHGSA的穩定性依舊較強、魯棒性好。綜上，對于高維函數，IABHGSA的尋優性能依舊強于基本GSA和六種改進GSA。以上表明IABHGSA可以有效地處理復雜的高維問題，驗證了IABHGSA的優越性和本文所提改進策略的有效性。

5結束語

本文提出了一種基于改進自適應黑洞機制的引力搜索算法，使用基于logistic映射改進的Tent映射進行種群初始化，改善算法的全局勘探能力;引入改進自適應黑洞機制，使粒子按照迭代進化情況選擇位置更新策略，使得位置更新更為合理，同時提升了算法的尋優精度;引入基于學習思想的最優與最差粒子更新策略，有效避免算法陷入局部最優和提升算法的收斂速度;采用群體遷徙機制，有效增強了算法的全局探索能力，為算法提供了有效的加速機制。最后，通過仿真驗證了IABHGSA的優越性和本文所提改進策略的有效性。由于IABHGSA的研究處于初始階段，接下來的研究方向主要是拓展IABHGSA在實際問題中的應用。

參考文獻：

[1]Rashedi E， Nezamabadi-Pour H， Saryazdi S. GSA： a gravitational search algorithm［J］.Information Sciences，2009，179（13）：2232-2248.

［2]韓維，崔榮偉，蘇析超，等.基于雙種群模糊引力搜索算法的艦載機甲板作業調度［J］.控制與決策，2021，36（11）：2751-2759.（Han Wei， Cui Rongwei， Su Xichao， et al. Flight deck operations scheduling based on dual population fuzzy gravitational search algorithm［J］.Control and Decision，2021，36（11）：2751-2759.）

［3]趙芮，顧幸生.基于引力搜索算法的混合零空閑置換流水車間調度［J］計算機集成制造系統，2021，27（7）：1909-1917.（Zhao Rui， Gu Xingsheng. Mixed no-idle permutation flow shop scheduling problem based on gravitational search algorithm［J］.Computer Integrated Manufacturing Systems，2021，27（7）：1909-1917.）

［4]徐珊玲，李俊紅，劉夢茹，等.Wiener系統的混沌引力搜索迭代辨識［J］.系統仿真學報，2021，33（9）：2138-2146.（Xu Shanling， Li Junhong， Liu Mengru， et al. Chaotic gravitational search iterative identification for Wiener systems［J］.Journal of System Simulation，2021，33（9）：2138-2146.）

［5]劉小剛，歐陽自根.改進萬有引力搜索算法在函數優化中的應用［J］.沈陽工業大學學報，2021，43（2）：193-197.（Liu Xiaogang， Ouyang Zigen. Application of improved gravitational search algorithm in function optimization［J］.Journal of Shenyang University of Technology，2021，43（2）：193-197.）

［6]李鵬，徐偉娜，周澤遠，等.基于改進萬有引力搜索算法的微網優化運行［J］.中國電機工程學報，2014，34（19）：3073-3079.（Li Peng， Xu Weina， Zhou Zeyuan， et al. Optimal operation of microgrid based on improved gravitation search algorithm［J］.Proceedings of the CSEE，2014，34（19）：3073-3079.）

［7]劉紫陽，龐志華，陶佩，等.記憶增強的萊維飛行引力搜索算法［J］.計算機仿真，2022，39（1）：312-317.（Liu Ziyang， Pang Zhihua， Tao Pei， et al. Memory-enhanced Lévy flight gravitational search algorithm［J］.Computer Simulation，2022，39（1）：312-317.）

［8]Mirjalili S， Hashim S Z M. A new hybrid PSOGSA algorithm for function optimization［C］//Proc of International Conference on Computer and Information Application.Piscataway，NJ：IEEE Press，2010：374-377.

［9]Su Zikang， Wang Honglun. A novel robust hybrid gravitational search algorithm for reusable launch vehicle approach and landing trajectory optimization［J］.Neurocomputing，2015，162（8）：116-127.

［10]張維平，任雪飛，李國強，等.改進的萬有引力搜索算法在函數優化中的應用［J］.計算機應用，2013，33（5）：1317-1320.（Zhang Weiping， Ren Xuefei， Li Guoqiang， et al. Improved gravitation search algorithm and its application to function optimization［J］.Journal of Computer Applications，2013，33（5）：1317-1320.）

［11]Joshi S K， Bansal J C. Parameter tuning for meta-heuristics［J］.Knowledge-Based Systems，2020，189（2）：105094.

［12]高晨峰，陳家清，石默涵.融合黃金正弦和曲線自適應的多策略麻雀搜索算法［J］.計算機應用研究，2022，39（2）：491-499.（Gao Chenfeng， Chen Jiaqing， Shi Mohan. Multi-strategy sparrow search algorithm integrating golden sine and curve adaptive［J］.Application Research of Computers，2022，39（2）：491-499.）

［13]白國振，荊鵬翔.基于改進引力搜索算法的Delta機械手軌跡規劃［J］.控制工程，2017，24（9）：1823-1828.（Bai Guozhen， Jing Pengxiang. Trajectory planning of Delta manipulators based on modified gravitational search algorithm［J］.Control Engineering，2017，24（9）：1823-1828.）

［14]Zhang Junqi， Liu Kun， Ying Tan， et al. Random black hole particle swarm optimization and its application［C］//Proc of International Conference on Neural Networks and Signal Processing.Piscataway，NJ：IEEE Press，2008：359-365.

［15]Rao R V， Savsani V J， Vakharia D P. Teaching-learning-based optimization： an optimization method for continuous non-linear large scale problems［J］.Information Sciences，2012，183（1）：1-15.

［16]孫翠珍，丁君，郭陳江.改進的引力搜索算法及在面陣綜合中的應用［J］.西北工業大學學報，2020，38（5）：1018-1024.（Sun Cuizhen， Ding Jun， Guo Chenjiang. Improved gravity search algorithm and its application in planar array synthesis［J］.Journal of Northwestern Polytechnical University，2020，38（5）：1018-1024.）

［17]張娜，趙澤丹，包曉安，等.基于改進的Tent混沌萬有引力搜索算法［J］.控制與決策，2020，35（4）：893-900.（Zhang Na， Zhao Zedan， Bao Xiaoan， et al. Gravitational search algorithm based on improved Tent chaos［J］.Control and Decision，2020，35（4）：893-900.）

［18]Zhang Peng， Cui Zhiwei， Wang Yinjiang， et al. Application of BPNN optimized by chaotic adaptive gravity search and particle swarm optimization algorithms for fault diagnosis of electrical machine drive system［J］.Electrical Engineering，2022，104（2）：819-831.

［19]Jiang Jianhua， Jiang Ran， Meng Xianqiu， et al. SCGSA： a sine chao-tic gravitational search algorithm for continuous optimization problems［J］.Expert Systems with Applications，2020，144（4）：113118.

［20]王云鋒，劉丹，裴作飛，等.基于改進引力搜索算法的SVM的參數優化及應用［J］.計算機應用研究，2020，37（S1）：152-154.（Wang Yunfeng， Liu Dan， Pei Zuofei， et al. SVM based on improved gravitational search algorithm and its application［J］.Application Research of Computers，2020，37（S1）：152-154.）

［21]逯清玉，張曉明.一種自適應混合變異的引力搜索算法［J］.重慶師范大學學報：自然科學版，2017，34（3）：85-90.（Lu Qingyu， Zhang Xiaoming. An adaptive hybrid mutation gravitational search algorithm［J］.Journal of Chongqing Normal University：Natural Science Edition，2017，34（3）：85-90.）

［22]Kennedy J， Eberhart R. Particle swarm optimization［C］//Proc of IEEE International Conference on Neural Networks.Piscataway，NJ：IEEE Press，1995：1942-1948.

［23]Yang Xinshe. Flower pollination algorithm for global optimization［C］//Proc of International Conference on Unconventional Computing and Natural Computation.Berlin：Springer，2012：240-249.

［24]Arora S， Singh S. Butterfly optimization algorithm：a novel approach for global optimization［J］.Soft Computing，2019，23（3）：715-734.

［25]Zervoudakis K， Tsafarakis S. A mayfly optimization algorithm［J］.Computers amp; Industrial Engineering，2020，145（7）：106559.

［26]Mirjalili S， Mirjalili S M， Lewis A. Grey wolf optimizer［J］.Advances in Engineering Software，2014，69（3）：46-61.

［27]呂方林，羅鳳鳴，張兵城.基于隨機黑洞和自適應策略的引力搜索算法［J］.西華大學學報：自然科學版，2019，38（3）：55-60.（Lyu Fanglin， Luo Fengming， Zhang Bingcheng. Gravitational search algorithm based on random black holes and adaptive strategies［J］.Journal of Xihua University：Natural Science Edition，2019，38（3）：55-60.）

［28]李咸善，王錦龍，楊絲琪，等.基于RBHPSO-GSA算法的微電網優化運行方法［J］.智慧電力，2018，46（9）：26-32.（Li Xianshan， Wang Jinlong， Yang Siqi， et al. Optimal operation of microgrid based on RBHPSO-GSA algorithm［J］.Smart Power，2018，46（9）：26-32.）

［29]高文欣，劉升，肖子雅，等.全局優化的蝴蝶優化算法［J］.計算機應用研究，2020，37（10）：2966-2970.（Gao Wenxin， Liu Sheng， Xiao Ziya， et al. Butterfly optimization algorithm for global optimization［J］.Application Research of Computers，2020，37（10）：2966-2970.）

收稿日期：2022-03-10；

修回日期：2022-05-05

基金項目：國家自然科學基金資助項目（71771143）

作者簡介：許文俊（1998-），男，湖北襄陽人，碩士研究生，主要研究方向為智能優化算法在電力系統運行優化中的應用；王錫淮（1961-），男（通信作者），江蘇淮安人，教授，博導，主要研究方向為復雜系統建模與控制、系統優化等（wxh@shmtu.edu.cn）；肖健梅（1962-），女，遼寧大連人，教授，碩導，主要研究方向為智能控制、粗糙集理論、物流系統優化等；顧俊瑜（1997-），女，江蘇南通人，碩士研究生，主要研究方向為基于人工智能算法的微電網優化控制與重構技術．