%遗传算法求解TSP程序
clear;
time1 = clock; %观察时间
%设置输入参数
popsize = 200; %群体规模,为偶数
Lchrom = 144; %染色体长度，这里即为城市个数
probcross = 0.9; %交叉概率
probmuta = 0.001; %变异概率
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%取得城市坐标
temp = load('D:\作业和实验\遗传算法\Homeworks\tsp144.txt','r');
xPos = temp(1:144,1)';
yPos = temp(1:144,2)';
plot(xPos,yPos,'o');axis([0 80 0 90]); %画出输入点
grid on;xlabel('x');ylabel('y');title('城市坐标');
%随机选取一组初始群体
for j=1:popsize
startPop(j,1:Lchrom) = randperm(Lchrom); %随机排序,以n城市的遍历次序作为算法的编码
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
done = 0;
gen = 0;
while(~done)
%计算适应度,适应度函数取路径长度Td的倒数,若结合TSP的约束条件(每个城市经过且只经过一次),则适应度函数可
%表示为:f=1/(Td+k*Nt),其中Nt是对TSP路径不合法的度量,k为惩罚系数.本实验只采用f=1/Td.
for i=1:popsize
fittemp1(i) = 0;
for j=1:Lchrom-1
fittemp1(i) = fittemp1(i) + (xPos(startPop(i,j+1))-xPos(startPop(i,j)))^2 + (yPos(startPop(i,j+1))-yPos(startPop(i,j)))^2; %两城市距离
end
fittemp2(i) = (xPos(startPop(i,Lchrom))-xPos(startPop(i,1)))^2 + (yPos(startPop(i,Lchrom))-yPos(startPop(i,1)))^2;
T = sqrt(fittemp1(i) + fittemp2(i));
singlefit(i) = 1/T; %单个个体适应度
end %适应度结束
totalfit = sum(singlefit); %总体适应度
plot(gen,max(singlefit),'r*');
hold on;
drawnow;
%赌轮方法选择select
prob=cumsum(singlefit/totalfit);
rNums=sort(rand(popsize,1)); %Generate random numbers
fitIn=1;newIn=1;
while newIn<=popsize
if(rNums(newIn)<prob(fitIn))
endPop(newIn,:) = startPop(fitIn,:);
newIn = newIn+1;
else
fitIn = fitIn + 1;
end
end %选择结束
%交叉，类似于OX交叉方式
for i1=1:popsize/2
ac = round(rand.*popsize + 0.5); %产生1到popsize的随机数
bc = round(rand.*popsize + 0.5);
p1 = endPop(ac,:); %选择两个父代
p2 = endPop(bc,:);
while(p1==p2) %保证每次用两个不同的父代进行交叉
ac = round(rand.*popsize + 0.5); %产生1到popsize的随机数
bc = round(rand.*popsize + 0.5);
p1 = endPop(ac,:);
p2 = endPop(bc,:);
end
%用交叉概率判断是否要进行交叉操作
probtemp = rand;
if(probcross<probtemp) %如果交叉概率小于随机概率不进行交叉
child1 = p1;
child2 = p2;
else %否则进行交叉
pos1 = round(rand.*Lchrom + 0.5); %产生交叉点pos1,pos2，交叉点从1到Lchrom
pos2 = round(rand.*Lchrom + 0.5);
pos1 = min(pos1,pos2);
pos2 = max(pos1,pos2);
cutlength = pos2 - pos1 + 1;
%产生子代
childtemp1 = [p2(pos1:pos2) p1];
childtemp2 = [p1(pos1:pos2) p2];
for i=(cutlength+1):(Lchrom+cutlength) %将子代1相同的城市码删除
for j=1:cutlength
if(childtemp1(i)==childtemp1(j))
childtemp1(i) = 0;
end
end
end
for i=(cutlength+1):(Lchrom+cutlength) %将子代2相同的城市码删除
for j=1:cutlength
if(childtemp2(i)==childtemp2(j))
childtemp2(i) = 0;
end
end
end
end
k=1;
for i=1:(cutlength+Lchrom)
if(childtemp1(i)>0)
childtemp11(k) = childtemp1(i);
k=k+1;
end
end
k=1;
for i=1:(Lchrom+cutlength)
if(childtemp2(i)>0)
childtemp22(k) = childtemp2(i);
k=k+1;
end
end
endPop(ac,:) = childtemp11(1:Lchrom);
endPop(bc,:) = childtemp22(1:Lchrom);
end %交叉结束
%1，交换变异
for i = 1:popsize
am = round(rand.*popsize + 0.5); %选择一个父代
cm = endPop(am,:);
probtemp = rand;
if(probmuta<probtemp) %不进行变异
cm = cm;
else %否则进行变异
%换位
ivePos1 = round(rand.*Lchrom + 0.5);
ivePos2 = round(rand.*Lchrom + 0.5);
mutatemp1 = cm(ivePos1);
cm(ivePos1) = cm(ivePos2);
cm(ivePos2) = mutatemp1;
end
endPop(am,:) = cm;
end %交换变异结束
%2:逆转变异
for i = 1:popsize
%am = round(rand.*popsize + 0.5); %Pick a parent
cm = endPop(i,:);
%计算父代适应度
cmfittemp1 = 0;
for j=1:Lchrom-1
cmfittemp1 = cmfittemp1 + (xPos(cm(j+1))-xPos(cm(j)))^2 + (yPos(cm(j+1))-yPos(cm(j)))^2; %两城市距离
end
cmfittemp2 = (xPos(cm(Lchrom))-xPos(cm(1)))^2 + (yPos(cm(Lchrom))-yPos(cm(1)))^2;
T = sqrt(cmfittemp1 + cmfittemp2);
cmFatherfit = 1/T;
%逆转
for q=1:40
ivePos1 = round(rand.*Lchrom + 0.5);
ivePos2 = round(rand.*Lchrom + 0.5);
maxinvese = max(ivePos1,ivePos2);
mininvese = min(ivePos1,ivePos2);
cm(mininvese:maxinvese) = cm(maxinvese:-1:mininvese);
%计算逆转后cm适应度
cmfittemp1 = 0;
for j=1:Lchrom-1
cmfittemp1 = cmfittemp1 + (xPos(cm(j+1))-xPos(cm(j)))^2 + (yPos(cm(j+1))-yPos(cm(j)))^2; %两城市距离
end
cmfittemp2 = (xPos(cm(Lchrom))-xPos(cm(1)))^2 + (yPos(cm(Lchrom))-yPos(cm(1)))^2;
T = sqrt(cmfittemp1 + cmfittemp2);
cmSonfit = 1/T; %单个个体适应度
if(cmSonfit>cmFatherfit) %在逆转变异中引入局部搜索
endPop(i,:) = cm;
cmFatherfit = cmSonfit;
else
cm = endPop(i,:);
end
end
end %逆转变异结束
%计算适应度，若子代的个体的最高适应度大于父代个体的最高适应度，则用子代代替父代
for i=1:popsize
fittemp1(i) = 0;
for j=1:Lchrom-1
fittemp1(i) = fittemp1(i) + (xPos(endPop(i,j+1))-xPos(endPop(i,j)))^2 + (yPos(endPop(i,j+1))-yPos(endPop(i,j)))^2; %两城市距离
end
fittemp2(i) = (xPos(endPop(i,Lchrom))-xPos(endPop(i,1)))^2 + (yPos(endPop(i,Lchrom))-yPos(endPop(i,1)))^2;
T = sqrt(fittemp1(i) + fittemp2(i));
newsinglefit(i) = 1/T; %单个个体适应度
end
newtotalfit = sum(newsinglefit); %总体适应度
if(max(newsinglefit) > max(singlefit))
maxsinglefit = max(singlefit);
startPop1 = startPop;
for p=1:1%popsize*0.05
[bestfather,position] = max(singlefit); %最佳保留策略，取出父代个体中适应度最高的个体，直接代替子代中适应度最低的个体
[worstson,position1] = min(newsinglefit);
endPop(position1,:) = startPop1(position,:);
singlefit(position) = 0;
startPop1(position,:) = 0;
end
startPop = endPop;
else
startPop = startPop;
end
gen = gen + 1;
if(gen>2500)
done = 1;
end
end %主循环结束
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%计算适应度
for i=1:popsize
fittemp1(i) = 0;
for j=1:Lchrom-1
fittemp1(i) = fittemp1(i) + (xPos(startPop(i,j+1))-xPos(startPop(i,j)))^2 + (yPos(startPop(i,j+1))-yPos(startPop(i,j)))^2; %两城市距离
end
fittemp2(i) = (xPos(startPop(i,Lchrom))-xPos(startPop(i,1)))^2 + (yPos(startPop(i,Lchrom))-yPos(startPop(i,1)))^2;
T = sqrt(fittemp1(i) + fittemp2(i));
singlefit(i) = 1/T; %单个个体适应度
end
totalfit = sum(singlefit); %总体适应度
plot(gen,max(singlefit),'r*');
xlabel('经过代数');ylabel('个体最高适应度');
drawnow;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%用line()函数画线
[best,position] = max(singlefit);
plot(gen,best,'b*');
figure;
