基于平均位置學(xué)習(xí)的改進(jìn)粒子群算法研究

楊妹蘭， 劉衍民， 張 倩， 舒小麗

(1.貴州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴陽 550025；2.遵義師范學(xué)院 數(shù)學(xué)學(xué)院, 貴州 遵義 563006；3.貴州民族大學(xué) 數(shù)據(jù)科學(xué)與信息工程學(xué)院, 貴陽 550025)

0 引 言

粒子群算法(Particle Swarm Optimization，PSO)[1]是1995年由 Eberhart 和 Kennedy提出的一種基于模擬鳥類覓食行為過程的隨機(jī)智能優(yōu)化算法。在PSO中，種群的每個(gè)粒子表示所研究問題的候選解，每個(gè)粒子通過向個(gè)體歷史最優(yōu)位置和種群歷史最優(yōu)位置學(xué)習(xí)來更新當(dāng)前速度和位置。PSO由于具有結(jié)構(gòu)簡(jiǎn)單、尋優(yōu)能力強(qiáng)、容易實(shí)現(xiàn)和收斂速度快等優(yōu)點(diǎn)，近幾年被廣泛應(yīng)用于各個(gè)領(lǐng)域，如煤炭[2]、工業(yè)生產(chǎn)[3]和水電調(diào)度[4]等。但是，PSO仍然存在一些問題，比如容易出現(xiàn)早熟問題、維數(shù)災(zāi)難問題和易陷入局部最優(yōu)解等。

為了提高PSO的綜合性能，許多研究者對(duì)PSO存在的問題進(jìn)行相了關(guān)的改進(jìn)研究，主要的改進(jìn)分為：

(1) 鄰居拓?fù)浣Y(jié)構(gòu)的改進(jìn)。研究者們已經(jīng)設(shè)計(jì)了許多不同類型的拓?fù)浣Y(jié)構(gòu)，從而以很多不同方式來改進(jìn)粒子的學(xué)習(xí)策略。如Kennedy等[5-6]提出了幾類基本的領(lǐng)域拓?fù)浣Y(jié)構(gòu)，如環(huán)形結(jié)構(gòu)、星型結(jié)構(gòu)和齒形結(jié)構(gòu)等，還分析了幾種拓?fù)浣Y(jié)構(gòu)對(duì)優(yōu)化問題結(jié)果的作用。文獻(xiàn)[7]利用全局版本和局部版本拓?fù)浣Y(jié)構(gòu)相結(jié)合，從而改進(jìn)了粒子的學(xué)習(xí)策略，有效提高算法的尋最優(yōu)解能力和收斂性能。

(2) 優(yōu)化粒子速度的更新過程。粒子的速度更新公式由學(xué)習(xí)樣本的選擇進(jìn)行決定，如文獻(xiàn)[8]利用個(gè)體間的歐式距離大小來選擇每個(gè)個(gè)體的學(xué)習(xí)樣本，有效增強(qiáng)了種群的多樣性；文獻(xiàn)[9]在粒子速度更新公式中引入全局最優(yōu)位置和綜合最優(yōu)位置作為學(xué)習(xí)對(duì)象，提高了粒子的搜索能力；文獻(xiàn)[10]引入免疫算法的粒子群優(yōu)化方法，既增強(qiáng)了每個(gè)粒子的搜索能力，還提高了算法的收斂性能；文獻(xiàn)[11]提出一種基于貝葉斯迭代法的綜合學(xué)習(xí)粒子群算法，增強(qiáng)了算法的局部最優(yōu)規(guī)避能力。這些改進(jìn)方法對(duì)提高算法的運(yùn)行效率，跳出局部最優(yōu)解具有一定作用。但是，在遇到復(fù)雜的多維多峰問題時(shí)，收斂效果不理想、全局搜索能力和局部開發(fā)能力不協(xié)調(diào)等問題依然存在。

