潘家文，錢 謙+，伏云發(fā)，馮 勇

1.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500

2.昆明理工大學(xué) 云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明 650500

遺傳算法（genetic algorithm，GA）[1]是20 世紀(jì)70年代初期由美國Michigan 大學(xué)Holland 提出來的借鑒生物界自然選擇思想和自然遺傳機(jī)制的一種全局隨機(jī)搜索算法。它把問題的可能解看作個(gè)體，多個(gè)個(gè)體組成種群，算法運(yùn)行時(shí)按照一定的進(jìn)化策略使個(gè)體所代表的可能解不斷進(jìn)化，直到產(chǎn)生最優(yōu)或近似最優(yōu)解。該算法的優(yōu)越性主要表現(xiàn)在：（1）使用時(shí)所需領(lǐng)域知識(shí)少，且優(yōu)化過程不依賴于梯度信息，不要求目標(biāo)函數(shù)的連續(xù)或可導(dǎo)；（2）求解復(fù)雜函數(shù)時(shí)，只需要選擇、交叉、變異三種操作就能獲得最優(yōu)解；（3）能夠同時(shí)搜索多個(gè)點(diǎn)，具有較好的并行尋優(yōu)能力。目前GA 已廣泛應(yīng)用于機(jī)器學(xué)習(xí)、控制、優(yōu)化等領(lǐng)域[2-4]。

傳統(tǒng)遺傳算法（standard GA，SGA）存在著“早熟”收斂和收斂速度慢等缺陷。目前已經(jīng)提出了許多解決這一問題的方法，如引入并行機(jī)制[5]、學(xué)習(xí)機(jī)制[6]等，這些方法都取得了較好的效果。群體的多樣性不足會(huì)使種群的搜索范圍被限制，導(dǎo)致GA 易陷入“早熟”收斂，因此需要保證算法在計(jì)算過程中的種群多樣性不能過快喪失。目前對種群初始化的研究較少，已有的GA 研究多數(shù)采用隨機(jī)初始化方法產(chǎn)生種群，隨機(jī)初始化方法會(huì)產(chǎn)生多樣性差、染色體分布不均勻的種群[7]。文獻(xiàn)[8]提出半初始化方法，該方法雖然豐富了種群多樣性，但也增加了計(jì)算復(fù)雜度，還影響了種群的穩(wěn)定性。文獻(xiàn)[9]通過海明距離作為標(biāo)準(zhǔn)約束個(gè)體來產(chǎn)生初始種群，但該方法由于隨機(jī)樣本的影響仍會(huì)產(chǎn)生多樣性較差的種群。引入并行機(jī)制是提高遺傳算法性能的一個(gè)重要方向[10]，通過對不同種群配置不同的進(jìn)化策略能夠有效控制子種群的獨(dú)立演化特性，同時(shí)還通過種群間的個(gè)體遷移來保證子種群間的融合，以此提升了算法的性能。鄭明等[5]將改進(jìn)的多種群并行遺傳算法用于基因調(diào)控網(wǎng)絡(luò)的構(gòu)建。Zhou 等[11]將改進(jìn)的多種群并行遺傳算法用于列車組調(diào)度優(yōu)化問題。但是上述方法仍存在一些問題，算法中的單個(gè)種群采用了具有固定數(shù)值的Pc和Pm的進(jìn)化策略，在搜索空間的勘探和開采上出現(xiàn)了矛盾，無法有效地調(diào)整種群多樣性和收斂速度之間的平衡。如果Pc和Pm的數(shù)值過高，雖然有利于跳出局部最優(yōu)，增大找到全局最優(yōu)的可能性，但是會(huì)破壞現(xiàn)有的優(yōu)良個(gè)體，增加算法隨機(jī)性；如果Pc和Pm的數(shù)值過低，又不容易產(chǎn)生新的個(gè)體，容易導(dǎo)致進(jìn)化停滯不前。文獻(xiàn)[10]提出在多種群并行遺傳算法的進(jìn)化策略中采用自適應(yīng)調(diào)整的進(jìn)化參數(shù)，雖然在一定程度上改善了進(jìn)化效果，但本質(zhì)上仍然是在固定區(qū)間內(nèi)對Pc和Pm取值，自適應(yīng)能力有限。遺傳操作在計(jì)算過程中是完全隨機(jī)的，經(jīng)過遺傳操作進(jìn)化的新染色體可能更加優(yōu)秀或劣質(zhì)，導(dǎo)致GA 在尋優(yōu)過程中缺乏方向性。而且GA 不善于對局部區(qū)域進(jìn)行細(xì)致搜索，導(dǎo)致該算法的局部搜索能力較差。Hinton 等[12]率先引入學(xué)習(xí)機(jī)制來引導(dǎo)GA 算法的進(jìn)化方向，為個(gè)體提供更加優(yōu)良的進(jìn)化途徑。在此基礎(chǔ)上，不同的學(xué)習(xí)方法被引入GA以增強(qiáng)GA的性能。如單純形法[13]、模擬退火算法[14]等。上述方法能夠有效增強(qiáng)GA 的運(yùn)行效率和求解質(zhì)量，但增加了算法的計(jì)算復(fù)雜度。文獻(xiàn)[15]將聚類思想與模式定理結(jié)合提出一種新的學(xué)習(xí)機(jī)制來引導(dǎo)種群的進(jìn)化方向，該算法實(shí)際操作較為簡單，其運(yùn)行時(shí)間與SGA 近似為一種次線性的關(guān)系，即在不增加算法的基本運(yùn)算頻度的基礎(chǔ)上增強(qiáng)了算法的局部尋優(yōu)能力。但該算法采用線性的方式來控制學(xué)習(xí)機(jī)制的運(yùn)行，在算法中后期會(huì)出現(xiàn)學(xué)習(xí)機(jī)制失效的現(xiàn)象。

為設(shè)計(jì)一種更加高效的遺傳算法，本文在前人研究基礎(chǔ)上做出改進(jìn)，提出了最優(yōu)權(quán)動(dòng)態(tài)控制學(xué)習(xí)機(jī)制的多種群遺傳算法（multi-population genetic algorithm based on optimal weight dynamic control learning mechanism，OWLMGA）。具體方法如下：

（1）采用一種均勻分區(qū)多種群初始化方法，該方法在避免擴(kuò)大種群規(guī)模的基礎(chǔ)上，能夠產(chǎn)生多個(gè)種群較均勻分布在解空間的不同區(qū)域，保證了初始解的多樣性，避免算法結(jié)果因多樣性差陷入局部最優(yōu)。

（2）采用一種改進(jìn)的多種群并行機(jī)制，該機(jī)制首先對現(xiàn)有進(jìn)化策略做出改進(jìn)并提出一種新的保存策略，其次將不同種群分離承擔(dān)不同的進(jìn)化功能（詳見1.2.1小節(jié)），減弱了傳統(tǒng)并行機(jī)制在解空間勘探和開采的矛盾，使算法能夠有效地保持種群多樣性和收斂速度之間的平衡。

（3）采用了最優(yōu)權(quán)動(dòng)態(tài)控制的學(xué)習(xí)機(jī)制，該機(jī)制利用一種基于適應(yīng)度的評價(jià)函數(shù)衡量基因模式的優(yōu)劣程度，并能夠根據(jù)進(jìn)化中種群個(gè)體適應(yīng)度的不同情況自適應(yīng)調(diào)節(jié)基因模式的引導(dǎo)過程。

1 OWLMGA 基本思想

為改進(jìn)GA 易“早熟”收斂的缺點(diǎn)，提出均勻分區(qū)多種群初始化方法和改進(jìn)的多種群并行機(jī)制。為引導(dǎo)算法進(jìn)化方向及加強(qiáng)局部搜索能力，提出了動(dòng)態(tài)控制的學(xué)習(xí)機(jī)制，并將兩種機(jī)制結(jié)合起來，形成一種能充分發(fā)揮兩種機(jī)制優(yōu)勢的混合算法。

1.1 均勻分區(qū)多種群初始化方法

GA 從一組分布于解空間超平面的可能解開始尋優(yōu)，理論上，算法希望這些可能解均勻分布在解空間，此時(shí)種群多樣性較豐富，有助于算法擺脫“早熟”收斂，找到全局最優(yōu)值。實(shí)際上，由于隨機(jī)初始化方法的不確定性，會(huì)出現(xiàn)可能解聚集在解空間超平面局部一側(cè)的情況，這樣種群的多樣性就會(huì)比較差。文獻(xiàn)[10-11]所代表的多種群并行遺傳算法都采用了隨機(jī)初始化方法獨(dú)立產(chǎn)生多個(gè)種群，雖然多個(gè)種群的存在一定程度上緩解了可能解局部聚集的情況，但多樣性較差的可能性仍然存在。多樣性差的種群通過遺傳操作進(jìn)化時(shí)，往往會(huì)收斂到可能解附近的局部最優(yōu)值便停滯不前，若要打破這種不利局面，則需要數(shù)值比較大的Pc和Pm，但是，數(shù)值比較大的Pc和Pm在幫助種群探索全局最優(yōu)解的同時(shí)，會(huì)不斷破壞群體內(nèi)個(gè)體的優(yōu)良基因，使個(gè)體遲遲不能收斂到全局最優(yōu)解，最終影響算法的性能。

