基于種群熵的多粒子群協(xié)同優(yōu)化

(1.華中科技大學(xué) 控制科學(xué)與工程系， 武漢 430074; 2.中國(guó)地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院， 武漢 430074)



摘 要：

提出了一種基于種群熵的多粒子群協(xié)同優(yōu)化算法，通過引入熵對(duì)種群粒子的分布性進(jìn)行度量，然后利用它來引導(dǎo)在多種群協(xié)同演化中粒子遷徙的時(shí)間和方向，從而保持粒子在尋優(yōu)過程中的多樣性和快速性。通過四個(gè)典型測(cè)試函數(shù)的仿真說明了該算法具有擺脫局部極值能力和較高的收斂速度。

 關(guān)鍵詞：種群熵； 粒子群優(yōu)化； 協(xié)同

 中圖分類號(hào)：TP3016 文獻(xiàn)標(biāo)志碼： A

文章編號(hào)：10013695(2008)12359303



Coevolutionary particle swarm optimization based on population entropy

HU Chengyu1，2， WU Xiangning2， WANG Yongji1



(1.Dept. of Control Science Engineering， Huazhong UniversityofScience Technology， Wuhan430074， China;

2. School of Computer， China University of Geosciences， Wuhan 430074， China)



Abstract:

This paper applied a modified CPSO based on population entropyin the context of ECPSO. The entropy was used to measure the diversity of the whole population and then guided the particles how to migrate. The ECPSO was tested on some benchmark optimization problems and the results show a superior performance compared with the standard PSO and CPSO.

 Key words：population entropy; particle swarm optimization(PSO); coevolutionary



粒子群優(yōu)化(PSO)算法作為一種新的優(yōu)化算法，由于收斂速度快、參數(shù)設(shè)置少，近年來受到眾多學(xué)者的重視^[1，2]。它常被用于解決大量非線性、不光滑和多峰值的復(fù)雜問題優(yōu)化，現(xiàn)已廣泛應(yīng)用于許多科學(xué)和工程領(lǐng)域。但是，人們?cè)趯?shí)際應(yīng)用中發(fā)現(xiàn)，對(duì)某些多峰、平坦函數(shù)優(yōu)化問題，PSO在進(jìn)化過程中種群多樣性損失過快，容易導(dǎo)致其陷入局部極值，引起算法過早收斂。針對(duì)這一問題，很多學(xué)者提出了改進(jìn)的方法，如增加粒子的多樣性、引入進(jìn)化選擇機(jī)制^[3，4]以及引入空間鄰域^[5]等。

另外，由于微粒群算法是基于同種群體內(nèi)信息共享的假設(shè)而提出的，它反映了在一個(gè)種群中個(gè)體之間的合作關(guān)系。在自然界的生態(tài)系統(tǒng)中，很多物種通過與其他物種相互作用來提高自己的生存能力。受此啟發(fā)，Shi等人^[6]提出了一種基于兩個(gè)種群協(xié)同進(jìn)化求解極大極小值的算法。Asmara等人在此算法的基礎(chǔ)上又提出了一種改進(jìn)算法 ACPSO（accelerated coevolutionary PSO），提高了算法的收斂速度并將此算法應(yīng)用到機(jī)器手臂計(jì)算機(jī)扭矩控制中。ElAbol等人^[7]指出了兩個(gè)相互合作的微粒群之間如何進(jìn)行信息交換。在國(guó)內(nèi)，很多學(xué)者也對(duì)協(xié)同進(jìn)化微粒群算法進(jìn)行了研究。Niu等人^[8]提出了多群體合作微粒群算法，并將其用在了為動(dòng)態(tài)系統(tǒng)構(gòu)建模糊模式上。李愛國(guó)^[9]提出了一種兩層結(jié)構(gòu)的多粒子群協(xié)同優(yōu)化算法。王俊年等人^[10，11]提出了將多種群協(xié)同進(jìn)化微粒群算法應(yīng)用到神經(jīng)網(wǎng)絡(luò)自適應(yīng)噪聲消除系統(tǒng)和徑向基神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)中。以上改進(jìn)算法都存在一些問題，即在多種群中粒子的遷移機(jī)制上主要依靠經(jīng)驗(yàn)。

雖然協(xié)同微粒群進(jìn)化算法在一定程度上得到了發(fā)展，但是在多種群協(xié)同的機(jī)制上有待于改善，特別是在多種群合作協(xié)同的過程中，粒子通過何種方式遷移才能保持種群的多樣性和收斂的快速性，還需要進(jìn)一步的研究。本文利用群熵的概念對(duì)粒子多樣性進(jìn)行量化，從而在時(shí)間和方法上對(duì)多種群協(xié)同中的信息流動(dòng)進(jìn)行引導(dǎo)，不僅保持了種群的多樣性、還保持種群了收斂速度。

