【正文】 ， 因采用自然編 碼，且產(chǎn)生的編碼不能重復(fù)，于是我采用了randperm 函數(shù)產(chǎn)生不重復(fù)的隨機自然數(shù)。因解題方法是使用的是計算每一對點，則我們編碼時將第一個節(jié)點單獨放入，合并成完整編碼。 因為節(jié)點有 11 個，可采用一個 1 行 11 列的矩陣儲存數(shù)據(jù)，同時，由于編號為數(shù)字，可直接使用數(shù)字編碼表示路徑的染色體。具體如下： 采用等長可變?nèi)旧w的方式，例如由 2到 9的路徑，染色體編碼可能為（ 2， 5， 1， 8，4， 6， 9， 3， 10， 7， 11），超過 9 之后的編碼，用來進行算子的運算，不具備實際意義。 第二：計算適應(yīng)度，因取最短路徑值， 即最小值，常用方法為 CF(x)或 C/F(x)（ C為一常數(shù)），此處采用前一種方式。于是，可進一步計算相對適應(yīng)度。 第三：選擇與復(fù)制 ， 采用輪盤賭算法，產(chǎn)生一個隨機值，比較它與累計相對適應(yīng)度的關(guān)系，從而選擇出優(yōu)良個體進入下一代。 第四：交叉 ， 因編碼是不重復(fù)的數(shù)字，所以采用傳統(tǒng)的交叉方法，即上一行與下一行對位交叉，會產(chǎn)生無效路徑，于是，采用了不同的交叉方法，具體如下： （ 1）在表示路徑的染色體 Tx 和 Ty 中，隨機選取兩個基因座（不能為起點基因座） i和 j, 即將 i個基因座和第 j 個基因座之間的各個基因 座定義為交叉域，并將交叉的內(nèi)容分別記憶為 temp1 和 temp2。 （ 2）根據(jù)交叉區(qū)域中的映射關(guān)系，在個體 Tx中找出所有與 temp2 相同的元素，在個體Ty中找出所有與 temp1 相同的元素，全部置為 0。 （ 3）將個體 Tx、 Ty 進行循環(huán)左移，遇到 0 就刪除，直到編碼串中交叉區(qū)域的左端不再有 0：然后將所有空位集中到交叉區(qū)域，而將交叉區(qū)域內(nèi)原有的基因依次向后移動。因0元素可能較多，在程序?qū)崿F(xiàn)時，我是將非零元素提出，后面再合成。 （ 4）將 temp2 插入到 Tx 的交叉區(qū)域， temp1 插入到 Ty 的交叉區(qū)域。形成新的染色體 [1]。 第五：變異 ， 染色體編碼為從 1 到 11 的無重復(fù)編碼，所以不能采用一般的生成一個隨機數(shù)替代的辦法。此處采用交換變異法。即隨機產(chǎn)生兩個數(shù)，交換兩個節(jié)點的順序。 貴州大學(xué) 第 15 頁 例： [ 1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10 , 11 ] , 1 3 , 2 8p K K? ? ? 則新染色體編碼為： [1 , 2 , 8 , 4 , 5 , 6 , 7, 3 , 9 , 10 , 11 ]p ? MATLAB 求解結(jié)果 距離矩陣： a(i,j) i 表示起點， j表示終點。 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 表示起點， j 表示終點。 outpath: 1 1,2 1,2,5,6,3 1,4 1,2,5 1,2,5,6 1,4,7 1,2,5,8 1,3,6,9 1,4,7,10 1,4,7,10,9,112,1 2 2,5,6,3 2,1,4 2,5 2,5,6 2,5,6,7 2,5,8 2,5,8,9 2,5,6,7,10 2,5,6,7,10,9,113,6,5,2,1 3,6,5,2 3 3,4 3,6,5 3,6 3,6,7 3,6,5,8 3,6,9 3,6,7,10 3,6,9,114,1 4,1,2 4,3 4 4,1,2,5 4,3,6 4,7 4,1,2,5,8 4,7,10,9 4,7,10 4,7,10,9,115,2,1 5,2 5,6,3 5,2,1,4 5 5,6 5,6,7 5,8 5,8,9 5,6,7,10 5,8,116,5,2,1 6,5,2 6,3 6,3,4 6,5 6 6,7 6,5,8 6,9 6,7,10 6,9,117,4,1 7,6,5,2 7,6,3 7,4 7,6,5 7,6 7 7,10,9,8 7,10,9 7,10 7,10,9,118,5,2,1 8,5,2 8,5,6,3 8,5,2,1,4 8,5 8,5,6 8,9,10,7 8 8,9 8,9,10 8,119,6,3,1 9,8,5,2 9,6,3 9,10,7,4 9,8,5 9,6 9,10,7 9,8 9 9,10 9,1110,7,4,1 10,7,6,5,2 10,7,6,3 10,7,4 10,7,6,5 10,7,6 10,7 10,9,8 10,9 10 10,9,1111,9,10,7,4,1 11,9,10,7,6,5,2 11,9,6,3 11,9,10,7,4 11,8,5 11,9,6 11,9,10,7 11,8 11,9 11,9,10 11 貴州大學(xué) 第 16 頁 4． 3 求解結(jié)果驗證與反思 此程序運算速度有待提高，程序的收斂速度不是很快?？赡艿?原因如下： （ 1） 在變異操作時，可能將本來很好的解棄掉，換來更差的染色體，導(dǎo)致收斂速度不佳。解決辦法：可以在變異操作時，增加個體求優(yōu)的自學(xué)習(xí)過程。即在某位基因變異后，計算新染色體的適應(yīng)函數(shù)值，若適應(yīng)值變大，即路徑更短，則保留；否則，保持原來的染色體不變。 （ 2） 算法的進一步改進，例如可加入 Floyd 算法的思想，在父代產(chǎn)生子代的過程中，不是單純的交叉，可以考慮隨機加入頂點是否路徑變短。 貴州大學(xué) 第 17 頁 第五章 附錄 5． 1 Matlab 程序代碼 clc。clear。 %初始化參數(shù) %注： popsize=200,MaxGeneration=100,約跑 2 分鐘。若不要求太精確，可減少循環(huán)次數(shù)。 pointnumber=11。 %節(jié)點個數(shù) Popsize=200。 %種群規(guī)模，只能取偶數(shù)（因 67 行的循環(huán)） MaxGeneration=100。 %最大代數(shù) Pc=。Pm=。 %交叉概率和變異概率 A=[0 2 8 1 50 50 50 50 50 50 50 2 0 6 50 1 50 50 50 50 50 50 8 6 0 7 50 1 50 50 50 50 50 1 50 7 0 50 50 9 50 50 50 50 50 1 50 50 0 3 50 2 50 50 50 50 50 1 50 3 0 4 50 6 50 50 50 50 50 9 50 4 0 50 50 1 50 50 50 50 50 2 50 50 0 7 50 9 50 50 50 50 50 6 50 7 0 1 2 50 50 50 50 50 50 1 50 1 0 4 50 50 50 50 50 50 50 9 2 4 0]。 %帶權(quán)鄰接矩陣。 A(A==50)=500。 %取值 50過小而修正為 500； Bestindividual=zeros(MaxGeneration,1)。 outdistance=zeros(11,11)。 outpath=cell(11,11)。 %用于存放 11 個點相互之間的最短路徑 貴州大學(xué) 第 18 頁 %****** 生成初始種群 ****** for a=1:pointnumber %起點的編號 %a=1。 tempvary=[1 2 3 4 5 6 7 8 9 10 11]。 tempvary(a)=[]。 %暫時剔除起點 tempm