海明距離（兩條染色體間相同基因座上不同基因的數(shù)量）是衡量遺傳算法種群多樣性的傳統(tǒng)方法之一。與其他度量方法相比，海明距離方法的主要優(yōu)點(diǎn)是操作簡單，僅需比較個(gè)體所代表的字符串，而不需要與目標(biāo)函數(shù)相關(guān)的信息，不會(huì)增加計(jì)算復(fù)雜度。該方法的另一個(gè)優(yōu)點(diǎn)是比較的是個(gè)體基因型的差距，而不是個(gè)體表現(xiàn)型之間的差距，能夠更好地判斷個(gè)體基因之間的親屬關(guān)系。

聚類分析是模式識(shí)別中非監(jiān)督學(xué)習(xí)的一個(gè)重要的方法，聚類分析的目的是將若干實(shí)例按照“相似度”劃分為不同的集合，每個(gè)集合中的實(shí)例按照規(guī)定的度量來說“相似”，而不同集合之間的實(shí)例按相同的度量來說“不相似”。本文借鑒聚類劃分中常用的K-means 算法的基本思想提出一種均勻分區(qū)多種群初始化方法，首先選取海明距離作為實(shí)例（個(gè)體）之間的相似性度量，以最大海明距離為準(zhǔn)則劃分出不同集合（種群）的聚類中心點(diǎn)，然后每個(gè)聚類中心點(diǎn)將符合海明距離的實(shí)例收入集合中。均勻分區(qū)多種群初始化方法在解空間中聚類劃分的問題可以描述為：對于給定的個(gè)體樣本，按照最大海明距離劃分為M個(gè)種群，種群染色體數(shù)目N，令P代表i個(gè)個(gè)體樣本構(gòu)成的集合，H1,H2,…,HM代表M個(gè)劃分后的種群集合，則基本思想滿足：

均勻分區(qū)多種群初始化方法能夠使不同種群較均勻地分布在解空間的不同區(qū)域，每個(gè)種群隨機(jī)地將適當(dāng)距離的可能解放入種群中，該方法避免了隨機(jī)初始化方法導(dǎo)致可能解聚集在局部區(qū)域的情況。通過這樣的方式進(jìn)行種群初始化，可以在避免擴(kuò)大種群規(guī)?；A(chǔ)上保證種群多樣性，有助于算法跳出局部最優(yōu)值，尋找全局最優(yōu)值。

均勻分區(qū)多種群初始化方法流程如下：

（1）初始化種群參數(shù)：種群總數(shù)目M，每個(gè)種群的染色體數(shù)目N，種群集合H，種群計(jì)數(shù)變量m=0，Hm表示第m個(gè)種群，Rm表示m種群染色體數(shù)目。

（2）P={x1,x2,…,xi}，代表一個(gè)含有i個(gè)染色體的可能解集合，其中i的規(guī)模為M×N的5～10倍左右。

（3）從P中選擇第一個(gè)染色體x1放入種群Hm，m=m+1，x1→Hm，Hm→H。

（4）對于?xi∈P，且xi?H使得Distance(x1,xi)=max(Distance(x1,xi))，m=m+1，xi→Hm，Hm→H。

（5）若m＜M，轉(zhuǎn)（6），否則轉(zhuǎn)（7）。

（6）對 于?xt∈H，若?xk∈P，且xk?H，使 得Distance(xt,xk)=max(Distance(xt,xk))(t=1,2,…,m;k=1,2,…,i)，則m=m+1，xk→Hm，Hm→H。轉(zhuǎn)（5）。

（7）若存在Rm＜N，對于xk∈Hm，xk=Hm.head，Hm.head表示種群m的第一個(gè)染色體，對于?xi∈P，且xi?H，使得Distance(xk,xi)≤max(Distance(xk,xi))/M，則xi→Hm，Rm=Rm+1，轉(zhuǎn)（5），否則結(jié)束。

上述初始化方法可以使種群均勻分布于解空間的不同區(qū)域，但同時(shí)也考慮了種群分布的整體質(zhì)量，并不是盲目地追求均勻化。具體來說，由步驟（3）至步驟（6）可以看出，本文首先選出聚類中心點(diǎn)，該中心點(diǎn)與其選定的度量距離保證了種群分布的均勻度。由步驟（7）可以看出，任意個(gè)體與某個(gè)聚類中心點(diǎn)只要在選定的距離范圍內(nèi)就會(huì)被收入種群中，在種群所代表的集合之間的分布具有足夠均勻度的前提下，這種隨機(jī)收入個(gè)體的偏好隨機(jī)方式能夠較好地保證種群初始化后有足夠豐富的解空間信息，又在一定程度上避免了盲目的隨機(jī)性，有利于保持種群的整體質(zhì)量。

1.2 改進(jìn)的多種群并行機(jī)制

有效控制種群多樣性是搜索到全局最優(yōu)解的基本條件，單種群演化較難克服GA 收斂速度和種群多樣性之間的矛盾，算法易出現(xiàn)早熟收斂或頻繁在非有效區(qū)域進(jìn)行搜索導(dǎo)致搜索效率較低[16]。OWLMGA在文獻(xiàn)[17]所提出的進(jìn)化策略基礎(chǔ)上做出部分改進(jìn)并提出一種改進(jìn)的多種群并行機(jī)制，通過變換種群遺傳操作的參數(shù)及種群分離承擔(dān)不同的進(jìn)化功能而有效地控制種群獨(dú)立演化特性，保持種群多樣性和收斂速度之間的平衡，進(jìn)而提升算法的性能。

將數(shù)值較大的Pm和數(shù)值較小的Pc稱為探索策略（exploration strategy），并且在遺傳操作上選擇先進(jìn)行變異操作再進(jìn)行交叉操作，最后執(zhí)行選擇復(fù)制操作。該進(jìn)化策略有利于種群跳出局部最優(yōu)，探索新的解空間。將數(shù)值較小的Pm和數(shù)值較大的Pc稱為開發(fā)策略（development strategy），該策略首先執(zhí)行交叉操作再進(jìn)行變異操作，最后執(zhí)行選擇復(fù)制操作。該策略能夠重組現(xiàn)有基因產(chǎn)生新的個(gè)體以期待獲得更好的性狀改變，使種群在當(dāng)前解空間內(nèi)充分進(jìn)行探索。普通策略（normal strategy）采用介于開發(fā)策略和探索策略之間程度的Pc和Pm，在進(jìn)化操作上采用SGA 的選擇復(fù)制、交叉、變異操作，該策略兼具以上兩者的功能。此外，還有一種與前述策略不同的策略稱為保存策略（reorganization strategy），該策略不通過遺傳操作在解空間進(jìn)行尋優(yōu)，而是作為一個(gè)容器不斷接收其他種群通過數(shù)據(jù)共享傳遞過來的優(yōu)秀個(gè)體進(jìn)行處理，該策略能夠充分發(fā)掘其他種群優(yōu)秀個(gè)體的“進(jìn)化潛能”，并使優(yōu)秀基因能夠有效遺傳下去。

圖1 描繪了OWLMGA 多種群并行機(jī)制的執(zhí)行過程，首先算法初始化產(chǎn)生多個(gè)種群，算法開始時(shí)，種群復(fù)制自身并配置上述改進(jìn)的進(jìn)化策略。各種群獨(dú)立進(jìn)行演化，種群之間每代都進(jìn)行個(gè)體遷移，即將當(dāng)代自身的優(yōu)秀個(gè)體傳遞給保存策略子群。保存策略子群對傳遞過來的優(yōu)秀個(gè)體進(jìn)行交叉來重組基因產(chǎn)生新染色體，選擇最優(yōu)N個(gè)染色體作為新子群進(jìn)入下一代。每隔一定代數(shù)，各種群之間進(jìn)行信息遷移，即與公共區(qū)域共享基因模式和最優(yōu)個(gè)體（詳見1.3.1小節(jié)定義9），探索策略與開發(fā)策略互換種群，然后再各自進(jìn)化，如此反復(fù)，直到算法結(jié)束。

Fig.1 Processing structure of improved multi-population parallel mechanism圖1 改進(jìn)的多種群并行機(jī)制執(zhí)行過程

1.2.1 改進(jìn)的并行機(jī)制理論研究

