基于蟻群算法求解求解TSP問題（JAVA）

原文位址：http://blog.csdn.net/wangqiuyun/article/details/8878298

一、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.其距離計算方法下圖所示：

具體代碼如下：

[java] 

view plain

 copy

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;  
30.      * 初始化螞蟻，随機選擇起始位置 
32.      * @param distance 
33.      *            距離矩陣 
34.      * @param a 
35.      *            alpha 
36.      * @param b 
37.      *            beta 
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;  
67.         // 将起始城市添加至禁忌表  
68.         tabu.add(Integer.valueOf(firstCity));  
69.         // 目前城市為起始城市  
70.         currentCity = firstCity;  
74.      * 選擇下一個城市 
76.      * @param pheromone 
77.      *            資訊素矩陣 
79.     public void selectNextCity(float[][] pheromone) {  
80.         float[] p = new float[cityNum];  
81.         float sum = 0.0f;  
82.         // 計算分母部分  
84.             sum += Math.pow(pheromone[currentCity][i.intValue()], alpha)  
85.                     * Math.pow(1.0 / distance[currentCity][i.intValue()], beta);  
87.         // 計算機率矩陣  
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.                 }  
98.             if (flag == false) {  
99.                 p[i] = 0.f;  
102.         // 輪盤賭選擇下一個城市  
104.         float sleectP = random.nextFloat();  
105.         int selectCity = 0;  
106.         float sum1 = 0.f;  
108.             sum1 += p[i];  
109.             if (sum1 >= sleectP) {  
110.                 selectCity = i;  
114.         // 從允許選擇的城市中去除select city  
116.             if (i.intValue() == selectCity) {  
121.         // 在禁忌表中添加select city  
122.         tabu.add(Integer.valueOf(selectCity));  
123.         // 将目前城市改為選擇的城市  
124.         currentCity = selectCity;  
127.      * 計算路徑長度 
129.      * @return 路徑長度 
131.     private int calculateTourLength() {  
132.         int len = 0;  
133.         //禁忌表tabu最終形式：起始城市,城市1,城市2...城市n,起始城市  
135.             len += distance[this.tabu.get(i).intValue()][this.tabu.get(i + 1)  
136.                     .intValue()];  
138.         return len;  
140.     public Vector<Integer> getAllowedCities() {  
141.         return allowedCities;  
143.     public void setAllowedCities(Vector<Integer> allowedCities) {  
144.         this.allowedCities = allowedCities;  
146.     public int getTourLength() {  
147.         tourLength = calculateTourLength();  
148.         return tourLength;  
150.     public void setTourLength(int tourLength) {  
151.         this.tourLength = tourLength;  
153.     public int getCityNum() {  
154.         return cityNum;  
156.     public void setCityNum(int cityNum) {  
157.         this.cityNum = cityNum;  
159.     public Vector<Integer> getTabu() {  
160.         return tabu;  
162.     public void setTabu(Vector<Integer> tabu) {  
163.         this.tabu = tabu;  
165.     public float[][] getDelta() {  
166.         return delta;  
168.     public void setDelta(float[][] delta) {  
169.         this.delta = delta;  
171.     public int getFirstCity() {  
172.         return firstCity;  
174.     public void setFirstCity(int firstCity) {  
175.         this.firstCity = firstCity;  
177. }  

[java] 

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; // 螞蟻數量  
10.     private int MAX_GEN; // 運作代數  
11.     private float[][] pheromone; // 資訊素矩陣  
13.     private int bestLength; // 最佳長度  
14.     private int[] bestTour; // 最佳路徑  
15.     // 三個參數  
18.     private float rho;  
19.     public ACO() {  
22.      * constructor of ACO 
24.      * @param n 
25.      *            城市數量 
26.      * @param m 
28.      * @param g 
29.      *            運作代數 
34.      * @param r 
35.      *            rho 
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;  
45.         rho = r;  
47.     // 給編譯器一條指令，告訴它對被批注的代碼元素内部的某些警告保持靜默  
48.     @SuppressWarnings("resource")  
50.      * 初始化ACO算法類 
51.      * @param filename 資料檔案名，該檔案存儲所有城市節點坐标資料 
52.      * @throws IOException 
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];  
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坐标  
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;  
91.         distance[cityNum - 1][cityNum - 1] = 0;  
92.         // 初始化資訊素矩陣  
93.         pheromone = new float[cityNum][cityNum];  
96.                 pheromone[i][j] = 0.1f; // 初始化為0.1  
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);  
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);  
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.                     }  
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]  
137.             // 更新資訊素  
138.             updatePheromone();  
139.             // 重新初始化螞蟻  
141.                 ants[i].init(distance, alpha, beta);  
144.         // 列印最佳結果  
145.         printOptimal();  
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.         // 資訊素更新  
156.                 for (int k = 0; k < antNum; k++) {  
157.                     pheromone[i][j] += ants[k].getDelta()[i][j];  
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]);  
170.      * @param args 
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();  

運作結果截圖：