改進(jìn)的小生境粒子群優(yōu)化算法

李娜??黃治國

摘要：傳統(tǒng)的小生境粒子群優(yōu)化算法（NPSO）需要兩個(gè)參數(shù)的輸入，一個(gè)是判斷子群合并的閾值，另一個(gè)是子群產(chǎn)生的閾值。參數(shù)設(shè)置的不當(dāng)，將直接影響計(jì)算結(jié)果。引入一個(gè)函數(shù)判斷兩個(gè)點(diǎn)是否在同一座山峰上，以克服NPSO算法需要輸入?yún)?shù)的弊端。在程序運(yùn)行時(shí)，無須嚴(yán)格限定小生境的半徑，也不需太多的先驗(yàn)知識(shí)。實(shí)驗(yàn)結(jié)果證明，該算法合理有效，能夠能快速有效地找到多峰函數(shù)的全局最優(yōu)點(diǎn)。

關(guān)鍵詞關(guān)鍵詞：小生境；NPSO算法；粒子群優(yōu)化算法；多峰值函數(shù)

DOIDOI：10.11907/rjdk.143736

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

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)文章編號(hào)：16727800（2015）002004503

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

作者簡介作者簡介：李娜（1981-），女，河南商丘人，博士，中南民族大學(xué)計(jì)算機(jī)科學(xué)學(xué)院講師，研究方向?yàn)橹悄苡?jì)算。

1小生境PSO算法

小生境（Niche）是來自于生物學(xué)的一個(gè)概念，是指特定環(huán)境下的一種生存環(huán)境。生物在其進(jìn)化過程中，一般總是與自己相同的物種生活在一起，共同繁衍后代，這些生物賴以生存的環(huán)境資源，稱為小生境。人們把這種思想提煉出來，運(yùn)用到優(yōu)化算法中來。優(yōu)化算法實(shí)現(xiàn)小生境的方法最早由Cavicchio 于1970 年提出，該方法叫做基于預(yù)選機(jī)制的小生境方法＼[1＼]；1975年DeJong提出了基于排擠機(jī)制的小生境實(shí)現(xiàn)方法＼[2＼]；Goldberg 在1987 年提出了基于共享機(jī)制的小生境實(shí)現(xiàn)方法＼[3＼]。隨著研究的深入，越來越多的小生境實(shí)現(xiàn)方法被提出，小生境在優(yōu)化算法中的應(yīng)用也越來越廣泛。文獻(xiàn)＼[4＼]提出了小生境粒子群優(yōu)化算法。在標(biāo)準(zhǔn)PSO算法中，種群中的粒子會(huì)不斷向當(dāng)前最優(yōu)位置靠攏，算法迅速收斂，但同時(shí)種群的多樣性也快速下降。在NPSO算法中，若某個(gè)粒子在連續(xù)幾代的進(jìn)化過程中，適應(yīng)度值只有很細(xì)微的變化，那么該粒子和它的鄰居將就會(huì)形成一個(gè)小生境粒子群，該粒子是這個(gè)小生境粒子群的中心。具體算法如下：

Step1：初始化主粒子群，并設(shè)置小生境的參數(shù)。

Step2：主粒子群中的粒子進(jìn)行速度、位置和適應(yīng)度值的更新。

Step3：對(duì)每個(gè)小生境粒子群中的粒子進(jìn)行速度、位置和適應(yīng)度值的更新。

Step4：根據(jù)小生境半徑的設(shè)置，查看是否有需要合并的小生境粒子群。

Step5：查看主群中是否有粒子進(jìn)入了小生境范圍，若有，則將該粒子吸收進(jìn)入小生境粒子群中。

Step6：搜索主群中是否有滿足產(chǎn)生新的小生境的條件的粒子，若有滿足條件的粒子，則建立以該粒子群為中心的新的小生境子粒子群。

Step7：返回至Step2，直到滿足算法終止條件。

NPSO算法實(shí)現(xiàn)過程中，需要輸入兩個(gè)參數(shù)μ和δ，μ是判斷子群是否合并的閾值，δ是判斷子群是否產(chǎn)生的閾值，算法的實(shí)現(xiàn)效果依賴于參數(shù)的設(shè)置。在文獻(xiàn)[5]中，小生境子粒子群的合并依賴于參數(shù)μ，如果該參數(shù)的選擇不合適，算法很容易將處在不同山峰上的兩個(gè)小生境子群合并，造成尋優(yōu)效率下降；在文獻(xiàn)[4]中，新的小生境子群的產(chǎn)生依賴于給定的參數(shù)δ，不同的參數(shù)其算法性能也不同，算法需要先驗(yàn)知識(shí)才能保持其穩(wěn)定性。

2改進(jìn)的小生境粒子群優(yōu)化算法

