基于隨機(jī)黑洞和自適應(yīng)策略的引力搜索算法

呂方林，羅鳳鳴，張兵城

(1.東北石油大學(xué)電氣信息工程學(xué)院，黑龍江 大慶 163318； 2.湖北華電江陵發(fā)電有限公司， 湖北 荊州 434100)

隨著工業(yè)的發(fā)展和科技的進(jìn)步，實(shí)際生產(chǎn)中出現(xiàn)了許多復(fù)雜的計(jì)算或優(yōu)化問題，這些問題往往是多變量、不可微的非線性問題。為解決這類復(fù)雜問題，大量的智能優(yōu)化求解算法應(yīng)運(yùn)而生，許多學(xué)者受自然現(xiàn)象的影響和啟發(fā)，提出了大量的啟發(fā)式優(yōu)化算法，如遺傳算法、粒子群算法等。

引力搜索算法[1](gravitational search algorithm，簡稱GSA)是近年來興起的一種元啟發(fā)式優(yōu)化算法，以其原理清晰、結(jié)構(gòu)簡單、優(yōu)化性能好等優(yōu)點(diǎn)逐漸受到廣大學(xué)者的肯定和推廣。GSA算法遵循萬有引力定律，在運(yùn)行時(shí)通過粒子間的萬有引力傳遞個(gè)體之間的信息，從而實(shí)現(xiàn)群體信息共享，達(dá)到尋優(yōu)探索的目的，具有很強(qiáng)的全局優(yōu)化能力。研究者已經(jīng)通過試驗(yàn)證明引力搜索算法在收斂速度和收斂精度上均優(yōu)于粒子群(PSO)、遺傳(GA)、中心引力(CFO)等優(yōu)化算法[2]，再加上其參數(shù)設(shè)置較少，原理簡單，易于實(shí)現(xiàn)，因此，越來越受到關(guān)注[3]。

然而后期收斂速度慢、易早熟等缺點(diǎn)是啟發(fā)式尋優(yōu)算法的通病，引力搜索算法也面臨著這樣的問題[4]。為此，學(xué)者們提出了各種改進(jìn)方案。文獻(xiàn)[5]結(jié)合粒子群算法的學(xué)習(xí)和記憶功能優(yōu)勢，提出一種混合粒子群引力搜索算法(HPSOGSA)；文獻(xiàn)[6]引入親和度概念對GSA算法的合力計(jì)算公式進(jìn)行改進(jìn)，修正粒子收斂方向；文獻(xiàn)[7]提出一種按照模糊規(guī)則加入斥力的引力搜索算法。雖然這些改進(jìn)方法均在一定程度上改善了原始GSA算法的收斂速度或優(yōu)化精度，但都沒有從根本上解決算法的不足，對引力搜索算法的研究仍有很大的空間[8]。本文為提高引力搜索算法的整體性能，通過引入自適應(yīng)策略，改進(jìn)算法的引力常量公式，優(yōu)化算法前期探索能力和后期的開發(fā)能力，并融合隨機(jī)黑洞策略，提高了局部收斂能力，從整體上提高了算法的收斂精度和速度，改善了GSA算法的優(yōu)化性能。最后，本文通過6個(gè)典型的測試函數(shù)對改進(jìn)算法的性能進(jìn)行數(shù)值仿真試驗(yàn)，并與標(biāo)準(zhǔn)GSA進(jìn)行對比，驗(yàn)證改進(jìn)策略的可行性和有效性。

1 基本引力搜索算法

在標(biāo)準(zhǔn)GSA中，算法通過粒子之間的相互吸引作用使得種群中粒子朝著質(zhì)量更大的粒子方向移動，從而實(shí)現(xiàn)種群間的粒子信息共享。算法中的每個(gè)粒子都具有位置、慣性質(zhì)量、施力粒子、受力粒子等4個(gè)個(gè)體特征，其中粒子的位置就是所求問題的解[9-13]。如圖1所示，M1受到其他3個(gè)粒子的吸引，最終沿著合力F的方向移動。

算法開始之前，需要隨機(jī)初始化產(chǎn)生初始的位置和速度信息，然后根據(jù)式(1)計(jì)算出每個(gè)粒子的慣性質(zhì)量，并做歸一化處理，如式(2)所示。

(1)

圖1 粒子運(yùn)動圖

(2)

式中：fiti(t)表示粒子Xi在t的適應(yīng)值；best(t)表示時(shí)刻t中的最佳解；worst(t)表示t時(shí)刻中的最差解。從式(1)中可以看到，將粒子的適應(yīng)值規(guī)范化到[0,1]之間，然后式(2)把其占總質(zhì)量的比重當(dāng)作粒子的慣性質(zhì)量Mi(t)，即做歸一化處理。

