一種動(dòng)態(tài)鄰域自適應(yīng)粒子群優(yōu)化算法

楊穎穎，陳壽文

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）［1］是由 Eberhart和 Kennedy于 1995 年提出的一種隨機(jī)優(yōu)化算法，該算法源于對(duì)鳥群和魚群覓食行為的模擬，因?yàn)樗哂泄ぷ髟砗?jiǎn)單、程序?qū)崿F(xiàn)簡(jiǎn)易、以及計(jì)算參數(shù)少［2］等優(yōu)點(diǎn)，所以被廣泛地應(yīng)用于科學(xué)和工程領(lǐng)域［3］.然而，迭代過(guò)程中群體多樣性逐漸降低，使得算法易于陷入局部最優(yōu)解.針對(duì)PSO算法的這一缺陷，很多學(xué)者開(kāi)展了增強(qiáng)群體多樣性以平衡算法全局搜索能力和局部搜索能力的研究，在一定程度上既提高了PSO算法尋優(yōu)精度又加快了算法收斂速度，例如：湯可宗等［4］引入了廣義中心粒子和狹義中心粒子，設(shè)計(jì)了個(gè)體極值和全局極值的更新策略，提出了增強(qiáng)群體多樣性的雙中心粒子群優(yōu)化算法，改善了PSO算法的收斂速度和精度；陶新民等［5］利用小尺度變異算子完成搜索局部精確解，大尺度變異算子實(shí)現(xiàn)快速發(fā)現(xiàn)全局最優(yōu)解，均勻算子維護(hù)種群多樣性，設(shè)計(jì)了一種結(jié)合多尺度變異算子和均勻算子來(lái)實(shí)現(xiàn)局部解逃逸的協(xié)同變異機(jī)制，提出了粒子群優(yōu)化算法MAEPSO，提高了算法的收斂速度及穩(wěn)定性；唐娜等［6］通過(guò)設(shè)計(jì)部分群體跟蹤適應(yīng)度值較高優(yōu)秀個(gè)體來(lái)保持群體多樣性的搜索機(jī)制，多種群之間通過(guò)全局最優(yōu)解來(lái)實(shí)現(xiàn)信息交換，提出了自適應(yīng)混沌搜索的雙粒子群優(yōu)化算法，提高了算法的收斂速度和精度.上述研究結(jié)果表明增強(qiáng)群體多樣性在一定程度上既提高了PSO算法尋優(yōu)精度又加快了算法收斂速度.本文運(yùn)用粒子聚集度因子［7］來(lái)監(jiān)測(cè)群體多樣性，利用全局版PSO和局部版PSO這兩種算法各自優(yōu)點(diǎn)，通過(guò)監(jiān)測(cè)粒子聚集度因子實(shí)現(xiàn)了一種動(dòng)態(tài)鄰域調(diào)度策略（Dynamic Neighborhood Scheduling Strategy，DNSS），進(jìn)而基于DNSS設(shè)計(jì)了一種動(dòng)態(tài)鄰域自適應(yīng)粒子群優(yōu)化算法（Adaptive PSO based on DNSS，APSOD）.用Sphere等六個(gè)函數(shù)來(lái)測(cè)試，通過(guò)與算法DIWPSO等的比較，實(shí)驗(yàn)結(jié)果顯示APSOD算法具有較強(qiáng)的尋優(yōu)能力和穩(wěn)定性.

1 粒子群優(yōu)化算法及群體反饋參數(shù)

1.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法中，每個(gè)個(gè)體被抽象為一個(gè)具有位置和速度的粒子，粒子位置代表待求解問(wèn)題的一個(gè)候選解.記為第i粒子直到第t次迭代為止所發(fā)現(xiàn)的最優(yōu)位置，gbest為群體迄今為止所發(fā)現(xiàn)的最優(yōu)位置.粒子分別用（1）式和（2）式來(lái)更新自身速度和位置，習(xí)慣上稱這種算法為全局版PSO.

其中，和分別為第t次搜索中第i粒子位置和速度，c1為粒子自身學(xué)習(xí)因子，c2為粒子社會(huì)學(xué)習(xí)因子，r1和r2均為[0,1]中的隨機(jī)數(shù)，ω為慣性權(quán)重，Shi等［8］所提出的DIWPSO算法中ω按照（3）式來(lái)計(jì)算.

其中，ωmax和ωmin分別為慣性權(quán)重的初始值和終止值，t和T分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù).

