遗传算法解旅行商(TSP)问题

frogfish

1. %用遗传算法解TSP的主程序
   
2. %一条染色体就是一条路线
   
3. clear,clc
   
4. %为了便于检查，城市均匀分布在圆周上
   
5. cityN=10;%城市数
   
6. chromosomeSum=100;%染色体数.注意，染色体数是偶数
   
7. radius=100;%圆周半径
   
8. minPath=2*sin(pi/cityN)*radius*cityN;%最短路径
   
9. circleN=500;%循环次数
   
10. precision=10;
    
11. 
    
12. %随机生成染色体
    
13. chromosomeGroup=randomChromosome(chromosomeSum,cityN);
    
14. holdBestChromosome=0;
    
15. holdLeastDistance=Inf;
    
16. 
    
17. compute=1;
    
18. circle=0;
    
19. while compute%开始迭代求解
    
20. circle=circle+1;
    
21. %%%%%%%%%%%%%%1：计算每条染色体的距离，也就是一条TSP距离
    
22. chromosomeCityDistance=chromosomeDisctance(chromosomeGroup,radius);
    
23. %%%%%%%%%%%%%%2：选择最好解对应的最优染色体
    
24. [bestChromosome,leastDistance]=best_worstChromosome(chromosomeGroup,chromosomeCityDistance);
    
25. %%%%%%%%%%%%%%3：保留每次迭代产生的最好的染色体
    
26. %本次最好解与上次最好解进行比较，如果上次最好解优于本次最好解，保留上次最好解；
    
27. %反之，保留本次最好解。保留的最好染色体放在holdBestChromosome中
    
28. [holdBestChromosome,holdLeastDistance]...
    
29. =compareBestChromosome(holdBestChromosome,holdLeastDistance,...
    
30. bestChromosome,leastDistance);
    
31. 
    
32. 
    
33. if holdLeastDistance-minPath<precision
    
34. '程序结束'
    
35. circle
    
36. minPath
    
37. holdLeastDistance
    
38. holdBestChromosome
    
39. return
    
40. end
    
41. if circle>circleN
    
42. circle
    
43. minPath
    
44. holdLeastDistance
    
45. holdBestChromosome
    
46. return
    
47. end
    
48. %%%%%%%%%%%%%%4:把保留的最好的染色体holdBestChromosome加入到染色体群中
    
49. order=round(rand(1)*chromosomeSum);
    
50. if order==0
    
51. order=1;
    
52. end
    
53. fatherChromosomeGroup(order,:)=holdBestChromosome;
    
54. chromosomeCityDistance(order)=holdLeastDistance;
    
55. 
    
56. %%%%%%%%%%%%%%%5:为每一条染色体(即可能解的序号)定义一个概率(关键步骤)
    
57. %%%%%%%%%%%%%%%好的染色体概率高，坏的概率低。依据误差functionError计算概率
    
58. [p,trueP]=chromosomeProbability(chromosomeCityDistance);
    
59. if trueP =='Fail'
    
60. '可能解严重不适应方程，请重新开始'
    
61. return%结束程序
    
62. end
    
63. %%%%%%%%%%%%%%%6：按照概率筛选染色体(关键步骤)
    
64. 
    
65. %从父染体中选择优秀染色体
    
66. selecteChromosomeGroup=selecteChromosome(chromosomeGroup,p);
    
67. 
    
68. %selecteChromosomeGroup=chromosomeGroup;
    
69. %%%%%%%%%%%%%%%7：染色体杂交(关键步骤)
    
70. half=chromosomeSum/2;
    
71. for i=1:half
    
72. [selecteChromosomeGroup(i,:),selecteChromosomeGroup(chromosomeSum-i+1,:)]...
    
73. =serchCross(selecteChromosomeGroup(i,:),selecteChromosomeGroup(chromosomeSum-i+1,:),4);
    
74. end
    
75. %%%%%%%%%%%%%%%%8:染色体变异
    
76. chromosomeGroup=mutant(selecteChromosomeGroup,0.5);
    
77. %chromosomeGroup=selecteChromosomeGroup;
    
78. 
    
79. end

复制代码

frogfish

%函数1：计算每条染色体的距离，也就是一条TSP距离

1. function chromosomeCityDistance=chromosomeDisctance(chromosomeGroup,radius)
   
2. chromosomeN=size(chromosomeGroup,1);
   
3. cityN=size(chromosomeGroup(1,:),2);
   
4. centralAngle=2*pi/cityN;%相邻城市的圆心角
   
5. radius=radius;
   
6. for i=1:chromosomeN
   
7. distance=0;
   
8. for j=2:cityN
   
9. city2angle=abs(chromosomeGroup(i,j)-chromosomeGroup(i,j-1))*centralAngle;
   
10. %计算路线上两个城市之间的角度
    
