前言

蚁群也是一种利用了大自然规律的启发式算法，与之前学习过的GA遗传算法类似，遗传算法是用了生物进行理论，把更具适应性的基因传给下一代，最后就能得到一个最优解，常常用来寻找问题的最优解。当然，本篇文章不会主讲GA算法的，想要了解的同学可以查看，我的和。话题重新回到蚁群算法，蚁群算法是一个利用了蚂蚁寻找食物的原理。不知道小时候有没有发现，当一个蚂蚁发现了地上的食物，然后非常迅速的，就有其他的蚂蚁聚拢过来，最后把食物抬回家，这里面其实有着非常多的道理的，在ACO中就用到了这个机理用于解决实际生活中的一些问题。

蚂蚁找食物

首先我们要具体说说一个有意思的事情，就是蚂蚁找食物的问题，理解了这个原理之后，对于理解ACO算法就非常容易了。蚂蚁作为那么小的动物，在地上漫无目的的寻找食物，起初都是没有目标的，他从蚂蚁洞中走出，随机的爬向各个方向，在这期间他会向外界播撒一种化学物质，姑且就叫做信息素，所以这里就可以得到的一个前提，越多蚂蚁走过的路径，信息素浓度就会越高，那么某条路径信息素浓度高了，自然就会有越多的蚂蚁感觉到了，就会聚集过来了。所以当众多蚂蚁中的一个找到食物之后，他就会在走过的路径中放出信息素浓度，因此就会有很多的蚂蚁赶来了。类似下面的场景：

至于蚂蚁是如何感知这个信息素，这个就得问生物学家了，我也没做过研究。

算法介绍

OK，有了上面这个自然生活中的生物场景之后，我们再来切入文章主题来学习一下蚁群算法，百度百科中对应蚁群算法是这么介绍的：蚁群算法是一种在图中寻找优化路径的机率型算法。他的灵感就是来自于蚂蚁发现食物的行为。蚁群算法是一种新的模拟进化优化的算法，与遗传算法有很多相似的地方。蚁群算法在比较早的时候成功解决了TSP旅行商的问题（在后面的例子中也会以这个例子）。要用算法去模拟蚂蚁的这种行为，关键在于信息素的在算法中的设计，以及路径中信息素浓度越大的路径，将会有更高的概率被蚂蚁所选择到。

算法原理

要想实现上面的几个模拟行为，需要借助几个公式，当然公式不是我自己定义的，主要有3个，如下图：

上图中所出现的alpha，beita，p等数字都是控制因子，所以可不必理会，Tij(n)的意思是在时间为n的时候，从城市i到城市j的路径的信息素浓度。类似于nij的字母是城市i到城市j距离的倒数。就是下面这个公式。

所以所有的公式都是为第一个公式服务的，第一个公式的意思是指第k只蚂蚁选择从城市i到城市j的概率，可以见得，这个受距离和信息素浓度的双重影响，距离越远，去此城市的概率自然也低，所以nij会等于距离的倒数，而且在算信息素浓度的时候，也考虑到了信息素浓度衰减的问题，所以会在上次的浓度值上乘以一个衰减因子P。另外还要加上本轮搜索增加的信息素浓度（假如有蚂蚁经过此路径的话），所以这几个公式的整体设计思想还是非常棒的。

算法的代码实现

由于本身我这里没有什么真实的数据，就随便自己构造了一个简单的数据，输入如下，分为城市名称和城市之间的距离，用#符号做区分标识，大家应该可以看得懂吧

 

[java]  

 

1. # CityName  
2. 1  
3. 2  
4. 3  
5. 4  
6. # Distance  
7. 1 2 1  
8. 1 3 1.4  
9. 1 4 1  
10. 2 3 1  
11. 2 4 1  
12. 3 4 1  

 

蚂蚁类Ant.:

 

[java]  

 

