基于蚁群算法求解求解TSP问题（JAVA）

2023-08-07 02:01| 来源: 网络整理| 查看: 265

一、TSP问题

TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述：

V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目；

E={(r, s): r,s∈ V}是所有城市之间连接的集合；

C = {crs: r,s∈ V}是所有城市之间连接的成本度量（一般为城市之间的距离）；

如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。

一个TSP问题可以表达为：

求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。

二、蚁群算法

蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。

蚁群算法原理：假如蚁群中所有蚂蚁的数量为m，所有城市之间的信息素用矩阵pheromone表示，最短路径为bestLength，最佳路径为bestTour。每只蚂蚁都有自己的内存，内存中用一个禁忌表（Tabu）来存储该蚂蚁已经访问过的城市，表示其在以后的搜索中将不能访问这些城市；还有用另外一个允许访问的城市表（Allowed）来存储它还可以访问的城市；另外还用一个矩阵（Delta）来存储它在一个循环（或者迭代）中给所经过的路径释放的信息素；还有另外一些数据，例如一些控制参数（α,β,ρ,Q），该蚂蚁行走玩全程的总成本或距离（tourLength），等等。假定算法总共运行MAX_GEN次，运行时间为t。

蚁群算法计算过程如下：（1）初始化（2）为每只蚂蚁选择下一个节点。（3）更新信息素矩阵（4）检查终止条件（5）输出最优值

三、蚁群算法求解TSP问题

在该JAVA实现中我们选择使用tsplib上的数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628.其距离计算方法下图所示：

具体代码如下：

