一種帶停滯信息的自適應粒子群優化方法

劉道華,陳良瓊,胡秀云,張 倩

(1.信陽師范學院計算機與信息技術學院,河南信陽 464000; 2.信陽師范學院土木工程學院,河南信陽 464000)

一種帶停滯信息的自適應粒子群優化方法

劉道華1,陳良瓊2,胡秀云1,張 倩1

(1.信陽師范學院計算機與信息技術學院,河南信陽 464000; 2.信陽師范學院土木工程學院,河南信陽 464000)

為了提高粒子群優化算法的性能,設計了優化粒子帶停滯信息的年齡結構網,并利用這種年齡結構網信息自適應地更改粒子群優化算法的3個關鍵參數.構建了一種帶停滯信息的自適應粒子群優化方法,給出了該方法的具體優化步驟.采用4個經典的低維及高維Benchmark測試函數驗證該優化方法的求解性能,并同引力搜索算法以及傳統的不帶停滯信息的粒子群優化算法進行求解對比.通過對比可知,該方法在低維多峰函數優化時,其搜索效率均2倍于其他文獻中的方法,對于維數高于2維的高維函數,該方法的優化效率同其他文獻中的方法基本相同,但在獲得全局解及局部解的能力以及所求解的精度方面均遠高于其他文獻中的方法.

停滯;粒子群優化;多峰函數優化;自適應調整策略

粒子群算法是源于鳥群和魚群捕食行為簡化模型的模擬,1995年由美國社會心理學家James Kennedy博士和電氣工程師Russell Eberhart博士提出的[1-3].由于其算法概念簡單,實現容易,故被廣泛應用于工程應用領域.粒子群算法雖被認為是一種全局智能搜索算法,但因算法是利用粒子個體的社會性(gbest)及局部性(pbest)共同搜索的結果,且粒子個體的這種社會性及局部性受其他環境參數設置的影響,導致算法在搜索時可能會停滯不前[4-6].現今許多學者也采用不同的辦法解決這一問題,如常磊等[7]提出了一種改進離散粒子群來解決虛擬網絡映射問題,這種算法的粒子進化更具方向性,同時引進不同粒子位置互斥因子,解決粒子群算法易早熟陷入局部最優解的缺陷.姜建國等[8]提出一種帶擾動加速因子的自適應粒子群優化算法,可以在運行過程中的不同階段自適應地以余弦函數的變化方式調整慣性權重系數,在加速因子線性變化的基礎上,基于一定的條件對加速因子進行擾動,并確定了相應條件參數的取值.這些改進方法均采用粒子間的自身相關信息來調整粒子群算法的3個關鍵參數,從而提高了粒子群算法的優化性能.但目前還沒有文獻利用粒子個體間的停滯信息來改善粒子群算法的優化性能.基于此,筆者提出了一種帶停滯信息的自適應粒子群優化方法,構建粒子的年齡結構信息以幫助粒子個體克服停滯不前及局部最優的特性.采用在粒子個體優化過程中的粒子信息來改善粒子群算法的優化性能,利用粒子優化過程中的停滯次數影響粒子適應度的變化率這一特性,統計粒子在優化過程中的停滯次數,進而采用停滯信息以自適應改變粒子群算法的3個關鍵參數,從而調整粒子優化進程,進而跳出局部最優而獲得全局最優解,提高整個粒子群優化算法的求解性能.通過幾個典型復雜函數以驗證該方法的優越性,這種方法尤其適用于高維多峰復雜函數的優化求解,并能在其他群智能算法中得以推廣應用.

1　帶停滯信息的粒子群相關設計

1.1粒子個體停滯次數的設計及計算

通過長期的實驗表明,當迭代至某一個粒子時,該粒子當前所有群體粒子處于不同停滯水平的總次數和的大小將直接影響該粒子的搜索結果.停滯次數總和越大,該粒子本次搜索時其適應度變化值越小;同時,停滯總次數和越大,整個粒子獲得最優解的總搜索時間將越長.

1.2粒子群全局最優粒子的確定方法

