王 蕾，潘 豐

(江南大學(xué)輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 無錫 214122)

1 概述

由文獻(xiàn)［1］提出的引力搜索算法(Gravitational Search Algorithm，GSA)是一種啟發(fā)式算法，是適合于大范圍搜索空間問題的全局搜索算法。研究證明，GSA 的全局搜索能力明顯優(yōu)于粒子群優(yōu)化算法［2］、遺傳算法［3］、蟻群算法［4］、中心引力算法［5］等智能優(yōu)化算法。目前，GSA 已成功地應(yīng)用于無人機(jī)航路規(guī)劃問題［6］、多目標(biāo)最優(yōu)能流問題［7］、電廠鍋爐廢氣排放模型［8］、原型分類［9］等。

在算法改進(jìn)方面，文獻(xiàn)［10］對GSA 引入反饋策略，均衡優(yōu)化了算法全局與局部搜索能力，文獻(xiàn)［11］在GSA 中引入了三角范數(shù)算子，進(jìn)一步提高了算法的全局搜索能力。文獻(xiàn)［12］對GSA 的記憶性進(jìn)行改進(jìn)，提出記憶改進(jìn)GSA (Memory Gravitational Search Algorithm，MGSA)，在一定程度上改善了GSA的局部搜索能力。

研究發(fā)現(xiàn)，以往的算法改進(jìn)主要針對GSA 算法的全局與局部搜索能力，但GSA 在搜索過程中，每個(gè)粒子都向質(zhì)量大的粒子靠近，在這種方式下，由于多樣性的失去，粒子群易在全局近優(yōu)點(diǎn)的吸引下陷入局部最優(yōu)，發(fā)生早熟收斂。在引力搜索算法中添加局部優(yōu)化策略和保持多樣性策略，從而在保留強(qiáng)大全局搜索能力與加強(qiáng)局部搜索能力的同時(shí)，更可以保持種群多樣性，避免早熟現(xiàn)象的發(fā)生。

本文提出了在引力搜索算法中添加多樣性和局部優(yōu)化策略的方法。主要在粒子進(jìn)化公式中引入粒子群算法［2，13］中的局部最優(yōu)解思想;在多樣性丟失時(shí)，采用細(xì)菌趨化中排斥操作［14-15］的概念，改進(jìn)粒子群整個(gè)搜索過程中的局部搜索能力，提高算法在迭代后期的種群多樣性，最后通過測試基準(zhǔn)函數(shù)驗(yàn)證改進(jìn)算法的有效性，并分析測試結(jié)果。

2 標(biāo)準(zhǔn)引力搜索算法

引力搜索算法是近年來提出的用于解決優(yōu)化問題的啟發(fā)式算法，和其他現(xiàn)有的著名啟發(fā)式優(yōu)化算法相比，引力搜索算法具有更好的全局搜索能力和更快的收斂能力［1，13］。算法中每個(gè)粒子有4 個(gè)特征:即位置、施力質(zhì)量、受力質(zhì)量和慣性質(zhì)量。每個(gè)粒子的位置就對應(yīng)了一個(gè)優(yōu)化問題的解，隨著一次次的迭代，粒子都被質(zhì)量大的粒子(代表問題的最優(yōu)解)所吸引，直到停止條件滿足，則停止迭代［1，10，13］。

引力搜索算法中粒子的初始位置是隨機(jī)生成的。假設(shè)一個(gè)由N 個(gè)粒子組成的粒子群在D 維的搜索空間以一定的速度飛行，定義第i 個(gè)粒子的位置為:

根據(jù)牛頓萬有引力定律，在第d 維空間上第j 個(gè)粒子對第i 個(gè)粒子的作用力可以定義為:

其中，Mi(t)和Mj(t)分別是粒子i 與粒子j 的慣性質(zhì)量;G(t)是在t 時(shí)刻的引力系數(shù);Rij(t)是t 時(shí)刻粒子i與粒子j 之間的歐式距離:Rij(t)=‖Xi(t)，Xj(t)‖2;ε 代表很小的常數(shù)。根據(jù)式(3)和式(4)利用適應(yīng)值更新粒子i 的慣性質(zhì)量Mi(t):

