求解約束優化問題的改進帝企鵝優化算法

李旭飛，王 貞

(北方民族大學 數學與信息科學學院，寧夏 銀川 750021)

0 引 言

約束優化問題是工程應用[1]及科學應用中廣泛研究的一類優化問題，例如：壓力容器設計、焊接梁設計、機器人優化等。在解決約束優化問題時，優化算法需要高效的約束處理技術平衡約束條件和目標函數的信息。因此，研究人員設計出多種約束處理技術，常見的約束處理技術[2]有：懲罰函數法、約束和目標分離法、多目標優化法等。此外，研究人員通過對約束處理技術進行改進[3]或對約束處理技術進行混合來設計更好的約束處理技術求解約束優化問題。另一方面，研究人員在設計有效的約束處理技術基礎上，也通過改進搜索算法來提高約束優化算法的性能。近些年，研究者們在求解約束優化問題的智能算法研究上有大量的成果。Long等針對螢火蟲算法收斂速度慢、易早熟等缺點，提出一種改進螢火蟲算法求解約束優化問題。Liu等[4]在教與學優化算法中引入自我學習過程，從而提出協同進化教與學優化算法求解約束優化問題。Wang等[5]提出了一種自適應的人工蜂群算法求解約束優化問題等。

帝企鵝優化算法[6](emperor penguin optimizer，EPO)是Gaurav等提出的一種新型群智能優化算法，其思想是模擬帝企鵝群體冬天擁擠在一起取暖的行為進行尋優。Baliarsingh等[7]進一步將EPO算法用于求解多目標優化問題。Kumar等[8]將EPO算法用于處理圖像分割問題。Jia等[9]通過結合多項式變異、levy飛行及熱交換操作策略改進帝企鵝優化算法。盡管，EPO算法的研究已取得部分研究成果，但算法仍存在迭代后期收斂速度慢、易陷入局部最優等缺點。因此，本文提出了改進帝企鵝優化算法(improved emperor penguin optimizer，IEPO)用于求解約束優化問題。IEPO算法利用動態線性調整粒子數目策略結合兩種變異操作的替換使用，平衡了算法的全局探索能力與局部開采能力，從而提高算法的收斂速度。算法通過存檔替換機制完善了可行性準則性能，增加了算法的收斂精度，提高了算法跳出局部最優的能力。最后，將IEPO算法用于求解13個標準約束優化測試函數驗證算法的有效性，并應用到2個實際工程問題中檢驗算法性能。

1 基本帝企鵝優化算法

EPO算法是模擬帝企鵝群體冬季取暖的群智能優化算法。該算法利用群體中心溫度最高點的個體為最優個體引導其它個體向最優點移動，從而達到尋優目的。種群中個體位置由最優個體引導移動，具體如下所示

(1)

(2)

(3)

式中：f和l兩個參數分別代表算法迭代過程中探索與開發，它們的取值范圍分別為[2,3]，[1.5,2]。

(4)

(5)

(6)

其中，T1是帝企鵝群體的溫度變化函數；M=2是避免帝企鵝個體間碰撞的一個控制參數；Pgrid(Accuracy) 是最優個體到其它個體位置的絕對值；Rand是[0,1]上均勻分布的隨機數。T1的具體表達式如下

(7)

(8)

其中：maxGen是算法最大迭代次數；R表示企鵝群體圍成多邊形區域的半徑；T代表在搜索空間中尋找最優解的時間。

基本EPO算法步驟如下。

算法1：帝企鵝優化算法

(1)設置算法參數并初始化。種群數量Popsize，最大迭代次數為maxGen，當前代數為gen，在解空間中隨機初始個體位置；

(3)利用式(7)、式(8)先確定群體范圍的溫度變化趨勢；

(4)根據式(1)、式(2)、式(4)更新群體的當前位置；

(6)判斷算法是否滿足終止條件，若滿足，則輸出最優值；否則，轉(3)。

