一種新的自適應(yīng)小生境遺傳算法在多峰NP組合問(wèn)題中研究與應(yīng)用摘要：為了求解多峰優(yōu)化問(wèn)題，本文將遺傳算法分成了兩個(gè)階段。第一個(gè)階段，把個(gè)體不重復(fù)的均勻的散布在整個(gè)解空間內(nèi)，不僅提高多樣性，而且把所有可能的峰值點(diǎn)搜集起來(lái)。第二階段，借用小生境遺傳算法的思想，在每一個(gè)候選峰值點(diǎn)附近進(jìn)行局部求精搜索，一直到所有候選峰值點(diǎn)搜索完。用這種方法可以比較細(xì)密的搜遍整個(gè)可行解域，對(duì)求多峰函數(shù)比較適合，起到密網(wǎng)捕魚(yú)一個(gè)不漏的效果，并用N皇后問(wèn)題進(jìn)行驗(yàn)證收到較好的效果。關(guān)鍵字：遺傳算法、小生境、自適應(yīng)、距離密度、進(jìn)化趨勢(shì)、N皇后前言許多優(yōu)化問(wèn)題中都有多個(gè)全局最優(yōu)解和多個(gè)局部最優(yōu)解，我們更多的是要把所有的全局最優(yōu)解和局部最優(yōu)解全部找出，然后決策人員結(jié)合生產(chǎn)生活的實(shí)際情況，權(quán)衡各方利弊，在所有的最優(yōu)或較優(yōu)解中選出適合的某幾個(gè)最優(yōu)解，這類(lèi)問(wèn)題常稱為多峰搜索問(wèn)題或多模態(tài)函數(shù)優(yōu)化問(wèn)題，見(jiàn)文獻(xiàn)［1］。這就需要尋解能力較強(qiáng)的遺傳算法，一次尋找多個(gè)最優(yōu)解以供參考選擇，但傳統(tǒng)的遺傳算法通常只能求一個(gè)最優(yōu)解難以滿足要求，見(jiàn)文獻(xiàn)⑵和［3］。目前研究遺傳算法求多峰優(yōu)化問(wèn)題主要集中在數(shù)值問(wèn)題上，例如文獻(xiàn)［1］提出用協(xié)同多群體并結(jié)合小生境的思想取得較好的效果，雖然該文也提出了解決多峰組合問(wèn)題的思路，但是不僅需要求適應(yīng)值與海明距離的函數(shù)關(guān)系，而且需要對(duì)其進(jìn)行平滑，相當(dāng)繁瑣。其他的遺傳算法解決多峰的組合問(wèn)題還是鳳毛麟角。與數(shù)值問(wèn)題相比組合問(wèn)題具有離散性強(qiáng)，差異性大，不規(guī)則等特點(diǎn)，而且很多組合問(wèn)題是NP難的，用通常的方法求解非常困難，因此有必要專(zhuān)門(mén)研究討論該問(wèn)題。本文以求最大值為例提出一種改進(jìn)的自適應(yīng)的小生境遺傳算法，試圖提高對(duì)多峰組合問(wèn)題的尋優(yōu)能力，尋找盡可能多的解，經(jīng)實(shí)驗(yàn)效果比較明顯。為了尋找盡可能多的解，我們需要算法盡可能的搜遍整個(gè)解空間，為此可以讓個(gè)體比較均勻的分散在整個(gè)解空間中，并且盡可能不重復(fù)的遍歷整個(gè)解空間。算法描述算法基本思想算法思想簡(jiǎn)介通常隨機(jī)生成的初始群體，并不一定保證均勻覆蓋整個(gè)解空間（如圖一）。因此我們必須通過(guò)一定的措施使初始群體更加均勻的散滿整個(gè)解空間，形成均勻群體，然后每隔一定距離選擇其中適應(yīng)值較優(yōu)的個(gè)體作為候選的小生境核（如圖二）。最后借用小生境遺傳算法的思想一次選擇一定數(shù)目的候選小生境核，并保證群體中的個(gè)體都集中在這些小生境內(nèi)，在每一個(gè)小生境核周?chē)M(jìn)行局部的細(xì)致搜索（如圖三）。如果在某一個(gè)小生境內(nèi)找到一個(gè)比當(dāng)前核更優(yōu)的個(gè)體，則可假設(shè)這個(gè)更優(yōu)個(gè)體附近更接近全局最優(yōu)解，因此以這個(gè)更優(yōu)個(gè)體為新核，對(duì)這個(gè)小生境的搜索就遷移到新核附近（如圖四）。當(dāng)在某個(gè)小生境內(nèi)找到一個(gè)最優(yōu)解或該小生境與某個(gè)已求解距離很近或搜索時(shí)間超過(guò)一定代數(shù)后，算法停止對(duì)當(dāng)前小生境的搜索，

