遺傳算法編程求解TSP問題

1、遺傳算法編程求解TSP問題摘要 本文利用基本遺傳算法的思路尋找雙峰或多峰函數(shù)的最大值，選擇仍然采用輪盤選擇方法；交叉算法采用一個(gè)啟發(fā)式交叉算法，交叉位置隨機(jī)，該算法以一定的概率生成一個(gè)比父代好的解，交叉概率取0.1；變異概率0.005。經(jīng)多次運(yùn)行，求得最優(yōu)值。停止法則為循環(huán)最大遺傳代數(shù)為止，另外如果30代解沒有改進(jìn)則停止。的編程環(huán)境為Matlab6.5。關(guān)鍵字 遺傳算法 TSP遺傳算法是一種通用性非常強(qiáng)，計(jì)算性能非常好的算法，解決TSP問題卻存在很多問題，主要問題是解的可行性問題，在交叉，變異操作過(guò)程中，可能產(chǎn)生不可行的解，因此交叉和變異算子的設(shè)計(jì)是本程序的關(guān)鍵。本程序中交叉算子采用一個(gè)啟發(fā)式

2、交叉算法，該算法以一定概率計(jì)算出一個(gè)比父代好的子代算法思路：設(shè)父代F1：10 4 3 2 9 7 8 1 5 6 F2：9 1 3 5 2 6 7 8 4 10 。隨機(jī)確定交叉點(diǎn)，如4。查找F1中第四位為2。將F1向左旋轉(zhuǎn)3位，使第四位在成為第一位，得到F1：2 9 7 8 1 5 6 10 4 3。在F2中找到2所在位置，進(jìn)行類似旋轉(zhuǎn)，使2成為第一位，得到 F2：2 6 7 8 4 10 9 1 3 5。然后比較兩個(gè)模式中第一位與第二位的距離：disance(2-9)，disance(2-6)，取比較小的如2-6所在父代F2不變，另外一個(gè)為，將F1進(jìn)行旋轉(zhuǎn)操作，使6在第2位，得到F2:：2

3、6 10 4 3 9 7 8 1 5。這樣就形成了2 6 *的模式，如此往復(fù)，直到最后一位。另外將這個(gè)交叉算子的效率和普通單點(diǎn)交叉算子的效率進(jìn)行了比較，發(fā)現(xiàn)該方法確實(shí)使得算法搜索能力增強(qiáng)。多次運(yùn)行程序，得到一個(gè)相對(duì)好的解。以下是得到最優(yōu)解的數(shù)據(jù)：代數(shù)最優(yōu)值平均值-最 優(yōu) 解-126250857192648103241451059281374106338551271102348956441650947110829536540951175101348926641650447110829536740350561098172534841651347110829536944550610465892371

4、104145094871105329611453495487165239101238549571102348956134405185792103684114421500487110623951542249948101752396164215124871106239517421508487110623951837650476102348915194214934871106239520421491487110623952142149048711062395224214854871106239523385491711023489562428648148719523106252864624871952

5、310626286418487195231062728640448719523106282863984871952310629286413487195231063028640148719523106312864184871952310632286444487195231063328642148719523106342864094871952310635286398487195231063625741648719526103372864114871952310638286375487195231063925739248719526103402573804871952610341257370487

6、195261034225738148719526103432573804871952610344246315487192531064526430048719532106462642984871953210647286298487195231064826429648719532106492642994871953210650264296487195321065126432448719532106522643054871953210653264322487195321065426433148719532106552643104871953210656264294487195321065726430

7、048719532106582643094871953210659264297487195321066026431648719532106612643364871953210662264334487195321066326435048719532106642643314871953210665264315487195321066626433348719532106672463184871925310668264323487195321066925731148719526103702572954871952610371257293487195261037225731048719526103732

8、573104871952610374264305487195321067526429848719532106762442924871953102677257300487195261037826430848719532106792573264871952610380264307487195321068126429748719532106822642854871953210683264304487195321068426430448719532106852643164871953210686264320487195321068726430048719532106882633004871953261