1 標(biāo)準(zhǔn)粒子群優(yōu)化算法

Shi等人^[12]在研究基本粒子群算法收斂性的過程中，發(fā)現(xiàn)在速度項(xiàng)加上一個(gè)權(quán)重ω，對(duì)整個(gè)算法非常重要。于是在1998年的IEEE國(guó)際進(jìn)化計(jì)算學(xué)術(shù)會(huì)議上發(fā)表了的論文，首次在速度進(jìn)化方程中引入慣性權(quán)重，即

以上公式常被認(rèn)為是粒子群算法標(biāo)準(zhǔn)版本。式中，ω稱為慣性權(quán)重，它使微粒保持運(yùn)動(dòng)慣性，使其有擴(kuò)展搜索空間的趨勢(shì)，有能力探索新的區(qū)域。引入慣性權(quán)重ω可清除基本PSO算法對(duì)Vmax的需要，因?yàn)楠鬲旧砭哂芯S護(hù)全局和局部搜索能力的平衡作用。這樣，當(dāng)Vmax增加時(shí)，可通過減小ω來達(dá)到平衡搜索，而ω的減小可使得所需的迭代次數(shù)變小。因此，可以將Vmax固定，只對(duì)ω進(jìn)行調(diào)節(jié)。通常的做法是:采用自適應(yīng)調(diào)整ω的策略，即隨著迭代的進(jìn)行，而線性減小ω的值。使得算法在迭代初期探索能力較強(qiáng)，可以不斷搜索新的區(qū)域；然后開發(fā)能力逐漸增強(qiáng)，使算法在可能最優(yōu)解周圍精細(xì)搜索。也有學(xué)者提出了一種用模糊規(guī)則動(dòng)態(tài)調(diào)整ω的方法^[13]。

2 基于群熵的多粒子群協(xié)同優(yōu)化算法

21 群熵的定義

定義在一種群所有適應(yīng)值構(gòu)成的集合R中，存在真子集 A1，A2，…，An，若A1∪A2∪…∪An=R，A1∩A2∩…∩An=， 集合A1，A2，…，An中

由定義可知，當(dāng)種群中所有粒子的適應(yīng)值都相同時(shí)，熵取最小值E=0；當(dāng)種群中粒子的適應(yīng)值分布越大，則粒子在解空間越具有多樣性和勘探能力。在多種群協(xié)同的過程中，可以通過種群的熵度量種群中各粒子的分布狀況，從而決定需要遷移的粒子及其轉(zhuǎn)移方向。

22 多粒子群協(xié)同

在生物界中不僅存在達(dá)爾文的“適者生存，優(yōu)勝劣汰”的自然進(jìn)化規(guī)律，同時(shí)還存在著多個(gè)個(gè)體或多個(gè)物種通過相互之間的合作而共同進(jìn)化的自然規(guī)律。多粒子協(xié)同進(jìn)化算法正是源于這種思想。在遺傳算法中，個(gè)體之間僅存在著競(jìng)爭(zhēng)關(guān)系，通過個(gè)體之間的競(jìng)爭(zhēng)而淘汰差的個(gè)體，保留優(yōu)秀個(gè)體，從而使得解群體不斷逼近最優(yōu)解。在協(xié)同進(jìn)化算法中，個(gè)體之間不僅存在競(jìng)爭(zhēng)關(guān)系，同時(shí)也存在相互合作、相互促進(jìn)的關(guān)系，各個(gè)子群體之間通過適應(yīng)度的關(guān)聯(lián)而共同進(jìn)化。

多種群的協(xié)同方式分為競(jìng)爭(zhēng)型協(xié)同進(jìn)化和合作型協(xié)同進(jìn)化，在本文中采用后者。合作型協(xié)同進(jìn)化是指某個(gè)群體中個(gè)體的與其他群體中個(gè)體通過一系列的合作，并根據(jù)其對(duì)目標(biāo)問題解決的貢獻(xiàn)度來決定進(jìn)化方向。

利用合作型協(xié)同進(jìn)化求解問題時(shí)，一般通過適應(yīng)值共享實(shí)現(xiàn)，在粒子遷移機(jī)制上對(duì)粒子的選擇通常有如下幾種方式：a）選擇最好的個(gè)體。選取當(dāng)前各種群中的最好個(gè)體作為代表，但在有些情況下，這種策略顯得太貪婪。b）隨機(jī)選擇。從每個(gè)種群中隨機(jī)選取個(gè)體的代表。c）選擇平均個(gè)體。顯然，合作方式的選擇對(duì)于問題解向量的優(yōu)劣有很大的影響，以上這些方式較多地依賴于經(jīng)驗(yàn)和具體問題。

23 基于群熵的多粒子群協(xié)同函數(shù)優(yōu)化

