混合遺傳算法自適應(yīng)策略研究

陳雄峰，曾霞霞，徐 戈1,

(1.福建省信息處理與智能控制重點(diǎn)實(shí)驗(yàn)室(閩江學(xué)院)， 福建 福州 350108；2.閩江學(xué)院計(jì)算機(jī)與控制工程學(xué)院， 福建 福州 350108)

0 引言

混合遺傳算法因其結(jié)合了全局探索與局部搜索，可折中平衡二者的搜索能力，非常利于搜索復(fù)雜的解空間，能有效處理大規(guī)模NP難組合優(yōu)化問題[1]。然而，混合遺傳算法必須進(jìn)行大量的適應(yīng)值估算，且種群容易失去多樣性，影響進(jìn)化效率，所需的計(jì)算時(shí)間較長[1-2]。問題針對(duì)性設(shè)計(jì)和自適應(yīng)策略是改進(jìn)混合遺傳算法性能的兩個(gè)主要措施。它是利用問題領(lǐng)域先驗(yàn)知識(shí)增強(qiáng)算法的整體性能，然而人們對(duì)NP難問題內(nèi)部結(jié)構(gòu)的先驗(yàn)領(lǐng)域知識(shí)總是有限的，通過人工實(shí)驗(yàn)設(shè)置的參數(shù)往往無法使混合遺傳算法達(dá)到滿意的搜索效率，因此需要自適應(yīng)策略。自適應(yīng)策略利用搜索過程中獲得的信息，通過自適應(yīng)的機(jī)制和參數(shù)來控制算法的多個(gè)方面，如搜索強(qiáng)度、種群多樣性等，使得搜索過程可動(dòng)態(tài)適應(yīng)問題解空間的適應(yīng)值地貌特征，從而提高算法搜索效率。近十來年，自適應(yīng)策略逐漸成為了混合遺傳等啟發(fā)式算法研究的最新趨勢，其中參數(shù)和算子自適應(yīng)策略是具有很好前景的重要研究方向[3]。

自適應(yīng)策略主要包括局部搜索概率、局部搜索個(gè)體選擇與強(qiáng)度和模因(meme)選擇與搜索過程等方面[1-3]。局部搜索概率自適應(yīng)旨在更好地分配基于種群的全局探索與基于個(gè)體的局部搜索的計(jì)算時(shí)間。局部搜索個(gè)體選擇自適應(yīng)則可增強(qiáng)獲得高質(zhì)量問題解的整體效率[1,4]。許多相關(guān)研究證實(shí)了局部搜索強(qiáng)度對(duì)搜索過程的性能有重大影響，很大程度上決定了搜索過程所需的計(jì)算時(shí)間，其主要自適應(yīng)策略是將搜索強(qiáng)度與個(gè)體適應(yīng)值或某種爬山啟發(fā)式相關(guān)聯(lián)[1,5]。模因(meme)是指體現(xiàn)個(gè)體特性的含有多個(gè)基因的基因片段。許多不同問題的研究闡述了模因作為混合遺傳等啟發(fā)式算法處理問題時(shí)計(jì)算表示的基本信息單元，被用作搜索過程的指南、規(guī)則、策略和先驗(yàn)知識(shí)等，會(huì)有效提升算法的問題求解能力[1,5-7]。其主要的自適應(yīng)機(jī)制是基于超啟發(fā)式策略[1-2,7]，即首先依據(jù)問題領(lǐng)域知識(shí)采用針對(duì)性策略確定一個(gè)模因集，然后在搜索過程的某個(gè)時(shí)刻，依據(jù)當(dāng)前個(gè)體、搜索區(qū)域和模因的不同特點(diǎn)，自適應(yīng)地選擇不同形式的模因組合，最后應(yīng)用模因組合逐步進(jìn)行啟發(fā)式搜索操作，如模因中兩個(gè)符號(hào)交換位置、幾個(gè)符號(hào)重新排序等，每一步獲得的候選解采用不同的接受準(zhǔn)則。