轉(zhuǎn)而搜索候選核中沒(méi)有搜索過(guò)的其他小生境，周而復(fù)始一直搜索遍歷完所有候選小生境核。圖一初始群體圖二均勻群體圖三 圖四在每個(gè)小生境內(nèi)搜索 小生境向更優(yōu)解遷移圖一初始群體圖二均勻群體圖三 圖四在每個(gè)小生境內(nèi)搜索 小生境向更優(yōu)解遷移算法基本流程該算法分為兩個(gè)階段，第一階段主要是讓初始群體盡可能的均勻化；第二階段主要是借用小生境遺傳算法的方法，在每一個(gè)小生境范圍內(nèi)搜索。第一階段首先計(jì)算群體中兩兩個(gè)體的距離和每個(gè)個(gè)體的距離密度，選擇距離密度比較大的若干對(duì)個(gè)體，每一對(duì)個(gè)體按照距離密度進(jìn)行交叉變異，然后用子個(gè)體替換父?jìng)€(gè)體，這個(gè)過(guò)程一直重復(fù)到連續(xù)幾代群體的多樣性不再增加為止，在這個(gè)過(guò)程中記下多樣性最好的幾代群體，最后在這些多樣性好的群體中選擇合適的候選小生境核，并放到預(yù)備小生境核隊(duì)列中。第二階段主要在一定量的小生境核內(nèi)進(jìn)行進(jìn)化，根據(jù)進(jìn)化程度和適應(yīng)值來(lái)調(diào)整交叉變異策略，并且隨著迭代代數(shù)的增加不斷減小小生境半徑。整個(gè)算法流程如下圖：

第一階段 第二階段圖五算法第一階段描述選擇算子為了實(shí)現(xiàn)群體均勻分布于解空間，我們根據(jù)每個(gè)個(gè)體的距離密度進(jìn)行選擇，而不是根據(jù)適應(yīng)值進(jìn)行選擇。距離密度越大選擇概率越高，反之越低。設(shè)N是群體規(guī)模，％表示個(gè)體i和j的距離。在文獻(xiàn)［4］中，距離密度定義為個(gè)體i和其余N-1個(gè)個(gè)體距離之和，即：

D=Nd=Il月（ximXjm）2，并聲稱一個(gè)個(gè)體距離密度越小，說(shuō)明其周?chē)鷤€(gè)j=1,j-i'j=1,j-im=1體越集中；密度越大越分散。筆者認(rèn)為此種定義和斷言有待改進(jìn)，例如，在圖六中對(duì)個(gè)體）求距離密度，從圖中可以看到這樣一個(gè)事實(shí)：C比A集中，B比C分散。按照文獻(xiàn)［4］的計(jì)算方法：D=1.5<D=1.7;Db=1.3<D=1.7，A比。集中，C比B分散，這與事實(shí)不符。因此文獻(xiàn)［4］的定義方法需要改進(jìn)，在此給出兩種衡量距離密集程度的方法。實(shí)不符。因此文獻(xiàn)［4］的定義方法需要改進(jìn)，在此給出兩種衡量距離密集程度的方法。ABC"=0.5d0i=0.1d01=0.1d/0.5d02=0.6d02=0.1d03=0.5d03=0.6d03=1.5圖六定義1在規(guī)模為N的群體中，任意個(gè)體i與其余N-1個(gè)個(gè)體距離的倒數(shù)之和稱為個(gè)體i的距離密度，記作R，用公式表示為：D=EdjT，j-iijR值越大個(gè)體i周?chē)矫芗?，反之越分散。該方法?qiáng)調(diào)了與個(gè)體i距離特別近的那些個(gè)體，如果個(gè)體j與個(gè)體i特別近它對(duì)i的距離密度影響越大。但此種方法也有缺陷，如圖七，按這種定義A中D0=21，B中D0=22，B應(yīng)當(dāng)密集些，但事實(shí)上群體B更分散些。造成這種現(xiàn)象的原因是式Q用到的函數(shù)V=j在（0,1］變化過(guò)快，扁有細(xì)微的擾動(dòng)Di就變化很大，在1,+8）中變化較慢，反而抹殺了扁的差別。另一方面群體中可能出現(xiàn)個(gè)體i,j相同分母為0的情況。3*2* 3*1+2*3*2* 3*1+2*1*LI*0*AB圖七考慮到個(gè)體j距i越近對(duì)距離密度影響越大，ABd=0.1d=0.050101d=0.1d=1.000202d=1.0d=1.000303越遠(yuǎn)影響越小，把這些影響力量化并把所有個(gè)體的影響力累加起來(lái)可以作為距離密度的衡量。為了量化這種影響力，可以把它表示成一個(gè)關(guān)于距離的遞減的函數(shù)，如果先考慮線性遞減函數(shù)，則有如下定義:定義2在規(guī)模為N的群體中，設(shè)Em>￡皿>0，dm為個(gè)體間最大距離，對(duì)任意個(gè)體i

