一種新型的自適應(yīng)小生境遺傳算法解決多值NP組合問(wèn)題

1、一種新型的自適應(yīng)小生境遺傳算法解決多值NP組合問(wèn)題前言傳統(tǒng)的遺傳算法通常只能一個(gè)最優(yōu)解，但在許多解優(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)解。這就需要尋解能力超強(qiáng)的遺傳算法，一次尋找多個(gè)最優(yōu)解以供參考。因此本文以求最大值為例提出一種新型的自適應(yīng)的小生境遺傳算法，試圖提高對(duì)多峰函數(shù)的尋優(yōu)能力，尋找盡可能多的解，經(jīng)實(shí)驗(yàn)效果比較明顯。為了尋找盡可能多的解，我們需要算法盡可能的搜遍整個(gè)解空間，為此可以讓個(gè)體比較均勻的分散在整個(gè)解空間中，并且盡可能不重

2、復(fù)的遍歷整個(gè)解空間。算法描述算法基本思想算法思想簡(jiǎn)介通常隨機(jī)生成的初始群體，并不一定保證均勻覆蓋整個(gè)解空間（如圖一）。因此我們必須通過(guò)一定的措施使初始群體更加均勻的散滿整個(gè)解空間，形成均勻群體，然后每隔一定距離選擇其中適應(yīng)值較優(yōu)的個(gè)體作為候選的小生境核（如圖二）。最后借用小生境遺傳算法的思想一次選擇一定數(shù)目的候選小生境核，并保證群體中的個(gè)體都集中在這些小生境內(nèi)，在每一個(gè)小生境核周圍進(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è)

3、最優(yōu)解或該小生境與某個(gè)已求解距離很近或搜索時(shí)間超過(guò)一定代數(shù)后，算法停止對(duì)當(dāng)前小生境的搜索，轉(zhuǎn)而搜索候選核中沒(méi)有搜索過(guò)的其他小生境，周而復(fù)始一直搜索遍歷完所有候選小生境核。圖一初始群體圖二均勻群體圖三在每個(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ò)程中記下多樣性

4、最好的幾代群體，最后在這些多樣性好的群體中選擇合適的候選小生境核，并放到預(yù)備小生境核隊(duì)列中。第二階段主要在一定量的小生境核內(nèi)進(jìn)行進(jìn)化，根據(jù)進(jìn)化程度和適應(yīng)值調(diào)整交叉變異策略，并且隨著迭代代數(shù)的增加不斷減小小生境半徑。整個(gè)算法流程如下圖：第一階段第二階段圖五 SHAPE * MERGEFORMAT 算法第一階段描述選擇算子為了實(shí)現(xiàn)群體均勻分布于解空間，我們根據(jù)每個(gè)個(gè)體的距離密度進(jìn)行選擇，而不是根據(jù)適應(yīng)值進(jìn)行選擇。距離密度越大選擇概率越高，反之越低。設(shè)N是群體規(guī)模，dij表示個(gè)體i和j的距離。在文獻(xiàn)1中，距離密度定義為個(gè)體i和其余N-1個(gè)個(gè)體距離之和，即：，并聲稱一個(gè)個(gè)體距離密度越小，說(shuō)明其周圍個(gè)體

5、越集中；密度越大越分散。筆者認(rèn)為此種定義和斷言有待改進(jìn)，例如，在圖六中對(duì)個(gè)體0求距離密度，從圖中可以看到這樣一個(gè)事實(shí)：C比A集中，B比C分散。按照文獻(xiàn)1的計(jì)算方法：，A比C集中，C比B分散，這與事實(shí)不符。因此文獻(xiàn)1的定義方法需要改進(jìn)，在此給出兩種衡量距離密集程度的方法。圖 六Ad01=0.5d02=0.5d03=0.5Bd01=0.1d02=0.6d03=0.6Cd01=0.1d02=0.1d03=1.5定義1 在規(guī)模為N的群體中，任意個(gè)體i與其余N-1個(gè)個(gè)體距離的倒數(shù)之和稱為個(gè)體i的距離密度，記作Di，用公式表示為： eq oac(,1)Di值越大個(gè)體i周圍越密集，反之越分散。該方法強(qiáng)調(diào)了與

6、個(gè)體i距離特別近的那些個(gè)體，如果個(gè)體j與個(gè)體i特別近它對(duì)i的距離密度影響越大。但此種方法也有缺陷，如圖七，按這種定義A中D0=21，B中D0=22， B應(yīng)當(dāng)密集些，但事實(shí)上群體B更分散些。造成這種現(xiàn)象的原因是式 eq oac(,1)用到的函數(shù)在變化過(guò)快，dij有細(xì)微的擾動(dòng)Di就變化很大，在中變化較慢，反而抹殺了dij的差別。另一方面群體中可能出現(xiàn)個(gè)體i,j相同分母為0的情況。AB圖七Ad01=0.1d02=0.1d03=1.0Bd01=0.05d02=1.00d03=1.00考慮到個(gè)體j距i越近對(duì)距離密度影響越大，越遠(yuǎn)影響越小，把這些影響力量化并把所有個(gè)體的影響力累加起來(lái)可以作為距離密度的衡量

7、。為了量化這種影響力，可以把它表示成一個(gè)關(guān)于距離的遞減的函數(shù)，如果先考慮線性遞減函數(shù)，則有如下定義：定義2 在規(guī)模為N的群體中，設(shè)，為個(gè)體間最大距離，對(duì)任意個(gè)體i的距離密度為：。交叉變異策略借用文獻(xiàn)2的自適應(yīng)交叉變異的思想，這里交叉變異也用了自適應(yīng)方法，讓密集個(gè)體進(jìn)行較多的交叉變異以分散開(kāi)來(lái)，個(gè)體越分散交叉變異的概率越小，用下式確定交叉變異概率：，其中其中表示群體的平均距離密度，讓距離密度高于平均距離密度的個(gè)體以較高的固定概率進(jìn)行交叉變異；低于平均距離密度的個(gè)體交叉變異的概率隨著Di的減小而線性遞減。替換數(shù)目的確定隨著迭代的進(jìn)行，多樣性不斷提高，群體越來(lái)越均勻，改進(jìn)的余地會(huì)越來(lái)越小，因?yàn)楫?dāng)群體

8、比較均勻時(shí)仍大幅度的進(jìn)行交叉變異，反而破壞了群體的均勻性。因此替換數(shù)目應(yīng)隨迭代代數(shù)不斷減少，用下式計(jì)算：，其中；是最大替換數(shù)目；是最小替換數(shù)目，通常取2；t是迭代代數(shù)。算法第二階段描述進(jìn)化趨勢(shì)的量化進(jìn)化趨勢(shì)即群體最近進(jìn)化的方向，用來(lái)衡量群體進(jìn)化的優(yōu)劣程度，用它可以反饋調(diào)節(jié)進(jìn)化策略。文獻(xiàn)3用適應(yīng)值變化率來(lái)表征，交叉變異策略首先確定整個(gè)群體的交叉變異概率的范圍，所有個(gè)體的均限于此范圍內(nèi)。小生境半徑的確定試驗(yàn)討論理論分析參考文獻(xiàn)：蔡良偉基于距離測(cè)度的實(shí)數(shù)編碼自適應(yīng)遺傳退火算法深圳大學(xué)學(xué)報(bào)理工版，2004，Vol21，No4Srinivas，and Patnaik，daptive probabilities of crossover and m