最優權動態控制學習機制的多種群遺傳算法

潘家文，錢 謙+，伏云發，馮 勇

1.昆明理工大學 信息工程與自動化學院，昆明 650500

2.昆明理工大學 云南省計算機技術應用重點實驗室，昆明 650500

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

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

為設計一種更加高效的遺傳算法，本文在前人研究基礎上做出改進，提出了最優權動態控制學習機制的多種群遺傳算法（multi-population genetic algorithm based on optimal weight dynamic control learning mechanism，OWLMGA）。具體方法如下：

（1）采用一種均勻分區多種群初始化方法，該方法在避免擴大種群規模的基礎上，能夠產生多個種群較均勻分布在解空間的不同區域，保證了初始解的多樣性，避免算法結果因多樣性差陷入局部最優。

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

（3）采用了最優權動態控制的學習機制，該機制利用一種基于適應度的評價函數衡量基因模式的優劣程度，并能夠根據進化中種群個體適應度的不同情況自適應調節基因模式的引導過程。

1 OWLMGA 基本思想

為改進GA 易“早熟”收斂的缺點，提出均勻分區多種群初始化方法和改進的多種群并行機制。為引導算法進化方向及加強局部搜索能力，提出了動態控制的學習機制，并將兩種機制結合起來，形成一種能充分發揮兩種機制優勢的混合算法。

1.1 均勻分區多種群初始化方法

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

海明距離（兩條染色體間相同基因座上不同基因的數量）是衡量遺傳算法種群多樣性的傳統方法之一。與其他度量方法相比，海明距離方法的主要優點是操作簡單，僅需比較個體所代表的字符串，而不需要與目標函數相關的信息，不會增加計算復雜度。該方法的另一個優點是比較的是個體基因型的差距，而不是個體表現型之間的差距，能夠更好地判斷個體基因之間的親屬關系。

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

均勻分區多種群初始化方法能夠使不同種群較均勻地分布在解空間的不同區域，每個種群隨機地將適當距離的可能解放入種群中，該方法避免了隨機初始化方法導致可能解聚集在局部區域的情況。通過這樣的方式進行種群初始化，可以在避免擴大種群規模基礎上保證種群多樣性，有助于算法跳出局部最優值，尋找全局最優值。

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

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

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

（3）從P中選擇第一個染色體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，轉（6），否則轉（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。轉（5）。

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

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

1.2 改進的多種群并行機制

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

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

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

Fig.1 Processing structure of improved multi-population parallel mechanism圖1 改進的多種群并行機制執行過程

1.2.1 改進的并行機制理論研究

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

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

1.2.2 改進的并行機制的測試

本文使用函數F1和F2來測試改進的并行機制的性能。

F1是多峰函數，其函數表達式為：

F1的定義域空間為-100 ＜Xi＜100，當（Xi,Xi+1）取值為（0，0）時，F1取得全局最小值0。

F2是高維函數，其函數表達式為：

F2的定義域空間為-10 ＜Xi＜10，本文測試計算中，F2的維度設置為20，F2的全局最小值為0。

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

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

Table 1 Experimental results of parallel mechanism表1 并行機制測試實驗結果

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

1.3 最優權動態控制學習機制

1.3.1 學習機制基本概念

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

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

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

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

定義3（優秀率）對于任意種群Hm都有He表示Hm的優秀率（計算公式見1.3.4 小節），優秀個體的數目r=He×N，N為種群大小，即將Hm中適應度最大的r個個體稱為優秀個體。

定義4（基因模式與模式抽取）對于任意種群Hm，設種群任意兩個染色體分別為x={x1,x2,…,xj}，y={y1,y2,…,yj}，xj,yj∈{0,1}，兩個染色體通過公式z=獲得的染色體稱為模式，其中zj∈{0,1,*}，“*”代表基因模式中非確定位，種群基于當代所有優秀個體進行抽取得到的模式稱為基因模式，Hmg.scheme表示Hm在第g代的基因模式。

定義5（模式學習）對于任意種群Hm，設種群的任意一個染色體為x={x1,x2,…,xj}，該染色體和基因模式Hmg.scheme={z1,z2,…,zj} 通過公式x⊙Hmg.scheme=進行模式學習得到一個新的染色體x.new。設待學習的染色體基因為x=1010110，基因模式Hmg.scheme=1*0100*，則經過學習后的x.new=1001000。

定義6（基因模式的權）對于任意種群Hm都有Hmg.weight表示Hmg.scheme的權值，權值越高，表示Hmg.scheme越“優良”，權值越低，表示Hmg.scheme越“劣質”（計算公式見1.3.8 小節）。