在本文提出的ECPSO算法中，利用兩個(gè)種群進(jìn)行協(xié)同演化，而在選擇遷移的粒子及遷移的方向上，主要依據(jù)種群的熵進(jìn)行度量。主要策略是：熵值較大的種群中，適應(yīng)值較大一部分粒子向熵值較小的種群遷徙，隨機(jī)替換相同數(shù)目的粒子；而在熵值較小的種群中，最優(yōu)的粒子向熵值較大種群移動(dòng)，替換其最差粒子。 通過這種遷移策略，保證了種群始終能夠保持一定的多樣性，也保證了種群全體的快速性。算法流程如圖1所示。 

3 仿真及結(jié)果分析

31實(shí)驗(yàn)設(shè)計(jì) 

為了測(cè)試本文提出的基于種群熵的協(xié)同粒子群（ECPSO）算法，本文把本算法和協(xié)同粒子群算法（CPSO）及標(biāo)準(zhǔn)的粒子群算法（SPSO）相比較，實(shí)驗(yàn)選用四個(gè)常用于優(yōu)化算法比較的基準(zhǔn)函數(shù)。

四個(gè)優(yōu)化函數(shù)非常具有代表性：F1是一個(gè)球面函數(shù)，只有一個(gè)全局最優(yōu)解0，分布在（0，…，0）處；F2函數(shù)是二維Schaffer’s f6函數(shù)，全局最優(yōu)解為0，分布在(0，0)處，特點(diǎn)是全局極小值被一群局部極小值包圍，很難跳出局部極小值;F3是Rastrigrin典型函數(shù)，全局最優(yōu)解為0，分布在(0，0)處，它是一個(gè)典型的欺騙函數(shù)，其特點(diǎn)是在極小值附近，存在多個(gè)局部極大和極小，局部極大值和局部極小值如樹狀林立，很難跳出局部最優(yōu)；F4函數(shù)比較平坦，所以在尋找極小值的過程中，一般的算法收斂速度比較慢。圖2~4分別是函數(shù)

在本文中，標(biāo)準(zhǔn)版本SPSO算法、基于貪婪機(jī)制的協(xié)同粒子群算法（CPSO）、基于群熵的協(xié)同粒子群算法（ECPSO）具體參數(shù)設(shè)置為:種群粒子為30，進(jìn)化世代數(shù)為300，收斂的退出條件是精度達(dá)到0000 1或者達(dá)到進(jìn)化代數(shù)，c1=c2=2，ω=08，Vmax為函數(shù)邊界的01倍。最終對(duì)20次平均適應(yīng)值進(jìn)行評(píng)測(cè)，以及對(duì)尋到極值的成功率進(jìn)行統(tǒng)計(jì)。

32 種群熵值的計(jì)算

種群的熵值不能預(yù)知，針對(duì)不同的優(yōu)化函數(shù)及其邊界，在不同的優(yōu)化代數(shù)內(nèi)，種群的熵值是變化的，是一個(gè)逐步趨近于0的過程。因此，使用如下方法對(duì)種群的熵進(jìn)行估計(jì)：首先估計(jì)解空間S及劃分區(qū)域數(shù)M。解空間用[ζmin，ζmax]來度量，設(shè)算法運(yùn)行中迄今為止所發(fā)現(xiàn)的最小和最大適應(yīng)值分別為min和max，則通過ζmin=α×

對(duì)于函數(shù)F1，從圖5和表1可以看到，三種方法的尋優(yōu)性能相差不多，ECPSO稍微占優(yōu)，CPSO次之，SPSO最差，但是由于球面函數(shù)只有一個(gè)全局極值，沒有局部極值的干擾，三種方法都可以收斂到極值。

對(duì)于函數(shù)F2，CPSO和SPSO雖然在收斂速度上占有優(yōu)勢(shì)，但是很快收斂到局部極值。因?yàn)樵谌謽O值附近有無數(shù)局部極值環(huán)繞。實(shí)驗(yàn)表明，在20次尋優(yōu)過程中，收斂到最優(yōu)值的幾率為0。而ECPSO在收斂過程中，由于粒子是基于熵值互相移動(dòng)，適應(yīng)值略有波動(dòng)，最終能夠跳出局部極值，找到最優(yōu)解。雖然ECPSO不是每次都能收斂到全局極值，在20次尋優(yōu)中有7次可以跳出局部極值，找到最優(yōu)解，成功率達(dá)到35%。

對(duì)于函數(shù)F3，CPSO和SPSO相比，收斂速度略占優(yōu)勢(shì)，但是兩者都很快收斂到局部極值。因?yàn)樵谌謽O值附近有無數(shù)局部極值林立。實(shí)驗(yàn)表明，在20次尋優(yōu)過程中，收斂到最優(yōu)值的幾率也為0。而ECPSO在前期收斂速度稍慢，但是經(jīng)過平均66代演化，均可以收斂到全局極值，在20次收斂到全局的極值成功率為100%。

