唐林英 王煉紅 李瀟瑤

(湖南大學(xué)電氣與信息工程學(xué)院 湖南 長沙 410082)

基于共軛梯度法和Tent映射的擬態(tài)物理學(xué)算法

唐林英 王煉紅 李瀟瑤

(湖南大學(xué)電氣與信息工程學(xué)院 湖南 長沙 410082)

針對擬態(tài)物理學(xué)算法優(yōu)化算法后期搜索精度差、陷入局部最優(yōu)的問題，提出一種融合共軛梯度法和混沌擾動的改進(jìn)擬態(tài)物理學(xué)算法。該算法是在擬態(tài)物理學(xué)算法后期難以精細(xì)搜尋時，采用高精度解析算法——共軛梯度法替代擬態(tài)物理學(xué)算法進(jìn)行局部搜尋；在整個算法中加入混沌擾動，避免算法“早熟”。仿真結(jié)果表明該算法收斂速度快、精度高，在跳出局部最優(yōu)解上有明顯優(yōu)勢。因此該算法適應(yīng)于高維的復(fù)雜函數(shù)的尋優(yōu)。

擬態(tài)物理學(xué)算法 共軛梯度法 尋優(yōu) 混沌擾動

0 引 言

擬態(tài)物理學(xué)算法APO(artificial physics optimization)是一種基于擬態(tài)物理學(xué)方法的隨機搜索方法[1]。該算法通過建立個體質(zhì)量和適應(yīng)度函數(shù)值之間的關(guān)系，模擬群機器人系統(tǒng)智能行為涌現(xiàn)的情況而提出的一種全局隨機優(yōu)化啟發(fā)式算法[2]。其在求解非線性問題以及離散變量的時候有著獨特的優(yōu)勢，具有實現(xiàn)方便、種群數(shù)目少，尋優(yōu)效率高的特點[3]，在國內(nèi)已成功運用到配電網(wǎng)規(guī)劃[4]、圖像處理[5]、頻譜分配[6]等多方面。基本APO算法在個體趨近最優(yōu)個體時會因為斥力而導(dǎo)致最優(yōu)解附近不能精細(xì)搜索，得到的解收斂精度不高等缺點。部分學(xué)者通過引入距離因子[7]、動態(tài)調(diào)整權(quán)重[8]和引力因子的方法[9]提高搜索精度，但是均難以平衡“開采”和“勘探”之間的矛盾。

針對APO算法的缺點，考慮傳統(tǒng)解析算法具有局部尋優(yōu)能力強的特點，在APO算法后期最優(yōu)點附近無法進(jìn)行精細(xì)尋優(yōu)時[1]，采用解析尋優(yōu)算子——共軛梯度法[10]替代APO算法局部尋優(yōu)算子；并在算法的整個過程陷入“停滯”狀態(tài)時，利用混沌擾動[11]，避免算法過早陷入局部最優(yōu)。通過對測試函數(shù)的仿真結(jié)果表明，改進(jìn)后的APO算法較PSO算法和標(biāo)準(zhǔn)社會情感優(yōu)化算法SEOA(Social Emotional Optimization Algorithm)以及基本APO算法在收斂速度、跳出局部最優(yōu)能力以及解的精度方面表現(xiàn)更佳。

1 擬態(tài)物理學(xué)算法

APO算法是類比擬態(tài)物理學(xué)的全局隨機搜索優(yōu)化算法。該算法先在問題的解空間中隨機選取一組初始個體，每個個體根據(jù)自身的速度、位置和所受合力學(xué)習(xí)調(diào)整自身的運動狀態(tài)，整個種群所尋得的歷史最優(yōu)位置即為全局最優(yōu)解，個體的好壞由適應(yīng)度函數(shù)值進(jìn)行評價。采取的原則是適應(yīng)度高的吸引適應(yīng)度低的，而適應(yīng)度低的個體排斥比它高的個體。目前找到的最優(yōu)個體吸引群體中其他個體而不受群體其余合力作用[2]。每個個體通過全局最好、最差適應(yīng)度值和自身適應(yīng)度值不斷更新質(zhì)量，隨著質(zhì)量變化，個體合力變化，從而更新個體的速度和位置。