其中，fiti(t)是指粒子i 在時(shí)刻t 的適應(yīng)值;best(t)和worst(t)分別是指在時(shí)刻t 整個(gè)粒子群的最優(yōu)適應(yīng)值和最差適應(yīng)值;而mi(t)為計(jì)算粒子質(zhì)量的中間變量。粒子的慣性質(zhì)量Mi(t)越大則說明粒子對其他粒子有更大吸引力，隨著迭代的進(jìn)行，其他粒子紛紛向其靠攏。反之其自身受其他粒子的吸引力對本身影響就很小，導(dǎo)致其移動(dòng)速度也變慢。所以，粒子慣性質(zhì)量越大則移動(dòng)速度越緩慢，位置改變越小，而其他粒子向其位置聚攏。因此，粒子慣性質(zhì)量越大意味著其本身位置越接近最優(yōu)解。在求解目標(biāo)函數(shù)最小值問題時(shí)，best(t)和worst(t)定義如下:

在求解目標(biāo)函數(shù)最大值問題時(shí)，best(t)和worst(t)定義如下:

值得指出的是，引力系數(shù)G(t)決定了GSA 算法的性能，搜索開始時(shí)就應(yīng)對引力系數(shù)G(t)初始化，G(t)值隨著時(shí)間逐步減小，從而控制搜索精度。G(t)是關(guān)于初始值G0和迭代次數(shù)β 的函數(shù)，定義為:

其中，G0是引力系數(shù)初始值;α 是個(gè)常數(shù);β 是當(dāng)前迭代次數(shù);T 是最大迭代次數(shù)。

其中，kbest 是一個(gè)隨著時(shí)間增加而減少的線性函數(shù)。一開始的值為搜索空間中粒子總數(shù)，表示所有粒子相互間都有作用力，這樣就增加了粒子的全局搜索能力，避免陷入局部最優(yōu);隨著迭代過程的進(jìn)行，應(yīng)逐步增加粒子的局部搜索能力，故kbest 值線性減少，最終值應(yīng)為1，此時(shí)只有一個(gè)慣性質(zhì)量最大的粒子i 作用于其他粒子。依據(jù)粒子所受作用力公式，若粒子慣性質(zhì)量為Mi(t)，那么粒子i 的加速度為:

基于萬有引力定律的搜索策略，粒子i 在下一時(shí)刻的速度和位置的進(jìn)化公式為:

其中，randi是介于［0，1］隨機(jī)產(chǎn)生的數(shù)。

3 引力搜索算法的改進(jìn)

3.1 多樣性和局部優(yōu)化策略及其實(shí)現(xiàn)

基于群體的啟發(fā)式算法有2 個(gè)共同點(diǎn):探索與開發(fā)［1］。GSA 算法中慣性質(zhì)量大的粒子產(chǎn)生更廣的吸引范圍和更大的吸引力，更易吸引其他粒子，使其他粒子向其靠近，即向最優(yōu)解靠攏［1，13］。而根據(jù)式(2)、式(6)、式(7)可知，當(dāng)粒子i 接近最優(yōu)解時(shí)，由于所受引力加大，速度將不斷加快，粒子易在最優(yōu)位置的附近來回振蕩，導(dǎo)致粒子搜索精度不高，種群多樣性丟失。而根據(jù)式(8)、式(9)可知，引力搜索算法在迭代過程中粒子i 的下一刻位置僅取決于下一刻的速度信息和當(dāng)前的位置信息，無法捕捉到最優(yōu)位置信息幫助粒子本身尋優(yōu)至最優(yōu)位置。針對以上問題，引入PSO 算法［14，16］中群體歷史最優(yōu)位置及自身歷史最優(yōu)位置的概念，同時(shí)加入細(xì)菌趨化中的排斥操作［15］，改進(jìn)引力搜索算法中粒子的局部搜索優(yōu)化能力與提高種群多樣性。其中，多樣性的度量公式如下:

根據(jù)迭代過程中粒子群不同的多樣性選擇不同的速度更新方式。當(dāng)diversity(N)≥dmax時(shí)，粒子就向當(dāng)前最優(yōu)位置和自身歷史最優(yōu)位置靠近，轉(zhuǎn)向吸引操作，以增加局部尋優(yōu)能力。運(yùn)用式(11)、式(12)進(jìn)行速度更新和位置更新:

當(dāng)diversity(N)≤dmin時(shí)，粒子就逃離當(dāng)前最差位置和自身歷史最差位置，轉(zhuǎn)入排斥操作，以增加種群多樣性，使粒子搜索空間其他位置，有助于粒子發(fā)現(xiàn)更好的位置。運(yùn)用式(13)、式(14)進(jìn)行速度更新和位置更新:

其中，randi，r1，r2，R1，R2是介于(0，1)產(chǎn)生的隨機(jī)數(shù);c1，c2，C1，C2為學(xué)習(xí)因子，c1，C1調(diào)節(jié)粒子飛向自身最優(yōu)位置的步長，c2，C2調(diào)節(jié)粒子飛向全局最優(yōu)位置的步長分別表示在時(shí)刻t 粒子i 的歷史最優(yōu)、最差位置分別表示在時(shí)刻t 種群的歷史最優(yōu)、最差位置［13-14］。

3.2 改進(jìn)算法的分析

對于上述提出的改進(jìn)的引力搜索算法可引入微分方程對其進(jìn)行描述，采用控制理論對其搜索能力進(jìn)行分析［17］。在速度更新公式式(11)、式(13)中，采用關(guān)于和的某個(gè)函數(shù)f 來代替(t)，函數(shù)f 為線性函數(shù)組合，表示為:

其中，τ 為區(qū)間(0，1)間隨機(jī)選取的常數(shù)。現(xiàn)將式(15)分別代入式(11)、式(13)可得:

以式(16)為例進(jìn)行分析，分解可以得到:

其中，V2，V3是研究算法收斂至局部最優(yōu)位置和全局最優(yōu)位置的部分。設(shè)γ1=c1r1，γ1為常數(shù)。

(1)對于V2，更新方程為:

由此可得:

利用微分方程［17］:為單位階躍函數(shù)，可得到［18］:

根據(jù)控制理論得到系統(tǒng)傳遞函數(shù)，利用拉普拉斯反變換可得［19］:

又因?yàn)棣印?0，1)，則:

(2)分析V3時(shí)同理，參數(shù)選擇滿足就可獲得振蕩環(huán)節(jié)。

而對于式(17)，算法分析如式(16)。只要參數(shù)選擇滿足條件，系統(tǒng)就可以獲得振蕩環(huán)節(jié)。與采用一階微分方程描述的慣性環(huán)節(jié)相比，采用二階微分方程描述的振蕩環(huán)節(jié)能夠使粒子在全局最優(yōu)位置和局部最優(yōu)位置附近進(jìn)行幅度由大到小的搜索，大大提高粒子速度的利用率和算法的全局與局部搜索能力。

改進(jìn)算法的流程如圖1 所示。

圖1 引力搜索算法流程

4 實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文算法的有效性，選用以下4 個(gè)測試函數(shù)進(jìn)行測試，如表1 所示。

表1 測試函數(shù)

為更好地驗(yàn)證多樣性與局部優(yōu)化能力改進(jìn)的GSA (Diversity and Local Optimization GSA，DLOGSA)算法的優(yōu)越性，同時(shí)采用標(biāo)準(zhǔn)GSA(Standard GSA，SGSA)和MGSA 對上述4 個(gè)函數(shù)進(jìn)行尋優(yōu)。采用Windows XP 為實(shí)驗(yàn)仿真平臺(tái)，Matlab2010b 版本進(jìn)行仿真模擬。粒子種群數(shù)目設(shè)為50，每個(gè)算法獨(dú)立運(yùn)行20 次，最大迭代次數(shù)設(shè)置為1 000，表1 中n 取30。按引力系數(shù)式(5)，G0設(shè)定為100，β 設(shè)定為20，按速度更新式(11)、式(13)，取學(xué)習(xí)因子c1=c2=C1=C2=0.5。其中多樣性閾值dmax=2.5 ×10-3，dmin=5.0 ×10-5。運(yùn)行完畢后統(tǒng)計(jì)運(yùn)行結(jié)果的平均值、中值和標(biāo)準(zhǔn)方差。

