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

丁艷 管燕明

[提要] 粒子群算法控制參數(shù)較少、使用簡(jiǎn)單，受到很多專家學(xué)者的關(guān)注。但是，傳統(tǒng)粒子群算法在求解非線性規(guī)劃問(wèn)題時(shí)，比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解。本文在算法設(shè)計(jì)過(guò)程中，對(duì)傳統(tǒng)的粒子群算法進(jìn)行改進(jìn)，以提高求解效果。

關(guān)鍵詞：非線性規(guī)劃；粒子群算法；回收網(wǎng)絡(luò)

中圖分類號(hào)：F27 文獻(xiàn)標(biāo)識(shí)碼：A

收錄日期：2017年11月28日

一、引言

粒子群算法（Particle Swarm Optimization，PSO）為常見(jiàn)優(yōu)化算法，是一種模擬鳥(niǎo)類覓食過(guò)程來(lái)尋求最優(yōu)解的算法，很多問(wèn)題的優(yōu)化都可以使用，如核動(dòng)力、車輛調(diào)度、巡回旅行等。因控制參數(shù)少、使用簡(jiǎn)單、易實(shí)現(xiàn)，粒子群算法受到很多專家學(xué)者的關(guān)注。但是傳統(tǒng)粒子群算法在求解非線性規(guī)劃問(wèn)題時(shí)，比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解，本文在傳統(tǒng)的粒子群算法上進(jìn)行了改進(jìn)，以提高求解效果。

二、粒子群算法介紹

粒子群算法（PSO）是一種基于群體的隨機(jī)優(yōu)化方法。傳統(tǒng)的粒子群算法思路如下：

設(shè)S在維目標(biāo)搜索空間中，有m個(gè)微粒組成一個(gè)群體，那么其中粒子i可以表示為一個(gè)S維的向量xi=（xi1，xi2，…，xis），i=1，2，…，m。同理，群體中的每個(gè)粒子都可以以同樣的方式表示，每個(gè)粒子的位置就是一個(gè)可行解。將其預(yù)先設(shè)定的目標(biāo)函數(shù)來(lái)計(jì)算每一個(gè)粒子的適應(yīng)值，并根據(jù)適應(yīng)值大小來(lái)衡量粒子所在位置的優(yōu)劣程度。在搜索空間中第i個(gè)粒子的飛翔速度也是一個(gè)S維向量，記為V=（v1，v2，…，vs）。除了粒子的飛行位置和飛行速度以外，還需要記錄兩個(gè)重要的信息：第i個(gè)粒子迄今為止搜索到的最優(yōu)位置為PbestiS=（Pbesti1，Pbesti2，…，Pbesti3）；整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為GbestS=（Gbest1，Gbest2，…，Gbest3）。設(shè)f（x）為目標(biāo)函數(shù)，則微粒當(dāng)前最好位置由下式確定：

p（t+1）=pi（t） 若f（xi（t+1））≥f（pi（t））xi（t+1） 若f（xi（t+1））≤f（pi（t））

在基礎(chǔ)上進(jìn)行微粒飛行迭代為兩步操作：位置移動(dòng)和速度變化，基本迭代公式分別為：

v（t+1）=v（t）+c1·（Gbest[]-present[]）+c2·（Pbest-p（t）） （1）

x（t+1）=x（t）+v（t+1） （2）

其中，學(xué)習(xí)因子c1、c2為非負(fù)常數(shù)，c1調(diào)節(jié)粒子飛向自身最好位置方向的步長(zhǎng)，c2調(diào)節(jié)粒子飛向全局最好位置方向的步長(zhǎng)。r1、r2為相互獨(dú)立的偽隨機(jī)數(shù)，服從[0，1]上的均勻分布。

經(jīng)典的PSO算法步驟如下：

Step1：初始化一個(gè)規(guī)模為m的粒子群，并設(shè)定各個(gè)微粒的初始位置和速度。

Step2：設(shè)置適應(yīng)度函數(shù)并計(jì)算每個(gè)微粒的適應(yīng)值。

Step3：把每個(gè)微粒的適應(yīng)值與其經(jīng)歷過(guò)的最好位置時(shí)的適應(yīng)值作比較，若當(dāng)前微粒所在位置的適應(yīng)值較好，則將其作為微粒當(dāng)前的最好位置。

