【正文】 遺傳算法研究．計(jì)算機(jī)工程與 用， 2020， 42(20)：5557． [5] 陳靜．改進(jìn)遺傳算法及其在旅行推銷商問(wèn)題中的應(yīng)用研究： (碩士學(xué)位論文 )．重慶：重慶大學(xué) 計(jì) 算機(jī)學(xué)院， 2020． [6] 徐麗佳，蒲海波，蔣宏?。倪M(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ò)我的老師。 double CityDistance[CITY_NUM][CITY_NUM]。 int BestFitCityXuh。j++){//最后一個(gè)城市還應(yīng)該返回到出發(fā)節(jié)點(diǎn) temp1=CityPos[j][0]CityPos[i][0]。//新生成節(jié)點(diǎn)沒(méi)有存在于已經(jīng)生成的路徑中 } void InitColony(PTSP city)//初始化城市，隨機(jī)生成數(shù)據(jù) { int i,j,r。iPOPSIZE。 for(i=0。 } cityfitness[i]=N/(cityDistance[i])。 int i,j。tempflag1==0。h2。 tempcityxuh[0][i]=tempcityxuh[1][i]。 }while(genePoint[0]==genePoint[1]||genePoint[0]==0||genePoint[1]==0)。i=genePoint[1]。 //for(h=0。 cityCross[(k+1)%2][i]=0。amp。i=countCrossGene。} } }//forh } //exchgTempcityxuh(tempcityxuh,countCrossGene)。i++) { cityCross[h][i]=citycolony[tempXuh[h]][i]。i++) { tempXuh[0]=rand()%(POPSIZE1)。j=int(POPSIZE*pm)。 //swich temp=citycolony[selCity][changePoint[0]]。 int selCity。 for(i=0。h++) { for(i=0。j++) { if(tempcityxuh[h][i]==tempcityxuh[(h+1)%2][j]) { flaglike=1。h++) { k=countCrossGene。i=CITY_NUM1。i=genePoint[1]。 cityCross[k][j]=CITY_NUM。k2。 do { genePoint[0]=rand()%(CITY_NUM1)。i=countCrossGene。 }//Select() void copyCityXuhToCityColony(int tempcityxuh[][CITY_NUM+1],int *tempXuh,PTSP city) { int i,h。jPOPSIZEamp。 }*/ } return。end=citycolony[i][j]。 } } } //求適應(yīng)值 void CalFitness(PTSP city) { int i,j。 cityBestFitness=0。i++){ if(k==citycolony[pop][i]) return true。i++){ for(j=0。//最優(yōu)路徑適應(yīng)值 double BestValue。 福建農(nóng)林大學(xué)本科畢業(yè)論文 23 附錄程序 // include include include include define CITY_NUM 10 //城市編號(hào)是 0~CITY_NUM1 define POPSIZE 50 define MAXVALUE 10000 //路徑越短越好 define MAXSAMETIME 15 //結(jié)果沒(méi)有改變的最大次數(shù) define N 1//需要根據(jù)實(shí)際求得的路徑值修正 unsigned seed=(unsigned)time(0)。還有不少其它的方法和策略可用于解決 TSP 問(wèn)題，如模擬退火算法、濃度控制策略等都取得了很好的效果。在求解的質(zhì)量和優(yōu)化效率上都表現(xiàn)出了比較突出的能力。從而降低了其抑制早熟的能力。 福建農(nóng)林大學(xué)本科畢業(yè)論文 18 //swich temp=citycolony[selCity][changePoint[0]]。 int selCity。 }while(tempXuh[0]==tempXuh[1])。 void Cross(PTSP city,double pc) {//交叉概率是 pc int crossNum,i。amp。i++)//選 POPSIZE 次 { tempRand=(rand()%100000)/*3。設(shè)群體大小為 N，個(gè)體 i 的適應(yīng)度值 Fi，則個(gè)體 i 被選擇的概率 Psi為： Psi=Fi／ ??nj j1F (n=l， 2?．． n) 顯然，概率 Psi反映了個(gè)體 i的適應(yīng)度在整個(gè)群體的個(gè)體適應(yīng)度總和中所占的比例。常用的選擇可略包括以下幾種： (1) 輪盤賭法。 for(j=1。適應(yīng)度較高的物種將會(huì)得到更多的繁殖的機(jī)會(huì)；從而導(dǎo)致適應(yīng)度低的物種被淘汰。編碼機(jī)制的主要工作是把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。人工神經(jīng)網(wǎng)絡(luò)算法成為近年來(lái)的熱點(diǎn)研究領(lǐng)域，涉及到 數(shù)學(xué) 、電氣工程、 計(jì)算機(jī)工程 、 物理學(xué) 等諸多學(xué)科，其應(yīng)用領(lǐng)域包括了建模、時(shí)間序列分析、模式識(shí)別和控制等，并且仍然在一斷擴(kuò)展。 (3)蟻群算法 又稱 螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型算法。 雖然傳統(tǒng)算法能夠找 TSP 問(wèn)題的最優(yōu)解，但隨著問(wèn)題規(guī)模的不斷增長(zhǎng)，算法所需要的時(shí)間非常巨大，因此只適用于求解規(guī)模較小的 TSP 問(wèn)題?？焖佟⒂行У亟鉀Q TSP 問(wèn)題有著極高的實(shí)際應(yīng)用價(jià)值，也就吸引了眾多領(lǐng)域的學(xué)者對(duì)它進(jìn)行研究。 福建農(nóng)林大學(xué)本科畢業(yè)論文 9 TSP問(wèn)題的數(shù)學(xué)模型 TSP 問(wèn)題的數(shù)學(xué)模型如下：設(shè)有 n個(gè)城 市，尋找一條巡回路徑 T=(t1， t2，．．．， tn)，使得下列目標(biāo)函數(shù)最?。? f(T)= ???1n1di(ti,ti+1)+d(tn,t1) 其中 ti為 城 市號(hào)，取值為 1 到 n 之間的自然數(shù)， d(i,j)為城市 i 和城市 j 之間的距離，對(duì)于對(duì)稱式 TSP，有 d(i， j)=d(j， i)。一些機(jī)器的目標(biāo)就是為了在某種材料片上鉆削不同的孔。 TSP的應(yīng)用與價(jià)值 TSP 在現(xiàn)實(shí)生活中有很多應(yīng)用。例如遺傳算法已經(jīng)在求解旅行商問(wèn)題、 背包問(wèn)題、裝箱問(wèn)題、圖形劃分問(wèn)題等方面得到成功的應(yīng)用 (3) 自動(dòng)控制 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問(wèn)題需要求解，遺傳算法已在其中得到了初步的應(yīng)用，并顯示了良好的效果。 (5)遺傳算法可以更加直接的應(yīng)用。它的并行性表現(xiàn)在兩個(gè)方面，一是遺傳算法的內(nèi)在并行性 (inherentparallelisml，即遺傳算法本身非常適合大規(guī)模并行。應(yīng)用遺傳算法求解問(wèn)題時(shí)，在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過(guò)程中獲得的信息自行組織搜索。在每一代中用適應(yīng)度 (fitness)來(lái)測(cè)量染色體的好壞。作為多個(gè)基因的集合，單個(gè)染色體是遺傳物質(zhì)的主要載體，其在種群中的命運(yùn)由其基因組合決定。 1989 年， David Goldberg 出版了 ((GeicAlgorithm in Search,Optimization and Machine Leaming》一書， 成為論述遺傳算法的第一本專著。同時(shí)，通過(guò)基因重組、基因變異和染色體在結(jié)構(gòu)和數(shù)目上的變異產(chǎn)生豐富多彩的變異現(xiàn)象。他認(rèn)為遺傳以密碼方式存在于細(xì)胞中，并以基因形式包含在染色體內(nèi)。 Darwin 進(jìn)化論最核心的是自然選擇學(xué)說(shuō) 。 論文的組織結(jié)構(gòu) 第 1章緒論。 TSP 問(wèn)題是一個(gè)具有廣泛的應(yīng)用背景和重要理論價(jià)值的組合優(yōu)化問(wèn)題，它是一個(gè)典型的 NP 問(wèn)題。 遺傳算法 (Geic Algorithms，簡(jiǎn)稱 GA)是借鑒生物選擇和進(jìn)化機(jī)制發(fā)展起來(lái)的一種高度并行、隨機(jī)和自適應(yīng)搜索算法 。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。 設(shè)計(jì)題目： _____基于 遺傳 算法 的 TSP問(wèn)題研究 _ 學(xué) 院 ： _______計(jì)算機(jī)與信息學(xué)院 __ _____ I 畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說(shuō)明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文），是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。本人完全意識(shí)到本聲明的法律 后果由本人承擔(dān)。傳統(tǒng)的求解方法在面對(duì)較大規(guī)模的問(wèn)題時(shí)，很不容易得到最優(yōu)解。旅行商問(wèn)題是一個(gè)比較古老的問(wèn)題，最早可追溯到 Euler 提出的騎士旅行問(wèn)題，同時(shí)它也是個(gè)“新問(wèn)題 ，因?yàn)橛?jì)算的復(fù)雜性 較高，人們一直在嘗試用新的方法來(lái)改進(jìn)求解該問(wèn)題的復(fù)雜度?；诖嗽颍疚牡闹饕怯?遺傳 算法的基本算子解決 TSP 這個(gè)有意義的 NP難問(wèn)題。遺傳算法正是從大自然的杰作 —— 生物進(jìn) 化論中得到的靈感和啟迪 ，其基本思想是Darwin 進(jìn)化論和 Mendel 的遺傳學(xué)說(shuō)。 Mendel 遺傳學(xué)說(shuō)最重要的是基因遺傳原理 。生物體自身通過(guò)對(duì)基因的復(fù)制和交叉即基因分離、基因自由組合和基因連鎖互換的操作使其性狀的遺傳得到選擇和控制。 1980 年， Smith 將遺傳算法應(yīng)用于機(jī)器學(xué)習(xí)領(lǐng)域； Bethke 對(duì)函數(shù)優(yōu)化的遺傳算法進(jìn)行了系統(tǒng)的研究。每個(gè)個(gè)體實(shí)際上是染色體(Chromosome)帶有特征的實(shí)體。這些染色體在后續(xù)迭代中不斷進(jìn)化，稱為遺傳。主要區(qū)別在于 (1)自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法按并行方式搜索一個(gè)種群數(shù)目的點(diǎn)，而不是單點(diǎn)。 (4)遺傳算法強(qiáng)調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)化規(guī)則。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)福建農(nóng)林大學(xué)本科畢業(yè)論文 7 化中的 NP問(wèn)題非常有效。但是遺憾的 是，計(jì)算復(fù)雜性理論給予我們的結(jié)論卻是，這種可能性尚屬未知 。例如在組裝線上的機(jī)器。為了通過(guò) TSP 解決這個(gè)時(shí)間的節(jié)約問(wèn)題，對(duì)每個(gè)節(jié)點(diǎn)做了簡(jiǎn)化，用需要鉆孔的位置來(lái)代替，而邊用節(jié)點(diǎn)之間的距離來(lái)代替。因此尋求一 種求解時(shí)間短，能滿足實(shí)際問(wèn)題精度要求的解，成為解決該問(wèn)題的主要途徑。傳統(tǒng)算法有精確算法和近似優(yōu)化算法，精確算法又有線性規(guī)劃方法、動(dòng)態(tài)規(guī)劃方法、分支定界方法等，而近似算法有插入法、最近鄰算法、 ropt 算法、混合算法、概率算法等。這種算法思想在求解優(yōu)化問(wèn)題時(shí)，不但接受對(duì)目標(biāo)函數(shù) (能量函數(shù) )有改進(jìn)的狀態(tài)，還以某種概率接受使目標(biāo)函數(shù)惡化的狀態(tài)，從而可使之避免過(guò)早收斂到某個(gè)局部極值點(diǎn)，也正是這種概率性的擾動(dòng)能夠使之跳出局部極值點(diǎn)，故而得到的解常常很好。