在NPSO進(jìn)化過程中，需要根據(jù)參數(shù)μ和δ的設(shè)定進(jìn)行。若有一種簡單的方法能夠判斷兩個(gè)粒子是否在同一個(gè)山峰上，此方法可以大大提高NPSO算法的收斂速度和收斂性能，也可以避免算法過于依賴參數(shù)設(shè)置。文獻(xiàn)[6]設(shè)計(jì)了一個(gè)hillvalley函數(shù)，能夠判別搜索空間的任意兩點(diǎn)是否在同一個(gè)山峰上。將此函數(shù)應(yīng)用到遺傳算法上可求解多峰值問題，本文將此函數(shù)與NPSO算法相結(jié)合，進(jìn)行多峰函數(shù)的求解。

設(shè)搜索空間的任意兩點(diǎn)e1和e2，hillvalley（e1，e2）為判斷e1和e2是否在同一山峰上的函數(shù)，若e1和e2不存在適應(yīng)度值同時(shí)小于e1和e2適應(yīng)度值的內(nèi)點(diǎn)，則e1和e2在同一個(gè)山峰上， hillvalley函數(shù)的返回值為0，否則hillvalley函數(shù)的返回值為非0值，則e1和e2不在同一個(gè)山峰上。e1和e2之間的內(nèi)點(diǎn)由抽樣向量samples確定：

iinterio=e1+（e2-e1）·samples[j]（1）

其中，j=1，…，L，L是抽樣向量samples的長度，本文中L 的取值為5。

一維hillvalley函數(shù)如圖1所示，圖中e1、e2之間的內(nèi)點(diǎn)i1、i2的適應(yīng)度值均大于e1和e2的適應(yīng)度值，不存在適應(yīng)度值小于該兩點(diǎn)的內(nèi)點(diǎn)，判定e1和e2在同一個(gè)山峰；圖中e3和e4之間的內(nèi)點(diǎn)i3、i4、i5、i3的適應(yīng)度值大于e3和e4的適應(yīng)度值，而i4、i5的適應(yīng)度值小于e3和e4的，故e3和e4不在同一座山峰上。將上述hillvalley函數(shù)應(yīng)用到NPSO算法中，解決NPSO算法依賴參數(shù)設(shè)置的弊端，新算法稱為改進(jìn)的小生境粒子群優(yōu)化算法（Improved Niche Particle Swarm Optimization，INPSO）。算法具體實(shí)現(xiàn)如下：

Step1：參數(shù)設(shè)置及主粒子群的初始化，主粒子群以認(rèn)知模型進(jìn)行更新。

Step2：判斷主粒子群中的每一個(gè)粒子xi是否為潛在的最優(yōu)解，如果是，則產(chǎn)生一個(gè)以xi為中心的小生境子粒子群。判斷最優(yōu)解時(shí)，設(shè)粒子xi的適應(yīng)度值變化為σi，在算法進(jìn)化過程中若在連續(xù)幾代（本算法中設(shè)置是5代）內(nèi)均滿足σi<δ （δ設(shè)定的一個(gè)很小的閾值），則產(chǎn)生新的小生境子群。

Step3：對(duì)每一個(gè)子群中的粒子進(jìn)行迭代。

Step4：對(duì)所有子群進(jìn)行合并操作，當(dāng)任意兩個(gè)子群的最優(yōu)粒在同一個(gè)山峰時(shí)，合并這兩個(gè)子群。假設(shè)子群Di（i≥1） 的最優(yōu)粒子xm，子群Dj（j≥1）的最優(yōu)粒子xn處于同一山峰時(shí)，即hillvalley（xm， xn）=0時(shí)，合并兩個(gè)子群。合并后的子群粒子數(shù)目變大，保留適應(yīng)度值較好的R個(gè)粒子，其余粒子移到主粒子群中。

Step5：對(duì)每個(gè)子群進(jìn)行吸收粒子的操作，主群中的粒子xm移動(dòng)到小生境的Di（i≥1）范圍內(nèi)，即對(duì)于任意xm∈Di 都有hillvalley（xm， xn）=0，且Di中的粒子數(shù)目小于R，則粒子xm被吸收到小生境子粒子Di中，若Di中的粒子數(shù)目等于R，用xm替換Di中適應(yīng)度值最小的粒子。

Step6：判斷是否滿足終止條件，若不滿足轉(zhuǎn)到Step2。

圖1hillvalley函數(shù)

3實(shí)驗(yàn)分析

為了驗(yàn)證INPSO算法的有效性，針對(duì)3個(gè)典型的多峰函數(shù)做了兩組實(shí)驗(yàn)，第一組實(shí)驗(yàn)測(cè)試算法能否搜索到多峰函數(shù)的所有山峰；第二組實(shí)驗(yàn)測(cè)試算法的精度。測(cè)試函數(shù)如下：

（1）f1（x）=xsin（10πx）+2.0，x∈（-1，2） 。該函數(shù)具有17的局部最大值，這些峰值大小不等，間隔相等，當(dāng)x=1.850 549時(shí)，函數(shù)有全局最大值[7]為3.850 274。

（2）f2（x）=∑5i=1icos[（i+1）x+i]，x∈（-10，10） 。

函數(shù)具有19個(gè)局部極大值，當(dāng)x=-7.083 5、-0.800 3、5.482 9時(shí)，函數(shù)有3個(gè)全局最大值：14.508 008。