1999年，Suganthan［9］提出了一種基于鄰域操作的局部版PSO（Local version PSO，LPSO），其基本思想是隨著迭代次數(shù)的增加，各個(gè)粒子鄰域從自身開(kāi)始增至整個(gè)群體，粒子分別用（4）式和（2）式來(lái)更新自身的速度和位置.

1999年，Clerc［10］提出了帶有約束因子的PSO算法（記為CPSO），粒子分別用（5）式和（2）式來(lái)更新自身的速度和位置.

Eberhart和Shi對(duì)算法DIWPSO和CPSO進(jìn)行了比較研究，驗(yàn)證了后者是前者對(duì)應(yīng)慣性權(quán)重為0.729的一種特殊表現(xiàn)形式［11］.

1.2 粒子聚集度因子

群體進(jìn)化過(guò)程中的多樣性可由群體聚集程度來(lái)體現(xiàn)，群體多樣性越大則越分散分布，多樣性越小越密集.通過(guò)監(jiān)測(cè)群體聚集程度可以觀察到群體多樣性的動(dòng)態(tài)變化，張選平等［7］定義了按照（6）式來(lái)計(jì)算的粒子聚集度因子s，并用該因子來(lái)監(jiān)測(cè)群體聚集程度.

其中，N為粒子總數(shù)為第i粒子第t次迭代時(shí)的適應(yīng)度，f( )gbestt為直到第t次迭代粒子群所發(fā)現(xiàn)的最優(yōu)解所對(duì)應(yīng)的適應(yīng)度.

倘若適應(yīng)度函數(shù)值在搜索空間恒大于0，則s∈(0，1],由（6）式可知，粒子聚集度因子s值越大，粒子群聚集度越大；當(dāng)粒子群中的所有粒子具有同一性，則s=1.

2 一種動(dòng)態(tài)鄰域自適應(yīng)粒子群優(yōu)化算法

2.1 動(dòng)態(tài)鄰域調(diào)度策略

群體多樣性是影響粒子個(gè)體行為的一個(gè)關(guān)鍵因素.張選平等［7］用粒子聚集度來(lái)監(jiān)測(cè)群體多樣性.本文設(shè)計(jì)動(dòng)態(tài)鄰域調(diào)度策略的思想是：結(jié)合局部版PSO收斂精度高和全局版PSO快速收斂各自優(yōu)點(diǎn)，選用環(huán)形和星形拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)建不同的粒子鄰域，通過(guò)監(jiān)測(cè)粒子聚集度因子來(lái)自適應(yīng)地確定粒子鄰域.

從PSO算法運(yùn)行過(guò)程來(lái)看，初始時(shí)，隨機(jī)初始化各粒子位置使得粒子聚集度較低；隨著算法迭代運(yùn)行次數(shù)的增加，粒子逐漸向某一個(gè)或多個(gè)位置聚集，使得粒子聚集度呈現(xiàn)上升趨勢(shì)；迭代后期，粒子聚集度趨于最高值，算法也趨于收斂.粒子聚集度較低和較高這兩種情形可用來(lái)區(qū)分群體進(jìn)化過(guò)程中多樣性.粒子聚集度因子（s）值越大，粒子聚集度越高.劃分s隸屬度區(qū)間后，s0＜s≤1和0＜s≤s0可相應(yīng)地指代粒子聚集度較高和較低等2種情形.其中，s0為閥值，后續(xù)測(cè)試中s0為0.45.

局部版PSO中，粒子同時(shí)跟蹤自身所發(fā)現(xiàn)的、以及鄰域中粒子所發(fā)現(xiàn)的迄今為止最優(yōu)位置pbest和lbest來(lái)更新自身速度，粒子鄰域拓?fù)浣Y(jié)構(gòu)不同，鄰域中所包含的其他粒子也各異.圖1（a）為粒子與前后位置相鄰半徑R為2的環(huán)形拓?fù)浣Y(jié)構(gòu)粒子鄰域示意圖，其中，群體規(guī)模假定為8，L{i}記錄了第i個(gè)粒子的鄰域中所包含粒子的編號(hào).全局版PSO中，第i個(gè)粒子的鄰域中所包含粒子是群體除自身以外的其他粒子.圖1（b）中L{i}標(biāo)記了第i個(gè)粒子鄰域內(nèi)其他粒子的編號(hào).

圖1 環(huán)形和星形拓?fù)浣Y(jié)構(gòu)粒子鄰域示意圖