因此，本文針PSO的特性和不足，提出了一種結(jié)合適應(yīng)度距離比值和平均位置的改進(jìn)粒子群算法MLFDR。通過與4個(gè)不同算法進(jìn)行實(shí)驗(yàn)對(duì)比與分析，證明MLFDR能夠更好地平衡局部開發(fā)和全局搜索，同時(shí)算法在求解精度和收斂性能上得到了顯著提高。

1 基本粒子群算法

標(biāo)準(zhǔn)粒子群算法(PSO)是一種生物進(jìn)化算法，它是受到鳥類覓食行為的啟發(fā)。在研究PSO時(shí)，把種群中每個(gè)粒子看作D維搜索空間中的一個(gè)搜索個(gè)體，個(gè)體的當(dāng)前位置視為優(yōu)化問題的一個(gè)可能解，即粒子的飛行過程可視為對(duì)應(yīng)個(gè)體的搜索過程。種群中粒子通過向個(gè)體歷史最優(yōu)位置和種群歷史最優(yōu)位置學(xué)習(xí)來更新當(dāng)前速度和位置。

(1)

(2)

2 改進(jìn)的粒子群算法

2.1 貪心策略

貪心策略總是在當(dāng)前條件下為最優(yōu)的選擇，換句話說，該策略不是從整體上進(jìn)行選擇，而它的選擇只是在某種意義下的局部最優(yōu)解，因此，很多問題自身的特點(diǎn)就決定著該問題采用貪心策略就能獲得最優(yōu)解或者較優(yōu)解。

定義1 貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解決問題方法。

本文改進(jìn)的PSO應(yīng)用貪心策略，粒子群在每次更新位置后，對(duì)局部搜索的結(jié)果個(gè)體歷史最優(yōu)位置(pbest)采用貪心策略選擇，即

(4)

2.2 MLFDR算法

PSO具有參數(shù)比較少、易實(shí)現(xiàn)以及操作方便等優(yōu)點(diǎn)，但算法也具有尋優(yōu)精度較低、前期收斂速度偏慢以及容易陷入局部最優(yōu)解等問題，種群中的每個(gè)粒子僅由它的個(gè)體歷史最優(yōu)位置和種群歷史最優(yōu)位置決定。針對(duì)PSO的上述情況，本文引入比粒子自身適應(yīng)值更好的鄰近粒子和平均位置[12]作為學(xué)習(xí)對(duì)象。在學(xué)習(xí)策略中引入比粒子自身適應(yīng)值更好的鄰近粒子，使種群避免陷入局部最優(yōu)解，還增強(qiáng)粒子的搜索能力。

在選擇過程中，考慮最簡(jiǎn)單和最穩(wěn)定的變化來選擇一個(gè)適應(yīng)值之差與一維位置距離的比值最大對(duì)應(yīng)粒子nbest，用粒子nbest來更新當(dāng)前粒子速度的每個(gè)分量，可提高算法的尋優(yōu)能力和收斂能力。選擇最大比值公式為

(5)

在學(xué)習(xí)策略中引入平均位置作為學(xué)習(xí)對(duì)象，可提升種群的多樣性和改善算法的學(xué)習(xí)策略，同時(shí)還能提高算法的運(yùn)行效率。該算法分為兩個(gè)階段更新粒子[13]，具體改進(jìn)策略如下。

2.2.1 前期引入種群的平均位置的改進(jìn)

階段一是指算法前期更新至第2×ps次的部分(ps表示種群規(guī)模)，改進(jìn)之處是在速度更新公式中引入種群的平均位置作為學(xué)習(xí)對(duì)象，該平均位置綜合了種群所有粒子的飛行行為，使算法在搜索過程具有一定的普遍性，可以保證算法的收斂性，同時(shí)提升了種群的多樣性，還提高了每個(gè)粒子飛行過程的穩(wěn)定性，還能更好地平衡局部開發(fā)能力和全局搜索能力，從而有效增強(qiáng)了算法的尋優(yōu)能力。在每一次更新前，先計(jì)算出當(dāng)前所有粒子位置的平均位置，具體平均位置公式如下：

