一種新型的帶有小生境技術(shù)和精英集策略的多目標(biāo)粒子群算法

李艷麗，黃天民,劉雅雅

(西南交通大學(xué), 數(shù)學(xué)學(xué)院，四川 成都 610031)

?

一種新型的帶有小生境技術(shù)和精英集策略的多目標(biāo)粒子群算法

李艷麗，黃天民,劉雅雅

(西南交通大學(xué), 數(shù)學(xué)學(xué)院，四川 成都 610031)

摘要：為提高多目標(biāo)粒子群算法的有效性和運(yùn)行效率，利用小生境技術(shù)求解適應(yīng)度，采取輪盤賭的方法根據(jù)精英集中各個(gè)粒子的適應(yīng)度選取全局最佳位置，提出一種新型的帶有小生境技術(shù)和精英集策略的多目標(biāo)粒子群算法。論文對(duì)算法運(yùn)行的過(guò)程作了調(diào)整，加入小概率變異方法，采用測(cè)試函數(shù)驗(yàn)證算法的有效性。結(jié)果表明，在相同的實(shí)驗(yàn)環(huán)境中本文算法的運(yùn)行時(shí)間為2.113 s，比基于粒子群的多目標(biāo)優(yōu)化算法(4.157s)縮短近一半，即本算法的運(yùn)算效率大大提高了。仿真結(jié)果還表明本文中的算法不僅有很好的收斂性，所得的解還有較好的均勻性。

關(guān)鍵詞：多目標(biāo)優(yōu)化;小生境技術(shù);小概率變異;粒子群;精英集

多目標(biāo)優(yōu)化問(wèn)題中各目標(biāo)之間通常相互制約，對(duì)其中一個(gè)目標(biāo)優(yōu)化必須以其他目標(biāo)的損失為代價(jià)，多目標(biāo)優(yōu)化問(wèn)題的解并非唯一，而且很難評(píng)價(jià)多目標(biāo)問(wèn)題解的優(yōu)劣性。隨著多目標(biāo)問(wèn)題研究的深入,對(duì)解的精度要求也越來(lái)越高，粒子群算法作為一種新而有效的算法因其概念簡(jiǎn)單, 控制參數(shù)少, 尋優(yōu)結(jié)果與初值無(wú)關(guān),具有一定的并行性，一直備受關(guān)注。

粒子群優(yōu)化算法(particle swarm optimization ,PSO)是由Eberhar等于1995年提出的一種進(jìn)化計(jì)算技術(shù),其源于鳥群群體運(yùn)動(dòng)行為的研究[1]。當(dāng)前，已經(jīng)有一些學(xué)者提出了基于PSO的多目標(biāo)粒子群算法，例如:2005年李寧等提出了基于粒子群的多目標(biāo)優(yōu)化算法[2];同年，Coello 等又提出了多目標(biāo)粒子群算法(簡(jiǎn)稱CMOPSO)[3];2012年，凌海風(fēng)等提出了改進(jìn)的約束多目標(biāo)粒子群算法[4];邢小紅等[5]設(shè)計(jì)了一種基于鄰域最大擁擠距離的全局極值選擇算子和基于差分進(jìn)化的精英種群自學(xué)習(xí)算子對(duì)多目標(biāo)粒子群算法進(jìn)行了改進(jìn) 。但是傳統(tǒng)的粒子群算法在多目標(biāo)求解方面還有待于進(jìn)一步的研究，比如粒子群算法本身在全局搜索和收斂方面也還有一定的不足，運(yùn)算復(fù)雜度還比較高，運(yùn)算時(shí)間還比較長(zhǎng)。文獻(xiàn)[2]雖然提高了解的均勻性，但也增加了運(yùn)算的復(fù)雜性、延長(zhǎng)了運(yùn)算時(shí)間；文獻(xiàn)[6]中增強(qiáng)了解的全局性，但是優(yōu)化的策略仍有待于改善。 本文在文獻(xiàn)[2，6]的研究的基礎(chǔ)上，旨在降低粒子群算法運(yùn)算的復(fù)雜性、減少運(yùn)算時(shí)間，提高算法的效率，在原有的算法中加入了邊界限制和擁擠距離策略。

1多目標(biāo)優(yōu)化問(wèn)題及其相關(guān)概念

一般的多目標(biāo)問(wèn)題可以描述如下：

minf(x)=min{f1(x),f2(x),f3(x),…,fn(x)}，

(1)

s.t. x∈S={x|g1(x)≤0,1=1,2,…,p}。

