排擠小生態(tài)遺傳算法的改進方法

排擠小生態(tài)遺傳算法的改進方法

譚竹梅

(湖南理工學院機械與電氣工程系，湖南岳陽414000)

摘要：提出了基于搜索空間聚類分析的聚類排擠小生態(tài)遺傳算法．通過分析適應值曲面的拓撲結構和擴大相似個體的搜索范圍,聚類排擠可確定搜索空間的局部性，減少排擠的替換錯誤并抑制種群的遺傳漂移；通過結合確定性替換和概率替換策略,聚類排擠提高了并行局部爬山能力和并行子種群維持能力．對不同多峰問題的仿真優(yōu)化結果表明，聚類排擠小生態(tài)遺傳算法的有效峰數(shù)量、平均峰值比和全局最優(yōu)解比等綜合性能一致地優(yōu)于適應值共享、簡單確定性排擠和概率排擠等小生態(tài)遺傳算法．

關鍵字：遺傳算法；小生態(tài)；排擠；聚類分析

中圖分類號：TP301文獻標識碼：A

ImprovementofNichingGeneticAlgorithmsUsingCrowding

TANZhu-mei

(DepartmentofMechanicalandElectricalEngineering,HunanInstituteofScienceandTechnology,HunanYueyang414000,China)

AbstractAclassofnichinggeneticalgorithmsusingclusteringcrowdingisproposed.Byanalyzingtopologyoffitnesslandscapeandextendingthespaceforsearchingsimilarindividual,clusteringcrowdingcandeterminethelocalityofsearchspacemoreaccurately,thusdecreasingthereplacementerrorsofcrowdingandsuppressinggeneticdriftofthepopulation.Theintegrationofdeterministicandprobabilisticcrowdingincreasesthecapacityofbothparallellocalhill-climbingandmaintainingmultiplesubpopulations.Theexperimentalresultsoptimizingvariousmultimodalfunctionsshowthat,theperformancessuchasthenumberofeffectivepeaksmaintained,averagepeakratioandglobaloptimumratioofgeneticalgorithmsusingclusteringcrowdingareuniformlysuperiortothatofthegeneticalgorithmsusingfitnesssharing,simpledeterministiccrowdingandprobabilisticcrowding.

Keywordsgeneticalgorithm;niche;crowding;clusteringanalysis

收稿日期:2003-4-25;收修改稿日期:

基金項目：湖南省教育廳科學研究基金(2001C380,2002A052)資助項目.

1引言(Introduction)

小生態(tài)技術是抑制進化計算遺傳漂移現(xiàn)象的方法．在流行的小生態(tài)算法中，共享[1](SH:fitnesssharing)存在小生態(tài)半徑[2]參數(shù)化問題，且計算成本高.確定性排擠⑶(DC:deterministiccrowding)存在相似個體的判斷錯誤和替換錯誤，遺傳漂移的抑制能力較弱.雖然概率排擠[4](PC:probabilisticcrowding)引入了低適應值物種的恢復壓，但沒有解決替換錯誤問題.因此，DC和PC均不能真正克服遺傳漂移現(xiàn)象，難以滿足搜索復雜多峰問題的應用要求.

本文研究基于搜索空間聚類分析的排擠小生態(tài)技術(CC:clusteringcrowding),提出一套公平地評估小生態(tài)算法性能的測度準則，通過多峰問題仿真優(yōu)化實驗比較不同小生態(tài)遺傳算法的綜合性能.

2搜索空間的聚類分析(Clusteringanalysisofsearchspace)山谷函數(shù)可用來模糊地確定搜索空間中任意兩點是否屬于相同的峰.一維山谷函數(shù)的例子如圖1所示.圖中e1和e2之間存在其適應值同時小于e1和e2適應值的內(nèi)部點，二者屬于兩個不同的峰；e3和e4之間不存在適應值同時小于二者適應值的中間點，二者屬于相同的峰.由于e和e6之間的點的

56適應值或大于、小于二者的適應值，因此，應用山谷函數(shù)判斷兩點的峰所屬關系時，其準確性取決于內(nèi)部點的數(shù)量和位置.一般地，當適應值曲面具有較高的峰密度時，需要離散地選取多個點才能做出準確的判斷.

在CC算法中，內(nèi)部點的數(shù)量選為1.令e1和e2分別表示兩個端點的坐標值，那么連線上內(nèi)部點

