CARP問題混代并行遺傳算法的研究

陳未如， 馬 超， 王翠青

(沈陽化工大學計算機科學與技術學院，遼寧沈陽 110142)

遺傳算法(Genetic Algorithm，GA)最早由美國密歇根大學Holland教授在1975年提出［1］，是在達爾文進化論思想的基礎上開發出的一種模擬自然界生物進化過程來求解優化問題的一類自適應技術.遺傳算法具有應用廣泛、適合于并行化處理等優點.遺傳算法善于全局搜索所有解空間，但存在容易早熟且局部尋優能力不足等缺欠.針對這些缺欠，許多研究者從多個方面開始著手多遺傳算法的改進.

吉根林［2］詳細介紹了遺傳算法的特點和基本原理，并討論了并行遺傳算法和混合遺傳算法以及遺傳算法的性能分析.Mariusz Nowostawski和Riccardo Poli［3］主要介紹了幾種重要的并行算法的分類.沈潔陳和李開榮［4］討論了遺傳算法進行并行處理的主從式并行算法、粗粒度并行算法及細粒度并行算法，分析和比較各種方法的優缺點，介紹了并行遺傳算法的適用范圍和應用前景.

針對CARP問題，目前大多采用啟發式非精確的解法.例如，Golden［5］在1981年提出的增量合并方法;1989年Pearn W L［6］提出的路徑分割方法;2006年但正剛、蔡臨寧、呂新福和鄭力［7］運用小環路啟發式方法求解CARP問題;2010年劉琳、朱征宇、許林和陳飛［8］提出混合隨機搜索算法來求解CARP車場選址問題;Tang K，Mei Y and Yao X［9］等提出了改進的帶有啟發式候選解策略的文化基因算法，即MAENS算法來求解CARP問題等.

本文著重研究了遺傳算法與并行計算，提出PCMGA和MGPGA的并行遺傳算法.通過實驗分析和比較，驗證PCMGA算法和MGPGA算法在并行機中高效的并行計算性能，并把PCMGA算法和MGPGA算法運用到在目前廣泛應用的CARP問題的求解中，取得了令人滿意的求解效率.

1 遺傳算法及其并行性分析

1.1 基本的遺傳算法

生物的遺傳和進化過程主要是通過染色體之間進行交叉和變異來完成，遺傳算法是模擬自然界生物進化過程用于解決最佳化的搜索問題的計算模型，它是自然遺傳學和計算機科學相互結合、相互滲透的新的計算方法［10］.

在遺傳算法中，參與運算的對象是由多個個體組成的一個群體.與自然界中生物的進化過程相似，遺傳算法的運算過程也是反復迭代的過程，首先，進行個體適應度的評價或者計算，從中選出優良個體作為初始種群，記為t，經過選擇、交叉和變異運算后得到新一代種群t+1.這個群體經過不斷的遺傳和進化等操作，并且每次都按照優勝劣汰的原則將適應度值大(適應環境較好)的個體遺傳到下一代，這樣在最終群體中將會得到一個優良的個體X，它即是達到或接近問題的最優解［11］.

1.2 遺傳算法的并行性分析

遺傳算法是借鑒了生物界自然選擇的原理發展起來的具有高度并行、隨機和自適應的搜索算法.近幾年來，對遺傳算法的研究非常廣泛，已被成功應用于經濟管理、交通運輸、工業等不同領域，解決了許多問題，是一種成熟的搜索算法［12］.

當用遺傳算法解決較大規模的實際問題時，需要對大量的個體進行編碼，對個體進行適應度值的計算、選擇、交叉和變異運算，使得算法的進化運算過程進展緩慢，因此，遺傳算法的并行計算問題受到重視，已成為廣大研究者的一個重要研究領域.并行遺傳算法可以從下列4個方面對其進行改進和發展［11］.

