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