基于蚁群算法求解求解TSP问题(JAVA)

一、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.其距离计算方法下图所示:

具体代码如下:

  1. package noah;
  2. import java.util.Random;
  3. import java.util.Vector;
  4. public class Ant implements Cloneable {
  5.     private Vector<Integer> tabu; // 禁忌表
  6.     private Vector<Integer> allowedCities; // 允许搜索的城市
  7.     private float[][] delta; // 信息数变化矩阵
  8.     private int[][] distance; // 距离矩阵
  9.     private float alpha;
  10.     private float beta;
  11.     private int tourLength; // 路径长度
  12.     private int cityNum; // 城市数量
  13.     private int firstCity; // 起始城市
  14.     private int currentCity; // 当前城市
  15.     public Ant() {
  16.         cityNum = 30;
  17.         tourLength = 0;
  18.     }
  19.     /**
  20.      * Constructor of Ant
  21.      *
  22.      * @param num
  23.      *            蚂蚁数量
  24.      */
  25.     public Ant(int num) {
  26.         cityNum = num;
  27.         tourLength = 0;
  28.     }
  29.     /**
  30.      * 初始化蚂蚁,随机选择起始位置
  31.      *
  32.      * @param distance
  33.      *            距离矩阵
  34.      * @param a
  35.      *            alpha
  36.      * @param b
  37.      *            beta
  38.      */
  39.     public void init(int[][] distance, float a, float b) {
  40.         alpha = a;
  41.         beta = b;
  42.         // 初始允许搜索的城市集合
  43.         allowedCities = new Vector<Integer>();
  44.         // 初始禁忌表
  45.         tabu = new Vector<Integer>();
  46.         // 初始距离矩阵
  47.         this.distance = distance;
  48.         // 初始信息数变化矩阵为0
  49.         delta = new float[cityNum][cityNum];
  50.         for (int i = 0; i < cityNum; i++) {
  51.             Integer integer = new Integer(i);
  52.             allowedCities.add(integer);
  53.             for (int j = 0; j < cityNum; j++) {
  54.                 delta[i][j] = 0.f;
  55.             }
  56.         }
  57.         // 随机挑选一个城市作为起始城市
  58.         Random random = new Random(System.currentTimeMillis());
  59.         firstCity = random.nextInt(cityNum);
  60.         // 允许搜索的城市集合中移除起始城市
  61.         for (Integer i : allowedCities) {
  62.             if (i.intValue() == firstCity) {
  63.                 allowedCities.remove(i);
  64.                 break;
  65.             }
  66.         }
  67.         // 将起始城市添加至禁忌表
  68.         tabu.add(Integer.valueOf(firstCity));
  69.         // 当前城市为起始城市
  70.         currentCity = firstCity;
  71.     }
  72.     /**
  73.      *
  74.      * 选择下一个城市
  75.      *
  76.      * @param pheromone
  77.      *            信息素矩阵
  78.      */
  79.     public void selectNextCity(float[][] pheromone) {
  80.         float[] p = new float[cityNum];
  81.         float sum = 0.0f;
  82.         // 计算分母部分
  83.         for (Integer i : allowedCities) {
  84.             sum += Math.pow(pheromone[currentCity][i.intValue()], alpha)
  85.                     * Math.pow(1.0 / distance[currentCity][i.intValue()], beta);
  86.         }
  87.         // 计算概率矩阵
  88.         for (int i = 0; i < cityNum; i++) {
  89.             boolean flag = false;
  90.             for (Integer j : allowedCities) {
  91.                 if (i == j.intValue()) {
  92.                     p[i] = (float) (Math.pow(pheromone[currentCity][i], alpha) * Math
  93.                             .pow(1.0 / distance[currentCity][i], beta)) / sum;
  94.                     flag = true;
  95.                     break;
  96.                 }
  97.             }
  98.             if (flag == false) {
  99.                 p[i] = 0.f;
  100.             }
  101.         }
  102.         // 轮盘赌选择下一个城市
  103.         Random random = new Random(System.currentTimeMillis());
  104.         float sleectP = random.nextFloat();
  105.         int selectCity = 0;
  106.         float sum1 = 0.f;
  107.         for (int i = 0; i < cityNum; i++) {
  108.             sum1 += p[i];
  109.             if (sum1 >= sleectP) {
  110.                 selectCity = i;
  111.                 break;
  112.             }
  113.         }
  114.         // 从允许选择的城市中去除select city
  115.         for (Integer i : allowedCities) {
  116.             if (i.intValue() == selectCity) {
  117.                 allowedCities.remove(i);
  118.                 break;
  119.             }
  120.         }
  121.         // 在禁忌表中添加select city
  122.         tabu.add(Integer.valueOf(selectCity));
  123.         // 将当前城市改为选择的城市
  124.         currentCity = selectCity;
  125.     }
  126.     /**
  127.      * 计算路径长度
  128.      *
  129.      * @return 路径长度
  130.      */
  131.     private int calculateTourLength() {
  132.         int len = 0;
  133.         //禁忌表tabu最终形式:起始城市,城市1,城市2…城市n,起始城市
  134.         for (int i = 0; i < cityNum; i++) {
  135.             len += distance[this.tabu.get(i).intValue()][this.tabu.get(i + 1)
  136.                     .intValue()];
  137.         }
  138.         return len;
  139.     }
  140.     public Vector<Integer> getAllowedCities() {
  141.         return allowedCities;
  142.     }
  143.     public void setAllowedCities(Vector<Integer> allowedCities) {
  144.         this.allowedCities = allowedCities;
  145.     }
  146.     public int getTourLength() {
  147.         tourLength = calculateTourLength();
  148.         return tourLength;
  149.     }
  150.     public void setTourLength(int tourLength) {
  151.         this.tourLength = tourLength;
  152.     }
  153.     public int getCityNum() {
  154.         return cityNum;
  155.     }
  156.     public void setCityNum(int cityNum) {
  157.         this.cityNum = cityNum;
  158.     }
  159.     public Vector<Integer> getTabu() {
  160.         return tabu;
  161.     }
  162.     public void setTabu(Vector<Integer> tabu) {
  163.         this.tabu = tabu;
  164.     }
  165.     public float[][] getDelta() {
  166.         return delta;
  167.     }
  168.     public void setDelta(float[][] delta) {
  169.         this.delta = delta;
  170.     }
  171.     public int getFirstCity() {
  172.         return firstCity;
  173.     }
  174.     public void setFirstCity(int firstCity) {
  175.         this.firstCity = firstCity;
  176.     }
  177. }
  1. package noah;
  2. import java.io.BufferedReader;
  3. import java.io.FileInputStream;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. public class ACO {
  7.     private Ant[] ants; // 蚂蚁
  8.     private int antNum; // 蚂蚁数量
  9.     private int cityNum; // 城市数量
  10.     private int MAX_GEN; // 运行代数
  11.     private float[][] pheromone; // 信息素矩阵
  12.     private int[][] distance; // 距离矩阵
  13.     private int bestLength; // 最佳长度
  14.     private int[] bestTour; // 最佳路径
  15.     // 三个参数
  16.     private float alpha;
  17.     private float beta;
  18.     private float rho;
  19.     public ACO() {
  20.     }
  21.     /**
  22.      * constructor of ACO
  23.      *
  24.      * @param n
  25.      *            城市数量
  26.      * @param m
  27.      *            蚂蚁数量
  28.      * @param g
  29.      *            运行代数
  30.      * @param a
  31.      *            alpha
  32.      * @param b
  33.      *            beta
  34.      * @param r
  35.      *            rho
  36.      *
  37.      **/
  38.     public ACO(int n, int m, int g, float a, float b, float r) {
  39.         cityNum = n;
  40.         antNum = m;
  41.         ants = new Ant[antNum];
  42.         MAX_GEN = g;
  43.         alpha = a;
  44.         beta = b;
  45.         rho = r;
  46.     }
  47.     // 给编译器一条指令,告诉它对被批注的代码元素内部的某些警告保持静默
  48.     @SuppressWarnings(“resource”)
  49.     /**
  50.      * 初始化ACO算法类
  51.      * @param filename 数据文件名,该文件存储所有城市节点坐标数据
  52.      * @throws IOException
  53.      */
  54.     private void init(String filename) throws IOException {
  55.         // 读取数据
  56.         int[] x;
  57.         int[] y;
  58.         String strbuff;
  59.         BufferedReader data = new BufferedReader(new InputStreamReader(
  60.                 new FileInputStream(filename)));
  61.         distance = new int[cityNum][cityNum];
  62.         x = new int[cityNum];
  63.         y = new int[cityNum];
  64.         for (int i = 0; i < cityNum; i++) {
  65.             // 读取一行数据,数据格式1 6734 1453
  66.             strbuff = data.readLine();
  67.             // 字符分割
  68.             String[] strcol = strbuff.split(” “);
  69.             x[i] = Integer.valueOf(strcol[1]);// x坐标
  70.             y[i] = Integer.valueOf(strcol[2]);// y坐标
  71.         }
  72.         // 计算距离矩阵
  73.         // 针对具体问题,距离计算方法也不一样,此处用的是att48作为案例,它有48个城市,距离计算方法为伪欧氏距离,最优值为10628
  74.         for (int i = 0; i < cityNum – 1; i++) {
  75.             distance[i][i] = 0; // 对角线为0
  76.             for (int j = i + 1; j < cityNum; j++) {
  77.                 double rij = Math
  78.                         .sqrt(((x[i] – x[j]) * (x[i] – x[j]) + (y[i] – y[j])
  79.                                 * (y[i] – y[j])) / 10.0);
  80.                 // 四舍五入,取整
  81.                 int tij = (int) Math.round(rij);
  82.                 if (tij < rij) {
  83.                     distance[i][j] = tij + 1;
  84.                     distance[j][i] = distance[i][j];
  85.                 } else {
  86.                     distance[i][j] = tij;
  87.                     distance[j][i] = distance[i][j];
  88.                 }
  89.             }
  90.         }
  91.         distance[cityNum – 1][cityNum – 1] = 0;
  92.         // 初始化信息素矩阵
  93.         pheromone = new float[cityNum][cityNum];
  94.         for (int i = 0; i < cityNum; i++) {
  95.             for (int j = 0; j < cityNum; j++) {
  96.                 pheromone[i][j] = 0.1f; // 初始化为0.1
  97.             }
  98.         }
  99.         bestLength = Integer.MAX_VALUE;
  100.         bestTour = new int[cityNum + 1];
  101.         // 随机放置蚂蚁
  102.         for (int i = 0; i < antNum; i++) {
  103.             ants[i] = new Ant(cityNum);
  104.             ants[i].init(distance, alpha, beta);
  105.         }
  106.     }
  107.     public void solve() {
  108.         // 迭代MAX_GEN次
  109.         for (int g = 0; g < MAX_GEN; g++) {
  110.             // antNum只蚂蚁
  111.             for (int i = 0; i < antNum; i++) {
  112.                 // i这只蚂蚁走cityNum步,完整一个TSP
  113.                 for (int j = 1; j < cityNum; j++) {
  114.                     ants[i].selectNextCity(pheromone);
  115.                 }
  116.                 // 把这只蚂蚁起始城市加入其禁忌表中
  117.                 // 禁忌表最终形式:起始城市,城市1,城市2…城市n,起始城市
  118.                 ants[i].getTabu().add(ants[i].getFirstCity());
  119.                 // 查看这只蚂蚁行走路径距离是否比当前距离优秀
  120.                 if (ants[i].getTourLength() < bestLength) {
  121.                     // 比当前优秀则拷贝优秀TSP路径
  122.                     bestLength = ants[i].getTourLength();
  123.                     for (int k = 0; k < cityNum + 1; k++) {
  124.                         bestTour[k] = ants[i].getTabu().get(k).intValue();
  125.                     }
  126.                 }
  127.                 // 更新这只蚂蚁的信息数变化矩阵,对称矩阵
  128.                 for (int j = 0; j < cityNum; j++) {
  129.                     ants[i].getDelta()[ants[i].getTabu().get(j).intValue()][ants[i]
  130.                             .getTabu().get(j + 1).intValue()] = (float) (1. / ants[i]
  131.                             .getTourLength());
  132.                     ants[i].getDelta()[ants[i].getTabu().get(j + 1).intValue()][ants[i]
  133.                             .getTabu().get(j).intValue()] = (float) (1. / ants[i]
  134.                             .getTourLength());
  135.                 }
  136.             }
  137.             // 更新信息素
  138.             updatePheromone();
  139.             // 重新初始化蚂蚁
  140.             for (int i = 0; i < antNum; i++) {
  141.                 ants[i].init(distance, alpha, beta);
  142.             }
  143.         }
  144.         // 打印最佳结果
  145.         printOptimal();
  146.     }
  147.     // 更新信息素
  148.     private void updatePheromone() {
  149.         // 信息素挥发
  150.         for (int i = 0; i < cityNum; i++)
  151.             for (int j = 0; j < cityNum; j++)
  152.                 pheromone[i][j] = pheromone[i][j] * (1 – rho);
  153.         // 信息素更新
  154.         for (int i = 0; i < cityNum; i++) {
  155.             for (int j = 0; j < cityNum; j++) {
  156.                 for (int k = 0; k < antNum; k++) {
  157.                     pheromone[i][j] += ants[k].getDelta()[i][j];
  158.                 }
  159.             }
  160.         }
  161.     }
  162.     private void printOptimal() {
  163.         System.out.println(“The optimal length is: ” + bestLength);
  164.         System.out.println(“The optimal tour is: “);
  165.         for (int i = 0; i < cityNum + 1; i++) {
  166.             System.out.println(bestTour[i]);
  167.         }
  168.     }
  169.     /**
  170.      * @param args
  171.      * @throws IOException
  172.      */
  173.     public static void main(String[] args) throws IOException {
  174.         System.out.println(“Start….”);
  175.         ACO aco = new ACO(48, 10, 100, 1.f, 5.f, 0.5f);
  176.         aco.init(“c://data.txt”);
  177.         aco.solve();
  178.     }
  179. }

运行结果截图:

四、总结

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

标签