改進萬有引力搜索算法在函數(shù)優(yōu)化中的應用*

劉小剛， 歐陽自根

(1. 西京學院 理學院， 西安 710123； 2. 南華大學 數(shù)理學院， 湖南 衡陽 421000)

實際工程領域中，許多求解最優(yōu)類的問題均可以看成是對一個連續(xù)函數(shù)進行優(yōu)化，如采礦工程的最優(yōu)化設計，優(yōu)化工程控制器的最優(yōu)參數(shù)(PID參數(shù)等)，工程最優(yōu)控制問題的數(shù)學建模和工程混合料最優(yōu)配料等.大多數(shù)最優(yōu)求解問題描述如下：

minf(x)

(1)

s.t.mi≤xi≤ni(i=1，2，…，d)

式中：f(x)為目標函數(shù)；x=(x1，x2，…，xd)為d維變量；ni和mi為變量的上下限.

由于問題(1)具有復雜性，傳統(tǒng)的方法已經(jīng)不能解決，所以越來越多的研究人員從自然界中生物的群體行為得到啟發(fā)，將其模型轉(zhuǎn)化為新型的智能算法，并提出許多啟發(fā)式優(yōu)化算法，如遺傳算法(genetic algorithm，GA)，蟻群算法(ant colony optimization，ACO)，粒子群算法(particle swarm optimization，PSO)等.這些算法都是針對一些特定問題提出的，目前尚沒有任何一種算法能夠成功地解決所有的優(yōu)化問題.因此，繼續(xù)探索新的啟發(fā)式智能優(yōu)化算法是非常有必要的.

萬有引力搜索[1](gravitational search algorithm，GSA)最開始是由伊朗克曼大學的教授Esmat Rashedi等于2009年提出的.它是一種依托于物理學中的萬有引力定律與牛頓第二定律的新型啟發(fā)式優(yōu)化算法.該優(yōu)化算法通過種群中各個粒子之間的相互作用力(萬有引力)來指導群體進行智能優(yōu)化搜索，與粒子群算法相似.研究[2]證明，GSA算法的優(yōu)化性能明顯優(yōu)于粒子群和遺傳等優(yōu)化算法.從目前來看，萬有引力搜索算法的研究已經(jīng)在快速發(fā)展中.張維平等[3]通過反向?qū)W習策略、精英策略以及邊界變異策略對GSA優(yōu)化算法進行改進，有效加快收斂速度和增加物種多樣性，繼而提高了萬有引力搜索算法全局尋優(yōu)能力；徐遙[4]提出通過引入權值來改變粒子的慣性質(zhì)量，從而改進萬有引力搜索算法，加快了全局搜索的收斂速度；李鵬等[5]提出將改進的GSA算法應用于多目標多約束的微網(wǎng)運行優(yōu)化問題，最終有效實現(xiàn)了微網(wǎng)優(yōu)化；李沛等[6]將改進的GSA算法用于無人機的航路規(guī)劃中，驗證了在復雜作戰(zhàn)環(huán)境下可實時有效規(guī)劃出無人機的最優(yōu)航路；龔安等[7]提出引入混沌序列和遺傳算法的交叉思想改進GSA算法，有效用于火電廠一次風機的狀態(tài)監(jiān)測；李世武等[8]引入自適應配時策略改進GSA，有效解決低排放自適應配時的優(yōu)化問題.

當然，萬有引力搜索算法也有一些缺陷，如GSA存在易陷入早熟和局部最優(yōu)等問題.因此，本文提出一種新型的改進PSOGSA混合算法.為了驗證優(yōu)化效果，選取四個非線性基準測試函數(shù)，并和PSO算法、GSA算法、基本PSOGSA混合算法優(yōu)化結(jié)果進行對比.

1 粒子群萬有引力搜索混合算法

1.1 粒子群算法

粒子群優(yōu)化算法是由Kennedy和Eberhart于1995年提出的一種全局優(yōu)化進化算法[9]，粒子群算法是在對鳥群和魚群的群體動力學行為研究的基礎上演化而來，是對其行為的一種模擬.在群體中，任何一個個體在覓食過程中不僅與過去積累的經(jīng)驗和認知有關，同時還和群體中其他的個體之間存在相互影響.在PSO算法中，每個個體在向最優(yōu)解過程移動中，都有自己的速度和位置信息，并且這些信息是不斷變化調(diào)整的(變化的主要依據(jù)是粒子過去積累的經(jīng)驗和群體中其他個體的信息).在PSO算法初始化過程中，隨機產(chǎn)生粒子群的種群，其中每個粒子都是目標函數(shù)的解，為了找尋函數(shù)的最優(yōu)解，每個粒子會根據(jù)個體歷史最優(yōu)位置和種群的最優(yōu)位置來多次調(diào)整自己的速度更新策略，然后調(diào)整位置更新策略，并經(jīng)多次迭代尋優(yōu)最終找到最優(yōu)解.