本文將自適應(yīng)策略應(yīng)用于全局探索與局部搜索過程、局部搜索個(gè)體選擇與強(qiáng)度以及種群多樣性等方面，并提出了單個(gè)交叉模因構(gòu)造過程和候選解接受準(zhǔn)則的自適應(yīng)策略，使得混合遺傳算法搜索過程可動(dòng)態(tài)適應(yīng)問題解空間的適應(yīng)值地貌特征，協(xié)調(diào)分配全局探索和局部搜索的計(jì)算時(shí)間，提高搜索效率，在保證可獲得同樣高質(zhì)量解的前提下，大幅減少運(yùn)行時(shí)間。以超大規(guī)模集成電路(VLSI, very large scale integration)標(biāo)準(zhǔn)單元布局問題為測試實(shí)例，實(shí)驗(yàn)結(jié)果表明了這些自適應(yīng)策略的有效性。

1 自適應(yīng)策略

1.1 候選解搜索與接受

候選解的接受準(zhǔn)則包括“全部” “好于” “好于或等于” “指數(shù)蒙特卡洛(Exponential Monte Carlo)”等[7]。不同的接受準(zhǔn)則適用于不同特征的搜索區(qū)域。“全部”接受準(zhǔn)則利于擴(kuò)大搜索區(qū)域，但不能保證尋獲更好的候選解，應(yīng)與其他接受準(zhǔn)則結(jié)合使用。“好于”和“好于或等于”接受準(zhǔn)則尋找更好候選解的效率高，但僅在可行解總是連續(xù)的搜索區(qū)域才能體現(xiàn)其優(yōu)勢?！爸笖?shù)蒙特卡洛”接受準(zhǔn)則可以小概率接受不好的候選解，適用于可行解不總是連續(xù)的搜索區(qū)域[2,4-7]。

本文算法全局探索和局部搜索過程所使用的候選解自適應(yīng)接受策略包括以下兩個(gè)方面。

1.1.1 候選解搜索

應(yīng)用模因集逐步搜索，以 “當(dāng)前步及其之前所有逐步搜索的結(jié)果” 為候選解即“全部”接受準(zhǔn)則。如此可動(dòng)態(tài)自適應(yīng)解空間的適應(yīng)值地貌特征。

1.1.2 候選解接受

當(dāng)“解空間可行解不總是連續(xù)的”時(shí)，以“指數(shù)蒙特卡洛”準(zhǔn)則接受候選解為當(dāng)前解，否則以“好于”準(zhǔn)則接受候選解為當(dāng)前解。如此可自適應(yīng)解空間的可行解特征。

1.2 交叉全局探索

基于進(jìn)化視角，模因是體現(xiàn)個(gè)體特性的含有多個(gè)基因的基因片段。基于算法視角，模因是問題求解時(shí)用于表示特定領(lǐng)域知識(shí)的信息單元[2]。在混合遺傳等啟發(fā)式算法中將模因用作搜索過程操作對(duì)象的指南，將具有良好的啟發(fā)效果。模因選擇與構(gòu)造是針對(duì)性和自適應(yīng)策略的基礎(chǔ)之一[1,6]。為使得交叉探索過程動(dòng)態(tài)自適應(yīng)解空間的地貌特征，本文算法在針對(duì)性選擇基因的基礎(chǔ)上，讓單個(gè)模因的構(gòu)成動(dòng)態(tài)自適應(yīng)于其當(dāng)時(shí)所影響的基因集合，讓單個(gè)模因所包含基因的個(gè)數(shù)(下文稱為模因大小)動(dòng)態(tài)自適應(yīng)于其當(dāng)時(shí)所影響基因集合的變化情況和一個(gè)問題的基因總個(gè)數(shù)。交叉全局探索過程動(dòng)態(tài)自適應(yīng)策略包括以下3個(gè)方面。

1.2.1 單個(gè)模因大小

單個(gè)模因大小與問題基因總個(gè)數(shù)|的成比例關(guān)系。

1.2.2 單個(gè)模因構(gòu)造

在雙親交叉過程中動(dòng)態(tài)構(gòu)造模因，在雙親個(gè)體交叉時(shí)所能影響的范圍內(nèi)選擇其構(gòu)成基因。

1.2.3 交叉全局探索過程