因此APO算法由初始化、合力計算、粒子位移、貪婪選擇、判斷終止5部分構(gòu)成。

1) 初始化：APO算法的初始化過程同其他智能算法類似，是一種隨機初始化的過程，即在解域隨機生成若干個解作為初代。與此同時計算初代的適應(yīng)度函數(shù)值f(x)，確定最優(yōu)個體xbest(t)=(x1(t),x2(t),…，xn(t))，其中n表示解的維數(shù),t表示進(jìn)化代數(shù)。APO算法定義個體xi的質(zhì)量計算公式為[1]：

(1)

式中：mi為第i個個體的質(zhì)量；Xbest為種群中適應(yīng)度值最高的個體，Xworst為種群中適應(yīng)度值最差的個體；f()為評價函數(shù)。顯然根據(jù)式(1)可以得到：適應(yīng)度值越大則質(zhì)量越大。

此外，規(guī)定種群最優(yōu)個體的質(zhì)量為其本身，即在搜索中不變化。

2) 合力計算：APO算法局部搜索策略模擬牛頓第二定律產(chǎn)生。其中兩個個體之間的作用力表達(dá)式[2]為：

(2)

式中，F(xiàn)ij,k為第i個個體和j個個體之間力的作用。從式(2)可以規(guī)定最優(yōu)個體不受外力作用。

最后計算種群中個體(除最優(yōu)個體外)所受其他個體的作用力合力公式[2]為：

(3)

式中Fi,k表示個體i在第k維受到合力作用。

3) 個體位移：除最優(yōu)個體外，其余任意個體i在t+1時刻每一維的速度和位移進(jìn)化方向[1]分別為:

(4)

xi,k(t+1)=xi,k(t)+vi,k(t+1)

(5)

4) 貪婪選擇：計算t+1時刻的適應(yīng)度值，采取貪婪選擇，若在t+1時刻出現(xiàn)個體適應(yīng)度函數(shù)值大于t時刻最優(yōu)值則取代，反之保持不變。

5) 終止判斷：設(shè)定終止條件，滿足條件則停止反之返回步驟2)。

2 基于共軛梯度法和Tent映射的改進(jìn)APO算法

2.1 共軛梯度法

當(dāng)算法后期個體i接近最優(yōu)個體Xbest時，|xbest,k-xi,k|→0，則|Fibest,k|→∞，使得個體i受很大合力，從而無法在最優(yōu)解個體附近進(jìn)行精細(xì)搜索[1]?？紤]傳統(tǒng)解析算法有很強的局部搜索能力，其中共軛梯度法是其典型代表[12]，因此本文在APO算法無法進(jìn)行精細(xì)搜索時，采用共軛梯度法代替APO算法進(jìn)行局部搜索。

共軛梯度法具有存儲量少且收斂速度快的優(yōu)點，考慮本文中是將共軛梯度法替代APO算法進(jìn)行高精度局部搜索，因此無須考慮共軛梯度法的全局尋優(yōu)能力，采用收斂能力較強的Conjugate-Descent(CD)共軛梯度法。其迭代式表示為:

xk=xk+αkdkk=0,1…

(6)

其中xk為當(dāng)前迭代點，αk為步長因子，dk為搜索方向，其計算公式為:

(7)

式中g(shù)k=▽f(xk)，βk為共軛參數(shù)，CD共軛梯度法共軛參數(shù)為:

(8)

2.2Tent映射