每個粒子均有自己的速度向量和位置向量，但在找到最優(yōu)解之前，粒子會不斷更新速度和位置，其表達式為

(2)

(3)

1.2 萬有引力搜索算法

萬有引力搜索算法是依據(jù)萬有引力定律、牛頓第二定律及粒子之間受到作用力而相互吸引現(xiàn)象的基礎上被提出來的.在萬有引力搜索算法中，將優(yōu)化問題的解看成是一組在空間運行的粒子[10]，再根據(jù)萬有引力定律和牛頓第二運動定律可知，這些搜索粒子由于彼此之間所受到的作用力而向一起聚集.粒子運動遵循動力學規(guī)律，慣性質(zhì)量大的粒子比慣性質(zhì)量小的粒子運動得慢，因此，物質(zhì)都朝著慣性質(zhì)量大的粒子方向進行運動，而慣性質(zhì)量最大的粒子占據(jù)著最優(yōu)的位置，從而得出問題的最優(yōu)解.

粒子i的速度、位置更新以及加速度表達式為

(4)

(5)

(6)

在GSA算法中，為了簡化模型，假設引力質(zhì)量與慣性質(zhì)量相等，而粒子的慣性質(zhì)量是依據(jù)其適應度的大小計算的，那么粒子的適應度越好，則該粒子的慣性質(zhì)量越大，吸引力也越大，越接近最優(yōu)值，但是其移動速度卻越慢.根據(jù)適應度函數(shù)得出的粒子引力質(zhì)量的更新算法表達式為

(7)

(8)

(9)

式中：fiti(t)為粒子i在t時刻的適應度函數(shù)值；worst(t)為粒子i在t時刻群體最差適應度函數(shù)值；best(t)為粒子i在t時刻群體最好適應度函數(shù)值.第d維空間上粒子i所受到的總作用力為

(10)

(11)

(12)

(13)

2 改進的粒子群萬有引力搜索混合算法

針對GSA優(yōu)化算法早熟、易陷入局部最優(yōu)及缺少有效的加速機制等問題，提出了基本PSOGSA混合算法.利用PSOGSA混合算法獲取的最優(yōu)解引導著慣性質(zhì)量大的粒子朝全局最優(yōu)移動，但并不是所有粒子都朝著最優(yōu)解聚集，顯然PSOGSA混合算法也加快了群體的整體運動，促使其尋優(yōu)能力增強，同時也有效緩解了算法停滯的缺點，避免早熟現(xiàn)象.混合算法中將粒子群的速度更新機制引入到GSA算法的速度更新中，有效解決了GSA易陷入局部最優(yōu)問題.此外，GSA算法在搜索的過程中，更新位置環(huán)節(jié)只有粒子的當前位置在起作用，而沒有群體記憶功能，但是由于引入粒子群算法，可提高粒子間的群體信息共享，基本PSOGSA混合算法速度更新公式為

(14)

粒子群算法(PSO)是一種新型、原理簡單且操作易實現(xiàn)的優(yōu)化問題解決方法，與萬有引力搜索算法同為優(yōu)化算法.根據(jù)無免費午餐定理[11]，對于任何一個工程領域中的優(yōu)化問題，任意兩種優(yōu)化算法的平均性能是相等的，即不存在任何一種優(yōu)化算法在計算效率、全局搜索能力、通用性等所有算法性能方面都占據(jù)著優(yōu)勢.由相關研究[12]可知，粒子群中的gbest加入到速度矢量中會減弱算法的尋優(yōu)能力，也會進一步平衡混合算法的全局探測與局部開采能力[13-14].因此，本文需要對基本PSOGSA混合算法進行改進，c1和c2的更新公式[15]為

(15)

(16)

式中，h為迭代次數(shù).

為了確保粒子在混合算法后期階段搜索時具有自適應移動，引入動量因子p來更新粒子位置，即

(17)

(18)

(19)

式中：N為種群規(guī)模；up為搜索上限；low為搜索下限；ai為粒子i的加速度；pbesti為粒子i的當前最優(yōu)位置.

為了更加清晰、直觀地描述改進的粒子群萬有引力搜索混合算法，現(xiàn)給出改進算法的步驟與流程如下：

