求解約束優(yōu)化問(wèn)題的改進(jìn)帝企鵝優(yōu)化算法

李旭飛，王 貞

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

0 引 言

約束優(yōu)化問(wèn)題是工程應(yīng)用[1]及科學(xué)應(yīng)用中廣泛研究的一類優(yōu)化問(wèn)題，例如：壓力容器設(shè)計(jì)、焊接梁設(shè)計(jì)、機(jī)器人優(yōu)化等。在解決約束優(yōu)化問(wèn)題時(shí)，優(yōu)化算法需要高效的約束處理技術(shù)平衡約束條件和目標(biāo)函數(shù)的信息。因此，研究人員設(shè)計(jì)出多種約束處理技術(shù)，常見(jiàn)的約束處理技術(shù)[2]有：懲罰函數(shù)法、約束和目標(biāo)分離法、多目標(biāo)優(yōu)化法等。此外，研究人員通過(guò)對(duì)約束處理技術(shù)進(jìn)行改進(jìn)[3]或?qū)s束處理技術(shù)進(jìn)行混合來(lái)設(shè)計(jì)更好的約束處理技術(shù)求解約束優(yōu)化問(wèn)題。另一方面，研究人員在設(shè)計(jì)有效的約束處理技術(shù)基礎(chǔ)上，也通過(guò)改進(jìn)搜索算法來(lái)提高約束優(yōu)化算法的性能。近些年，研究者們?cè)谇蠼饧s束優(yōu)化問(wèn)題的智能算法研究上有大量的成果。Long等針對(duì)螢火蟲算法收斂速度慢、易早熟等缺點(diǎn)，提出一種改進(jìn)螢火蟲算法求解約束優(yōu)化問(wèn)題。Liu等[4]在教與學(xué)優(yōu)化算法中引入自我學(xué)習(xí)過(guò)程，從而提出協(xié)同進(jìn)化教與學(xué)優(yōu)化算法求解約束優(yōu)化問(wèn)題。Wang等[5]提出了一種自適應(yīng)的人工蜂群算法求解約束優(yōu)化問(wèn)題等。

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

1 基本帝企鵝優(yōu)化算法

EPO算法是模擬帝企鵝群體冬季取暖的群智能優(yōu)化算法。該算法利用群體中心溫度最高點(diǎn)的個(gè)體為最優(yōu)個(gè)體引導(dǎo)其它個(gè)體向最優(yōu)點(diǎn)移動(dòng)，從而達(dá)到尋優(yōu)目的。種群中個(gè)體位置由最優(yōu)個(gè)體引導(dǎo)移動(dòng)，具體如下所示

(1)

(2)

(3)

式中：f和l兩個(gè)參數(shù)分別代表算法迭代過(guò)程中探索與開(kāi)發(fā)，它們的取值范圍分別為[2,3]，[1.5,2]。

(4)

(5)

(6)

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

(7)

(8)

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

基本EPO算法步驟如下。

算法1：帝企鵝優(yōu)化算法

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

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

(4)根據(jù)式(1)、式(2)、式(4)更新群體的當(dāng)前位置；

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

2 改進(jìn)帝企鵝優(yōu)化算法

EPO算法缺少變異機(jī)制，導(dǎo)致算法在搜索后期收斂速度慢，易陷入局部最優(yōu)。因此，IEPO算法通過(guò)引入兩種變異操作機(jī)制結(jié)合動(dòng)態(tài)線性調(diào)整粒子數(shù)目策略，在迭代前期可以增加算法的全局搜索能力，后期提高算法的局部勘探能力。為了平衡約束條件和目標(biāo)函數(shù)信息，在可行性準(zhǔn)則中加入存檔替換操作機(jī)制，并在IEPO算法中使用目標(biāo)函數(shù)最優(yōu)值個(gè)體作為最優(yōu)引導(dǎo)個(gè)體。

2.1 變異策略

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

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)

其中，隨機(jī)選擇的序號(hào)r1、r2和r3互不相同，且與目標(biāo)向量序號(hào)i也不相同；xr1、xr2和xr3是種群中隨機(jī)選取的個(gè)體；Vi是個(gè)體xi的變異個(gè)體；xbest是當(dāng)前種群最優(yōu)個(gè)體；變異算子F∈[0,2]，是一個(gè)實(shí)常數(shù)，控制偏差變量的放大作用；rand是[0,1]上均勻分布的隨機(jī)數(shù)。

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

Popsize1+Popsize2=Popsize

(11)

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

(12)

算法2： 變異操作

(1)fori=1∶Popsize

(2)ifi

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

(4)else

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

(6)end

(7)end

2.2 改進(jìn)可行性準(zhǔn)則

