【正文】 最后， 再次 感謝 陶 老師 您 能夠在百忙之中對(duì)我的論文進(jìn)行精心地指導(dǎo)。在 論文的寫作過(guò)程中，他們給了我很多寶貴建議，在此一并致以最誠(chéng)摯的謝意。 首先，誠(chéng)摯的感謝 陶 老師 對(duì)我論文的指導(dǎo)。 [6]康曉軍，王茂才 .基于遺傳算法的最短路徑問(wèn)題的求解 .計(jì)算機(jī)工程與應(yīng)用[J],2021,44(23)。 [4]張文修、梁怡 .遺傳算法數(shù)學(xué)基礎(chǔ) [M].西安交通大學(xué)出版社 .2021 年 5月。 [2]王小平、曹立明 .遺傳算法理論應(yīng)用與軟件實(shí)現(xiàn) [M].西安交通大學(xué)出版社 .2021 年 1月。39。 %實(shí)現(xiàn)距離的對(duì)稱 outpath{i,j}=fliplr(outpath{j,i})。 %將最短距離寫入矩陣 outpath{a,b}=Bestpath。 %找出終點(diǎn) Bestpath=BestS(1:bb)。 %變異交換 end end path(Popsize,:)=BestS。 %交換前用一臨時(shí)容器存放數(shù)據(jù) path(i,temPm6)=path(i,temPm7)。 temPm7=fix((rand(1)+)*10)。 %************ Step 4: 變異操作 ************** for i=1:Popsize tempPm=rand(1)。 path(i+1,:)=[v2(1:temPm41) temp1 v2(temPm41+size(temp2):end)]。 v2=path(i+1,m)。 v1=path(i,h)。 貴州大學(xué) 第 20 頁(yè) path(i+1,f)=0。 path(i,d)=0。 %將兩點(diǎn)之間的基因儲(chǔ)存，方便交叉 temp2=path(i+1,temPm4:temPm5)。 temPm5=max(temPm2,temPm3)。 %因起點(diǎn)基因不能改變 temPm3=fix((rand(1)+)*10)。 for i=1:2:row tempP2=rand(1)。 end end path(i,:)=temppath(j,:)。 for i=1:Popsize tempP=rand(1)。 %記錄每一代中最優(yōu)個(gè)體的路線 %****** Step 2 : 選擇與復(fù)制操作 ****** temppath=path。 %按照適應(yīng)度大小排序 Bestfi=Orderfi(Popsize)。 %****** Step 1 : 選擇最優(yōu)個(gè)體 ****** Bestindividual(k)=min(pathlong)。 end end %計(jì)算適應(yīng)度 Fitness=length(A)*max(max(A))pathlong。 %找出終點(diǎn)在路線中的位置 pathlong(i)=0。 for b=a:pointnumber %終點(diǎn)的編號(hào) %b=10。 %生成一系列剔除起點(diǎn)的隨機(jī)路線 end path=[tempmatrix path]。 %聲明矩陣大小，避免減慢速度 for i=1:Popsize temprand=randperm(pointnumber1)。 %暫時(shí)剔除起點(diǎn) tempmatrix=a*ones(Popsize,1)。 tempvary=[1 2 3 4 5 6 7 8 9 10 11]。 outpath=cell(11,11)。 %取值 50過(guò)小而修正為 500； Bestindividual=zeros(MaxGeneration,1)。 %帶權(quán)鄰接矩陣。Pm=。 %種群規(guī)模，只能取偶數(shù)（因 67 行的循環(huán)） MaxGeneration=100。 pointnumber=11。 %初始化參數(shù) %注： popsize=200,MaxGeneration=100,約跑 2 分鐘。 貴州大學(xué) 第 17 頁(yè) 第五章 附錄 5． 1 Matlab 程序代碼 clc。即在某位基因變異后，計(jì)算新染色體的適應(yīng)函數(shù)值，若適應(yīng)值變大，即路徑更短，則保留；否則，保持原來(lái)的染色體不變?？赡艿?原因如下： （ 1） 在變異操作時(shí)，可能將本來(lái)很好的解棄掉，換來(lái)更差的染色體，導(dǎo)致收斂速度不佳。 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)。即隨機(jī)產(chǎn)生兩個(gè)數(shù)，交換兩個(gè)節(jié)點(diǎn)的順序。 第五：變異 ， 染色體編碼為從 1 到 11 的無(wú)重復(fù)編碼，所以不能采用一般的生成一個(gè)隨機(jī)數(shù)替代的辦法。 （ 4）將 temp2 插入到 Tx 的交叉區(qū)域， temp1 插入到 Ty 的交叉區(qū)域。 （ 3）將個(gè)體 Tx、 Ty 進(jìn)行循環(huán)左移，遇到 0 就刪除，直到編碼串中交叉區(qū)域的左端不再有 0：然后將所有空位集中到交叉區(qū)域，而將交叉區(qū)域內(nèi)原有的基因依次向后移動(dòng)。 第四：交叉 ， 因編碼是不重復(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。于是，可進(jìn)一步計(jì)算相對(duì)適應(yīng)度。具體如下： 采用等長(zhǎng)可變?nèi)旧w的方式，例如由 2到 9的路徑，染色體編碼可能為（ 2， 5， 1， 8，4， 6， 9， 3， 10， 7， 11），超過(guò) 9 之后的編碼，用來(lái)進(jìn)行算子的運(yùn)算，不具備實(shí)際意義。因解題方法是使用的是計(jì)算每一對(duì)點(diǎn)，則我們編碼時(shí)將第一個(gè)節(jié)點(diǎn)單獨(dú)放入，合并成完整編碼。這樣周而復(fù)始，群體中個(gè)體適應(yīng)度不斷提高，直到滿足一定的條件。觀察本題可發(fā)現(xiàn)，所有節(jié)點(diǎn)都是可雙向行走，則可只計(jì)算 i到 j的路徑與距離，然后將矩陣按主對(duì)角線翻折即可得到全部數(shù)據(jù)。 問(wèn)題要求求出任意兩點(diǎn)間的最短路徑， Floyd 算法采用的是在兩點(diǎn)間嘗試插入頂點(diǎn)，比較距離長(zhǎng)短的方法。要求設(shè)計(jì)遺傳算法對(duì)該問(wèn)題求解。通過(guò)保持邊的有用信息找到更好的算法，這是算法改進(jìn)的一個(gè)趨勢(shì)，同時(shí)為了防止局部收斂必須讓算法達(dá)到收斂性與群體多樣性的平衡。 總之，對(duì)于 TSP 問(wèn)題，可從問(wèn)題的編碼及遺傳算子設(shè)計(jì)方面來(lái)改進(jìn)發(fā)展遺傳算 法。對(duì)于復(fù)雜優(yōu)化問(wèn)題，單一機(jī)制的優(yōu)化算法很難實(shí)現(xiàn)全局優(yōu)化，且效率較低。 TSP 問(wèn)題的總結(jié) 對(duì)于 TSP，目前還不存在能找到完美解的方法，這個(gè)問(wèn)題是 NP 難的。簡(jiǎn)單的倒位操作，即首先在父?jìng)€(gè)體中隨機(jī)地選擇兩截?cái)帱c(diǎn)，然后將該兩點(diǎn)所夾的子串中的城市進(jìn)行反序。在變異操作中，變異率不能取得太大。變異是沿著個(gè)體字符空間的隨機(jī)移動(dòng)，當(dāng)它有節(jié)制地和交叉一起使用時(shí)，它就是一種防止過(guò)度成熟而丟失重要概念的保險(xiǎn)策略。 變異算子 盡管復(fù)制 和交叉操作很重要 ,在遺傳算法中是第一位的 ,但不能保證不會(huì)遺漏一些重要