陳未如， 馬 超， 王翠青

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

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

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

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

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

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

1.1 基本的遺傳算法

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

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

1.2 遺傳算法的并行性分析

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

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

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

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

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

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

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

2 并行遺傳算法的改進

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

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

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

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

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

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

與PCMGA類似，MGPGA算法分主進程和從進程兩部分.從進程的工作與PCMGA算法相同，主進程的工作也與PCMGA類似，所不同的是MGPGA算法中沒有明確的新種群排序、選擇、淘汰過程，每當(dāng)有新的個體產(chǎn)生，立即將之以適當(dāng)?shù)倪m應(yīng)度關(guān)系插入到原種群中并參與新的遺傳，淘汰一個較差的個體.目前常見的并行遺傳算法基本上都是基于1.2節(jié)所述的4種并行機制或其組合來實現(xiàn)的.而混代并行遺傳算法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，每個子代個體產(chǎn)生的平均時間，包括相應(yīng)的通信時間和進程同步等待時間;tm，每個新個體插入到種群中的平均時間;p，從進程個數(shù);m，算法過程產(chǎn)生的新個體總數(shù).

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

與PCMGA算法相比較，MGPGA有以下幾個優(yōu)點:

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

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

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

3 仿真實例

3.1 問題描述

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

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

3.2 數(shù)學(xué)模型

對CARP問題的描述可建立數(shù)學(xué)模型如下:

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

3.3 仿真實驗

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

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

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

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

表1 初始化參數(shù)設(shè)定Table 1 Setting of Initialization parameter

表2 實驗數(shù)據(jù)Table 2 Experimental Data

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

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

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

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

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

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

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

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

4 結(jié)語

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

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

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

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

［4］ 沈潔陳，李開榮.遺傳算法的并行實現(xiàn)［J］.揚州大學(xué)學(xué)報(自然科學(xué)版)，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問題的小環(huán)路啟發(fā)式求解方法［J］.系統(tǒng)工程學(xué)報，2006，21(5):502-507.

［8］ 劉琳，朱征宇，許林，等.求解CARP車場選址問題的混合隨機搜索算法［J］.計算機應(yīng)用，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］陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及應(yīng)用［M］.北京:人民郵電出版社，1996:25-30.

［11］周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京:國防工業(yè)出版社，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］.計算機工程與應(yīng)用，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.