（3）f3（x，y）=cos（x）2+sin（y）2，x∈（-5，5），y∈（-5，5） 。函數(shù)具有12個(gè)局部極大值2。

測(cè)試中的參數(shù)設(shè)置為：迭代次數(shù)50，慣性權(quán)重ω=0.729 ，學(xué)習(xí)因子c1=c2=1.49，實(shí)驗(yàn)結(jié)果為30次獨(dú)立實(shí)驗(yàn)的平均值。

第一組實(shí)驗(yàn)是為了驗(yàn)證新算法的有效性，函數(shù)f1和f2的初始種群規(guī)模為100，函數(shù)f3的初始種群規(guī)模為80。

圖2小生境子群最優(yōu)值

3個(gè)函數(shù)運(yùn)行的結(jié)果如圖2所示，其結(jié)果是30次運(yùn)行結(jié)果的平均值。圖中星星表示粒子，a、b、c圖是函數(shù)的圖形表示，d、e、f圖是小生境子群中最優(yōu)粒子在圖形中的位置。d圖是函數(shù)f1的運(yùn)行結(jié)果，基本上最優(yōu)的粒子都爬到了山峰的頂端。e是函數(shù)f2的運(yùn)行結(jié)果，所有的峰值都有粒子。f1和f2是的維度是一維，函數(shù)f3的維度設(shè)定為二維。f圖是函數(shù)f3的俯視效果圖，圖上的白色星星表示粒子。從圖形上可以看出粒子處在山峰的頂端位置，本算法能夠找到所有的峰值。因此，本算法對(duì)多元函數(shù)仍然適用。

第二組實(shí)驗(yàn)是為了驗(yàn)證新算法的有效性，將本文所得測(cè)試結(jié)果與NPSO算法＼[8＼]所得結(jié)果進(jìn)行對(duì)比分析。參數(shù)的設(shè)置和第一組實(shí)驗(yàn)中的參數(shù)設(shè)置基本相同，個(gè)別參數(shù)設(shè)置如表1所示。本文INPSO算法不需要設(shè)置參數(shù)，是否合并兩個(gè)子群由hillvalley判斷兩個(gè)子群中的最優(yōu)粒子是否在同一山峰上實(shí)現(xiàn)。兩種算法的實(shí)驗(yàn)對(duì)比結(jié)果如表2所示。

2上都得到了較好的結(jié)果，收斂率是100，而在二維函數(shù)運(yùn)行上INPSO算法每次都能搜索到函數(shù)的全部峰值，而NPSO算法只有26次找到全部峰值，收斂率87%。另外，INPSO算法搜索到每個(gè)峰值的平均位置偏差要比NPSO算法要小，說明本文提出的INPSO算法的精確度高于NPSO算法。

4結(jié)語

本文引入一個(gè)函數(shù)判斷兩個(gè)粒子是否在同一座山峰上，克服了NPSO算法需要輸入兩個(gè)參數(shù)的弊端。通過對(duì)3個(gè)典型函數(shù)的優(yōu)化實(shí)驗(yàn)可以看出，本文所提出的算法能夠找到多峰函數(shù)的所有峰值，并且在平均偏離度和收斂率上都優(yōu)于NPSO方法，是一種有潛力的優(yōu)化方法。改進(jìn)后的小生境粒子群算法有更強(qiáng)的全局搜索能力和更高的收斂速度，能夠高效地尋找到多個(gè)全局最優(yōu)值 是一種尋優(yōu)能力、效率和可靠性更高的優(yōu)化算法，其綜合性能比基本NPSO 算法有顯著提高。

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

＼[1＼]CAVICCHIO D J.Adaptive search using simulated evolution＼[D＼].Michigan，Arbor Illinois：University of Michigan， 1970.

＼[2＼]DeJong K A.An analysis of the behavior of a class of genetic adaptive systems＼[D＼]. Michigan： University of Michigan， 1975.

＼[3＼]GOLDBERG D E，RicharDson J J. Genetic algorithms with sharing for muhimodal function optimization＼[C＼].Proc of the 2rid International Conference on Genetic Algorithms，1987：2736.

＼[4＼]BRITS R， ENGELBRECHT A P， VAN DEN BERGH F.A niching particle swarm optimizer＼[C＼].Proc of the 4th AsiaPacific Conf On Simulated Evolution and learning，2002： 692696.

＼[5＼]王俊年，申群太，沈洪遠(yuǎn)，等.一種基于聚類的小生境微粒群算法＼[J＼].信息與控制，2005，35（6）：680684.

＼[6＼]R K URSEM.Multinational evolutionary algorithms＼[C＼].Washington：Proceedings of Congress of Evolutionary Computation，1999（3）：16331640.

＼[7＼]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)＼[M＼].西安：西安交通大學(xué)出版社，2002.

＼[8＼]S W.MAHFOUD.A comparison of parallel and sequential niching methods＼[C＼].California：Proceedings of the Sixth International Conference on Genetic Algorithms，1995：136143.

責(zé)任編輯（責(zé)任編輯：孫娟）