求最小值問題時(shí)，best(t)、worst(t)的計(jì)算方式由式(3)、(4)給出。

(3)

(4)

然后，根據(jù)式(5)計(jì)算在第d維上第i個(gè)粒子與第j個(gè)粒子之間的萬有引力。

(5)

引力常量G(t)更新公式為

(6)

式中：G0為引力常數(shù)的初始值；alfa為速率衰減常數(shù)；max_it為最大迭代次數(shù)；t為當(dāng)前迭代的次數(shù)。

在引力搜索算法中，第d維作用在第i個(gè)粒子上總的作用力大小的計(jì)算公式為

(7)

根據(jù)牛頓第二定律，第i個(gè)粒子在第d維上t時(shí)刻的加速度定義為

(8)

最后根據(jù)式(9)、(10)更新粒子的速度和位置。

(9)

(10)

2 算法的改進(jìn)策略

引力搜索算法是通過粒子間的萬有引力來傳遞粒子的質(zhì)量和位置信息，從而達(dá)到種群交互的目的，實(shí)現(xiàn)信息共享。每一個(gè)粒子所受到的力來自于群體中其他粒子的作用，因此個(gè)體能夠觀察其他所有粒子的位置信息及其重量信息[13-15]。算法的位置更新情況需要速度來度量，速度的更新又取決于合力的大?。灰虼?，要對算法進(jìn)行改進(jìn)，研究粒子的位置更新和合力計(jì)算是很重要的切入點(diǎn)。

綜上所述，為保證算法尋優(yōu)過程中探索和開發(fā)能力的平衡，本文采用2種策略對算法進(jìn)行改進(jìn)。

2.1 引力常數(shù)G的自適應(yīng)策略

由式(5)可知，引力常數(shù)G的大小直接影響算法中粒子受到的合力大小，從而決定著算法運(yùn)算時(shí)粒子每次移動“步長”的大小，也是影響粒子能否擺脫局部最優(yōu)、實(shí)現(xiàn)最優(yōu)精細(xì)度最直接的因素[14]。擁有良好性能的算法，在初期要進(jìn)行全面探索，后期進(jìn)行局部開發(fā)，有效平衡探索和開發(fā)能力。然而，由式(6)可知，引力常量G從剛開始就迅速下降，即在算法搜索初期就加大了開發(fā)力度，雖說這樣有利于算法快速收斂，但是缺少前期的有效探索過程，容易使算法陷入局部最優(yōu)。顯然，這種情況容易打破算法探索和開發(fā)的平衡，不是我們所期望的，為解決此問題，設(shè)計(jì)引力常量的自適應(yīng)變化公式，為

(11)

式中：n為描述勘探和開發(fā)比例的一個(gè)參數(shù)，其余符號意義同式(6)。值得說明的是，當(dāng)n=1時(shí)，式(11)將退化成式(6)。

引入自適應(yīng)引力常量，改進(jìn)引力常量的計(jì)算公式，通過改變算法比例系數(shù)n來調(diào)整算法的探索與開發(fā)能力，自適應(yīng)調(diào)整算法的尋優(yōu)步長，使算法在初期加大搜索力度，后期加大開發(fā)力度，避免算法在尋優(yōu)初期就陷入局部最優(yōu)，從而有利于提高算法的全局尋優(yōu)能力。

2.2 隨機(jī)黑洞策略

基本引力搜索算法是依靠粒子間的引力作用來傳遞粒子位置信息和質(zhì)量信息，從而達(dá)到一種信息共享，實(shí)現(xiàn)尋優(yōu)功能[16-19]，缺少對歷史個(gè)體最優(yōu)值和群體最優(yōu)值的記憶學(xué)習(xí)功能，這樣會丟掉一些有利于粒子更新的歷史信息，不利于算法的快速收斂。因此，在引入隨機(jī)黑洞策略之前先加入學(xué)習(xí)因子對算法的速度和位置更新公式進(jìn)行改進(jìn)，計(jì)算公式為：

(12)

(13)

根據(jù)黑洞理論[20-21]，粒子運(yùn)動到黑洞附近會被黑洞捕獲，加快收斂速度。同時(shí)，為保證粒子的多樣性，在粒子被黑洞捕獲后會有一個(gè)隨機(jī)的概率逃離黑洞。在算法運(yùn)行過程中，將全局最優(yōu)解gbest附近的一個(gè)粒子看作是黑洞，以黑洞為中心在半徑為R的范圍內(nèi)，粒子可能會被黑洞捕獲。常數(shù)p∈[0，1]表示黑洞的捕獲能力，即捕獲概率值；設(shè)置一個(gè)隨機(jī)數(shù)l∈[0,1]，當(dāng)l