考慮混沌運動是在特定范圍內(nèi)的一定規(guī)則下的不重復(fù)遍歷運動，具有良好的多樣性，因此加入混沌擾動可以使得算法保持一定的種群多樣性，其跳出局部極值的能力加強。Tent映射結(jié)構(gòu)簡單具有良好的遍歷性，迭代速度要優(yōu)于Logistic映射[13]，因此本文采用Tent混沌映射作為擾動因子[14]。具體操作如下：

隨機生成混沌變量X=(X1,X2,…,Xn)，對混沌變量采取Tent映射為：

(9)

通過式(10)將混沌變量逆映射到所求的解域得到新的變量，表示為:

(10)

其中min_l和max_l分別是原來解域變量的下限和上限。

2.3 改進(jìn)APO算法具體步驟

基于共軛梯度法和Tent算子的改進(jìn)擬態(tài)物理學(xué)算法具體步驟如下所示：

(1) 初始化。

(2) 判斷是否采用共軛梯度法進(jìn)行局部尋優(yōu)。即設(shè)定閾值ε,若|xbest,k-xi,k|<ε則按照共軛梯度法進(jìn)行局部尋優(yōu)，并跳轉(zhuǎn)至步驟(5)。反之進(jìn)入下一步。

(3) 計算合力。依據(jù)式(1)-式(3)分別計算個體的質(zhì)量，受其他個體作用力，以及所受合力。

(4) 計算下一代速度和位置。

(5) 貪婪選擇。計算步驟(3)中個體適應(yīng)度值，并與上一代最佳個體比較，若能優(yōu)于上一代個體則保留。反之進(jìn)入步驟(6)。

(6)Tent混沌映射過程。采用文中所提Tent混沌映射得到新的變量，與上一代最佳個體比較，較優(yōu)者保留。

(7) 算法終止判斷。判斷是否滿足終止條件，滿足則停止迭代，反之則返回步驟(2)。

3 仿真實例

本文采用3個經(jīng)典的測試函數(shù)[15]Quartic (f1)、Rastrigin (f2)以及Griewank (f3)來進(jìn)行算法仿真。其中Quartic函數(shù)是個帶噪聲的函數(shù)，雖然它是單模態(tài)函數(shù)，但是明顯比Sphere函數(shù)要難以找到全局最優(yōu)，用來評價算法的可行性；Rastrigin函數(shù)是和Griewank函數(shù)局部極值點很多，且與維數(shù)成正比，所以全局最優(yōu)解附近就有很多局部極值點，算法在優(yōu)化時很容易陷入局部極值中，常被用來測試算法跳出局部最優(yōu)的能力。

為了驗證改進(jìn)后算法可行性，我們將本文算法進(jìn)行測試函數(shù)仿真50次，設(shè)置種群規(guī)模為100；解的維數(shù)分別為30、100、200；終止條件為維數(shù)×50代。運行結(jié)果與加速度系數(shù)隨時間變化的改進(jìn)粒子群算法TVAC-PSO(ModifiedTime-varyingacceleratorcoefficientsParticleSwarmOptimization)[16，17]和融合NW小世界模型的社會情感優(yōu)化算法NW-SEOA(WS-SocialEmotionalOptimizationAlgorithm)[18]比較，具體參數(shù)參見文獻(xiàn)[12-14]。最后得到統(tǒng)計的平均值和方差統(tǒng)計表如表1所示。

表1 三種算法對測試函數(shù)尋優(yōu)統(tǒng)計表 (a) Quartic函數(shù)統(tǒng)計表

(b) Rastrigin函數(shù)統(tǒng)計表

(c) Griewank函數(shù)統(tǒng)計表

