【正文】 （geic operator）：遺傳算法中有三種關(guān)于染色體的運算：選擇、交叉和變異，這三種運算被稱為遺傳操作。 個體(individual) ：指染色體帶有特征的實體。而本文要實現(xiàn)的基于佳點集的遺傳算法就是通過設(shè)計合適的交叉算子來解決收斂速度和收斂性能的問題的。（2（ 遺傳算法的收斂性研究。2022 年，戴曉明等應(yīng)用多種群遺傳并行進化的思想，對不同種群基于不同的遺傳策略，如變異概率，不同的變異算子等來搜索變量空間，并利用種群間遷移算子來進行遺傳信息交流，以解決經(jīng)典遺傳算法的收斂到局部最優(yōu)解問題　　2022 年，趙宏立等針對簡單遺傳算法在較大規(guī)模組合優(yōu)化問題上搜索效率不高的現(xiàn)象，提出了一種用基因塊編碼的并行遺傳算法（Buildingblock Coded Parallel GA，BCPGA）。實驗結(jié)果表明，SIGH 與單點交叉、均勻交叉的神經(jīng)遺傳算法相比，所測試的六個函數(shù)中有四個表現(xiàn)出更好的性能，而且總體來講，SIGH 比現(xiàn)存的許多算法在求解速度方面更有競爭力。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無疑均給遺傳算法增添了新的活力。80 年代中期，遺傳算法廣泛的應(yīng)用于許多的應(yīng)用領(lǐng)域，如 TSP 問題、調(diào)度問題、機器學(xué)習(xí)、模式分類問題，囚徒困境問題以及多關(guān)節(jié)機械手軌跡規(guī)劃問題。到了 80 年代初期，Holland 的一些學(xué)生的畢業(yè)論文中對遺傳算法的應(yīng)用以及在應(yīng)用中遇到的問題進行了研究，其中有 Delong(1975)對 GA 的各種策略的性能和機理進行了大量的細(xì)致分析與實驗。普通遺傳算法是通過模擬染色體群的選擇、交叉和變異等操作，不斷迭代，最終收斂到高適應(yīng)度值的染色體，從而求得問題的最優(yōu)解。關(guān)鍵詞： Tsp 問題；普通遺傳算法；佳點集遺傳算法；單切點交叉算子；雙切點交叉算子； 循環(huán)交叉算子；佳點集交叉算子；引言 遺傳算法 Geic Algorithm（GA ）是由美國密歇根大學(xué)的 John H. Holland 教授及其學(xué)生于 20 世紀(jì) 60 年代末到 70 年代初提出的。目 錄摘要......................................................................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參考文獻.................................................................19ABSTRACT.................................................................19KEY WORDS................................................................19遺傳算法在 TSP 問題上的應(yīng)用摘要：遺傳算法(GA)模擬自然進化機制，在搜索優(yōu)化問題全局或全局附近的最優(yōu)解上具有較好的魯棒性、內(nèi)在的并行性和較優(yōu)越的穩(wěn)定性，因而在諸如組合優(yōu)化、圖像處理等方面有著廣泛的應(yīng)用。我們的實驗結(jié)果表明對于較大規(guī)模的 TSP 組合問題佳點集的優(yōu)勢是非常明顯的。正是遺傳算法的諸多特點，使得它在求解組合優(yōu)化、機器學(xué)習(xí)、并行處理等問題上得到了廣泛的應(yīng)用。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)志著遺傳算法的誕生。也正是他們的研究使得更多的人把目光投向了遺傳算法，1985 年召開了第一屆 GA 國際會議，至此以后每兩年召開一次。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不僅它的應(yīng)用領(lǐng)域擴大，而且利用遺傳算法進行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。D. H. Ackley 等提出了隨機迭代遺傳爬山法（Stochastic Iterated Geic Hillclimbing，SIGH ）采用了一種復(fù)雜的概率選舉機制，此機制中由 m 個“ 投票者” 來共同決定新個體的值（m 表示群體的大小） 。 近年來，國內(nèi)也有不少的專家和學(xué)者對遺傳算法的交叉算子進行改進?？傊藗儗z傳算法的研究主要可以概括為以下三個方面：（1（ 遺傳算法搜索在進化到一定的程度就往往會使得種群的適應(yīng)度趨向于相同，這樣似的種群間的概率變的非常接近，這時的選擇和復(fù)制策略接近于純隨機的抽樣過程，使得搜索的收斂速度比較慢，針對這一問題，人們提出了不同的選擇和復(fù)制策略。（3（ 遺傳算法收斂性能的研究，普通的遺傳算法搜索