i可按公式

i=ei+0.5(e2-勺)

計算，這樣選擇的內(nèi)部點已能滿足分析絕大多數(shù)測試函數(shù)曲面拓撲的準確性要求．對于高密度的多峰問題，雖然山谷函數(shù)不能百分之百地保證適應值曲面拓撲分析的準確性，但與根據(jù)距離確定相似個體的測度技術相比較，山谷函數(shù)顯著地減少了判斷錯誤，繼而可達到減少排擠替換錯誤的目的．

圖1山谷函數(shù)的采樣示意圖

Fig.1Samplingmapofhill-valleyfunction

3聚類排擠小生態(tài)遺傳算法(Nichinggeneticalgorithmsusingclusteringcrowding)

CC算法的偽代碼如下：

ALGORITHMCC

GeneraterandomlyapopulationPofsize“;

While(notfulfillstoppingcriterion)

A={1,2,...,“};B=(p;P'=0；

For(k=1;kW〃/2;k=k+1)

i=arandomintegerinsetA-B;B=BU{i};j=arandomintegerinsetA-B;B=BU{j};(C,C)=mutation?recombination(P,P);

ijij

P'=P'U(Ci,Cj);

For(i=1;iWy;i=i+1)

FindoutthenearestPjju[1,“]toP；;

AnalyzeifPi'andPjbelongtoanidenticalpeakbyhill-valleyfunction;

If(Pi'andPjbelongtoanidenticalclass

ij

andf(Pi')>f(Pj))

ij

P'replaceP;

ij

Elseif(K^f(P')/(f(P.')+f(P)))P'replaceP;

ij

Endofthealgorithm

其中，0表示空集，f>0表示目標問題的適應值函數(shù)，K表示[0,1]區(qū)間上均勻分布的隨機變量,每次引用都采樣一個新的隨機數(shù)．

CC算法首先隨機地生成規(guī)模為“的初始種群P，然后將全體個體隨機地(不放回采樣)配成〃/2對父代，所有配對的父代經(jīng)重組和變異操作后生成子代個體種群P'.對每個子代個體P.'|iu[1，“],

i

從父代種群P中找到與之距離最近的個體P}ju[1，“]，然后應用山谷函數(shù)分析P.'和P.是否屬于相同ij

的峰，如果二者屬于相同的峰且P.'的適應值大于

.

P.的適應值，P.'替換P,如果P.'和P.屬于不同j.j.j

的峰，P.'以與其適應值成正比的概率替換P,.j

性能準則(Performancecriterions)

在設計小生態(tài)進化算法時，不但需要考慮算法并行地搜索多個局部最優(yōu)解的能力，還需考慮所找到的局部最優(yōu)解和全局最優(yōu)解的質(zhì)量(精度).因此，使用下列指標來測度算法的綜合性能.

有效峰數(shù)量(NEC:numberofeffectivepeaksmaintained)當搜索空間中某個峰在種群中存在至少一個元素，且該元素的適應值至少達到該峰所對應的局部極值的80%時，這樣的峰稱為一個有效峰.種群維持的有效峰的數(shù)量表示算法搜索到的有效局部最優(yōu)解的個數(shù)，是對算法的并行搜索能力的測度.

平均峰值比APR:averagepeakratio)種群中每個有效峰存在一個適應值最大的元素，該元素稱為有效局部最優(yōu)解，種群中全體有效局部最優(yōu)解的適應值之和除以搜索空間中全體真實局部最優(yōu)解的適應值之和稱為平均峰值比，該指標是對種群中的多個有效局部最優(yōu)解的平均質(zhì)量的測度，理想值被規(guī)范化為1.

全局最優(yōu)解比GOR:globaloptimumratio)種群中適應值最大的有效局部最優(yōu)解稱為有效全局最優(yōu)解，有效全局最優(yōu)解的適應值與真實全局最優(yōu)解的適應值之比稱為全局最優(yōu)解比，該指標是對種群中的有效全局最優(yōu)解的質(zhì)量的測度，理想值被規(guī)范化為1.

優(yōu)化實驗(Optimizationexperiments)

5.1測試函數(shù)(Testfunctions)