從表1(a)中我們可以發(fā)現(xiàn)，由于Quartic測試函數(shù)雖然只有一個極值點，但是本身含有一個隨機噪聲變量,所以運用TVAC-PSO算法和NW-SOEA算法時，難以深入“勘探”，得到較好的解，而改進(jìn)APO算法能采用共軛梯度算子來詳盡“勘探”，只要尋優(yōu)方向正確能得到精度更高的解；表1(b)所示Rastrigin測試函數(shù)尋優(yōu)過程中，隨著維數(shù)的增加，尋優(yōu)難度明顯增加，而改進(jìn)APO算法混沌映射的能力使得其受影響程度較小，尋優(yōu)較穩(wěn)定且精度高;表1(c)所示的Griewank測試函數(shù)的尋優(yōu)過程，我們發(fā)現(xiàn)無論是低維還是高維的尋優(yōu)，本文算法由于產(chǎn)生混沌擾動能很快地跳出局部最優(yōu)，因此全局“勘探”能力較強，而傳統(tǒng)共軛梯度法替代APO算法局部尋優(yōu)算子使得搜尋到精度很高的近似解，即本文算法跳出局部的能力很強，局部尋優(yōu)精度高。

為了對比算法改進(jìn)后的算法的優(yōu)越性，本文對基本APO算法和本文提出算法進(jìn)行3個經(jīng)典測試函數(shù)的仿真測試100次,Quartic、Rastrigin以及Griewank測試函數(shù)解的維數(shù)分別為：30、100、200。取其中最優(yōu)解來進(jìn)行統(tǒng)計對比，得到表2所示結(jié)果，表2中基本APO算法統(tǒng)計數(shù)據(jù)取自文獻(xiàn)[1]。繪制迭代收斂圖如圖1-圖3所示。

表2 算法改進(jìn)前后測試結(jié)果對比

圖1 Quartic測試函數(shù)迭代收斂曲線對比圖

圖2 Rastrigin測試函數(shù)收斂曲線對比圖

圖3 Griewank測試函數(shù)收斂曲線對比圖

如圖1所示，由于Quartic函數(shù)自身隨機噪聲的原因，APO算法難以深入“勘探”，加上APO算法后期自身不足，從而導(dǎo)致300代左右尋優(yōu)停滯；而改進(jìn)APO算法在其尋優(yōu)停滯時運用混沌映射產(chǎn)生新個體并在優(yōu)解附近采用共軛梯度法詳細(xì)搜尋，從表2所示結(jié)果可以發(fā)現(xiàn)對于Quartic函數(shù)而言，改進(jìn)后算法較基本擬態(tài)物理學(xué)算法精度上提升較大。

如圖2所示，APO算法難以找尋到優(yōu)質(zhì)的解，加之算法局部尋優(yōu)能力不強，因此算法全局近乎處于停滯狀態(tài)，基本APO算法在Rastrigin測試函數(shù)尋優(yōu)能力較差，其結(jié)果不理想；而改進(jìn)APO算法加入混沌擾動后，利用Tent映射產(chǎn)生新解有可能落在最優(yōu)區(qū)域，從而引導(dǎo)算法向最優(yōu)解方向搜尋，與此同時共軛梯度法的引入讓本文算法在向著最優(yōu)解的同時能充分“開采”。由表2可知，在Rastrigin測試函數(shù)中改進(jìn)APO算法較基本APO算法在相同迭代次數(shù)下，能成功地搜尋到高精度解。

如圖3所示，改進(jìn)APO算法性能明顯占優(yōu)。結(jié)合表2可知，改進(jìn)APO算法較基本APO算法在Griewank測試函數(shù)上解精度高，收斂速度快。分析原因為Griewank函數(shù)是一個多模態(tài)函數(shù)，其局部最優(yōu)個數(shù)與維數(shù)成正比[19]。改進(jìn)APO算法利用混沌擾動增強了種群多樣性，能在解空間內(nèi)較詳細(xì)的探索，從而提高了算法“勘探”能力，避免算法早熟收斂。

最后為了驗證算法收斂速度，設(shè)定收斂閾值即當(dāng)算法求得數(shù)值與測試函數(shù)標(biāo)準(zhǔn)最優(yōu)之差小于收斂閾值則認(rèn)為算法收斂。不妨設(shè)定3個測試函數(shù)收斂閾值分別為：1.0、0.01、1.0e-3。采用改進(jìn)APO算法、APO算法測試多次取其算法執(zhí)行時間；為防止算法陷入死循環(huán)，設(shè)置終止條件為：3000代。

