1. package tspsolver;
2. import java.util.Random;
3. /**
4. *蚂蚁类
5. * @author FashionXu
6. */
7. public class ant {
8. /**
9. * 蚂蚁获得的路径
10. */
11. public int[]tour;
12. //unvisitedcity 取值是0或1，
13. //1表示没有访问过，0表示访问过
14. int[] unvisitedcity;
15. /**
16. * 蚂蚁获得的路径长度
17. */
18. public int tourlength;
19. int citys;
20. /**
21. * 随机分配蚂蚁到某个城市中
22. * 同时完成蚂蚁包含字段的初始化工作
23. * @param citycount 总的城市数量
24. */
25. public void RandomSelectCity(int citycount){
26. citys=citycount;
27. unvisitedcity=new int[citycount];
28. tour=new int[citycount+1];
29. tourlength=0;
30. for(int i=0;i<citycount;i++){
31. tour[i]=-1;
32. unvisitedcity[i]=1;
33. }
34. long r1 = System.currentTimeMillis();
35. Random rnd=new Random(r1);
36. int firstcity=rnd.nextInt(citycount);
37. unvisitedcity[firstcity]=0;
38. tour[0]=firstcity;
39. }
40. /**
41. * 选择下一个城市
42. * @param index 需要选择第index个城市了
43. * @param tao 全局的信息素信息
44. * @param distance 全局的距离矩阵信息
45. */
46. public void SelectNextCity(int index,double[][]tao,int[][]distance){
47. double []p;
48. p=new double[citys];
49. double alpha=1.0;
50. double beta=2.0;
51. double sum=0;
52. int currentcity=tour[index-1];
53. //计算公式中的分母部分
54. for(int i=0;i<citys;i++){
55. if(unvisitedcity[i]==1)
56. sum+=(Math.pow(tao[currentcity][i], alpha)*
57. Math.pow(1.0/distance[currentcity][i], beta));
58. }
59. //计算每个城市被选中的概率
60. for(int i=0;i<citys;i++){
61. if(unvisitedcity[i]==0)
62. p[i]=0.0;
63. else{
64. p[i]=(Math.pow(tao[currentcity][i], alpha)*
65. Math.pow(1.0/distance[currentcity][i], beta))/sum;
66. }
67. }
68. long r1 = System.currentTimeMillis();
69. Random rnd=new Random(r1);
70. double selectp=rnd.nextDouble();
71. //轮盘赌选择一个城市；
72. double sumselect=0;
73. int selectcity=-1;
74. for(int i=0;i<citys;i++){
75. sumselect+=p[i];
76. if(sumselect>=selectp){
77. selectcity=i;
78. break;
79. }
80. }
81. if (selectcity==-1)
82. System.out.println();
83. tour[index]=selectcity;
84. unvisitedcity[selectcity]=0;
85. }
86. /**
87. * 计算蚂蚁获得的路径的长度
88. * @param distance 全局的距离矩阵信息
89. */
90. public void CalTourLength(int [][]distance){
91. tourlength=0;
92. tour[citys]=tour[0];
93. for(int i=0;i<citys;i++){
94. tourlength+=distance[tour[i]][tour[i+1]];
95. }
96. }
97. } 1. package tspsolver;
2. import java.io.*;
3. /**
4. *蚁群优化算法，用来求解TSP问题
5. * @author FashionXu
6. */
7. public class ACO {
8. //定义蚂蚁群
9. ant []ants;
10. int antcount;//蚂蚁的数量
11. int [][]distance;//表示城市间距离
12. double [][]tao;//信息素矩阵
13. int citycount;//城市数量
14. int[]besttour;//求解的最佳路径
15. int bestlength;//求的最优解的长度
16. /** 初始化函数
17. *@param filename tsp数据文件
18. *@param antnum 系统用到蚂蚁的数量
19. *@throws 如果文件不存在则抛出异常
20. */
21. public void init(String filename,int antnum) throws FileNotFoundException, IOException{
22. antcount=antnum;
23. ants=new ant[antcount];
24. //读取数据
25. int[] x;
26. int[] y;
27. String strbuff;
28. BufferedReader tspdata = new BufferedReader(new InputStreamReader(new FileInputStream(filename)));
29. strbuff = tspdata.readLine();
30. citycount = Integer.valueOf(strbuff);
31. distance = new int[citycount][citycount];
32. x = new int[citycount];
33. y = new int[citycount];
34. for (int citys = 0; citys < citycount; citys++) {
35. strbuff = tspdata.readLine();
36. String[] strcol = strbuff.split(" ");
37. x[citys] = Integer.valueOf(strcol[1]);
38. y[citys] = Integer.valueOf(strcol[2]);
39. }
40. //计算距离矩阵
41. for (int city1 = 0; city1 < citycount - 1; city1++) {
42. distance[city1][city1] = 0;
43. for (int city2 = city1 + 1; city2 < citycount; city2++) {
44. distance[city1][city2] = (int) (Math.sqrt((x[city1] - x[city2]) * (x[city1] - x[city2])
45. + (y[city1] - y[city2]) * (y[city1] - y[city2])) + 0.5);
46. distance[city2][city1] = distance[city1][city2];
47. }
48. }
49. distance[citycount - 1][citycount - 1] = 0;
50. //初始化信息素矩阵
51. tao=new double[citycount][citycount];
52. for(int i=0;i<citycount;i++)
53. {
54. for(int j=0;j<citycount;j++){
55. tao[i][j]=0.1;
56. }
57. }
58. bestlength=Integer.MAX_VALUE;
59. besttour=new int[citycount+1];
60. //随机放置蚂蚁
61. for(int i=0;i<antcount;i++){
62. ants[i]=new ant();
63. ants[i].RandomSelectCity(citycount);
64. }
65. }
66. /**
67. * ACO的运行过程
68. * @param maxgen ACO的最多循环次数
69. *
70. */
71. public void run(int maxgen){
72. for(int runtimes=0;runtimes<maxgen;runtimes++){
73. //每一只蚂蚁移动的过程
74. for(int i=0;i<antcount;i++){
75. for(int j=1;j<citycount;j++){
76. ants[i].SelectNextCity(j,tao,distance);
77. }
78. //计算蚂蚁获得的路径长度
79. ants[i].CalTourLength(distance);
80. if(ants[i].tourlength<bestlength){
81. //保留最优路径
82. bestlength=ants[i].tourlength;
83. System.out.println("第"+runtimes+"代，发现新的解"+bestlength);
84. for(int j=0;j<citycount+1;j++)
85. besttour[j]=ants[i].tour[j];
86. }
87. }
88. //更新信息素矩阵
89. UpdateTao();
90. //重新随机设置蚂蚁
91. for(int i=0;i<antcount;i++){
92. ants[i].RandomSelectCity(citycount);
93. }
94. }
95. }
96. /**
97. * 更新信息素矩阵
98. */
99. private void UpdateTao(){
100. double rou=0.5;
101. //信息素挥发
102. for(int i=0;i<citycount;i++)
103. for(int j=0;j<citycount;j++)
104. tao[i][j]=tao[i][j]*(1-rou);
105. //信息�
评论0