11. if city2angle>pi
    
12. city2angle=2*pi-city2angle;%角度换算到pi以内
    
13. end
    
14. city2distance=radius*sin(city2angle/2)*2;%计算城市间的距离
    
15. distance=distance+city2distance;
    
16. end
    
17. city2angle=abs(chromosomeGroup(i,j)-chromosomeGroup(i,1))*centralAngle;
    
18. %计算头尾两个城市的角度
    
19. if city2angle>pi
    
20. city2angle=2*pi-city2angle;%角度换算到pi以内
    
21. end
    
22. city2distance=radius*sin(city2angle/2)*2;%计算城市间的距离
    
23. distance=distance+city2distance;
    
24. chromosomeCityDistance(i,1)=distance;
    
25. end

复制代码

frogfish

%函数2：选择最好解对应的最优染色体

1. %找出最小误差所对应的最好染色体，最大误差所对应的最坏染色体
   
2. function [bestChromosome,leastFunctionError]=best_worstChromosome(chromosomeGroup,functionError)
   
3. [leastFunctionError minErrorOrder]=min(functionError);
   
4. %[maxFunctionError maxErrorOrder]=max(functionError);
   
5. bestChromosome=chromosomeGroup(minErrorOrder,:);
   
6. %worstChromosome=chromosomeGroup(maxErrorOrder,:);

复制代码

frogfish

%函数3：保留每次迭代产生的最好的染色体

1. %选择最好的基因保留下来
   
2. function [newBestChromosome,newLeastFunctionError]...
   
3. =compareBestChromosome(oldBestChromosome,oldLeastFunctionError,...
   
4. bestChromosome,leastFunctionError)
   
5. if oldLeastFunctionError>leastFunctionError
   
6. newLeastFunctionError=leastFunctionError;
   
7. newBestChromosome=bestChromosome;
   
8. else
   
9. newLeastFunctionError=oldLeastFunctionError;
   
10. newBestChromosome=oldBestChromosome;
    
11. end

复制代码

frogfish

%函数4:为每一条染色体(即可能解的序号)定义一个概率(关键步骤)

1. %根据待解的非线性函数的误差计算染色体的概率
   
2. function [p,isP]=chromosomeProbability(x_Error)
   
3. InfN=sum(isinf(x_Error));%估计非线性方程计算的结果
   
4. NaNN=sum(isnan(x_Error));
   
5. if InfN>0 || NaNN>0
   
6. isP='Fail';
   
7. p=0;
   
8. return
   
9. else
   
10. isP='True';
    
11. errorReciprocal=1./x_Error;
    
12. sumReciprocal=sum(errorReciprocal);
    
13. p=errorReciprocal/sumReciprocal;%p:可能解所对应的染色体的概率
    
14. end

复制代码

frogfish

%函数5：按照概率筛选染色体(关键步骤)

1. function chromosome=selecteChromosome(chromosomeGroup,p)
   
2. cumuP=cumsum(p);%累积概率,也就是把每个染色体的概率映射到0~1的区间
   
3. [chromosomeSum,chromosomeLength]=size(chromosomeGroup);
   
4. for i=1:chromosomeSum%这个循环产生概率值
   
5. rN=rand(1);
   
6. if rN==1
   
7. chromosome(i,:)=chromosomeGroup(chromosomeSum,:);
   
8. elseif (0<=rN) && (rN<cumuP(1))
   
9. chromosome(i,:)=chromosomeGroup(1,:);%第1条染色体被选中
   
10. else
    
11. for j=2:chromosomeSum%这个循环确定第1条以后的哪一条染色体被选中
    
12. if (cumuP(j-1)<=rN) && (rN<cumuP(j))
    
13. chromosome(i,:)=chromosomeGroup(j,:);
    
14. break
    
15. end
    
16. end
    
17. end
    
18. end

复制代码

frogfish

%函数6：染色体杂交(关键步骤)

1. function sonChromosome=crossChromosome(fatherChromosome,parameter)
   
2. [chromosomeSum,chromosomeLength]=size(fatherChromosome);
   
3. %chromosomeSum:染色体的条数；chromosomeLength：染色体的长度
   
4. switch parameter
   
5. case 1%随机选择父染色体进行交叉重组
   
6. for i=1:chromosomeSum/2
   
7. crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
   
8. randChromosomeSequence1=round(rand(1)*chromosomeSum);
   
9. %随机产生第1条染色体的序号
   
10. randChromosomeSequence2=round(rand(1)*chromosomeSum);
    
11. %随机产生第2条染色体的序号，这两条染色体要进行杂交
    
12. if randChromosomeSequence1==0%防止产生0序号
    
13. randChromosomeSequence1=1;
    
14. end
    
15. if randChromosomeSequence2==0%防止产生0序号
    
16. randChromosomeSequence2=1;
    