2 改進帝企鵝優化算法

EPO算法缺少變異機制，導致算法在搜索后期收斂速度慢，易陷入局部最優。因此，IEPO算法通過引入兩種變異操作機制結合動態線性調整粒子數目策略，在迭代前期可以增加算法的全局搜索能力，后期提高算法的局部勘探能力。為了平衡約束條件和目標函數信息，在可行性準則中加入存檔替換操作機制，并在IEPO算法中使用目標函數最優值個體作為最優引導個體。

2.1 變異策略

差分進化算法是一種隨機搜索的進化算法，該算法具有很好的全局搜索能力和局部探索能力。在變異操作中，DE/current-to-rand具有較好的探索能力，可以增加算法的全局搜索能力；DE/current-to-best具有很好的開發能力，可以增加算法的局部搜索能力，使算法能夠快速找到最優解[10]。因此本文利用上述兩個變異操作來增加算法的尋優能力。具體如下所示：

DE/current-to-best/1

Vi,gen+1=xi,gen+rand·(xbest,gen-xi,gen)+F·(xr1,gen-xr2,gen)

(9)

DE/current-to-rand/1

Vi,gen+1=xi,gen+rand·(xr1,gen-xi,gen)+F·(xr2,gen-xr3,gen)

(10)

其中，隨機選擇的序號r1、r2和r3互不相同，且與目標向量序號i也不相同；xr1、xr2和xr3是種群中隨機選取的個體；Vi是個體xi的變異個體；xbest是當前種群最優個體；變異算子F∈[0,2]，是一個實常數，控制偏差變量的放大作用；rand是[0,1]上均勻分布的隨機數。

為保證IEPO算法的搜索性能，本文利用動態線性調整粒子數目策略[11]結合式(9)和式(10)不同的變異操作進行變異。將種群分為兩個子種群N1和N2，對應子種群數量分別為Popsize1和Popsize2。 在算法早期搜索時，子種群N1使用DE/current-to-rand進行變異操作增加種群多樣性，讓更多的個體參與到全局搜索過程中。隨著算法迭代到后期，為保證局部搜索能力，子種群N2使用DE/current-to-best來提高算法的局部探索能力。既可以平衡算法收斂速度與種群多樣性，又使得種群能快速進入可行域并收斂到最優點避免陷入局部最優。動態線性調整粒子數目策略具體計算方式如下

Popsize1+Popsize2=Popsize

(11)

Popsize2=floor[(gen/maxGen)·Popsize]

(12)

算法2： 變異操作

(1)fori=1∶Popsize

(2)ifi

(3) 利用式(9)進行變異操作；

(4)else

(5) 利用式(10)進行變異操作；

(6)end

(7)end

2.2 改進可行性準則

可行性準則在處理約束問題時簡單有效，因此是常見的一種約束處理技術。它通常采用以下3條準則比較兩個個體的優劣。

(1)可行個體與不可行個體比較，選擇可行個體；

(2)兩個可行個體比較，選擇目標函數值好的個體；

(3)兩個不可行個體比較，選擇約束程度小的個體。

在第一種情況中，如果不可行個體相比可行個體距最優點更近，此時如果能夠選擇保留不可行個體則可能使算法更快收斂于最優點。可行性準則過度偏好于約束條件的信息，沒有充分利用具有較好目標函數值的個體。鑒于上述情況，文獻[12]使用了一種存檔替換機制，在算法中存檔約束程度小且目標函數值占優的個體，然后通過替換種群中目標函數值較劣的個體，使算法充分平衡約束條件和目標函數的信息。具體的存檔替換機制如下：

算法3： 存檔替換機制

(1)將種群按目標函數值降序排列，平均分為m個子種群；

(2)令i=1；

(3)While|A|>0andi

(4) 從等分群體的第一個部分中選取約束程度大的個體記為xa；

(5) 從存檔A中選取約束違反程度小的個體記為xb；

(6)Iff(xb)