(1)適應度評價算法的并行性:由于對初始種群以及每一個新產生的個體都要進行適應度值的計算，并根據適應度的結果進行選擇，因此，在整個遺傳操作中，個體適應度值的計算占用時間較長，如能找到高效并行的適應度計算方法，將能夠提高整個遺傳算法的效率.

(2)個體間適應度評價的并行性:由初始種群生成新個體的過程中，每個個體適應度之間是獨立、無相互依賴的，可將個體適應度的計算在不同處理器或者不同進程之間獨立并行地進行，以加快求解速度.

(3)子代群體產生過程的并行性:父代產生子代的遺傳運算中，與選擇運算相關的是個體適應度值的大小，交叉和變異運算與個體的編碼方式直接相關，因此，可將子代生成過程中的選擇、交叉和變異并行地進行運算，以加快求解過程.

(4)群體分組的并行性:從整個遺傳算法來看，遺傳算法的操作對象是由多個個體所組成的一個群體.可將大的群體分成若干個組，運用遺傳算法在多臺處理器上將各個分組獨立進行遺傳操作，來提高整個進化過程的效率.

傳統遺傳算法的并行性主要從個體適應度評價并行性、整個種群中各個體適應度評價并行性、子代群體產生過程并行性及基于群體分組并行性進行考慮.

2 并行遺傳算法的改進

遺傳算法是計算機科學與進化論相結合的產物，它不僅有包括自組織、自適應和自學習性在內的智能特性，而且還有內在本質的并行特性，這些特性使它具有非常廣泛的應用范圍.在第1.2節所述的遺傳算法并行性研究的基礎上，本文主要研究并提出了PCMGA和MGPGA并行遺傳算法.

2.1 并行交變遺傳算法—PCMGA算法

基于上述子代群體產生過程的并行性，對傳統的并行遺傳算法做了一定的改進:即主進程負責對種群適應度的計算、排序和選擇操作;將遺傳操作中的交叉操作和變異操作分配給各子進程并行計算.子進程將交叉和變異操作后得到的新個體再返給主進程，直到得到滿足要求的最優解或者達到預先設定的最大迭代次數.將此子代種群并行產生過程的遺傳算法稱為并行交變遺傳算法(Parallel Crossover and Mutation Genetic Algorithm)，簡稱PCMGA算法.

PCMGA算法是在傳統遺傳算法的基礎上，將父代群體產生下一代群體所需進行的遺傳運算分解，選擇操作由主進程完成，交叉操作和變異操作由從進程完成.這樣，產生子代群體的選擇、交叉、變異等遺傳操作就可以相互獨立地并行進行，提高了處理器資源的利用率，以達到高速求解CARP問題的目的.

2.2 混代并行遺傳算法—MGPGA算法

在第1.2節所述的4種并行處理方式中，都保留了原始遺傳算法分代的概念.然而在現實世界中，生物在長期的遺傳繁衍過程中，有的進化速度快，有的慢，代與代之間已經沒有明確的界限.本文提出一個新的思路，充分利用遺傳過程的并行性，將該過程交由多個進程同時處理，并將每次遺傳變異所產生的新個體直接插入到已經概率有序的種群中參與遺傳，以加速求解過程，而不是等到整個新生代產生后再形成新的種群.這個思路打破了代與代之間的界限，稱為混代并行遺傳算法MGPGA(Mixed Generation Parallel Genetic Algorithm).

與PCMGA類似，MGPGA算法分主進程和從進程兩部分.從進程的工作與PCMGA算法相同，主進程的工作也與PCMGA類似，所不同的是MGPGA算法中沒有明確的新種群排序、選擇、淘汰過程，每當有新的個體產生，立即將之以適當的適應度關系插入到原種群中并參與新的遺傳，淘汰一個較差的個體.目前常見的并行遺傳算法基本上都是基于1.2節所述的4種并行機制或其組合來實現的.而混代并行遺傳算法MGPGA則是一種新的探索和研究，也是本文研究的重點.MGPGA算法的主進程流程如圖1所示，MGPGA算法的從進程流程如圖2所示.