為了測試和比較不同小生態(tài)算法的并行局部搜索能力和搜索速度(用NEC,APR和GOR等三個性能指標表示)，采用下列三個不同難度的常用多峰函數(shù)：

2(]2)(x—0?08)2()

fi(x)二e—(n)(7834)sin6￡(x0-75—0.05)丿

2hd2

h—

r2

2h(d一r)2

r2

0

r

fd<—

2

rif<d<r

2

其它

距離測度，采用均勻隨機變異和兩點交叉算子，變

異概率p=0.001,交叉概率p=1(這是DC,PC和mc

CC隱含的交叉概率)，其它運行參數(shù)如表1所示，其中，CC的函數(shù)評估次數(shù)已包含了山谷函數(shù)進行拓撲分析所需要的評估次數(shù).

表1測試算法對不同函數(shù)的非公共參數(shù)

Table1Uncommonparametersoftestalgorithms

0

,x1

,x29

i=0\j=0

fj5］的定義域為［0,1］,該函數(shù)有5個非均勻分布的不等高的峰，其局部極大點分別位于x=0.080,0.247,0.451,0.681和0.934,相應的極大值分別為1，0.948，0.770，0.503和0.250．

厶［6］稱為Bell函數(shù)，其中丫表示鈴鐺狀圓錐體底面的半徑，h表示高度，d表示點到圓錐體底面中心的距離．通過改變搜索空間中圓錐體的數(shù)量、中心位置、大小和高度，該函數(shù)可提供不同的優(yōu)化復雜度．在本文的優(yōu)化實驗中，30個圓錐體底面隨機地分布于定義域為xu［0,1］的二維空間中，每個圓錐體底面半徑和圓錐體高度分別為區(qū)間［0.02,0.1］和［0.1,1］上的隨機數(shù)?高度為1的最高圓錐體底面中心的坐標值為(0.76,0.61),在該點Bell函數(shù)取全局最大值1.

f^］的自變量為長度為30位的二進制字符串，該字符串被均勻地分割成5個長度均為6位的子串，f3的函數(shù)值定義成5個子函數(shù)u(x)的適應值之和.子函數(shù)u(x)的自變量為6位二進制子串中“1”的位數(shù)，u(x)分別在點x=0和x=6取全局最大值1,在點x=1和x=5取全局最小值0，在點x=2和x=4取近似為0.4的中間值，在點x=3取局部最大值0.640576.厶被故意地設計成欺騙性的有極多峰的函數(shù)，該函數(shù)共有5153632個局部極值［8］，其中有32個為全局最大值點，全局最大點的函數(shù)值等于5，其它局部極值點的函數(shù)值位于3.203到4.641之間.

5.2測試算法(Testalgorithms)

對四種不同的小生態(tài)遺傳算法進行測試，四種算法分別是:SH,DC,PC和CC小生態(tài)遺傳算法.SH采用適應值比例選擇和通用隨機采樣，共享函數(shù)值調(diào)節(jié)指數(shù)［6嗆=1.所有算法均采用表現(xiàn)型的歐幾里得

函數(shù)

種群規(guī)模

卩

編碼長度

l

小生態(tài)半徑

o(SH)

評估次數(shù)

E

30

30

0.1

10000

100

2x30

0.1

40000

100

30

0.2

50000

表2100次獨立運行的性能指標算術平均值

Table2Averagevaluesofperformancecriterionsfor100independentruns

函數(shù)

性能指標

NEC

APR

GOR

NEC

APR

GOR

NEC

APR

GOR

SH

DC

PC

CC

2.79

4.65

2.80

5.00

0.706

0.941

0.579

1.000

0.994

0.993

0.992

1.000

10.47

14.22

4.41

27.37

0.455

0.656

0.201

0.945

0.961

0.987

0.951

0.981

2.38

14.95

0.66

27.89

0.074

0.467

0.021

0.872

1.000

1.000

0.963

1.000

5.3測試結果(Testresults)

對每一個函數(shù)，四種算法各進行100次獨立的運行，每次運行完成表1設定的函數(shù)評估次數(shù).實驗結果用每次獨立運行終止時的NEC,APR和GOR表示，100次運行的算術平均值如表2所示.

CC在1?104次的函數(shù)評估時間內(nèi)均可靠地搜索到f］的5個局部最優(yōu)解，APR和GOR值近似地等于1的事實說明由CC搜索到的所有有效局部最優(yōu)解和有效全局最優(yōu)解的質(zhì)量接近真實的局部最優(yōu)解和全局最優(yōu)解.

