【正文】 [5]敖友云、遲洪欽 .基于遺傳算法求解 TSP 問(wèn)題的一種算法 [J].計(jì)算機(jī)與數(shù)字工程。 %產(chǎn)生兩個(gè)用于交換的隨機(jī)數(shù) tempvessel=path(i,temPm6)。 temp1=path(i,temPm4:temPm5)。 %因要求最小值，采且常數(shù)減函數(shù)值構(gòu)造適應(yīng)度 Fitness=Fitness./sum(Fitness)。 outdistance=zeros(11,11)。解決辦法：可以在變異操作時(shí)，增加個(gè)體求優(yōu)的自學(xué)習(xí)過(guò)程。 第二：計(jì)算適應(yīng)度，因取最短路徑值， 即最小值，常用方法為 CF(x)或 C/F(x)（ C為一常數(shù)），此處采用前一種方式。多種優(yōu)化機(jī)制和鄰域搜索結(jié)構(gòu)相混合，是能較大程度提高全局優(yōu)化度和魯棒性的有力途徑，并可一定程度上放松對(duì)單一算法參數(shù)選擇的苛刻性，所以混合優(yōu)化策略會(huì)是一種趨勢(shì)。 上述幾種 TSP 操作基本上考慮的是城市的位置和順序，未考慮城市間的連 Grefenstette 認(rèn)為遺傳算法應(yīng)用與 TSP，其遺傳操作不僅要考慮城市間的位置，而且有必要考慮 城市間的關(guān)系，城市間的關(guān)系定義為邊，讓子個(gè)體繼承父?jìng)€(gè)體中邊的信息設(shè)計(jì)邊的遺傳操作很有意義。 貴州大學(xué) 第 10 頁(yè) 選擇算子 選擇是從一個(gè)舊種群 (old population)中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過(guò)程。借助遺傳算法的搜索能力解決 TSP 問(wèn)題是很自然的想法。一般來(lái)說(shuō)適應(yīng)度越高 , 解的素質(zhì)越好。進(jìn)入 80年代，遺傳算法迎來(lái)了興盛發(fā)展時(shí)期，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門的話題近年來(lái)，遺傳算法已被成功地應(yīng)用于經(jīng)濟(jì)答理、交通運(yùn)輸、工業(yè)設(shè)計(jì)等不同領(lǐng)域．解決了許多問(wèn)題。 TSP 旅行商問(wèn)題是一類典型的 NP 完全問(wèn)題， 遺傳算法是解決 NP問(wèn)題的一種較理想 的方法。 其基本思想基于 Darwin 的進(jìn)化論和 Mendel 的遺傳學(xué)。 遺傳算法的主要特點(diǎn)是群體搜索策略和群體中個(gè)體之間的信息交換，搜索不以梯度信息為基礎(chǔ)。 貴州大學(xué) 第 6 頁(yè) 遺傳算法的基本求解步驟 編碼： 確定用何種碼制 , 然后將問(wèn)題參數(shù)編碼形成基因碼鏈，每一個(gè)碼鏈代表一個(gè)個(gè)體 , 表示優(yōu)化問(wèn)題的一個(gè)解。 TSP 搜索空間隨著城市數(shù)n 的增加而增大，所有 的旅程路線組合數(shù)為 (n1)! /2。迭代停止條件一般是：若某代群體中的最差個(gè)體與最好的個(gè)體適應(yīng)度的差不大于某個(gè)數(shù)（根據(jù)問(wèn)題規(guī)模變化），則終止算法。也是首先隨機(jī)地在父?jìng)€(gè)體中選擇兩雜交點(diǎn)，再交換雜交段，其它位置根據(jù)保持父代個(gè)體中城市的相對(duì)次序來(lái)確定。 TSP 問(wèn)題的總結(jié) 對(duì)于 TSP，目前還不存在能找到完美解的方法，這個(gè)問(wèn)題是 NP 難的。因解題方法是使用的是計(jì)算每一對(duì)點(diǎn)，則我們編碼時(shí)將第一個(gè)節(jié)點(diǎn)單獨(dú)放入，合并成完整編碼。 outdistance = 0 2 7 1 3 6 10 5 12 11 14 2 0 5 3 1 4 8 3 10 9 12 7 5 0 7 4 1 5 6 7 6 9 1 3 7 0 4 8 9 6 11 10 13 3 1 4 4 0 3 7 2 9 8 11 6 4 1 8 3 0 4 5 6 5 8 10 8 5 9 7 4 0 9 2 1 4 5 3 6 6 2 5 9 0 7 8 9 12 10 7 11 9 6 2 7 0 1 2 11 9 6 10 8 5 1 8 1 0 3 14 12 9 13 11 8 4 9 2 3 0 路徑： b(i,j) i 表示起點(diǎn)， j 表示終點(diǎn)。 %帶權(quán)鄰接矩陣。 %找出終點(diǎn)在路線中的位置 pathlong(i)=0。 %因起點(diǎn)基因不能改變 temPm3=fix((rand(1)+)*10)。 %************ Step 4: 變異操作 ************** for i=1:Popsize tempPm=rand(1)。 [2]王小平、曹立明 .遺傳算法理論應(yīng)用與軟件實(shí)現(xiàn) [M].西安交通大學(xué)出版社 .2021 年 1月。 首先，誠(chéng)摯的感謝 陶 老師 對(duì)我論文的指導(dǎo)。 %變異交換 end end path(Popsize,:)=BestS。 path(i,d)=0。 %按照適應(yīng)度大小排序 Bestfi=Orderfi(Popsize)。 tempvary=[1 2 3 4 5 6 7 8 9 10 11]。 貴州大學(xué) 第 17 頁(yè) 第五章 附錄 5． 1 Matlab 程序代碼 clc。 第四：交叉 ， 因編碼是不重復(fù)的數(shù)字，所以采用傳統(tǒng)的交叉方法，即上一行與下一行對(duì)位交叉，會(huì)產(chǎn)生無(wú)效路徑，于是，采用了不同的交叉方法，具體如下： （ 1）在表示路徑的染色體 Tx 和 Ty 中，隨機(jī)選取兩個(gè)基因座（不能為起點(diǎn)基因座） i和 j, 即將 i個(gè)基因座和第 j 個(gè)基因座之間的各個(gè)基因 座定義為交叉域，并將交叉的內(nèi)容分別記憶為 temp1 和 temp2。通過(guò)保持邊的有用信息找到更好的算法，這是算法改進(jìn)的一個(gè)趨勢(shì)，同時(shí)為了防止局部收斂必須讓算法達(dá)到收斂性與群體多樣性的平衡。 1991 年， Stark weather 等提出了一種改進(jìn)的方法，在 ER 操作中不再保留父?jìng)€(gè)體中共同部分的序列。根據(jù)個(gè)體的適值拷貝位串意味著：具有高的適值的個(gè)體更大可能在下一代中產(chǎn)生一個(gè)或多個(gè)子孫。由于二進(jìn)制編碼具有如下的特點(diǎn)數(shù)據(jù)冗長(zhǎng)，并且表達(dá)能力有限，計(jì)算機(jī)無(wú)法承受如此巨大的計(jì)算量甚至根據(jù)調(diào)整不同的參數(shù)時(shí)，所運(yùn)行的時(shí)間，有時(shí)會(huì)達(dá)到近幾個(gè)小時(shí)，從時(shí)間效率來(lái)說(shuō)，工作效率實(shí)在是低下，并達(dá)到無(wú)法忍受的程度，所以實(shí)際中很少使用。 交叉 : 從種群中隨機(jī)選擇兩個(gè)染色體 , 按一定的概率進(jìn)行基因交換，交換位置 的選取是隨機(jī)的。基因雜交和基因突變可能產(chǎn)生對(duì)環(huán)境適應(yīng)性強(qiáng)的后代，通過(guò)優(yōu)勝劣汰的自然選擇，適應(yīng)值高的基因結(jié)構(gòu)就保存下來(lái)。s theory of evolution and Mendel39。 論文（設(shè)計(jì)）作者簽名： 日 期： 貴州大學(xué) 第 1 頁(yè) 目錄 第一章 緒 論 ........................................................... 4 第二章 遺傳算法介紹 ..................................................... 5 遺傳算法介紹 ...................................................... 5 遺傳算法的產(chǎn)生和發(fā)展 .............................................. 5 遺傳算法的基本求解步驟 ............................................ 6 編碼： ...................................................... 6 初始化： ..................................................... 6 估計(jì)適應(yīng)度： ................................................. 6 再生 (選擇 ): .................................................. 6 交叉 : ....................................................... 6 變異： ...................................................... 6 重復(fù)： ...................................................... 7 遺傳算法流程圖： ...........................................