17. end
    
18. if crossDot==0 || crossDot==1
    
19. sonChromosome(i*2-1,:)=fatherChromosome(randChromosomeSequence1,:);
    
20. sonChromosome(i*2,:)=fatherChromosome(randChromosomeSequence2,:);
    
21. else
    
22. %执行两条染色体的交叉
    
23. %把父染色体整条传给子染色体
    
24. sonChromosome(i*2-1,:)=fatherChromosome(randChromosomeSequence1,:);
    
25. 
    
26. sonChromosome(i*2-1,crossDot:chromosomeLength)=...
    
27. fatherChromosome(randChromosomeSequence2,crossDot:chromosomeLength)
    
28. %下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
    
29. sonChromosome(i*2,:)=fatherChromosome(randChromosomeSequence2,:);
    
30. sonChromosome(i*2,crossDot:chromosomeLength)...
    
31. =fatherChromosome(randChromosomeSequence1,crossDot:chromosomeLength)
    
32. end
    
33. end
    
34. case 2 %父染色体的第i号与第chromosomeSum+1-i号交叉
    
35. for i=1:chromosomeSum/2
    
36. crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
    
37. if crossDot==0 || crossDot==1
    
38. sonChromosome(i*2-1,:)=fatherChromosome(i,:);
    
39. sonChromosome(i*2,:)=fatherChromosome(chromosomeSum+1-i,:);
    
40. else
    
41. %执行两条染色体的交叉
    
42. sonChromosome(i*2-1,:)=fatherChromosome(i,:);%把父染色体整条传给子染色体
    
43. sonChromosome(i*2-1,crossDot:chromosomeLength)...
    
44. =fatherChromosome(chromosomeSum+1-i,crossDot:chromosomeLength);
    
45. %下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
    
46. sonChromosome(i*2,:)=fatherChromosome(chromosomeSum+1-i,:);
    
47. sonChromosome(i*2,crossDot:chromosomeLength)...
    
48. =fatherChromosome(i,crossDot:chromosomeLength);
    
49. end
    
50. end
    
51. case 3 %父染色体的第i号与第i+chromosomeSum/2号交叉
    
52. for i=1:chromosomeSum/2
    
53. crossDot=fix(rand(1)*chromosomeLength);%随机选择染色体的交叉点位
    
54. if crossDot==0 || crossDot==1
    
55. sonChromosome(i*2-1,:)=fatherChromosome(i,:);
    
56. sonChromosome(i*2,:)=fatherChromosome(i+chromosomeSum/2,:);
    
57. else
    
58. %执行两条染色体的交叉
    
59. sonChromosome(i*2-1,:)=fatherChromosome(i,:);%把父染色体整条传给子染色体
    
60. sonChromosome(i*2-1,crossDot:chromosomeLength)...
    
61. =fatherChromosome(i+chromosomeSum/2,crossDot:chromosomeLength);
    
62. %下一条父染色体上交叉点crossDot后的基因传给子染色体，完成前一条染色体的交叉
    
63. sonChromosome(i*2,:)=fatherChromosome(i+chromosomeSum/2,:);
    
64. sonChromosome(i*2,crossDot:chromosomeLength)...
    
65. =fatherChromosome(i,crossDot:chromosomeLength);
    
66. end
    
67. end
    
68. end

复制代码

frogfish

%函数7:染色体变异

1. %实现染色体的变异。
   
2. %变异方法：随机取出一段染色体，把这段染色体头尾相掉(旋转180度)，再放回原来的位置
   
3. function chromosomeGroup=mutant(chromosomeGroup,parameter)
   
4. chromosomeSum=size(chromosomeGroup,1);
   
5. chromosomeLength=size(chromosomeGroup(1,:),2);
   
6. for i=1:chromosomeSum
   
7. if rand(1)>parameter%设置变异概率
   
8. head=fix(rand(1)*chromosomeLength)+1;
   
9. tail=fix(rand(1)*chromosomeLength)+1;
   
10. if head>chromosomeLength
    
11. head=chromosomeLength
    
12. elseif tail>chromosomeLength
    
13. tail=chromosomeLength
    
14. end
    
15. if head==tail
    
16. break
    
17. end
    
18. if head>tail
    
19. k=head;head=tail;tail=k;
    
20. end
    
21. kk(1:tail-head+1)=chromosomeGroup(i,head:tail);
    
22. for j=head:tail
    
23. chromosomeGroup(i,head)=kk(tail-j+1);
    
24. end
    
25. end
    
26. end

复制代码

来自搜狐博客=〉人工智能

mzy0186

没有randomChromosome(chromosomeSum,cityN)函数啊，麻烦帖上来啊，谢谢！！:@)

liulbcd

没有randomChromosome(chromosomeSum,cityN)函数啊，麻烦帖上来。谢谢了。学习一下