可行性準(zhǔn)則在處理約束問(wèn)題時(shí)簡(jiǎn)單有效，因此是常見(jiàn)的一種約束處理技術(shù)。它通常采用以下3條準(zhǔn)則比較兩個(gè)個(gè)體的優(yōu)劣。

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

(2)兩個(gè)可行個(gè)體比較，選擇目標(biāo)函數(shù)值好的個(gè)體；

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

在第一種情況中，如果不可行個(gè)體相比可行個(gè)體距最優(yōu)點(diǎn)更近，此時(shí)如果能夠選擇保留不可行個(gè)體則可能使算法更快收斂于最優(yōu)點(diǎn)?？尚行詼?zhǔn)則過(guò)度偏好于約束條件的信息，沒(méi)有充分利用具有較好目標(biāo)函數(shù)值的個(gè)體。鑒于上述情況，文獻(xiàn)[12]使用了一種存檔替換機(jī)制，在算法中存檔約束程度小且目標(biāo)函數(shù)值占優(yōu)的個(gè)體，然后通過(guò)替換種群中目標(biāo)函數(shù)值較劣的個(gè)體，使算法充分平衡約束條件和目標(biāo)函數(shù)的信息。具體的存檔替換機(jī)制如下：

算法3： 存檔替換機(jī)制

(1)將種群按目標(biāo)函數(shù)值降序排列，平均分為m個(gè)子種群；

(2)令i=1；

(3)While|A|>0andi

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

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

(6)Iff(xb)

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

(8)endIf

(9)i=i+1；

(10)endWhile

2.3 IEPO算法步驟

IEPO算法具體步驟如下。

算法4：改進(jìn)帝企鵝優(yōu)化算法

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

(2)計(jì)算每個(gè)個(gè)體目標(biāo)函數(shù)值和約束違背程度；

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

(4)根據(jù)式(1)、式(2)、式(4)更新群體的當(dāng)前位置；

(5)利用可行性準(zhǔn)則比較父代與子代個(gè)體，并保留優(yōu)秀個(gè)體；

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

(7)利用算法3選擇優(yōu)秀個(gè)體作為下一代進(jìn)化個(gè)體；

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

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

2.4 算法時(shí)間復(fù)雜度分析

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

3 數(shù)值實(shí)驗(yàn)及分析

為了驗(yàn)證改進(jìn)帝企鵝優(yōu)化算法(IEPO)對(duì)約束優(yōu)化問(wèn)題的有效性，本次實(shí)驗(yàn)采用13個(gè)標(biāo)準(zhǔn)約束優(yōu)化測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)比較。具體的測(cè)試函數(shù)情況參考文獻(xiàn)[13]。在實(shí)驗(yàn)中，設(shè)備處理器為：inter(R) Core(TM) i7-6500U CPU@2.50 GHz 2.59 GHz，內(nèi)存4 G。算法均在MATLAB2014a中進(jìn)行實(shí)驗(yàn)。

3.1 與原始帝企鵝優(yōu)化算法比較

本次實(shí)驗(yàn)將IEPO算法與EPO算法進(jìn)行比較。參數(shù)設(shè)置如下：種群數(shù)量均為80，最大迭代次數(shù)為1000次，對(duì)算法均進(jìn)行30次獨(dú)立實(shí)驗(yàn)。

實(shí)驗(yàn)結(jié)果見(jiàn)表1，分別給出IEPO算法和EPO算法的實(shí)驗(yàn)結(jié)果對(duì)比，Best、Mean、Worst和Std分別是算法獨(dú)立運(yùn)行30次的最優(yōu)值、平均值、最差值和標(biāo)準(zhǔn)差，標(biāo)準(zhǔn)差反映了算法的穩(wěn)定程度，Percentage表示可行解所占種群的比例?？梢钥闯鲈跍y(cè)試優(yōu)化問(wèn)題中，IEPO算法都優(yōu)于EPO算法，且能尋找到所有優(yōu)化問(wèn)題的可行解；并且在G3、G4、G5、G6、G7、G8、G9、G10、G11、G12、G13這些問(wèn)題中，IEPO 算法可以比較準(zhǔn)確尋找到函數(shù)最優(yōu)值，G12有非常好的穩(wěn)定性，在剩余優(yōu)化問(wèn)題上算法也表現(xiàn)出良好的穩(wěn)定性。在G1、G2等問(wèn)題中IEPO也沒(méi)有尋找到函數(shù)最優(yōu)值。