其中：x=[x1,x2,x3,…,xm]T為m維決策變量，fk(x)(k=1,2,…,n)表示第i個(gè)目標(biāo)函數(shù)；g1(x)≤0,(1=1,2,…,p)表示第j個(gè)不等式約束條件，(由于等式約束在求解的過(guò)程中通常轉(zhuǎn)化為不等式約束，故此省略)S為決策變量的可行域。

占優(yōu)：對(duì)于決策變量x、y,若有fk(x)≤fk(y)，(k=1,2,…,n),且至少有一個(gè)k使得fk(x)

Pareto最優(yōu)解(非劣解)：如果在決策空間里沒(méi)有其他解比x*占優(yōu)，則稱x*為多目標(biāo)優(yōu)化問(wèn)題 Pareto最優(yōu)解(或Pareto非劣解)。

2改進(jìn)的多目標(biāo)粒子群算法

文獻(xiàn)[1]提出的粒子群算法是基于鳥群遷徙行為的思想。假設(shè)現(xiàn)有一個(gè)由N個(gè)粒子組成的群落，每個(gè)粒子i的位置都是決策空間的一個(gè)m維的向量，記為xi=[xi1,xi2,xi3,…,xim]T(i=1,2,…,N)，各個(gè)粒子的適應(yīng)值可由xi代入目標(biāo)函數(shù)或適應(yīng)度函數(shù)求得，由適應(yīng)值的大小判斷粒子的優(yōu)劣。把每個(gè)粒子的當(dāng)前最優(yōu)位置(與最優(yōu)值對(duì)應(yīng))與歷次選代中的最優(yōu)位置進(jìn)行比較，得出個(gè)體歷史最優(yōu)位置。第i個(gè)粒子在算法搜索過(guò)程中的歷史最優(yōu)位置記為Xipb=[xi1pb,xi2pb,xi3pb,…,ximpb]T，全體粒子的歷史最優(yōu)位置記為Xigb=[xi1gb,xi2gb,xi3gb,…,ximgb]T，每個(gè)粒子i也有各自相對(duì)應(yīng)的速度，記為Vi=[vi1,vi2,vi3,…,vim]T(i=1,2,…,N)。

在粒子群算法的求解過(guò)程中粒子的速度和位置更新公式如下：

(2)

xid(t+1)=xid(t)+vid(t+1);

(3)

Vmax=[v1max,v2max,…,vmmax]T。

(4)

式中：Vmax為常數(shù)；c1、c2稱為學(xué)習(xí)因子，為非負(fù)常數(shù)；ri1,t、ri2,t為0和1之間的隨機(jī)數(shù)；w稱為慣性權(quán)重，當(dāng)選擇較大的慣性權(quán)重時(shí)，粒子群算法通常因?yàn)榱Ｗ悠x全局最優(yōu)位置和自己的歷史最優(yōu)位置而具有較好的全局搜索能力，較小的慣性權(quán)重就不利于全局搜索。

本文借鑒文獻(xiàn)[2]中適應(yīng)度求解的思想，在可行解空間中隨機(jī)初始化粒子群，選取非劣解“粒子”構(gòu)成精英集P，精英集在粒子更新的過(guò)程中可以指導(dǎo)粒子的“飛行”。通過(guò)小生境技術(shù)求解精英集中粒子的適應(yīng)度，粒子的聚集程度越高，粒子的適應(yīng)度就越小。第i個(gè)粒子的適應(yīng)度定義如下：

(5)

其中，j∈P,s(d(ij))為P中第i個(gè)粒子和第j個(gè)粒子的適應(yīng)度分享函數(shù)：

(6)

式中：σshare為小生境半徑，在計(jì)算時(shí)可預(yù)設(shè)為常數(shù)；α為常數(shù)。

本算法采取輪盤賭的方法根據(jù)精英集中各個(gè)粒子的適應(yīng)度選取全局最佳位置，在算法迭代過(guò)程中，具有全局最佳位置的粒子指導(dǎo)其他粒子按照公式(2)—(4)更新各個(gè)粒子的位置和速度；每次迭代之后，選取所得粒子中的非劣解加入到精英集中，這樣精英集中的粒子數(shù)會(huì)因迭代次數(shù)的增加而不斷增加，從而影響算法的運(yùn)行速度；因此，當(dāng)精英集中的粒子數(shù)超過(guò)精英集的最大容量時(shí)，根據(jù)適應(yīng)度公式(5)計(jì)算精英集中各粒子的適應(yīng)度，刪除其中適應(yīng)度較小的個(gè)體粒子。當(dāng)算法滿足終止迭代條件時(shí)，精英集的粒子即可認(rèn)為是所求的Pareto最優(yōu)解。

