印煜民,李 帥,馬 川，廖柏林

(1.吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000；2.香港理工大學(xué)計(jì)算機(jī)系，香港 999077)

與一般方法相比，生物啟發(fā)式算法在處理復(fù)雜的優(yōu)化問(wèn)題方面更為有效.J Kennedy等[1]開(kāi)發(fā)了粒子群優(yōu)化算法(Particle Swarm Optimization,簡(jiǎn)稱PSO算法)，這是經(jīng)典的生物啟發(fā)式算法之一.該算法基于動(dòng)物的群體行為，如魚和鳥群的覓食行為，通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)，即從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解[2].受到螞蟻如何找到最短路徑的啟發(fā)，M Dorigo等[3]和葉志偉等[4]提出了蟻群算法用來(lái)解決旅行商問(wèn)題(Traveling Salesman Problem,TSP).基于螢火蟲閃爍特性的一些理想化行為，Yang X S等[5]和張明等[6]提出了一個(gè)解決閥門負(fù)荷效應(yīng)的非凸經(jīng)濟(jì)調(diào)度問(wèn)題的螢火蟲算法.這些算法的性能表明，基于動(dòng)物行為進(jìn)行算法設(shè)計(jì)是可行的，且有很大的應(yīng)用前景.經(jīng)觀察，西瓜蟲的生存行為主要有2種，即群體聚集的行為和個(gè)體探索新環(huán)境的行為.這2種行為是西瓜蟲為了尋找合適的生存環(huán)境所必不可少的技能.基于此，筆者提出了一種新型的求解優(yōu)化問(wèn)題的算法，即西瓜蟲(PorcellioScaber)算法，簡(jiǎn)稱PS算法.

1 PS算法設(shè)計(jì)

圖1 西瓜蟲Fig. 1 Porcellio Scaber

西瓜蟲(圖1)屬于潮蟲科(oniscidae)、鼠婦屬(porcellio)[7]，喜歡生活在潮濕、黑暗和涼爽的地方，并且以群居為主[8].西瓜蟲有明顯的負(fù)趨光性，在干燥和溫度急劇下降的條件下，西瓜蟲的數(shù)量會(huì)大量下降，這時(shí)它們會(huì)選擇合適的環(huán)境來(lái)避難[9].西瓜蟲除了利用眼睛接收光線外，還有許多用以探測(cè)環(huán)境中的化學(xué)、機(jī)械和濕度情況的其他感官受體[10].當(dāng)環(huán)境條件不好的時(shí)候，西瓜蟲會(huì)移動(dòng)到適合生存的位置；當(dāng)外界環(huán)境十分惡劣時(shí)，它們會(huì)加速移動(dòng)；當(dāng)環(huán)境條件較好時(shí)，即適宜它們生存時(shí)，西瓜蟲會(huì)選擇停留在那里.

(1)

其中i,j∈{1,2,…,N}.由(1)式可知，所有西瓜蟲最終處于最佳環(huán)境中的同一位置.若只有聚集行為，而西瓜蟲最初又處于惡劣環(huán)境，則不能生存，因此西瓜蟲都具有探索新環(huán)境的傾向[10].西瓜蟲的實(shí)際運(yùn)動(dòng)是聚集行為和探索新環(huán)境行為加權(quán)的結(jié)果.基于此，模型(1)被進(jìn)一步修正為

其中：p表示移動(dòng)速度要求，

(2)

(2)式中的函數(shù)g(·)有下界，但該函數(shù)可以是不可微的，并且可以有多個(gè)局部最小值.通過(guò)觀察西瓜蟲的行為，設(shè)計(jì)PS算法來(lái)求解(2)式的最優(yōu)值.主要思想為將西瓜蟲尋找最優(yōu)環(huán)境條件的過(guò)程視作求解優(yōu)化函數(shù)最小值的過(guò)程，并將西瓜蟲的位置向量視為決策變量.由于西瓜蟲的運(yùn)動(dòng)結(jié)果是要停留在最好的環(huán)境條件下，所以基于西瓜蟲行為的優(yōu)化算法是可行的.PS算法的具體流程如下：

(ⅰ)設(shè)置目標(biāo)函數(shù)g(x)，x=(x1,x2,…,xd)T；

(ⅲ)由函數(shù)g(x)決定x位置處的環(huán)境條件Ex；

(ⅳ)基于西瓜蟲的聚集行為和探索新環(huán)境的行為來(lái)設(shè)置加權(quán)參數(shù)λ；

(ⅵ)隨機(jī)選擇一個(gè)方向y進(jìn)行檢測(cè)，y=(y1,y2,…,yd)T；

(ⅹ)根據(jù)權(quán)重決定移動(dòng)到新的位置，這個(gè)權(quán)重值由西瓜蟲的聚集和探索新環(huán)境2種行為來(lái)確定；

(ⅶ)根據(jù)環(huán)境條件排列西瓜蟲停留的地方，找到最佳位置.

2 驗(yàn)證實(shí)驗(yàn)

為了測(cè)試PS算法的有效性，采用PS算法求解基準(zhǔn)優(yōu)化函數(shù)——McCormic函數(shù).McCormic函數(shù)的表達(dá)式為