(6)

(7)

其中，mp(1，j)表示第j維的平均位置；h參數(shù)是一個(gè)社會(huì)影響因素；d表示維數(shù)變量(d≤D)，取β=0.01。

一般情況下，種群的收斂要求每個(gè)粒子位置向量的每個(gè)維度收斂，所以算法的收斂難度與搜索維數(shù)成正比。在搜索維數(shù)的基礎(chǔ)上建立社會(huì)影響因素h，有利于收斂性與多樣性之間有良好的平衡狀態(tài)。根據(jù)觀察，參數(shù)h與優(yōu)化問題維數(shù)d成正比，可以控制種群平均位置的影響；如果該參數(shù)的值取得很大，可能會(huì)出現(xiàn)過早收斂到平均位置的情況，從而不能到達(dá)最佳行為。

在階段一采用貪心策略，每次在當(dāng)前粒子的速度和位置更新后，將更新后的個(gè)體歷史最優(yōu)位置適應(yīng)值(pbestval)與種群歷史最優(yōu)適應(yīng)值(gbestval)比較，若更新后的個(gè)體歷史最優(yōu)適應(yīng)值(pbestval)更優(yōu)，則將對(duì)應(yīng)的個(gè)體歷史最優(yōu)位置(pbest)儲(chǔ)存起來，還將個(gè)體歷史最優(yōu)位置和適應(yīng)值分別賦值給種群歷史最優(yōu)位置和適應(yīng)值；反之就不用儲(chǔ)存且種群歷史最優(yōu)位置和適應(yīng)值保留原值。具體公式如下：

(8)

(9)

其中，sgn表示符號(hào)函數(shù)；pbest(k)表示算法儲(chǔ)存的第k個(gè)個(gè)體歷史最優(yōu)位置。

2.2.2 后期引入最佳位置的平均位置改進(jìn)

階段二是指算法從第2×ps次評(píng)價(jià)之后的部分，粒子個(gè)體的收斂速度較快，但容易出現(xiàn)局部最優(yōu)停滯的現(xiàn)象。為了使算法效果更好，在算法后期引入更新后儲(chǔ)存的所有個(gè)體歷史最優(yōu)位置的平均位置，去替換階段一的平均位置，既可以使算法跳出停滯現(xiàn)象，還提升了局部搜索精度，而且階段一的優(yōu)點(diǎn)依然保持，還能夠很好地協(xié)調(diào)算法的局部開發(fā)能力與全局搜索能力。在本階段更新后繼續(xù)使用貪心策略，若與種群歷史最優(yōu)位置比較后得個(gè)體歷史最優(yōu)適應(yīng)值更優(yōu)，則儲(chǔ)存對(duì)應(yīng)個(gè)體歷史最優(yōu)位置。在階段一結(jié)束后，開始計(jì)算儲(chǔ)存中所有個(gè)體歷史最優(yōu)位置的平均位置，具體平均公式如下：

(10)

其中，u表示儲(chǔ)存?zhèn)€體歷史最優(yōu)位置的個(gè)數(shù)；pbest(k)j表示儲(chǔ)存中被標(biāo)記的第k個(gè)粒子第j維的個(gè)體歷史最優(yōu)位置；mp表示平均位置。

MLFDR的學(xué)習(xí)對(duì)象除了個(gè)體歷史最優(yōu)位置和種群歷史最優(yōu)位置外，還添加了兩個(gè)學(xué)習(xí)對(duì)象，即比粒子自身適應(yīng)值更好的鄰近粒子(nbest)和平均位置(mp)，可保證算法改進(jìn)的優(yōu)點(diǎn)，還能使整個(gè)算法達(dá)到更佳的效果。粒子的迭代更新速度公式如下：

(11)

其中，nbestij表示最佳適應(yīng)度距離比值對(duì)應(yīng)的粒子位置；mp表示平均位置，階段一用式(6)計(jì)算平均位置，階段二用式(10)計(jì)算平均位置；h表示社會(huì)影響因素，控制種群平均位置的影響，還可以更好地平衡種群多樣性與收斂性之間的狀態(tài)。

