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

陳未如， 馬 超， 王翠青

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

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

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

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

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

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

1.1 基本的遺傳算法

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

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

1.2 遺傳算法的并行性分析

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

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

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

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

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

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

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

2 并行遺傳算法的改進(jìn)

遺傳算法是計(jì)算機(jī)科學(xué)與進(jìn)化論相結(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)的并行遺傳算法做了一定的改進(jìn):即主進(jìn)程負(fù)責(zé)對種群適應(yīng)度的計(jì)算、排序和選擇操作;將遺傳操作中的交叉操作和變異操作分配給各子進(jìn)程并行計(jì)算.子進(jìn)程將交叉和變異操作后得到的新個(gè)體再返給主進(jìn)程，直到得到滿足要求的最優(yōu)解或者達(dá)到預(yù)先設(shè)定的最大迭代次數(shù).將此子代種群并行產(chǎn)生過程的遺傳算法稱為并行交變遺傳算法(Parallel Crossover and Mutation Genetic Algorithm)，簡稱PCMGA算法.

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

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

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

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

圖1 MGPGA算法主進(jìn)程流程Fig.1 The Flow of Main Process in MGPGA

圖2 MGPGA算法從進(jìn)程流程Fig.2 The Flow of Secondary Process in MGPGA

從性能上看，算法具體解題時(shí)間計(jì)算如下:

式中，ti，初始化時(shí)間;tc，每個(gè)子代個(gè)體產(chǎn)生的平均時(shí)間，包括相應(yīng)的通信時(shí)間和進(jìn)程同步等待時(shí)間;tm，每個(gè)新個(gè)體插入到種群中的平均時(shí)間;p，從進(jìn)程個(gè)數(shù);m，算法過程產(chǎn)生的新個(gè)體總數(shù).

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

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

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

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

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

3 仿真實(shí)例

3.1 問題描述

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

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

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

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

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

3.3 仿真實(shí)驗(yàn)

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

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

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

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

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

表2 實(shí)驗(yàn)數(shù)據(jù)Table 2 Experimental Data

表3 針對表2實(shí)驗(yàn)數(shù)據(jù)用PCMGA和MGPGA算法進(jìn)程數(shù)P為1、4和9的實(shí)驗(yàn)結(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時(shí)針對E1、E2和 E3中的 CARP問題，用 PCMGA和MGPGA算法求得最優(yōu)解所用的平均時(shí)間.

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

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

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

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

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

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

4 結(jié)語

主要研究了目前遺傳算法的4種不同并行性，比較它們的適用場合;根據(jù)CARP問題的目標(biāo)函數(shù)、適應(yīng)度計(jì)算時(shí)間以及遺傳操作中的交叉和變異計(jì)算時(shí)間長等特點(diǎn)，構(gòu)建了主從并行模型改進(jìn)處理后的遺傳算法，提出了 PCMGA和MGPGA算法，提高了遺傳算法求解速度;在MAENS算法基礎(chǔ)上實(shí)現(xiàn)了PCMGA和MGPGA算法，并將其運(yùn)用到CARP問題求解中.實(shí)驗(yàn)證明:PCMGA和MGPGA算法在整體算法運(yùn)行的平均時(shí)間以及最優(yōu)解上，取得滿意的結(jié)果:在求解精度上與改進(jìn)前算法相當(dāng)，求解速度隨處理器個(gè)數(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］.計(jì)算機(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］ 沈潔陳，李開榮.遺傳算法的并行實(shí)現(xiàn)［J］.揚(yáng)州大學(xué)學(xué)報(bào)(自然科學(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é)報(bào)，2006，21(5):502-507.

［8］ 劉琳，朱征宇，許林，等.求解CARP車場選址問題的混合隨機(jī)搜索算法［J］.計(jì)算機(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ìn)遺傳算法求解［J］.計(jì)算機(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.