全局版PSO中粒子通過(guò)與群體中其他各個(gè)粒子通信來(lái)加速粒子群收斂速度，使得該算法具有快速收斂特點(diǎn).局部版PSO中鄰域粒子位置鄰接的若干粒子發(fā)生信息交互以提高粒子群尋優(yōu)精度，使得該算法具有高精度收斂特征.本文結(jié)合全局版和局部版PSO各自優(yōu)點(diǎn)，在粒子聚集度較低時(shí)，用星形拓?fù)浣Y(jié)構(gòu)來(lái)確定粒子鄰域，在粒子聚集度較高時(shí)，用環(huán)形拓?fù)浣Y(jié)構(gòu)來(lái)確定粒子鄰域，通過(guò)監(jiān)測(cè)粒子聚集度因子，提出一種動(dòng)態(tài)鄰域調(diào)度策略（Dynamic Neighborhood Scheduling Strategy，DNSS），對(duì)應(yīng)粒子速度更新式如（7）式.

其中，t為當(dāng)前迭代次數(shù)，s為粒子聚集度因子，s0為閥值，χ為約束因子且設(shè)定為0.729，lbest是由相鄰半徑R為2的環(huán)形拓?fù)浣Y(jié)構(gòu)所確定的粒子鄰域最優(yōu)位置，其他參數(shù)函數(shù)同（1）式、（4）式和（5）式.

2.2 自適應(yīng)粒子群優(yōu)化算法

按照（7）式來(lái)確定粒子鄰域拓?fù)浣Y(jié)構(gòu)并更新粒子速度，本文設(shè)計(jì)了一種基于DNSS的自適應(yīng)粒子群優(yōu)化算法（Adaptive PSO based on DNSS，APSOD）.該算法的執(zhí)行過(guò)程為①設(shè)定約束因子χ、最大迭代次數(shù)T和群體規(guī)模N；②初始化粒子群，隨機(jī)產(chǎn)生每個(gè)粒子的位置Xti和速度Vti；③評(píng)價(jià)各個(gè)粒子的適應(yīng)度，并確定各個(gè)粒子的pbest和lbest或種群對(duì)應(yīng)的gbest；④用（6）式來(lái)計(jì)算粒子聚集度因子s；⑤用（7）式和（2）式分別來(lái)更新粒子速度和位置；⑥判定終止運(yùn)行條件是否滿足，若滿足，終止；否則，轉(zhuǎn)步驟3.

3 仿真實(shí)驗(yàn)及結(jié)果分析

本實(shí)驗(yàn)的運(yùn)行環(huán)境為內(nèi)存16G，Inteli7-7500U CPU 2.7GHz，Windows 10操作系統(tǒng)，算法采用Matlab R2018a實(shí)現(xiàn).為了檢驗(yàn)算法APSOD的有效性，用Sphere等6個(gè)函數(shù)來(lái)測(cè)試，并與算法DIWPSO和相鄰半徑R為2的環(huán)形拓?fù)浣Y(jié)構(gòu)所確定粒子鄰域的局部版PSO（記為L(zhǎng)PSO-R2）進(jìn)行比較.粒子群的適應(yīng)度函數(shù)選用各測(cè)試目標(biāo)函數(shù)，對(duì)應(yīng)各測(cè)試函數(shù)及其屬性描述如表1所示.

設(shè)定c1=c2=2，S=40，D=30，算法DIWPSO對(duì)應(yīng)ωmin=0.4，ωmax=0.9.以達(dá)到最大迭代次數(shù)T為算法終止運(yùn)行判定條件，算法獨(dú)立運(yùn)行30輪，記錄算法所有輪最后一次迭代所對(duì)應(yīng)的群體最優(yōu)適應(yīng)度的最小值（Min）、均值（Ave）、中位數(shù)（Median）、最大值（Max）及標(biāo)準(zhǔn)差（Std）如表2和表3所示.

表1 測(cè)試函數(shù)及其屬性描述

表2 不同算法測(cè)試結(jié)果（S=40,D=30,T=3 000）

