基于混沌優(yōu)化的動(dòng)態(tài)自適應(yīng)粒子群優(yōu)化算法

朱洪根，田立勤,2，陳 楠

(1. 華北科技學(xué)院 計(jì)算機(jī)學(xué)院,北京 東燕郊 065201; 2. 青海師范大學(xué) 計(jì)算機(jī)學(xué)院,青海 西寧 810000)

0 引言

粒子群算法(Particle Swarm Optimization,PSO)是受鳥(niǎo)群和魚(yú)群捕食行為啟發(fā)而產(chǎn)出的一種全局迭代優(yōu)化算法，是由Kennedy和Eberhart等[1]在1995年提出的一種演化算法，該算法的優(yōu)點(diǎn)為:結(jié)構(gòu)簡(jiǎn)單、收斂速度快、魯棒性強(qiáng)。

由于PSO算法在尋優(yōu)搜索過(guò)程中，不能很好的平衡粒子的局部和全局搜索能力，導(dǎo)致PSO算法易陷入局部最優(yōu)，降低了PSO尋優(yōu)解的精確度。基于此，Shi與Eberhar[2]于1998年提出慣性權(quán)重的概念(基本粒子群算法,BPSO)，通過(guò)慣性權(quán)重可以更好的控制粒子的搜索范圍，慣性權(quán)重偏大則有利于提高算法的全局搜索能力，偏小則有利于增強(qiáng)算法的局部搜索能力。針對(duì)PSO算法的全局和局部搜索能力不平衡問(wèn)題，Shi與Eberhart進(jìn)一步提出了線性遞減的慣性權(quán)重[3](標(biāo)準(zhǔn)粒子群算法,SPSO)，該算法對(duì)靜態(tài)的慣性權(quán)重進(jìn)行了改進(jìn)，線性遞減的慣性權(quán)重可以對(duì)粒子的迭代前期和后期搜索行為進(jìn)行限定，粒子在整個(gè)迭代期間可以進(jìn)行多元搜索。文獻(xiàn)[4]使用壓縮因子K來(lái)保證PSO快速收斂(KPSO)，該算法比SPSO能夠更快收斂，但也易陷入早熟狀態(tài)。針對(duì)粒子群算法的優(yōu)化問(wèn)題，國(guó)內(nèi)學(xué)者也取得了一定的研究成果。文獻(xiàn)[5]提出一種基于鄰域速度模仿策略的粒子群算法，該算法讓迭代中的粒子以一定的概率直接模仿鄰域內(nèi)的最優(yōu)粒子的速度，自適應(yīng)的調(diào)整粒子的收斂情況，并對(duì)速度排名靠后的粒子進(jìn)行質(zhì)心變異，以增強(qiáng)算法跳出局部極值的能力。文獻(xiàn)[6]將種群分成3個(gè)子種群，不同種群之間的參數(shù)設(shè)置將影響最后的PSO算法的綜合性能，但該算法需要憑借經(jīng)驗(yàn)對(duì)其算法本身進(jìn)行參數(shù)設(shè)置。文獻(xiàn)[7]針對(duì)求解符號(hào)回歸問(wèn)題，提出突變算子和散開(kāi)算子的概念以改進(jìn)粒子群算法早熟收斂的問(wèn)題，當(dāng)滿(mǎn)足突變要求時(shí)，對(duì)粒子進(jìn)行突變以改變粒子狀態(tài)；當(dāng)某一點(diǎn)上聚集過(guò)多粒子時(shí)，只保留其中一個(gè)，其余粒子采用突變的方式讓其離開(kāi)原始位置。但文獻(xiàn)[5-7]并沒(méi)有對(duì)粒子群算法的慣性權(quán)重進(jìn)行改進(jìn)，基于此，文獻(xiàn)[8]使用指數(shù)函數(shù)來(lái)構(gòu)造慣性權(quán)重、文獻(xiàn)[9]使用非線性sigmoid函數(shù)來(lái)構(gòu)造慣性權(quán)重，為慣性權(quán)重的改進(jìn)提供了一種新思路。文獻(xiàn)[10]結(jié)合差分進(jìn)化算法對(duì)慣性權(quán)重進(jìn)行改進(jìn)，并加入了邊界值的處理，對(duì)粒子的速度和搜索位置進(jìn)行限制，但文中并沒(méi)有對(duì)陷入局部極值的粒子予以處理，算法容易早熟收斂。文獻(xiàn)[11]采用多尺度選擇性學(xué)習(xí)機(jī)制在多個(gè)維度上進(jìn)行選擇性學(xué)習(xí)，以提高粒子的學(xué)習(xí)效率，當(dāng)粒子處于局部極值狀態(tài)時(shí)，執(zhí)行空間收縮策略，將種群的搜索空間限定在一個(gè)較小的區(qū)域，以增強(qiáng)算法的搜索能力。文獻(xiàn)[12]提出一種自適應(yīng)慣性權(quán)重混沌粒子群算法，使用動(dòng)態(tài)的慣性權(quán)重對(duì)粒子速度進(jìn)行更新，并對(duì)處于局部極值狀態(tài)下的粒子使用Logistic方程的一種演化式對(duì)粒子的位置進(jìn)行更新，但該算法存在穩(wěn)定性不足等問(wèn)題。