Step4：把每個(gè)微粒的適應(yīng)值與整個(gè)粒子群經(jīng)歷過(guò)的最好位置時(shí)的適應(yīng)值作比較，若當(dāng)前微粒所在位置的適應(yīng)值較好，則將其作為當(dāng)前的粒子群全局的最好位置。

Step5：根據(jù)方程（1）、（2）分別對(duì)粒子的速度和位置進(jìn)行更新。

Step6：如果滿足終止條件，則輸出最優(yōu)解；否則返回Step2。

三、改進(jìn)的粒子群算法設(shè)計(jì)

基本粒子群算法在求解非線性規(guī)劃問(wèn)題時(shí)，比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解，因此，本文在算法設(shè)計(jì)過(guò)程中，對(duì)傳統(tǒng)的粒子群算法進(jìn)行了改進(jìn)，以提高求解效果。改進(jìn)的算法分別采用強(qiáng)引導(dǎo)型粒子群算法和自適應(yīng)粒子群算法對(duì)原有位置、速度迭代公式進(jìn)行優(yōu)化，對(duì)式（1）、（2）進(jìn)行改進(jìn)，使改進(jìn)的位置迭代公式為：

x（t+1）=x（t）+（rand（）+k）·v（t）+10-6·rand（）

其中，rand（）為0～1之間的隨機(jī)數(shù)，k為調(diào)節(jié)系數(shù)，隨著迭代次數(shù)的增加，調(diào)節(jié)系數(shù)逐漸降低，可取k=kmax-·iter，其中iter表示迭代次數(shù)。速度更新采用自適應(yīng)速度更新公式，在傳統(tǒng)的速度更新公式中隨迭代次數(shù)改變？棕，例如迭代100次，可取：

？棕=0.5 1≤gen≤400.1 40≤gen≤600.001 60≤gen≤100

速度更新公式可表示為：

v（）=？棕·v（）+c1·rand（）·（Gbest[]-present[]）+c2·rand（）（Pbest-present[]）

其中，學(xué)習(xí)因子c1和c2為常數(shù)，避免粒子陷入局部最優(yōu)并實(shí)現(xiàn)信息共享，以保證粒子的空間搜索能力，數(shù)值大小設(shè)置具體應(yīng)視情況而定。

（一）粒子的編碼形式。編碼過(guò)程是整個(gè)算法設(shè)計(jì)過(guò)程中的難點(diǎn)之一，高效的編碼方式能夠大大減輕模型運(yùn)算的難度，提高模型求解效率，因此編碼的設(shè)計(jì)十分關(guān)鍵。再制造物流網(wǎng)絡(luò)中參數(shù)較多，編碼過(guò)程需要把每個(gè)變量進(jìn)行合理編碼，以保證在交叉迭代過(guò)程中解得可行性，并保證迭代效率。主要的編碼設(shè)計(jì)思路為：分派過(guò)程中對(duì)粒子進(jìn)行實(shí)數(shù)編碼，根據(jù)分派比例設(shè)定粒子的每一個(gè)分向量，如對(duì)I個(gè)回收點(diǎn)、J個(gè)倉(cāng)儲(chǔ)點(diǎn)、K個(gè)分揀點(diǎn)的編碼可采用如下形式：

（x1，1…xi，j…xI，J||y1，1…yj，k…yJ，K||z1，1…zk，s…zK，S||v1，1…vi，j…vI，J||u1，1…uj，k…uJ，K||w1，1…wk，s…wK，S）x代表從回收點(diǎn)到倉(cāng)庫(kù)段粒子的位置，y代表從倉(cāng)庫(kù)到分揀中心段粒子的位置，z代表從分揀中心到再制造中心段粒子的位置，v代表x的變化速度，u代表y的變化速度，w代表z的變化速度，分揀中心到再利用中心的費(fèi)用另外計(jì)算。

選址過(guò)程對(duì)粒子進(jìn)行實(shí)數(shù)編碼，每一項(xiàng)代表各后選點(diǎn)建立倉(cāng)庫(kù)或分揀中心的大小，若為0，表示此處將不建立物流節(jié)點(diǎn)。因此，J個(gè)倉(cāng)庫(kù)備選點(diǎn)和K個(gè)分揀中心備選點(diǎn)的編碼為：

（x1，x2…xJ||y1，y2…yK||v1，v2…vJ||u1，u2…uK）