在N個粒子的迭代過程中,每個個體粒子迭代一次總會找到一個gbest解.當連續迭代3次且gbest的值沒有發生任何變化時,該粒子將在停滯次數標記上自動加1.這樣每個粒子均進行一次迭代搜索后,整個粒子個體群將附加一種年齡網,即附加了年齡結構網信息.

進化算法中的粒子個體同動植物個體一樣,存在著生物體生命進化的少、中、老衰退過程.假設λi為該粒子群算法第i個粒子的存活率,并假設每個迭代的存活率隨迭代數的增長呈幾何級數下降,則

設傳統的粒子群第i個粒子的初始適應度評價函數為Fi,1(x),則第i個粒子在迭代至第k步時,其適應度評價函數為

以粒子群優化最小化設計問題為例,整個優化的適應度評價函數值呈現下降趨勢,從而將以gbest值的變化率作為選擇新的gbest最好方式.依據式(2),有gbest值的變化率表達式:

1.3帶停滯信息的粒子群參數自適應調整方法

傳統的粒子群算法的兩個最重要的表達式為[9-11]

從式(4)和式(5)中可以看出,ω、c1和c2這3個參數的確定將直接影響粒子群算法的求解性能.當粒子在尋優過程中出現gbest連續多次不變時,需加大ω和c1的值,同時降低c2的值,即自適應地增強粒子的“探索”能力.基于此,將粒子的停滯信息添加到粒子群算法的3個關鍵參數中.粒子群算法的3個關鍵參數的自適應調整方案如下:

其中,θ是一個事先設置的較小的常數;wi,j表示第i個粒子迭代到當前時,停滯不全處于j次的次數.

2　帶停滯信息的自適應粒子群優化方法

步驟1 設置整個粒子群優化的最大迭代次數為N,并設置所有優化變量取值范圍,即xmin和xmax,對優化變量進行歸一化處理.

步驟2 隨機地產生一個初始粒子群S,并具有M個粒子;設置適應度停滯計數器s,并設s=1;整個粒子群中當前連續停滯次數η的初始化.

步驟3 判斷整個迭代中止條件是否滿足.如滿足條件,則轉步驟13;否則,轉步驟4.

步驟4 每一個粒子進行迭代尋優,計算每個粒子的適應度,即計算式(2)和式(3).

步驟5 比較本次該粒子適應度值是否同前次迭代的適應度值相等.如果ai,t+1[t]=ai,t[t],則k=k+1 (k為該粒子連續迭代次數).如果條件成立,執行步驟6;否則,轉步驟8.

步驟6 判斷適應度值連續停滯次數是否達到事先指定的次數.如果k>η條件成立,執行步驟7;否則,轉步驟8.

步驟7 該粒子適應度停滯計數器s=s+1,且統計粒子連續迭代次數變化量k=1,同時使ai,t+1[k]=F.

步驟8 判斷該粒子的適應度值是否優于歷史最佳值.如果條件成立,則將該粒子獲得的最優解進行解碼,然后驗證該設計問題的所有約束條件.如果滿足所有設計問題的約束條件,則轉步驟9;否則,轉步驟10.

步驟9 更新該粒子的個體極值,即更新該粒子的個體pbest值.

步驟10 選取當前粒子群中的最佳粒子信息.

步驟11 判斷當前最佳粒子是否優于群體歷史最佳粒子.如果條件成立,則用當前群最佳粒子更新全局gbest.

步驟12 依據式(6)～(8),為每一個粒子進行速度及位置更新.

步驟13 輸出gbest的值,并依據gbest的值解析出相關變量參數值,即獲得優化問題的最優解.

3　多峰函數優化實例

為了驗證這種帶停滯信息的粒子群優化性能,采用經典的Benchmark測試函數進行優化求解驗證,具體實驗函數信息如表1[12-15].

表1　多峰測試函數信息表

