一種帶停滯信息的自適應(yīng)粒子群優(yōu)化方法

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

(1.信陽師范學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院,河南信陽 464000; 2.信陽師范學(xué)院土木工程學(xué)院,河南信陽 464000)

一種帶停滯信息的自適應(yīng)粒子群優(yōu)化方法

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

(1.信陽師范學(xué)院計(jì)算機(jī)與信息技術(shù)學(xué)院,河南信陽 464000; 2.信陽師范學(xué)院土木工程學(xué)院,河南信陽 464000)

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

停滯;粒子群優(yōu)化;多峰函數(shù)優(yōu)化;自適應(yīng)調(diào)整策略

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

1　帶停滯信息的粒子群相關(guān)設(shè)計(jì)

1.1粒子個(gè)體停滯次數(shù)的設(shè)計(jì)及計(jì)算

通過長期的實(shí)驗(yàn)表明,當(dāng)?shù)聊骋粋€(gè)粒子時(shí),該粒子當(dāng)前所有群體粒子處于不同停滯水平的總次數(shù)和的大小將直接影響該粒子的搜索結(jié)果.停滯次數(shù)總和越大,該粒子本次搜索時(shí)其適應(yīng)度變化值越小;同時(shí),停滯總次數(shù)和越大,整個(gè)粒子獲得最優(yōu)解的總搜索時(shí)間將越長.

1.2粒子群全局最優(yōu)粒子的確定方法

在N個(gè)粒子的迭代過程中,每個(gè)個(gè)體粒子迭代一次總會(huì)找到一個(gè)gbest解.當(dāng)連續(xù)迭代3次且gbest的值沒有發(fā)生任何變化時(shí),該粒子將在停滯次數(shù)標(biāo)記上自動(dòng)加1.這樣每個(gè)粒子均進(jìn)行一次迭代搜索后,整個(gè)粒子個(gè)體群將附加一種年齡網(wǎng),即附加了年齡結(jié)構(gòu)網(wǎng)信息.

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

設(shè)傳統(tǒng)的粒子群第i個(gè)粒子的初始適應(yīng)度評價(jià)函數(shù)為Fi,1(x),則第i個(gè)粒子在迭代至第k步時(shí),其適應(yīng)度評價(jià)函數(shù)為

以粒子群優(yōu)化最小化設(shè)計(jì)問題為例,整個(gè)優(yōu)化的適應(yīng)度評價(jià)函數(shù)值呈現(xiàn)下降趨勢,從而將以gbest值的變化率作為選擇新的gbest最好方式.依據(jù)式(2),有g(shù)best值的變化率表達(dá)式:

1.3帶停滯信息的粒子群參數(shù)自適應(yīng)調(diào)整方法

傳統(tǒng)的粒子群算法的兩個(gè)最重要的表達(dá)式為[9-11]

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

其中,θ是一個(gè)事先設(shè)置的較小的常數(shù);wi,j表示第i個(gè)粒子迭代到當(dāng)前時(shí),停滯不全處于j次的次數(shù).

2　帶停滯信息的自適應(yīng)粒子群優(yōu)化方法

步驟1 設(shè)置整個(gè)粒子群優(yōu)化的最大迭代次數(shù)為N,并設(shè)置所有優(yōu)化變量取值范圍,即xmin和xmax,對優(yōu)化變量進(jìn)行歸一化處理.

步驟2 隨機(jī)地產(chǎn)生一個(gè)初始粒子群S,并具有M個(gè)粒子;設(shè)置適應(yīng)度停滯計(jì)數(shù)器s,并設(shè)s=1;整個(gè)粒子群中當(dāng)前連續(xù)停滯次數(shù)η的初始化.

步驟3 判斷整個(gè)迭代中止條件是否滿足.如滿足條件,則轉(zhuǎn)步驟13;否則,轉(zhuǎn)步驟4.

步驟4 每一個(gè)粒子進(jìn)行迭代尋優(yōu),計(jì)算每個(gè)粒子的適應(yīng)度,即計(jì)算式(2)和式(3).

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

步驟6 判斷適應(yīng)度值連續(xù)停滯次數(shù)是否達(dá)到事先指定的次數(shù).如果k>η條件成立,執(zhí)行步驟7;否則,轉(zhuǎn)步驟8.

步驟7 該粒子適應(yīng)度停滯計(jì)數(shù)器s=s+1,且統(tǒng)計(jì)粒子連續(xù)迭代次數(shù)變化量k=1,同時(shí)使ai,t+1[k]=F.

步驟8 判斷該粒子的適應(yīng)度值是否優(yōu)于歷史最佳值.如果條件成立,則將該粒子獲得的最優(yōu)解進(jìn)行解碼,然后驗(yàn)證該設(shè)計(jì)問題的所有約束條件.如果滿足所有設(shè)計(jì)問題的約束條件,則轉(zhuǎn)步驟9;否則,轉(zhuǎn)步驟10.

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

步驟10 選取當(dāng)前粒子群中的最佳粒子信息.

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

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

步驟13 輸出gbest的值,并依據(jù)gbest的值解析出相關(guān)變量參數(shù)值,即獲得優(yōu)化問題的最優(yōu)解.

3　多峰函數(shù)優(yōu)化實(shí)例

為了驗(yàn)證這種帶停滯信息的粒子群優(yōu)化性能,采用經(jīng)典的Benchmark測試函數(shù)進(jìn)行優(yōu)化求解驗(yàn)證,具體實(shí)驗(yàn)函數(shù)信息如表1[12-15].

表1　多峰測試函數(shù)信息表

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

表2　實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)表

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

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

圖1　F2函數(shù)的3種方法進(jìn)化曲線對比圖

圖2　F4函數(shù)的3種方法進(jìn)化曲線對比圖

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

4　結(jié)束語

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

[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ì)離散粒子群優(yōu)化算法[J].電子學(xué)報(bào),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熵的多目標(biāo)粒子群優(yōu)化算法[J].軟件學(xué)報(bào),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]常磊,顧華璽,張之義,等.一種粒子群優(yōu)化的用戶優(yōu)先級虛擬網(wǎng)絡(luò)映射算法[J].西安電子科技大學(xué)學(xué)報(bào),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]姜建國,田旻,王向前,等.采用擾動(dòng)加速因子的自適應(yīng)粒子群優(yōu)化算法[J].西安電子科技大學(xué)學(xué)報(bào),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

時(shí)間:2015-07-27

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

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

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