第一階段為模因集組成，依據(jù)“1.單個(gè)模因大小”和“2.單個(gè)模因構(gòu)成”自適應(yīng)策略構(gòu)造交叉的單個(gè)模因，而后采用簡單隨機(jī)方法組成模因集，模因集大小可通過簡單實(shí)驗(yàn)確定；第二階段為候選解搜索與接受，即對(duì)第一階段已組成的模因集，雙親交叉時(shí)使用“1.1.2候選解搜索與接受”自適應(yīng)策略獲得當(dāng)前解。

1.3 局部搜索

局部搜索個(gè)體選擇與強(qiáng)度方面使用自適應(yīng)策略，可更好分配全局探索與局部搜索的計(jì)算時(shí)間。交替使用不同類型的局部搜索，適當(dāng)控制每一步局部搜索的鄰域范圍，都是利于跳出局部優(yōu)解區(qū)域的有效措施。本文算法交替使用單個(gè)基因局部搜索和染色體窗口局部搜索。局部搜索過程動(dòng)態(tài)自適應(yīng)策略包括以下4個(gè)方面。

1.3.1 個(gè)體選擇

問題解個(gè)體質(zhì)量越高，局部搜索尋獲高質(zhì)量候選解的可能性越大，計(jì)算時(shí)間的價(jià)值體現(xiàn)得越充分，因此局部搜索個(gè)體選擇范圍和搜索強(qiáng)度通常自適應(yīng)于體現(xiàn)個(gè)體質(zhì)量水平的適應(yīng)值[1]。對(duì)于超大規(guī)模問題，通常采用小規(guī)模種群(5～10個(gè))，局部搜索個(gè)體選擇自適應(yīng)策略可相對(duì)簡約。本文算法將局部搜索個(gè)體選擇范圍簡單地劃分為“沒有”、“當(dāng)前最好個(gè)體”和“全部個(gè)體”3種情況，而后與當(dāng)前最好個(gè)體的適應(yīng)值(記為fitness(sbest))動(dòng)態(tài)自適應(yīng)，具體為：1) 當(dāng)fitness(sbest)

1.3.2 單個(gè)模因選擇

遺傳算法中一條染色體編碼對(duì)應(yīng)一個(gè)問題解個(gè)體，染色色編碼上基因符號(hào)位置變化會(huì)直接或間接影響問題解個(gè)體質(zhì)量。讓一個(gè)基因所包含的符號(hào)在染色體編碼上聚攏，或?qū)θ旧w編碼上窗口(若干連續(xù)基因符號(hào))進(jìn)行最佳排列，以優(yōu)化問題解個(gè)體質(zhì)量為目的調(diào)整這些基因符號(hào)的位置，對(duì)局部搜索過程具有良好的啟發(fā)引導(dǎo)作用。同時(shí)考慮限制個(gè)體鄰域范圍的需要，本文算法將“染色體編碼上符號(hào)不連續(xù)單個(gè)基因”和“染色體編碼上4～5個(gè)連續(xù)符號(hào)窗口”作為局部搜索的一個(gè)模因。

1.3.3 局部搜索過程

第一階段，如上“1.3.1個(gè)體選擇”選擇局部搜索個(gè)體，如上“1.3.2單個(gè)模因選擇”選擇單個(gè)模因，隨機(jī)選擇多個(gè)模因組成模因集，模因集大小可通過簡單實(shí)驗(yàn)確定；第二階段為候選解搜索與接受，即對(duì)第一階段已組成的模因集，局部搜索時(shí)使用“1.1候選解搜索與接受”自適應(yīng)策略獲得當(dāng)前解。

1.3.4 局部搜索強(qiáng)度

分別使用兩種策略：1)自適應(yīng)于當(dāng)時(shí)獲得更好鄰域解個(gè)體的可能性，即重復(fù)進(jìn)行上述局部搜索，直到3次未能獲得更好的鄰域解個(gè)體。2)自適應(yīng)于當(dāng)前解個(gè)體si的適應(yīng)值fitness (si)大小。

1.4 種群多樣性保持