從表2和表3可以看出，比較的三個(gè)算法均能夠求解到f5的最優(yōu)解；在求解函數(shù)f1～f4和f6最優(yōu)解時(shí)，算法APSOD的Ave指標(biāo)和Median指標(biāo)均要小于其他兩個(gè)算法，這表明所比較的3個(gè)算法中APSOD算法的尋優(yōu)精度最高.在求解函數(shù)f1～f3最優(yōu)解時(shí)，APSOD算法的Std指標(biāo)比DIWPSO和LPSO-R2算法的均要小，求解f4和f6最優(yōu)解時(shí)，APSOD算法的Std指標(biāo)比LPSO-R2算法的稍大，但這兩個(gè)算法的該項(xiàng)指標(biāo)均小于DIWPSO算法.總體上來(lái)看，APSOD算法的穩(wěn)定性強(qiáng)于其他兩個(gè)算法.

依次設(shè)定函數(shù)f1～f6的容許精度為10-40、10-20、0.5、0.05、10-50和5×10-12，算法終止運(yùn)行的判定條件設(shè)定為所求解的測(cè)試函數(shù)達(dá)到容許精度且不超過(guò)最大迭代次數(shù)，算法獨(dú)立運(yùn)行30輪，記錄函數(shù)評(píng)估次數(shù)平均值和成功可達(dá)率如表4所示.

從表4可以看出，就成功可達(dá)率指標(biāo)來(lái)說(shuō)，求解f1～f6函數(shù)最優(yōu)解時(shí)，算法APSOD均能夠達(dá)到可容許的尋優(yōu)精度，算法DIWPSO僅在求解f4和f5時(shí)能夠達(dá)到可容許精度，在求解其他4個(gè)函數(shù)時(shí)均不能達(dá)到，除函數(shù)f1和f3外，LPSO-R2算法均能夠達(dá)到可容許精度；就函數(shù)評(píng)估次數(shù)平均值指標(biāo)來(lái)說(shuō)，除求解函數(shù)f5外，算法APSOD的該項(xiàng)指標(biāo)均要低于算法DIWPSO和LPSO-R2的，這表明所比較的三個(gè)算法在求解函數(shù)f1～f4和f6時(shí)，APSOD算法的收斂速度是最快的；就算法運(yùn)行時(shí)間平均值指標(biāo)來(lái)說(shuō)，算法APSOD的該項(xiàng)指標(biāo)要低于其他兩個(gè)算法，這也在一定程度上說(shuō)明了APSOD算法收斂速度較快.

表3 不同算法測(cè)試結(jié)果（S=40,D=30,T=5 000）

表4 三個(gè)算法的函數(shù)評(píng)估次數(shù)平均值和成功可達(dá)率

另外，以Sphere和Ellipsoid為例，APSOD等3個(gè)算法對(duì)應(yīng)的平均最佳適應(yīng)度（f）的迭代如圖2所示.

圖2 函數(shù)Sphere和Ellipsoid測(cè)試30輪所對(duì)應(yīng)的平均最佳適應(yīng)度進(jìn)化

由圖2可以看出，APSOD算法的平均最佳適應(yīng)度比算法DIWPSO和LPSO-R2都要小，這說(shuō)明算法APSOD的尋優(yōu)能力比其他兩個(gè)算法都要強(qiáng).由以上實(shí)驗(yàn)結(jié)果及其分析可知，總體來(lái)說(shuō)，所比較的三個(gè)算法中，APSOD算法尋優(yōu)能力最強(qiáng)，尋優(yōu)過(guò)程最穩(wěn)定.這說(shuō)明使用粒子聚集度因子判定群體狀態(tài)后，通過(guò)自適應(yīng)調(diào)整粒子鄰域拓?fù)浣Y(jié)構(gòu)可增強(qiáng)粒子群多樣性，進(jìn)而增強(qiáng)粒子群的尋優(yōu)能力，算法APSOD是有效的.

4 結(jié)論

為了提高PSO算法的尋優(yōu)能力，本文選用環(huán)形和星形拓?fù)浣Y(jié)構(gòu)來(lái)構(gòu)建粒子鄰域，提出了一種動(dòng)態(tài)鄰域調(diào)度策略DNSS，進(jìn)而設(shè)計(jì)了基于DNSS的自適應(yīng)PSO算法APSOD.使用6個(gè)基本函數(shù)進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果顯示算法APSOD能增強(qiáng)尋優(yōu)能力，且具有較強(qiáng)的穩(wěn)定性，表明粒子感知鄰域聚集度以調(diào)整鄰域拓?fù)浣Y(jié)構(gòu)利于提高PSO算法尋優(yōu)性能.進(jìn)一步的測(cè)試將在今后的實(shí)際工程問(wèn)題展開(kāi)，如組合優(yōu)化問(wèn)題、車間調(diào)度問(wèn)題等.