模式定理（scheme theorem）與積木塊假設(shè)（building block hypothesis）是由Holland 提出的構(gòu)成GA 進(jìn)化動(dòng)力學(xué)的基本原理[18]，Holland 將種群中個(gè)體基因型相似樣板稱為遺傳模式，其中“低階、短距并高于種群平均適應(yīng)度的遺傳模式”被定義為積木塊。模式定理說明了積木塊有更大概率在進(jìn)化過程中被遺傳算子繼承并重新聯(lián)結(jié)成新的解，這個(gè)過程可以看作“搭積木”的過程[16]。GA 在遺傳算子的作用下不斷整合積木塊產(chǎn)生適應(yīng)度更高的個(gè)體，從而找到更優(yōu)的解，這就是Holland 提出的積木塊假設(shè)。以上兩種理論共同闡述了GA 尋求最優(yōu)解的可能性及能力，對遺傳算法的理論和實(shí)踐具有重要的引導(dǎo)意義。

Holland 早期的研究[18]指出，GA 中的遺傳操作對基因的重組作用主要包含兩方面：遺傳模式保存能力和遺傳模式重組能力。前者是指重新聯(lián)結(jié)已有的低階有效遺傳模式組成高階遺傳模式；后者是指打破已有的遺傳模式并對其中的基因位進(jìn)行重組產(chǎn)生新的低階有效遺傳模式。算法依靠著兩種能力不斷改進(jìn)現(xiàn)有解朝著最優(yōu)解的方向收斂，兩種能力互為矛盾，算法難以同時(shí)具備強(qiáng)力的遺傳模式保存能力和遺傳模式重組能力[18]。而本文利用并行機(jī)制中多種群獨(dú)立演化及優(yōu)秀個(gè)體遷移的特性，賦予不同種群不同的進(jìn)化功能（即模式重組和模式保存），進(jìn)而使算法從整體上看同時(shí)具備較強(qiáng)的遺傳模式重組能力和遺傳模式保存能力。一方面，多數(shù)種群使用互不相同的進(jìn)化策略進(jìn)行搜索，主要負(fù)責(zé)勘探新的有效基因并對其進(jìn)行重組產(chǎn)生新的低階有效遺傳模式。為了進(jìn)一步增強(qiáng)算法的遺傳模式重組能力，保持這些個(gè)體在解空間勘探與開采的有效平衡，本文首先對傳統(tǒng)進(jìn)化策略進(jìn)行改進(jìn)，當(dāng)種群多樣性低時(shí)，種群差異度小，種群包含的解空間信息不夠豐富，此時(shí)按照傳統(tǒng)遺傳算法先進(jìn)行選擇與交叉操作，產(chǎn)生新個(gè)體的可能性較小，之后進(jìn)行變異操作雖然能夠產(chǎn)生新的有效基因，但其個(gè)體表現(xiàn)型的適應(yīng)度普遍比較低，這些基因還沒通過交叉操作重組成新的低階有效遺傳模式就隨所在個(gè)體被執(zhí)行順序靠前的選擇操作所淘汰；當(dāng)種群多樣性高時(shí)，種群差異度大，種群包含足夠豐富的信息，此時(shí)按照傳統(tǒng)遺傳算法先進(jìn)行選擇、交叉操作，雖然有機(jī)會(huì)重組有效基因產(chǎn)生新的低階遺傳模式提升個(gè)體表現(xiàn)型的適應(yīng)度，但之后進(jìn)行變異操作很可能使新產(chǎn)生的低階遺傳模式被破壞，削弱了交叉算子的作用。針對這一情況，本文提出的進(jìn)化策略更符合種群進(jìn)化狀況，提高了搜索效率和收斂性；其次對種群的進(jìn)化策略進(jìn)行了調(diào)整，具有較強(qiáng)勘探能力的種群經(jīng)過一段時(shí)間的進(jìn)化后，種群具有豐富的多樣性，包含較多解空間的信息，此時(shí)應(yīng)調(diào)整種群的進(jìn)化策略，使種群專注于對信息的開發(fā)，產(chǎn)生更多的低階遺傳模式；而具有較強(qiáng)開采能力的種群經(jīng)過一段時(shí)間的進(jìn)化后，對現(xiàn)有的基因挖掘出了足夠的信息，此時(shí)應(yīng)調(diào)整種群的進(jìn)化策略，使種群探索更多的有效基因。另一方面，實(shí)行保存策略的種群通過個(gè)體遷移的方式接收其他種群傳遞來的優(yōu)秀個(gè)體，該類個(gè)體往往包含較多的低階有效遺傳模式，通過對這些個(gè)體進(jìn)行交叉處理，使低階遺傳模式有更大幾率重新聯(lián)結(jié)組成高階遺傳模式，產(chǎn)生新的最優(yōu)解，增強(qiáng)了算法的遺傳模式保存能力。

1.2.2 改進(jìn)的并行機(jī)制的測試

本文使用函數(shù)F1和F2來測試改進(jìn)的并行機(jī)制的性能。

F1是多峰函數(shù)，其函數(shù)表達(dá)式為：

F1的定義域空間為-100 ＜Xi＜100，當(dāng)（Xi,Xi+1）取值為（0，0）時(shí)，F(xiàn)1取得全局最小值0。

F2是高維函數(shù)，其函數(shù)表達(dá)式為：

F2的定義域空間為-10 ＜Xi＜10，本文測試計(jì)算中，F(xiàn)2的維度設(shè)置為20，F(xiàn)2的全局最小值為0。

選取文獻(xiàn)[5]提出算法中的并行機(jī)制（parallel mechanism，PM）與本文提出的改進(jìn)并行機(jī)制（improved parallel mechanism，IPM）進(jìn)行對比，PM 中進(jìn)化策略與文獻(xiàn)[5]保持一致，各種群獨(dú)立進(jìn)化，每代將全局最優(yōu)個(gè)體傳遞給其他種群，大體定位后再采用爬山法進(jìn)行細(xì)致搜索（詳見該文）。主要參數(shù)設(shè)置為：PM 種群數(shù)目為6，IPM 種群數(shù)量為2（IPM 經(jīng)復(fù)制后與PM種群數(shù)量一致），染色體數(shù)目50，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05，在IPM 中每隔10 代進(jìn)行一次策略調(diào)整。測試選取兩個(gè)指標(biāo)來評價(jià)并行機(jī)制的性能：（1）平均最優(yōu)解（average optimum solution，AOS），該指標(biāo)是算法多次運(yùn)行的最優(yōu)適應(yīng)度的均值，反映求解質(zhì)量的好壞。（2）收斂率（convergence rate，CR）函數(shù)收斂次數(shù)占實(shí)驗(yàn)總執(zhí)行次數(shù)的百分比。當(dāng)函數(shù)求解結(jié)果滿足于指定的收斂精度時(shí)認(rèn)為收斂成功，收斂精度應(yīng)綜合考量并行機(jī)制的性能來設(shè)定，以便更好地區(qū)分并行機(jī)制之間的優(yōu)劣。

表1 表示兩種并行機(jī)制各執(zhí)行30 次后的實(shí)驗(yàn)結(jié)果，可以看出IPM 的性能要好于PM，這是由于PM 使用固定的進(jìn)化策略，難以保持在搜索空間勘探和開采之間的平衡，使得大部分染色體進(jìn)化效果較差。對于具有較大Pc和Pm數(shù)值的種群來說，雖然容易豐富群體多樣性，擴(kuò)大種群的搜索范圍，但是其中有希望成為全局最優(yōu)解的優(yōu)秀個(gè)體的基因容易被破壞，使種群無法保持穩(wěn)定，難以收斂。對于具有較小Pc和Pm數(shù)值的種群來說，雖然能夠充分利用現(xiàn)有染色體的基因，但其跳出局部最優(yōu)解探尋全局最優(yōu)解的可能性較小，并且也缺少對遷移來的優(yōu)秀個(gè)體進(jìn)行進(jìn)一步開發(fā)的能力。而IPM 通過種群分離控制不同功能進(jìn)而有效地控制了勘探與開采的平衡，部分種群實(shí)施上述改進(jìn)的策略負(fù)責(zé)在解空間勘探新基因并重組成新的低階遺傳模式，保存策略子群負(fù)責(zé)將低階遺傳模式重新聯(lián)結(jié)為高階遺傳模式，通過這樣的方式使算法同時(shí)具備良好的遺傳模式重組能力和遺傳模式保存能力。為進(jìn)一步加強(qiáng)算法的遺傳模式重組能力，OWLMGA 對進(jìn)化策略進(jìn)行了改進(jìn)，并對種群的進(jìn)化策略進(jìn)行調(diào)整，通過這樣的方式提高了搜索效率，改善了染色體的進(jìn)化效果。

Table 1 Experimental results of parallel mechanism表1 并行機(jī)制測試實(shí)驗(yàn)結(jié)果