1) 隨機初始化粒子的位置、速度、加速度和質(zhì)量以及各粒子間所受到的作用力；

2) 設置粒子搜索范圍，并計算種群中粒子的適應度函數(shù)值；

3) 利用式(12)計算引力常數(shù)，式(7)～(9)計算種群每個粒子的質(zhì)量；

4) 利用式(11)計算種群中兩兩粒子之間相互受到的萬有引力；

5) 利用式(6)計算每個粒子在每個維數(shù)上所受到合力產(chǎn)生的加速度，并將其更新；

6) 更新種群中每個粒子的速度和位置；

7) 判斷算法迭代次數(shù)是否達到最大，或者連續(xù)若干次最優(yōu)值是否一直保持不變，若滿足，則停止搜索，否則轉(zhuǎn)向步驟2).

3 仿真分析

3.1 測試函數(shù)

為了檢驗改進的PSOGSA混合算法的優(yōu)化效果，選取了PSO、GSA和基本PSOGSA算法進行對比實驗，并引入四個Benchmark函數(shù)進行測試.四個測試函數(shù)中，Sphere是一個非線性的、平滑的、對稱的單模態(tài)函數(shù)，變量間可分離，常用來分析算法的執(zhí)行性能；Rosenbrock是一個非對稱的典型病態(tài)單模態(tài)函數(shù)，很難實現(xiàn)全局最優(yōu)；Ackley和Griewank均為典型的不同維度之間不可分離的、連續(xù)的復雜多模態(tài)函數(shù)，兩者均具有廣泛的搜索空間，以及大量的局部極小點和高大的障礙物.在這四個函數(shù)中，除了Rosenbrock函數(shù)在全局最優(yōu)解[1，1，…，1]處有極小值，其余測試函數(shù)均在全局最優(yōu)解[0，0，…，0]處有極小值，并且極小值均為0.具體函數(shù)如表1所示.

表1 測試函數(shù)

3.2 實驗結(jié)果及分析

利用改進的PSOGSA混合算法、PSO算法、GSA算法以及基本PSOGSA算法對上述四個測試函數(shù)進行數(shù)值實驗來驗證本文算法的性能.各算法涉及的主要參數(shù)設置如下：種群規(guī)模N=50；最大迭代次數(shù)T=1 000；函數(shù)維度d=30；標準粒子群算法中慣性權重w=0.9；加速因子c1=2，c2=2；萬有引力算法中引力常數(shù)G0=100；PSOGSA混合算法中加速因子c1=0.5，c2=1.5.為了驗證改進粒子群萬有引力混合算法的優(yōu)越性和可行性，分別對表1所示的四個函數(shù)進行優(yōu)化，如圖1～4所示.

圖1 Sphere函數(shù)優(yōu)化曲線

圖2 Rosenbrock函數(shù)優(yōu)化曲線

圖3 Ackley函數(shù)優(yōu)化曲線

根據(jù)圖形所示的結(jié)果可以看出，改進的粒子群萬有引力混合算法在高維函數(shù)優(yōu)化中較其他群智能算法(粒子群算法PSO、萬有引力算法GSA和粒子群萬有引力混合粒子群算法PSOGSA)相比具有明顯的優(yōu)勢，收斂速度快，搜索精度高，避免早熟現(xiàn)象，易找到全局最優(yōu)解，克服了傳統(tǒng)PSO算法和GSA算法中出現(xiàn)的不足和缺點.改進后的混合算法具有更加優(yōu)良的性能指標，同時也證明改進策略的可行性和正確性.

圖4 Griewank函數(shù)優(yōu)化曲線

4 結(jié) 論

本文在基本PSOGSA混合算法的基礎上進行改進，提出了改進的PSOGSA混合算法.由于GSA算法具有早熟、易陷入局部最優(yōu)及缺少有效的加速機制等問題，將PSO與GSA算法結(jié)合，并對c1、c2進行改進，緩解由于gbest加入到速度矢量中而導致算法尋優(yōu)能力減弱的缺點，同時也平衡了全局與局部最優(yōu).為了確保粒子在后期階段能夠自適應移動，引入動量因子p來更新粒子位置.通過四個測試函數(shù)對改進的PSOGSA混合算法進行測試，與PSO、GSA和基本PSOGSA混合算法相比，不論是單峰函數(shù)還是多峰函數(shù)，本文算法均表現(xiàn)出較快的收斂性和較好的穩(wěn)定性，從而驗證了本文算法的有效性.