本程序求解常見的組合優化問題TSP問題，如果僅僅是用一個程序去求解一個優化問題，顯然這樣的工作意義并不大。主要是因為求解的好壞往往是很難評價的，另外尤其對于遺傳算法來說，遺傳算法交叉

變異方法不同，交叉率，變異率等參數選擇的不同，對結果都有很大的影響。我們采用如下的一個30個城市的TSP問題benckmark問題，最優解為423.7，30個城市的坐標如下

41

94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18

54;22 60;83 46;91 38;25 38; 24 42;58 69;71

71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4

50

%以遺傳算法求解30個城市的TSP問題

%程序主要變量表

%A(30,2) 存放30個城市的坐標 ?zhongqun(100,30)存放種群規模100的父代

%k 總的循環迭代次數 ?zhongqun1(200,30)存放父代和交叉之后的子代

%n1 n2 隨機選擇交叉的兩個個體

%gene1 geng2 隨機選擇兩點交叉的兩個交叉位置

%zxh1 父代1的子回路 ?zxh_1

排序完成后子代1的子回路

%zxh2 父代2的子回路 ?zxh_2

排序完成后子代2的子回路

%bianyi(200,1) 變異參數 小于變異概率 該個體就發生變異

%bianyi1 ?bianyi2

變異時交換編碼的位置

%bianyilv 小于變異概率的個體發生變異

%din(1,200)存放父代與子代的適值函數 由小到大

tic;%統計程序的運行時間

A=[41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83

69;64 60;18 54;22 60;83 46;91 38;25 38;

24 42;58 69;71 71;74

78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50];%輸入數據

TSP問題中30個城市的坐標

chushi=rand(100,30);%生產初始矩陣 存放初始解

for i=1:1:100

zhongqun(i,1:1:30)=1:1:30;

end

for i=1:1:50%生產初始解 對0到1之間的隨機數進行排序 來確定初始解

for k=1:1:30

for j=1:1:29

if(chushi(i,j)>chushi(i,j+1))%排序

temp=chushi(i,j);

chushi(i,j)=chushi(i,j+1);

chushi(i,j+1)=temp;

temp=zhongqun(i,j);

zhongqun(i,j)=zhongqun(i,j+1);

zhongqun(i,j+1)=temp;

end

end

end

end

for k1=1:1:300%迭代次數

%交叉開始 采用子巡回交換交叉方式

zhongqun1=zeros(200,30);% 存放父代和交叉之后的子代

zhongqun1(1:100,1:end)=zhongqun;%前100個存放父代

for k=1:2:99%交叉開始

gene1=ceil(30*rand(1));%兩點交叉的第一個節點

gene2=ceil(gene1*rand(1));%兩點交叉的第二個節點

n1=ceil(100*rand(1));%隨機選擇從父代中選擇兩個個體

n2=ceil(100*rand(1));%隨機選擇從父代中選擇兩個個體

zhongqun1(k+100,1:1:gene2)=zhongqun(n1,1:1:gene2);%交叉

zhongqun1(k+101,1:1:gene2)=zhongqun(n2,1:1:gene2);%交叉

zxh1=zhongqun(n1,(gene2+1):1:gene1);%存放父代1的子巡回

zxh_1=zeros(1,gene1-gene2);%存放子代1的子巡回

i1=1;

%以父代2的次序 對父代1的子巡回編碼進行排序 得到子代1的子巡回

for i1=1:1:(gene1-gene2)

for i=1:1:30

if(zhongqun(n2,i)==zxh1(i1))

zxh_1(i1)=i;

end

end

end

for i1=1:1:(gene1-gene2)

for i=1:1:(gene1-gene2-1)

if(zxh_1(i)

temp=zxh_1(i);

zxh_1(i)=zxh_1(i+1);

zxh_1(i+1)=temp;

temp=zxh1(i);

zxh1(i)=zxh1(i+1);

zxh1(i+1)=temp;

end

end

end

zhongqun1(k+100,(gene2+1):1:gene1)=zxh1;

zxh2=zhongqun(n2,(gene2+1):1:gene1);%存放父代2的子巡回

zxh_2=zeros(1,gene1-gene2);%存放子代2的子巡回

i1=1;

%以父代1的次序 對父代2的子巡回編碼進行排序 得到子代2的子巡回

for i1=1:1:(gene1-gene2)

for i=1:1:30

if(zhongqun(n1,i)==zxh2(i1))

zxh_2(i1)=i;

end

end

end

for i1=1:1:(gene1-gene2)

for i=1:1:(gene1-gene2-1)

if(zxh_2(i)

temp=zxh_2(i);

zxh_2(i)=zxh_2(i+1);

zxh_2(i+1)=temp;

temp=zxh2(i);

zxh2(i)=zxh2(i+1);

zxh2(i+1)=temp;

end

end

end

zhongqun1(k+101,(gene2+1):1:gene1)=zxh2;

zhongqun1(k+100,(gene1+1):1:30)=zhongqun(n1,(gene1+1):1:30);%交叉

zhongqun1(k+101,(gene1+1):1:30)=zhongqun(n2,(gene1+1):1:30);%交叉

end

%變異開始 采用交換變異方式

bianyi=rand(200,1);%生產變異參數 來判斷是否變異

bianyi1=ceil(30*rand(1));%生成隨機數 用來確定 變異的時候交換哪兩個位置的編碼

bianyi2=ceil(30*rand(1));%生成隨機數

if(k1<50)

bianyilv=0.1;%自適應的修改變異概率當迭代初期選擇大的變異概率

end

if((k1<=100)&&(k1>=50))

bianyilv=0.05;%自適應的修改變異概率

end

if(k1>100)

bianyilv=0.02;%自適應的修改變異概率 當迭代末期選擇小的變異概率

end

for i=1:1:200

if(bianyi(i)

tempb=zhongqun1(i,bianyi1);%交換

zhongqun1(i,bianyi1)=zhongqun1(i,bianyi2);

zhongqun1(i,bianyi1)=tempb;

end

end

din=zeros(200,1);%存放父代和子代的適值函數

for i=1:1:200%計算適值函數

for j=1:1:29

din(i)=din(i)+sqrt((A(zhongqun1(i,j),1)-A(zhongqun1(i,j+1),1))^2+(A(zhongqun1(i,j),2)-A(zhongqun1(i,j+1),2))^2);%計算距離

end

din(i)=din(i)+sqrt((A(zhongqun1(i,1),1)-A(zhongqun1(i,30),1))^2+(A(zhongqun1(i,1),2)-A(zhongqun1(i,30),2))^2);%計算起點與終點距離

end

xuanze=1:1:200;

%對父代與子代的個體適值函數由小到大排序

for i=1:1:200

for j=1:1:199

if(din(j)>din(j+1))

tempx=din(j+1);

din(j+1)=din(j);

din(j)=tempx;

tempx1=xuanze(j+1);

xuanze(j+1)=xuanze(j);

xuanze(j)=tempx1;

end

end

end

%保持種群規模不變 只選擇其中適值函數較小的100個 做為下一次迭代的父代

for i=1:1:100

zhongqun(i,1:end)=zhongqun1(xuanze(i),1:end);

end

%畫圖程序

plot(k1,din(1),'*'),hold on

,xlabel('迭代次數'),ylabel('計算結果'),title('種群數=50')

end

fprintf('計算結果=%f\n',din(1));

toc;

總結

以上是生活随笔為你收集整理的ga tsp matlab,遗传算法（GA）求解TSP问题MATLAB程序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。