【正文】 。amp。 ind++。 delete temp。 int x。 jLENGTH。其中chrom，realchrom分別是個體的編碼和解碼后的真實路徑，他們都是一個長為城市個數(shù)的整數(shù)序列。將全部順序排列在一起所得到的一個列表： ()就可以表示一條巡回路線，也就是遺傳算法中一個個體的基因型。旅行商問題是一個典型的組合優(yōu)化問題，并且是一個NP難題．其可能的路徑數(shù)目與城市數(shù)目n是成指數(shù)型增長的，所以一般很難精確地求出其最優(yōu)解，因而尋找出其有效的近似求解算法就具有重要的理論意義。第一節(jié) 旅行商問題描述旅行商問題（Travelling Salesman Problem，簡稱TSP，中文又稱貨郎擔(dān)問題）[2]的描述很簡單：【】(旅行商問題)設(shè)G =(V,E)是一個圖，其中V是頂點集，E是邊集。三、 MPICHMPICH是一種最重要的MPI實現(xiàn)。迄今為止所有的并行計算機(jī)制造商都提供對MPI的支持，可以在網(wǎng)上免費(fèi)得到MPI在不同并行計算機(jī)上的實現(xiàn)一個正確的MPI程序，可以不加修改地在所有的并行機(jī)上運(yùn)行。：圖42粗粒度模型三、 細(xì)粒度模型也叫鄰接模型。也就是說，同一個遺傳算法應(yīng)該可以同時處理多組群體，這些多組群體可看作是由一個大的群體劃分而成。對于基本遺傳算法的運(yùn)行過程，為實現(xiàn)其并行化的要求，可以從四種并行性方面對其進(jìn)行改造:一、 個體適應(yīng)度評價的并行性個體適應(yīng)度的評價或計算在遺傳算法的運(yùn)行過程中占用運(yùn)行時間比較長。第二節(jié) 遺傳算法在并行實現(xiàn)上的困難雖然遺傳算法無論是從直觀上還是從理論上來看都具備并行性，其實標(biāo)準(zhǔn)遺傳算法的并行化并不是想象中那么手到擒來，也會遇到通信量過大的困難。圖中橫軸表示進(jìn)化代數(shù)，縱軸表示適應(yīng)度(也是目標(biāo)函數(shù)值)，圖中的兩條曲線分別為各代群體中個體適應(yīng)度的最大值和平均值。 if(pPm){ population[i].chrom[j]=(population[i].chrom[j]==39。 population[index[i+1]].chrom[j]=ch。 } /*onepoint crossover operation*/ for(i=0。 iPopSize。iPopSize。i++){ cfitness[i]=cfitness[i1]+cfitness[i]。 /*calculate relative fitness*/ for(i=0。 }else{ temp=。 x1=*temp1/。由式(26)可知，Rosenbrock函數(shù)的值域總是非負(fù)的。 char *pointer。139。 randomize()。即式()： Max 第三步：確定編碼方法。 第七步：確定遺傳算法的有關(guān)運(yùn)行參數(shù)，即確定出遺傳算法的M、T、pc、pm等參數(shù)。 圖31 基本遺傳算法框圖第二節(jié) 遺傳算法的構(gòu)造步驟 遺傳算法提供一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架．它不依賴于問題的領(lǐng)域和種類。前者測量收斂性，后者測量動態(tài)性能。當(dāng)遺傳算法通過交叉算子已接近最優(yōu)解臨近值時，利用變異算子的這種局部隨機(jī)搜索能力可以加速向最優(yōu)解收斂。3．交叉算子與遺傳算法的收斂型 遺傳算法的收斂性不僅取決于編碼，初始化群體，適應(yīng)度函數(shù)，選擇算子的設(shè)計，而且還取決于交叉算子和下面要提到的變異算子。也就是說，交叉算子設(shè)計和編碼設(shè)計需協(xié)調(diào)操作。 另外，最佳個體保存方法還可加以推廣，即在每一代的進(jìn)化過程中保留多個最優(yōu)個體不參加交叉、變異等遺傳操作，而直接將它們復(fù)制到下一代群體中。它也叫賭輪（roulette wheel）或蒙特卡羅（Monte Carlo）選擇[1]。在遺傳進(jìn)化的初期，通常出現(xiàn)一些超常的個體，這些異常個體有可能在群體中占據(jù)很大的比例，因而可能導(dǎo)致未成熟收斂現(xiàn)象。即使某一問題可自然的表示成求最大值形式，也不能保證對于所有的 x,使 f(x)取非負(fù)值。另外，群體規(guī)模的確定受遺傳操作中選擇操作的影響很大。符號編碼方法是指個體染色體編碼串的基因值取自一個無數(shù)值含義而只有代碼含義的符號集。假設(shè)某一參數(shù)的取值范圍是[A,B], AB。當(dāng) 1時，模式H 在變異算子作用下的生存概率為： =(1－)O(H) ≈1－*O(H) (） 綜上所述，模式H 在遺傳算子選擇、交叉和變異的共同作用下，其子代的樣本數(shù)為 () 由上式，就可以得到模式定理： 【】（模式定理） 在遺傳算子選擇，交叉和變異的作用下，具有低階、短的定義長度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按指數(shù)級增長。令群體平均適應(yīng)度為則有 () 可見，模式的增長（減少），即樣本數(shù)的增加（減少），依賴于模式的平均適應(yīng)度與群體平均適應(yīng)度之筆：那些平均適應(yīng)度高于群體平均適應(yīng)度的模式將在下一代中得以增長；而那些平均適應(yīng)度低于群體平均適應(yīng)度的模式將在下一代中減少?！尽磕Ｊ紿 中第一個確定位置和最后一個確定位置之間的距離稱作該模式的定義距離或定義長度[5]，記作δ(H)。因此通過分析模式在遺傳操作下的變化，就可以了解什么性質(zhì)被延續(xù)，什么性質(zhì)被丟棄，從而把握遺傳算法的實質(zhì)，這正是模式定理所要揭示的內(nèi)容。現(xiàn)在增加一個通配符“*” ，“*”既可以被當(dāng)作“0”，又可以被當(dāng)作“1”。9．機(jī)器學(xué)習(xí)學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所應(yīng)具備的能力之一、基于遺傳算法的機(jī)器學(xué)習(xí)．特別是分類器系統(tǒng)，在許多領(lǐng)域得到了應(yīng)用。遺傳算法在圖像處理中的優(yōu)化計算方面是完全勝任的。因此，目前在現(xiàn)實生產(chǎn)中也主要靠一些經(jīng)驗進(jìn)行調(diào)度，遺傳算法已成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)。使用這種搜索方式，雖然每次只執(zhí)行與種群規(guī)模n成比例的計算，但實質(zhì)上已進(jìn)行了大約次有效搜索．這就使遺傳算法能以較少的計算獲得較大的收益。通常，適應(yīng)度大的個體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)再通過基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代．進(jìn)化算法的這種自組織、自適應(yīng)特征，使它同時具有能根據(jù)環(huán)境變化來自動發(fā)現(xiàn)環(huán)境的特性和規(guī)律的能力 自然選擇消除了算法設(shè)計過程中的一個最大障礙，即需要事先描述問題的全部特點．并要說明針對問題的不同特點算法應(yīng)采取的措施。 ●Pm：變異概率，～?！褡儺愃阕幼儺惒僮魇前次贿M(jìn)行的，即把某一位的內(nèi)容進(jìn)行變異。這一操作是借用了達(dá)爾文適者生存的進(jìn)化原則。對問題最優(yōu)解的搜索是通過對染色體 X 的搜索過程來進(jìn)行的。遺傳算法是一種群體型操作，該操作以群體中的所有個體為對象。第二節(jié) 遺傳算法簡介遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式構(gòu)造的一類優(yōu)化搜索算法，是對生物進(jìn)化過程進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計算的最重要的形式。雖然這種變化的概率是可以預(yù)測的，但是具體哪一個個體發(fā)生變化卻是偶然的。有性生殖生物在繁殖下一代時，兩個同源染色體之間通過交叉（Crossover）而重組，即在兩個染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合而形成兩個新的染色體。細(xì)胞通過分裂具有自我復(fù)制的能力，在細(xì)胞分裂的過程中，其遺傳基因也同時被復(fù)制到下一代，從而其性狀也被下一代所繼承。關(guān)鍵字：遺傳算法 并行遺傳算法 TSP問題The Design and Parallel Realization of Genetic AlgorithmAbstractGenetic Algorithm is the putation model which simulating the biological evolution process of Darwin’s heredity choice and the natural selection. Although the traditional genetic algorithm has the concealment parallelism, but realized the method in essentially still was actually serial. When this kind of serial genetic algorithm solves some actual problems, it will need lots of individuals and putations, and this will causes the evolution process to be so slow that difficult to meets the realtime requirements. Therefore, the Parallel Genetic Algorithm has received a big value, and already bees the main topic at genetic algorithm research. With the PGA, you can unites the parallel machine’s high speed with genetic algorithm’s inherent parallelism. The present paper designed and has realized simple heredity algorithm (GA), and parallel genetic algorithm (PGA) with two examples. Including:1. Rosenbrock function.2. TSP problem.Keywords: Genetic Algorithm GA Parallel Genetic Algorithm PGA TSP目錄畢業(yè)設(shè)計（論文）任務(wù)書 I摘要 VAbstract VI第一章 遺傳算法簡介 1第一節(jié) 遺傳算法的生物學(xué)基礎(chǔ) 1一、 遺傳和變異 1二、 進(jìn)化 1三、 遺傳與進(jìn)化的系統(tǒng)觀 2第二節(jié) 遺傳算法簡介 2第三節(jié) 遺傳算法的特點 4第四節(jié) 遺傳算法的應(yīng)用情況 5第二章 遺傳算法的基本原理和實現(xiàn)技術(shù) 7第一節(jié) 模式定理（schemata theorem） 7一、 模式 7二、 模式定理 7第二節(jié) 編碼方法 9一、 編碼概念 9二、 編碼技術(shù) 9第三節(jié) 群體設(shè)定 10第四節(jié) 適應(yīng)度函數(shù) 11一、 目標(biāo)函數(shù)到適應(yīng)度函數(shù)的映射 11二、適應(yīng)度尺度變換（適應(yīng)度函數(shù)定標(biāo)） 11第五節(jié) 遺傳操作 12一、選擇算子 12二、交叉算子 12三、變異算子 13第六節(jié) 遺傳算法的性能分析 13一、在線性性能評估 14二、離線性能評估 14第三章 遺傳算法的求解構(gòu)造步驟及應(yīng)用舉例 15第一節(jié) 遺傳算法的求解步驟 15一、遺傳算法的偽碼描述和形式化定義 15二、遺傳算法的求解步驟及其框圖 16第二節(jié) 遺傳算法的構(gòu)造步驟 18第三節(jié) 基本遺傳算法在函數(shù)優(yōu)化中的應(yīng)用舉例 19第四章 并行遺傳算法 25第一節(jié) 遺傳算法并行化的目的 25第二節(jié) 遺傳算法在并行實現(xiàn)上的困難 25第三節(jié) 遺傳算法的并行性分析 25一、 個體適應(yīng)度評價的并行性 26二、 群體中各個個體適應(yīng)度評價的并行性 26三、 子代群體產(chǎn)生過程的并行 26四、 基于群體分組的并行性 26第四節(jié) 遺傳算法的并行化途徑 26一、 步進(jìn)模型 26二、 粗粒度模型 27三、 細(xì)粒度模型 27第五節(jié) 并行程序設(shè)計環(huán)境MPICH簡介 28一、 什么是MPI 28二、 MPI的語言綁定 28三、 MPICH 29第五章 用并行遺傳算法實現(xiàn)TSP問題 30第一節(jié) 旅行商問題描述 30第二節(jié) 編碼方法與群體初始化 30一、 編碼 30二、 種群初始化 31第三節(jié) 解碼設(shè)計 32第四節(jié) 個體適應(yīng)度評價方法設(shè)計 33第五節(jié) 遺傳算子設(shè)計 33一、 選擇算子設(shè)計 33二、 交叉算子設(shè)計 34三、 變異算子設(shè)計 34第六節(jié) 程序的并行化改造 35一、 算法描述 35二、 并行化的實現(xiàn) 35第七節(jié) 運(yùn)行參數(shù)的確定和實驗結(jié)果分析 36一、 運(yùn)行參數(shù)的確定 36二、實驗結(jié)果及分析 40結(jié)論 43參考文獻(xiàn) 44致謝 45英文翻譯 46英文原文 46中文翻譯 55附錄 65附錄1 求解Rosenbrock函數(shù)最大值源碼 65附錄2 TSP問題源碼 73第一章 遺傳算法簡介第一節(jié) 遺傳算法的生物學(xué)基礎(chǔ)生物在自然界中生存繁衍，顯示出其對自然環(huán)境的自適應(yīng)能力。遺傳算法設(shè)計及其并行實現(xiàn)摘要遺傳算法（Genetic Algorithm——GA），是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計算模型。2. TSP問題。遺傳信息是由基因（Gene）組成的，生物的各種性狀由其相應(yīng)的基因所控制，基因是遺傳的基本單位。一個細(xì)胞核中所有染色體所攜帶的遺傳信息的全體稱為一個基因組（Genome）細(xì)胞在分列時，遺傳物質(zhì)DNA通過復(fù)制（Reproduction）