對于每個(gè)測試函數(shù)，每種算法分別獨(dú)立運(yùn)行20 次，表2 給出了20 次實(shí)驗(yàn)后3 種算法對每個(gè)測試函數(shù)的優(yōu)化結(jié)果的平均值、中間值和標(biāo)準(zhǔn)方差。

表2 標(biāo)準(zhǔn)測試函數(shù)優(yōu)化結(jié)果比較

Sphere 是簡單的單峰值函數(shù)，只有一個(gè)全局最優(yōu)解，SGSA、MGSA 和DLOGSA 在搜索過程中都可快速收斂至最優(yōu)值，不會(huì)陷入局部最優(yōu)。如圖2 所示，3 種算法的過程曲線較為相似，在迭代過程中始終保持著較快的收斂速度。但DLOGSA 算法優(yōu)化結(jié)果從迭代開始就明顯優(yōu)于SGSA 和MGSA，迭代快結(jié)束時(shí)DLOGSA 算法收斂速度加快，獲得了良好的收斂效果。

圖2 Sphere 函數(shù)優(yōu)化過程曲線

Noise 函數(shù)是含有高斯噪聲的4 次函數(shù)，不考慮噪聲影響時(shí)，函數(shù)具有全局最小值f(0，0，…，0)=0。從圖3 可以看出，在這個(gè)測試函數(shù)中，MGSA 在前100 次迭代中優(yōu)化結(jié)果明顯大于 SGSA 和DLOGSA，在100 次～200 次迭代過程中3 種函數(shù)都快速收斂，很快收斂到最優(yōu)值，但在測試函數(shù)200 次迭代過程以后SGSA 和MGSA 就陷入早熟收斂。相比較而言，DLOGSA 在200 次迭代以后仍進(jìn)化振蕩向下，進(jìn)一步收斂，最終找到最優(yōu)結(jié)果，其優(yōu)化結(jié)果明顯優(yōu)于SGSA 和MGSA。

圖3 Noise 函數(shù)優(yōu)化過程曲線

Rastrigin 函數(shù)是一個(gè)多峰值函數(shù)，本次仿真模擬中選取30 個(gè)維數(shù)，故該測試函數(shù)是多峰高維函數(shù)。如圖4 所示，在整個(gè)優(yōu)化的過程中，DLOGSA 在迭代過程中一直保持很快的收斂速度，DLOGSA 算法的優(yōu)化結(jié)果也明顯優(yōu)于SGSA 和MGSA。SGSA和MGSA 收斂過程類似，在迭代200 次左右就陷入局部最優(yōu)，表現(xiàn)為進(jìn)化曲線平直，而DLOGSA 持續(xù)進(jìn)化振蕩向下。該結(jié)果表明對于這類復(fù)雜函數(shù)，DLOGSA 算法具有優(yōu)越性，這在于在進(jìn)化過程中不僅有吸引操作更有排斥操作在起作用，很好地保持了種群的多樣性，避免函數(shù)陷入早熟收斂。

圖4 Rastrigin 函數(shù)優(yōu)化過程曲線

Griewank 函數(shù)是典型的多模態(tài)函數(shù)，具有大量局部極值，可以很好地檢驗(yàn)算法的全局搜索性能。如圖5 所示，對于SGSA 算法的改進(jìn)并未影響SGSA原有的良好全局搜索性能。迭代之初，3 種算法性能接近，在迭代100 次～200 次之間，DLOGSA 的收斂速度就明顯快于 SGSA 和 MGSA，而在迭代200 次～300次之間，SGSA 已收斂到局部最優(yōu)值，DLOGSA 和MGSA 仍持續(xù)振蕩向下，進(jìn)一步收斂，最終DLOGSA 優(yōu)化結(jié)果仍優(yōu)于MGSA。

圖5 Griewank 函數(shù)優(yōu)化過程曲線

5 結(jié)束語

