【正文】 .求解 TSP 問(wèn)題的遺傳算法實(shí)現(xiàn) [J].計(jì)算機(jī)時(shí)代 ,2020 ,2:1921. [3] 周明 ,孫樹棟 .遺傳算法原理及應(yīng)用 [M].國(guó)防工業(yè)出版社 .1999. [4] 柳林，楊峰．求解 TSP 問(wèn)題的改進(jìn)遺傳算法研究．計(jì)算機(jī)工程與 用， 2020， 42(20)：5557． [5] 陳靜．改進(jìn)遺傳算法及其在旅行推銷商問(wèn)題中的應(yīng)用研究： (碩士學(xué)位論文 )．重慶：重慶大學(xué) 計(jì) 算機(jī)學(xué)院， 2020． [6] 徐麗佳，蒲海波，蔣宏健．改進(jìn)遺傳算法的路徑規(guī)劃研究．微計(jì)算機(jī)信息． 2020(5).215253． [7] 趙振勇，王力，王保華等．遺傳算法改進(jìn)策略的研究．計(jì)算機(jī)應(yīng)用． 2020，26(12)． 189191． [8] Aytug H．， Koehler GJ． Stopping criteria for finite length geical gorithms[J]． ORASJofComputation， 1996， (8)： 183— 191． [9] 柳林，楊峰．求解 TSP 問(wèn)題的改進(jìn)遺傳算法研究．計(jì)算機(jī)工程與應(yīng)用， 2020， 42(20)：5557． [10] 段海濱 .人生智能計(jì)算 .北京： 科學(xué)出版社 .2020 [11] 王超學(xué)，崔杜武，王竹榮，費(fèi)蓉．一種求解 TSP 的高效遺傳算法 [J]．西安 理工 大學(xué)學(xué)報(bào)， 2020． 1(22) [12] 韋雪潔，黎明，劉高杭，田貴超．基于知識(shí)庫(kù)求解 TSP 問(wèn)題的改進(jìn)遺傳 [J]．計(jì)算機(jī)仿真， 2020， 08： 161— 163． [13] 梁艷春 ， 群 智能優(yōu)化算法及其應(yīng)用 [M]．北京：科學(xué) 出版社， 2020 [14] 紀(jì)震，廖惠連，吳青華，粒子群算法及應(yīng)用，北京：科學(xué)出版社， 2020 [15] 張軍，計(jì)算智能，北京 ： 清華大學(xué)出版社， 2020 [16]王耀南，智能控制理論及應(yīng)用，北京：機(jī)械工業(yè)出版社， 2020 福建農(nóng)林大學(xué)本科畢業(yè)論文 22 致 謝 大學(xué)本科的學(xué)習(xí)即將結(jié)束，在此首先感 謝所有曾經(jīng)教導(dǎo)過(guò)我的老師。 (2)如何獲得更好的性能是用算法解決實(shí)際問(wèn)題時(shí)必須要考慮的，如針對(duì)具體問(wèn)題開發(fā)相應(yīng)的初始群體的生成技術(shù)，更好的交叉、變異算子的設(shè)計(jì)，控制參數(shù)的選擇等，都是需要進(jìn)一步深入研究的重要課 題。如種群大小影響了種群的多樣性，過(guò)少會(huì)導(dǎo)致算法陷入局部最優(yōu)，而找不到全局最優(yōu)解，過(guò)多大大的增加算法的計(jì)算量，增大機(jī)器開銷，算法效率低下。 福建農(nóng)林大學(xué)本科畢業(yè)論文 20 結(jié) 論 本文通過(guò)遺傳算法求解 TSP 問(wèn)題，成功獲得了全局最優(yōu)解。在本算法中變異率因取 到 為宜。一般的 10個(gè)點(diǎn)城市，初始種群取 50 到 100為好。 citycolony[selCity][changePoint[1]]=temp。 changePoint[1]=rand()%(CITY_NUM1)+1。j=int(POPSIZE*pm)。變異操作是改善遺傳算法的局部搜索能力和維持群體的多樣性防止早熟現(xiàn)象。 crossTwo(city,tempXuh,cityCross)。i++) { tempXuh[0]=rand()%(POPSIZE1)。 int tempXuh[2]。 這 是 在選中用于繁 殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體，也即對(duì)兩個(gè)父染色體的部分結(jié)構(gòu)進(jìn)行重組，以產(chǎn)生新一代子染色體。 } } } } return。j++) { if(tempRand=cityaddFitness[j])//輪盤賭選中第 j個(gè) { 福建農(nóng)林大學(xué)本科畢業(yè)論文 15 tempflag1=1。 for(j=0。 for(i=0。 輪盤賭的具體執(zhí)行過(guò)程如下： a)先計(jì)算出種群中所有個(gè)體的適應(yīng)度的總和。本文采用的是 輪盤賭法 。 (3) 最優(yōu)保存策略。 } } 遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選 取哪 些個(gè)體遺傳到福建農(nóng)林大學(xué)本科畢業(yè)論文 14 下一代群體中的一種遺傳運(yùn)算。j++){ start=citycolony[i][j1]。iPOPSIZE。 本文中適應(yīng)度函數(shù)取為哈密爾頓圈的長(zhǎng)度的倒數(shù)。初始種群個(gè)數(shù)越多，得到最優(yōu)解的希望越大，但個(gè)數(shù)過(guò)多會(huì)導(dǎo)致每進(jìn)行一輪的機(jī)器時(shí)間變長(zhǎng)，致使算法效率低下。遺傳算法中經(jīng)常使用二進(jìn)制串進(jìn)行編碼，其優(yōu)點(diǎn)是編碼、解碼操作簡(jiǎn)單，交叉、變異等操作也易于實(shí)現(xiàn)，且便于應(yīng)用模式定理進(jìn)行理論分析；其缺點(diǎn)主要是處理 連續(xù)函數(shù)的優(yōu)化問(wèn)題時(shí)存在映射誤差：編碼長(zhǎng)度較小時(shí)達(dá)不到精度要求， 度較大時(shí)又會(huì)使算法搜索空間過(guò)大。 圖 41遺傳算法運(yùn)用在 TSP上的流圖程 福建農(nóng)林大學(xué)本科畢業(yè)論文 13 遺傳算法的進(jìn)化過(guò)程是建立在編碼機(jī)制基礎(chǔ)上的，編碼對(duì) 于算法的性能，如搜索能力和種群多樣性等影響很大。其一是有一組突觸或連接，常用表示內(nèi)部神經(jīng)元的聯(lián)接強(qiáng)度，或者稱 為權(quán)值，取值 范圍 可在負(fù)值和正值之間 ， 其二是 可以 反映生物神經(jīng)元時(shí)空整合功能的輸入信號(hào)累加器 ， 其三是具有一個(gè)激勵(lì)函數(shù)用于限制神經(jīng)元的輸出 。 但是，它存在收斂慢、易于陷人局部最優(yōu) 的缺點(diǎn) 。 反過(guò)來(lái)， 信息激素濃度高的路徑上會(huì)吸引更多的螞蟻。 (2)模擬退火算法 這是一種源 于五十年代、基于 Monte Carlo 迭代求解思想的隨機(jī)搜索算法，八十年代才開始應(yīng)用于組合優(yōu)化領(lǐng)域，其出發(fā)點(diǎn)是將組合優(yōu)化問(wèn)題與統(tǒng)計(jì)力學(xué)的熱平衡作類比，把優(yōu)化的目標(biāo)函數(shù)視作能量函數(shù)，模仿物理學(xué)中固體物質(zhì)的退火處理，先加溫使之具有足夠高的能量，然后再逐漸降溫，其內(nèi)部能量也相應(yīng)下降，在熱平衡條件下，物體內(nèi)部處于不同狀態(tài)的概率服從 Boltzmann分布，若退火步驟恰當(dāng)，則最終會(huì)形成最低能量的基態(tài)。引入智能演化算法的原因在于避免陷人局部最優(yōu)解，希望得到更好的解上界。 TSP 問(wèn)題 ,即 EuclidTSP,它給出每個(gè)點(diǎn)在歐式平面 上的坐標(biāo) ,而城市間的距離就是以他們的歐式距離來(lái)定義 . 福建農(nóng)林大學(xué)本科畢業(yè)論文 10 現(xiàn)有的求解 TSP 問(wèn)題的幾種算法 在求解 TSP的算法的過(guò)程中，人們一直在尋找切實(shí)有效的方法，按招時(shí)間出現(xiàn)的順序大致可分為：傳統(tǒng) 算法和智能演化算法。 1954 年 Dantzig， Fulkerson 和 Johnson 解決了 49 個(gè)城市數(shù)目的 TSP 問(wèn)題，經(jīng)過(guò)半個(gè)世紀(jì)的研究，目前，最大的已成功求解的旅行商問(wèn)題有 24798 個(gè)城市。在理論上雖然枚舉法可以解這一問(wèn)題，但是當(dāng) n較大時(shí)，解題的時(shí)間消耗會(huì)使枚舉法顯得沒(méi)有任何實(shí)際價(jià)值。 TSP 問(wèn)題是組合優(yōu)化領(lǐng)域中的一個(gè)典型問(wèn)題，涉及求多個(gè)變量的函數(shù)的最小值。在裝配線的實(shí)例中，對(duì)每個(gè)工件為完成裝配過(guò)程節(jié)約的少許時(shí)間意味著一天的產(chǎn)量的相應(yīng)增加。鉆頭通過(guò)定位裝置在材料片上重定位。 TSP 在其他領(lǐng)域還有很多重要的實(shí)際應(yīng)用。了解了對(duì)每個(gè)城市訪問(wèn)一次的最優(yōu)旅行路徑能夠?yàn)槁眯泄?jié)約很多潛在的時(shí)間。該問(wèn)題在圖論的意義下就是所謂的最小 Hamilton 圈問(wèn)題，由于可以廣泛應(yīng)用在許多領(lǐng)域，所以尋找出實(shí)際而有效的算法就顯得比較重要了。 (4)人工生命 人工生命是用計(jì)算機(jī)，機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)，自組織能力和自學(xué)能力是人工生命的兩大主要特征。對(duì)這 類復(fù)雜的問(wèn)題，人們已經(jīng)意識(shí)到應(yīng)把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)問(wèn)題的通用框架，它不依賴于問(wèn)題的具體領(lǐng)域，對(duì)問(wèn)題的種類有很強(qiáng)的 魯棒性 ，所以廣泛應(yīng)用于許多科學(xué) 。 (3)遺傳算法不需要求導(dǎo)或其他輔助知識(shí)，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)。這種并行處理方式對(duì)并行系統(tǒng)結(jié)構(gòu)沒(méi)有什么限制和要求，可以說(shuō)，遺傳算法適合在目前所有的并行機(jī)或分布式系統(tǒng)上進(jìn)行并行處理，而且對(duì)運(yùn)行效率沒(méi)有太大的影響。 (2)遺傳算法的本質(zhì)并行性。通常，適應(yīng)度大的個(gè)體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)，在通過(guò)基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。隨著問(wèn)題種類的不同以及問(wèn)題規(guī)模的擴(kuò)大，需要尋求一種能以有限的代價(jià)來(lái)解決搜索和優(yōu)化的通用方法，遺傳算法 正是為我們提供了一個(gè)有效途徑，它不同于傳統(tǒng)的 搜索和優(yōu)化方法。后代是由前一代染色體通過(guò)交叉 (crossover)或者變異 (mutation)運(yùn)算形成的。種群中的每個(gè)個(gè)體是問(wèn)題的一個(gè)解 ，稱為“染色體 ，染色體是一串符號(hào)，比如二進(jìn)制 01 串。在每一代， 根據(jù)問(wèn)題域中個(gè)體的適應(yīng)度 (fitness)大小挑選個(gè)體，并借助代表于自然遺傳學(xué)的遺傳算子 (Geic Operators)進(jìn)行交叉 (Grossover)和變異(Mutation)，產(chǎn)生出代表新的解集的種群。 遺傳算法 基本原理 遺傳算法是從代表問(wèn)題可能潛在解集的一個(gè)種群 (Population)開始的，而一個(gè)種群則由經(jīng)過(guò)基因 (Gene)編碼 (Coding)的一定數(shù)目的個(gè)體 (Individual)組成。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，被廣 泛地應(yīng)用于組合優(yōu)化、生產(chǎn)調(diào)度 、機(jī)器學(xué)習(xí)、圖像處理、人工生命等領(lǐng)域，不僅如此，利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高。 80 年代，遺傳算法開始在各個(gè)領(lǐng)域得到廣泛應(yīng)用。 上個(gè)世紀(jì) 60 年代， Michigan 大學(xué)的 J． H． Holland 教授開始認(rèn)識(shí)到生物的遺傳和自然進(jìn)化現(xiàn)象與人工自適應(yīng)系統(tǒng)的相似關(guān)系，并將生物遺傳機(jī)制引入人工自適應(yīng)系統(tǒng)的研究。基因可以精確的復(fù)制，也可以發(fā)生突變，并可以通過(guò)控制蛋白質(zhì)的合成而控制生物的性狀。所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性。 Darwin 把這種在生存斗爭(zhēng)中適者生存、不適者淘汰的過(guò)程稱為自然選擇?！拔锔?jìng)天擇，適者生存”。 第 5章 總結(jié) 福建農(nóng)林大學(xué)本科畢業(yè)論文 2 第 2 章 遺傳 算法理論概述 起源和發(fā)展 20 世紀(jì) 40年代以來(lái)，科學(xué)家努 力從生物學(xué)中尋找用于計(jì)算機(jī)科學(xué)和人工系統(tǒng)的新思維、新方法和新途徑，生命科學(xué)與工程科學(xué)相互交叉、相互滲透、相互促進(jìn)成為近代科學(xué)發(fā)展的顯著特點(diǎn)之一。 第 2章，概要介紹了 遺傳 算法的 起源和發(fā)展、 思想 及應(yīng)用等問(wèn)題，并重點(diǎn)介紹了基本 遺傳算法。而 遺傳 算法是一種的元啟發(fā)式優(yōu)化算法 ,基于 遺傳 算法在許多方面有重要的應(yīng)用空間。TSP 問(wèn)題就是要決定一條經(jīng)過(guò)圖中所有頂點(diǎn)，當(dāng)且僅當(dāng)一次且代價(jià)最小的回路，即代價(jià)最小的Hamilton 回路， 為簡(jiǎn)化問(wèn)題。 crossover opera福建農(nóng)林大學(xué)本科畢業(yè)論文 1 第 1 章 緒論 旅行商問(wèn)題 (Traveling Salesman Problem， TSP)，也稱貨郎擔(dān)問(wèn)題，是指對(duì)于給定的甩個(gè)城市，旅行商從某一個(gè)城市出發(fā)，不重復(fù)地訪問(wèn)其余每一個(gè)城市，最后又返回到原出發(fā)城市，要求找出一條旅行路線，使其的旅行所付出的代價(jià)最小。它的兩個(gè)最大的顯著特點(diǎn)是隱含并行性和全局搜索。故對(duì)此問(wèn)題的求解具有理論與實(shí)用兩方面的意義。 涉密論文按學(xué)校規(guī)定處理。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。對(duì)本研究提供過(guò)幫助和做出過(guò)貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說(shuō)明并表示了謝意。盡我所知，除文中特別加以標(biāo)注和致謝的地方外，不包含其他人或組織已經(jīng)發(fā)表或公布過(guò)的研究成 果，也不包含我為獲得 及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過(guò)的材料。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。本人授權(quán) 大學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存和匯編本學(xué)位論文。 TSP 是經(jīng)典的 NPhard 組合優(yōu)化問(wèn)題之一，也是一個(gè)測(cè)試算法優(yōu)劣性的標(biāo)準(zhǔn)問(wèn)題，且現(xiàn)實(shí)中有很多應(yīng)用問(wèn)題都可歸結(jié)或轉(zhuǎn)化為 TSP 問(wèn)題。特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線形問(wèn)題。TSP。 G=（ V， E）為賦權(quán)圖， V=1， 2，?， N 為頂點(diǎn)集， E為邊集， Cij 表示旅行商經(jīng)過(guò)對(duì)應(yīng)弧段（ i， j）所花的費(fèi)用，如時(shí)間、距離、花費(fèi)等 。所以 TSP 問(wèn)題在計(jì)算理論上和實(shí)際應(yīng)用上都有很高的價(jià)值，將直接帶動(dòng)整個(gè)組合優(yōu)化領(lǐng)域新的發(fā)展。本章論述旅行商問(wèn)題的基本概念，以及本課題的主要研究?jī)?nèi)容及其研究意義，并對(duì)本文的章節(jié)結(jié)構(gòu)加以概述。詳細(xì)論述了用 遺傳 算法在 TSP 的實(shí)現(xiàn)方法和主要參數(shù)設(shè)置、程序?qū)崿F(xiàn)。他認(rèn)為，生物進(jìn)化是一個(gè)緩慢的變化過(guò)程，物種不是被創(chuàng)造出來(lái)的，而是自然選擇的必然結(jié)果。只有適應(yīng)性強(qiáng)的個(gè)體才能在斗爭(zhēng)中存活下來(lái)，并且有更多的機(jī)會(huì)將有利變異傳給后代；而不適應(yīng)斗爭(zhēng)環(huán)境、具有不利變異的個(gè)體將面臨淘汰。每個(gè)基因有特殊的位置并控制某種特 殊性質(zhì)。 現(xiàn)代遺傳學(xué)和細(xì)胞學(xué)的 研究表明 ，生物的遺傳物質(zhì)主要保存在染色體中， 染色體由 DNA(脫氧核糖核酸 )和蛋白質(zhì)組成；基因則是指攜帶有遺傳信息的 DNA 序列，是控制性狀的基本遺傳單位。 能否將生