陶 玲,高曉智
(1.上海海事大學 信息工程學院,上海 201306;2.芬蘭阿爾托大學,芬蘭 赫爾辛基 00076)
入侵雜草優(yōu)化算法[1]是伊朗德黑蘭大學的MEHRABIAN A R和LUCAS C在2006年首次提出的。該算法自適應性強、魯棒性強,算法參數(shù)相對較少,比較容易實現(xiàn)。近年來,它已成功應用在求解TSP問題[2]、0/1背包問題[3]等眾多領域之中。
針對基本的IWO算法存在易陷入局部極小點的不足,2009年HAJIMIRSADEGHI H等人將IWO和PSO兩算法混合[4],對雜草的種子進行速度和位移的更新,再進行正態(tài)分布,加快了算法收斂速度,并改善了算法的全局優(yōu)化能力;2012年賈盼龍等人提出一種NIWO算法[5],對種群個體分類,利用自適應小生境策略,改善了種群的多樣性,提高了算法的全局優(yōu)化性能;2013年劉彩霞等人提出了雙種群雜草算法[6],采用雙變異算子策略,將種群劃分為兩個獨立進化的子群,采用柯西變異和高斯變異兩種方式產(chǎn)生子代個體,這種變異機制使得算法更易避開函數(shù)的局部最優(yōu)點,最終提高了算法的性能。
本文提出一種混合的IWOPSO算法,對父代雜草產(chǎn)生的種子個體引入粒子群算法中的位置、速度公式,對種子個體進行位置和速度更新,得到新的種子個體,然后引入一個隨機數(shù),對新的種子個體進行IWO中的正態(tài)分布擴散,以改善種子個體質量,提高算法迭代后期的局部尋優(yōu)能力。利用5個不同維數(shù)的benchmark函數(shù)測試,結果表明本文算法有效,收斂精度和速度有較大提高。
基本IWO算法具體實現(xiàn)步驟[7]如下:
(1)初始化種群,根據(jù)實際問題初始化算法的各個參數(shù)。
(2)根據(jù)初始種群大小、初始搜索空間和問題的求解維數(shù)隨機產(chǎn)生初始解。
(3)進化代數(shù)的更新及子代個體正態(tài)分布標準差的計算。其計算公式為:
其中,iter為當前迭代次數(shù)。
(4)子代的生長繁殖。父代個體允許繁殖種子個數(shù)與其適應度值服從向下取整的線性關系,如圖1所示。
圖1 父代個體繁殖種子的方式
(5)判斷是否達到最大種群數(shù)量,當超過最大種群數(shù)量時,競爭排除;反之,重復步驟(4)。
(6)判斷是否達到最大迭代次數(shù),當達到時輸出最優(yōu)解,反之重復步驟(4)~(5)。圖2為基本IWO算法流程圖。
圖2 IWO算法流程圖
在IWOPSO算法中,對種子個體引入PSO[8]中的速度公式(3)和位置公式(4)對種子個體的速度和位置進行更新,得到新的種子個體,然后,利用式(5)對種子個體進行正態(tài)分布,提高種子個體的質量,以獲得更高的尋優(yōu)精度。慣性權重更新公式為:
其中,iter為當前迭代次數(shù),itermax為最大迭代次數(shù),wmax為最大慣性權重,wmin為最小慣性權重。
其中,w為慣性權重,c1、c2為學習因子,r1、r2為隨機數(shù),pi(t)為個體極值,pg(t)為群體極值。
其中,xnew為正態(tài)分布后的種子個體,xl(i,:)為經(jīng)過位置和速度更新后的種子個體,delta_iter為正態(tài)分布標準差。
各種測試函數(shù)如表1所示。其中:f1、f2、f3是單峰函數(shù),f4、f5是多峰函數(shù)。
表1 benchmark函數(shù)
IWOPSO算法中參數(shù)取值如表2所示。
表2 IWOPSO算法參數(shù)設置
對于每個benchmark函數(shù),每次最大迭代次數(shù)為600,獨立運行50次,兩種算法測試結果如表3所示。圖3、圖4分別是f4、f5函數(shù)的收斂曲線。
表3 benchmark函數(shù)測試結果
圖3 函數(shù)f4迭代1 200代的收斂曲線
圖4 函數(shù)f5迭代600代的收斂曲線
從表3可以看出,對于5個benchmark函數(shù),無論函數(shù)是單峰的還是多峰的,IWOPSO算法的平均最優(yōu)解幾乎均小于標準的IWO算法,而且其標準差也顯著減小,這表明,將IWO和PSO算法混合后較大提高了IWO的全局收斂性,說明改進后的算法IWOPSO可行有效。
從圖3、圖4可以看出,在迭代過程中,IWOPSO算法相對于IWO和PSO算法收斂速度有明顯的提高。
本文針對入侵性雜草優(yōu)化算法 (IWO)在搜索深度上的不足,將粒子群算法(PSO)的思想引入到IWO算法中,在子代擴散中以PSO算法中的位置、速度公式代替了雜草算法中的正態(tài)分布擴散,而雜草算法中的正態(tài)分布擴散用于對子代個體進一步正態(tài)分布,提高算法后期的局部尋優(yōu)能力,加強了算法的全局收斂性能,使算法在處理連續(xù)性問題時具有更高的求解精度和穩(wěn)定性,提高了算法的有效性。
[1]MEHRABIAN A R,LUCAS C.A novel numerical optimization algorithm inspired from weed colonization[J].Ecological Informatics,2006,1(4):355-366.
[2]彭斌,胡常安,邵兵,等.求解TSP問題的混合雜草優(yōu)化算法[J].振動、測試與診斷,2013,33(1):52-55.
[3]宋曉萍,胡常安.離散雜草優(yōu)化算法在0/1背包問題中的應用[J].計算機工程與應用,2012,48(30):239-242.
[4]HAJIMIRSADEGHI H,LUCAS C.A hybrid IWO/PSO algorithm for fast and global optimization[C].IEEE Congress on Evolutionary Computation,Stpetersburg:IEEE,2009:1964-1971.
[5]賈盼龍,田學民.基于自適應小生境的改進入侵性雜草優(yōu)化算法[J].上海電機學院學報,2012,15(4):225-230.
[6]劉彩霞,周暉,周伏秋.基于雙種群入侵性雜草算法的服務型城市綜合資源規(guī)劃[J].電力系統(tǒng)保護與控制,2013,41(19):67-74.
[7]張帥,王營冠,夏凌楠.離散二進制入侵雜草算法[J].華中科技大學學報(自然科學版),2011,39(10):55-60.
[8]劉曉峰,陳通.PSO算法的收斂性及參數(shù)選擇研究[J].計算機工程與應用,2007,43(9):14-17.