表3 算法改進(jìn)前后收斂時間對比表 s

從表3可以發(fā)現(xiàn)，對于測試函數(shù)1、2、3，改進(jìn)APO算法收斂速度明顯占優(yōu)。對于Quartic噪聲函數(shù)，改進(jìn)APO算法由于在算法后期引入共軛梯度算子，使得算法能深入“勘探”，從而得到較優(yōu)解；而基本APO算法搜索時間為6.277 s，進(jìn)一步查看迭代次數(shù)發(fā)現(xiàn)該算法是因為達(dá)到算法終止條件停止搜索，尋優(yōu)失敗。對于Rastrigin測試函數(shù)，改進(jìn)APO算法通過混沌映射能很好地跳出局部最優(yōu)，并且在引入共軛梯度法作為局部尋優(yōu)算子后能有效提高尋優(yōu)效率，使得算法有明顯改善；進(jìn)一步查看基本APO算法發(fā)現(xiàn)其搜索失敗，達(dá)到迭代終止條件停止搜索。對于Griewank測試函數(shù)，APO算法雖然能收斂，但是如果對精度加強，比如收斂精度改為1e-4乃至更高，則無法收斂，而改進(jìn)APO算法由于通過Tent混沌擾動使得算法在“勘探”方面能力大大加強，因此得到的解精度要占優(yōu)。

4 結(jié) 語

本文針對APO算法基本原理的缺點，采用共軛梯度法APO算法局部尋優(yōu)，大大提高算法局部搜索性能；在迭代過程中，利用Tent算子的混沌無序特性，避免算法“早熟”從而能得到優(yōu)良的解。最后仿真結(jié)果發(fā)現(xiàn)，改進(jìn)APO算法能更好地進(jìn)行尋優(yōu)，在高維函數(shù)的尋優(yōu)中也能成功運用。

本文算法中對閾值設(shè)定需要根據(jù)經(jīng)驗值假設(shè)，所以算法有待進(jìn)一步改進(jìn)。由于算法對于調(diào)用共軛梯度法作為局部尋優(yōu)算子時期敏感，即其對算法影響較大，對于如何設(shè)定達(dá)到最好效果需要進(jìn)一步的實驗和研究。

[1] 謝麗萍, 曾建潮. 基于擬態(tài)物理學(xué)方法的全局優(yōu)化算法[J]. 計算機研究與發(fā)展, 2011, 48(5):848-854.

[2] 王艷, 曾建潮. 一種基于擬態(tài)物理學(xué)優(yōu)化的多目標(biāo)優(yōu)化算法[J]. 控制與決策, 2010, 25(7):1040-1044.

[3] 陳廷斌, 張奇松, 楊曉光. 基于改進(jìn)人工勢場-魚群算法的LBS最短路徑修正研究[J]. 計算機應(yīng)用與軟件, 2015, 32(6):259-262.

[4] 詹昕, 向鐵元, 陳紅坤, 等. 基于搜索矢量擬態(tài)物理學(xué)算法的微電網(wǎng)脆弱性評估及重構(gòu)[J]. 電工技術(shù)學(xué)報, 2014, 29(2):74-81,92.