1. package DataMining_ACO;  
2.   
3. import java.util.ArrayList;  
4.   
5. /** 
6.  * 蚂蚁类，进行路径搜索的载体 
7.  *  
8.  *  lyq 
9.  *  
10.  */  
11. public class Ant implements Comparable<Ant> {  
12.     // 蚂蚁当前所在城市  
13.     String currentPos;  
14.     // 蚂蚁遍历完回到原点所用的总距离  
15.     Double sumDistance;  
16.     // 城市间的信息素浓度矩阵，随着时间的增多而减少  
17.     double[][] pheromoneMatrix;  
18.     // 蚂蚁已经走过的城市集合  
19.     ArrayList<String> visitedCitys;  
20.     // 还未走过的城市集合  
21.     ArrayList<String> nonVisitedCitys;  
22.     // 蚂蚁当前走过的路径  
23.     ArrayList<String> currentPath;  
24.   
25.     public Ant(double[][] pheromoneMatrix, ArrayList<String> nonVisitedCitys) {  
26.         this.pheromoneMatrix = pheromoneMatrix;  
27.         this.nonVisitedCitys = nonVisitedCitys;  
28.   
29.         this.visitedCitys = new ArrayList<>();  
30.         this.currentPath = new ArrayList<>();  
31.     }  
32.   
33.     /** 
34.      * 计算路径的总成本(距离) 
35.      *  
36.      *  
37.      */  
38.     public double calSumDistance() {  
39.         sumDistance = 0.0;  
40.         String lastCity;  
41.         String currentCity;  
42.   
43.         for (int i = 0; i < currentPath.size() - 1; i++) {  
44.             lastCity = currentPath.get(i);  
45.             currentCity = currentPath.get(i + 1);  
46.   
47.             // 通过距离矩阵进行计算  
48.             sumDistance += ACOTool.disMatrix[Integer.parseInt(lastCity)][Integer  
49.                     .parseInt(currentCity)];  
50.         }  
51.   
52.         return sumDistance;  
53.     }  
54.   
55.     /** 
56.      * 蚂蚁选择前往下一个城市 
57.      *  
58.      *  city 
59.      *            所选的城市 
60.      */  
61.     public void goToNextCity(String city) {  
62.         this.currentPath.add(city);  
63.         this.currentPos = city;  
64.         this.nonVisitedCitys.remove(city);  
65.         this.visitedCitys.add(city);  
66.     }  
67.   
68.     /** 
69.      * 判断蚂蚁是否已经又重新回到起点 
70.      *  
71.      *  
72.      */  
73.     public boolean isBack() {  
74.         boolean isBack = false;  
75.         String startPos;  
76.         String endPos;  
77.   
78.         if (currentPath.size() == 0) {  
79.             return isBack;  
80.         }  
81.   
82.         startPos = currentPath.get(0);  
83.         endPos = currentPath.get(currentPath.size() - 1);  
84.         if (currentPath.size() > 1 && startPos.equals(endPos)) {  
85.             isBack = true;  
86.         }  
87.   
88.         return isBack;  
89.     }  
90.   
91.     /** 
92.      * 判断蚂蚁在本次的走过的路径中是否包含从城市i到城市j 
93.      *  
94.      *  cityI 
95.      *            城市I 
96.      * @param cityJ 
97.      *            城市J 
98.      * @return 
99.      */  
100.     public boolean pathContained(String cityI, String cityJ) {  
101.         String lastCity;  
102.         String currentCity;  
103.         boolean isContained = false;  
104.   
105.         for (int i = 0; i < currentPath.size() - 1; i++) {  
106.             lastCity = currentPath.get(i);  
107.             currentCity = currentPath.get(i + 1);  
108.   
109.             // 如果某一段路径的始末位置一致，则认为有经过此城市  
110.             if ((lastCity.equals(cityI) && currentCity.equals(cityJ))  
111.                     || (lastCity.equals(cityJ) && currentCity.equals(cityI))) {  
112.                 isContained = true;  
113.                 break;  
114.             }  
115.         }  
116.   
117.         return isContained;  
118.     }  
119.   
120.     @Override  
121.     public int compareTo(Ant o) {  
122.         // TODO Auto-generated method stub  
123.         return this.sumDistance.compareTo(o.sumDistance);  
124.     }  
125. }  

 

蚁群算法工具类ACOTool.java:

[java]  

 