(7) 用xb替換xa，并從種群中刪掉xa；

(8)endIf

(9)i=i+1；

(10)endWhile

2.3 IEPO算法步驟

IEPO算法具體步驟如下。

算法4：改進帝企鵝優化算法

(1)設置算法參數并初始化。種群數量Popsize，最大迭代次數為maxGen，當前代數為gen=1，在解空間隨機初始種群個體位置；

(2)計算每個個體目標函數值和約束違背程度；

(3)利用式(7)、式(8)先確定群體范圍的溫度變化趨勢；

(4)根據式(1)、式(2)、式(4)更新群體的當前位置；

(5)利用可行性準則比較父代與子代個體，并保留優秀個體；

(6)利用算法2變異操作，提高算法搜索能力；

(7)利用算法3選擇優秀個體作為下一代進化個體；

(8)判斷算法是否滿足終止條件，若滿足，則輸出最優值；否則，轉(3)。

通過算法1與算法4相比較可知，在EPO算法中引入變異操作，可以使算法在整個尋優過程中靈活搜索，增加種群多樣性，有效避免算法陷入局部最優。改進可行性準則策略的引入，能使算法保留較優不可行個體，當保留個體比當前種群中的個體更快接近最優點時，通過保留個體替換當前種群中目標函數值較劣的個體，使得算法跳出局部最優。改進可行性準則充分利用約束條件和目標函數信息，提高了算法的尋優能力。變異操作和改進可行性準則策略的結合，克服了帝企鵝優化算法求解約束優化問題時收斂精度低、易陷入局部最優等問題。

2.4 算法時間復雜度分析

根據算法1可知EPO算法的時間復雜度為O(maxGen×Popsize×n)，其中：maxGen為最大循環次數，Popsize為種群數量，問題維數為n。 IEPO算法相比于EPO算法，將種群隨機初始化時間復雜度為O(Popsize×n)。 IEPO算法在每次迭代過程中增加了變異操作，則其時間復雜度為O(maxGen×Popsize×n)。 所以IEPO算法的時間復雜度為O(Popsize×n+maxGen×Popsize×n)，即：O(maxGen×Popsize×n)。 所以IEPO算法的時間復雜度為O(maxGen×Popsize×n)。

3 數值實驗及分析

為了驗證改進帝企鵝優化算法(IEPO)對約束優化問題的有效性，本次實驗采用13個標準約束優化測試函數進行實驗比較。具體的測試函數情況參考文獻[13]。在實驗中，設備處理器為：inter(R) Core(TM) i7-6500U CPU@2.50 GHz 2.59 GHz，內存4 G。算法均在MATLAB2014a中進行實驗。

3.1 與原始帝企鵝優化算法比較

本次實驗將IEPO算法與EPO算法進行比較。參數設置如下：種群數量均為80，最大迭代次數為1000次，對算法均進行30次獨立實驗。

實驗結果見表1，分別給出IEPO算法和EPO算法的實驗結果對比，Best、Mean、Worst和Std分別是算法獨立運行30次的最優值、平均值、最差值和標準差，標準差反映了算法的穩定程度，Percentage表示可行解所占種群的比例。可以看出在測試優化問題中，IEPO算法都優于EPO算法，且能尋找到所有優化問題的可行解；并且在G3、G4、G5、G6、G7、G8、G9、G10、G11、G12、G13這些問題中，IEPO 算法可以比較準確尋找到函數最優值，G12有非常好的穩定性，在剩余優化問題上算法也表現出良好的穩定性。在G1、G2等問題中IEPO也沒有尋找到函數最優值。

結合表1中的數據和圖1中收斂曲線，可以推斷出 IEPO 算法通過上述改進的策略可以有效避免在尋找到最優點之前出現早熟現象，而EPO算法不僅在可行域外出現停滯現象，在可行域內也出現陷入局部最優的情況。

表1 EPO算法與IEPO算法對約束優化問題尋優對比結果