圖2 表示某次實(shí)驗(yàn)中兩種并行機(jī)制求解函數(shù)的最優(yōu)值曲線，可以看出IPM 所代表的進(jìn)化曲線出現(xiàn)了多次的波折提升，而PM 所代表的曲線每次波折后會(huì)出現(xiàn)一段時(shí)間的停滯，這是由于PM 采用固定的進(jìn)化策略，使得探索能力較強(qiáng)的種群發(fā)現(xiàn)了新的有效基因卻沒有能力對其重組，反而不斷破壞新基因和原有的遺傳模式；而開發(fā)能力較強(qiáng)的種群雖然能夠重組有效基因產(chǎn)生新的遺傳模式，但該種群對搜索空間的勘探能力較弱，種群若長時(shí)間未發(fā)現(xiàn)新的有效基因會(huì)陷入停滯狀態(tài)；PM 這種矛盾的進(jìn)化方式較難控制種群多樣性和收斂速度的有效平衡。而IPM中每個(gè)種群只需負(fù)責(zé)單一進(jìn)化功能，不同種群之間相互協(xié)作，通過這樣的方式減緩了PM 進(jìn)化過程中出現(xiàn)的矛盾，增強(qiáng)了算法的尋優(yōu)能力，有效控制了GA收斂速度和種群多樣性之間的平衡。

1.3 最優(yōu)權(quán)動(dòng)態(tài)控制學(xué)習(xí)機(jī)制

1.3.1 學(xué)習(xí)機(jī)制基本概念

定義1設(shè)H={H1,H2,…,Hm} 為所有種群的集合，種群的個(gè)數(shù)設(shè)為M，每個(gè)種群內(nèi)染色體數(shù)目為N。

定義2（年齡與超齡）對于任意種群Hm存在?xi∈Hm，都有xig.age表示染色體xi在g代的年齡，對于任意染色體xi，其初始年齡為0，年齡更新公式（1）如下：

Fig.2 Comparison of performance of parallel mechanism圖2 并行機(jī)制性能對比

其中，i=1～N，α表示控制參數(shù)（取值范圍為0～1），Hmg.ave表示Hm在第g代的平均適應(yīng)度，xi.fit表示染色體xi的適應(yīng)度值。若染色體長期低于種群平均適應(yīng)度，其年齡就較大，表明該染色體“進(jìn)化潛能”較差，當(dāng)染色體年齡超過規(guī)定年限life時(shí)，成為超齡個(gè)體，在后續(xù)進(jìn)化中會(huì)被淘汰。Hm.old表示Hm中超齡個(gè)體的數(shù)目，即群體內(nèi)年齡大于規(guī)定年限染色體的數(shù)目。

定義3（優(yōu)秀率）對于任意種群Hm都有He表示Hm的優(yōu)秀率（計(jì)算公式見1.3.4 小節(jié)），優(yōu)秀個(gè)體的數(shù)目r=He×N，N為種群大小，即將Hm中適應(yīng)度最大的r個(gè)個(gè)體稱為優(yōu)秀個(gè)體。

定義4（基因模式與模式抽?。τ谌我夥N群Hm，設(shè)種群任意兩個(gè)染色體分別為x={x1,x2,…,xj}，y={y1,y2,…,yj}，xj,yj∈{0,1}，兩個(gè)染色體通過公式z=獲得的染色體稱為模式，其中zj∈{0,1,*}，“*”代表基因模式中非確定位，種群基于當(dāng)代所有優(yōu)秀個(gè)體進(jìn)行抽取得到的模式稱為基因模式，Hmg.scheme表示Hm在第g代的基因模式。

定義5（模式學(xué)習(xí)）對于任意種群Hm，設(shè)種群的任意一個(gè)染色體為x={x1,x2,…,xj}，該染色體和基因模式Hmg.scheme={z1,z2,…,zj} 通過公式x⊙Hmg.scheme=進(jìn)行模式學(xué)習(xí)得到一個(gè)新的染色體x.new。設(shè)待學(xué)習(xí)的染色體基因?yàn)閤=1010110，基因模式Hmg.scheme=1*0100*，則經(jīng)過學(xué)習(xí)后的x.new=1001000。

定義6（基因模式的權(quán)）對于任意種群Hm都有Hmg.weight表示Hmg.scheme的權(quán)值，權(quán)值越高，表示Hmg.scheme越“優(yōu)良”，權(quán)值越低，表示Hmg.scheme越“劣質(zhì)”（計(jì)算公式見1.3.8 小節(jié)）。

定義7（最優(yōu)基因模式）對于任意種群Hm，都有Hm.bscheme表示該種群截止到當(dāng)前代次最“優(yōu)良”（權(quán)最高）的基因模式。

定義8（全局最優(yōu)模式）在算法進(jìn)化過程中，截止到當(dāng)前代次所有種群最優(yōu)秀（權(quán)最高）的基因模式為全局最優(yōu)模式，全局最優(yōu)模式用H.bscheme表示。

定義9（公共區(qū)域）粗粒度模型[19]的多種群GA需要定期進(jìn)行數(shù)據(jù)遷移和交換，本文利用公共區(qū)域來接收上述并行機(jī)制內(nèi)各種群共享的基因模式和最優(yōu)個(gè)體。之后，公共區(qū)域會(huì)比較不同基因模式的優(yōu)劣程度選出H.bscheme，同時(shí)篩選出全局最優(yōu)個(gè)體。此外，公共區(qū)域還持續(xù)監(jiān)聽各個(gè)種群，將H.bscheme分配給發(fā)出群間學(xué)習(xí)請求的種群。

1.3.2 學(xué)習(xí)機(jī)制操作過程

學(xué)習(xí)機(jī)制包括群內(nèi)學(xué)習(xí)（learning within populations，LWP）和群間學(xué)習(xí)（learning between populations，LBP）兩種學(xué)習(xí)方式，分別由群內(nèi)學(xué)習(xí)算子Pi和群間學(xué)習(xí)算子Po進(jìn)行控制。在群內(nèi)學(xué)習(xí)方式中，以模式學(xué)習(xí)作為主要學(xué)習(xí)操作，在群間學(xué)習(xí)方式中，以模式學(xué)習(xí)結(jié)合局部搜索策略作為主要學(xué)習(xí)操作。

（1）群內(nèi)學(xué)習(xí)操作過程如下：

①計(jì)算種群的He。

②按照個(gè)體適應(yīng)度大小降序選擇r個(gè)染色體作為種群優(yōu)秀個(gè)體。

③對優(yōu)秀個(gè)體進(jìn)行模式抽取得到Hmg.scheme，將得到的Hmg.scheme與該種群的Hm.bscheme的權(quán)值進(jìn)行比較，更新Hm.bscheme。

④Pi控制群內(nèi)染色體對Hm.bscheme進(jìn)行學(xué)習(xí)，并及時(shí)更新適應(yīng)度值與年齡。

⑤若達(dá)到規(guī)定進(jìn)行信息遷移的代次，將Hm.bscheme和最優(yōu)染色體傳遞到公共區(qū)域。

⑥公共區(qū)域?qū)⒏鞣N群傳遞過來的Hm.bscheme和最優(yōu)染色體與已有的H.bscheme和全局最優(yōu)個(gè)體進(jìn)行比較，并更新H.bscheme和全局最優(yōu)個(gè)體。

（2）群間學(xué)習(xí)操作過程如下：

①Po判斷種群是否進(jìn)行群間學(xué)習(xí)，確定進(jìn)行群間學(xué)習(xí)的種群向公共區(qū)域發(fā)送學(xué)習(xí)請求。

②公共區(qū)域?qū).bscheme發(fā)送給該種群。

③種群首先淘汰超齡個(gè)體，剩存染色體通過結(jié)合局部搜索策略的模式學(xué)習(xí)方法對H.bscheme進(jìn)行學(xué)習(xí)，通過局部搜索策略新產(chǎn)生的染色體按適應(yīng)度大小填補(bǔ)被淘汰超齡個(gè)體的空缺，并及時(shí)更新適應(yīng)度值和年齡。

群內(nèi)學(xué)習(xí)能夠引導(dǎo)個(gè)體的進(jìn)化方向，個(gè)體通過對優(yōu)秀個(gè)體共性基因的學(xué)習(xí)使自身性狀在較少遺傳代次得到改善。但是若只進(jìn)行群內(nèi)學(xué)習(xí)，種群之間沒有共享信息，就無法避免因?qū)W習(xí)共性基因而引起的多樣性的減弱，容易陷入局部收斂。群間學(xué)習(xí)引導(dǎo)種群的進(jìn)化方向，具有較多超齡個(gè)體的種群進(jìn)化程度較低，說明該種群“進(jìn)化潛力”較差，僅僅通過群內(nèi)學(xué)習(xí)很難追趕上其他種群。因此不但要通過模式學(xué)習(xí)對H.bscheme的確定位進(jìn)行學(xué)習(xí)，還要通過局部搜索策略對H.bscheme的非確定位的鄰域進(jìn)行探索開發(fā)以產(chǎn)生新的染色體，并使用新染色體取代超齡個(gè)體，新染色體通過對種群多樣性的提高來提高種群的“進(jìn)化潛能”，以期待該種群在后續(xù)進(jìn)化中有較大的進(jìn)步。若只進(jìn)行群間學(xué)習(xí)，個(gè)體之間缺乏信息傳遞和反饋，會(huì)影響算法的收斂速度。因此需要同時(shí)采用兩種方式對種群進(jìn)行共同引導(dǎo)。具體來說，每次迭代時(shí)某種群中的每個(gè)個(gè)體分別以概率Pi進(jìn)行群內(nèi)學(xué)習(xí)，之后種群本身以概率Po進(jìn)行群間學(xué)習(xí)，如此，發(fā)揮兩種學(xué)習(xí)方式優(yōu)勢，提升算法的性能。

