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