并行化遺傳算法研究綜述

馮智莉 易國洪,2 李普山 黎慧源 代 瑜

1(武漢工程大學計算機科學與工程學院 湖北 武漢 430205)2(武漢工程大學智能機器人湖北省重點實驗室 湖北 武漢 430205)

0 引 言

人工智能領域中，一個非常關鍵的問題是需要在非常龐大并且十分復雜的解空間中找到最優解或者是近似最優解。對這種NP-hard問題[1]，不恰當的搜索方法可能會出現組合爆炸的問題[2]，因此找到一個通用的搜索算法一直都受到相關領域研究人員的關注。

最優化問題一般可以分成兩類：組合優化問題和函數優化問題[3]。其中：函數優化問題即連續變量的優化問題，目標對象是指定區間的所有變量；而組合優化的目標對象則是在無限集中某一個符合要求的目標答案，如旅行商問題[4]TSP 。目前對于函數優化問題常見的解決策略是精確算法和智能優化算法。精確算法包括:整數規劃[6]、動態規劃[7]、線性規劃算法[5]和分支定界[8-9]等，這些時間復雜性較大，適合用于小規模問題。智能優化算法主要包括文獻[10]在1953年提出的模擬退火算法、文獻[11]于1973年提出的遺傳算法GA、文獻[12-14]于1986年提出的禁忌算法、文獻[15]于1992年提出的蟻群算法和文獻[16]以革新的方式使用神經網絡方法。其中，以遺傳算法、模擬退火算法等為代表的指導性搜索法，以貪心算法[17]等算法為代表的局部搜索法，均借鑒了一些自然現象，以及人的思維活動來指導搜索活動的展開。遺傳算法優勢在于：可以快速地將解空間中的全體解搜索出，全局搜索能力優秀[18]，克服了其他算法的快速下降陷阱問題；適合分布式計算，天然并行性加快了收斂速度。但是相對的，遺傳算法局部搜索能力不足，簡單遺傳算法耗時長，在進化后期搜索效率較低[19]，所以存在一定的早熟收斂的風險。遺傳算法的難點是采用何種選擇方法，在充分保留好的個體的同時，又要維持群體的多樣性。

1 基本概念和主要環節討論

遺傳算法是諸多進化算法中的一種。模擬了自然界中生物自然淘汰的進化過程，學習不僅可以通過單個生物個體的適應來完成，還可以通過種群的進化來實現，并將其運用到計算機模型之中[20]。Darwin 進化論中適者生存的原理認為，每一代種群最終都會越來越適應環境。每一個個體都會繼承但不完全繼承父輩的特性，自身會隨機的產生一些新特性，只有高度適應環境的個體才能被保留下來。遺傳算法從代表問題中生成一個或多個初代解集(種群)，解集中的解又被稱之為個體，個體本質上是帶有特征的實體，經過基因編碼來實現。經過適應函數篩選的個體形成的新的種群，遺傳算法不斷地評價每一個個體，保證更適應環境的個體擁有更多的繁殖機會。遺傳算法放棄了梯度信息，重視的是種群之間的搜索策略，以及個體信息在種群內的交換，克服了傳統搜索算法難以解決非線性復雜問題的缺點，具有適合并行處理、魯棒性強、簡單通用、搜索能力強和運用范圍廣的特點[20]。目前已經廣泛地運用在自適應控制、機器學習、組合優化、人工生命等領域。

在遺傳算法中，問題的解(表現型)所組成的群體(種群)會朝著更加適應環境的方向變化。每個候選解都有一組屬性(個體染色的編碼信息)，屬性會根據一定的比例或者規則被突變和切割連接。完整的進化通常從隨機生成的個體群體開始，是一個迭代過程，每個迭代中的群體稱為一代。每一代都要用適應度函數(通常是目標函數)來衡量篩選更適應環境的個體；從經過選擇的個體中對其基因組進行修飾(重組并且可能隨機突變)，將獲得的新的個體組成新的一代；在種群成熟之前，算法會不斷地迭代，并可能使用不同的候選解決方案。通常情況下，經過數代進化工作，該算法終止時，基本可以得到令人滿意水平的個體。

基本遺傳算法的形式描述如算法1所示。

算法1遺傳算法

1: 初始化一個解集，并評估每個個體的適應度