1.3.3 學(xué)習(xí)機(jī)制的理論研究

學(xué)習(xí)機(jī)制對種群內(nèi)優(yōu)秀個(gè)體提取共性基因組成基因模式，控制種群內(nèi)其他個(gè)體對基因模式進(jìn)行學(xué)習(xí)來改變自身。這種機(jī)制是否有理論上的支持？

拉馬克進(jìn)化學(xué)說（Lamarckian learning）主張環(huán)境條件的改變能引起生物發(fā)生適應(yīng)環(huán)境的變異，即生物體通過后天學(xué)習(xí)獲得性狀改變，這種改變可以通過基因遺傳給后代。即“用進(jìn)廢退”和“獲得性遺傳”。把上述思想應(yīng)用在遺傳算法中，則染色體需要在“環(huán)境”影響下獲得性狀改變并直接編碼到染色體基因上[20]。在本文中，“環(huán)境”即學(xué)習(xí)機(jī)制，學(xué)習(xí)機(jī)制在模式定理思想（詳見1.2.1 小節(jié)）引導(dǎo)下對種群抽取基因模式，作用于染色體，使其對基因模式進(jìn)行學(xué)習(xí)，通過這樣的方式使染色體獲得性狀上的改變，基于拉馬克學(xué)習(xí)的學(xué)習(xí)機(jī)制可以將這種變化按照表現(xiàn)型空間與基因型空間的映射關(guān)系直接編碼到個(gè)體的基因型。但是拉馬克學(xué)習(xí)無法對這種變化進(jìn)行有效的區(qū)分，搜索到更好的表現(xiàn)型就改變原有基因型，在增大算法尋優(yōu)性能的同時(shí)，陷入局部收斂的可能性也在增大。而學(xué)習(xí)機(jī)制通過對種群的優(yōu)秀個(gè)體進(jìn)行模式抽取，獲得的基因模式包含多個(gè)優(yōu)秀個(gè)體的共性基因，因此基因模式可以進(jìn)一步地定義為“由多個(gè)低階有效模式組成的定長基因串”。個(gè)體通過學(xué)習(xí)基因模式獲得優(yōu)秀個(gè)體的共性基因，由于各染色體的基因組合不同，有的染色體會(huì)直接學(xué)習(xí)到有效遺傳模式，也有染色體的基因與學(xué)習(xí)到的基因組成新的有效遺傳模式，兩種形式都有助于個(gè)體產(chǎn)生有益的性狀變化?；蚰Ｊ匠槿〉牟皇菃为?dú)染色體的基因，而是多個(gè)優(yōu)秀個(gè)體共有的基因，降低了種群因?qū)W習(xí)陷入局部收斂的風(fēng)險(xiǎn)。搜索到更高表現(xiàn)型的個(gè)體在選擇操作作用下有更大概率被選入下一代，通過這樣的方式來引導(dǎo)進(jìn)化方向并將有效遺傳模式繼承下去。

1.3.4 自適應(yīng)改變優(yōu)秀率He的值

優(yōu)秀率He負(fù)責(zé)每次迭代時(shí)篩選種群內(nèi)優(yōu)秀個(gè)體，通過對優(yōu)秀個(gè)體進(jìn)行模式抽取得到的基因模式來引導(dǎo)種群進(jìn)化方向。文獻(xiàn)[15]采用線性的方式（詳見該文）計(jì)算He，使得He的值在種群平均適應(yīng)度隨迭代次數(shù)而增加時(shí)將越來越高，高數(shù)值He意味著優(yōu)秀個(gè)體的數(shù)目較多，在此基礎(chǔ)上進(jìn)行模式抽取獲得的基因模式將充滿非確定位，使基因模式失去作用。因此，為了更好地發(fā)揮優(yōu)秀率在學(xué)習(xí)機(jī)制不同時(shí)期的作用，避免基因模式在算法進(jìn)化中后期充滿非確定位，本文提出了一種根據(jù)進(jìn)化代數(shù)自適應(yīng)控制優(yōu)秀率值的選取計(jì)算式（2）：

式中，He1是最小優(yōu)秀概率，He2是最大優(yōu)秀概率，g是當(dāng)前進(jìn)化代數(shù)，G是總進(jìn)化代數(shù)。

圖3 中，虛線代表遵循線性變換的文獻(xiàn)[15]中的He，實(shí)線表示遵循式（2）的He的變化規(guī)律。文獻(xiàn)[15]所提出的優(yōu)秀率計(jì)算式是基于線性的改變，本文引入sin 函數(shù)可以起到非線性地自適應(yīng)改變優(yōu)秀率的作用，使He的數(shù)值更加符合算法的進(jìn)化現(xiàn)狀，使種群能夠更好地選取優(yōu)秀個(gè)體。具體來說，算法開始時(shí)，實(shí)線相比同時(shí)期的虛線有更高的優(yōu)秀率值，這是因?yàn)樗惴ㄟM(jìn)化初期，種群平均適應(yīng)度較低，優(yōu)秀個(gè)體內(nèi)包含較多劣質(zhì)基因，為避免劣質(zhì)基因混入基因模式，式（2）在進(jìn)化前期自適應(yīng)地提高He的值，旨在增加優(yōu)秀個(gè)體數(shù)量，對較多優(yōu)秀個(gè)體進(jìn)行模式抽取會(huì)減小劣質(zhì)基因混入基因模式的概率。隨著算法進(jìn)入中后期，優(yōu)秀個(gè)體基因之間相似度比較高，為避免真正的優(yōu)秀基因被較差優(yōu)秀個(gè)體的劣質(zhì)基因干擾，實(shí)線隨著進(jìn)化代數(shù)增加而提升的速度比同時(shí)期的虛線緩慢，這樣能夠保證只有真正優(yōu)秀的基因才被抽取到基因模式中，還可以避免算法中后期基因模式充滿非確定位的現(xiàn)象，使基因模式在算法中后期也能夠引導(dǎo)進(jìn)化方向。

Fig.3 Adaptive curve of excellent rate values圖3 優(yōu)秀率自適應(yīng)曲線

1.3.5 自適應(yīng)改變?nèi)簝?nèi)學(xué)習(xí)算子Pi的值

群內(nèi)學(xué)習(xí)算子Pi控制種群內(nèi)染色體對Hm.bscheme進(jìn)行群內(nèi)學(xué)習(xí)操作。文獻(xiàn)[15]計(jì)算Pi時(shí)未充分考慮種群進(jìn)化情況，隨著種群平均適應(yīng)度的增長，群內(nèi)學(xué)習(xí)頻率逐漸升高，種群極易陷入“早熟”收斂。在本文中，計(jì)算Pi不但要考慮進(jìn)化的時(shí)期，還要考慮種群本身進(jìn)化程度。算法前期，種群內(nèi)個(gè)體質(zhì)量普遍較差，應(yīng)通過增大Pi加強(qiáng)對種群的引導(dǎo)進(jìn)化，隨著算法的進(jìn)行，應(yīng)逐漸降低Pi來保持種群多樣性，以提升收斂到最優(yōu)解的能力。此外，還要考慮種群本身進(jìn)化情況，適應(yīng)度較低的種群更應(yīng)取較大數(shù)值的Pi來加強(qiáng)引導(dǎo)，適應(yīng)度較高的種群為了保持種群多樣性，避免發(fā)生“早熟”收斂的現(xiàn)象，加快收斂速度，應(yīng)該適當(dāng)減小Pi。綜合以上幾點(diǎn)，本文設(shè)計(jì)了一種自適應(yīng)動(dòng)態(tài)控制的群內(nèi)學(xué)習(xí)算子：

式中，Pi1是最小群內(nèi)學(xué)習(xí)概率；Pi2是最大群內(nèi)學(xué)習(xí)概率；g是當(dāng)前進(jìn)化代數(shù)；G是總進(jìn)化代數(shù)；Hm.ave為種群Hm平均適應(yīng)度值；Hm.best為種群Hm最優(yōu)適應(yīng)度值。

1.3.6 自適應(yīng)改變?nèi)洪g學(xué)習(xí)算子Po的值

