【正文】 目 錄摘要......................................................................1關(guān)鍵詞....................................................................1引言......................................................................11 遺傳算法概論...........................................................11．1 遺傳算法的歷史和研究現(xiàn)狀 .............................................11．2 遺傳算法的基本原理..................................................31．2．1 遺傳算法基本概念.................................................31．2．2 遺傳算法基本原理..................................................31．2．3 遺傳算法的特點...................................................32 普通遺傳算法...........................................................42．1 普通遺傳遺傳算法思想................................................42．2 普通遺傳算法的遺傳操作..............................................42．2．1 選擇（selection）操作.............................................42．2．2 交叉(crossover)操作...............................................42．2．3 變異(mutation)操作................................................54 遺傳算法在 TSP問題上的應(yīng)用..............................................84．1 TSP 問題概述 ........................................................84．2 遺傳算法求解 TSP問題 .................................................84．2．1 編碼與解碼 ........................................................84．2．2 初始化種群 ........................................................94．2．3 適應(yīng)度函數(shù) ........................................................94．2．4 選擇算子 .........................................................104．2．5 交叉算子 .........................................................104．2．6 變異算子 .........................................................154．2．7 停止準(zhǔn)則.........................................................155 TSP問題的實驗結(jié)果及分析 ..............................................155．1 普通遺傳算法與佳點集遺傳算法的比較與分析............................155．1．1 最優(yōu)解分析 .......................................................155．1．2 算法收斂速度分析 .................................................175．1．3 算法運行時間分析.................................................18總 結(jié)....................................................................18致 謝....................................................................18參考文獻(xiàn).................................................................19ABSTRACT.................................................................19KEY WORDS................................................................19遺傳算法在 TSP 問題上的應(yīng)用摘要：遺傳算法(GA)模擬自然進(jìn)化機制，在搜索優(yōu)化問題全局或全局附近的最優(yōu)解上具有較好的魯棒性、內(nèi)在的并行性和較優(yōu)越的穩(wěn)定性，因而在諸如組合優(yōu)化、圖像處理等方面有著廣泛的應(yīng)用。但是傳統(tǒng)的遺傳算法性能很大程度上依賴于相關(guān)參數(shù)的取值與算子的作用方式，佳點集遺傳算法利用數(shù)論中的佳點集理論和方法，來改進(jìn)普通遺傳算法中的各相關(guān)算子，以期克服普通遺傳算法收斂速度慢，易陷入局部最優(yōu)的弱點。本文在分析普通遺傳算法和佳點集遺傳算法機理上，利用 JAVA語言實現(xiàn)了佳點集算法演示系統(tǒng)，通過選取不同的遺傳算子來對標(biāo)準(zhǔn) TSP 的數(shù)據(jù)集中的大量數(shù)據(jù)進(jìn)行了對比分析和驗證。我們的實驗結(jié)果表明對于較大規(guī)模的 TSP 組合問題佳點集的優(yōu)勢是非常明顯的。關(guān)鍵詞： Tsp 問題；普通遺傳算法；佳點集遺傳算法；單切點交叉算子；雙切點交叉算子； 循環(huán)交叉算子；佳點集交叉算子；引言 遺傳算法 Geic Algorithm（GA ）是由美國密歇根大學(xué)的 John H. Holland 教授及其學(xué)生于 20 世紀(jì) 60 年代末到 70 年代初提出的。它是以達(dá)爾文的自然進(jìn)化論“適者生存、優(yōu)勝劣汰”和孟德爾遺傳變異理論為基礎(chǔ)，模擬生物進(jìn)化過程。它具有大范圍快速全局搜索能力，能在搜索過程中自動獲取和積累有關(guān)搜索空間的知識，并自適應(yīng)地控制搜索過程以求的最優(yōu)解。正是遺傳算法的諸多特點，使得它在求解組合優(yōu)化、機器學(xué)習(xí)、并行處理等問題上得到了廣泛的應(yīng)用。普通遺傳算法是通過模擬染色體群的選擇、交叉和變異等操作，不斷迭代，最終收斂到高適應(yīng)度值的染色體，從而求得問題的最優(yōu)解。 但是隨著問題規(guī)模的擴大，組合優(yōu)化問題的搜索空間急劇擴大，普通遺傳算法的收斂速度慢、易陷入局部最優(yōu)的缺點就暴露了。而佳點集遺傳算法正是通過佳點集的方法改進(jìn)交叉算子，加快算法收斂到全局最優(yōu)解的速度，降低發(fā)生早熟的概率，提高整個算法的計算效率。1 遺傳算法概論1．1 遺傳算法的歷史和研究現(xiàn)狀 早在 1967 年 Bagley 和 Rosenberg 就提出了生物遺傳算法(GA) 的初步思想，1975年由美國 Michigan 大學(xué)的 John Holland 的出色工作奠定了遺傳學(xué)算法的理論基礎(chǔ)，遺傳變異和優(yōu)勝劣汰現(xiàn)象的優(yōu)化搜索算法付諸了實際應(yīng)用，這也標(biāo)志著遺傳算法的誕生。到了 80 年代初期，Holland 的一些學(xué)生的畢業(yè)論文中對遺傳算法的應(yīng)用以及在應(yīng)用中遇到的問題進(jìn)行了研究，其中有 Delong(1975)對 GA 的各種策略的性能和機理進(jìn)行了大量的細(xì)致分析與實驗。與此同時 Holland 還給出了一個自適應(yīng)的規(guī)則學(xué)習(xí)系統(tǒng)，并于 1980 年成功地實現(xiàn)了這一學(xué)習(xí)系統(tǒng)，Holland 及其學(xué)生的研究成果使得人們開始看到了 GA 的應(yīng)用價值。1981 年 Betake 的博士論文中提出了用 Walsh 函數(shù)來研究遺傳算法的方法，Alberta 大學(xué)的 Brindle 在其博士論文中開始對選擇策略進(jìn)行了研究，這一時期的研究回答了 GA 算法的到底有何意義，有何價值。也正是他們的研究使得更多的人把目光投向了遺傳算法，1985 年召開了第一屆 GA 國際會議，至此以后每兩年召開一次。80 年代中期，遺傳算法廣泛的應(yīng)用于許多的應(yīng)用領(lǐng)域，如 TSP 問題、調(diào)度問題、機器學(xué)習(xí)、模式分類問題，囚徒困境問題以及多關(guān)節(jié)機械手軌跡規(guī)劃問題。1989 年. Goldberg 總結(jié)了遺傳算法的主要成果，全面論述了遺傳學(xué)的基本原理極其應(yīng)用，奠定了現(xiàn)代 GA 的科學(xué)基礎(chǔ)。進(jìn)入 90 年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不僅它的應(yīng)用領(lǐng)域擴大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴展到了許多更新、更工程化的應(yīng)用方面。1991 年 D. Whi