為了避免陷入不好的局部優(yōu)解區(qū)域，更恰當(dāng)?shù)靥鼍植績?yōu)解區(qū)域，在全局探索過程保持種群個(gè)體具有適當(dāng)?shù)亩鄻有允窃O(shè)計(jì)基于種群尋優(yōu)算法必須考慮的一個(gè)重要因素。多樣性的度量方法主要包括基于適應(yīng)值和基于距離兩種[1]。實(shí)驗(yàn)觀察，由于計(jì)算時(shí)間過長，基于距離的度量方法并不適用于大規(guī)模組合優(yōu)化問題。本文算法使用基于適應(yīng)值，以動(dòng)態(tài)替換種群個(gè)體作為保持種群多樣性的主要自適應(yīng)策略，具體描述為：當(dāng)所有“個(gè)體適應(yīng)值fitness(si)/ 當(dāng)前最好個(gè)體適應(yīng)值fitness(sbest)>99.5%”時(shí)，用新的初始個(gè)體替換除當(dāng)前最好個(gè)體之外的其他所有個(gè)體。

2 算法基本框架

使用自適應(yīng)策略的混合遺傳算法基本框架如算法1所述，其中：自適應(yīng)策略如上第1節(jié)所述，Np、PGS、PLS、PGENorWIN和“算法終止條件”的可通過簡單實(shí)驗(yàn)確定，具體設(shè)定值見“3、實(shí)驗(yàn)結(jié)果與分析”。

算法1:使用自適應(yīng)策略的混合遺傳算法基本框架

輸入:求解問題所需信息Problem(info).

輸出:近優(yōu)解s*.

begin

生成初始種群{s[0], s[1], …, s[Np-1]};

repeat

隨機(jī)生成0, 1, …, Np-1的一個(gè)排列φ;

for ( i = 0 to Np-1)

選擇雙親s[φi], s[φ( i + 1 ) % Np];

以概率PGS進(jìn)行自適應(yīng)“交叉全局搜索”，生成孩子個(gè)體sc，記為sc=Adaptive Crosser_GS(s[φ( i + 1 ) % Np], s[φi]);

以“好于”準(zhǔn)則接受s[φi]=sc或s[φi];

if(個(gè)體 s[φi]同時(shí)滿足局部搜索概率PLS和“個(gè)體選擇”自適應(yīng)策略)

以概率PGENorWIN交替進(jìn)行自適應(yīng)“局部搜索”，生成鄰域個(gè)體sn，記為sn=AdaptiveGen_LS (s[φi])或AdaptiveWin _LS (s[φi]);

以“候選解搜索與接受”自適應(yīng)策略接受s[φi]= sn或s[φi];

end if

end for

使用“種群多樣性保持”自適應(yīng)策略;

until 滿足“算法終止條件”;

輸出近優(yōu)解s*=種群中當(dāng)前最好個(gè)體;

end

3 實(shí)驗(yàn)結(jié)果與分析

算法以超大規(guī)模集成電路標(biāo)準(zhǔn)單元布局問題作為測試實(shí)例，其問題描述、解表示、優(yōu)化目標(biāo)如文[8]所述。算法優(yōu)化目標(biāo)是一個(gè)布局的半周長HPWL(Half-Perimeter WireLength)， HPWL越小表示其布局質(zhì)量越高[8-12]。陣列布局可行解總是連續(xù)的，非陣列布局可行解不總是連續(xù)的，二者分別使用標(biāo)準(zhǔn)測試電路實(shí)例Peko suite3[13]、 ISPD04 ibm[14]，ISPD04與Peko suite3規(guī)模完全相同。

算法基本框架中種群規(guī)模Np=5，交叉全局搜索概率PGS=0.6，局部搜索概率PLS=0.6，單個(gè)基因和染色體窗口交替局部搜索概率PGENorWIN=0.15，動(dòng)態(tài)替換種群個(gè)體的自適應(yīng)判斷條件為“所有fitness(si)/ fitness(sbest)>99.5%”，算法結(jié)束條件為“20 min(陣列布局)或40 min(非陣列布局)時(shí)間間隔HPWL進(jìn)化減小量小于0.01×106”。

3.1 自適應(yīng)策略整體有效性