群間學(xué)習(xí)算子Po控制種群進(jìn)行群間學(xué)習(xí)操作，由定義2 可知，如果染色體的適應(yīng)度在進(jìn)化過程中長期處于較低狀態(tài)，則該染色體的年齡會(huì)比較大，說明該染色體“進(jìn)化潛能”較差，此時(shí)需要淘汰超齡個(gè)體并以新染色體補(bǔ)充超齡個(gè)體的空缺，新染色體的加入能夠提升種群多樣性。文獻(xiàn)[15]計(jì)算Po時(shí)未充分考慮超齡個(gè)體的影響，使得種群進(jìn)行群間學(xué)習(xí)時(shí)可能出現(xiàn)淘汰超齡個(gè)體過多的情況而造成算法不穩(wěn)定或出現(xiàn)無超齡個(gè)體的情況而使群間學(xué)習(xí)無效。計(jì)算Po應(yīng)當(dāng)首要考慮群內(nèi)超齡個(gè)體的數(shù)目，種群內(nèi)超齡個(gè)體較多時(shí)，說明該種群內(nèi)染色體的“進(jìn)化潛能”較差，應(yīng)當(dāng)加大Po淘汰超齡個(gè)體，種群內(nèi)超齡個(gè)體少時(shí)，說明該種群內(nèi)染色體有較大“進(jìn)化潛能”，該種群應(yīng)當(dāng)以群內(nèi)學(xué)習(xí)為主，因此要減少Po。此外，還要考慮種群相對于其他種群的進(jìn)化情況，平均適應(yīng)度較低的種群更應(yīng)該進(jìn)行群間學(xué)習(xí)，以便追趕其他種群。綜合以上幾點(diǎn)，本文提出了根據(jù)種群內(nèi)超齡個(gè)體數(shù)目以及種群進(jìn)化情況自適應(yīng)調(diào)節(jié)群間學(xué)習(xí)概率的計(jì)算式（4）：

式中,Po1是最小群間學(xué)習(xí)概率；Po2是最大群間學(xué)習(xí)概率；g是當(dāng)前進(jìn)化代數(shù)；G是總進(jìn)化代數(shù)；Hm.old表示種群內(nèi)超齡個(gè)體數(shù)目；N表示種群內(nèi)染色體總數(shù)目；max(Hm.ave) 為所有種群中最大平均適應(yīng)度值；Hm.ave為當(dāng)前種群平均適應(yīng)度值；min(Hm.ave)為所有種群中最小平均適應(yīng)度值。

從式（4）中可以看出種群內(nèi)超齡個(gè)體的數(shù)量決定了Po的大小，當(dāng)超齡個(gè)體的數(shù)目較少時(shí)，Po值也較小，隨著迭代的進(jìn)行，種群內(nèi)超齡個(gè)體的數(shù)目不斷增多，Po值也逐漸增大，超齡個(gè)體被淘汰的幾率也逐漸增大。這樣，每次進(jìn)行群間學(xué)習(xí)時(shí)，種群內(nèi)的超齡個(gè)體能夠保持在一定的數(shù)目，避免了種群進(jìn)行學(xué)習(xí)時(shí)群內(nèi)沒有超齡個(gè)體或者超齡個(gè)體過多的情況，保證了種群進(jìn)化的穩(wěn)定性。最后，引入余弦函數(shù)非線性控制不同種群的學(xué)習(xí)概率，能夠使種群的學(xué)習(xí)更加平滑，保持種群進(jìn)化時(shí)的穩(wěn)定性。具體來說，對于種群平均適應(yīng)度值處于[min(Hm.ave),(max(Hm.ave)-min(Hm.ave))/2]的種群，該種群更應(yīng)該追趕其他種群，因此有較大的Po值；對于種群平均適應(yīng)度值處于[(max(Hm.ave)-min(Hm.ave))/2,(max(Hm.ave)+min(Hm.ave))/2]的種群，該種群本身基因質(zhì)量比較好，產(chǎn)生更好結(jié)果的可能性更大，因此小幅度增加該類種群的Po值；其余種群與上述區(qū)間的種群相比有更大的平均適應(yīng)度，說明這類種群有較好的“進(jìn)化潛能”，應(yīng)當(dāng)以群內(nèi)學(xué)習(xí)為主，因此取較小的Po。通過非線性地改變不同質(zhì)量的種群學(xué)習(xí)比重，使群間學(xué)習(xí)能更好地發(fā)揮引導(dǎo)種群進(jìn)化方向和加強(qiáng)局部搜索能力的作用。

超齡個(gè)體經(jīng)歷過多代的進(jìn)化，雖然適應(yīng)度較低，但也代表著解空間內(nèi)與其相鄰的可能解所在區(qū)域的信息。文獻(xiàn)[15]采用隨機(jī)產(chǎn)生新染色體的方法取代超齡個(gè)體，該方法的缺點(diǎn)一方面是由于新產(chǎn)生的個(gè)體往往表現(xiàn)比較劣質(zhì)，在一定程度上會(huì)減緩算法的收斂速度；另一方面是超齡個(gè)體所代表的解空間信息會(huì)直接消失。本文采用1.3.7 小節(jié)所表述的局部搜索策略對超齡個(gè)體進(jìn)行信息挖掘，并以適應(yīng)度作為質(zhì)量準(zhǔn)則來評價(jià)這些信息的價(jià)值，具有高價(jià)值的個(gè)體往往也具有更高的質(zhì)量。從另一角度來說，這類個(gè)體也具有一定的“進(jìn)化潛能”。局部搜索策略對這類個(gè)體進(jìn)行了保留，對沒有價(jià)值的個(gè)體進(jìn)行了淘汰，通過這樣的方式避免了超齡個(gè)體所代表的有效信息的缺失，同時(shí)還對這一有效信息進(jìn)行了進(jìn)一步的挖掘，有希望得到更優(yōu)秀的個(gè)體。

1.3.7 一種新型局部搜索策略——分裂爬山法

GA 在迭代進(jìn)化過程中，總是貪心選擇適應(yīng)度大的個(gè)體，導(dǎo)致GA 容易陷入局部最優(yōu)，無法收斂到全局最優(yōu)解。為此，有國內(nèi)外學(xué)者引入梯度法[21]、爬山法[5]、列表尋優(yōu)法[22]等優(yōu)化方法作為局部搜索策略，加強(qiáng)GA 的局部搜索能力。本文在前人研究基礎(chǔ)上，提出一種新的局部搜索策略，在染色體對基因模式的確定位進(jìn)行學(xué)習(xí)時(shí)，該策略能夠?qū)ζ浞谴_定位進(jìn)行局部細(xì)搜，通過這種局部搜索策略，染色體能夠在允許的鄰域內(nèi)搜索到適應(yīng)度更高的個(gè)體。

設(shè)H.bscheme=10*10*011，待學(xué)習(xí)的個(gè)體為x1=011001011，首先是x1的第一個(gè)和第二個(gè)基因?qū).bscheme的相應(yīng)位置基因進(jìn)行學(xué)習(xí)，x1的第一個(gè)和第二個(gè)基因位置變?yōu)? 和0，當(dāng)在第三個(gè)基因位置碰到H.bscheme的非確定位的時(shí)候，通過分裂算子來判定是否進(jìn)行分裂，確定進(jìn)行分裂后，以該非確定位基因?yàn)楹诵倪M(jìn)行分裂，非確定位基因同時(shí)取0、1 兩個(gè)基因，并結(jié)合之前學(xué)習(xí)過的基因進(jìn)行分裂產(chǎn)生兩個(gè)新的染色體，分裂后的第一個(gè)染色體x2=100001011，第二個(gè)染色體x3=101001011，分裂后對父染色體x1的第三個(gè)基因位進(jìn)行取反操作（將0 基因置為1，1 基因置為0），然后父染色體x1繼續(xù)進(jìn)行學(xué)習(xí)和分裂操作，直至學(xué)習(xí)到H.bscheme的最后一個(gè)基因位。

圖4 描繪了分裂爬山法作用于染色體在基因型空間和表現(xiàn)型空間的影響。由圖中基因型空間可以看出x1在第三個(gè)基因位進(jìn)行分裂產(chǎn)生了x2和x3兩個(gè)染色體，在表現(xiàn)型空間可以看到x2和x3在x1的基礎(chǔ)上進(jìn)行適應(yīng)度的攀爬，通過這樣的方式實(shí)現(xiàn)了對x1鄰域空間的探索，彌補(bǔ)GA 局部搜索能力弱的缺陷，實(shí)現(xiàn)了探索新適應(yīng)度的目的。而在群間學(xué)習(xí)中，該局部搜索策略分裂產(chǎn)生的新染色體按適應(yīng)度值排列后用于補(bǔ)充被淘汰超齡個(gè)體的空缺，新染色體比“進(jìn)化潛能”普遍較差的超齡個(gè)體更有機(jī)會(huì)進(jìn)化為優(yōu)良個(gè)體。此外，通過學(xué)習(xí)遍歷H.bscheme后，第一個(gè)非確定位和最后一個(gè)非確定位之間有多種組合，因此新染色體之間基因相似程度并不高，新染色體補(bǔ)足超齡個(gè)體的空缺后，能夠豐富種群的多樣性。

1.3.8 基因模式的權(quán)

學(xué)習(xí)機(jī)制通過群內(nèi)學(xué)習(xí)和群間學(xué)習(xí)共同引導(dǎo)種群進(jìn)化，因此會(huì)有概率出現(xiàn)下一代基因模式不如上一代基因模式“優(yōu)秀”的情況。

