【正文】 關(guān)于遺傳算法研究的內(nèi)容調(diào)研設(shè)計(jì)畢業(yè)論文目 錄摘　要 IAbstract II第一章 遺傳算法概論 1 遺傳算法的產(chǎn)生和國(guó)內(nèi)外研究現(xiàn)狀 1 遺傳算法的基本原理 2 3 4 6第二章　基本遺傳算法 7 基本遺傳算法簡(jiǎn)介 7 基本遺傳算法描述 7 基本遺傳算法的實(shí)現(xiàn) 10第三章　遺傳算法求解TSP 15 旅行商問(wèn)題概述 15 使用改進(jìn)的遺傳算法求解TSP 16第四章　求解TSP的實(shí)驗(yàn)結(jié)果及分析 26 26 26 27 28第五章　總　　結(jié) 30參考文獻(xiàn) 32附錄1　改良遺傳算法求解TSP Java源程序 33附錄2　英文文獻(xiàn)翻譯 50致　謝 56 I 第一章 遺傳算法概論 遺傳算法的產(chǎn)生和國(guó)內(nèi)外研究現(xiàn)狀 遺傳算法（Genetic Algorithm簡(jiǎn)稱(chēng)GA）美國(guó)的J. Holland教授于1975年在他的專(zhuān)著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的，它是一類(lèi)借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法[1] 。 遺傳算法模擬自然選擇和自然遺傳過(guò)程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體（優(yōu)勝劣汰），利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過(guò)程，直到滿足某種收斂指標(biāo)為止。最后一代候選解群中的最優(yōu)解就是所求得的最優(yōu)解。（Adjacency based crossover），這個(gè)算子是特別針對(duì)用序號(hào)表示基因的個(gè)體的交叉，并將其應(yīng)用到了（旅行商）TSP問(wèn)題中，通過(guò)實(shí)驗(yàn)對(duì)其進(jìn)行了驗(yàn)證。（Stochastic Iterated Genetic Hillclimbing，SIGH）采用了一種復(fù)雜的概率選舉機(jī)制，此機(jī)制中由m個(gè)“投票者”來(lái)共同決定新個(gè)體的值（m表示群體的大?。?。實(shí)驗(yàn)結(jié)果表明，SIGH與單點(diǎn)交叉、均勻交叉的神經(jīng)遺傳算法相比，所測(cè)試的六個(gè)函數(shù)中有四個(gè)表現(xiàn)出更好的性能，而且總體來(lái)講，SIGH比現(xiàn)存的許多算法在求解速度方面更有競(jìng)爭(zhēng)力[2]。（simplex method）結(jié)合起來(lái)，形成了一種叫單一操作的多親交叉算子（simplex crossover），該算子在根據(jù)兩個(gè)母體以及一個(gè)額外的個(gè)體產(chǎn)生新個(gè)體，事實(shí)上他的交叉結(jié)果與對(duì)三個(gè)個(gè)體用選舉交叉產(chǎn)生的結(jié)果一致。同時(shí)，文獻(xiàn)還將三者交叉算子與點(diǎn)交叉、均勻交叉做了比較，結(jié)果表明，三者交叉算子比其余兩個(gè)有更好的性能。國(guó)內(nèi)也有不少的專(zhuān)家和學(xué)者對(duì)遺傳算法的交叉算子進(jìn)行改進(jìn)。2002年，戴曉明等應(yīng)用多種群遺傳并行進(jìn)化的思想，對(duì)不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來(lái)搜索變量空間，并利用種群間遷移算子來(lái)進(jìn)行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)值問(wèn)題2004年，趙宏立等針對(duì)簡(jiǎn)單遺傳算法在較大規(guī)模組合優(yōu)化問(wèn)題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Buildingblock Coded Parallel GA，BCPGA）。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識(shí)別出可能的基因塊，然后用基因塊作為新的基因單位對(duì)染色體重新編碼，產(chǎn)生長(zhǎng)度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。2005年，江雷等針對(duì)并行遺傳算法求解TSP，探討了使用彈性策略來(lái)維持群體的多樣性，使得算法跨過(guò)局部收斂的障礙，向全局最優(yōu)解方向進(jìn)化。 遺傳算法的基本原理由于遺傳算法的研究與應(yīng)用尚在不斷發(fā)展之中，有關(guān)術(shù)語(yǔ)的運(yùn)用尚未完全取得統(tǒng)一。為了在下面的研究中做到準(zhǔn)確、清晰、規(guī)范的描述，對(duì)本文使用到的遺傳算法術(shù)語(yǔ)解釋如下[3]：個(gè)體(individual)：遺傳算法中處理的基本對(duì)象、數(shù)據(jù)結(jié)構(gòu)，對(duì)應(yīng)于自然遺傳學(xué)中的生物個(gè)體。種群( population)：個(gè)體的集合，對(duì)應(yīng)于自然遺傳學(xué)中的生物種群。種群大小( population size)：種群中個(gè)體數(shù)目稱(chēng)為種群大小。位串( bit string)：也叫染色體（chromosome），個(gè)體特征的表現(xiàn)形式，對(duì)應(yīng)于自然遺傳學(xué)中的染色體?；? gene)：位串中的元素，表示不同的特征，對(duì)應(yīng)于生物學(xué)中的遺傳物質(zhì)單位，以DNA序列形式把遺傳信息譯成編碼?；蛭? locus)：某一基因在位串（染色體）中的位置適應(yīng)度(fitness)：某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度，或者在環(huán)境壓力下的生存能力，取決于遺傳特性。適應(yīng)度函數(shù)（fitness function）：為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)，適應(yīng)度函數(shù)是計(jì)算個(gè)體在種群中被使用的概率。遺傳操作（genetic operator）：遺傳算法中有三種關(guān)于染色體的運(yùn)算：選擇、交叉和變異，這三種運(yùn)算被稱(chēng)為遺傳操作。選擇（selection）操作：選擇（selection）操作是模擬生物界優(yōu)勝劣汰的自然選擇法則，從種群中選擇適應(yīng)度較好（較好可能是高于種群的平均適應(yīng)度也可能是低于種群的平均適應(yīng)度，取決于要解決的問(wèn)題和使用什么作為適應(yīng)度）的個(gè)體來(lái)生成下一代種群進(jìn)行交叉變異。交叉(crossover)操作：交叉就是互換兩個(gè)染色體某些位上的基因以產(chǎn)生新的個(gè)體，普通遺傳算法中常用的交叉算子有單切點(diǎn)交叉、雙切點(diǎn)交叉、循環(huán)交叉。變異(mutation)操作：位串中的基因發(fā)生變化，發(fā)生在同一個(gè)個(gè)體之內(nèi)，常見(jiàn)的變異有交換（兩個(gè)基因交換位置）、倒序（位串上的某一段基因位置反轉(zhuǎn)）、插入（位串上的某一個(gè)基因被插入到位串中的其它位置）。交叉率：發(fā)生交叉運(yùn)算的個(gè)體個(gè)數(shù)占全體個(gè)體總數(shù)的比例，~。變異率：發(fā)生變異的基因位數(shù)所占全體個(gè)體的基因總位數(shù)的比例，~。遺傳算法是一類(lèi)借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)化搜索算法。在遺傳算法中問(wèn)題的解被表示成“染色體”，在算法中也即是以二進(jìn)制編碼或?qū)崝?shù)編碼的串[4]。并且，在執(zhí)行遺傳算法之前，隨機(jī)給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問(wèn)題的“環(huán)境”中，設(shè)定相應(yīng)的適應(yīng)度函數(shù)，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過(guò)交叉，變異過(guò)程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體” 群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，得到問(wèn)題的最優(yōu)解或者近似最優(yōu)解。遺傳算法的處理對(duì)象不是參數(shù)（優(yōu)化問(wèn)題的參變量）本身，而是對(duì)參數(shù)集進(jìn)行了編碼的個(gè)體。這種編碼操作，使得遺傳算法可直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作（所謂結(jié)構(gòu)對(duì)象泛指集合、序列、矩陣、樹(shù)、圖、鏈和表等各種一維或高維結(jié)構(gòu)形式）。這一特點(diǎn)使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域，例如：通過(guò)對(duì)連接矩陣的操作，遺傳算法可用來(lái)對(duì)神經(jīng)網(wǎng)絡(luò)或自動(dòng)機(jī)的結(jié)構(gòu)或參數(shù)加以優(yōu)化。通過(guò)對(duì)集合的操作，遺傳算法可實(shí)現(xiàn)對(duì)規(guī)則集合或知識(shí)庫(kù)的精練而達(dá)到高質(zhì)量的機(jī)器學(xué)習(xí)目的[5]。通過(guò)對(duì)樹(shù)結(jié)構(gòu)的操作，遺傳算法可得到用于分類(lèi)的最佳結(jié)構(gòu)樹(shù)。通過(guò)對(duì)任務(wù)序列的操作，遺傳算法可用于任務(wù)規(guī)劃，而通過(guò)對(duì)操作序列的處理，遺傳算法可自動(dòng)構(gòu)造順序控制系統(tǒng)。 遺傳算法的基本作用對(duì)象是多個(gè)可行解的集合，而非單個(gè)可行解。它是采用同時(shí)處理群體中多個(gè)個(gè)體的方法，即同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估。這一特點(diǎn)使遺傳算法具有較好的全局搜索性能，減少了陷于局部?jī)?yōu)解的可能性。同時(shí)這又使得遺傳算法本身具有良好的并行性。遺傳算法僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體，而無(wú)須搜索空間的知識(shí)或其它輔助信息。遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。對(duì)適應(yīng)度函數(shù)的唯一要求是，對(duì)于輸入可計(jì)算出能夠進(jìn)行比較的輸出。遺傳算法的這一特點(diǎn)使它的應(yīng)用范圍極大拓寬，使之可廣泛應(yīng)用于目標(biāo)函數(shù)不可微、不連續(xù)、非規(guī)劃、極其復(fù)雜或無(wú)解析表達(dá)式等類(lèi)優(yōu)化問(wèn)題。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)它的搜索方向。遺傳算法執(zhí)行選擇、交叉、變異等類(lèi)似生物進(jìn)化過(guò)程的簡(jiǎn)單隨機(jī)操作，具有極強(qiáng)的魯棒性。需要指出，遺傳算法采用概率僅僅是作為一種工具來(lái)引導(dǎo)其搜索過(guò)程朝著搜索空間的更優(yōu)的解的區(qū)域移動(dòng)。因此盡管看起來(lái)它是一種盲目的搜索方法，但實(shí)際上有明確的搜索方向。 遺傳算法由于具有魯棒性強(qiáng)，實(shí)現(xiàn)簡(jiǎn)單，對(duì)問(wèn)題依賴(lài)性小等優(yōu)點(diǎn)，為求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題提供了通用框架，下面是一些主要應(yīng)用領(lǐng)域：（1）函數(shù)優(yōu)化：是GA的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)GA進(jìn)行性能評(píng)價(jià)的常用算例，對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問(wèn)題，用其他優(yōu)化方法較難求解，GA卻可以得到較好的結(jié)果。（2）組合優(yōu)化[6]：隨問(wèn)題規(guī)模的擴(kuò)大，搜索空間急劇擴(kuò)大，對(duì)這類(lèi)復(fù)雜問(wèn)題，實(shí)踐證明，GA對(duì)于組合優(yōu)化的NP完全問(wèn)題非常有效。例如求解TSP。（3）生產(chǎn)調(diào)度問(wèn)題：GA已成為解決復(fù)雜調(diào)度問(wèn)題的有效工具，在單件生產(chǎn)車(chē)間調(diào)度、流水線生產(chǎn)車(chē)間調(diào)度、生產(chǎn)規(guī)模、人物分配等方面都得到了有效的應(yīng)用。（4）自動(dòng)控制：GA在自動(dòng)控制領(lǐng)域中的應(yīng)用日益增加，并顯示了良好的效果。如在參數(shù)辨識(shí)、人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和權(quán)值學(xué)習(xí)，都顯示了GA的應(yīng)用優(yōu)勢(shì)。（5）機(jī)器人智能控制：GA是源自于對(duì)人工自適應(yīng)系統(tǒng)的研究，已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)律、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動(dòng)協(xié)調(diào)等方面得到研究和應(yīng)用。（6）圖像處理和模式識(shí)別：在圖像處理過(guò)程中，如掃描、特征提取、圖像分割等不可避免的會(huì)產(chǎn)生一些誤差。目前，GA已在圖像恢復(fù)、圖像邊緣特征提取、幾何形狀識(shí)別等方面得到了應(yīng)用。（7）人工生命[7]：基于GA的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面得到應(yīng)用。（8）遺傳程序設(shè)計(jì)：Koza發(fā)展了遺傳程序設(shè)計(jì)，基本思想是：采用樹(shù)型結(jié)構(gòu)表示計(jì)算機(jī)程序，運(yùn)用遺傳算法的思想，通過(guò)自動(dòng)生成計(jì)算機(jī)程序來(lái)解決問(wèn)題。雖然該理論尚未成熟，應(yīng)用也有些限制，但已成功地應(yīng)用于人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域。（9）機(jī)器學(xué)習(xí)：基于GA的機(jī)器學(xué)習(xí)、特別分類(lèi)器系統(tǒng)，在調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán)、神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化設(shè)計(jì)、和多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。（10）生物信息學(xué)：多重序列比對(duì)是生物信息學(xué)的重要研究?jī)?nèi)容，它的目標(biāo)是通過(guò)同時(shí)比較多個(gè)序列，發(fā)現(xiàn)它們之間的相似區(qū)域和保守性位點(diǎn), 進(jìn)而推斷未知生物分子的結(jié)構(gòu)和功能， 或者重構(gòu)系統(tǒng)發(fā)育樹(shù)，尋找物種之間的進(jìn)化關(guān)系[8]。遺傳算法也是一種啟發(fā)式算法，它由于能夠避免算法陷入局部最優(yōu)解而受到人們的重視，在生物序列多重比對(duì)中也有一定的應(yīng)用[9]。旅行商問(wèn)題（Traveling Saleman Problem，TSP）又譯為旅行推銷(xiāo)員問(wèn)題、貨郎擔(dān)問(wèn)題，簡(jiǎn)稱(chēng)為T(mén)SP，是最基本的路線問(wèn)題，該問(wèn)題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過(guò)所有給定的需求點(diǎn)之后，最后再回到原點(diǎn)的最小路徑成本。最早的旅行商問(wèn)題的數(shù)學(xué)規(guī)劃是由Dantzig（1959）等人提出[10]。顧名思義，旅行商問(wèn)題就是有一個(gè)推銷(xiāo)員，要到n個(gè)城市推銷(xiāo)商品，最后再回到出發(fā)點(diǎn)，為了節(jié)約時(shí)間和成本，他想找出一個(gè)包含所有n個(gè)城市并且總路徑（包括回到出發(fā)點(diǎn)）最短的環(huán)路。進(jìn)行本課題研究是想通過(guò)學(xué)習(xí)遺傳算法的理論基礎(chǔ)，實(shí)現(xiàn)和優(yōu)化技術(shù)來(lái)掌握一種實(shí)現(xiàn)計(jì)算機(jī)模擬自然的智能優(yōu)化算法。研究的內(nèi)容包括：遺傳算法的發(fā)展歷史、研究現(xiàn)狀、基本原理、基本實(shí)現(xiàn)技術(shù)及應(yīng)用前景。擬解決的問(wèn)題主要有： 使用基本遺傳算法求解旅行商問(wèn)題（TSP）。 在基本遺傳算法基礎(chǔ)上，對(duì)算法加以改進(jìn)，加快算法的收斂速度和提高解的質(zhì)量。 嘗試多種改進(jìn)方法，分析不同的改進(jìn)策略對(duì)算法的收斂速度和解的質(zhì)量的影響。第二章　基本遺傳算法 基本遺傳算法簡(jiǎn)介基于對(duì)自然界中生物遺傳與進(jìn)化機(jī)理的模仿，針對(duì)不同的問(wèn)題，很多學(xué)者設(shè)計(jì)了許多不同的編碼方法來(lái)表示問(wèn)題的可行解，開(kāi)發(fā)出來(lái)許多種不同的遺傳算子來(lái)模仿不同環(huán)境下的生物遺傳特性。這樣，由不同的編碼方法和不同的遺傳算子就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法都有共同的特點(diǎn)，即通過(guò)對(duì)生物遺傳和進(jìn)化過(guò)程中的選擇、交叉、變異機(jī)理的模仿，來(lái)完成對(duì)問(wèn)題最優(yōu)解的自適應(yīng)搜索過(guò)程?；谶@個(gè)共同特點(diǎn)，Goldberg總結(jié)出了一種統(tǒng)一的最基本的遺傳算法——基本遺傳算法（Simple Genetic Algorithms，簡(jiǎn)稱(chēng)SGA）。基本遺傳算法只使用選擇算子、交叉算子和變異算子這三種基本遺傳算子，其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，是其他一些遺傳算法的（皺）行和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值[11]。 基本遺傳算法描述基本遺傳算法可定義為一個(gè)8元組：SGA=（C,E,P0,M,O,R,W,T） (21)式中：C ——個(gè)體的編碼方法；E——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；P0——初始種群；M——種群大??；O——選擇算子；R——交叉算子；W——變異算子；T——算法終止條件； 圖 21 SGA流程圖基本遺傳算法(SGA)流程如下：（1） 隨機(jī)初始化種群（2） 計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度（3）根據(jù)個(gè)體的適應(yīng)度選擇優(yōu)良的個(gè)體保留下來(lái)，作為下一代種群，并保持種群大小不變（使用優(yōu)良個(gè)體的位串覆蓋被淘汰被的個(gè)體的位串）。（4）對(duì)種群中的個(gè)體進(jìn)行隨機(jī)兩兩配對(duì)（若種群大小為M，則有M/2對(duì)），然后根據(jù)交叉概率從配對(duì)的個(gè)體中選出一部分執(zhí)行交叉操作。（5）根據(jù)變異概率從種群中選出一部分個(gè)體執(zhí)行變異操作（6）若沒(méi)有達(dá)到算法終止條件（比如達(dá)到最大迭代次數(shù)或者種群的多樣性降低到一定程度）則跳轉(zhuǎn)到第2步，繼續(xù)執(zhí)行下面操作，否則跳轉(zhuǎn)到第7步（7）輸出最優(yōu)解或者近似最優(yōu)解SGA算法偽代碼如下：Procedure SGAbegin //算法開(kāi)始 initialize P(0) //初始化種群 t=0。 //當(dāng)前迭代次數(shù)小于預(yù)設(shè)的最大迭代次數(shù)時(shí)，循環(huán)做下面的遺傳操作 while(t=T)do for i=1 to M do //計(jì)算第t代種群中各個(gè)個(gè)體的適應(yīng)度 Evaluate fitness of P(t)。 end for for i=1 to M do //執(zhí)行選擇算子//選擇當(dāng)前種群中的優(yōu)良個(gè)體并復(fù)制到下一