（二）粒子群規(guī)模和終止條件。由于粒子群算法有較強(qiáng)的收斂性和全局搜索能力，理論上粒子群規(guī)模較大能提高搜索效率，但考慮到計(jì)算機(jī)運(yùn)算的復(fù)雜度，把粒子群體規(guī)模范圍設(shè)置在50～100之間可以達(dá)到理想效果。終止條件以迭代次數(shù)達(dá)到預(yù)先給定值時(shí)程序終止，一般可以設(shè)置迭代次數(shù)為100次。

四、實(shí)例驗(yàn)算

假設(shè)某第三方企業(yè)需要建立一條廢舊物品回收再制造網(wǎng)絡(luò)。該企業(yè)回收3種廢舊物品，建立5個(gè)廢舊物品回收中心，有2個(gè)存儲(chǔ)中心候選點(diǎn)，擁有3家再制造客戶企業(yè)和2個(gè)分揀中心候選點(diǎn)。其中新建存儲(chǔ)中心10元/m2的單位維修費(fèi)，15元/單位的分揀中心單位維修費(fèi)，3種廢舊物在5個(gè)回收點(diǎn)的回收數(shù)量分別為：1（260，240，360），2（290，370，380），3（380，260，380），4（270，390，280），5（270，300，340）；客戶企業(yè)回收各種物品的數(shù)量：C1（20，68，30），C2（18，28，20），C3（89，12，54）；各個(gè)物流節(jié)點(diǎn)之間的運(yùn)輸費(fèi)率：回收點(diǎn)至存儲(chǔ)/分揀點(diǎn)運(yùn)輸費(fèi)率為：H1（0.13，0.21，0.06）/（0.10，0.07，0.06），H2（0.14，0.12，0.16）/（0.24，0.22，0.19），H3（0.24，0.18，0.09）/（0.13，0.07，0.24），H4（0.12，0.1，0.05）/（0.13，0.07，0.07），H5（0.22，0.23，0.19）/（0.17，0.16，0.18）；分揀點(diǎn)至客戶企業(yè)運(yùn)輸費(fèi)率：1-1（0.09，0.08，0.16），1-2（0.07，0.04，0.15），2-1（0.17，0.05，0.08），2-2（0.17，0.22，0.09），3-1（0.05，0.13，0.09），3-2（0.21，0.08，0.14）；存儲(chǔ)點(diǎn)至分揀點(diǎn)運(yùn)輸費(fèi)率：1-1（0.19，0.08，0.16），1-2（0.07，0.14，0.5），2-1（0.17，0.08，0.08），2-2（0.05，0.22，0.19）；其他各種費(fèi)率：3種廢舊物品的利潤(rùn)率（元/件）分別為（150，130，100），（4，3，1）為分揀中心廢棄率（%），（1，7，3）為存儲(chǔ)中心物品廢棄率（%）。

（一）目標(biāo)函數(shù)

maxh（X）=Q+O-T-W-B+A+C+D+P

（二）約束條件。約束條件可表示為：

可得各物流節(jié)點(diǎn)的容量為：2924和2201為存儲(chǔ)點(diǎn)I的存儲(chǔ)容量（m3），1636和1082為分揀點(diǎn)J的分揀量。

五、結(jié)論

鑒于傳統(tǒng)粒子群算法在求解非線性規(guī)劃問(wèn)題時(shí)，比較容易陷入局部最優(yōu)而找不到全局最優(yōu)解，因此，本文在算法設(shè)計(jì)過(guò)程中，對(duì)傳統(tǒng)的粒子群算法進(jìn)行了改進(jìn)，對(duì)第三方廢舊物品回收企業(yè)建立一條物品再制造回收網(wǎng)絡(luò)進(jìn)行求解，結(jié)果顯示改進(jìn)的粒子群算法具有更好的效果。

主要參考文獻(xiàn)：

[1]劉建華.粒子群算法的基本理論及其改進(jìn)研究[D].長(zhǎng)沙：中南大學(xué)，2009.

[2]劉成洋，閻昌琪.粒子群遺傳算法及其應(yīng)用[J].核動(dòng)力工程，2012.33.4.

[3]李雅瓊.基于粒子群算法的遺傳算法優(yōu)化研究[J].蘭州文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2017.31.1.

[4]黃太安，生佳根.一種改進(jìn)的簡(jiǎn)化粒子群算法[J].計(jì)算機(jī)仿真，2013.30.2.

[5]蒲興成.基于改進(jìn)粒子群算法的移動(dòng)機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃[J].智能系統(tǒng)學(xué)報(bào)，2017.12.6.