嵌入差分進(jìn)化和慣性權(quán)重的正弦余弦算法*

寧中正,和 煦,楊小勇,趙小強(qiáng)

(1.西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121； 2.國(guó)家無(wú)線電頻譜管理研究所，陜西 西安 710061)

0 引 言

在圖像處理、生產(chǎn)調(diào)度、特征集選取等工程領(lǐng)域中，絕大多數(shù)的工程應(yīng)用問(wèn)題都可以轉(zhuǎn)化為最優(yōu)化問(wèn)題，而群體智能優(yōu)化算法能使一些用常規(guī)優(yōu)化算法難以解決的復(fù)雜問(wèn)題得到解決，因此,各類性能優(yōu)異的群體智能優(yōu)化算法成為當(dāng)前一個(gè)熱點(diǎn)研究方向。其中較經(jīng)典的優(yōu)化算法主要有遺傳算法(genetic algorithm,GA)[1]、差分進(jìn)化(differential evolution,DE)算法[2]、粒子群優(yōu)化(particle swarm optimization,PSO)算法[3]等。隨著人們對(duì)新優(yōu)化理論和算法的需求增多，近些年也相繼出現(xiàn)了新的優(yōu)化算法，如果蠅優(yōu)化算法(fruit fly optimization algorithm,FOA)[4]、灰狼優(yōu)化(grey wolf optimizer,GWO)算法[5]、鯨魚(yú)優(yōu)化算法(whale optimization algorithm,WOA)[6]等。

然而幾乎不存在一個(gè)算法能有效解決所有的優(yōu)化問(wèn)題，這激勵(lì)著國(guó)內(nèi)外學(xué)者不斷嘗試新的思路來(lái)開(kāi)發(fā)新的算法?；谶@一思想，Mirjalili S于2016年提出了正弦余弦算法(sine cosine algorithm,SCA)，其在飛機(jī)的翼型設(shè)計(jì)[7]，電力系統(tǒng)[8]，圖像分割[9]等方面取得了較好的應(yīng)用效果，充分證實(shí)了SCA解決優(yōu)化問(wèn)題方面的顯著優(yōu)點(diǎn)。然而該算法也存在易陷入局部最優(yōu)和收斂速度較慢等問(wèn)題。

近幾年，國(guó)內(nèi)外研究學(xué)者通過(guò)引入不同的策略，基于SCA提出了不同的改進(jìn)方法。文獻(xiàn)[10]引入動(dòng)態(tài)慣性權(quán)重、指數(shù)型遞減函數(shù)以及變異因子，提出一種多策略改進(jìn)的SCA，提高了算法的收斂速度及精度。文獻(xiàn)[11]設(shè)計(jì)轉(zhuǎn)換參數(shù)拋物線函數(shù)遞減和指數(shù)函數(shù)遞減的兩種策略，平衡了局部開(kāi)發(fā)和全局搜索能力。文獻(xiàn)[12]引入反向?qū)W習(xí)策略，提出一種基于反向?qū)W習(xí)的SCA，提高了種群的多樣性。文獻(xiàn)[13]引入精英反向?qū)W習(xí)和個(gè)體的反思學(xué)習(xí)策略，提出一種具有學(xué)習(xí)機(jī)制的SCA，提高了算法的全局優(yōu)化能力。文獻(xiàn)[14]提出一種基于對(duì)數(shù)非線性參數(shù)調(diào)整和精英混沌搜索策略的交替SCA，提升了算法的全局搜索與局部開(kāi)發(fā)能力。盡管以上研究使SCA在尋優(yōu)精度上有一定的提高，但由于該算法較新穎，對(duì)其研究還需進(jìn)一步加強(qiáng)。

本文針對(duì)原始SCA的不足，通過(guò)引入動(dòng)態(tài)變異因子對(duì)DE算法進(jìn)行改進(jìn)，然后將這種動(dòng)態(tài)變異的DE嵌入到SCA中，改善SCA易陷入局部最優(yōu)的缺點(diǎn)。同時(shí)通過(guò)個(gè)體的適應(yīng)度值引入自適應(yīng)慣性權(quán)重，提出一種改進(jìn)的SCA(improved SCA,ISCA)。并與原始的SCA,DE以及PSO算法比較，通過(guò)實(shí)驗(yàn)表明ISCA顯著的性能優(yōu)勢(shì)。

1 SCA

(1)

(2)

式中a一般取值為2；t為當(dāng)前的迭代次數(shù)；T為算法的最大迭代次數(shù)。

最后計(jì)算更新后種群中所有個(gè)體的適應(yīng)度值，選出當(dāng)前迭代的最優(yōu)位置和對(duì)應(yīng)的最優(yōu)適應(yīng)度值。通過(guò)不斷增加迭代次數(shù)來(lái)更新個(gè)體位置，直至滿足終止條件跳出循環(huán)，輸出當(dāng)前最優(yōu)解。