對(duì)于函數(shù)F4，由于函數(shù)過于平坦，三種算法在最優(yōu)極值的尋找都有困難，速度上相差也不多，說明此類平坦函數(shù)三種算法效果均不太好，還需要進(jìn)一步的改進(jìn)。

通過分析可以得知：CPSO的遷移機(jī)制是采用基于最優(yōu)值共享的方法，這種方式比較貪婪，使得種群收斂速度變快，而容易陷入局部最優(yōu)；而在ECPSO中，遷移之前首先計(jì)算每個(gè)種群的熵值，根據(jù)熵的大小進(jìn)行遷移，這樣不僅使得收斂的速度基本不變，而種群的多樣性可以保持。從計(jì)算復(fù)雜性的角度考慮，SPSO算法較為簡(jiǎn)單，而CPSO和ECPSO較為復(fù)雜，但是ECPSO與CPSO相比難易程度相差無幾，性能卻提高很多。

這里通過對(duì)函數(shù)F3在尋優(yōu)過程中兩個(gè)種群在協(xié)同時(shí)熵值的變化曲線（圖9）可以看出，兩個(gè)種群熵值開始都從3左右向05下降，并且在下降過程中，熵值交替變化，說明兩個(gè)種群通過粒子的遷移，種群的多樣性呈現(xiàn)交替變化，從而證明了算法的有效性。

4 結(jié)束語

本文采用種群的熵值對(duì)種群中粒子分布情況進(jìn)行量化，從而利用熵值引導(dǎo)兩個(gè)種群在協(xié)同過程中粒子的遷移時(shí)機(jī)和方向。用SPSO、CPSO和本文提出的ECPSO算法對(duì)四個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的優(yōu)化表明，ECPSO對(duì)大部分函數(shù)具有快速收斂性和跳出局部極值的能力，對(duì)于平坦的函數(shù)還需要研究新的遷移機(jī)制，才能保證收斂到全局極值，這也是本文后續(xù)的研究?jī)?nèi)容。

參考文獻(xiàn)：

[1]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. 1995.

[2] EBERHART R C， KENNEDY J. A new optimizer using particle swarm theory[C]//Proc of the 6th International Symposium on Micro Machine and Human Science. Nagoya: [s.n.]， 1995.

[3] ANGELINE P J. Using selection to improve particle swarm optimization[C]//Proc of IEEE International Conference on Evolutionary Computation. Anchorage:[s.n.]， 1998:8489.

[4]LOVBJERG M， RASMUSSEN T K， KRINK T. Hybrid particle swarmoptimizer with breeding and subpopulations[C]//Proc of the 3rd Genetic and Evolutionary Computation Conference. 2001.

[5] SUGANTHAN P N. Particle swarm optimizer with neighbourhood operator[C]//Proc of Congress on Evolutionary Computation. Piscataway， NJ:IEEE Service Center， 1999:19581962.

[6] SHI Y， KROHLING R. Coevolutionary particle swarm optimization to solving minmax problems[C]//Proc of IEEE Congress on Evolutionary Computation. Honolulu，Hawaii:[s.n.]， 2002:16821687.

[7] ELABD M， KAMEL M. Information exchange in multiple cooperating swarms[C]//Proc of Conference on Genetic and Evolutionary Computation. 2005:269270.

[8] NIU Ben， ZHU Yunlong， HE Xiaoxian. Multipopulation cooperative particle swarm optimization[C]//Proc of the 8th Conference on ECAL. 2005:874883.

[9] 李愛國(guó).多粒子群協(xié)同優(yōu)化算法[J].復(fù)旦學(xué)報(bào):自然科學(xué)版，2004， 43 (5):923925.

[10] 王俊年，申群太，沈洪遠(yuǎn)，等.基于多種群協(xié)同進(jìn)化微粒群算法的徑向基神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)[J].控制理論與應(yīng)用，2006， 23 (2):251255.

[11] 王俊年，申群太，沈洪遠(yuǎn)，等.基于協(xié)同進(jìn)化微粒群算法的神經(jīng)網(wǎng)絡(luò)自適應(yīng)噪聲消除系統(tǒng)[J].計(jì)算機(jī)工程與應(yīng)用，2005， 41 (13):2023.

[12] SHI Y， EBERHART R C. A modified particle swarm optimizer[C]//Proc of IEEE International Conference on Evolutionary Computation. Piscataway， NJ: IEEE Press， 1998:6973.

[13] SHI Y， EBERHART R C. Fuzzy adaptive particle swarm optimization[C]//Proc of IEEE Conference on Evolutionary Computation. 2001:101110.