(14)

式中：R表示黑洞半徑；r3為[0,1]的隨機(jī)數(shù)。

隨機(jī)黑洞策略的引入，使得粒子能夠更快地收斂于全局最優(yōu)，加快了粒子的迭代速度，而且粒子又有一定的概率逃逸黑洞，如此增加了粒子的多樣性[12]，使得算法在提高收斂速度的同時(shí)又不易陷入局部最優(yōu)，從而提高算法的收斂精度，有利于快速得到全局最優(yōu)解。

2.3 改進(jìn)算法的流程

本文所提出的基于自適應(yīng)策略和隨機(jī)黑洞策略的改進(jìn)引力搜索算法(a gravity search algorithm based on adaptive and random black hole，ABHGSA)流程如下：

Step1，隨機(jī)初始化粒子的位置X，設(shè)定種群規(guī)模N、維度dim和最大迭代次數(shù)max-it；

Step2，設(shè)定c1、c2、p、R和開發(fā)比例n；

Step3，由目標(biāo)函數(shù)來計(jì)算每個(gè)粒子的適應(yīng)度值fit；

Step4，參照式(11)自適應(yīng)更新引力常量G′(t);

Step5，根據(jù)式(1)和式(2)計(jì)算每個(gè)粒子的慣性質(zhì)量M(t)；

Step7，計(jì)算粒子的歷史最優(yōu)值，在其半徑R范圍內(nèi)，判斷粒子是否被黑洞捕獲，如果l

Step8，判斷算法是否滿足結(jié)束條件，不滿足則重復(fù)step3—step7，滿足則結(jié)束算法，輸出結(jié)果。

圖2為改進(jìn)算法(ABHGSA)的流程圖。

圖2 改進(jìn)算法的流程圖

2.4 時(shí)間復(fù)雜度分析

引力搜索算法的時(shí)間復(fù)雜度包括：初始化(Tini)、適應(yīng)度值計(jì)算(Teva)、加速度計(jì)算(Tacc)、每個(gè)粒子的速度(Tv)和位置更新(Tp)。

(15)

式中：D表示搜索空間的維度；N表示群體規(guī)模；Tmax表示最大迭代次數(shù)。因此，標(biāo)準(zhǔn)GSA的時(shí)間復(fù)雜度為

TGSA=O(DN2·Tmax)=O(DN2)

(16)

對于改進(jìn)的引力搜索算法，類似標(biāo)準(zhǔn)引力搜索算法，也有初始化(Tini)、適應(yīng)度值計(jì)算(Teva)、加速度計(jì)算(Tacc)、每個(gè)粒子的速度更新(Tv)和位置更新(Tp)，不過引入隨機(jī)黑洞策略后，位置更新有了變化，在黑洞范圍外的粒子參與更新迭代，在黑洞范圍內(nèi)的粒子直接被黑洞捕獲。其時(shí)間復(fù)雜度為

(17)

式中p表示參與迭代的粒子比例。ABHGSA算法的時(shí)間復(fù)雜度為

TABHGSA=O(DN2Tmax)=O(DN2)

(18)

雖然從最終計(jì)算出的時(shí)間復(fù)雜度來看，兩者相等；但從具體計(jì)算發(fā)現(xiàn)，由于p<1，所以ABHGSA的時(shí)間復(fù)雜度略小于標(biāo)準(zhǔn)GSA的。

3 算例仿真分析

3.1 參數(shù)設(shè)置

基本引力搜索算法的參數(shù)設(shè)置為：種群規(guī)模N=50；最大迭代次數(shù)max_it=1 000；alfa=20；G0=100；種群維度dim=30。

改進(jìn)的引力搜索算法的參數(shù)設(shè)置為：種群規(guī)模N=50；最大迭代次數(shù)max_it=1 000；alfa=20；G0=100；種群維度dim=30；記憶學(xué)習(xí)因子c1=0.5、c2=1.5；勘探與開發(fā)比例n=2；黑洞吸引的概率值p=0.4；施瓦茲半徑R=8。

3.2 測試函數(shù)