2: Repeat

3: 通過適應度函數篩選出部分個體

4: 按照“適應度越高，被選中的可能性越高”的原則，以一定的比例選擇部分個體進行雜交，產生子代

5: 按照一定比例選擇部分個體進行變異操作

6: until 新種群產生

2 遺傳算法并行化策略

當問題的規模和復雜程度不斷增加以后，遺傳算法收斂到全局最優所花費的時間也更長。遺傳算法具備天然的并行性，并且并行機目前也比較普及，為遺傳算法的并行化奠定了基礎。常見的并行化策略主要有以下幾點：

(1) 適應度評價函數 個體適應度評價需要占用一定的時間，提升計算個體適應度的效率，可以通過研究并行化遺傳算法的適應函數，找到并行計算個體適應度函數的恰當表達方式，可以有效地提升遺傳算法的選擇效率。該方法依賴于數值的開發成果和并行化研究。

(2) 產生新種群 前文已經提到遺傳算法中個體的選擇是同時完成的，不同個體的適應度相互獨立的，彼此之間互不影響。在適應度函數評價個體的時候可以采用并行化策略，因此，計算個體適應度可以分發給不同的機器上完成。同理，簡單遺傳算法的交叉、變異過程都可以實現并行化。

(3) 種群分組 前面的方法主要還是根據遺傳算法本身的特點進行改進。需要注意的是：可以將一個遺傳算法用在多個種群上，例如可以將遺傳算法放在集群環境中，同時處理多個種群。將種群分組則對簡單遺傳算法的結構進行改進，在并行機上實現起來相對來說也更加簡單。

2.1 四種基本模型

運用分而治之的思想，文獻[21]最早在大型的并行計算機上應用并行遺傳算法PGAs(Parallel Ge-netic Algorithms)。同時分而治之的思想有多種實現途徑，目前并行化遺傳算法主要有4類模型：主從模型、孤島模型、鄰域模型、混合模型。

(1) 主從模型 主從模型易于實現，是遺傳算法的直接并行化方案之一。僅有一個種群，種群的選擇交叉變異等操作都在主節點機上完成，適應度的評價在從節點機完成。從節點接收主節點發送過來的個體，主節點獲得從節點計算的個體適應度值。文獻[22]設計了基于MPI的可重用的主從式PGAs框架；文獻[23]將主從PGAs運用到模糊關聯規則的挖掘算法，加速性能比提升了19.1%。

當模型需要大量的計算適應度的工作的時候就可以采用這種并行化方案，但是也存在著主節點和從節點之間通信延遲或者瓶頸問題，負荷不均勻的問題等，導致并行失效。

(2) 孤島模型 孤島模型又被稱為分布式模型或者粗粒度模型，這種模型適合如Transputer的多處理機系統的MMD機器或者是集群環境。先依照節點機的個數分布成多個種群(或者是子群體)，子群體在自己所在的節點機上運行GA，在經歷一定的進化代數(進化時間)以后，子群體交換部分個體，豐富了子群體的多樣性，降低了未成熟就收斂的可能。目前孤島模型的研究熱點主要是確定遷移規模、遷移拓撲以及遷移策略問題。文獻[24]將粗粒度并行遺傳算法與動態規劃相結合，孤島模型的加速比提升，且通信開銷較小。文獻[25]將遺傳規劃算法與粗粒度并行遺傳算法結合，并用語言數據實驗證明新算法的預測誤差更低。

(3) 鄰域模型 鄰域模型，或稱細粒度模型，常用于連接機或者是多處理器系統陣列式SIMD系統的機器。該模型對于每個個體都在所在的處理機或者是鄰域處理機上完成，幾乎沒有全局操作，充分展現了遺傳算法的特性。鄰域模型中的每一個處理機都只分配一個個體，將一個個體視為一個子群體，子群體只和鄰接子群體交換信息。在文獻[26]中提出了基于GPU的細粒度并行化遺傳算法，提升了算法的運行速度。文獻[27]提出了細粒度模型在Hadoop的MapReduce上并行編程求解最短路徑，取得了優于經典遺傳算法的效果。

