遗传算法解旅行商(TSP)问题
%用遗传算法解TSP的主程序%一条染色体就是一条路线
clear,clc
%为了便于检查，城市均匀分布在圆周上
cityN=10;%城市数
chromosomeSum=100;%染色体数.注意，染色体数是偶数
radius=100;%圆周半径
minPath=2*sin(pi/cityN)*radius*cityN;%最短路径
circleN=500;%循环次数
precision=10;
%随机生成染色体
chromosomeGroup=randomChromosome(chromosomeSum,cityN);
holdBestChromosome=0;
holdLeastDistance=Inf;
compute=1;
circle=0;
while compute%开始迭代求解
circle=circle+1;
%%%%%%%%%%%%%%1：计算每条染色体的距离，也就是一条TSP距离
chromosomeCityDistance=chromosomeDisctance(chromosomeGroup,radius);
%%%%%%%%%%%%%%2：选择最好解对应的最优染色体
=best_worstChromosome(chromosomeGroup,chromosomeCityDistance);
%%%%%%%%%%%%%%3：保留每次迭代产生的最好的染色体
%本次最好解与上次最好解进行比较，如果上次最好解优于本次最好解，保留上次最好解；
%反之，保留本次最好解。保留的最好染色体放在holdBestChromosome中
...
=compareBestChromosome(holdBestChromosome,holdLeastDistance,...
bestChromosome,leastDistance);
if holdLeastDistance-minPath<precision
'程序结束'
circle
minPath
holdLeastDistance
holdBestChromosome
return
end
if circle>circleN
circle
minPath
holdLeastDistance
holdBestChromosome
return
end
%%%%%%%%%%%%%%4:把保留的最好的染色体holdBestChromosome加入到染色体群中
order=round(rand(1)*chromosomeSum);
if order==0
order=1;
end
fatherChromosomeGroup(order,:)=holdBestChromosome;
chromosomeCityDistance(order)=holdLeastDistance;
%%%%%%%%%%%%%%%5:为每一条染色体(即可能解的序号)定义一个概率(关键步骤)
%%%%%%%%%%%%%%%好的染色体概率高，坏的概率低。依据误差functionError计算概率
=chromosomeProbability(chromosomeCityDistance);
if trueP =='Fail'
'可能解严重不适应方程，请重新开始'
return%结束程序
end
%%%%%%%%%%%%%%%6：按照概率筛选染色体(关键步骤)
%从父染体中选择优秀染色体
selecteChromosomeGroup=selecteChromosome(chromosomeGroup,p);
%selecteChromosomeGroup=chromosomeGroup;
%%%%%%%%%%%%%%%7：染色体杂交(关键步骤)
half=chromosomeSum/2;
for i=1:half
...
=serchCross(selecteChromosomeGroup(i,:),selecteChromosomeGroup(chromosomeSum-i+1,:),4);
end
%%%%%%%%%%%%%%%%8:染色体变异
chromosomeGroup=mutant(selecteChromosomeGroup,0.5);
%chromosomeGroup=selecteChromosomeGroup;
end %函数1：计算每条染色体的距离，也就是一条TSP距离
function chromosomeCityDistance=chromosomeDisctance(chromosomeGroup,radius)
chromosomeN=size(chromosomeGroup,1);
cityN=size(chromosomeGroup(1,:),2);
centralAngle=2*pi/cityN;%相邻城市的圆心角
radius=radius;
for i=1:chromosomeN
distance=0;
for j=2:cityN
city2angle=abs(chromosomeGroup(i,j)-chromosomeGroup(i,j-1))*centralAngle;
%计算路线上两个城市之间的角度
if city2angle>pi
city2angle=2*pi-city2angle;%角度换算到pi以内
end
city2distance=radius*sin(city2angle/2)*2;%计算城市间的距离
distance=distance+city2distance;
end
city2angle=abs(chromosomeGroup(i,j)-chromosomeGroup(i,1))*centralAngle;
%计算头尾两个城市的角度
if city2angle>pi
city2angle=2*pi-city2angle;%角度换算到pi以内
end
city2distance=radius*sin(city2angle/2)*2;%计算城市间的距离
distance=distance+city2distance;
chromosomeCityDistance(i,1)=distance;
end %函数2：选择最好解对应的最优染色体
%找出最小误差所对应的最好染色体，最大误差所对应的最坏染色体
function =best_worstChromosome(chromosomeGroup,functionError)
=min(functionError);
%=max(functionError);
bestChromosome=chromosomeGroup(minErrorOrder,:);
%worstChromosome=chromosomeGroup(maxErrorOrder,:); %函数3：保留每次迭代产生的最好的染色体
%选择最好的基因保留下来
function ...
=compareBestChromosome(oldBestChromosome,oldLeastFunctionError,...
bestChromosome,leastFunctionError)
if oldLeastFunctionError>leastFunctionError
newLeastFunctionError=leastFunctionError;
newBestChromosome=bestChromosome;
else
newLeastFunctionError=oldLeastFunctionError;
newBestChromosome=oldBestChromosome;
end %函数4:为每一条染色体(即可能解的序号)定义一个概率(关键步骤)
%根据待解的非线性函数的误差计算染色体的概率
function =chromosomeProbability(x_Error)
InfN=sum(isinf(x_Error));%估计非线性方程计算的结果
NaNN=sum(isnan(x_Error));
if InfN>0 || NaNN>0
isP='Fail';
p=0;
return
else
isP='True';
errorReciprocal=1./x_Error;
sumReciprocal=sum(errorReciprocal);
p=errorReciprocal/sumReciprocal;%p:可能解所对应的染色体的概率
end %函数5：按照概率筛选染色体(关键步骤)
function chromosome=selecteChromosome(chromosomeGroup,p)
cumuP=cumsum(p);%累积概率,也就是把每个染色体的概率映射到0~1的区间
=size(chromosomeGroup);
for i=1:chromosomeSum%这个循环产生概率值
rN=rand(1);
if rN==1
chromosome(i,:)=chromosomeGroup(chromosomeSum,:);
elseif (0<=rN) && (rN<cumuP(1))
chromosome(i,:)=chromosomeGroup(1,:);%第1条染色体被选中
else
for j=2:chromosomeSum%这个循环确定第1条以后的哪一条染色体被选中
if (cumuP(j-1)<=rN) && (rN<cumuP(j))
chromosome(i,:)=chromosomeGroup(j,:);
break
end
end
end
end %函数6：染色体杂交(关键步骤)
function sonChromosome=crossChromosome(fatherChromosome,parameter)
=size(fatherChromosome);
%chromosomeSum:染色体的条数；chromosomeLength：染色体的长度
switch parameter
case 1%随机选择父染色体进行交叉重组
for i=1:chromosomeSum/2
crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
randChromosomeSequence1=round(rand(1)*chromosomeSum);
%随机产生第1条染色体的序号
randChromosomeSequence2=round(rand(1)*chromosomeSum);
%随机产生第2条染色体的序号，这两条染色体要进行杂交
if randChromosomeSequence1==0%防止产生0序号
randChromosomeSequence1=1;
end
if randChromosomeSequence2==0%防止产生0序号
randChromosomeSequence2=1;
end
if crossDot==0 || crossDot==1
sonChromosome(i*2-1,:)=fatherChromosome(randChromosomeSequence1,:);
sonChromosome(i*2,:)=fatherChromosome(randChromosomeSequence2,:);
else
%执行两条染色体的交叉
%把父染色体整条传给子染色体
sonChromosome(i*2-1,:)=fatherChromosome(randChromosomeSequence1,:);
sonChromosome(i*2-1,crossDot:chromosomeLength)=...
fatherChromosome(randChromosomeSequence2,crossDot:chromosomeLength)
%下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
sonChromosome(i*2,:)=fatherChromosome(randChromosomeSequence2,:);
sonChromosome(i*2,crossDot:chromosomeLength)...
=fatherChromosome(randChromosomeSequence1,crossDot:chromosomeLength)
end
end
case 2 %父染色体的第i号与第chromosomeSum+1-i号交叉
for i=1:chromosomeSum/2
crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
if crossDot==0 || crossDot==1
sonChromosome(i*2-1,:)=fatherChromosome(i,:);
sonChromosome(i*2,:)=fatherChromosome(chromosomeSum+1-i,:);
else
%执行两条染色体的交叉
sonChromosome(i*2-1,:)=fatherChromosome(i,:);%把父染色体整条传给子染色体
sonChromosome(i*2-1,crossDot:chromosomeLength)...
=fatherChromosome(chromosomeSum+1-i,crossDot:chromosomeLength);
%下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
sonChromosome(i*2,:)=fatherChromosome(chromosomeSum+1-i,:);
sonChromosome(i*2,crossDot:chromosomeLength)...
=fatherChromosome(i,crossDot:chromosomeLength);
end
end
case 3 %父染色体的第i号与第i+chromosomeSum/2号交叉
for i=1:chromosomeSum/2
crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
if crossDot==0 || crossDot==1
sonChromosome(i*2-1,:)=fatherChromosome(i,:);
sonChromosome(i*2,:)=fatherChromosome(i+chromosomeSum/2,:);
else
%执行两条染色体的交叉
sonChromosome(i*2-1,:)=fatherChromosome(i,:);%把父染色体整条传给子染色体
sonChromosome(i*2-1,crossDot:chromosomeLength)...
=fatherChromosome(i+chromosomeSum/2,crossDot:chromosomeLength);
%下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
sonChromosome(i*2,:)=fatherChromosome(i+chromosomeSum/2,:);
sonChromosome(i*2,crossDot:chromosomeLength)...
=fatherChromosome(i,crossDot:chromosomeLength);
end
end
end %函数7:染色体变异
%实现染色体的变异。
%变异方法：随机取出一段染色体，把这段染色体头尾相掉(旋转180度)，再放回原来的位置
function chromosomeGroup=mutant(chromosomeGroup,parameter)
chromosomeSum=size(chromosomeGroup,1);
chromosomeLength=size(chromosomeGroup(1,:),2);
for i=1:chromosomeSum
if rand(1)>parameter%设置变异概率
head=fix(rand(1)*chromosomeLength)+1;
tail=fix(rand(1)*chromosomeLength)+1;
if head>chromosomeLength
head=chromosomeLength
elseif tail>chromosomeLength
tail=chromosomeLength
end
if head==tail
break
end
if head>tail
k=head;head=tail;tail=k;
end
kk(1:tail-head+1)=chromosomeGroup(i,head:tail);
for j=head:tail
chromosomeGroup(i,head)=kk(tail-j+1);
end
end
end
来自搜狐博客=〉人工智能 没有randomChromosome(chromosomeSum,cityN)函数啊，麻烦帖上来啊，谢谢！！:@) 没有randomChromosome(chromosomeSum,cityN)函数啊，麻烦帖上来。谢谢了。学习一下
页:
[1]