【正文】 將每個基因都作為潛在的交叉點，首先隨機地產生兩個與個體染色體等長的掩碼樣本，根據掩碼樣本確定兩個子個體。圖五 雙點交叉多點交叉是雙點交叉的推廣，首先隨機選擇介于之間的多個不重復的交叉點，間序地交換兩個父個體之間的基因。圖四 單點交叉（2）雙點交叉與多點交叉雙點交叉是指隨機選擇兩個介于之間的交叉點，然后交換兩個父染色體位于兩個交叉點之間的基因段，從而形成兩個子染色體。（1）單點交叉單點交叉是指在兩個父染色體上隨機選擇一個介于之間的交叉點，是染色體的長度，交換兩個父染色體位于交叉點之后的基因段。遺傳算法強調交叉的作用，可行解的進化主要靠選擇機制和交叉策略來完成。圖三 隨機遍歷抽樣法 交叉算子遺傳算法中的交叉操作是指兩個相互配對的父個體按照某種方式交換部分基因，從而形成兩個子個體的過程，用映射形式表示為父個體空間到子個體空間的映射，表示父個體空間，由一對父個體組成，表示子個體空間。圖二 輪盤賭選擇法（2）隨機遍歷抽樣法 假設需要選擇個個體，隨機遍歷抽樣法是根據累積適應度選擇指針等距離地移動來選擇個個體，選擇指針移動的距離為，初始指針的位置由之間的隨機數確定，選擇指針從初始指針開始依次選擇個個體。在選擇時首先產生一個的隨機數，然后與累積概率比較，若，則選中第個個體。（1）輪盤賭選擇法輪盤賭選擇法是一種最簡單的選擇方法。基于排序的適應度分配是按照適應度進行排序，僅按照個體在群體中的序位進行選擇。按比例的適應度分配是以各個個體的適應度與總適應度的比例作為選擇概率決定個體的生存可能性。選擇操作在種群中選擇個體時需要以適應度作為選擇標準，然后以一定的選擇概率進行選擇操作?，F在還有很多新型的遺傳算子，如顯性操作算子、倒位算子等。在實際應用中可以根據具體問題靈活定義適應度函數。一般情況下適應度函數由目標函數變換得到。適應度是衡量種群中個體優(yōu)劣的重要指標，如果該個體在種群中的適應度越高，則它適應環(huán)境的能力就越強，那么遺傳到下一代的概率也就越大。假如對4個城市的一條路線為，那么染色體編碼串為或者。 符號編碼法符號編碼法是指將個體編碼串的基因值用一些無數值含義只有代碼含義的符號集表示的方法，符號集的元素可以是字母、數字或者代碼等。例如基因： 其中每個變量的區(qū)間為，那么目標問題有4個決策變量，的表現型為。 浮點數編碼法二進制編碼在將連續(xù)函數離散化時存在映射誤差，所以提出了浮點數編碼法。假設某一個個體的編碼為，其中，則對應的解碼公式為。問題所要求的精度決定了串的長度。 二進制編碼法 二進制編碼是最基本的編碼方法，編碼符號集是由0和1組成的二值符號集{0，1}。在對實際問題進行編碼時我們應根據問題的不同情況選擇不同的編碼方法。編碼是把一個問題的可行解從其解空間轉化到遺傳算法所能處理的搜索空間的一種轉化方法，編碼同時決定了解碼，好的編碼方法直接影響算法的執(zhí)行效率。 遺傳算法的實現 編碼遺傳算法的一個重要特點就是在算法的運行過程中不對所求問題的實際決策變量直接進行操作，而是對表示可行解的個體基因型的編碼進行遺傳操作。（3）遺傳算法直接使用由目標函數變換得到的適應度函數作為搜索標準，就可以確定進一步的搜索方向和搜索范圍，不需要目標函數的導數等輔助信息，這給很多目標函數無法求導或很難求導的、或導數不存在的函數優(yōu)化問題，以及組合優(yōu)化問題帶來了方便。遺傳算法同時使用一個群體中多個個體的搜索信息開始最優(yōu)解的搜索，而不是從一個單一的個體開始搜索，經過對群體的選擇、交叉、變異操作后，產生出新的群體，這樣群體中包含了更多的群體信息，這是遺傳算法的內含并行性。隨著進化過程的進行，新的群體中總會產生出許多優(yōu)良的個體。在應用遺傳算法時給定了編碼方法、適應度函數以及遺傳算子后，算法將利用進化過程中獲取的信息自行組織搜索。個體P(0)代累積適應度選擇次數選擇結果配對情況112011055/285/281011013203001199/281/21001132310111313/2827/282101124401000111/28101011交叉點交叉結果變異點變異結果P(1)代13：201111111111113310102111011103224：3001130001000101101141010101022表一 手工進行的遺傳算法示意表 遺傳算法的特點相對于其他優(yōu)化算法，遺傳算法有下列一些特點。算法終止條件是到最大進化代數為止。在執(zhí)行選擇操作時運用輪盤賭選擇法，比例度量以個體適應度與總適應度的比值，高適應度的個體遺傳到下一代的幾率大。編碼時對目標函數的兩個未知量分別用二位二進制數編碼，則整個染色體的長度是4，初始種群P(0)代用隨機方法產生，由于問題域以及采用二進制編碼，因此隨機產生的初始種群不會脫離約束范圍，即產生的個體均為合法個體。以二元函數為例。圖一是遺傳算法的流程圖，通過流程圖我們可以了解遺傳算法的執(zhí)行過程。因為算法是在計算機上執(zhí)行的，而計算機要求一定的精度，因此目標函數的最優(yōu)解無法達到理論上的數值，而是一個接近最優(yōu)解的近似值，所以確定終止代數是必要的，最后逐個解碼個體并輸出適應度最大的個體的表現型，即為滿意解。 遺傳算法的運算過程遺傳算法是通過模仿生物學中遺傳和進化的機理完成對問題域中最優(yōu)解的搜索。積木塊假設：積木塊在遺傳算子的作用下相互結合能生成高階、長定義距、高平均適應度的模式，可最終生成全局最優(yōu)解。我們把低階、短定義距以及高適應度的模式叫做積木塊。比如編碼為0***10****1*表示的模式，它的階為4，定義距為10。例如二進制編碼中字符集為，*是通配符，可以是0或1，0***10****1*則表示一種模式。模式是一個描述字符串集的模板，該字符串集中串的某些位置上存在相似性。遺傳算法是一個迭代求解的過程，首先初始化當前種群，然后從當前種群中按照某種機制選擇適量個體進行遺傳操作，在產生新一代種群后找到當前種群中的最佳個體，然后將新產生的種群作為當前種群，繼續(xù)以上操作，直到滿足某種終止條件為止?？偨Y部分對全文的內容進行了總結并指出了文章的不足之處。全文包括遺傳算法概述、基于遺傳算法對TSP的實現及對四組遺傳算子的比較、總結等幾大部分組成。TSP是組合優(yōu)化問題中的NP難問題，可能的路徑數隨著城市的數目的增大呈指數級增長，城市數目越大尋優(yōu)路徑的難度也就越大，到目前為止已經提出了許多種解法。從20世紀90年代開始我國對遺傳算法的研究處于升溫時期，在最近的幾年里也取得了舉世矚目的成績。1 緒論遺傳算法是最近幾十年來發(fā)展起來的新型優(yōu)化方法，在六十年代末七十年代初主要由美國密歇根大學的John Holland教授與其同事、學生們共同研究形成了較完整的理論和方法，70年代De Jong基于遺傳算法的思想在計算機上進行了大量的純數值函數的優(yōu)化計算實例，80年代由Goldberg歸納總結了一系列研究工作，形成了遺傳算法的基本框架。目前人們已經將遺傳算法和其他諸如模擬退火算法、貪婪算法、最速下降法等結合起來形成了混合遺傳算法，使得對所求解的問題有更快的收斂速度和更強的魯棒性。遺傳算法的主要應用領域有函數優(yōu)化、組合優(yōu)化、生產調度、自動控制、機器人智能控制學、圖像處理和模式識別、人工生命、遺傳編程和機器學習。本文基于遺傳算法對對稱旅行商問題進行求解，并對各種實現方法進行對比討論。在遺傳算法概述部分簡單介紹了遺傳算法的機理、各種不同的編碼方法、適應度函數和遺傳操作，在基于遺傳算法對TSP的實現及對四組遺傳算子的比較部分首先對TSP作了簡要概述，然后介紹了常用的編碼方法、適應度函數的確定和針對TSP的遺傳算子的設計，接著闡述了實現部分匹配交叉法時需要注意的問題和新設計的交叉算子類貪婪交叉算子，最后對四種實現方法的結果進行對比評價。2 遺傳算法概述遺傳算法是通過模擬生物在自然環(huán)境中遺傳和進化的過程而形成的一種自適應的全局優(yōu)化概率搜索算法，借鑒生物學遺傳機制，模仿進化過程中的選擇、交叉和變異機理，以群體的方法進行自適應搜索，找到目標空間中的近似最優(yōu)解或滿意解。首先引入模式（schema）的概念。一個串中可以隱藏多個模式，一個模式可以隱藏在多個串中，不同的字符串之間通過模式相互聯系，所以說遺傳算法中串的運算實質上是模式的運算。模式階是指模式中確定的位置的個數，定義距指的是模式中第一個確定位置和最后一個確定位置之間的距離。模式定理：在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距和平均適應度高于群體平均適應度的模式在子代中將以指數級增長。由此引出積木塊假設。模式定理保證了較優(yōu)模式的樣本數呈指數級增長，從而滿足了尋找最優(yōu)解的必要條件，即遺傳算法存在找到最優(yōu)解的可能性，而積木塊假設指出了遺傳算法具備找到全局最優(yōu)解的能力。首先對目標問題進行編碼，編碼是表現型到基因型的映射，而遺傳算法的實現基礎是基因，因此需要將問題域轉換成基因空間；其次確定種群大小和適應度函數，種群中的合法個體在解碼后其表現型滿足目標問題的約束條件，算法在迭代的種群中逐步搜索目標問題的最優(yōu)解或滿意解，因此最優(yōu)解或滿意解經過有限次迭代后一定可以找到，適應度函數是用來評價優(yōu)良個體的依據，適應度高的個體得以保留，適應度低的個體被淘汰掉；再次隨機產生初始種群，產生初始種群時要確保個體的合法性約束，算法從初始種群開始對種群中的每個個體執(zhí)行遺傳操作；基本遺傳算子包括選擇算子、交叉算子和變異算子，選擇算子以個體的適應度為標準來決定哪些個體是否能夠保留，交叉和變異算子是產生新一代種群的關鍵遺傳算子，隨機確定交叉點和變異點在編碼串中的位置，可以產生新個體從而使種群進化逐步逼近最優(yōu)解或滿意解；最后確定中止代數，即達到什么條件終止算法的執(zhí)行。算法結束。 圖一 基本遺傳算法流程圖 遺傳算法的手工描述為了對遺傳算法的執(zhí)行過程有一個更清楚的了解，我們通過一個手工演算的例子來說明。假設群體中的個體數為4，序號分別為1，2，3，4。在產生新種群后計算四個個體的適應度，這里以目標函數值作為適應度值。選擇操作結束后隨機確定配對情況，之后我們進行單點交叉，交叉點以交叉概率隨機選取，變異操作采用基本位變異，同樣以變異概率選擇變異點，之后產生的新種群即為下一代種群。為方便起見算例中僅進行一次遺傳操作，在表一中可以看到在新產生的種群中已出現了目標函數的最優(yōu)解的基因型，通過解碼即可得到目標函數的最優(yōu)解。（1）自組織、自適應、自學習性和概率性。這種搜索方法是一種基于概率的搜索技術，其選擇、交叉、變異運算都是以一種概率的方式來進行的，從而增加了搜索過程的靈活性。 （2）隱并行性。另一種是遺傳算法的內在并行性，即遺傳算法適合大規(guī)模的并行，可以讓數千臺計算機各自孤立進行運算，運行過程中不需要信息交換，等到運算結束后才進行通信比較，選取最佳個體。（4）遺傳算法以決策變量的編碼作為運算對象，通過借鑒生物學中染色體和基因等概念來模仿生物的遺傳和進化機理，可以方便地進行遺傳算子的操作，特別是對無數值或很難有數值概念的優(yōu)化問題，編碼處理更顯現出優(yōu)越性，同時遺傳算法靠編碼和交叉算子的使用才能保證種群的進化。編碼與交叉操作共同決定了遺傳算法的結構。目前有許多種編碼方法，例如二進制編碼、符號編碼、浮點數編碼、格雷碼編碼、多參數級聯編碼、多參