與其他智能優(yōu)化算法相比，SCA在求解優(yōu)化問(wèn)題的全局最優(yōu)解方面存在一定的優(yōu)勢(shì)：其參數(shù)少，結(jié)構(gòu)簡(jiǎn)單，易實(shí)現(xiàn)，能求解不同領(lǐng)域的優(yōu)化問(wèn)題，如很好解決了優(yōu)化飛機(jī)的翼型設(shè)計(jì)問(wèn)題。同時(shí)也存在一些不足：在部分測(cè)試函數(shù)上易陷入局部最優(yōu)，尋優(yōu)精度有待提高；由于慣性權(quán)重一直默認(rèn)為1，在迭代后期上一代個(gè)體的位置信息易使得當(dāng)前個(gè)體發(fā)生位置震蕩。

2 ISCA

2.1 嵌入動(dòng)態(tài)變異的差分進(jìn)化

針對(duì)原始SCA在部分測(cè)試函數(shù)上易陷入局部最優(yōu)的問(wèn)題，嵌入全局搜索能力較強(qiáng)的動(dòng)態(tài)變異DE算法，該算法主要包括如下操作步驟:

1)變異操作，標(biāo)準(zhǔn)DE算法中變異操作的變異因子F的值為常數(shù)，其值越大全局搜索能力就越強(qiáng)，本文采用動(dòng)態(tài)的變異因子F，使得F隨著迭代次數(shù)的增加而減小，前期保持較強(qiáng)的全局搜索能力，后期保持較強(qiáng)的局部開(kāi)發(fā)能力，變異因子F和變異操作的表達(dá)式分別為

F=0.4×[cos((t-1)π/T)+Fmax]+Fmin

(3)

i≠k1≠k2≠k3

(4)

2)交叉操作，通過(guò)交叉概率決定個(gè)體的交叉情況，交叉操作表示為

(5)

3)選擇操作，采用貪婪策略從當(dāng)前目標(biāo)個(gè)體和經(jīng)過(guò)變異、交叉操作之后的實(shí)驗(yàn)個(gè)體之間選擇適應(yīng)度值更優(yōu)者。

從以上三個(gè)操作步驟可以看出DE算法采用變異和交叉操作，通過(guò)增加種群的多樣性來(lái)提高全局搜索能力。采用貪婪策略選擇較優(yōu)的個(gè)體作為下一次迭代個(gè)體，增強(qiáng)算法收斂到全局最優(yōu)的能力。而從式(1)可以看出，在SCA中個(gè)體的搜索機(jī)制與DE算法不同，主要依賴上一次個(gè)體位置及當(dāng)前最優(yōu)位置來(lái)進(jìn)行自身位置的更新，導(dǎo)致算法有可能陷入局部最優(yōu)。因此，將動(dòng)態(tài)變異的DE算法嵌入到SCA中，有利于加強(qiáng)SCA的全局搜索能力，改善其易陷入局部最優(yōu)的缺點(diǎn)。

主要思想是將動(dòng)態(tài)變異的DE嵌入到SCA的位置迭代之后，通過(guò)交叉、變異操作之后分別計(jì)算當(dāng)前個(gè)體的適應(yīng)度值與之前僅執(zhí)行SCA個(gè)體的適應(yīng)度值，并作比較進(jìn)行擇優(yōu)選擇，只有適應(yīng)度較優(yōu)的個(gè)體才被選為下一次迭代的個(gè)體，否則繼續(xù)選用僅執(zhí)行SCA的個(gè)體。

2.2 引入自適應(yīng)慣性權(quán)重

在SCA迭代尋優(yōu)的過(guò)程中，應(yīng)用較多的是隨著時(shí)間線性減小的慣性權(quán)重，經(jīng)過(guò)測(cè)試發(fā)現(xiàn)，在部分單峰函數(shù)上有較好的性能提升，但在其他函數(shù)上性能表現(xiàn)較差。為了彌補(bǔ)這一不足，本文在嵌入了動(dòng)態(tài)變異的DE基礎(chǔ)上，提出一種自適應(yīng)的慣性權(quán)重方法。此慣性權(quán)重表示為

(6)

式中wmax和wmin分別為慣性權(quán)重的最大值和最小值；t為當(dāng)前的迭代次數(shù)；T為算法的最大迭代次數(shù)；fi(t)為第i個(gè)個(gè)體在第t次迭代時(shí)的適應(yīng)度值；favg(t)和fbest(t)分別為第t次迭代時(shí)所有個(gè)體的適應(yīng)度平均值和最優(yōu)值。