鄰域模型的關鍵是采用什么樣的鄰域結構，因為鄰域結構極大地影響了個體在種群當中的傳播路徑以及個體的空間位置。目前采用什么樣的鄰域拓撲最優尚無權威說法。根據Shapiro B的理論，在海明距離r>2的時候，效果較差，并且通過對r內所有鄰域實驗后發現4鄰域模型比8鄰域模型效果更好。

(4) 混合模型 近幾年來出現了較多的混合模型，主要是將前三種基本模型進行整合形成新的層次結構。例如混合模型中有：細粒度-粗粒度模型、粗粒度粗粒度模型以及粗粒度-主從式模型，上層模型將下層并行結構模型視為一個種群，下層模型中的子群體則是真實的子群體(種群)。一般來說下層模型中內部信息交換量比較大。文獻[28]提出了一種分層遺傳算法解決了作業車間調度問題。

以上的模型根據其自身的特點來說，各有優劣。主從模型適合計算時間主要在評估適應度環節的問題，使用范圍有限。細粒度模型對處理機的要求比較高，目前就適用于小范圍直徑還是大規模鄰域尚有爭議。粗粒度模型的通信開銷小，加速比呈線性，因此使用范圍比較廣，適合在通信帶寬低的集群環境上運行，不過，目前對采用什么樣的遷移策略和遷移規模來說仍然有待進一步的研究。混合模型因為其具有較好的并行性，是當前研究的主流模型，在混合模型當中，粗粒度-主從式模型運用效果較好[29]。

常見的實現并行化遺傳算法的并行機主要有多數據流、多指令流的MIMD機器，粗粒度的并行計算機，多數據流、單指令流的SIMD機器，細粒度的并行計算機等，還可以在局域網環境或者是集群環境下實現并行算法。需要根據具體的實現方法來選用不同的硬件環境。

2.2 并行化性能評估標準

加速比是評級多核架構性能的主要參數。加速比是串行和并行時間的耗時比。例如并行耗時5.9單位，串行耗時95.1單位，那么加速比即為16.12。依據多核處理器加速比已有的研究，現在對并行化遺傳算法的評價模型進行介紹。

2.2.1 固定任務模型

評價并行化遺傳算法的性能的指標有很多，其中最常見的就是Amdahl定律中的加速比。

原始的加速比的原理如下：假設有p個并行機，可以組成一個性能更高的并行化運行平臺。單個計算節點的運算速度(即性能)為1，p個計算節點所創建的結構的串行性能為pref(p)。已知加速比為串行運行時間與并行運行時間之比，即：

(1)

式中：T1是串行計算所需的時間；Tp是該算法在p個處理機組成的并行機上的運行時間；Sp即為加速比。

假設問題為w，單個計算節點執行任務的時間即為：

并行化運行平臺的基本執行時間為：

(2)

(3)

令perf(p)=c,c為常數，則有：

(4)

式(4)在c=1的時候就是大型機之父的理論解析式，系統功效提高的程度和總執行時間以及執行方式有關：

(5)

f是并行處理部分在整個系統中的占比；對應的，(1-f)就是串行處理的部分在整個系統中的占比。m是并行處理機的數量，Speedup即為加速比。固定模型的三維圖解變化趨勢如圖1所示。

圖1 固定任務模型加速比變化趨勢圖

該定律主要適用于負載固定的情況，例如在主從式模型中可以得到幾乎呈線性的加速比；而在孤島模型當中，當群體規模恒定，子群體的規模與數量不成正比的時候，其加速與主從式模型加速比相同。目前該定律在鄰域模型中運用的較少[29]。

2.2.2 固定時間模型

文獻[30]于1988年提出了Gustafson定律。

假設原始任務為w,比例擴增任務為w′，在同等的時間內，p核并行和串行完成的任務相同，則有：

w′=(1-f)w+fmw

(6)

那么：

(7)

固定時間的三維模型圖解變化趨勢如圖2所示。

圖2 固定時間模型加速比變化趨勢圖

2.2.3 其他模型

文獻[31-32]結合實際問題給出了其他兩種評價指標：(1) 改進了Amadahl定律的加速比，先確定一個適應度指標，當個體適應度高于此指標的時候，穿行計算的時間與并行計算的時間之比為加速比。(2) 計算并行運算和串行運算獲得個體的最高適應度的差值大小。

