劉小剛， 歐陽(yáng)自根

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

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

minf(x)

(1)

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

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

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

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

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

1 粒子群萬(wàn)有引力搜索混合算法

1.1 粒子群算法

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

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

(2)

(3)

1.2 萬(wàn)有引力搜索算法

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

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

(4)

(5)

(6)

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

(7)

(8)

(9)

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

(10)

(11)

(12)

(13)

2 改進(jìn)的粒子群萬(wàn)有引力搜索混合算法

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

(14)

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

(15)

(16)

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

為了確保粒子在混合算法后期階段搜索時(shí)具有自適應(yīng)移動(dòng)，引入動(dòng)量因子p來(lái)更新粒子位置，即

(17)

(18)

(19)

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

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

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

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

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

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

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

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

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

3 仿真分析

3.1 測(cè)試函數(shù)

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

表1 測(cè)試函數(shù)

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

4 結(jié) 論

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