通過(guò)個(gè)體的適應(yīng)度值對(duì)權(quán)重進(jìn)行動(dòng)態(tài)調(diào)整，當(dāng)個(gè)體的適應(yīng)度值小于或等于適應(yīng)度平均值時(shí)，主要依據(jù)與適應(yīng)度最優(yōu)值的差值來(lái)調(diào)整慣性權(quán)重。其中當(dāng)差值較小時(shí)，說(shuō)明個(gè)體離最優(yōu)解較近，此時(shí)應(yīng)減小慣性權(quán)重，增強(qiáng)局部開(kāi)發(fā)能力。當(dāng)差值較大時(shí)，說(shuō)明個(gè)體離最優(yōu)解較遠(yuǎn)，此時(shí)應(yīng)增大慣性權(quán)重，增強(qiáng)全局搜索能力。當(dāng)個(gè)體的適應(yīng)度值大于適應(yīng)度平均值時(shí)，說(shuō)明個(gè)體離最優(yōu)解更遠(yuǎn)，此時(shí)直接賦值為最大慣性權(quán)重，使個(gè)體保持較強(qiáng)的全局搜索能力。因此，算法的位置更新方程由式(1)變換為如下

(7)

2.3 一種嵌入差分進(jìn)化和慣性權(quán)重的ISCA

ISCA主要針對(duì)原始SCA易陷入局部最優(yōu)的不足，嵌入動(dòng)態(tài)變異的差分進(jìn)化算法來(lái)增強(qiáng)全局搜索能力，同時(shí)引入自適應(yīng)慣性權(quán)重來(lái)平衡全局搜索和局部開(kāi)發(fā)能力，減少算法陷入局部最優(yōu)的概率。ISCA的主要步驟如下：

Step1 初始化種群規(guī)模、種群維度、最大迭代次數(shù)等各參數(shù)，并隨機(jī)產(chǎn)生初始種群；

Step2 計(jì)算初始種群中所有個(gè)體的適應(yīng)度值，并記錄當(dāng)前最優(yōu)個(gè)體；

Step3 更新r1,r2,r3,r4，并依據(jù)式(6)更新慣性權(quán)重；

Step4 每個(gè)個(gè)體依據(jù)式(7)進(jìn)行位置的更新；

Step5 依據(jù)式(3)更新變異因子，并執(zhí)行變異、交叉以及選擇操作；

Step6 計(jì)算種群中所有個(gè)體的適應(yīng)度值，并更新最優(yōu)個(gè)體及最優(yōu)適應(yīng)度值；

Step7 若達(dá)到最大迭代次數(shù)，則算法結(jié)束，輸出最優(yōu)適應(yīng)度值和最優(yōu)個(gè)體，否則返回Step3繼續(xù)執(zhí)行。