本文在引力搜索算法的基礎(chǔ)上，提出一種改進(jìn)對種群多樣性和粒子局部搜索能力的方法。針對引力搜索算法中粒子局部搜索能力弱和種群易陷入早熟收斂的情況，引入粒子群算法中的局部搜索思想和細(xì)菌趨化理論，使得粒子在進(jìn)行速度更新時(shí)，對歷史最優(yōu)位置和自身最優(yōu)位置都具有記憶性，加強(qiáng)局部搜索能力;引入的多樣性策略決定搜索粒子是實(shí)行吸引操作還是排斥操作，從而實(shí)現(xiàn)全局搜索與局部搜索的平衡，最大程度地保持種群多樣性。用4 個(gè)典型的標(biāo)準(zhǔn)函數(shù)進(jìn)行測試，驗(yàn)證了改進(jìn)后的算法搜索能力有較大的提高。而針對不同的應(yīng)用場合選擇合適的多樣性閾值是今后的工作重點(diǎn)。

［1］Rashedi E，Nezamabadi-pour H，Saryazdi S.GSA:A Gravitational Search Algorithm ［J］.Information Sciences，2009，179(13):2232-2248.

［2］Trelea I C.The Particle Swarm Optimization Algorithm:Convergence Analysis and Parameter Selection［J］.Information Processing Letters，2003，85(6):317-325.

［3］馬永杰，云文霞.遺傳算法研究進(jìn)展［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(4):1201-1206，1210.

［4］高 尚，江新姿，湯可宗.蟻群算法與遺傳算法的混合算 法［C］//第26 屆中國控制會(huì)議論文集.北京:北京航空航天大學(xué)，2007:701-704.

［5］Formato R A.Central Force Optimization:A New Metaheuristic with Applications in Applied Electromagnetic［J］.Ballooning，2007，77:425-491.

［6］李 沛，段海濱.基于改進(jìn)萬有引力搜索算法的無人機(jī)航路規(guī)劃［J］.中國科學(xué)，2012，42(10):1130-1136.

［7］Bhattacharya A.Solution of Multi-objective Optimal Power Flow Using Gravitational Search Algorithm［J］.IET Gener Transm Distrib，2012，6(8):751-763.

［8］牛培峰，肖興軍，李國強(qiáng).萬有引力搜索算法在電廠鍋爐NOx排放模型中的應(yīng)用研究［J］.自動(dòng)化博覽，2011，(S2):87-92.

［9］Abbas B，Nezamabadi-pour H.A Prototype Classifier Based on Gravitational Search Algorithm［J］.Applied Soft Computing，2012，12(2):819-825.

［10］顧斌杰，潘 豐.基于反饋策略的引力搜索算法及其在支持向量機(jī)中應(yīng)用［J］.計(jì)算機(jī)應(yīng)用，2013，33(3):806-809.

［11］徐 遙，安亞靜，王士同.基于三角范數(shù)的引力搜索算法分析［J］.計(jì)算機(jī)科學(xué)，2011，38(11):225-230.

［12］李春龍，戴 娟，潘 豐.引力搜索算法中粒子記憶性改進(jìn)的研究［J］.計(jì)算機(jī)應(yīng)用，2012，32 (10):2732-2735.

［13］徐 遙，王士同.引力搜索算法的改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(35):188-192.

［14］Niu B，Zhu Y L，He X X，et al.An Improved Particle Swarm Optimization Based on Bacterial Chemotaxis［C］//Proceedings of the 6th World Congress on Intelligent Control and Automation.Shenyang，China:［s.n.］，2006:3193-3197.

［15］Soujik V，Wingreen N S.Responding toChemical Gradients Bacterial Chemotaxis［J］.Current Opinion in Cell Biology，2012，24(2):262-268.

［16］Liang J J，Qin A K，Suganthan P N，et al.Comprehensive Learning Particle Swarm Optimize for Global Optimization of Multimodal Functions［J］.IEEE Transactions on Evolutionary Computation，2006，10(3):281-295.

［17］同濟(jì)大學(xué)數(shù)學(xué)系.高等數(shù)學(xué)［M］.北京:高等教育出版，2007.

［18］崔志華，曾建潮.基于控制理論的微粒群算法分析與改進(jìn)［J］.小型微型計(jì)算機(jī)系統(tǒng)，2006，27(5):849-853.

［19］胡壽松.自動(dòng)控制原理［M］.北京:科學(xué)出版社，2008:89-99.