package noah; import java.util.Random; import java.util.Vector; public class Ant implements Cloneable { private Vector tabu; // 禁忌表 private Vector allowedCities; // 允许搜索的城市 private float[][] delta; // 信息数变化矩阵 private int[][] distance; // 距离矩阵 private float alpha; private float beta; private int tourLength; // 路径长度 private int cityNum; // 城市数量 private int firstCity; // 起始城市 private int currentCity; // 当前城市 public Ant() { cityNum = 30; tourLength = 0; } /** * Constructor of Ant * * @param num * 蚂蚁数量 */ public Ant(int num) { cityNum = num; tourLength = 0; } /** * 初始化蚂蚁，随机选择起始位置 * * @param distance * 距离矩阵 * @param a * alpha * @param b * beta */ public void init(int[][] distance, float a, float b) { alpha = a; beta = b; // 初始允许搜索的城市集合 allowedCities = new Vector(); // 初始禁忌表 tabu = new Vector(); // 初始距离矩阵 this.distance = distance; // 初始信息数变化矩阵为0 delta = new float[cityNum][cityNum]; for (int i = 0; i < cityNum; i++) { Integer integer = new Integer(i); allowedCities.add(integer); for (int j = 0; j < cityNum; j++) { delta[i][j] = 0.f; } } // 随机挑选一个城市作为起始城市 Random random = new Random(System.currentTimeMillis()); firstCity = random.nextInt(cityNum); // 允许搜索的城市集合中移除起始城市 for (Integer i : allowedCities) { if (i.intValue() == firstCity) { allowedCities.remove(i); break; } } // 将起始城市添加至禁忌表 tabu.add(Integer.valueOf(firstCity)); // 当前城市为起始城市 currentCity = firstCity; } /** * * 选择下一个城市 * * @param pheromone * 信息素矩阵 */ public void selectNextCity(float[][] pheromone) { float[] p = new float[cityNum]; float sum = 0.0f; // 计算分母部分 for (Integer i : allowedCities) { sum += Math.pow(pheromone[currentCity][i.intValue()], alpha) * Math.pow(1.0 / distance[currentCity][i.intValue()], beta); } // 计算概率矩阵 for (int i = 0; i < cityNum; i++) { boolean flag = false; for (Integer j : allowedCities) { if (i == j.intValue()) { p[i] = (float) (Math.pow(pheromone[currentCity][i], alpha) * Math .pow(1.0 / distance[currentCity][i], beta)) / sum; flag = true; break; } } if (flag == false) { p[i] = 0.f; } } // 轮盘赌选择下一个城市 Random random = new Random(System.currentTimeMillis()); float sleectP = random.nextFloat(); int selectCity = 0; float sum1 = 0.f; for (int i = 0; i < cityNum; i++) { sum1 += p[i]; if (sum1 >= sleectP) { selectCity = i; break; } } // 从允许选择的城市中去除select city for (Integer i : allowedCities) { if (i.intValue() == selectCity) { allowedCities.remove(i); break; } } // 在禁忌表中添加select city tabu.add(Integer.valueOf(selectCity)); // 将当前城市改为选择的城市 currentCity = selectCity; } /** * 计算路径长度 * * @return 路径长度 */ private int calculateTourLength() { int len = 0; //禁忌表tabu最终形式：起始城市,城市1,城市2...城市n,起始城市 for (int i = 0; i < cityNum; i++) { len += distance[this.tabu.get(i).intValue()][this.tabu.get(i + 1) .intValue()]; } return len; } public Vector getAllowedCities() { return allowedCities; } public void setAllowedCities(Vector allowedCities) { this.allowedCities = allowedCities; } public int getTourLength() { tourLength = calculateTourLength(); return tourLength; } public void setTourLength(int tourLength) { this.tourLength = tourLength; } public int getCityNum() { return cityNum; } public void setCityNum(int cityNum) { this.cityNum = cityNum; } public Vector getTabu() { return tabu; } public void setTabu(Vector tabu) { this.tabu = tabu; } public float[][] getDelta() { return delta; } public void setDelta(float[][] delta) { this.delta = delta; } public int getFirstCity() { return firstCity; } public void setFirstCity(int firstCity) { this.firstCity = firstCity; } }

package noah; import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; public class ACO { private Ant[] ants; // 蚂蚁 private int antNum; // 蚂蚁数量 private int cityNum; // 城市数量 private int MAX_GEN; // 运行代数 private float[][] pheromone; // 信息素矩阵 private int[][] distance; // 距离矩阵 private int bestLength; // 最佳长度 private int[] bestTour; // 最佳路径 // 三个参数 private float alpha; private float beta; private float rho; public ACO() { } /** * constructor of ACO * * @param n * 城市数量 * @param m * 蚂蚁数量 * @param g * 运行代数 * @param a * alpha * @param b * beta * @param r * rho * **/ public ACO(int n, int m, int g, float a, float b, float r) { cityNum = n; antNum = m; ants = new Ant[antNum]; MAX_GEN = g; alpha = a; beta = b; rho = r; } // 给编译器一条指令，告诉它对被批注的代码元素内部的某些警告保持静默 @SuppressWarnings("resource") /** * 初始化ACO算法类 * @param filename 数据文件名，该文件存储所有城市节点坐标数据 * @throws IOException */ private void init(String filename) throws IOException { // 读取数据 int[] x; int[] y; String strbuff; BufferedReader data = new BufferedReader(new InputStreamReader( new FileInputStream(filename))); distance = new int[cityNum][cityNum]; x = new int[cityNum]; y = new int[cityNum]; for (int i = 0; i < cityNum; i++) { // 读取一行数据，数据格式1 6734 1453 strbuff = data.readLine(); // 字符分割 String[] strcol = strbuff.split(" "); x[i] = Integer.valueOf(strcol[1]);// x坐标 y[i] = Integer.valueOf(strcol[2]);// y坐标 } // 计算距离矩阵 // 针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628 for (int i = 0; i < cityNum - 1; i++) { distance[i][i] = 0; // 对角线为0 for (int j = i + 1; j < cityNum; j++) { double rij = Math .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) / 10.0); // 四舍五入，取整 int tij = (int) Math.round(rij); if (tij < rij) { distance[i][j] = tij + 1; distance[j][i] = distance[i][j]; } else { distance[i][j] = tij; distance[j][i] = distance[i][j]; } } } distance[cityNum - 1][cityNum - 1] = 0; // 初始化信息素矩阵 pheromone = new float[cityNum][cityNum]; for (int i = 0; i < cityNum; i++) { for (int j = 0; j < cityNum; j++) { pheromone[i][j] = 0.1f; // 初始化为0.1 } } bestLength = Integer.MAX_VALUE; bestTour = new int[cityNum + 1]; // 随机放置蚂蚁 for (int i = 0; i < antNum; i++) { ants[i] = new Ant(cityNum); ants[i].init(distance, alpha, beta); } } public void solve() { // 迭代MAX_GEN次 for (int g = 0; g < MAX_GEN; g++) { // antNum只蚂蚁 for (int i = 0; i < antNum; i++) { // i这只蚂蚁走cityNum步，完整一个TSP for (int j = 1; j < cityNum; j++) { ants[i].selectNextCity(pheromone); } // 把这只蚂蚁起始城市加入其禁忌表中 // 禁忌表最终形式：起始城市,城市1,城市2...城市n,起始城市 ants[i].getTabu().add(ants[i].getFirstCity()); // 查看这只蚂蚁行走路径距离是否比当前距离优秀 if (ants[i].getTourLength() < bestLength) { // 比当前优秀则拷贝优秀TSP路径 bestLength = ants[i].getTourLength(); for (int k = 0; k < cityNum + 1; k++) { bestTour[k] = ants[i].getTabu().get(k).intValue(); } } // 更新这只蚂蚁的信息数变化矩阵，对称矩阵 for (int j = 0; j < cityNum; j++) { ants[i].getDelta()[ants[i].getTabu().get(j).intValue()][ants[i] .getTabu().get(j + 1).intValue()] = (float) (1. / ants[i] .getTourLength()); ants[i].getDelta()[ants[i].getTabu().get(j + 1).intValue()][ants[i] .getTabu().get(j).intValue()] = (float) (1. / ants[i] .getTourLength()); } } // 更新信息素 updatePheromone(); // 重新初始化蚂蚁 for (int i = 0; i < antNum; i++) { ants[i].init(distance, alpha, beta); } } // 打印最佳结果 printOptimal(); } // 更新信息素 private void updatePheromone() { // 信息素挥发 for (int i = 0; i < cityNum; i++) for (int j = 0; j < cityNum; j++) pheromone[i][j] = pheromone[i][j] * (1 - rho); // 信息素更新 for (int i = 0; i < cityNum; i++) { for (int j = 0; j < cityNum; j++) { for (int k = 0; k < antNum; k++) { pheromone[i][j] += ants[k].getDelta()[i][j]; } } } } private void printOptimal() { System.out.println("The optimal length is: " + bestLength); System.out.println("The optimal tour is: "); for (int i = 0; i < cityNum + 1; i++) { System.out.println(bestTour[i]); } } /** * @param args * @throws IOException */ public static void main(String[] args) throws IOException { System.out.println("Start...."); ACO aco = new ACO(48, 10, 100, 1.f, 5.f, 0.5f); aco.init("c://data.txt"); aco.solve(); } } 运行结果截图：

四、总结

蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力，但是也正是由于其并行性的本质，蚁群算法的搜索时间较长，在求解小规模的NP问题时耗费的计算资源相比其他启发式算法要多，因而显得效率很低下，而当问题趋向于大规模时，蚁群算法还是存在难收敛的问题，个人感觉除非你真想耗费大量计算资源来干一件事情，否则还是慎用蚁群算法。

注：本文部分内容来源于网络，但程序以及分析结果属于本人成果，转载请注明！

【本文地址】

公司简介

联系我们