圖1 MGPGA算法主進程流程Fig.1 The Flow of Main Process in MGPGA

圖2 MGPGA算法從進程流程Fig.2 The Flow of Secondary Process in MGPGA

從性能上看，算法具體解題時間計算如下:

式中，ti，初始化時間;tc，每個子代個體產生的平均時間，包括相應的通信時間和進程同步等待時間;tm，每個新個體插入到種群中的平均時間;p，從進程個數;m，算法過程產生的新個體總數.

從式(1)中可以看出:如果對于給定問題，算法不變，則m基本確定(等于PCMGA算法的n·g)，決定運算時間T的關鍵因素是tc、tm和p.

與PCMGA算法相比較，MGPGA有以下幾個優點:

(1)tm·m 等于 ts·g，但是不能簡單這么計算，因為MGPGA將tm分配每個新個體的產生過程當中，可以充分利用主進程的空閑等待時間，使MGPGA算法CPU利用率提高，從而提高了運算速度;

(2)由于沒有明顯的代劃分，不需要代間同步等待時間，從而減少部分運算時間;

(3)MGPGA使新個體加入遺傳的時間提前.如果按代計算，平均提前n/2個子個體產生時間.而如果不考慮代的劃分，該時間還會提前更多.新個體提前參與遺傳，意味著遺傳速度的提高.雖然有可能產生種群早熟問題，但如果能避免這個問題，將會對遺傳算法的改進和應用起到重要作用.

3 仿真實例

3.1 問題描述

CARP(Capacitated Arc Routing Problem)是車輛帶有容量限制的弧的路徑選擇問題，是Golden等最早提出的，并由他們證明該問題是NP難問題［13］.在我們的日常生活中，CARP 的應用范圍非常廣泛，凡是針對道路進行服務的問題都可以納入其研究范圍，例如:郵件快遞、城市垃圾回收、輸電線檢查、班車路線安排問題等.

CARP問題定義如下［14］:給定帶權強連通有向圖G=(V，A)，其中V和A分別代表圖的頂點集和弧集.頂點集V可以分為兩個集合，Vd={v1，v2，…，vq}和 Vc={vq+1，…，vq+n}，分別代表了q個車場頂點和n個非車場頂點;A={τi|i=1，2，…，m}代表弧集，是由 m 條有向弧構成的集合，其中包含ε條服務弧，τi弧的花費(長度)值為ω(τi)，其中ε條服務弧組成了子集R?A，對于任意弧 τi∈R，其系數 λ 為1，對于任意非服務弧，τi∈A-R，λ的值為0.先假設一個有N車輛的車隊，問題的目標是尋找到K條路徑，每輛車輛從車場 v(x=1，2，…，q)出發，服務完該路徑后再回到原車場，要求需服務弧有且只能屬于一條路徑，且每條路徑服務弧需求的總和部超過服務該路徑的車輛容量C，每條弧只能被一輛車服務，但一輛車可以服務多條路徑，最終使得所有車總花費最小.

3.2 數學模型

對CARP問題的描述可建立數學模型如下:

以上計算公式中，式(2)為目標函數，即使得總的花費最小，式(3)～式(6)為約束條件.其中Ti表示第i條路徑，|Ti|表示該路徑中服務的弧數量.一個可行解包含了K條路徑，分別表示為 T1，T2，…，Tk，K 為所有的路徑總數，Tij表示第i條路徑中第j條服務弧，L(Tij)表示Tij的路徑長度.(3)式表示每一條路徑Ti中的總需求不大于服務該路徑的車輛容量C.(4)式為花費函數，其中路徑Ti的花費為:從停車場σ出發，到第一條服務弧的最短路徑，加上第二條弧的長度，加上第二條弧到第三條弧的最短路徑，一直累加到最后一條弧，然后再加上最后一條弧到車場 σ 的最短路徑.d(Tij，Ti，j+1)表示 Tij的終點到Ti，j+1的起點之間的最短距離，σ表示行駛路徑Ti車輛的停車場.(5)式保證了每條服務弧都被服務，ε為服務弧的總數.(6)式定義了集合Rk，Rk中的元素有第k條路徑中的服務弧組成.任意兩條路徑中不能有重復的服務弧，保證了任意一條服務弧只能被服務一次.