g(x)=sin(x1+x2)+(x1-x2)2-1.5x1+2.5x2+1，

(4)

其中x1∈[-1.5,4]，x2∈[-3,4].該函數(shù)在(x1，x2)=(-0.547 19,-1.547 19)時(shí)，存在一個(gè)全局最小值-1.913 3.筆者設(shè)標(biāo)準(zhǔn)偏差為0.01，權(quán)重系數(shù)λ=0.8，西瓜蟲樣本數(shù)量N=30，最大迭代次數(shù)Smax=30，利用PS算法做30組平行實(shí)驗(yàn).結(jié)果顯示，只有1組存在局部最小值，其他29組無(wú)局部最小值.選取存在局部最小值組作為特例組，并在其他29組中隨機(jī)選取9組作為實(shí)驗(yàn)組.圖2示出實(shí)驗(yàn)組中一組無(wú)局部最小值的運(yùn)動(dòng)軌跡，圖3示出特例組存在局部最小值的運(yùn)動(dòng)軌跡.圖中二維平面內(nèi)的線條表示西瓜蟲的運(yùn)動(dòng)軌跡，不同的顏色代表所處位置對(duì)應(yīng)的函數(shù)值.

圖2 無(wú)局部最小值的運(yùn)動(dòng)軌跡Fig. 2 Motion Trail Without Local Minimum

圖3 存在局部最小值的運(yùn)動(dòng)軌跡Fig. 3 Motion Trail with Local Minimum

從圖2可以看出，西瓜蟲從不同的位置出發(fā)，向區(qū)域內(nèi)的最小值點(diǎn)移動(dòng)，30個(gè)實(shí)驗(yàn)樣本最終落入了最優(yōu)值點(diǎn)附近位置.

從圖3可以看出，a點(diǎn)為一個(gè)局部最小值，b點(diǎn)為全局最小值，所有隨機(jī)產(chǎn)生的西瓜蟲會(huì)進(jìn)入局部最小值，但最終還是落入全局最優(yōu)點(diǎn)附近.

通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，該算法能夠有效找出最優(yōu)解，并最終落入全局最優(yōu)值附近，而且與理論全局最小值的誤差非常微小.將10組實(shí)驗(yàn)數(shù)據(jù)與McCormic函數(shù)的理論最小值列于表1.實(shí)驗(yàn)數(shù)據(jù)顯示，特例組落入的位置為x1=-0.547 21，x2=-1.547 20，對(duì)應(yīng)的函數(shù)g(x)=-1.913 2.由此可見(jiàn)，即使存在局部極小值，該算法也能在局部極小值附近找到全局最小值點(diǎn).

表1 PS算法求解McCormic函數(shù)的10組實(shí)驗(yàn)結(jié)果Table 1 Results of 10 Experiments with PS Algorithm for McCormic Function

3 算法對(duì)比

圖4 McCormic函數(shù)在PSO算法下的適應(yīng)度曲線Fig. 4 Fitness Curve of McCormic Function Through PSO Algorithm

PSO算法也稱為鳥群覓食算法[12]，該算法從隨機(jī)解出發(fā)，以迭代的方式尋找最優(yōu)值.利用PSO算法求解McCormic函數(shù)，然后與PS算法的求解結(jié)果進(jìn)行對(duì)比.

利用PSO算法求解McCormic函數(shù)最優(yōu)解的過(guò)程中，樣本數(shù)取30，迭代次數(shù)為100，進(jìn)行30組平行實(shí)驗(yàn)，隨機(jī)選取其中10組作為實(shí)驗(yàn)組.第1組實(shí)驗(yàn)中，McCormic函數(shù)在PSO算法下的適應(yīng)度曲線如圖4所示.在迭代次數(shù)為24時(shí)，函數(shù)在x1=-0.562 3，x2=-1.551 9處取得最優(yōu)值,g(x)=-1.912 9.10組實(shí)驗(yàn)結(jié)果列于表2.

表2 PSO算法求解McCormic函數(shù)的10次實(shí)驗(yàn)結(jié)果Table 2 Results of 10 Experiments with PSO Algorithm for McCormic

從表2可以看出，相比于PS算法，PSO算法在求解McCormic函數(shù)時(shí)有以下缺陷：(1)實(shí)驗(yàn)結(jié)果波動(dòng)較大，且無(wú)法通過(guò)增加迭代次數(shù)來(lái)改善性能；(2)存在無(wú)法得出正確解的情況.對(duì)比實(shí)驗(yàn)進(jìn)一步驗(yàn)證了PS算法的有效性和優(yōu)越性.

通過(guò)觀察西瓜蟲的生存規(guī)則，筆者提出了一種新穎、簡(jiǎn)單且有效的生物啟發(fā)式算法，即PS算法，用于求解優(yōu)化問(wèn)題；給出了該算法的設(shè)計(jì)過(guò)程，并利用其對(duì)基準(zhǔn)優(yōu)化函數(shù)——McCormic函數(shù)進(jìn)行求解.實(shí)驗(yàn)結(jié)果證明了該算法的有效性和優(yōu)越性.