綜上所述，針對(duì)基本粒子群算法存在早熟收斂、易陷入局部極值的問(wèn)題，提出了基于混沌優(yōu)化的動(dòng)態(tài)自適應(yīng)粒子群優(yōu)化算法(dynamic adaptive inertial weight particle swarm optimization algorithm based on chaos optimization， DAWCPSO)。使用動(dòng)態(tài)自適應(yīng)的慣性權(quán)重對(duì)粒子在迭代前期和后期的搜索行為進(jìn)行改進(jìn)，當(dāng)粒子陷入局部極值狀態(tài)時(shí)，使用混沌優(yōu)化策略擴(kuò)大粒子的搜索范圍，使粒子能夠繼續(xù)在可行域下進(jìn)行尋優(yōu)。

1 基本粒子群算法

(1)

(2)

基本粒子群算法的計(jì)算步驟如下：

step1初始化一個(gè)規(guī)模為N，維度為D的粒子群，設(shè)定粒子的初始位置和速度；

step2計(jì)算適應(yīng)度值；

step3更新pbest和gbest信息：

(1) 將粒子i的適應(yīng)度值和粒子i經(jīng)過(guò)的pbest做比較，如果粒子i的適應(yīng)度值優(yōu)于pbest，則pbest的值為粒子i的適應(yīng)度值；

(2) 將粒子i的適應(yīng)度值和全局最優(yōu)位置gbest做比較，如果粒子i的適應(yīng)度值優(yōu)于gbest，則gbest的值為粒子i的適應(yīng)度值；

step4根據(jù)式(1)和式(2)，更新每個(gè)粒子的位置X和速度V；

step5滿(mǎn)足終止條件則退出，否者返回step2繼續(xù)迭代。

2 DAWCPSO算法

2.1 動(dòng)態(tài)自適應(yīng)的慣性權(quán)重

慣性權(quán)重(ω)表示粒子的歷史速度對(duì)當(dāng)前速度的影響程度，由于慣性權(quán)重的存在，新粒子對(duì)歷史粒子具有一種“記憶”，能夠平衡新粒子的搜索行為。慣性權(quán)重較大，則粒子的全局搜索能力較好；反之，則局部搜索能力較好。在PSO算法迭代過(guò)程中，線性遞減的慣性權(quán)重是對(duì)慣性權(quán)重的一種比較基礎(chǔ)改進(jìn)方式，但PSO算法的迭代演化過(guò)程是一種十分復(fù)雜的計(jì)算，線性遞減的方法顯得相對(duì)單一。在迭代后期，慣性權(quán)重偏小，當(dāng)粒子的pbest和gbest距離較近時(shí)，所有粒子會(huì)快速趨于一點(diǎn)，此時(shí)粒子速度接近于零，雖然能較快收斂，但是也導(dǎo)致了算法早熟收斂。因此，本文提出一種新的動(dòng)態(tài)自適應(yīng)慣性權(quán)重方法，公式如式(3)和式(4)，在算法演化后期，慣性權(quán)重稍有提升，能夠提升算法演化后期的全局搜索能力。

(3)

(4)

式中，iter和itermax分別表示當(dāng)前迭代次數(shù)和最大迭代次數(shù)；參數(shù)k是迭代系數(shù)[12]，以確保慣性權(quán)重在迭代前期較大和后期較小的需要[3,13]。

2.2 結(jié)合混沌優(yōu)化擺脫局部極值

混沌(Chaos)是一種非線性的自然現(xiàn)象[14,15]，其行為復(fù)雜，類(lèi)似隨機(jī)，但也有內(nèi)在規(guī)律性。由于混沌運(yùn)動(dòng)具有遍歷性，利用混沌運(yùn)動(dòng)的思想優(yōu)化粒子搜索路徑會(huì)比盲目無(wú)序的隨機(jī)搜索更具有優(yōu)越性，它可以避免每次的隨機(jī)運(yùn)動(dòng)不會(huì)發(fā)生重復(fù)。常用的產(chǎn)生類(lèi)似于隨機(jī)的混沌序列的方程式為L(zhǎng)ogistic映射，如式(5)所示。