在Matlab R2010a編程環境下,采用Intel(R)Core(TM)i3-2120,3.30 GHz CPU的微機為每個測試函數獨立進行實驗,其中對于低于3維的函數需進行60次獨立實驗,高于3維的函數需進行6n+1次獨立實驗(n為函數維數).在實驗過程中,考慮到對于不同變量個數的優化問題,粒子群個體數量的多少將影響實驗的優化時間.對于F1(x)、F2(x1,x2)實例,實驗時粒子群個數M=30;對于Rastrigin Function及cRastrigin Function的函數維數n設為3,且在對F3(x)、F4(x)實驗時,粒子群個數M=100.實驗時其他參數設置為:η=5,α=0.8,β=0.6,N=500,θ=0.02,最大迭代終止次數t=2 000.為了驗證文中算法的優化求解性能,將其同傳統的不采用停滯信息的粒子群算法(Particle Swarm Optimization,PSO)以及文獻[15]的引力搜索算法(Gravitational Search Algorithm,GSA)在其他參數設置一致的情況下進行對比,實驗結果如表2所示.

表2　實驗結果統計表

從表2中可知,這種帶停滯信息的粒子群優化算法在優化復雜函數時,若維數低于2維,則由于粒子的組成比較簡單,故在獲得全局解以及局部解的收斂比率同其他方法差別不大,因統計每次粒子的停滯次數,故整個優化時間比其他兩種方法都多.而對于高于2維的復雜多峰函數,該方法獲得全局峰值個數以及局部峰值個數的準確率幾乎是100%,而其他兩種方法獲得局部峰值個數基本上都低于80%,獲得全局峰值個數均低于90%,同時,在優化過程中事先排除不滿足約束條件的個體,從而大大節省了優化時間.

為了進一步驗證這種帶停滯信息的粒子群算法同其他方法在進化進程中的變化情況,以函數F2和函數F4進行統計對比,3種方法的進化代數與進化平均適應度變化曲線如圖1和圖2所示.

圖1　F2函數的3種方法進化曲線對比圖

圖2　F4函數的3種方法進化曲線對比圖

從圖1可以看出,對于低維多峰函數(維數低于2維的),采用這種帶停滯信息的粒子群優化方法,由于進化時適應度變化值參入到自適應調整粒子群的關鍵參數中,故其平均適應度變化比較平穩;其他兩種方法因粒子適應度變化率處于停滯信息得不到調整的情況下,故其進化時平均適應度波動次數多,且變化幅度也比較大.從圖2中可以看出,這種高維的多峰函數,即對于這種帶約束條件的多峰函數優化,由于在優化過程中把約束條件事先考慮了,使得整個多峰復雜函數優化及早尋優獲得全局優化解,從而提高了優化效率.

4　結束語

在粒子群個體優化過程中統計粒子個體停滯的次數,并將這種信息添加到粒子群關鍵參數中,從而實現粒子群參數的自適應性調整.這種帶停滯信息的自適應粒子群優化方法,在優化低維多峰函數時,能獲得精度更高的解;在優化高維多峰函數時,能獲得所有的全局峰值以及局部峰值.同時在粒子群個體優化過程中檢查約束條件,使得整個算法的優化效率得以提高.這種方法既能提高多峰函數獲得全局解的精度,還能提高整個優化求解效率,同時該求解方法可對其他群智能算法(如蟻群優化、魚群優化、蜂群優化)的改進起到了很好的借鑒作用.

[1]LI M S,TANG W J,WU Q H.Paired-bacteria Optimiser—a Simple and Fast Algorithm[J].Information Processing Letters,2011,111:809-813.

[2]ANTANAS Z.On Strong Homogeneity of Two Global Optimization Algorithms Based on Statistical Models of Multimodal Objective Functions[J].Applied Mathematics and Computation,2012,218:8131-8136.

[3]周雅蘭,王甲海,黃聰.求解排列問題的分布估計離散粒子群優化算法[J].電子學報,2014,42(3):561-571. ZHOU Yalan,WANG Jiahai,HUANG Cong.Estimation of Distribution-discrete Particle Swarm Optimization Algorithm for Permutation-based Problems[J].Acta Electronica Sinica,2014,42(3):561-571.

[4]ISNARDO R,EDGAR R A S,DANIEL U C D.Non-rigid Multimodal Medical Image Registration Based on the Conditional Statistics of the Joint Intensity Distribution[J].Procedial Technology,2013,7:126-133.

[5]胡旺,YEN G G,張鑫.基于Pareto熵的多目標粒子群優化算法[J].軟件學報,2014,25(5):1025-1050. HU Wang,YEN G G,ZHANG Xin.Multiobjective Particle Swarm Optimization Based on Pareto Entropy[J].Journal of Software,2014,25(5):1025-1050.