2.3 改進(jìn)粒子群算法的基本步驟

(1) 種群初始化。種群初始化的粒子是以隨機(jī)方式來生成初始位置和速度。

(2) 計(jì)算適應(yīng)值。計(jì)算每個(gè)粒子的適應(yīng)度值，然后，確定當(dāng)前的個(gè)體歷史最優(yōu)位置和種群歷史最優(yōu)位置，將個(gè)體最優(yōu)的適應(yīng)度值存儲(chǔ)在pbestval中，將種群最優(yōu)的適應(yīng)度值存儲(chǔ)在gbestval中。

(3) 按照式(5)計(jì)算最大值比，求得nbest；用式(7)計(jì)算h；在前ps次更新時(shí),需按照式(6)計(jì)算種群所有粒子位置的平均位置mp。

(4) 更新粒子位置。按照式(11)和式(2)來更新當(dāng)前粒子的速度和位置。

(5) 更新個(gè)體最優(yōu)。將粒子更新后的適應(yīng)度值與其未更新前的適應(yīng)度進(jìn)行比較，取適應(yīng)值較好的粒子作為當(dāng)前迭代后的粒子。

(6) 更新種群最優(yōu)。通過比較個(gè)體歷史最優(yōu)適應(yīng)值和種群歷史最優(yōu)適應(yīng)值，若個(gè)體歷史最優(yōu)適應(yīng)值較好，將對(duì)應(yīng)的個(gè)體歷史最優(yōu)位置儲(chǔ)存起來，且將個(gè)體歷史最優(yōu)適應(yīng)值賦值給種群歷史最優(yōu)適應(yīng)值的方式更新種群歷史最優(yōu)位置。

(7) 判斷算法是否評(píng)價(jià)至第2×ps次，若是則按照式(10)計(jì)算mp后，將mp賦值給步驟(3)的mp。

(8) 算法終止。如果滿足最大迭代數(shù)結(jié)束條件，算法搜索停止；否則返回到步驟(3)繼續(xù)搜索。

MLFDR流程如圖1所示。

圖1 MLFDR算法流程

3 MLFDR算法性能測(cè)試與分析

3.1 檢測(cè)函數(shù)選取

為了測(cè)試MLFDR的收斂速度和全局搜索能力，利用CEC2017測(cè)試函數(shù)中的單峰和多峰共8個(gè)測(cè)試函數(shù)進(jìn)行函數(shù)優(yōu)化的對(duì)比實(shí)驗(yàn)。其中，f4和f5為單峰函數(shù)，f1、f2、f3、f6、f7和f8為多峰函數(shù)，它們分別用于檢驗(yàn)不同算法的搜索速度、尋優(yōu)能力和全局搜索能力。具體測(cè)試函數(shù)見表1。

表1 本文選用的8個(gè)測(cè)試函數(shù)

為了增加這些檢測(cè)函數(shù)的優(yōu)化難度，將部分函數(shù)都進(jìn)行旋轉(zhuǎn)，用“*”表示對(duì)應(yīng)測(cè)試函數(shù)進(jìn)行旋轉(zhuǎn) 。選擇4個(gè)不同算法與本文提出的MLFDR相比較，4個(gè)不同算法分別是：PSO[1]、FDR[8]、wFIPS[14]和UPSO[7]算法。

3.2 算法參數(shù)設(shè)置

選取FDR、PSO、wFIPS和UPSO算法進(jìn)行對(duì)比，為了體現(xiàn)不同算法之間的可比性，實(shí)驗(yàn)中所有算法都取參數(shù)保持一致，種群規(guī)模是10，每個(gè)測(cè)試函數(shù)單獨(dú)運(yùn)行了50次，對(duì)于非旋轉(zhuǎn)的測(cè)試函數(shù)則每次運(yùn)行進(jìn)行3×104函數(shù)評(píng)價(jià)，旋轉(zhuǎn)的測(cè)試函數(shù)則每次運(yùn)行進(jìn)行2×104函數(shù)評(píng)價(jià)，其他參數(shù)設(shè)置見表2。