改進(jìn)后的算法具體步驟如下：

1)設(shè)置粒子群的種群規(guī)模N，最大速度Vmax，精英集的容量M，預(yù)設(shè)M=?，迭代次數(shù)t=0，設(shè)定算法終止的條件(迭代次數(shù)達(dá)到預(yù)先設(shè)定值)，隨機(jī)初始化粒子的位置、速度，計(jì)算各粒子的目標(biāo)函數(shù)值，得出初始解。

2)選取粒子群中的非劣解加入精英集中，利用式(5)計(jì)算精英集中各粒子的適應(yīng)度。

3)當(dāng)?shù)螖?shù)小于最大迭代次數(shù)，執(zhí)行步驟4)至7)，否則跳出循環(huán)，算法結(jié)束。

4)根據(jù)精英集中各個(gè)粒子的適應(yīng)度選取全局最佳位置Xigb，按照公式(2)—(4)更新各個(gè)粒子的位置和速度，再次計(jì)算種群內(nèi)每個(gè)粒子的目標(biāo)函數(shù)值。

5)選取粒子群中的非劣解加入精英集中，利用式(5)計(jì)算精英集中各粒子的適應(yīng)度，并且刪除精英集中適應(yīng)度小的劣解，保證精英集中的個(gè)體數(shù)不超過(guò)其最大容量。

6)如果當(dāng)前粒子的位置優(yōu)于其歷史最佳位置的粒子X(jué)ipb，則用當(dāng)前的粒子替換Xipb，如果當(dāng)前粒子的位置既不優(yōu)于也不劣于其歷史最佳位置的粒子，則按照50%的概率替換或保持Xipb，對(duì)于劣于Xipb的粒子，按照5%的幾率進(jìn)行變異操作，即再次初始化該粒子。

7)如果群體中某個(gè)粒子當(dāng)前的位置優(yōu)于全體粒子的歷史最佳位置Xigb，則更新，否則保持全體粒子的歷史最佳位置Xigb不變。

8)最后所得的精英集即為所求的Pareto最優(yōu)解集。

本算法在求解過(guò)程中加入限制條件(如步驟中的Vmax，精英集的容量M)，在步驟6)中改善了變異機(jī)制。

3實(shí)例驗(yàn)證算法的有效性及結(jié)果分析

為了驗(yàn)證本文算法的有效性，本文采用了測(cè)試函數(shù)，在算法運(yùn)行的過(guò)程中群粒子數(shù)和迭代次數(shù)根據(jù)函數(shù)的復(fù)雜程度選取，對(duì)每個(gè)函數(shù)均做50次試驗(yàn)以消除隨機(jī)性。

測(cè)試函數(shù)1(Schaffer函數(shù))：

minf1(x)=x2，-3≤x≤3；

minf2(x)=(x-2)2，-3≤x≤3。

測(cè)試函數(shù)2(K.Deb函數(shù))：

minf1(x)=x1，

minf2(x)=g(x)×h(x)。

其中：

1(xi2-10·cos(4πxi))；

-5≤xi≤5,x=(x1,…xi,…xn)。

算法選取的參數(shù)如下：

w=0.729,c1=c2=1.495,σshare=0.48,α=1.2,P=200。

結(jié)果分析：對(duì)于測(cè)試函數(shù)1、2(參數(shù)n取2)，當(dāng)粒子數(shù)和最大迭代次數(shù)均取50時(shí)，所得的解99%均為Pareto最優(yōu)解，而且解的均勻性也比較好，算法所得結(jié)果在解的均勻性、錯(cuò)誤率和分散性方面和文獻(xiàn)[2]基本一致。由運(yùn)算結(jié)果可知，本算法的收斂速度要比標(biāo)準(zhǔn)的粒子群算法快了許多，而且在相同的實(shí)驗(yàn)環(huán)境下本文算法的運(yùn)行時(shí)間(2.113 s)比文獻(xiàn)[2]運(yùn)行時(shí)間(4.147 s)縮短了近一半，即本算法的運(yùn)算效率大大提高了。

圖1和圖2分別為測(cè)試1和測(cè)試2的某一次的運(yùn)行結(jié)果，即Pareto邊界。

圖3為在一次實(shí)驗(yàn)時(shí)的2種算法的貼近度收斂情況：(虛線為本算法，實(shí)線為文獻(xiàn)的算法)由圖3可以看出本算法的收斂性確實(shí)具有一定的優(yōu)越性。

圖1　測(cè)試函數(shù)1的Pareto最優(yōu)解

圖2　測(cè)試函數(shù)2的Pareto最優(yōu)解