[6]LEANDRO F F M,RAFAEL H L,LETICIA F F M.Multimodal Size,Shape,and Topology Optimisation of Truss Structures Using the Firefly Algorithm[J].Advances in Engineering Software,2013,56:23-37.[7]常磊,顧華璽,張之義,等.一種粒子群優化的用戶優先級虛擬網絡映射算法[J].西安電子科技大學學報,2015,42 (1):17-24. CHANG Lei,GU Huaxi,ZHANG Zhiyi,et al.Particle Swarm Optimization User-priority Virtual Network Embedding Algorithm[J].Journal of Xidian University,2015,42(1):17-24.

[8]姜建國,田旻,王向前,等.采用擾動加速因子的自適應粒子群優化算法[J].西安電子科技大學學報,2012,39(4): 74-80. JIANG Jianguo,TIAN Min,WANG Xiangqian,et al.Adaptive Particle Swarm Optimization Via Disturbing Acceleration Coefficents[J].Journal of Xidian University,2012,39(4):74-80.

[9]SUBHRAJIT R,MINHAZUL I,SWAGATAM D,et al.Multimodal Optimization by Artificial Weed Colonies Enhanced with Localized Group Search Optimizers[J].Applied Soft Computing,2013,13:27-46.

[10]PUNAM B,ROLI B,PRITI S.Multimodal Biometric Authentication Using PSO Based on Watermarking[J].Procedia Technology,2012,4:612-618.

[11]TANG Y,WANG Z D,FANG J N.Feedback Learning Particle Swarm Optimization[J].Applied Soft Computing,2011,11:4713-4725.

[12]WONG K C,WU C H,RICKY K P M,et al.Evolutionary Multimodal Optimization Using the Principle of Locality [J].Information Sciences,2012,194:138-170.

[13]MANOJ T.A New Genetic Algorithm for Global Optimization of Multimodal Continuous Functions[J].Journal of Computational Science,2014,5(2):298-311.

[14]WANG H F,MOON L,YANG S X,et al.A Memetic Particle Swarm Optimization Algorithm for Multimodal Optimization Problems[J].Information Sciences,2012,197:38-52.

[15]JOVANI L F,LUIZ F L,PAULO L C L.Comparison of Methods for Multivariate Moment Inversion-Introducing the Independent Component Analysis[J].Computers and Chemical Engineering,2014,60:41-56.

(編輯:郭 華)

Adaptive particle swarm optimization method with stagnancy information

LIU Daohua1,CHEN Liangqiong2,HU Xiuyun1,ZHANG Qian1
(1.School of Computer and Information Technology,Xinyang Normal Univ.,Xinyang 464000,China; 2.College of Civil Engineering,Xinyang Normal Univ.,Xinyang 464000,China)

To improve the performance of the particle swarm optimization algorithm,the optimal network of the particle age structure with stagnation information is designed,and the information about this network is used to adaptively change the three key parameters of the particle swarm optimization algorithm.At the same time,an adaptive particle swarm optimization method with stagnancy information is proposed and specific optimization steps of this method are given.Four classical low and high dimension benchmark test functions are used to validate the performance of the optimization method,and a comparison study is made with gravitational search algorithm and the traditional particle swarm optimization algorithm without stagnancy information.The comparison study shows that the search efficiency of the proposed method is 2 times higher than that of other methods in the literature in the case of low dimensional multimodal functions.When the dimension of functions is higher than 2,the search efficiency of the proposed method is almost the same as that of other methods,but with the better ability to achieve global solution and local solutions,and the higher solving precision.

stagnancy;particle swarm optimization;multimodal function optimization;self-adaptive adjust tactics

TP202+.7

A

1001-2400(2016)03-0120-05

10.3969/j.issn.1001-2400.2016.03.021

2015-01-14

時間:2015-07-27

國家自然科學基金資助項目(61402393);河南省高等學校重點科研資助項目(16A535001);河南省教師教育課程改革研究資助項目(2015-JSJYYB-037)

劉道華(1974-),男,教授,博士,E-mail:ldhzzx@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20150727.1952.021.html