另外還可以設計多個指標，例如增加平均進化代數、平均計算時間等因素，設計成具有不同集合特點的測試函數來比較不同模型之間的優劣。

3 遺傳算法的研究和未來發展方向

本文重點考察了近五年國內外工程技術人員以及相關領域研究者在遺傳算法方面的研究情況，數據來自2013年-2017年已發表在核心期刊上的“工業技術類”有關遺傳算法的研究。圖3是遺傳算法在包含函數優化、生產調度、自動控制、圖像處理、人工智能、遺傳編程、數據挖掘、機器學習以及遺傳算法綜述以內10個方向的應用，圖4是遺傳算法在編碼策略、遺傳算子、物種多樣性、測試函數、收斂性、欺騙問題和綜述等7個方面文獻的統計結構。

圖3 2013年-2017年遺傳算法應用領域分布柱形圖

圖4 2013年-2017年遺傳算法研究領域分布柱形圖

根據圖3、圖4可以得到如下結論：

就應用領域而言，遺傳算法的主要應用方向集中在機器人學、數據挖掘和機器學習方面。在生產調度中的應用基本呈現出逐年增加的趨勢。

就研究方向而言，遺傳算法研究的熱門在遺傳算子、測試函數、收斂性和編碼策略上。相比而言，在物種多樣性和欺騙問題上研究成果不多，有待更深層次的研究。

整體而言，2016年以前遺傳算法領域的研究持平，說明遺傳算法仍然是機器學習領域和數據挖掘領域的研究關鍵點。加上真正有效的成果在總體的研究成果中占比較少，因此遺傳算法仍然是一個值得進行深入研究的領域。

遺傳算法具有魯棒性強的特點，即可以用一個通用的框架來系統的解決優化問題，目前已經取得了較多的成果。在研究應用方向層面，函數優化是評價遺傳算法的基本算例，多樣化的測試函數有助于體現算法的性能和效果。文獻[33]提出了一些多極值并具有最優點的函數。對于如背包問題、布局優化、旅行商問題、圖形劃分等NP-hard問題，解空間急劇上升，已經不能用枚舉法或是暴力求解法解決問題。文獻[34-36]成功地將遺傳算法運用到求解TSP問題上，文獻[37-39]分別將遺傳算法運用到了排課問題、車間作業調度問題上。在自動控制方面，文獻[40]用遺傳算法優化了航空控制系統，文獻[41]利用遺傳算法對模糊控制器進行了優化。在機器人方面，遺傳算法也被廣泛的運用，例如文獻[42]將遺傳算法運用到機器人移動的路徑規劃。圖像處理對降低圖像分割、掃描等操作的誤差有一定的要求，因此可以用遺傳算法進行優化計算。文獻[43-45]分別將遺傳算法運用到漢字識別、圖像恢復和圖像邊緣特征提取上。在機器學習領域，遺傳算法可以通過學習模糊控制規則來改進模糊系統的功能，文獻[46-47]已經將遺傳算法用來調整CNN的連接權，以達到優化CNN結構的效果。另外數據挖掘問題也可以轉換成最優解的搜索問題，數據庫就是搜索空間，遺傳算法隨機產生一組規則，當不斷進化的規則可以全面覆蓋數據庫的時候則進化完成[46]。文獻[48]中已經開發出相應的數據挖掘工具，主要是基于遺傳算法的思想，對失事飛機的數據進行數據挖掘，結果證明這種方法十分有效。

在研究領域，編碼方式是遺傳算法的關鍵之一，遺傳算法之父Holland建議用二進制。文獻[49]提出了多目的進程調度二進制編碼方式，強調識別關鍵產品、單位、任務，僅將少部分變量進行二進制編碼。文獻[50]提出混沌gary編碼方式，對于多參數的優化問題來說實數編碼的效果更好。文獻[51]針對實數編碼僅適用于連續變量問題，提出了將混沌變異與映射到量子位的實數染色體交叉的編碼方式。文獻[52]為了減低早熟的概率，將復數的思想運用到遺傳算法的編碼方式中。文獻[53]提出了基于動態相似度的零件族編碼，優化了遺傳算法的收斂時間和編碼長度。