時(shí)間復(fù)雜度可以間接反映算法的運(yùn)行效率，在原始SCA中時(shí)間復(fù)雜度主要受算法的最大迭代次數(shù)T，種群規(guī)模N以及空間維度的D影響，SCA的時(shí)間復(fù)雜度為O(T(N×D))。由以上步驟可以看出ISCA較原始SCA主要增加了引入自適應(yīng)慣性權(quán)重和動(dòng)態(tài)變異的差分進(jìn)化算法步驟，其中引入自適應(yīng)慣性權(quán)重增加了O((T×N))的計(jì)算量，引入動(dòng)態(tài)變異的差分進(jìn)化算法增加了O(T(N×D))的計(jì)算量，因此,整個(gè)ISCA的時(shí)間復(fù)雜度為O(2×T(N×D)+O(T×N)，高于SCA的時(shí)間復(fù)雜度。但當(dāng)優(yōu)化問(wèn)題的空間維度較高時(shí)，ISCA的時(shí)間復(fù)雜度近似為O(T(N×D))，與原始SCA的時(shí)間復(fù)雜度一致。

3 算法設(shè)計(jì)與仿真

3.1 參數(shù)選取

種群規(guī)模都設(shè)置為30，最大迭代次數(shù)都設(shè)置為1 000，ISCA的wmax和wmin分別設(shè)置為1.1和0.1，F(xiàn)max和Fmin分別設(shè)置為1.0和0.1，CR設(shè)置為0.2；DE算法的變異因子F和CR依據(jù)文獻(xiàn)[15]分別設(shè)置為0.5和0.2；PSO算法的各參數(shù)依據(jù)文獻(xiàn)[14]進(jìn)行設(shè)置，其中,vmax和vmin分別設(shè)置為6和-6，wmax和wmin分別設(shè)置為0.9和0.2，c1和c2都設(shè)置為1.496。

3.2 算法仿真

本文中所有的算法均采用MATLAB 8.5軟件編程，在Intel?CoreTMi7 CPU，8 GB內(nèi)存，2.6 GHz主頻的計(jì)算機(jī)上實(shí)現(xiàn)。采用表1中9個(gè)測(cè)試函數(shù)對(duì)SCA,DE,PSO和ISCA四種算法的性能進(jìn)行對(duì)比測(cè)試。其中f1～f5為單峰函數(shù)，f6～f9為多峰函數(shù)，除了f6函數(shù)的理論最優(yōu)值為-12 569.5外，其余函數(shù)的理論最優(yōu)值都為0。為了避免單次測(cè)試的誤差，將測(cè)試函數(shù)在每個(gè)算法上獨(dú)立運(yùn)行40次，分別記錄其平均值和標(biāo)準(zhǔn)差。統(tǒng)計(jì)結(jié)果如表2所示，較好的優(yōu)化結(jié)果用粗體表示。同時(shí)選取其中4個(gè)函數(shù)的收斂曲線進(jìn)行展示，如圖1所示。

圖1 部分函數(shù)在SCA,DE,PSO及ISCA算法上的收斂曲線

表1 測(cè)試函數(shù)的基本信息

表2 測(cè)試函數(shù)在4種算法上獨(dú)立運(yùn)行40次的結(jié)果對(duì)比

3.3 ISCA算法分析

從ISCA的設(shè)計(jì)角度分析，在SCA的基礎(chǔ)上嵌入動(dòng)態(tài)變異的DE算法，增強(qiáng)全局搜索能力，同時(shí)根據(jù)個(gè)體的適應(yīng)度值引入自適應(yīng)慣性權(quán)重來(lái)平衡全局搜索和局部開(kāi)發(fā)能力，使得ISCA較原始的SCA有顯著的性能優(yōu)勢(shì)。

ISCA在表1中所有單峰函數(shù)上的平均值和標(biāo)準(zhǔn)差均優(yōu)于對(duì)比的3種算法，且在f1～f3函數(shù)上都收斂到了理論最優(yōu)值。說(shuō)明ISCA在單峰函數(shù)上具有較好的尋優(yōu)精度和穩(wěn)定性；同時(shí)，ISCA在表1中所有多峰函數(shù)上，除了在f6函數(shù)上的平均值差于DE和PSO算法外，其余測(cè)試結(jié)果均優(yōu)于對(duì)比的3種算法，其中在f7和f9函數(shù)上都收斂到理論最優(yōu)值，說(shuō)明ISCA在大多數(shù)多峰函數(shù)上同樣具有較好的尋優(yōu)精度和穩(wěn)定性。

3.4 工程應(yīng)用

將本文提出的ISCA應(yīng)用于一個(gè)經(jīng)典的工程優(yōu)化問(wèn)題，即壓力彈簧設(shè)計(jì)，設(shè)計(jì)圖如圖2所示。

圖2 壓力彈簧設(shè)計(jì)

壓力彈簧設(shè)計(jì)旨在求解彈簧重量的最小值，有3個(gè)變量分別為線的直徑d，平均線圈直徑D，有效線圈數(shù)量N，令x=[x1,x2,x3]=[d,D,N]，其中x1,x2,x3的取值范圍分別為[0.05,2]，[0.25,1.3],[2,15]將此優(yōu)化問(wèn)題描述為如下

(8)

(9)

(10)

(11)

(12)

依據(jù)文獻(xiàn)[16]中的懲罰函數(shù)設(shè)計(jì)方法,將約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，算法的種群規(guī)模設(shè)置為30，最大迭代次數(shù)設(shè)置為1 000，分別獨(dú)立運(yùn)行20次，記錄各參數(shù)的平均值，結(jié)果如表3所示。

表3 壓力彈簧設(shè)計(jì)問(wèn)題的對(duì)比結(jié)果

可以看出，ISCA較DE和PSO算法，能尋求較好的優(yōu)化效果。說(shuō)明ISCA在求解較復(fù)雜的非線性約束優(yōu)化問(wèn)題時(shí)具有一定的性能優(yōu)勢(shì)。

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

通過(guò)在原始的SCA中嵌入動(dòng)態(tài)變異的差分進(jìn)化算法，來(lái)增強(qiáng)全局搜索能力，并根據(jù)個(gè)體的適應(yīng)度值引入自適應(yīng)慣性權(quán)重來(lái)平衡全局搜索和局部開(kāi)發(fā)的能力，使得本文提出的ISCA在測(cè)試函數(shù)上具有較好的尋優(yōu)精度和穩(wěn)定性，且在部分測(cè)試函數(shù)上都收斂到了理論最優(yōu)值。最后將其應(yīng)用于壓力彈簧設(shè)計(jì)的優(yōu)化問(wèn)題，結(jié)果也表明ISCA的性能優(yōu)勢(shì)。基于這些優(yōu)勢(shì)，有望應(yīng)用于無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法的研究中。