【正文】 成。若把它們及對它們的進(jìn)化處理分別置于不同的處理機(jī)上，肯定能夠提高運(yùn)行效率。具體的做法是，對群體按照一定的方式進(jìn)行分組，分組后的單個或一組個體的遺傳進(jìn)化過程可以在不同的處理機(jī)上相互獨(dú)立的進(jìn)行。在適當(dāng)?shù)臅r候，各處理機(jī)之間再以適當(dāng)?shù)姆绞浇粨Q一些信息。第四節(jié) 遺傳算法的并行化途徑并行遺傳算法有以下一些模型：一、 步進(jìn)模型該模型的各個子群體中所含個體的數(shù)量多于1，各個子群體在其處理機(jī)上并行獨(dú)立的運(yùn)行遺傳算法，子群體之間的信息交換只能是在物理上的鄰接處理機(jī)之間進(jìn)行。該模型由于對處理機(jī)之間的通信要求不高，所以實(shí)現(xiàn)起來比較簡單。如圖41所示：圖41步進(jìn)模型二、 粗粒度模型也叫島嶼模型。該模型每個處理機(jī)上子群體中所含個體數(shù)量多于1，各個子群體在其各自的處理機(jī)上并行獨(dú)立的運(yùn)行簡單遺傳算法或者混合遺傳算法，并且按照一定的時間間隔、在特定的處理機(jī)之間交換個體信息。：圖42粗粒度模型三、 細(xì)粒度模型也叫鄰接模型。該模型中每個處理機(jī)上值分配一個個體，即子群體只由一個個體組成，每個子群體只和與其海明距離為 1 的“鄰接”子群體相互交換信息。該模型能夠有效的維持群體的多樣性，有效的抑制早熟現(xiàn)象。如圖43所示：圖43細(xì)粒度模型第五節(jié) 并行程序設(shè)計環(huán)境MPICH簡介一、 什么是MPI對MPI的定義是多種多樣的但不外乎下面三個方面它們限定了MPI的內(nèi)涵和外延[7]。 1．MPI是一個庫而不是一門語言許多人認(rèn)為MPI就是一種并行語言這是不準(zhǔn)確的。但是按照并行語言的分類，可以把FORTRAN+MPI或C+MPI 看作是一種在原來串行語言基礎(chǔ)之上擴(kuò)展后得到的并行語言。MPI庫可以被Fortran77/C/Fortran90/C++調(diào)用，從語法上說它遵守所有對庫函數(shù)/過程的調(diào)用規(guī)則，和一般的函數(shù)/過程沒有什么區(qū)別。2．MPI是一種標(biāo)準(zhǔn)或規(guī)范的代表，而不特指某一個對它的具體實(shí)現(xiàn)。迄今為止所有的并行計算機(jī)制造商都提供對MPI的支持，可以在網(wǎng)上免費(fèi)得到MPI在不同并行計算機(jī)上的實(shí)現(xiàn)一個正確的MPI程序，可以不加修改地在所有的并行機(jī)上運(yùn)行。3．MPI是一種消息傳遞編程模型并成為這種編程模型的代表和事實(shí)上的標(biāo)準(zhǔn)。MPI雖然很龐大，但是它的最終目的是服務(wù)于進(jìn)程間通信這一目標(biāo)的。在MPI上很容易移植其它的并行代碼，而且編程者不需要去努力掌握許多其它的全新概念就可以學(xué)習(xí)編寫MPI程序。二、 MPI的語言綁定由于MPI是一個庫而不是一門語言,因此對MPI的使用必須和特定的語言結(jié)合起來。進(jìn)行FORTRAN是科學(xué)與工程計算的領(lǐng)域語言，而C又是目前使用最廣泛的系統(tǒng)和應(yīng)用程序開發(fā)的語言之一，因此對FORTRAN和C的支持是必須的。因此MPI提供了MPI和FORTRAN與C/C++語言的綁定。這樣，我們就可以在用C/C++程序編寫的遺傳算法程序中使用MPI庫函數(shù)，以實(shí)現(xiàn)算法的并行化設(shè)計。三、 MPICHMPICH是一種最重要的MPI實(shí)現(xiàn)。它可以免費(fèi)從。更為重要的是MPICH是一個與MPI1規(guī)范同步發(fā)展的版本。每當(dāng)MPI推出新的版本，就會有相應(yīng)的MPICH的實(shí)現(xiàn)版本。，它支持部分的MPI2的特征。Argonne國家試驗(yàn)室和MSU對MPICH作出了重要的貢獻(xiàn)。第五章 用并行遺傳算法實(shí)現(xiàn)TSP問題 在本章中，將按照第三章介紹的遺傳算法構(gòu)建步驟，逐步設(shè)計并實(shí)現(xiàn)TSP問題，并根據(jù)第五章對遺傳算法并行性的分析，實(shí)現(xiàn)此遺傳算法的并行化改造，使其在MPICH并行環(huán)境下運(yùn)行。最后是搜索性能分析和設(shè)計總結(jié)。第一節(jié) 旅行商問題描述旅行商問題（Travelling Salesman Problem，簡稱TSP，中文又稱貨郎擔(dān)問題）[2]的描述很簡單：【】(旅行商問題)設(shè)G =(V,E)是一個圖，其中V是頂點(diǎn)集，E是邊集。設(shè)是與E相聯(lián)系的距離矩陣。旅行商問題就是要決定一條通過所有頂點(diǎn)且每個頂點(diǎn)只通過一次的最短距離回路，這樣的回路就是哈密爾頓回路。即尋找一條最短的遍歷n個城市的路徑，或者說搜索整數(shù)子集 X ={1,2,…,n}的一個排列，使得 ()取最小值。其中表示城市到的距離 。在一些應(yīng)用中，C也可以解釋為費(fèi)用或旅行時間矩陣。旅行商問題分為兩種類型：一種是對稱問題，即對所有的 i, j∈V ，成立；另一種是非對稱問題，這時，非對稱旅行商問題較難求解。這里我們只討論對稱TSP問題。旅行商問題是一個典型的組合優(yōu)化問題，并且是一個NP難題．其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，因而尋找出其有效的近似求解算法就具有重要的理論意義。另一方面，很多實(shí)際應(yīng)用問題，如印制電路板的鉆孔路線方案、連鎖店的貨物配送路線、輸油管道鋪設(shè)等，經(jīng)過簡化處理后，均可建模為旅行商問題，因而對旅行商問題求解方法的研究也具有重要的應(yīng)用價值。再者，旅行商問題是一種典型的需要使用符號編碼方法的實(shí)際問題，所以，研究求解旅行商問題的遺傳算法，對促進(jìn)遺傳算法本身的發(fā)展也具有重要意義。第二節(jié) 編碼方法與群體初始化一、 編碼最易想到的方法是以遍歷城市的次序排列進(jìn)行編碼。比如碼串12345678表示從城市1開始，依次經(jīng)過城市2，3，4，5，6，7，8，最后返回城市1的遍歷路徑。這是一種針對 TSP 問題的最自然的編碼方式，但與這種編碼方法所對應(yīng)的交叉運(yùn)算和變異運(yùn)算實(shí)現(xiàn)起來比較困難，因?yàn)槌Ｒ?guī)的交叉運(yùn)算和變異運(yùn)算會使群體中產(chǎn)生一些不滿足問題約束條件或無實(shí)際意義的巡回路線。 為克服上面這種巡回路線編碼的缺點(diǎn)，基于各個城市的訪問順序，先驅(qū)Grefenstette等提出了一種新的編碼方法，該方法能夠使任意的基因型個體都能夠?qū)?yīng)一條具有實(shí)際意義的巡回路線。具體操作如下： 對于一個旅行商問題的城市列表W，假定對各個城市的一個訪問順序?yàn)門： ()規(guī)定每訪問完一個城市，就從城市列表W中將該城市去掉，則用第個所訪問的城市在所有未訪問城市列表中的對應(yīng)位置序號就可以表示具體訪問哪個城市，如此這樣直到處理完W中所有的城市。將全部順序排列在一起所得到的一個列表： ()就可以表示一條巡回路線，也就是遺傳算法中一個個體的基因型。 二、 種群初始化種群初始化采用隨機(jī)生成的辦法，產(chǎn)生一組個體（染色體），每個個體由一組符合編碼規(guī)則的數(shù)，即一個列表。這組個體的數(shù)量就是種群規(guī)模。種群規(guī)模越大，個體多樣性越好，陷入局部解危險越小，但計算量越大，計算速度越慢。個體的結(jié)構(gòu)定義如下：struct individual{ int chrom[LENGTH]。 int realchrom[LENGTH]。 double value。}。其中chrom，realchrom分別是個體的編碼和解碼后的真實(shí)路徑，他們都是一個長為城市個數(shù)的整數(shù)序列。Value是計算后得到的路徑總距離。種群定義：struct individual population[PopSize]。初始化種群函數(shù)如下： void GenerateInitialPopulation(void){ int i,j。 srand(time(0))。 for(i=0。 iPopSize。 i++){ for(j=0。 jLENGTH。j++){ population[i].chrom[j]=1+rand()%(LENGTHj)。 } } }第三節(jié) 解碼設(shè)計 在程序設(shè)計中，初始種群個體基因由計算機(jī)隨機(jī)生成，但要計算適應(yīng)度值就必須通過真實(shí)路徑序列計算總路程長度，所以在采用這種編碼方法后，關(guān)鍵是設(shè)計解碼方法。 通過分析編碼方法，可以使用鏈表：typedef struct pointlist{ int point。 struct pointlist *next。}PointList。實(shí)現(xiàn)譯碼操作。下面是具體譯碼函數(shù)DecodeChromosome：void DecodeChromosome(int seq){ //seq: the sequence number of in the population PointList *T,*temp。 int x。 T=creat()。 for(int i=0。iLENGTH。i++){ x=population[seq].chrom[i]。 if(x==1){ x=Tpoint。 temp=T。 T=Tnext。 delete temp。 } else if(x1) {coutx。} else{ x=ListDelete(T,x)。 } population[seq].realchrom[i]=x。 } }由creat()函數(shù)構(gòu)建一個point值從1到LENGT的鏈表，然后由個體的每一個基因依次代入解碼函數(shù)中x, 找到對應(yīng)的真實(shí)值，賦給對應(yīng)的realchrom，然后用ListDelete()函數(shù)刪除此鏈表項(xiàng)。直到個體轉(zhuǎn)換完畢，鏈表也刪除完畢。Creat()函數(shù)和ListDelete()函數(shù)如下：PointList *creat(void){ PointList *p= new PointList。 ppoint=ind。 ind++。 if(indLENGTH+1){ pnext=creat()。 }else{ pnext=NULL。 ind=1。 } return p。}int ListDelete(PointList *p,int i){ PointList *q。 int x。 while((pnext)amp。amp。(i2)){ p=pnext。 i。 } if((!(pnext))||i2) { couterror。 exit(8)。 } q=pnext。 pnext=qnext。 x=qpoint。 delete q。 return x。}第四節(jié) 個體適應(yīng)度評價方法設(shè)計適應(yīng)度函數(shù)通常取路徑長度T的倒數(shù)，即 f =1/T 。這是因?yàn)槲覀円骉的最小值，而T又是正實(shí)數(shù)。但結(jié)合具體問題，會有一些調(diào)整。在這里T可能是一個很大的實(shí)數(shù)，這會使f值太小而失真，所以根據(jù)適應(yīng)度尺度變換的線性定標(biāo)原理，將適應(yīng)度函數(shù)調(diào)整為f = LENGHT/T，在比例選擇算子下可以提高個體適應(yīng)度的評價的準(zhǔn)確性。第五節(jié) 遺傳算子設(shè)計遺傳算子設(shè)計是以生成下一代個體為目的的，包括選擇算子設(shè)計，交叉算子設(shè)計，變異算子設(shè)計。對于旅行商問題，使用由Grefenstette等所提出的編碼方法來表示個體時，個體基因型和個體表現(xiàn)型之間具有一一對應(yīng)的關(guān)系，特別是它使得經(jīng)過遺傳運(yùn)算后所得到的任意的一個基因型個體都能夠?qū)?yīng)于一條具有實(shí)際意義的巡回路線。這樣．就可以用基本遺傳算法來求解旅行商問題。而無需重新去開發(fā)一些位置重排序方面的遺傳算子。這時，交叉運(yùn)算可以使用通常的單點(diǎn)交叉算子或多點(diǎn)交叉算子；變異運(yùn)算也可使用常規(guī)的一些變異算子。只是基因(i=1，2，3，…，n)所對應(yīng)的等位基因值應(yīng)從{1，2，3，…，ni+l}中選取。一、 選擇算子設(shè)計 選擇算子是用于選擇適應(yīng)度優(yōu)良個體參與生成下一代，淘汰適應(yīng)度差的個體的算子。是體現(xiàn)遺傳算法優(yōu)剩劣汰的重要算子。選擇算子有很多方法，在TSP問題中，選擇算子仍使用前面用到的比例選擇算子，其實(shí)現(xiàn)方法并沒有什么不同。這體現(xiàn)了遺傳算法的通用性。請參見第三章。二、 交叉算子設(shè)計 在TSP問題中，如果不采用Grefenstette等提出的編碼方法表示個體，而采用城市的直接編碼來表示，那么交叉算子設(shè)計將是個相當(dāng)復(fù)雜的工作，也有很多種方法可供選擇和研究，例如：部分映射交叉PMX、順序交叉OX、巡環(huán)交叉CX、邊重組交叉EX等等。而Grefenstette等提出的編碼方法使得TSP問題可以使用簡單遺傳算法的單點(diǎn)或雙點(diǎn)交叉來實(shí)現(xiàn)交叉操作。具體操作請參見第三章。三、 變異算子設(shè)計在第三章的例子中使用的是二進(jìn)制編碼的方法。其中變異算子的作用就是在變異概率內(nèi)將個體某位的編碼由1變?yōu)?，或者由0變?yōu)?。可見變異算子的設(shè)計是與編碼的表示有直接的相關(guān)。在TSP問題中，根據(jù)使用的編碼方案，要使變異后的個體仍然是一個有意義的巡回路線，那么變異應(yīng)該遵循一些準(zhǔn)則。只要對于基因(i=1，2，3，…，n)所對應(yīng)的等位基因值應(yīng)從{1，2，3，…，ni+l}中選取，即，就可以保證變異所獲得的序列是有意義的個體。例如：對變異前的編碼是44121，城市序列為 45132的個體的第二位進(jìn)行變異，則變異后的編碼可能為4312421241121，它們解碼后的城市序列分別為4315421541253。可見變異后仍為有意義的完整序列。其源碼如下：void MutationOperator(void){ int i, j。 double p。 /*bit mutation*/ srand(time(0))。 for(i=0。 iPopSize。i++){ for(j=0。 jLENGTH。j++){ p=rand()%1000/。 if(pPm){ int x。 x=rand()%(population[i].chrom[j])+1。 population[i].chrom[j]=x。 } } } }第六節(jié) 程序的并行化改造一、 算法描述并行算法采用粗顆粒模型（見第四章）。并行環(huán)境是：硬件由各個節(jié)點(diǎn)即個人電腦組成的局域網(wǎng)。軟件環(huán)境是：windows2000/xp下實(shí)現(xiàn)的MPI環(huán)境。并行算法偽碼為：PGASTART 并行環(huán)境初始話； 分配一定的內(nèi)存空間接收其他節(jié)點(diǎn)傳過來的中間結(jié)果；