(5)

(6)

(7)

2.3 DAWCPSO算法計(jì)算流程

圖1是改進(jìn)后的粒子群優(yōu)化算法(DAWCPSO)的計(jì)算流程圖，以下是DAWCPSO算法的計(jì)算步驟：

Step1初始化一個(gè)規(guī)模為N，維度為D的粒子群，設(shè)定參數(shù)μ和η，給定粒子的初始位置和速度；

Step2計(jì)算適應(yīng)度值；

Step3更新pbest和gbest信息：

(1) 將粒子i的適應(yīng)度值和粒子i經(jīng)過(guò)的pbest做比較，如果粒子i的適應(yīng)度值優(yōu)于pbest，則pbest的值為粒子i的適應(yīng)度值；

(2) 將粒子i的適應(yīng)度值和全局最優(yōu)位置gbest做比較，如果粒子i的適應(yīng)度值優(yōu)于gbest，則gbest的值為粒子i的適應(yīng)度值。

Step4對(duì)粒子的位置X和速度V進(jìn)行更新：

(1) 根據(jù)式(3)和式(4)更新當(dāng)前迭代的慣性權(quán)重；

(2) 根據(jù)式(1)和新的慣性權(quán)重更新粒子的速度，并判斷更新后的粒子速度是否超出速度的臨界值，當(dāng)超出臨界值時(shí)，則將當(dāng)前粒子的速度設(shè)為臨界值狀態(tài)；

(3) 根據(jù)式(7)判斷當(dāng)前粒子的位置是否處于局部極值狀態(tài)，如果是，則使用式(5)更新粒子的位置信息，否則使用式(1)更新粒子的位置，判斷更新后的粒子位置是否超出位置區(qū)間的臨界值，如果是，則將粒子放在搜索去邊界繼續(xù)搜索。

Step5如果當(dāng)前迭代次數(shù)大于最大迭代次數(shù)itermax則退出，否者返回Step2繼續(xù)迭代。

圖1 DAWCPSO算法流程圖

2.4 算法復(fù)雜度分析

算法時(shí)間復(fù)雜度是一種能定性描述當(dāng)前算法的運(yùn)行時(shí)間的指標(biāo)，算法時(shí)間復(fù)雜度越大，表示算法的執(zhí)行效率越低，時(shí)間復(fù)雜度越小，則執(zhí)行效率越高。

假設(shè)粒子總數(shù)為N、搜索維度為D、最大迭代次數(shù)為Imax，假設(shè)基本粒子群算法每一次迭代過(guò)程的計(jì)算時(shí)間為T(mén)B，則T1為N×D×Imax×TB。假設(shè)DAWCPSO算法在每次迭代過(guò)程中的計(jì)算時(shí)間為T(mén)D，則T2為N×D×Imax×TD，從T1和T2可以看出，BPSO和DAWCPSO算法的時(shí)間復(fù)雜度本質(zhì)上取決于算法每次迭代過(guò)程的計(jì)算時(shí)間。BPSO算法的每次迭代需要對(duì)式(1)和式(2)進(jìn)行計(jì)算；DAWCPSO算法的每次迭代則先對(duì)式(1)進(jìn)行計(jì)算，再根據(jù)式(7)的計(jì)算結(jié)果做出判斷選擇(2)或式(5)進(jìn)行計(jì)算。但由于當(dāng)前適應(yīng)度值和全局最優(yōu)值的計(jì)算結(jié)果是在對(duì)式(7)判斷之前計(jì)算完成的，所以DAWCPSO算法比BPSO算法需要多花的時(shí)間開(kāi)銷(xiāo)便是對(duì)式(7)中的分子和分母做商值計(jì)算的時(shí)間以及與η做判斷的時(shí)間，其時(shí)間復(fù)雜度相當(dāng)于在BPSO算法基礎(chǔ)上多做了兩次計(jì)算。根據(jù)時(shí)間復(fù)雜度的計(jì)算規(guī)則，這兩次計(jì)算所消耗的時(shí)間屬于常數(shù)時(shí)間，可忽略不計(jì)，其推理過(guò)程如下：

式中，n表示算法的運(yùn)算量。

綜上所述，DAWCPSO算法的時(shí)間復(fù)雜度和基本粒子群算法的時(shí)間復(fù)雜度都為O(n)，空間復(fù)雜度也是O(n)。

3 算例分析