[5] 王立國, 魏芳潔. 結(jié)合APO算法的高光譜圖像波段選擇[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 2013, 45(9):100-106.

[6] 柴爭義, 王秉, 李亞倫. 擬態(tài)物理學(xué)優(yōu)化的認(rèn)知無線電網(wǎng)絡(luò)頻譜分配[J]. 物理學(xué)報, 2014, 63(22):433-438.

[7] 麻曉寧. 引入距離因子的擬態(tài)物理學(xué)優(yōu)化算法[D]. 太原：太原科技大學(xué), 2014.

[8] 柴爭義, 王秉, 李亞倫, 等. 擬態(tài)物理學(xué)多目標(biāo)算法求解認(rèn)知參數(shù)優(yōu)化問題[J]. 電子學(xué)報, 2015, 43(8):1526-1530.

[9] 孫寶, 孫大剛, 李占龍, 等. 基于序值與擁擠度的擬態(tài)物理學(xué)多目標(biāo)算法[J]. 系統(tǒng)工程與電子技術(shù), 2014, 36(12):2442-2448.

[10] 汪云飛, 畢篤彥, 孫毅, 等. 一種采用雙勢阱策略的小直徑圖分割方法[J]. 計算機應(yīng)用與軟件, 2013, 30(4):275-278.

[11] 鄭皎凌, 唐常杰, 徐開闊, 等. 基于協(xié)同進(jìn)化的異構(gòu)種群挖掘混沌迭代函數(shù)[J]. 計算機學(xué)報, 2010, 33(4):672-685.

[12] 高雷阜, 陳曦, 于冬梅. 信賴域共軛梯度法求解二次規(guī)劃逆問題[J]. 計算機工程與應(yīng)用, 2014, 50(1):41-44.

[13] 祁俊, 趙慧雅, 李明. 基于雙混沌映射改進(jìn)的人工魚群算法[J]. 計算機應(yīng)用與軟件, 2012, 29(9):230-233.

[14] 呂善翔, 馮久超. 一種混沌映射的相空間去噪方法[J]. 物理學(xué)報, 2013, 62(23):52-59.

[15] 李擎, 張超, 陳鵬, 等. 一種基于粒子群參數(shù)優(yōu)化的改進(jìn)蟻群算法[J]. 控制與決策, 2013, 28(6):873-878,883.

[16] 王維博. 粒子群優(yōu)化算法研究及其應(yīng)用[D]. 成都：西南交通大學(xué), 2012.

[17] Subasi A. Classification of EMG signals using PSO optimized SVM for diagnosis of neuromuscular disorders[J].Computers in Biology and Medicine, 2013, 43(5):576-586.

[18] Li X, Cui Z, Shi Z. Newman and Watts Small World Social Emotional Optimization Algorithm with WSN[J].Sensor Letters, 2012, 10(8):1676-1681.

[19] Alfi A. PSO with Adaptive Mutation and Inertia Weight and Its Application in Parameter Estimation of Dynamic Systems[J]. Acta Automatica Sinica, 2011,37(5):541-549.

THE ARTIFICIAL PHYSICS OPTIMIZATION ALGORITHM BASED ON CONJUGATE GRADIENT METHOD AND TENT MAPPING

Tang Linying Wang Lianhong Li Xiaoyao

(CollegeofElectricalandInformationEngineering,HunanUniversity,Changsha410082,Hunan，China)

An improved artificial physics algorithm which is combined conjugate gradient method with chaotic perturbations is proposed to solve the problem that the improved artificial physics algorithm has poor search accuracy in later period and it is easy to fall into local optimum. This algorithm adopted conjugate gradient method, a high accuracy analytical algorithm, to search locally when it is difficult for artificial physics algorithm to search accurately in later period, replacing artificial physics algorithm. It also introduced the Chaotic Perturbations to the whole algorithm, to a certain extent, to prevent the algorithm convergent too early. Tests show that the algorithm could jump out from the local optimal solution and had better solution in precision, stability and speed. So this algorithm is suitable for the high dimension complex functions optimization.

Artificial physics algorithm Conjugate gradient method Optimization Chaotic perturbations

2015-12-11。國家自然科學(xué)基金項目(61174140)；湖南省自然科學(xué)基金項目(14JJ4026)。唐林英，碩士生，主研領(lǐng)域：智能算法，智能信息處理。王煉紅，副教授。李瀟瑤，博士生。

TP18

A

10.3969/j.issn.1000-386x.2017.02.044