圖3　實(shí)驗(yàn)時(shí)的2種算法的貼近度收斂情況

4結(jié)論

本文在基本粒子群算法的基礎(chǔ)上，結(jié)合了小生境技術(shù)和精英集策略的優(yōu)勢(shì)，采用了輪盤賭的方法，在算法運(yùn)行的過(guò)程中加入了小概率變異策略，使得粒子群算法具有更好的全局搜索能力、收斂性，并且算法所得到的Pareto最優(yōu)解分布也更均勻，最重要的是，本算法的運(yùn)算效率大大提高了。但是本文設(shè)計(jì)的算法在保持解的多樣性方面還有待于進(jìn)一步研究，把算法用于解決實(shí)際問(wèn)題也是下一步將要進(jìn)行的工作。

參考文獻(xiàn)

[1]KENNEDY J,EBERHART R. Particle Swarm Optimization[C]//Proceeding of IEEE International Conference on Neural Networks.Perth:[s.n.],1995:1942.

[2]李寧,雛丹. 基于粒子群的多目標(biāo)優(yōu)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005(23): 43.

[3]COELLO C C A, PULIDO G T, LECHUGA M S. Handling Multiple Objectives with Particle Swarm Optimization[J]. IEEE Trans on Evolutionary Computation, 2004, 8(3): 256.

[4]凌海風(fēng),周獻(xiàn)中. 改進(jìn)的約束多目標(biāo)粒子群算法[J]. 計(jì)算機(jī)應(yīng)用, 2012, 32(5): 1320.

[5]邢小紅,羅軍剛. 基于改進(jìn)多目標(biāo)粒子群算法的水庫(kù)防洪調(diào)度[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012, 48(30): 33.

[6]肖樂(lè),吳相林. 自適應(yīng)混沌粒子群優(yōu)化的糧食應(yīng)急點(diǎn)選址研究[J]. 河南工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012, 33(4): 77.

[7]崔遜學(xué). 多目標(biāo)進(jìn)化算法及其應(yīng)用[M].北京:國(guó)防工業(yè)出版社,2006:279.

[8]王維博,林川. 粒子群算法中參數(shù)的實(shí)驗(yàn)與分析[J].西華大學(xué)學(xué)報(bào)(自然科學(xué)版), 2008,27(1):76.

[9]張其亮,陳永生,韓斌,等. 改進(jìn)的粒子群算法求解置換流水車間調(diào)度問(wèn)題[J].計(jì)算機(jī)應(yīng)用,2012,32(4):1022.

[10]劉淳安. 帶Levy變異的約束優(yōu)化PSO算法[J].西華大學(xué)學(xué)報(bào)(自然科學(xué)版),2008,27(2):72.

[12]SHI Y, EBERHART R C. AModified Particle Swarm Optimizer[C]// The 1998 IEEE International Conference on Evolutionary Computation Proceedings .IEEE World Congress on Computational Intelligence. Piscataway: IEEE Press, 1998: 69.

(編校：葉超)

A New Multi-objective Particle Swarm Algorithm with a Niche Technology and Elite Set Policies

LI Yanli, HUANG Tianmin, LIU Yaya

(InstituteofMathematics,SouthwestJiaotongUniversity,Chengdu610031China)

Abstract:In order to improve the effectiveness and efficiency of the multi-objective particle swarm optimization (pso) algorithm, by using niche technology to solve the fitness, this paper puts forward a new kind of multi-objective particle swarm optimization (PSO) algorithm with a niche technology and elite set strategy. the fitness was solved with niche technology and the roulette method was utilized to select global best position with the fitness of each particle of elite set .The adjustment in the process of algorithm running was made in this paper and the small probability variation method was also used. Finally, the test function was adopted to verify the effectiveness of the algorithm. The results show that the algorithm running time is 2.113 s, multi-objective optimization ratio on particle swarm algorithm(4.147s) was reduced by neraly half, and that the operation efficiency of the algorithm is greatly improved. The simulation results also show that the algorithm has better convergence and the solution has better uniformity.

Keywords:multi-objective optimization; niche technology; small probability variation; PSO; elite set

doi:10.3969/j.issn.1673-159X.2016.01.015

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1673-159X(2016)01-0073-04

基金項(xiàng)目：中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(swjtu11zt29)。

收稿日期：2014-09-09

第一作者：李艷麗(1988—),女,碩士研究生，主要研究方向?yàn)閮?yōu)化與決策-多目標(biāo)優(yōu)化。

·計(jì)算機(jī)軟件理論、技術(shù)與應(yīng)用·