表2 對(duì)比5個(gè)算法的具體參數(shù)設(shè)置

3.3 實(shí)驗(yàn)結(jié)果和分析

3.3.1 收斂特性仿真實(shí)驗(yàn)

為了檢測(cè)不同算法的收斂特性，給出在確定的函數(shù)評(píng)價(jià)次數(shù)下不同算法的運(yùn)行特性。不同算法以3×104和2×104函數(shù)評(píng)估后的收斂曲線圖分別有圖2和圖3。

從圖2可以看出，采用非旋轉(zhuǎn)測(cè)試函數(shù)檢測(cè)算法的情況，對(duì)于Rastrigin’s 、Rosenbrock’s、Non-con tinuous Rotated Rostrigin’s 、Ackley’s、Happy Cat和HGBat函數(shù)檢測(cè)時(shí)，MLFDR算法取得了最好的運(yùn)行效果，且表現(xiàn)出更加明顯的優(yōu)勢(shì)。而FDR和wFIPS算法在多峰問題上也表現(xiàn)出求解能力，主要是它們的學(xué)習(xí)策略不同于PSO和UPSO算法，可以有效地避免早熟收斂。從圖3可以看出，采用旋轉(zhuǎn)測(cè)試函數(shù)，對(duì)于Rastrigin’s、Non-continuous Rotated Rostrigin’s、High Conditioned Elliptic、Rosenbrock’s、Discus 、Ackley’s、Happy Cat和HGBat 函數(shù)檢測(cè)時(shí)，MLFDR表現(xiàn)出較好的收斂性，主要是引入平均位置來構(gòu)建廣泛學(xué)習(xí)策略，于是提高了種群的多樣性，增強(qiáng)了種群跳出局部最優(yōu)解的能力。

(a) Rastrigin’s 函數(shù)

(a) Rastrigin’s函數(shù)

3.3.2 魯棒性分析

為了檢測(cè)5個(gè)不同算法在相同測(cè)試函數(shù)的不同環(huán)境(函數(shù)旋轉(zhuǎn)和不旋轉(zhuǎn))下算法運(yùn)行是否具有穩(wěn)定性，選擇了3個(gè)Benchmark函數(shù)(Ackley、Happy Cat和HGBat)，通過實(shí)驗(yàn)研究算法在這些測(cè)試函數(shù)的穩(wěn)定性。魯棒性分析結(jié)果在表3中給出，本文“魯棒性”是在50次單獨(dú)運(yùn)行過程中算法成功取到指定閾值的比例，F(xiàn)Es為取到閾值時(shí)的函數(shù)評(píng)價(jià)次數(shù)，S為取到指導(dǎo)閾值的比例(單位是%)。其中3個(gè)函數(shù)的閾值分別是0.4、0.3和0.5。

在表3可以看出，PSO、wFIPS、FDR和MLFDR算法在Ackley’s函數(shù)非旋轉(zhuǎn)情況下100%取到了指定閾值，但在旋轉(zhuǎn)情況下只有MLFDR成功取得閾值。Happy Cat函數(shù)在非旋轉(zhuǎn)和旋轉(zhuǎn)情況下都只有MLFDR算法成功取得閾值，但FDR在旋轉(zhuǎn)和非旋轉(zhuǎn)的情況下表現(xiàn)較為穩(wěn)定，wFIPS在旋轉(zhuǎn)情況下也表現(xiàn)較為穩(wěn)定。HGBat函數(shù)在非旋轉(zhuǎn)和旋轉(zhuǎn)情況下都僅有PSO、FDR和MLFDR算法成功取到了閾值，但MLFDR算法比PSO和FDR算法都用了較少的函數(shù)評(píng)價(jià)。

表3 5個(gè)算法的魯棒性分析