定義7（最優基因模式）對于任意種群Hm，都有Hm.bscheme表示該種群截止到當前代次最“優良”（權最高）的基因模式。

定義8（全局最優模式）在算法進化過程中，截止到當前代次所有種群最優秀（權最高）的基因模式為全局最優模式，全局最優模式用H.bscheme表示。

定義9（公共區域）粗粒度模型[19]的多種群GA需要定期進行數據遷移和交換，本文利用公共區域來接收上述并行機制內各種群共享的基因模式和最優個體。之后，公共區域會比較不同基因模式的優劣程度選出H.bscheme，同時篩選出全局最優個體。此外，公共區域還持續監聽各個種群，將H.bscheme分配給發出群間學習請求的種群。

1.3.2 學習機制操作過程

學習機制包括群內學習（learning within populations，LWP）和群間學習（learning between populations，LBP）兩種學習方式，分別由群內學習算子Pi和群間學習算子Po進行控制。在群內學習方式中，以模式學習作為主要學習操作，在群間學習方式中，以模式學習結合局部搜索策略作為主要學習操作。

（1）群內學習操作過程如下：

①計算種群的He。

②按照個體適應度大小降序選擇r個染色體作為種群優秀個體。

③對優秀個體進行模式抽取得到Hmg.scheme，將得到的Hmg.scheme與該種群的Hm.bscheme的權值進行比較，更新Hm.bscheme。

④Pi控制群內染色體對Hm.bscheme進行學習，并及時更新適應度值與年齡。

⑤若達到規定進行信息遷移的代次，將Hm.bscheme和最優染色體傳遞到公共區域。

⑥公共區域將各種群傳遞過來的Hm.bscheme和最優染色體與已有的H.bscheme和全局最優個體進行比較，并更新H.bscheme和全局最優個體。

（2）群間學習操作過程如下：

①Po判斷種群是否進行群間學習，確定進行群間學習的種群向公共區域發送學習請求。

②公共區域將H.bscheme發送給該種群。

③種群首先淘汰超齡個體，剩存染色體通過結合局部搜索策略的模式學習方法對H.bscheme進行學習，通過局部搜索策略新產生的染色體按適應度大小填補被淘汰超齡個體的空缺，并及時更新適應度值和年齡。

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

1.3.3 學習機制的理論研究

學習機制對種群內優秀個體提取共性基因組成基因模式，控制種群內其他個體對基因模式進行學習來改變自身。這種機制是否有理論上的支持？

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

1.3.4 自適應改變優秀率He的值

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

式中，He1是最小優秀概率，He2是最大優秀概率，g是當前進化代數，G是總進化代數。

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

Fig.3 Adaptive curve of excellent rate values圖3 優秀率自適應曲線

1.3.5 自適應改變群內學習算子Pi的值

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

式中，Pi1是最小群內學習概率；Pi2是最大群內學習概率；g是當前進化代數；G是總進化代數；Hm.ave為種群Hm平均適應度值；Hm.best為種群Hm最優適應度值。

1.3.6 自適應改變群間學習算子Po的值

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

式中,Po1是最小群間學習概率；Po2是最大群間學習概率；g是當前進化代數；G是總進化代數；Hm.old表示種群內超齡個體數目；N表示種群內染色體總數目；max(Hm.ave) 為所有種群中最大平均適應度值；Hm.ave為當前種群平均適應度值；min(Hm.ave)為所有種群中最小平均適應度值。

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

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

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

GA 在迭代進化過程中，總是貪心選擇適應度大的個體，導致GA 容易陷入局部最優，無法收斂到全局最優解。為此，有國內外學者引入梯度法[21]、爬山法[5]、列表尋優法[22]等優化方法作為局部搜索策略，加強GA 的局部搜索能力。本文在前人研究基礎上，提出一種新的局部搜索策略，在染色體對基因模式的確定位進行學習時，該策略能夠對其非確定位進行局部細搜，通過這種局部搜索策略，染色體能夠在允許的鄰域內搜索到適應度更高的個體。

設H.bscheme=10*10*011，待學習的個體為x1=011001011，首先是x1的第一個和第二個基因對H.bscheme的相應位置基因進行學習，x1的第一個和第二個基因位置變為1 和0，當在第三個基因位置碰到H.bscheme的非確定位的時候，通過分裂算子來判定是否進行分裂，確定進行分裂后，以該非確定位基因為核心進行分裂，非確定位基因同時取0、1 兩個基因，并結合之前學習過的基因進行分裂產生兩個新的染色體，分裂后的第一個染色體x2=100001011，第二個染色體x3=101001011，分裂后對父染色體x1的第三個基因位進行取反操作（將0 基因置為1，1 基因置為0），然后父染色體x1繼續進行學習和分裂操作，直至學習到H.bscheme的最后一個基因位。

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

