基于蚁群优化算法的TSP问题求解计算智能实验报告

智能计算实验报告学院： 班级： 学号： 姓名： 成绩： 日期： 实验名称： 基于蚁群优化算法的TSP问题求解题目要求：利用蚁群优化算法对给定的TSP问题进行求解，求出一条最短路径。蚁群优化算法简介：蚁群算法是一中求解复杂优化问题的启发式算法，该方法通过模拟蚁群对“信息素”的控制和利用进行搜索食物的过程，达到求解最优结果的目的。它具有智能搜索、全局优化、稳健性强、易于其它方法结合等优点，适应于解决组合优化问题，包括运输路径优化问题。TSP数据文件格式分析：本次课程设计采用的TSP文件是att48.tsp ，文件是由48组城市坐标构成的，文件共分成三列，第一列为城市编号，第二列为城市横坐标，第三列为城市纵坐标。数据结构如下所示：城市编号城市横坐标城市纵坐标实验操作过程：1、 TSP文件的读取：class chengshi int no; double x; double y; chengshi(int no, double x, double y) this.no = no; this.x = x; this.y = y; private double getDistance(chengshi chengshi) return sqrt(pow(x - chengshi.x), 2) + pow(y - chengshi.y), 2); try /定义HashMap保存读取的坐标信息 HashMap map = new HashMap(); /读取文件 BufferedReader reader = new BufferedReader(new FileReader(new File(filename); for (String str = reader.readLine(); str != null; str = reader.readLine() /将读到的信息保存入HashMap if (str.matches(0-9+)(s*)(0-9+)(.?)(0-9*)(s*)(0-9+)(.?)(0-9*) String data = str.split(s+); chengshi chengshi = new chengshi(Integer.parseInt(data0), Double.parseDouble(data1), Double.parseDouble(data2); map.put(chengshi.no, chengshi); /分配距离矩阵存储空间 distance = new doublemap.size() + 1map.size() + 1; /分配距离倒数矩阵存储空间 heuristic = new doublemap.size() + 1map.size() + 1; /分配信息素矩阵存储空间 pheromone = new doublemap.size() + 1map.size() + 1; for (int i = 1; i map.size() + 1; i+) for (int j = 1; j map.size() + 1; j+) /计算城市间的距离，并存入距离矩阵 distanceij = map.get(i).getDistance(map.get(j); /计算距离倒数，并存入距离倒数矩阵 heuristicij = 1 / distanceij; /初始化信息素矩阵 pheromoneij = 1; catch (Exception exception) System.out.println(初始化数据失败！); 2、 TSP作图处理：private void evaporatePheromone() for (int i = 1; i pheromone.length; i+) for (int j = 1; j pheromone.length; j+) pheromoneij *= 1-rate; 3、 关键源代码（带简单的注释）：蚂蚁类代码: class mayi /已访问城市列表 private boolean visited; /访问顺序表 private int tour; /已访问城市的个数 private int n; /总的距离 private double total; mayi() /给访问顺序表分配空间 tour = new intdistance.length+1; /已存入城市数量为n，刚开始为0 n = 0; /将起始城市1,放入访问结点顺序表第一项 tour+n = 1; /给已访问城市结点分配空间 visited = new booleandistance.length; /第一个城市为出发城市，设置为已访问 visitedtourn = true; private int choosechengshi() /用来random的随机数 double m = 0; /获得当前所在的城市号放入j,如果和j相邻的城市没有被访问，那么加入m for (int i = 1, j = tourn; i pheromone.length; i+) if (!visitedi) m += pow(pheromoneji, alpha) * pow(heuristicji, beta); /保存随机数 double p = m * random(); /寻找随机城市 double k = 0; /保存城市 int q = 0; for (int i = 1, j = tourn; k p; i+) if (!visitedi) k += pow(pheromoneji, alpha) * pow(heuristicji, beta); q = i; return q; 城市选择代码：private int choosechengshi() /用来random的随机数 double m = 0; /获得当前所在的城市号放入j,如果和j相邻的城市没有被访问，那么加入m for (int i = 1, j = tourn; i pheromone.length; i+) if (!visitedi) m += pow(pheromoneji, alpha) * pow(heuristicji, beta); /保存随机数 double p = m * random(); /寻找随机城市 double k = 0; /保存城市 int q = 0; for (int i = 1, j = tourn; k p; i+) if (!visitedi) k += pow(pheromoneji, alpha) * pow(heuristicji, beta); q = i; return q; 4、 算法运行收敛图（即运行到第几步，求得的最优值是多少）：run：本次为倒数第100次迭代,当前最优路径长度为 41634.60本次为倒数第99次迭代,当前最优路径长度为 41514.21本次为倒数第98次迭代,当前最优路径长度为 38511.61本次为倒数第97次迭代,当前最优路径长度为 38511.61本次为倒数第96次迭代,当前最优路径长度为 38511.61本次为倒数第95次迭代,当前最优路径长度为 38511.61本次为倒数第94次迭代,当前最优路径长度为 37293.07、本次为倒数第6次迭代,当前最优路径长度为 37293.07本次为倒数第5次迭代,当前最优路径长度为 37293.07本次为倒数第4次迭代,当前最优路径长度为 37293.07本次为倒数第3次迭代,当前最优路径长度为 37293.07本次为倒数第2次迭代,当前最优路径长度为 37293.07本次为倒数第1次迭代,当前最优路径长度为 37293.07得到的最优的路径长度为: 37293.075、 最终求得的最优解的TSP图像：最优路径如下：1938314418728371963043271736463315121123142513204721393248529226435451042243441162234081成功生成（总时间：3 秒）实验结果分析：本次通过JAVA语言实现蚁群优化算法，我们发现虽然我们找到了问题的最优解，但是最优解的收敛性并不乐观，并不能求得问题的精确解，并且随着参数的调节运行结果有随机性。另外，在蚁群算法求解过程中，蚂蚁的数量和城市的数量差距对结果也是具有一定影响的。信息素的蒸发速度，对结果也有重要影响。目前来看，蚂蚁系统只是蚁群算法的一个最初的版本，他还有有待提高。这种算法，蚂蚁在其爬过的边上释放与其构建路径长度成反比的信息素量，蚂蚁构建的路径越好，属于路径的各个边上所获得的信息素就越多，这些边在以后的迭代中被蚂蚁选择的几率也就越大，但是我们不难想象，当城市的规模较大的时候，问题的复杂