本文提出一種評價(jià)函數(shù)，通過該函數(shù)對基因模式進(jìn)行賦權(quán)操作，算法以權(quán)值來比較不同基因模式的優(yōu)劣程度，選出群內(nèi)最優(yōu)基因模式Hm.bscheme和全局最優(yōu)模式H.bscheme。基因模式的權(quán)計(jì)算公式如下：

Fig.4 Effect of split mountain climbing method on new chromosomes圖4 分裂爬山法對新染色體的影響

式中，Hm.best為種群最優(yōu)秀個(gè)體適應(yīng)度值；fˉ是種群內(nèi)除Hm.best剩余優(yōu)秀個(gè)體平均適應(yīng)度值；g是當(dāng)前進(jìn)化代數(shù)；G是總進(jìn)化代數(shù)。

進(jìn)化前期，種群平均適應(yīng)度較低，群內(nèi)大部分染色體“劣質(zhì)”基因較多，應(yīng)當(dāng)加強(qiáng)群體內(nèi)最優(yōu)秀個(gè)體引導(dǎo)種群進(jìn)化方向的力度，減弱其他較差優(yōu)秀個(gè)體的影響，因此在進(jìn)化前期提高Hm.best的權(quán)重，降低fˉ的權(quán)重。隨著迭代的進(jìn)行，種群平均適應(yīng)度逐漸升高，群體內(nèi)最優(yōu)秀個(gè)體和其他優(yōu)秀個(gè)體相似度也逐漸變大，考慮到最優(yōu)秀個(gè)體有可能是局部最優(yōu)解，為了避免種群進(jìn)化方向被局部最優(yōu)解錯(cuò)誤引導(dǎo)，應(yīng)逐漸降低Hm.best的權(quán)重，提高fˉ的權(quán)重。

1.4 OWLMGA 算法流程

算法流程如圖5 所示。

算法執(zhí)行流程如下：

（1）初始化控制參數(shù)和公共區(qū)域。

（2）多樣本均勻分區(qū)種群初始化產(chǎn)生父種群，父種群自我復(fù)制生成子種群，子種群部署不同進(jìn)化策略。

（3）各子種群按自身進(jìn)化策略獨(dú)立計(jì)算演化，進(jìn)行遺傳操作，更新個(gè)體適應(yīng)度和年齡。

Fig.5 Flow chart of OWLMGA algorithm圖5 OWLMGA 算法流程圖

（4）各子種群將群體內(nèi)優(yōu)秀個(gè)體傳遞給同父種群實(shí)施保存策略的子種群。保存策略子種群對優(yōu)秀個(gè)體進(jìn)行發(fā)掘，保留優(yōu)秀基因。

（5）對種群進(jìn)行模式抽取獲得基因模式，同時(shí)將基因模式和全局最優(yōu)個(gè)體上傳到公共區(qū)域。

（6）種群內(nèi)個(gè)體通過Pi判定是否進(jìn)行群內(nèi)學(xué)習(xí)，否則轉(zhuǎn)（7）。

（7）各子種群通過Po判定是否進(jìn)行群間學(xué)習(xí)，否則轉(zhuǎn)（8）。

（8）檢查終止條件，滿足轉(zhuǎn)（9），否則轉(zhuǎn)（4）。

（9）算法結(jié)束。

算法實(shí)施時(shí)可利用Matlab 的并行計(jì)算工具箱(parallel computing toolbox，PCT)進(jìn)行并行運(yùn)算，通過并行處理不同種群的進(jìn)化，提升了算法的收斂速度，大幅度減少了算法解決問題的時(shí)間。

2 仿真研究

2.1 測試函數(shù)及對比算法

為驗(yàn)證本文提出的OWLMGA 算法性能，本節(jié)以12 個(gè)基準(zhǔn)函數(shù)為對象進(jìn)行仿真測試。f1～f6所代表的多峰值函數(shù)能夠測驗(yàn)算法的開采能力及跳出局部最優(yōu)的能力，f7～f12所代表的高維函數(shù)用于測試算法的勘探能力及收斂能力。本文選取標(biāo)準(zhǔn)多種群遺傳算法（standard multi-population genetic algorithm，SMGA）、文獻(xiàn)[5]提出的HGA（hybrid genetic algorithm）及文獻(xiàn)[15]提出的PGABL（parallel genetic algorithm based on learning mechanism）作為對比算法，其中以SMGA驗(yàn)證OWLMGA 所改進(jìn)的多種群并行機(jī)制的性能；HGA 將多種群遺傳算法與局部搜索策略混合增強(qiáng)了多種群遺傳算法的局部搜索能力，以該算法驗(yàn)證OWLMGA 改進(jìn)的局部搜索策略的有效性；PGABL雖然使用了多種群并行機(jī)制，但各種群均使用了相同的交叉及變異參數(shù)，未能發(fā)揮多種群的優(yōu)勢，因此以該算法印證OWLMGA 的學(xué)習(xí)機(jī)制。測試函數(shù)如表2 所示，其中D是變量的維數(shù)。

2.2 仿真實(shí)驗(yàn)設(shè)置

為公平起見，SMGA、HGA、OWLMGA 均采用相同的參數(shù)，PGABL與原文保持一致。以上算法均采用二進(jìn)制編碼，適應(yīng)度比例選擇，單點(diǎn)交叉和多基因位變異。算法的控制參數(shù)如下：種群數(shù)目為4，每個(gè)種群染色體規(guī)模N均為50，染色體長度為40，算法迭代次數(shù)G為400。在SMGA中，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05。在HGA 中，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05。PGABL 中α=1，life=15，Pc=0.80，Pm=0.06。在OWLMGA 中，α=1，life=15，pc1=0.70，pm1=0.10，pc2=0.50，pm2=0.30，pc3=0.85，pm3=0.05，Pe1=0.10，Pe2=0.20，Pi1=0.30，Pi2=0.50，Po1=0.10，Po2=0.15，種群之間每隔15 代進(jìn)行一次信息遷移和策略調(diào)整。

實(shí)驗(yàn)選取4 個(gè)指標(biāo)評價(jià)算法的性能：（1）最優(yōu)值，該指標(biāo)反映了算法求解質(zhì)量的好壞；（2）最優(yōu)收斂代數(shù)，該指標(biāo)反映了算法求解最優(yōu)值的速度，收斂代數(shù)越少，說明算法求解速度越快；（3）平均收斂代數(shù)，該指標(biāo)是算法多次運(yùn)行的最優(yōu)收斂代數(shù)的平均值，反映了算法求解最優(yōu)值的穩(wěn)定性；（4）收斂次數(shù)及收斂率，收斂結(jié)果滿足指定收斂精度時(shí)則認(rèn)為收斂成功，收斂次數(shù)反映了算法求解最優(yōu)值的成功率。收斂精度應(yīng)綜合考量函數(shù)維度及不同算法之間的性能來設(shè)定，以便更好區(qū)分算法之間的優(yōu)劣。

2.3 仿真實(shí)驗(yàn)結(jié)果分析

表3 與表4 表示4 種算法各執(zhí)行30 次后的優(yōu)化測試結(jié)果。由測試結(jié)果可以看出，與SMGA、HGA、PGABL相比，OWLMGA 求解的函數(shù)最優(yōu)值更接近函數(shù)的理論最優(yōu)值，說明該算法求解精度高。OWLMGA的收斂次數(shù)接近實(shí)驗(yàn)總次數(shù)，其中對函數(shù)f1和f2求解的收斂次數(shù)與實(shí)驗(yàn)總次數(shù)一致，說明該算法的穩(wěn)定性較好。由PGABL 求解f1結(jié)果可知，雖然收斂次數(shù)較低，但發(fā)生收斂的平均代數(shù)也較低，說明學(xué)習(xí)機(jī)制賦予了該算法較好的尋優(yōu)能力，而PGABL 求解f2未發(fā)生滿足收斂精度的收斂，這是因?yàn)閒2的全局最優(yōu)值被局部最優(yōu)值包圍，算法尋優(yōu)過程中極易陷入局部極值點(diǎn)，說明該算法跳出局部最優(yōu)能力較差。f3的數(shù)學(xué)特性類似于聚集的多個(gè)山峰，其每個(gè)頂峰都有一個(gè)局部最大值，會(huì)對算法造成干擾，該函數(shù)能夠體現(xiàn)算法跳出局部極值及收斂能力，由最優(yōu)迭代次數(shù)和收斂次數(shù)上可以看出，HGA 雖然收斂次數(shù)比SMGA 低，但最優(yōu)迭代次數(shù)表現(xiàn)較好，這是因?yàn)镠GA所使用的局部搜索策略提升了該算法的局部搜索能力，但也更易陷入局部最優(yōu)。而OWLMGA 求解f3收斂次數(shù)較高，且收斂的平均迭代次數(shù)較低，說明該算法具有更好的跳出局部最優(yōu)的能力和開發(fā)能力。在求解f7、f8高維函數(shù)時(shí)出現(xiàn)了兩個(gè)極端，在本文30次實(shí)驗(yàn)中，PGABL 求解f7、f8未發(fā)生收斂，而SMGA和HGA 有較少收斂次數(shù)，說明并行機(jī)制提升了算法的全局尋優(yōu)能力，OWLMGA 求解f7、f8具有較高的收斂率，說明OWLMGA 有更好的全局尋優(yōu)能力和收斂能力。