1.3.8 基因模式的權

學習機制通過群內學習和群間學習共同引導種群進化，因此會有概率出現下一代基因模式不如上一代基因模式“優秀”的情況。

本文提出一種評價函數，通過該函數對基因模式進行賦權操作，算法以權值來比較不同基因模式的優劣程度，選出群內最優基因模式Hm.bscheme和全局最優模式H.bscheme。基因模式的權計算公式如下：

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

式中，Hm.best為種群最優秀個體適應度值；fˉ是種群內除Hm.best剩余優秀個體平均適應度值；g是當前進化代數；G是總進化代數。

進化前期，種群平均適應度較低，群內大部分染色體“劣質”基因較多，應當加強群體內最優秀個體引導種群進化方向的力度，減弱其他較差優秀個體的影響，因此在進化前期提高Hm.best的權重，降低fˉ的權重。隨著迭代的進行，種群平均適應度逐漸升高，群體內最優秀個體和其他優秀個體相似度也逐漸變大，考慮到最優秀個體有可能是局部最優解，為了避免種群進化方向被局部最優解錯誤引導，應逐漸降低Hm.best的權重，提高fˉ的權重。

1.4 OWLMGA 算法流程

算法流程如圖5 所示。

算法執行流程如下：

（1）初始化控制參數和公共區域。

（2）多樣本均勻分區種群初始化產生父種群，父種群自我復制生成子種群，子種群部署不同進化策略。

（3）各子種群按自身進化策略獨立計算演化，進行遺傳操作，更新個體適應度和年齡。

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

（4）各子種群將群體內優秀個體傳遞給同父種群實施保存策略的子種群。保存策略子種群對優秀個體進行發掘，保留優秀基因。

（5）對種群進行模式抽取獲得基因模式，同時將基因模式和全局最優個體上傳到公共區域。

（6）種群內個體通過Pi判定是否進行群內學習，否則轉（7）。

（7）各子種群通過Po判定是否進行群間學習，否則轉（8）。

（8）檢查終止條件，滿足轉（9），否則轉（4）。

（9）算法結束。

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

2 仿真研究

2.1 測試函數及對比算法

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

2.2 仿真實驗設置

為公平起見，SMGA、HGA、OWLMGA 均采用相同的參數，PGABL與原文保持一致。以上算法均采用二進制編碼，適應度比例選擇，單點交叉和多基因位變異。算法的控制參數如下：種群數目為4，每個種群染色體規模N均為50，染色體長度為40，算法迭代次數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 代進行一次信息遷移和策略調整。

實驗選取4 個指標評價算法的性能：（1）最優值，該指標反映了算法求解質量的好壞；（2）最優收斂代數，該指標反映了算法求解最優值的速度，收斂代數越少，說明算法求解速度越快；（3）平均收斂代數，該指標是算法多次運行的最優收斂代數的平均值，反映了算法求解最優值的穩定性；（4）收斂次數及收斂率，收斂結果滿足指定收斂精度時則認為收斂成功，收斂次數反映了算法求解最優值的成功率。收斂精度應綜合考量函數維度及不同算法之間的性能來設定，以便更好區分算法之間的優劣。

2.3 仿真實驗結果分析

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

Table 2 Test function表2 測試函數

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

Table 3 Experimental results of function f1 to f6表3 f1～f6 函數實驗結果

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

Table 4 Experimental results of function f7 to f12表4 f7～f12 函數實驗結果

2.4 計算復雜度分析

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

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

Fig.6 Comparison of optimum curves of algorithms圖6 算法尋優曲線對比

3 結論

通過介紹相關研究并結合分析遺傳算法易“早熟”收斂及收斂速度慢等缺點產生的原因，指出現有方法的不足之處及缺陷。本文在前人研究基礎上，秉著充分發揮遺傳算法優點，克服遺傳算法的不足的思路，提出了均勻分區的多種群初始化方法，改進的多種群并行機制及動態控制的學習機制，并融合上述改進形成一種新的混合遺傳算法。

最后實驗結果證明，改進的多種群并行機制和最優權動態控制學習機制天然具有良好的溝通能力，兩種機制結合起來充分發揮了每個機制的優勢，增強了算法的全局搜索能力和局部搜索能力。