3.3 仿真實驗

CARP問題是一個具有廣泛應用背景與重要理論價值的組合優化難題.實驗采用CARP問題是一個城市垃圾回收問題.在車輛的數量N和容量C有限制的前提下，尋找一個最短路徑使得花費最小，并且能夠把所有垃圾的道路進行清掃.

實驗是在Inter Core i5四核處理器，8.00 GB內存，采用C語言，編譯環境為VS2010，MPI并行環境下實現的.實驗數據來源于Eglese［15］中的3組基于CARP的實例，在表1所示的實驗環境下，在進程數 P 分別為 1、2、3、4、5、6、7、8、9、10的條件下，對3組實驗數據獨立運行30次，實驗的參數設定如表1所示，實驗的數據說明如表2所示，將所得的最優解取30次中的平均值，與文獻［16］中的求解結果進行對比，來驗證PCMGA和MGPGA算法效率.由于篇幅有限，在表3中僅例舉了進程數P為1、4和9時對應的最優解的實驗結果.

其中，表 2中的 vertexNum、ReqEdgeNum、NonReqEdgeNum、vehicle、capacity、best 和MAENS分別代表CARP問題在實驗中的頂點數、有需求的邊、沒有需求的邊、車輛數、車的容量、已知理論上的最優解和運用MAENS算法［9］求得的最優解.

表3中P代表試驗中的進程數，PCMGA、MGPGA和A_TIME分別表示當用P個進程數計算時所求得的最優解以及所求的最優解30次所用的平均時間.

表1 初始化參數設定Table 1 Setting of Initialization parameter

表2 實驗數據Table 2 Experimental Data

表3 針對表2實驗數據用PCMGA和MGPGA算法進程數P為1、4和9的實驗結果Table 3 Experimental Results of Table 2 with process number 1，4 and 9 in PCMGA and MGPGA

以下圖3～圖5為當P等于1～10時針對E1、E2和 E3中的 CARP問題，用 PCMGA和MGPGA算法求得最優解所用的平均時間.

圖3 E1組數據用MGPGA和PCMGA平均時間Fig.3 E1:The average time with MGPGA and PCMGA

PCMGA和MGPGA算法都是基于MPI的主從式并行算法，理論分析可以得出:當系統中進程數為2時，當主進程初始化操作結束后，就將交叉和變異的遺傳操作交給子進程，此時主進程閑置;當子進程遺傳操作結束后，主進程負責處理提交的新個體的排序和選擇操作，此時從進程閑置.因此，P=2時的并行遺傳算法實際上同一時刻還是只有一個進程在單獨操作，并改變原有傳統遺傳算法的基本特點，卻在傳統遺傳算法的基礎上增加了并行程序所需的MPI初始化、進程之間的通信和MPI結束等操作，因此P=2的并行遺傳算法的運行效率明顯會低于P=1的傳統遺傳算法.

當P=4或8時求解CARP問題的平均時間較小.因為實驗環境為四核處理器，當P=4時，為1個主進程3個從進程，資源利用率較高，但是當P=5時，就要有某一個CPU要分給主從兩個進行參與運算，其它從進程運算結束后，與主進程通信的等待時間交叉，因而出現計算時間的高峰.

圖4 E2組數據用MGPGA和PCMGA平均時間Fig.4 E2:The average time with MGPGA and PCMGA

圖5 E3組數據用MGPGA和PCMGA平均時間Fig.5 E3:The average time with MGPGA and PCMG