所有測試電路實(shí)例均可獲得有效實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果為5次運(yùn)行算法獲得結(jié)果的平均值，限于篇幅僅列出不同規(guī)模代表電路實(shí)例的測試結(jié)果，如表1所列。其中，“運(yùn)行時(shí)間減少”是指獲得相同HPWL平均值情況下，與全部不用第1節(jié)所述主要自適應(yīng)策略而其他要素相同的算法相比的結(jié)果。全部不用第1節(jié)所述主要自適應(yīng)策略時(shí)，相應(yīng)替代方法為： 1)1.1小節(jié)所述接受準(zhǔn)則都使用“好于”；2)1.2小節(jié)所述單個(gè)模因固定為交叉前隨機(jī)選定的平均大小的線網(wǎng)即基因；3)1.3小節(jié)所述個(gè)體選擇策略保持不變，局部搜索強(qiáng)度分別固定為1次或6個(gè)窗口；4)1.4小節(jié)所述種群替換條件固定為“每隔3 000代”。測試結(jié)果表明，對(duì)可行解是否總是連續(xù)的解空間，算法所使用的自適應(yīng)策略都是有效的。

表1 自適應(yīng)策略整體有效性Tab.1 The overall effectiveness of the adaptive strategies

3.2 主要自適應(yīng)策略各自作用

為驗(yàn)證各個(gè)主要自適應(yīng)策略的有效性和作用大小，分別單獨(dú)不用第1節(jié)所述主要自適應(yīng)策略，下文分別簡稱不用“接受”、 不用“模因”、 不用“強(qiáng)度”、不用“替換”，與此同時(shí)其他自適應(yīng)策略、參數(shù)保持不變，執(zhí)行算法直到獲得與表1“本文算法HPWL”相同的布局結(jié)果。選用不同規(guī)模代表電路實(shí)例Peko/ibm01、05、10、15、18進(jìn)行測試，相應(yīng)運(yùn)行時(shí)間減少程度的計(jì)算方法與表1“運(yùn)行時(shí)間減少”相同，簡稱相應(yīng)“運(yùn)行時(shí)間減少”。測試結(jié)果如表2所列，其中“⊿RRT”是相應(yīng)“運(yùn)行時(shí)間減少”與表1“運(yùn)行時(shí)間減少”之間的差距，即“⊿RRT”=(表1“運(yùn)行時(shí)間減少”)-(相應(yīng)“運(yùn)行時(shí)間減少”)，“⊿RRT”大小體現(xiàn)了相應(yīng)自適應(yīng)策略作用的大小。因?yàn)椴挥谩敖邮堋钡奶娲椒ㄅc對(duì)陣列布局的接受準(zhǔn)則相同，此時(shí)“⊿RRT”為0，所以表2的“陣列”部分沒有列舉不用“接受”的情況。

測試結(jié)果表明，候選解接受自適應(yīng)策略僅對(duì)可行解不總是連續(xù)的解空間有作用；對(duì)可行解是否總是連續(xù)的解空間，單個(gè)模因構(gòu)造自適應(yīng)策略都有較大作用；對(duì)可行解總是連續(xù)的解空間，局部搜索強(qiáng)度和種群多樣性保持自適應(yīng)策略的作用相對(duì)更大。

表2 主要自適應(yīng)策略各自作用Tab.2 The respective effect of the major adaptive strategies

4 結(jié)語

針對(duì)性設(shè)計(jì)使得混合遺傳算法可處理超大規(guī)模組合優(yōu)化問題，在此基礎(chǔ)上使用適應(yīng)性策略可大幅減少運(yùn)行時(shí)間，是提高混合遺傳算法整體性能的有效途徑。實(shí)驗(yàn)結(jié)果證實(shí)了本文提出和采用自適應(yīng)策略的有效性，其中，本文提出的交叉全局探索單個(gè)模因構(gòu)造和候選解接受自適應(yīng)策略具有顯著的作用，采用的局部搜索個(gè)體選擇與強(qiáng)度自適應(yīng)策略也具有重要作用。后續(xù)研究的重點(diǎn)將是交叉全局探索和局部搜索的自適應(yīng)交互策略，進(jìn)一步協(xié)調(diào)全局探索和局部搜索的能力，從而進(jìn)一步提高算法的整體性能。