3.3.3 測(cè)試函數(shù)尋優(yōu)結(jié)果分析

為了排除偶然性引起的誤差，分別對(duì)6個(gè)非旋轉(zhuǎn)和8個(gè)旋轉(zhuǎn)測(cè)試函數(shù)進(jìn)行50次獨(dú)立實(shí)驗(yàn)。在多個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上，對(duì)5個(gè)不同算法進(jìn)行50次獨(dú)立運(yùn)行后所得實(shí)驗(yàn)結(jié)果如下。

實(shí)驗(yàn)結(jié)果如表4和表5可知，實(shí)驗(yàn)在相同約束條件下，MLFDR分別在非旋轉(zhuǎn)測(cè)試函數(shù)和旋轉(zhuǎn)測(cè)試函數(shù)的統(tǒng)計(jì)結(jié)果中明顯優(yōu)于另4個(gè)對(duì)比算法。對(duì)于測(cè)試函數(shù)f6，幾種算法尋優(yōu)效果差別不大，MLFDR尋優(yōu)結(jié)果略大于其他4個(gè)算法；對(duì)于f1、f2、f3、f7、f8和旋轉(zhuǎn)的所有測(cè)試函數(shù)，MLFDR尋優(yōu)效果都優(yōu)于其他4個(gè)算法。不論是非旋轉(zhuǎn)測(cè)試函數(shù)還是旋轉(zhuǎn)測(cè)試函數(shù)，MLFDR尋優(yōu)結(jié)果優(yōu)于其他4個(gè)算法，平均值和標(biāo)準(zhǔn)差都比其他4個(gè)算法小，說明MLFDR的穩(wěn)定性和魯棒性優(yōu)于其他4個(gè)算法，證明改進(jìn)后的粒子群算法具有一定優(yōu)勢(shì)。

表4 非旋轉(zhuǎn)測(cè)試函數(shù)尋優(yōu)結(jié)果

表5 旋轉(zhuǎn)測(cè)試函數(shù)尋優(yōu)結(jié)果

3.3.4 Wilcoxon秩和檢驗(yàn)

由表6可知，為了進(jìn)一步評(píng)估MLFDR的性能，在a=5%顯著性水平下，對(duì)30次獨(dú)立運(yùn)行下的MLFDR于其他4個(gè)算法的最佳結(jié)果進(jìn)行Wilconxon秩和檢驗(yàn)。以驗(yàn)證MLFDR所得結(jié)果與其他4個(gè)算法中最好結(jié)果的差別是否有統(tǒng)計(jì)意義。表6顯示檢驗(yàn)結(jié)果所示，小于等于0.05表示結(jié)果有差(符號(hào)“1”)，大于0.05表示結(jié)果沒有差異(符號(hào)“0”)，在8個(gè)基準(zhǔn)測(cè)試函數(shù)中，MLFDR的性能在8個(gè)測(cè)試函數(shù)上與PSO、FDR、wFIPS和UPSO算法有差異，而且MLFDR的p值基本都小于等于0.05，表明MLFDR的差異性在統(tǒng)計(jì)上顯著的。

表6 Wilcoxon秩與檢驗(yàn)p值

4 結(jié) 論

本文為解決PSO存在尋優(yōu)精度不高、易陷入局部最優(yōu)解等不足，提出了一種基于平均位置學(xué)習(xí)的改進(jìn)粒子群算法MLFDR。該算法通過引入比粒子自身適應(yīng)值更好的鄰近粒子和平均位置作為學(xué)習(xí)對(duì)象，改善了算法的早熟收斂問題，提高了收斂速度。其主要研究粒子群算法在優(yōu)化問題時(shí)綜合所有粒子平均位置的有益信息，提高了算法對(duì)函數(shù)的優(yōu)化，特別是多峰函數(shù)優(yōu)化中的性能。通過用8個(gè)測(cè)試函數(shù)進(jìn)行實(shí)驗(yàn)，與其他4個(gè)算法的比較得出MLFDR綜合性能更好。