gatspmatlab,遗传算法（GA）求解TSP问题MATLAB程序

本程序求解常见的组合优化问题TSP问题&＃xff0c;如果仅仅是用一个程序去求解一个优化问题&＃xff0c;显然这样的工作意义并不大。主要是因为求解的好坏往往是很难评价的&＃xff0c;另外尤其对于遗传算法来说&＃xff0c;遗传算法交叉

变异方法不同&＃xff0c;交叉率&＃xff0c;变异率等参数选择的不同&＃xff0c;对结果都有很大的影响。我们采用如下的一个30个城市的TSP问题benckmark问题&＃xff0c;最优解为423.7&＃xff0c;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&＃61;[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&＃61;rand(100,30);%生产初始矩阵 存放初始解

for i&＃61;1:1:100

zhongqun(i,1:1:30)&＃61;1:1:30;

end

for i&＃61;1:1:50%生产初始解 对0到1之间的随机数进行排序 来确定初始解

for k&＃61;1:1:30

for j&＃61;1:1:29

if(chushi(i,j)>chushi(i,j&＃43;1))%排序

temp&＃61;chushi(i,j);

chushi(i,j)&＃61;chushi(i,j&＃43;1);

chushi(i,j&＃43;1)&＃61;temp;

temp&＃61;zhongqun(i,j);

zhongqun(i,j)&＃61;zhongqun(i,j&＃43;1);

zhongqun(i,j&＃43;1)&＃61;temp;

end

end

end

end

for k1&＃61;1:1:300%迭代次数

%交叉开始 采用子巡回交换交叉方式

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

zhongqun1(1:100,1:end)&＃61;zhongqun;%前100个存放父代

for k&＃61;1:2:99%交叉开始

gene1&＃61;ceil(30*rand(1));%两点交叉的第一个节点

gene2&＃61;ceil(gene1*rand(1));%两点交叉的第二个节点

n1&＃61;ceil(100*rand(1));%随机选择从父代中选择两个个体

n2&＃61;ceil(100*rand(1));%随机选择从父代中选择两个个体

zhongqun1(k&＃43;100,1:1:gene2)&＃61;zhongqun(n1,1:1:gene2);%交叉

zhongqun1(k&＃43;101,1:1:gene2)&＃61;zhongqun(n2,1:1:gene2);%交叉

zxh1&＃61;zhongqun(n1,(gene2&＃43;1):1:gene1);%存放父代1的子巡回

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

i1&＃61;1;

%以父代2的次序 对父代1的子巡回编码进行排序 得到子代1的子巡回

for i1&＃61;1:1:(gene1-gene2)

for i&＃61;1:1:30

if(zhongqun(n2,i)&＃61;&＃61;zxh1(i1))

zxh_1(i1)&＃61;i;

end

end

end

for i1&＃61;1:1:(gene1-gene2)

for i&＃61;1:1:(gene1-gene2-1)

if(zxh_1(i)

temp&＃61;zxh_1(i);

zxh_1(i)&＃61;zxh_1(i&＃43;1);

zxh_1(i&＃43;1)&＃61;temp;

temp&＃61;zxh1(i);

zxh1(i)&＃61;zxh1(i&＃43;1);

zxh1(i&＃43;1)&＃61;temp;

end

end

end

zhongqun1(k&＃43;100,(gene2&＃43;1):1:gene1)&＃61;zxh1;

zxh2&＃61;zhongqun(n2,(gene2&＃43;1):1:gene1);%存放父代2的子巡回

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

i1&＃61;1;

%以父代1的次序 对父代2的子巡回编码进行排序 得到子代2的子巡回

for i1&＃61;1:1:(gene1-gene2)

for i&＃61;1:1:30

if(zhongqun(n1,i)&＃61;&＃61;zxh2(i1))

zxh_2(i1)&＃61;i;

end

end

end

for i1&＃61;1:1:(gene1-gene2)

for i&＃61;1:1:(gene1-gene2-1)

if(zxh_2(i)

temp&＃61;zxh_2(i);

zxh_2(i)&＃61;zxh_2(i&＃43;1);

zxh_2(i&＃43;1)&＃61;temp;

temp&＃61;zxh2(i);

zxh2(i)&＃61;zxh2(i&＃43;1);

zxh2(i&＃43;1)&＃61;temp;

end

end

end

zhongqun1(k&＃43;101,(gene2&＃43;1):1:gene1)&＃61;zxh2;

zhongqun1(k&＃43;100,(gene1&＃43;1):1:30)&＃61;zhongqun(n1,(gene1&＃43;1):1:30);%交叉

zhongqun1(k&＃43;101,(gene1&＃43;1):1:30)&＃61;zhongqun(n2,(gene1&＃43;1):1:30);%交叉

end

%变异开始 采用交换变异方式

bianyi&＃61;rand(200,1);%生产变异参数 来判断是否变异

bianyi1&＃61;ceil(30*rand(1));%生成随机数 用来确定 变异的时候交换哪两个位置的编码

bianyi2&＃61;ceil(30*rand(1));%生成随机数

if(k1<50)

bianyilv&＃61;0.1;%自适应的修改变异概率当迭代初期选择大的变异概率

end

if((k1<&＃61;100)&&(k1>&＃61;50))

bianyilv&＃61;0.05;%自适应的修改变异概率

end

if(k1>100)

bianyilv&＃61;0.02;%自适应的修改变异概率 当迭代末期选择小的变异概率

end

for i&＃61;1:1:200

if(bianyi(i)

tempb&＃61;zhongqun1(i,bianyi1);%交换

zhongqun1(i,bianyi1)&＃61;zhongqun1(i,bianyi2);

zhongqun1(i,bianyi1)&＃61;tempb;

end

end

din&＃61;zeros(200,1);%存放父代和子代的适值函数

for i&＃61;1:1:200%计算适值函数

for j&＃61;1:1:29

din(i)&＃61;din(i)&＃43;sqrt((A(zhongqun1(i,j),1)-A(zhongqun1(i,j&＃43;1),1))^2&＃43;(A(zhongqun1(i,j),2)-A(zhongqun1(i,j&＃43;1),2))^2);%计算距离

end

din(i)&＃61;din(i)&＃43;sqrt((A(zhongqun1(i,1),1)-A(zhongqun1(i,30),1))^2&＃43;(A(zhongqun1(i,1),2)-A(zhongqun1(i,30),2))^2);%计算起点与终点距离

end

xuanze&＃61;1:1:200;

%对父代与子代的个体适值函数由小到大排序

for i&＃61;1:1:200

for j&＃61;1:1:199

if(din(j)>din(j&＃43;1))

tempx&＃61;din(j&＃43;1);

din(j&＃43;1)&＃61;din(j);

din(j)&＃61;tempx;

tempx1&＃61;xuanze(j&＃43;1);

xuanze(j&＃43;1)&＃61;xuanze(j);

xuanze(j)&＃61;tempx1;

end

end

end

%保持种群规模不变 只选择其中适值函数较小的100个 做为下一次迭代的父代

for i&＃61;1:1:100

zhongqun(i,1:end)&＃61;zhongqun1(xuanze(i),1:end);

end

%画图程序

plot(k1,din(1),&＃39;*&＃39;),hold on

,xlabel(&＃39;迭代次数&＃39;),ylabel(&＃39;计算结果&＃39;),title(&＃39;种群数&＃61;50&＃39;)

end

fprintf(&＃39;计算结果&＃61;%f\n&＃39;,din(1));

toc;