\Md+\Md+EM7iJ=1,J&I交叉變異策略這里交叉變異也用了自適應(yīng)方法，讓密集借用文獻(xiàn)［5］和［6］的自適應(yīng)交叉變異的思想這里交叉變異也用了自適應(yīng)方法，讓密集個(gè)體進(jìn)行較多的交叉變異以分散開(kāi)來(lái)，個(gè)體越分散交叉變異的概率越小，用下式確定交叉變異概率：D<Di avg，D>Di avgk+k—k)￡iD<Di avg，D>Di avgkavg nub其中D表示群體的平均距離密度，讓距離密度高于平均距離密度的個(gè)體以較高的固定概其中D表示群體的平均距離密度，讓距離密度高于平均距離密度的個(gè)體以較高的固定概率k進(jìn)行交叉變異；低于平均距離密度的個(gè)體交叉變異的概率隨著Di的減小而線性遞減。2替換數(shù)目的確定隨著迭代的進(jìn)行，多樣性不斷提高，群體越來(lái)越均勻，改進(jìn)的余地會(huì)越來(lái)越小，因?yàn)楫?dāng)群體比較均勻時(shí)仍大幅度的進(jìn)行交叉變異，反而破壞了群體的均勻性。因此替換數(shù)目應(yīng)隨迭代代數(shù)不斷減少，用下式計(jì)算：rc(t)=max(kt+rc,rc)，其中k<0；rc是最maxmin max大替換數(shù)目；rc.是最小替換數(shù)目，通常取2；t是迭代代數(shù)；rc(t)第t代的替換數(shù)目。算法第二階段描述1.進(jìn)化趨勢(shì)的量化進(jìn)化趨勢(shì)即群體最近進(jìn)化的方向，用來(lái)衡量群體進(jìn)化的優(yōu)劣程度，用它可以反饋調(diào)節(jié)進(jìn)化策略。文獻(xiàn)［7］用適應(yīng)值變化率k化策略。文獻(xiàn)［7］用適應(yīng)值變化率k=f(t)-f(t-10)

f(—10)來(lái)衡量，該思路雖有定依據(jù)但刻畫(huà)得也不夠精確，例如圖八中，若用上式變化率的計(jì)算方法，t=10與t=12的變化趨勢(shì)一樣的，但事實(shí)上t=10時(shí)進(jìn)化，t=12是退化。要想用上式變化率檢測(cè)到t=11后是退化必須等到t=21后才行，顯得滯后和不精確。造成這種現(xiàn)象的原因是只考慮了兩端t=0，t=10的變化，沒(méi)有考慮中間的適應(yīng)值變化。f(0)=af(10)=b,,,■11111111111111111.,f⑵=a(12)斗02 1012圖八由于進(jìn)化趨勢(shì)與最近幾代的適應(yīng)值增減有關(guān)，而且與當(dāng)前代越接近關(guān)系越密切衡量越準(zhǔn)確，因此可用E°)=EwG*G)描述進(jìn)化程度。其中sG)表示第i和i-1相鄰兩代的進(jìn)化；w(i)i=t-c