1. package DataMining_ACO;  
2.   
3. import java.io.BufferedReader;  
4. import java.io.File;  
5. import java.io.FileReader;  
6. import java.io.IOException;  
7. import java.text.MessageFormat;  
8. import java.util.ArrayList;  
9. import java.util.Collections;  
10. import java.util.HashMap;  
11. import java.util.Map;  
12. import java.util.Random;  
13.   
14. /** 
15.  * 蚁群算法工具类 
16.  *  
17.  * @author lyq 
18.  *  
19.  */  
20. public class ACOTool {  
21.     // 输入数据类型  
22.     public static final int INPUT_CITY_NAME = 1;  
23.     public static final int INPUT_CITY_DIS = 2;  
24.   
25.     // 城市间距离邻接矩阵  
26.     public static double[][] disMatrix;  
27.     // 当前时间  
28.     public static int currentTime;  
29.   
30.     // 测试数据地址  
31.     private String filePath;  
32.     // 蚂蚁数量  
33.     private int antNum;  
34.     // 控制参数  
35.     private double alpha;  
36.     private double beita;  
37.     private double p;  
38.     private double Q;  
39.     // 随机数产生器  
40.     private Random random;  
41.     // 城市名称集合,这里为了方便，将城市用数字表示  
42.     private ArrayList<String> totalCitys;  
43.     // 所有的蚂蚁集合  
44.     private ArrayList<Ant> totalAnts;  
45.     // 城市间的信息素浓度矩阵，随着时间的增多而减少  
46.     private double[][] pheromoneMatrix;  
47.     // 目标的最短路径,顺序为从集合的前部往后挪动  
48.     private ArrayList<String> bestPath;  
49.     // 信息素矩阵存储图,key采用的格式(i,j,t)->value  
50.     private Map<String, Double> pheromoneTimeMap;  
51.   
52.     public ACOTool(String filePath, int antNum, double alpha, double beita,  
53.             double p, double Q) {  
54.         this.filePath = filePath;  
55.         this.antNum = antNum;  
56.         this.alpha = alpha;  
57.         this.beita = beita;  
58.         this.p = p;  
59.         this.Q = Q;  
60.         this.currentTime = 0;  
61.   
62.         readDataFile();  
63.     }  
64.   
65.     /** 
66.      * 从文件中读取数据 
67.      */  
68.     private void readDataFile() {  
69.         File file = new File(filePath);  
70.         ArrayList<String[]> dataArray = new ArrayList<String[]>();  
71.   
72.         try {  
73.             BufferedReader in = new BufferedReader(new FileReader(file));  
74.             String str;  
75.             String[] tempArray;  
76.             while ((str = in.readLine()) != null) {  
77.                 tempArray = str.split(" ");  
78.                 dataArray.add(tempArray);  
79.             }  
80.             in.close();  
81.         } catch (IOException e) {  
82.             e.getStackTrace();  
83.         }  
84.   
85.         int flag = -1;  
86.         int src = 0;  
87.         int des = 0;  
88.         int size = 0;  
89.         // 进行城市名称种数的统计  
90.         this.totalCitys = new ArrayList<>();  
91.         for (String[] array : dataArray) {  
92.             if (array[0].equals("#") && totalCitys.size() == 0) {  
93.                 flag = INPUT_CITY_NAME;  
94.   
95.                 continue;  
96.             } else if (array[0].equals("#") && totalCitys.size() > 0) {  
97.                 size = totalCitys.size();  
98.                 // 初始化距离矩阵  
99.                 this.disMatrix = new double[size + 1][size + 1];  
100.                 this.pheromoneMatrix = new double[size + 1][size + 1];  
101.   
102.                 // 初始值-1代表此对应位置无值  
103.                 for (int i = 0; i < size; i++) {  
104.                     for (int j = 0; j < size; j++) {  
105.                         this.disMatrix[i][j] = -1;  
106.                         this.pheromoneMatrix[i][j] = -1;  
107.                     }  
108.                 }  
109.   
110.                 flag = INPUT_CITY_DIS;  
111.                 continue;  
112.             }  
113.   
114.             if (flag == INPUT_CITY_NAME) {  
115.                 this.totalCitys.add(array[0]);  
116.             } else {  
117.                 src = Integer.parseInt(array[0]);  
118.                 des = Integer.parseInt(array[1]);  
119.   
120.                 this.disMatrix[src][des] = Double.parseDouble(array[2]);  
121.                 this.disMatrix[des][src] = Double.parseDouble(array[2]);  
122.             }  
123.         }  
124.     }  
125.   
126.     /** 
127.      * 计算从蚂蚁城市i到j的概率 
128.      *  
129.      * @param cityI 
130.      *            城市I 
131.      * @param cityJ 
132.      *            城市J 
133.      * @param currentTime 
134.      *            当前时间 
135.      * @return 
136.      */  
137.     private double calIToJProbably(String cityI, String cityJ, int currentTime) {  
138.         double pro = 0;  
139.         double n = 0;  
140.         double pheromone;  
141.         int i;  
142.         int j;  
143.   
144.         i = Integer.parseInt(cityI);  
145.         j = Integer.parseInt(cityJ);  
146.   
147.         pheromone = getPheromone(currentTime, cityI, cityJ);  
148.         n = 1.0 / disMatrix[i][j];  
149.   
150.         if (pheromone == 0) {  
151.             pheromone = 1;  
152.         }  
153.   
154.         pro = Math.pow(n, alpha) * Math.pow(pheromone, beita);  
155.   
156.         return pro;  
157.     }  
158.   
159.     /** 
160.      * 计算综合概率蚂蚁从I城市走到J城市的概率 
161.      *  
162.      * @return 
163.      */  
164.     public String selectAntNextCity(Ant ant, int currentTime) {  
165.         double randomNum;  
166.         double tempPro;  
167.         // 总概率指数  
168.         double proTotal;  
169.         String nextCity = null;  
170.         ArrayList<String> allowedCitys;  
171.         // 各城市概率集  
172.         double[] proArray;  
173.   
174.         // 如果是刚刚开始的时候，没有路过任何城市，则随机返回一个城市  
175.         if (ant.currentPath.size() == 0) {  
176.             nextCity = String.valueOf(random.nextInt(totalCitys.size()) + 1);  
177.   
178.             return nextCity;  
179.         } else if (ant.nonVisitedCitys.isEmpty()) {  
180.             // 如果全部遍历完毕，则再次回到起点  
181.             nextCity = ant.currentPath.get(0);  
182.   
183.             return nextCity;  
184.         }  
185.   
186.         proTotal = 0;  
187.         allowedCitys = ant.nonVisitedCitys;  
188.         proArray = new double[allowedCitys.size()];  
189.   
190.         for (int i = 0; i < allowedCitys.size(); i++) {  
191.             nextCity = allowedCitys.get(i);  
192.             proArray[i] = calIToJProbably(ant.currentPos, nextCity, currentTime);  
193.             proTotal += proArray[i];  
194.         }  
195.   
196.         for (int i = 0; i < allowedCitys.size(); i++) {  
197.             // 归一化处理  
198.             proArray[i] /= proTotal;  
199.         }  
200.   
201.         // 用随机数选择下一个城市  
202.         randomNum = random.nextInt(100) + 1;  
203.         randomNum = randomNum / 100;  
204.         // 因为1.0是无法判断到的，,总和会无限接近1.0取为0.99做判断  
205.         if (randomNum == 1) {  
206.             randomNum = randomNum - 0.01;  
207.         }  
208.   
209.         tempPro = 0;  
210.         // 确定区间  
211.         for (int j = 0; j < allowedCitys.size(); j++) {  
212.             if (randomNum > tempPro && randomNum <= tempPro + proArray[j]) {  
213.                 // 采用拷贝的方式避免引用重复  
214.                 nextCity = allowedCitys.get(j);  
215.                 break;  
216.             } else {  
217.                 tempPro += proArray[j];  
218.             }  
219.         }  
220.   
221.         return nextCity;  
222.     }  
223.   
224.     /** 
225.      * 获取给定时间点上从城市i到城市j的信息素浓度 
226.      *  
227.      * @param t 
228.      * @param cityI 
229.      * @param cityJ 
230.      * @return 
231.      */  
232.     private double getPheromone(int t, String cityI, String cityJ) {  
233.         double pheromone = 0;  
234.         String key;  
235.   
236.         // 上一周期需将时间倒回一周期  
237.         key = MessageFormat.format("{0},{1},{2}", cityI, cityJ, t);  
238.   
239.         if (pheromoneTimeMap.containsKey(key)) {  
240.             pheromone = pheromoneTimeMap.get(key);  
241.         }  
242.   
243.         return pheromone;  
244.     }  
245.   
246.     /** 
247.      * 每轮结束，刷新信息素浓度矩阵 
248.      *  
249.      * @param t 
250.      */  
251.     private void refreshPheromone(int t) {  
252.         double pheromone = 0;  
253.         // 上一轮周期结束后的信息素浓度，丛信息素浓度图中查找  
254.         double lastTimeP = 0;  
255.         // 本轮信息素浓度增加量  
256.         double addPheromone;  
257.         String key;  
258.   
259.         for (String i : totalCitys) {  
260.             for (String j : totalCitys) {  
261.                 if (!i.equals(j)) {  
262.                     // 上一周期需将时间倒回一周期  
263.                     key = MessageFormat.format("{0},{1},{2}", i, j, t - 1);  
264.   
265.                     if (pheromoneTimeMap.containsKey(key)) {  
266.                         lastTimeP = pheromoneTimeMap.get(key);  
267.                     } else {  
268.                         lastTimeP = 0;  
269.                     }  
270.   
271.                     addPheromone = 0;  
272.                     for (Ant ant : totalAnts) {  
273.                         if(ant.pathContained(i, j)){  
274.                             // 每只蚂蚁传播的信息素为控制因子除以距离总成本  
275.                             addPheromone += Q / ant.calSumDistance();  
276.                         }  
277.                     }  
278.   
279.                     // 将上次的结果值加上递增的量，并存入图中  
280.                     pheromone = p * lastTimeP + addPheromone;  
281.                     key = MessageFormat.format("{0},{1},{2}", i, j, t);  
282.                     pheromoneTimeMap.put(key, pheromone);  
283.                 }  
284.             }  
285.         }  
286.   
287.     }  
288.   
289.     /** 
290.      * 蚁群算法迭代次数 
291.      * @param loopCount 
292.      * 具体遍历次数 
293.      */  
294.     public void antStartSearching(int loopCount) {  
295.         // 蚁群寻找的总次数  
296.         int count = 0;  
297.         // 选中的下一个城市  
298.         String selectedCity = "";  
299.   
300.         pheromoneTimeMap = new HashMap<String, Double>();  
301.         totalAnts = new ArrayList<>();  
302.         random = new Random();  
303.   
304.         while (count < loopCount) {  
305.             initAnts();  
306.   
307.             while (true) {  
308.                 for (Ant ant : totalAnts) {  
309.                     selectedCity = selectAntNextCity(ant, currentTime);  
310.                     ant.goToNextCity(selectedCity);  
311.                 }  
312.   
313.                 // 如果已经遍历完所有城市，则跳出此轮循环  
314.                 if (totalAnts.get(0).isBack()) {  
315.                     break;  
316.                 }  
317.             }  
318.   
319.             // 周期时间叠加  
320.             currentTime++;  
321.             refreshPheromone(currentTime);  
322.             count++;  
323.         }  
324.   
325.         // 根据距离成本，选出所花距离最短的一个路径  
326.         Collections.sort(totalAnts);  
327.         bestPath = totalAnts.get(0).currentPath;  
328.         System.out.println(MessageFormat.format("经过{0}次循环遍历，最终得出的最佳路径：", count));  
329.         System.out.print("entrance");  
330.         for (String cityName : bestPath) {  
331.             System.out.print(MessageFormat.format("-->{0}", cityName));  
332.         }  
333.     }  
334.   
335.     /** 
336.      * 初始化蚁群操作 
337.      */  
338.     private void initAnts() {  
339.         Ant tempAnt;  
340.         ArrayList<String> nonVisitedCitys;  
341.         totalAnts.clear();  
342.   
343.         // 初始化蚁群  
344.         for (int i = 0; i < antNum; i++) {  
345.             nonVisitedCitys = (ArrayList<String>) totalCitys.clone();  
346.             tempAnt = new Ant(pheromoneMatrix, nonVisitedCitys);  
347.   
348.             totalAnts.add(tempAnt);  
349.         }  
350.     }  
351. }  

