1 内容介绍
巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲,使用穷举法不但可以求解TSP问题,而且还可以求出该问题的最优解。但是对现有的计算机来说,使用常规的穷举法在如此庞大的搜索空间中寻求最优解,几乎是不可能的。所以,各种求解TSP问题的优化算法应运而生了,本文所用到的遗传算法也在其中。遗传算法是一种高效智能搜索方法,并行遗传算法是遗传算法研究中的一个重要方向。并行遗传算法能够提供各种大型计算问题的解决方案。
2 部分代码
%遗传算法求解TSP问题
%D是距离矩阵，n为种群个数
%参数a是中国31个城市的坐标(初始给定)
%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定
%m为适值淘汰加速指数,最好取为1,2,3,4,不宜太大
%交叉概率Pc,变异概率Pm
%R为最短路径,Rlength为路径长度
function [R,Rlength]=geneticTSP(D,a,n,C,m,Pc,Pm)
[N,NN]=size(D);%(31*31)
farm=zeros(n,N);%用于存储种群
for i=1:n
farm(i,:)=randperm(N);%随机生成初始种群
end
R=farm(1,:);%一个随机解(个体)
%在二维图上画出所有点
scatter(a(:,1),a(:,2),'x');
hold on
pause(1)
%输出随机的解得路径和总距离
disp('初始种群中的一个随机值:')
R
Rlength=myLength(D,R)
disp('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~')
%计算各个个体总距离和适配置
%farm(1,:)=R;
len=zeros(n,1);%存储路径长度
fitness=zeros(n,1);%存储适配值
counter=0;
while counter<C
for i=1:n
len(i,1)=myLength(D,farm(i,:));%计算路径长度
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);%计算适应度
rr=find(len==minlen);%返回的是在len中路径最短的路径坐标(i,1)
R=farm(rr(1,1),:);%更新最短路径
FARM=farm;%优胜劣汰，nn记录了复制的个数
%选择,
nn=0;%nn-选择后种群数
for i=1:n
if fitness(i,1)>=rand
nn=nn+1;
FARM(nn,:)=farm(i,:);
end
end
FARM=FARM(1:nn,:); % FARM (nn*N)
[aa,bb]=size(FARM);%(aa=nn)
% 交叉操作
FARM2=FARM;
for i=1:2:aa
if Pc>rand&&i<aa %交叉概率Pc
A=FARM(i,:);
B=FARM(i+1,:);
[A,B]=intercross(A,B);
FARM(i,:)=A;
FARM(i+1,:)=B;
end
end
%交叉检验 (可省去)
for i=1:aa
if myLength(D,FARM(i,:))>myLength(D,FARM2(i,:))
FARM(i,:)=FARM2(i,:);
end
end
clear FARM2
[aa,bb]=size(FARM); %aa=nn2
% 变异
FARM2=FARM;
for i=1:aa
if Pm>=rand
FARM(i,:)=mutate(FARM(i,:));
end
end
%变异检验(可省略)
for i=1:aa
if myLength(D,FARM(i,:))>myLength(D,FARM2(i,:))
FARM(i,:)=FARM2(i,:);
end
end
clear FARM2
%群体的更新
FARM2=zeros(n-aa+1,N);
if n-aa>=1
for i=1:n-aa
FARM2(i,:)=randperm(N);%随机生成n-aa种群
end
end
FARM=[R;FARM;FARM2];%将随机产生的n-aa个体加入从后面种群,将上次迭代的最优解从前面加入种群
[aa,bb]=size(FARM);
%保持种群规模为n
if aa>n
FARM=FARM(1:n,:);
end
%更新farm
farm=FARM;
clear FARM
%更新迭代次数
counter=counter+1 ;
end
%结果输出
Rlength=myLength(D,R);
figure
plotaiwa(a,R)%画图
disp('迭代次数c');
disp(C);
disp('迭代后结果');
R
Rlength=myLength(D,R)%结果输出
3 运行结果
4 参考文献
[1]温清芳. 遗传算法求解TSP问题的MATLAB实现[J]. 韶关学院学报, 2007, 28(6):5.