通過表1中的6個(gè)經(jīng)典標(biāo)準(zhǔn)測試函數(shù)[1]對改進(jìn)引力搜索算法(ABHGSA)的性能進(jìn)行測試，并與標(biāo)準(zhǔn)引力搜索算法(GSA)做對比，分析其改善情況。選擇多種函數(shù)做測試，是為了避免出現(xiàn)算法改善能力的偶然現(xiàn)象，使測試更具有說服力。其中：F1、F2是單峰函數(shù)，其搜索速度是檢驗(yàn)算法性能的重要指標(biāo)，因此用來測試算法的搜索速度；F3—F6是復(fù)雜的多峰函數(shù)，存在較多的局部最優(yōu)解，因此，可用來檢驗(yàn)算法的全局搜索能力。

3.3 仿真與分析

針對表1中的6個(gè)測試函數(shù)分別采用GSA算法和ABHGSA算法進(jìn)行求解，仿真出的適應(yīng)度值曲線對比結(jié)果如圖3—8所示。觀察發(fā)現(xiàn)引入自適應(yīng)引力常量策略和隨機(jī)黑洞策略改進(jìn)引力搜索算法(ABHGSA)后，算法的收斂速度比標(biāo)準(zhǔn)引力搜索算法更快，搜索得到的最優(yōu)解精確度更高，ABHGSA算法的種群多樣性和全局搜索能力得到改善。

為進(jìn)一步驗(yàn)證ABHGSA算法的優(yōu)化性能，分別將2種算法運(yùn)行30次，并取其最小值、平均值和方差，并標(biāo)粗各項(xiàng)的最優(yōu)結(jié)果，如表2所示。

1)單峰函數(shù)。對于F1、F2來說，其收斂速度的快慢是檢測算法性能好壞的重要指標(biāo)。從表2可以看出：函數(shù)F1無論是在最小值、平均值還是方差方面，采用ABHGSA算法的優(yōu)化結(jié)果均比標(biāo)準(zhǔn)GSA小2個(gè)數(shù)量級；F2函數(shù)的優(yōu)化結(jié)果小1個(gè)數(shù)量級。結(jié)合圖3、4可以看出，在保證找到較好的全局最優(yōu)解的情況下， ABHGSA的收斂速度比標(biāo)準(zhǔn)GSA算法更快，且精度更高。

表1 標(biāo)準(zhǔn)測試函數(shù)列表

圖3 函數(shù)F1的適應(yīng)度值曲線

圖4 函數(shù)F2的適應(yīng)度值曲線

圖5 函數(shù)F3的適應(yīng)度值曲線

圖6 函數(shù)F4的適應(yīng)度值曲線

圖7 函數(shù)F5的適應(yīng)度值曲線

圖8 函數(shù)F6的適應(yīng)度值曲線

2)多峰函數(shù)。由于存在較多的局部最優(yōu)解，優(yōu)化難度大，因此，對于函數(shù)F3—F6，尋優(yōu)的難度在于找到其全局最優(yōu)解。收斂精度是判斷其算法性能的主要指標(biāo)。通過表2中的結(jié)果顯示：F3、F4、F5、F6的優(yōu)化精度均有所提高，即ABHGSA的優(yōu)化結(jié)果均優(yōu)于標(biāo)準(zhǔn)GSA算法，尤其是F4的最小值和平均值優(yōu)化了19個(gè)數(shù)量級，方差優(yōu)化了38個(gè)數(shù)量級，優(yōu)化曲線如圖5—8所示。

表2 ABHGSA與GSA算法結(jié)果對比

4 結(jié)論

針對原始引力搜索算法收斂速度慢、精度低等缺點(diǎn)，本文引入自適應(yīng)引力常量，改進(jìn)引力常量的計(jì)算公式，通過改變算法比例系數(shù)n來調(diào)整算法的探索與開發(fā)能力，自適應(yīng)調(diào)整算法的尋優(yōu)步長，使算法在初期加大搜索力度，后期加大開發(fā)力度，有利于提高算法的全局尋優(yōu)能力；然后融合隨機(jī)黑洞策略，將最優(yōu)解附近的一個(gè)粒子作為黑洞，當(dāng)粒子運(yùn)行到黑洞周圍將會被黑洞捕獲，從而加快了粒子的迭代速度，并且被黑洞捕獲的粒子又有一定的概率逃離，增加粒子新的搜索區(qū)域，使算法更易收斂到全局最優(yōu)解，不易陷入局部最優(yōu)，提高收斂精度。通過6個(gè)標(biāo)準(zhǔn)測試函數(shù)對改進(jìn)算法進(jìn)行仿真試驗(yàn)，并與標(biāo)準(zhǔn)GSA算法做對比分析，結(jié)果表明，改進(jìn)后的ABHGSA算法能夠有效地改善GSA算法易早熟、收斂速度慢等問題，具有較好的收斂特性和優(yōu)化性能，在解決函數(shù)尋優(yōu)問題上具有很好的推廣價(jià)值。