场景测试类Client.java:

 

[java]  

 

1. package DataMining_ACO;  
2.   
3. /** 
4.  * 蚁群算法测试类 
5.  * @author lyq 
6.  * 
7.  */  
8. public class Client {  
9.     public static void main(String[] args){  
10.         //测试数据  
11.         String filePath = "C:\\Users\\lyq\\Desktop\\icon\\input.txt";  
12.         //蚂蚁数量  
13.         int antNum;  
14.         //蚁群算法迭代次数  
15.         int loopCount;  
16.         //控制参数  
17.         double alpha;  
18.         double beita;  
19.         double p;  
20.         double Q;  
21.           
22.         antNum = 3;  
23.         alpha = 0.5;  
24.         beita = 1;  
25.         p = 0.5;  
26.         Q = 5;  
27.         loopCount = 5;  
28.           
29.         ACOTool tool = new ACOTool(filePath, antNum, alpha, beita, p, Q);  
30.         tool.antStartSearching(loopCount);  
31.     }  
32. }  

 

算法的输出，就是在多次搜索之后，找到的路径中最短的一个路径：

 

[java]  

 

1. 经过5次循环遍历，最终得出的最佳路径：  
2. entrance-->4-->1-->2-->3-->4  

 

因为数据量比较小，并不能看出蚁群算法在这方面的优势，博友们可以再次基础上自行改造，并用大一点的数据做测试，其中的4个控制因子也可以调控。蚁群算法作为一种启发式算法，还可以和遗传算法结合，创造出更优的算法。蚁群算法可以解决许多这样的连通图路径优化问题。但是有的时候也会出现搜索时间过长的问题。