CC在4.104次的函數(shù)評估時間內(nèi)平均地搜索到f2的30個局部最優(yōu)解中的27個，APR值已達到0.945，說明每個有效局部最優(yōu)解的質(zhì)量均接近真實

的局部最優(yōu)解.因此，CC形成和維持有效峰的能力顯著地優(yōu)于DC,SH和PC算法.雖然四種算法的GOR指標比較接近，這并不表示它們具有相近的全局最優(yōu)解搜索能力，這是因為計算GOR時并未判斷有效全局最優(yōu)解和真實全局最優(yōu)解是否屬于相同的峰，因此，有可能將某個具有最大適應值的有效局部最優(yōu)解錯誤地當成有效全局最優(yōu)解.分析100次運行終止時的種群分布可以發(fā)現(xiàn)，DC，SH和PC算法分別有6、0和33次未生成全局有效峰，因此不同程度地存在丟失真實全局最優(yōu)解的現(xiàn)象，但CC在100次運行中尚未發(fā)現(xiàn)一次類似的情況，因此，只有CC的GOR值才是全局最優(yōu)解質(zhì)量的真實反映.

Mahfoud[7]指出，無論采用多大的種群規(guī)模，在一百五十萬次函數(shù)評估時間內(nèi)，SH均不能找到f3的全部32個全局最優(yōu)解；Mahfoud采用種群規(guī)模為600的DC和并行爬山法的混合算法，平均花費1.01?105次函數(shù)評估找到了全部32個全局最優(yōu)解.Sareni[5]應用種群規(guī)模為100的清除過程，2.104次函數(shù)評估平均只找到了15個全局最優(yōu)解，在同樣的運行條件下，DC平均只找到了0.43個全局最優(yōu)解.如表2所示，CC在5?104次的函數(shù)評估時間內(nèi)平均地搜索到28個全局最優(yōu)解，其全局最優(yōu)解的形成和維持能力分別是DC，SH和PC的2~42倍.

觀察有效峰數(shù)量平均值的動態(tài)曲線（限于篇幅，圖略）還可發(fā)現(xiàn)，對于三個不同的優(yōu)化問題，只有CC的動態(tài)曲線表現(xiàn)出先單調(diào)上升，后穩(wěn)定的特征，其他三種算法的曲線或者在上升到一定階段后呈現(xiàn)出下降趨勢，或者呈現(xiàn)出明顯的波動。因此說明，只有CC能維持穩(wěn)定的平衡態(tài)。對于三個測試函數(shù)，在平衡狀態(tài)下，種群中所維持的有效峰數(shù)量分別為5，29.31和29.63（實際的局部最優(yōu)解和全局最優(yōu)解依次為5，30和32個），達到平衡態(tài)所需要的函數(shù)評估次數(shù)依次為44103，5.76?104和9.13J04.

結論（ConCusions）

CC通過擴大相似個體的搜索范圍和應用山谷函數(shù)分析適應值曲面拓撲結構來提高相似個體判斷的準確性，達到減少替換錯誤和抑制遺傳漂移的目的.實驗結果表明，CC能夠自適應地、高效地形成和維持穩(wěn)定的子種群，實現(xiàn)對搜索空間不同區(qū)域的并行搜索.

CC結構簡單，應用時無需任何附加控制參數(shù)，是低成本的隱式自適應小生態(tài)技術.對SH,DC,PC和CC的綜合性能進行測試和比較，結果表明，CC是最優(yōu)的小生態(tài)算法.

當然，由于適應制曲面的拓撲分析需要函數(shù)評估的開銷，與DC和PC相比較，在總的函數(shù)評估次數(shù)相同的前提下，CC用于優(yōu)化搜索的評估次數(shù)較少，所以并行局部爬山速度較低，尚需研究改進這一缺陷的并行局部搜索技術.

參考文獻(References)

GOLDBERGDE,RICHARDSONJ.Geneticalgorithmswithsharingformultimodalfunctionoptimization[A].Procofthe2ndIntConfonGeneticAlgorithms[C],Hillsdale,NJ:LawrenceErlbaum,1987:41-49.

JELASITYM,DOMBIT.GAS,aconceptonmodelingspeciesi