從以上圖中分析，PCMGA和MGPGA算法都將群體中的個體分布在各個處理器的存儲器中，獨立地對子群體進行遺傳進化操作，所以，能夠有近似線性的加速度比，能夠有效地提高遺傳算法的運行速度.尤為明顯的是MGPGA并行遺傳算法，從進行的實驗可以看到:當MGPGA算法正在運行時，系統CPU的使用率一直都是100%，直到算法結束;而PCMGA算法運行時CPU使用率最高為96% ～99%.以上實驗結果的比較可以看出;PCMGA和MGPGA的并行遺傳方法都有效地提高了遺傳算法的運行速度，MGPGA并行遺傳算法是一種效率極高的并行遺傳算法.

4 結語

主要研究了目前遺傳算法的4種不同并行性，比較它們的適用場合;根據CARP問題的目標函數、適應度計算時間以及遺傳操作中的交叉和變異計算時間長等特點，構建了主從并行模型改進處理后的遺傳算法，提出了 PCMGA和MGPGA算法，提高了遺傳算法求解速度;在MAENS算法基礎上實現了PCMGA和MGPGA算法，并將其運用到CARP問題求解中.實驗證明:PCMGA和MGPGA算法在整體算法運行的平均時間以及最優解上，取得滿意的結果:在求解精度上與改進前算法相當，求解速度隨處理器個數的增加而有所提高，并行效率令人滿意.另外，本文所提出的混代并行遺傳算法MGPGA在提高收斂速度上有很好的效果，較未采用混代技術的并行算法PCMGA的收斂速度有成倍的提高.

［1］ Holland J H.Adaptation in Natural and Artificial Systems［M］.Michigan:University of Michigan press，1975:5-6.

［2］ 吉根林.遺傳算法研究綜述［J］.計算機應用與軟件，2004，21(2):69-73.

［3］ Nowostawski M，Poli R.Parallel Genetic Algorithm Taxonomy［R］.Adelaide，SA:KES’99，1999:88-92.

［4］ 沈潔陳，李開榮.遺傳算法的并行實現［J］.揚州大學學報(自然科學版)，2000，3(2):1-6.

［5］ Golden B L，DeArmon J S，Baker E K.Computational Experiments with Algorithms for a Class of Routing Problems［J］.Computers and Operation Research，1983(10):47-59.

［6］ Pearn W L.Approximate Solutions for the Capacitated Arc Routing Problem［J］.Computers and Operations Research，1989(6):589-600.

［7］ 但正剛，蔡臨寧，呂新福，等.CARP問題的小環路啟發式求解方法［J］.系統工程學報，2006，21(5):502-507.

［8］ 劉琳，朱征宇，許林，等.求解CARP車場選址問題的混合隨機搜索算法［J］.計算機應用，2010，30(6):1508-1512.

［9］ Tang K，Mei Y，Yao X.Memetic Algorithm with Extended Neighborhood Search(MAENS)for Capacitated Arc Routing Problem［J］.IEEE Trans.On Evol.Comput，2009，13(5):1151-1166.

［10］陳國良，王煦法，莊鎮泉，等.遺傳算法及應用［M］.北京:人民郵電出版社，1996:25-30.

［11］周明，孫樹棟.遺傳算法原理及應用［M］.北京:國防工業出版社，1999:65-68.

［12］ Erick Cantu-Paz.A Summary of Research on Parallel Genetic Algorithms［R］.Illinois:IlliGAL，1995.

［13］ Golden B L，Wong R T.Capacitated Arc Routing Problems［J］.Networks，1981，11(3):305-316.

［14］李小花，朱征宇，夏夢霜.多車場CARP問題的改進遺傳算法求解［J］.計算機工程與應用，2009，45(11):230-234.

［15］ Eglese R W.Routing Winter Gritting Vehicles［J］.Discrete Applied Mathematics，1994，48(3):231-244.

［16］ Fu Haobo，Mei Yi，Tang Ke，et al.Evolutionary Computation(CEC)［C］.Barcelona:IEEE，2010:3229-3236.