圖1 EPO算法與IEPO算法部分約束優化問題收斂曲線對比

3.2 IEPO與其它優化算法的比較

為了進一步驗證IEPO算法在約束優化問題上的性能，接下來與文獻[13]中ABC、PSO及HCS-LSAL和文獻[14]中ICA等算法的優化結果進行比較，并且算法參數設置與原參考文獻中相同，比較結果見表2。其中Na表示原文中沒有相對應數值，表中加粗表示較好結果。可以看出，在函數G3、G5、G7、G9、G10、G11、G12、G13上，IEPO 不僅可以尋找到最優值，而且穩定性更好；在函數G4、G6、G8上，IEPO算法能尋找到最優值，但標準差比其它算法大，穩定性較弱；在問題G1、G2上，IEPO算法沒有尋找到函數最優值，但平均值非常接近最優值；從而可以得到，IEPO算法在約束優化問題上有很好的尋優效果。

表2 不同算法對約束優化問題尋優對比結果

表2(續)

4 工程優化中的應用

為驗證IEPO算法對現實工程問題優化的性能，將該算法應用于焊接梁設計和拉力/壓力彈簧設計這兩個工程問題上。將EPO和IEPO算法分別獨立運行30次，算法其它參數設置見3.1節。

4.1 焊接梁設計問題

焊接梁優化設計的主要目標是在一定約束條件下使其費用最小，該問題的4個決策變量分別為h(x1)、l(x2)、t(x3)、b(x4)，問題的具體表達形式如下

其中

P=6000;L=14;E=30×106;G=12×106;τmax=13600;σmax=30000;δmax=0.25; 0.1≤x1≤2.0; 0.1≤x2≤10.0; 0.1≤x3≤10.0; 0.1≤x4≤2.0。

通過IEPO算法求解焊接梁結構設計優化問題，并與EPO算法以及文獻[1]中CDE、CPSO、MBA、IFA等算法結果比較見表3，表中加粗表示較好結果。從表3中可知，在焊接梁結構優化設計上IEPO算法明顯優于EPO算法；平均值和標準差都優于CDE、CPSO、IFA等算法；與MBA算法相比，平均值略優；圖2為EPO算法與IEPO算法在焊接梁結構設計優化上的收斂曲線，可以直觀看出，IEPO算法的收斂精度和速度都優于EPO算法。

4.2 拉力/壓力彈簧設計問題

拉力/壓力彈簧優化設計的主要目標是在一定約束條件下最小化張力弦質量，該問題的數學具體表達式如下

其中，0.25≤x1≤1.30; 0.05≤x2≤2.00; 2.00≤x3≤15.00。

表3 不同算法對焊接梁問題優化結果對比

圖2 焊接梁結構設計問題優化收斂曲線

利用IEPO算法求解拉力/壓力彈簧結構設計問題，并與EPO以及文獻[1]中CDE、CPSO、IFA等算法進行比較，比較數據見表4，表中加粗表示較好結果。從表4中可知，IEPO算法在拉力/壓力彈簧結構設計等優化問題上優于EPO算法，平均值和標準差都優于CDE、CPSO、IFA等算法。圖3為EPO算法與IEPO算法拉力/壓力彈簧結構設計的收斂曲線，可以直觀看出，IEPO算法的收斂精度和速度更優。

5 結束語

針對約束優化問題，本文提出一種改進帝企鵝優化算法。通過標準的測試優化函數及實際工程問題驗證，IEPO算法利用兩種變異操作可以充分平衡全局搜索和局部開采能力。動態線性調整粒子數目策略，可以有效增加算法的收斂能力。此外，增加存檔替換機制的可行性準則可使得算法有效避免了早熟現象。通過實驗結果驗證本文提出的改進帝企鵝優化算法可以有效解決約束優化問題。

表4 不同算法對拉壓彈簧設計問題優化結果對比

圖3 拉力/壓力彈簧結構設計問題優化收斂曲線