描述第i代進(jìn)化的權(quán)重系數(shù)，i與t越接近權(quán)重w(i)越大；EQ刻畫(huà)了從t-。代到第t代c「+1展)」0-1連續(xù)c代的進(jìn)化趨勢(shì)，E「+1展)」0-1七一W(i-t)f(i)-f(i七一W(i-t)-0<f(i)-f(i-1)<0；wO=W+

f(i)-f(i-1)<-0 MW,W分別為最大最小權(quán)重系數(shù)。另外也可簡(jiǎn)單的取:Mm80=f(i)-f(i-1)，wG)=i+1-(t-c)。2,交叉變異策略首先確定整個(gè)群體的交叉變異概率的范圍，所有個(gè)體的概率均限于此范圍內(nèi)。通常群體的平均適應(yīng)值較低時(shí)，說(shuō)明進(jìn)化還不成熟，應(yīng)加快進(jìn)化速度;平均適應(yīng)值較高時(shí)，說(shuō)明比較接近最優(yōu)解，應(yīng)該進(jìn)行局部求精，減少交叉變異的概率。另一方面，當(dāng)最近進(jìn)化緩慢時(shí)，應(yīng)加大概率促進(jìn)進(jìn)化；當(dāng)進(jìn)化過(guò)快時(shí)，應(yīng)適當(dāng)?shù)囊种七M(jìn)化速度防止早熟。因此我們確定的交叉變異的浮動(dòng)范圍為平均適應(yīng)值f和進(jìn)化趨勢(shì)EG)的函數(shù)：Pf,E(t)=p+axfL-PxEQ，avgPf，E應(yīng)p+axfL-PxE(t)” avg其中，p、p分別是固定的最大最小概率；系數(shù)以不僅要把!調(diào)節(jié)到［0，1］內(nèi)，而avg且確定了適應(yīng)值對(duì)概率浮動(dòng)的影響；系數(shù)P用來(lái)調(diào)節(jié)進(jìn)化趨勢(shì)EG)的對(duì)概率的作用效果。C然后對(duì)群體中每個(gè)個(gè)體，適應(yīng)值大的實(shí)行小概率進(jìn)化，以保持優(yōu)良基因；適應(yīng)值小的實(shí)行大的概率進(jìn)化，加快尋優(yōu)步伐。依此原則每個(gè)個(gè)體根據(jù)各自的適應(yīng)值在群體概率范圍內(nèi)確定自己的概率。如果用線性關(guān)系則有下面方法:Lr定自己的概率。如果用線性關(guān)系則有下面方法:Lrpf，e(t立pf，e譏—M——avg f f_m——avg c \ minmax Jf-f )+pf，EQ。imaxmavgc其中，f,f,f 分別是群體的最小、平均、最大適應(yīng)值。minavgmax小生境半徑的確定在對(duì)每個(gè)小生境搜索時(shí)，隨著迭代代數(shù)的增加，應(yīng)越來(lái)越趨向局部求精。因此某個(gè)小生境半徑隨著該小生境的迭代代數(shù)的增加而不斷減小，但為了保證能遍歷完解空間每一個(gè)區(qū)域，小生境半徑應(yīng)該有個(gè)下限R通常取0.6倍個(gè)體間的平均距離。成）=maXRm-k*t,Rm），其中Rm是最大的小生境半徑，k是小生境半徑減少的步長(zhǎng)。試驗(yàn)討論理論分析參考文獻(xiàn)：李民強(qiáng)，寇紀(jì)淞，林丹，李書(shū)全.遺傳算法的基本理論與應(yīng)用.科學(xué)出版社CampbellPJ.Reviews:Geneticalgorthmsinsearch,optimizationandmachinelearningbyDavidE.Goldberg[J].MathematicsMagazine,1989,62(3):206-207RudolphG.Convergenceanalysisofcanonicalgeneticalgorithms[J].IEEETransactionsonNeuralNetworks,1994,5(1):96?101.蔡良偉.基于距離測(cè)度的實(shí)數(shù)編碼自適應(yīng)遺傳退火算法.深圳大學(xué)學(xué)報(bào)理工版，200