基于共軛梯度法和Tent映射的擬態物理學算法

唐林英 王煉紅 李瀟瑤

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

基于共軛梯度法和Tent映射的擬態物理學算法

唐林英 王煉紅 李瀟瑤

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

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

擬態物理學算法 共軛梯度法 尋優 混沌擾動

0 引 言

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

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

1 擬態物理學算法

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

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

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

(1)

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

此外，規定種群最優個體的質量為其本身，即在搜索中不變化。

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

(2)

式中，Fij,k為第i個個體和j個個體之間力的作用。從式(2)可以規定最優個體不受外力作用。

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

(3)

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

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

(4)

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

(5)

4) 貪婪選擇：計算t+1時刻的適應度值，采取貪婪選擇，若在t+1時刻出現個體適應度函數值大于t時刻最優值則取代，反之保持不變。

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

2 基于共軛梯度法和Tent映射的改進APO算法

2.1 共軛梯度法

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

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

xk=xk+αkdkk=0,1…

(6)

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

(7)

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

(8)

2.2Tent映射

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

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

(9)

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

(10)

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

2.3 改進APO算法具體步驟

基于共軛梯度法和Tent算子的改進擬態物理學算法具體步驟如下所示：

(1) 初始化。

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

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

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

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

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

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

3 仿真實例

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

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

表1 三種算法對測試函數尋優統計表 (a) Quartic函數統計表

(b) Rastrigin函數統計表

(c) Griewank函數統計表

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

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

表2 算法改進前后測試結果對比

圖1 Quartic測試函數迭代收斂曲線對比圖

圖2 Rastrigin測試函數收斂曲線對比圖

圖3 Griewank測試函數收斂曲線對比圖

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

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

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

最后為了驗證算法收斂速度，設定收斂閾值即當算法求得數值與測試函數標準最優之差小于收斂閾值則認為算法收斂。不妨設定3個測試函數收斂閾值分別為：1.0、0.01、1.0e-3。采用改進APO算法、APO算法測試多次取其算法執行時間；為防止算法陷入死循環，設置終止條件為：3000代。

表3 算法改進前后收斂時間對比表 s

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

4 結 語

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

本文算法中對閾值設定需要根據經驗值假設，所以算法有待進一步改進。由于算法對于調用共軛梯度法作為局部尋優算子時期敏感，即其對算法影響較大，對于如何設定達到最好效果需要進一步的實驗和研究。

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

[2] 王艷, 曾建潮. 一種基于擬態物理學優化的多目標優化算法[J]. 控制與決策, 2010, 25(7):1040-1044.

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

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

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

[6] 柴爭義, 王秉, 李亞倫. 擬態物理學優化的認知無線電網絡頻譜分配[J]. 物理學報, 2014, 63(22):433-438.

[7] 麻曉寧. 引入距離因子的擬態物理學優化算法[D]. 太原：太原科技大學, 2014.

[8] 柴爭義, 王秉, 李亞倫, 等. 擬態物理學多目標算法求解認知參數優化問題[J]. 電子學報, 2015, 43(8):1526-1530.

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

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

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

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

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

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

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

[16] 王維博. 粒子群優化算法研究及其應用[D]. 成都：西南交通大學, 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。國家自然科學基金項目(61174140)；湖南省自然科學基金項目(14JJ4026)。唐林英，碩士生，主研領域：智能算法，智能信息處理。王煉紅，副教授。李瀟瑤，博士生。

TP18

A

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