9、089264295487195321069026428248719532106912642964871953210692264285487195321069326427948719532106942642774871953210695264279487195321069626428448719532106972442854871953102698263301487195326109926429248719532106264269487195321062642674871953210624426748719531026264280487195321062642804871953210626427

10、448719532106263294487195326102462834871925310624628148719253106264279487195321062572854871359210626430348719532106264300487195321062572924871359210625729748713592106257290487135921062572884871359210625729448713592106257300487135921062573094871359210625729848713592106257308487135921062643244871953210

11、6264305487195321062643234871953210626433048719532106263315487195326102643234871953210626430048719532106最短路徑為: 244最優(yōu)解為: 4 8 7 1 9 5 3 10 2 6代數(shù)： 76該問題采用禁忌搜索算法得到的最優(yōu)解為229。可見遺傳算法雖然是很好的方法，但是如果設(shè)計(jì)不好則不一定能夠收斂到全局最優(yōu)值，有文章也表明簡(jiǎn)單遺傳算法是不收斂的。遺傳算法的改進(jìn)方法有很多，但是究竟使用什么方法則需要具體問題具體分析，這正是遺傳算法的困難之處，雖然遺傳算法上手很快，但是要想設(shè)計(jì)出好的算法卻需要更多的努

12、力。本程序文件名為：SGA_TSP.m源程序如下：function SGA_TSP()%旅行商問題的遺傳算法解法disp('此次計(jì)算的距離矩陣如下')%此矩陣為一個(gè)演示矩陣，上面的代碼產(chǎn)生了一個(gè)隨機(jī)的距離矩陣，但又被此矩陣暫時(shí)覆蓋distance= Inf 76 45 81 34 99 12 70 10 21 76 Inf 61 72 2 9 100 84 19 5 45 61 Inf 44 15 96 83 86 80 40 81 72 44 Inf 98 21 53 46 41 16 34 2 15 98 Inf 23 8 99 13 57 99 9 96 21 23 In