結(jié)合表1中的數(shù)據(jù)和圖1中收斂曲線，可以推斷出 IEPO 算法通過(guò)上述改進(jìn)的策略可以有效避免在尋找到最優(yōu)點(diǎn)之前出現(xiàn)早熟現(xiàn)象，而EPO算法不僅在可行域外出現(xiàn)停滯現(xiàn)象，在可行域內(nèi)也出現(xiàn)陷入局部最優(yōu)的情況。

表1 EPO算法與IEPO算法對(duì)約束優(yōu)化問(wèn)題尋優(yōu)對(duì)比結(jié)果

圖1 EPO算法與IEPO算法部分約束優(yōu)化問(wèn)題收斂曲線對(duì)比

3.2 IEPO與其它優(yōu)化算法的比較

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

表2 不同算法對(duì)約束優(yōu)化問(wèn)題尋優(yōu)對(duì)比結(jié)果

表2(續(xù))

4 工程優(yōu)化中的應(yīng)用

為驗(yàn)證IEPO算法對(duì)現(xiàn)實(shí)工程問(wèn)題優(yōu)化的性能，將該算法應(yīng)用于焊接梁設(shè)計(jì)和拉力/壓力彈簧設(shè)計(jì)這兩個(gè)工程問(wèn)題上。將EPO和IEPO算法分別獨(dú)立運(yùn)行30次，算法其它參數(shù)設(shè)置見(jiàn)3.1節(jié)。

4.1 焊接梁設(shè)計(jì)問(wèn)題

焊接梁優(yōu)化設(shè)計(jì)的主要目標(biāo)是在一定約束條件下使其費(fèi)用最小，該問(wèn)題的4個(gè)決策變量分別為h(x1)、l(x2)、t(x3)、b(x4)，問(wèn)題的具體表達(dá)形式如下

其中

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。

通過(guò)IEPO算法求解焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化問(wèn)題，并與EPO算法以及文獻(xiàn)[1]中CDE、CPSO、MBA、IFA等算法結(jié)果比較見(jiàn)表3，表中加粗表示較好結(jié)果。從表3中可知，在焊接梁結(jié)構(gòu)優(yōu)化設(shè)計(jì)上IEPO算法明顯優(yōu)于EPO算法；平均值和標(biāo)準(zhǔn)差都優(yōu)于CDE、CPSO、IFA等算法；與MBA算法相比，平均值略優(yōu)；圖2為EPO算法與IEPO算法在焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化上的收斂曲線，可以直觀看出，IEPO算法的收斂精度和速度都優(yōu)于EPO算法。

4.2 拉力/壓力彈簧設(shè)計(jì)問(wèn)題

拉力/壓力彈簧優(yōu)化設(shè)計(jì)的主要目標(biāo)是在一定約束條件下最小化張力弦質(zhì)量，該問(wèn)題的數(shù)學(xué)具體表達(dá)式如下

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

表3 不同算法對(duì)焊接梁?jiǎn)栴}優(yōu)化結(jié)果對(duì)比

圖2 焊接梁結(jié)構(gòu)設(shè)計(jì)問(wèn)題優(yōu)化收斂曲線

利用IEPO算法求解拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)問(wèn)題，并與EPO以及文獻(xiàn)[1]中CDE、CPSO、IFA等算法進(jìn)行比較，比較數(shù)據(jù)見(jiàn)表4，表中加粗表示較好結(jié)果。從表4中可知，IEPO算法在拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)等優(yōu)化問(wèn)題上優(yōu)于EPO算法，平均值和標(biāo)準(zhǔn)差都優(yōu)于CDE、CPSO、IFA等算法。圖3為EPO算法與IEPO算法拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)的收斂曲線，可以直觀看出，IEPO算法的收斂精度和速度更優(yōu)。

5 結(jié)束語(yǔ)

針對(duì)約束優(yōu)化問(wèn)題，本文提出一種改進(jìn)帝企鵝優(yōu)化算法。通過(guò)標(biāo)準(zhǔn)的測(cè)試優(yōu)化函數(shù)及實(shí)際工程問(wèn)題驗(yàn)證，IEPO算法利用兩種變異操作可以充分平衡全局搜索和局部開(kāi)采能力。動(dòng)態(tài)線性調(diào)整粒子數(shù)目策略，可以有效增加算法的收斂能力。此外，增加存檔替換機(jī)制的可行性準(zhǔn)則可使得算法有效避免了早熟現(xiàn)象。通過(guò)實(shí)驗(yàn)結(jié)果驗(yàn)證本文提出的改進(jìn)帝企鵝優(yōu)化算法可以有效解決約束優(yōu)化問(wèn)題。

表4 不同算法對(duì)拉壓彈簧設(shè)計(jì)問(wèn)題優(yōu)化結(jié)果對(duì)比

圖3 拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)問(wèn)題優(yōu)化收斂曲線