Table 2 Test function表2 測試函數(shù)

圖6 描繪了某次實(shí)驗(yàn)中SMGA、HGA、PGABL 與OWLMGA 對12 個(gè)測試函數(shù)求解的每代最優(yōu)值的比較。由圖6 中的（c）和（e）可以看出，相對于其他算法，OWLMGA 有更好的初始解，這是由于均勻分區(qū)初始化方法產(chǎn)生的種群，其群體內(nèi)的個(gè)體能夠較好地分布在解空間，該方法使得新產(chǎn)生的個(gè)體有幾率位于函數(shù)峰值附近，因此算法有較好的初始解。

Table 3 Experimental results of function f1 to f6表3 f1～f6 函數(shù)實(shí)驗(yàn)結(jié)果

由圖6 的（d）和（g）可以看出，SMGA、HGA 與OWLMGA 在求解高維函數(shù)的表現(xiàn)要優(yōu)于PGABL，這是因?yàn)槎喾N群并行機(jī)制使算法能夠保持較好的多樣性及全局尋優(yōu)能力。而由圖6中的（b）可知，SMGA雖然能夠收斂到全局最優(yōu)值，但是該算法的進(jìn)化曲線出現(xiàn)了長時(shí)間水平停滯狀態(tài)，這是由于該算法使用固定的進(jìn)化策略導(dǎo)致群體內(nèi)個(gè)體的進(jìn)化效果較差，但是由于種群間個(gè)體遷移的作用使得該算法總能產(chǎn)生新的最優(yōu)值，使得該算法在大部分情況下總是能夠收斂。而OWLMGA 所對應(yīng)的進(jìn)化曲線更加“陡峭”，這是由于算法為每個(gè)種群部署不同的進(jìn)化策略并定期調(diào)整進(jìn)化策略，使得種群不必等待個(gè)體遷移，而是通過策略的調(diào)整便能進(jìn)行自我開發(fā)產(chǎn)生新的最優(yōu)解，保存策略保證了算法不會(huì)因更換策略而導(dǎo)致群體內(nèi)優(yōu)秀個(gè)體的基因被破壞，優(yōu)秀個(gè)體之間重組產(chǎn)生更優(yōu)秀解的可能性更大。由圖6 中（e）和（h）可以看出，PGABL 算法對應(yīng)的曲線在進(jìn)化前期有比較“陡峭”的變化趨勢，表明該算法在進(jìn)化前期有較強(qiáng)的尋優(yōu)能力，而在進(jìn)化后期，該曲線出現(xiàn)了長時(shí)間的水平停滯狀態(tài)，直到算法結(jié)束也沒有接近全局最優(yōu)值。這是由于PGABL 算法通過學(xué)習(xí)機(jī)制引導(dǎo)種群進(jìn)化方向，該機(jī)制能夠使算法在進(jìn)化前期很快接近全局最優(yōu)值，但是進(jìn)化一段時(shí)間后，該算法的基因模式充滿了不確定位，使基因模式失去了引導(dǎo)作用，從而使PGABL 算法淪落為SGA 算法，導(dǎo)致該算法在進(jìn)化中后期經(jīng)常陷入局部最優(yōu)值，難以收斂到全局最優(yōu)值。而從OWLMGA 算法的進(jìn)化曲線可以看出，算法在整體進(jìn)化的過程中能夠保持較快的收斂速度，在較短的進(jìn)化代數(shù)內(nèi)就能夠收斂到全局最優(yōu)解。進(jìn)化前期，進(jìn)化曲線呈上升趨勢快速接近全局最優(yōu)解，表明該算法能夠不斷尋得新的最優(yōu)值，而在算法后期，該算法出現(xiàn)多次短暫停滯并繼續(xù)上升，表明該算法的學(xué)習(xí)機(jī)制在算法中后期不會(huì)出現(xiàn)學(xué)習(xí)機(jī)制失效的現(xiàn)象，仍能夠發(fā)揮良好的作用。

Table 4 Experimental results of function f7 to f12表4 f7～f12 函數(shù)實(shí)驗(yàn)結(jié)果

2.4 計(jì)算復(fù)雜度分析

設(shè)種群數(shù)目為M，種群大小為N，染色體長度為L，采用隨機(jī)初始化方法（random initialization method）產(chǎn)生多個(gè)種群，種群中任意個(gè)體的各基因位取1 或0的概率相等，即p=q=0.5，且各基因位之間是獨(dú)立的。采用隨機(jī)初始化方法的時(shí)間復(fù)雜度與種群規(guī)模有關(guān)。其中，M、N、L的數(shù)值越大，其計(jì)算的時(shí)間復(fù)雜度O(MNL)也就越大。而本文提出的初始化方法，雖然在大規(guī)模樣本下以海明距離為標(biāo)準(zhǔn)選取個(gè)體，理論上計(jì)算的時(shí)間復(fù)雜度為O(iMNL)，其中，i為樣本比例的系數(shù)。但各種群的大小未變，即初始化過程中不會(huì)用到超過種群大小或接近樣本規(guī)模數(shù)量的個(gè)體，因此本文初始化方法的實(shí)際時(shí)間復(fù)雜度為O(MNL|iMNL)，涉及上述參數(shù)的計(jì)算對Matlab 軟件來說計(jì)算量較小，且初始化行為只會(huì)發(fā)生一次，不存在多次迭代，因此不會(huì)較明顯地影響運(yùn)算速度。

數(shù)學(xué)模型的參數(shù)擬合決定了算法的時(shí)間復(fù)雜度[5]，OWLMGA 和對比算法（SMGA、HGA）采用了相同種群規(guī)模，OWLMGA 提出的并行機(jī)制通過種群分離控制不同進(jìn)化功能，并且采用了改進(jìn)的進(jìn)化策略及調(diào)整種群的進(jìn)化策略，但是上述行為不會(huì)使并行機(jī)制發(fā)生更深層的循環(huán)。而本文選取的另外兩種對比算法（HGA、PGABL）分別采用了爬山法和線性的學(xué)習(xí)機(jī)制。前者對遺傳算法的每代尋優(yōu)結(jié)果使用爬山法進(jìn)行局部搜索，在遺傳算法的計(jì)算復(fù)雜度基礎(chǔ)上多了爬山法的內(nèi)層循環(huán)，使得該算法的時(shí)間復(fù)雜度較高。后者所使用的學(xué)習(xí)機(jī)制由于其參數(shù)設(shè)置的不合理使得學(xué)習(xí)機(jī)制在算法中后期的操作頻率越來越高，增加了算法的時(shí)間復(fù)雜度。相比之下，OWLMGA 中的學(xué)習(xí)機(jī)制是作為并行機(jī)制的附加模塊參與計(jì)算，與遺傳操作處于同一迭代次數(shù)，近似為一種線性的關(guān)系，使得OWLMGA 基本運(yùn)算的頻度與SMGA 相同，沒有過多地增加算法的時(shí)間復(fù)雜度。此外，學(xué)習(xí)機(jī)制中的局部搜索策略雖然對淘汰個(gè)體及其非確定位進(jìn)行了循環(huán)搜索，但由于自適應(yīng)的He與Po的存在，使得每代參與計(jì)算的非確定位基因的數(shù)目l和被淘汰個(gè)體的數(shù)目n小于染色體長度L和種群大小N，增加的計(jì)算量有限。

Fig.6 Comparison of optimum curves of algorithms圖6 算法尋優(yōu)曲線對比

3 結(jié)論

通過介紹相關(guān)研究并結(jié)合分析遺傳算法易“早熟”收斂及收斂速度慢等缺點(diǎn)產(chǎn)生的原因，指出現(xiàn)有方法的不足之處及缺陷。本文在前人研究基礎(chǔ)上，秉著充分發(fā)揮遺傳算法優(yōu)點(diǎn)，克服遺傳算法的不足的思路，提出了均勻分區(qū)的多種群初始化方法，改進(jìn)的多種群并行機(jī)制及動(dòng)態(tài)控制的學(xué)習(xí)機(jī)制，并融合上述改進(jìn)形成一種新的混合遺傳算法。

最后實(shí)驗(yàn)結(jié)果證明，改進(jìn)的多種群并行機(jī)制和最優(yōu)權(quán)動(dòng)態(tài)控制學(xué)習(xí)機(jī)制天然具有良好的溝通能力，兩種機(jī)制結(jié)合起來充分發(fā)揮了每個(gè)機(jī)制的優(yōu)勢，增強(qiáng)了算法的全局搜索能力和局部搜索能力。