為了驗(yàn)證DAWCPSO算法的有效性，使用6種測(cè)試函數(shù)對(duì)該算法進(jìn)行測(cè)試，測(cè)試函數(shù)信息見(jiàn)表1，并與BPSO[2]、SPSO[3]、KPSO[4]、IPSO[1]算法進(jìn)行比較。

表1 測(cè)試函數(shù)及其參數(shù)

3.1 實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)定

3.1.1 實(shí)驗(yàn)環(huán)境

硬件環(huán)境：CPU型號(hào)為Intel Core i5-10300H @ 2.50 GHz (8 CPUs)，內(nèi)存為DDR4 (16G )，硬盤(pán)為KINGSTON OM8PCP3(512G)；軟件環(huán)境：操作系統(tǒng)為64位的Windows10，編程語(yǔ)言為Python 3.6.10，集成開(kāi)發(fā)環(huán)境為PyCharm Professional 2020.2。

3.1.2 參數(shù)設(shè)定

粒子群算法的粒子數(shù)都設(shè)定為30，搜索維度都設(shè)為30，學(xué)習(xí)因子c1和c2都取2，最大迭代次數(shù)為3000次。不同PSO算法的其他參數(shù)設(shè)定如下：BPSO算法的慣性權(quán)重為0.83；SPSO算法中，ωmax為0.9，ωmin為0.4；KPSO算法中，α取值為4.1，則K為0.729；IPSO算法中，a和b分別取值0.1和0.2；DAWCPSO算法中，μ為3.98，η為0.3。

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 實(shí)驗(yàn)結(jié)果

每種算法執(zhí)行50次后取其平均值進(jìn)行比較，各算法對(duì)表1中6種測(cè)試函數(shù)的測(cè)試結(jié)果如圖2-8所示，其中，由于各算法對(duì)Ridge函數(shù)的尋優(yōu)結(jié)果起始點(diǎn)過(guò)高(1464.668)，為了便于觀察，將第1000次迭代到3000次的迭代結(jié)果重新畫(huà)圖，如圖7所示；各算法的平均最優(yōu)解如表2所示。

表2 各算法尋優(yōu)結(jié)果的平均最優(yōu)值

圖2 各算法對(duì)Sphere的收斂曲線

圖3 各算法對(duì)Schwefel’s 2.22的收斂曲線

圖4 各算法對(duì)Ackley的收斂曲線

圖5 各算法對(duì)Schaffer’s F7的收斂曲線

圖6 各算法對(duì)Ridge的收斂曲線

3.2.2 結(jié)果分析

從表2可以看出，DAWCPSO算法在6個(gè)測(cè)試函數(shù)上的測(cè)試效果都要優(yōu)于其他對(duì)比PSO算法。其中，DAWCPSO算法對(duì)Sphere和Rastrigin函數(shù)的解已經(jīng)達(dá)到了理論最優(yōu)解。且在Schwefel’s 2.22、Ackley、Schaffer’s F7、Ridge函數(shù)的測(cè)試結(jié)果中，DAWCPSO算法的解精度也更高。當(dāng)粒子處于局部極值狀態(tài)時(shí)，DAWCPSO算法能夠?qū)Ξ?dāng)前粒子的位置做出調(diào)整，及時(shí)改變粒子的搜索位置使其能夠繼續(xù)在可行域下尋找其他可能解。從圖2～圖6以及圖8可以看出，DAWCPSO算法在較短時(shí)間內(nèi)可收斂到某個(gè)局部極值點(diǎn)，但在該極值點(diǎn)停留一段時(shí)間后，粒子開(kāi)始繼續(xù)迭代尋優(yōu)，進(jìn)一步提高解的精度。

4 結(jié) 論

(1) 針對(duì)粒子群算法易早熟收斂的問(wèn)題，本文提出了基于混沌優(yōu)化的動(dòng)態(tài)自適應(yīng)慣性權(quán)重粒子群優(yōu)化算法，其中，慣性權(quán)重根據(jù)粒子的迭代次數(shù)進(jìn)行調(diào)整，以平衡算法的全局和局部搜索能力。

(2) 當(dāng)DAWCPSO算法判斷當(dāng)前粒子處于局部極值點(diǎn)時(shí)，能夠使用混沌優(yōu)化策略擴(kuò)大粒子的搜索范圍，當(dāng)前粒子能夠獲得一個(gè)新的隨機(jī)且不重復(fù)的位置，從而能夠繼續(xù)在可行域下尋找最優(yōu)解。

(3) 經(jīng)時(shí)間復(fù)雜度分析，在不影響粒子群算法收斂性能的前提下，DAWCPSO算法提升了粒子群算法所求解的精度。