13、f 70 87 89 8 12 100 83 53 8 70 Inf 73 24 84 70 84 86 46 99 87 73 Inf 90 82 10 19 80 41 13 89 24 90 Inf 41 21 5 40 16 57 8 84 82 41 Inf; %輸出距離矩陣 %遺傳算法開始gen_len=guimo; %基因長(zhǎng)度cross_probability=0.01;%交叉概率mutate_probability=0.005;%變異概率Maxgen=300; %最大遺傳代數(shù)NIND=gen_len*10; %個(gè)體數(shù)目%生成初始種群 關(guān)鍵是生成可行解Chrom=rand(NIN

14、D,gen_len);for i=1:NIND a indexa=sort(Chrom(i,:);%排序值是不會(huì)重復(fù)的 Chrom(i,:)=indexa; end%計(jì)算目標(biāo)函數(shù)值Obj(1:NIND)=0;for j=1:NIND for i=1:9 Obj(j)=Obj(j)+distance(Chrom(j,i),Chrom(j,i+1); end Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1);end%記錄每一代的最小值,平均值ma(1,1)=1;ma(1,2) index=min(Obj);most_min=ma(1,2);%全局最優(yōu)值mo

15、st_min_index=1;%種群平均值ma(1,3)=round(mean(Obj);ma(1,4:3+gen_len)=Chrom(index,:);for gen=1:Maxgen %終止判斷 %最近30代的最優(yōu)值都比前面的最優(yōu)值大則結(jié)束 if gen>29+most_min_index & gen>100 m n=find(ma(gen-30:gen,2)>most_min); if length(n)>29 break; end end %計(jì)算適應(yīng)度 mmm=max(Obj)+1; Obj=mmm-Obj+1; sumObj=sum(Obj);%所有

16、個(gè)體的目標(biāo)函數(shù)值之和 fitness=Obj/sumObj;%每個(gè)個(gè)體的選擇概率 fitness2=cumsum(fitness);%累計(jì)概率 %輪盤選擇 tempChrom=Chrom;%儲(chǔ)存一個(gè)原始的個(gè)體值 父代 index=1; for k=1:NIND for j=1:NIND if rand<fitness2(j) Chrom(index,:)=tempChrom(j,:); index=index+1; break; end end end %交叉運(yùn)算 關(guān)鍵是如何產(chǎn)生可行解 n1=0; for i=1:NIND if rand(1)<cross_probability

17、if n1=0 n1=1; temindex=i;%紀(jì)錄第一個(gè)交叉?zhèn)€體 continue; else %選夠兩個(gè)個(gè)體則交叉 temp1=Chrom(temindex,:);%記錄父代1 temp2=Chrom(i,:);%記錄父代2 Chrom(i,:)=tsp_cross_func1(temp1,temp1,distance);%TSP的一個(gè)啟發(fā)式交叉算法函數(shù)產(chǎn)生一個(gè)子代 %另一個(gè)子代從父代中繼承一個(gè)較好的 if Obj(i)>Obj(temindex) Chrom(temindex,:)=temp2; else Chrom(temindex,:)=temp1; end n1=0; e

18、nd end end %Chrom %檢查交叉運(yùn)算是否正確,解是否可行解 %變異運(yùn)算 實(shí)際上是交換位置 for i=1:NIND for j=1:gen_len if rand<mutate_probability value=round(rand*(gen_len-1)+1; tt=Chrom(i,value); Chrom(i,value)=Chrom(i,j); Chrom(i,j)=tt; end end end %計(jì)算目標(biāo)函數(shù)值 Obj(1:NIND)=0; for j=1:NIND for i=1:9 Obj(j)=Obj(j)+distance(Chrom(j,i),Chr

19、om(j,i+1); end Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1); end %記錄每一代的最小值,平均值 ma(gen+1,1)=gen+1; ma(gen+1,2) index=min(Obj); %各代種群平均值 ma(gen+1,3)=round(mean(Obj); ma(gen+1,4:3+gen_len)=Chrom(index,:); most_min index=min(ma(:,2); most_min_index=index;enddisp('計(jì)算過(guò)程中的最優(yōu)值記錄')disp('代數(shù) 最優(yōu)值

20、平均值 |最優(yōu)解-')disp(num2str(ma)best_Y =min(ma(:,2);str='最短路徑為: ' num2str(best_Y) ;disp(str)X=ma(index,4:3+gen_len);str='最優(yōu)解為: ' num2str(X) '代數(shù)： ' num2str(index);disp(str)function child=tsp_cross_func1(father1,father2,distance)%TSP的一個(gè)啟發(fā)式交叉算法函數(shù)%該算法以一定概率計(jì)算出一個(gè)比父代好的子代%算法思路：F1：10 4

21、 3 2 9 7 8 1 5 6 F2：9 1 3 5 2 6 7 8 4 10 。%隨機(jī)確定交叉點(diǎn)，如4,F1中第四位為2。%將F1向左旋轉(zhuǎn)3位，使第四位在成為第一位 F1：2 9 7 8 1 5 6 10 4 3。%在F2中找到2所在位置，進(jìn)行旋轉(zhuǎn)2成為第一個(gè) F2：2 6 7 8 4 10 9 1 3 5。%然后比較disance(2-9) disance(2-6),取比較小的如2-6所在父代F2,F2不變,%將F1的后9位旋轉(zhuǎn),使6在第2位 成為F2: 2 6 10 4 3 9 7 8 1 5%這樣就形成了2 6 *的模式,如此往復(fù),%演示的例子%distance= Inf 76 45 81 34 99 12 70 10 21% 76 Inf 61 72 2 9 100 84 19 5% 45 61 Inf 44 15 96 83 86 80 40 % 81 72 44 Inf 98 21 53 46 41 16% 34 2 15 98 Inf 23 8 99 13 57% 99 9 96 21 23 Inf 70 87 89 8% 12 100 83 53 8 70 Inf 73 24 84% 70 84 86 46 99 87 73 Inf 9