遺傳算法的關鍵主要在于交叉、選擇、變異算子的設計。文獻[54]提出了局部搜索能力納入選擇算子，提升了算法在不可能解的領域找到可行解的幾率。文獻[55]設計了一種局部競爭選擇算子，為避免陷于局部最優的問題，通過強調個體差異保證了種群的多樣性。文獻[56]將模擬退火算法運用到選擇算子中，提升了算法的穩定性。文獻[57]提出了拉普拉斯交叉算子，達到實現遺傳算法穩定高效的搜索的效果。文獻[58]通過高斯分布概率調整了實數編碼的交叉算子。文獻[59]提出了單親遺傳算子，確保最終一定找到可行解。文獻[60]提出了功率變異算子。文獻[61]設計了定向編譯算子，提升了交互遺傳算法的性能。文獻[62]提出了貪婪子循環算子，提升了遺傳算法在TSP問題中的性能。

遺傳算法中涉及到位串、交叉概率、變異概率和群體規模等參數的設計。文獻[63]設計了一套模糊規則，在線動態地改變交叉概率和變異概率。文獻[64]則用條件發生器來產生交叉和變異概率，具備一定的穩定傾向性和隨機性。文獻[65]通過大量實驗提出了針對調度問題的最佳遺傳算法參數。文獻[66]針對遺傳算法存在的早熟問題，提出了遺傳優勢原則，讓交叉概率和編譯概率自適應的改變。

收斂性是優化問題的重要考核指標，目前主要是運用Markov鏈來證明遺傳算法的全局收斂性。文獻[67]闡明了遺傳算法收斂性的定義，并提出了新算法解決多峰值優化過早收斂問題。文獻[68]運用齊次Markov鏈證明了當保留了上一代最優個體的經典遺傳算法可以收斂到全局最優。文獻[69]闡明了遺傳算法出現早熟問題的原因，提出了新的遺傳算法收斂理論。

建筑塊理論認為在遺傳過程中低階短距、適應度高的模式將會以指數級別增長，并轉變成高階長距、適應值高的模式。但受到“欺騙條件”的影響，最終可能會形成非最優模式，導致問題最終無法收斂到全局最優解，這就是欺騙問題。文獻[70]給出了模式欺騙和遺傳算法欺騙問題的定義，并討論了欺騙問題和收斂性和并行性的問題。文獻[67]提出了解決連續性欺騙問題的定向變異算子。文獻[71]計算了部分領域的遺傳算法解決完全欺騙問題的所需的平均值時間。

4 結 語

遺傳算法為解決復雜優化問題提供了通用模板，是近些年進化算法研究的熱點之一。同時統計數據還表明遺傳算法已經漸漸走向了應用，目前已經較為廣泛地運用在數據挖掘的技術中，改進也是當前遺傳算法的研究熱點。縱觀遺傳算法的研究方向可以發現，主要仍集中于機器學習和數據挖掘等方面，并呈現出逐年增加的趨勢，但是在機器學習領域實際應用成果方面并不豐富。因此還存在進一步的發展空間，在欺騙問題等理論問題研究方面尚有欠缺。整體來看遺傳算法還有相當的發展空間，未來發展主要集中在以下幾個方面：

1) 遺傳算法未來會在并行化方面進一步發展。目前數據挖掘的運用較多，并行化遺傳算法能夠顯著地提升運算速度，有較高的應用價值。

2) 遺傳算法目前在欺騙問題、參數設定等理論性研究方面尚顯不足。這限制了遺傳算法更深層次的發展，因此未來遺傳算法的研究重點可能會更多的出現在理論方面，建立起相應的數學基礎。

3) 遺傳算法會與其他技術進一步融合。因為遺傳算法的局部搜索能力較弱，存在著早熟收斂的風險，需要和其他能夠快速局部收斂算法相結合才能實現更有效的收斂策略，這需要大量的實驗和理論研究來實現。

4) 算法的早熟機理、參數設置的理論指導、收斂速度等理論研究可能會成為后進的研究熱點。這些理論將指導算法發展的方向，目前還有很多不足，因此仍然有發展的空間。

5) 并行化理論研究方面未來會更加深入。遺傳算子之間相互獨立，個體與個體之間的適應度選擇過程也都相互獨立，具備并行化的天然優勢。設計對應的并行策略和并行遺傳算子，建立相應的數學基礎，尤其是在數據挖掘領域，顯得十分必要。