蚁群算法(ACA)详细介绍（JAVA实现及代码详解)_蚁群算法 java

1.蚁群算法概要

什么是蚁群算法

• 蚁群算法是一种用于寻找优化路径的概率算法
• 蚁群算法模拟蚁群可以在不同的环境中寻找到最优路径
• 进一步研究表明，蚂蚁在路径上会释放一种称之为信息素的物质，假如一只蚂蚁寻找到食物（较优路径），其在路径上的信息素（概率）就会引导同伴蚂蚁走相同的路径，蚂蚁增多的同时释放更浓的信息素（正反馈机制）。假设信息素引导的路径不是食物（不是较优路径），则这条路径的信息素就只有相对较少的值（与有食物的路径相比较小）。
• 信息素会随着时间流失而挥发（较差的路径被选择的概率变小）
• 由以上的描述可知，算法应模拟蚁群，令不同的蚂蚁去寻食（找更短的路径），若寻找到食物（较优路径），通过释放信息素（改变路径被选中的概率），引导其余蚂蚁选择更优的路径。通过不断寻找（在较优路径的基础上不断地迭代寻找更优的路径），最终找到一个比较短的距离（最终的路径）。
• 在具体实现采用的是TSP问题，蚁群算法还可用于其他问题求解，在此不多做说明。

蚁群算法的数学公式

蚂蚁从i城市到j城市的概率公式

$p_{i,j}^k$ = $\frac{[{\tau }_{i,j}^{}(t){]}^{\alpha }[{\eta }_{i,j}^{}(t){]}^{\beta }}{{\sum }_{j\in allow(k)}[{\tau }_{i,j}^{}(t){]}^{\alpha }[{\eta }_{i,j}^{}(t){]}^{\beta }}j\in allow(k)$

• 其中K是第K只蚂蚁，i,j是两座城市之间的边，$p_{i,j}^k$意为第K只蚂蚁在I城市选择去J城市的可能性，且J城市一定为K蚂蚁从未到达的城市。
• $[{\tau }_{i,j}^{}(t){]}^{\alpha }$:$[{\tau }_{i,j}^{}(t)]$为路径上的信息素浓度，$\alpha$代表信息素重要程度。
• $[{\eta }_{i,j}^{}(t){]}^{\beta }$:$[{\eta }_{i,j}^{}(t)]$是i到j城市的距离的倒数，$\beta$代表路径距离重要程度。
• $allow(k)$是存放当前没有走过城市的集合。
• 当一个城市不在allow(k)中时，我们将其概率P设置为0。

信息素的释放公式

$\Delta {\tau }_{i,j}^{}(t)$ $=\frac{Q}{L_k^{}}$

• 这里采用蚂蚁每走完一周才释放信息素，具体代码实现时是让所有蚂蚁走完一圈才进行信息素的释放，以避免前面的蚂蚁直接影响到后面的蚂蚁。
• $Q$是一个常量（我设置为1），$L_k^{}$为第$K$只蚂蚁经过的路径长度

信息素的挥发公式

${\tau }_{i,j}^{}(t)=\rho \ast {\tau }_{i,j}^{}(t)$（$\rho$为设置的挥发系数）

蚁群算法的框架

• 初始化参数：对初始的信息素浓度进行定义，定义如α之类的常量，设置蚂蚁的个数，以及循环(iter)的次数
• 进行循环：令蚁群进行觅食，每进行一次迭代，更新信息素，并释放信息素，若本次产生较前次更优的路径，则记录更优解。
• 得到最终结果，并输出路径

2.TSP描述（旅行商问题)

旅行商问题是给定一组城市，环绕此城市一圈，经过每一个城市，找到路径的最短距离。
此类问题在路径较小时可使用暴力解，但当城市数量较多时（本次采用ATT48的数据，共48个城市，解空间大小为48的阶乘），暴力解及传统的解法无法在较短的时间内计算出路径（普通计算机得连续工作几万年，反正那时谁还记得谁，另一句，几万年是我瞎BB的，就是时间很长就行了，不过也差不多是这个数），这显然不是我们想要的，而贪婪算法能在有限时间内求得一个较好的答案，但仍然离最优解相差甚远（误差值达到13%）。
蚁群算法本质上是一种启发式的优化算法，有分布计算、信息正反馈和启发式搜索的特征，能尽量避开局部最优，达到一个较好的解（根据我的实测，依然不如遗传算法，有时间再写个遗传算法）。

3.JAVA源代码实现

参数设置

参数设置对于蚁群算法的性能有着极其重要的影响，不同的参数设置会导致结果的较大差异，一般情况下将不同常量设置如下可取得较好的结果：
$\alpha$（信息素浓度的影响因子）:设置为1；
$\beta$（城市间距离的影响因子）:设置为5；
$\rho$（挥发因子）：设置为0.9。

几个重要的函数

通过这几天写各种算法，我深刻体会到将不同的计算包装成不同的函数，可以提高很大的效率，以下介绍几个具体的函数。

• init_p(int [][]distance)：对路径开始的信息素浓度进行初始化，初始值我将他设定为路径与每个结点路径和的倒数；
• roulette(double [][]p,int current,int []allow,int[][]distance)：轮盘赌算法，用于结点概率的选择；
• not_exit(int current,int []allow)：判断当前选择的城市是否存在于ALLOW子集，这一点至关重要；
• init(String filename) ：算出距离矩阵，返回二维数组Distance.
• 这里额外提一下，什么是伪欧式距离，第一次接触这个我也比较懵逼，他对原距离进行了除以根号十的处理，现在才明白这个距离是官方文档(ATT48数据集)定义的距离公式，他综合考虑了以下两点因素，1.地球是圆的（欧式距离计算的是平面距离）2.大数据不方便处理，所以采用了这个公式。
  JAVA代码公式体现在这：double rij = Math .sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) /10.0);

JAVA具体代码

蚁群算法类（main方法所在类）：

package aca;

import java.awt.Image;
import java.io.IOException;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.stream.events.StartDocument;

public class ACA {
	int ant_num=50;/*蚂蚁数量*/
	int alpha =1;//α因子
	int beta = 5;//β因子
	static double rho =0.9;//信息素挥发因子
	int Q=1;//常数
	public double[][] init_p(int [][]distance) {
	//对信息素概率的初始量进行更新，初始概率为每个点到其余点的路径和分之路径
		double p[][] = new double[48][48] ;//用于保存信息素概率
		for(int i=0;i<48;i++) {
			double sum = for_each_sum(distance, i);//对每个结点进行和的计算
			for(int j=0;j<48;j++) {
				p[i][j]=(distance[i][j]*1.0)/sum;
			}
		}
		for(int i=0;i<48;i++) {
			p[i][i]=0;
		}
		return p;
	}
	public int[] start(double [][]p,int[][]distance) {
		int length=0;
		int []allow = new int[48];//保存走过的距离
		for(int m=0;m<48;m++) {
			allow[m]=100;//防止NOT_EXIT失效
		}
		int i=0;
		int temple = (int) (Math.random()*48);
		allow[i]=temple;
		i++;
		int current =temple;
		while(i<48) {
			int tmp[]= new int[48];
			for(int m=0;m<48;m++) {
				tmp[m]=allow[m];
				//System.out.println(m);
			}
			int next = roulette(p, current, tmp,distance);
			allow[i]=next;
			current = next;
			i++;
		}
		return allow;
	}
	public int roulette(double [][]p,int current,int []allow,int[][]distance) {
		//轮盘赌，current为当前城市标号
		double sum =0;
		int temple = 0;
		double a = sum_single_possible(distance, p, current,allow);
		while(sum<0.3) {
			temple = (int) (Math.random()*48);
			if(not_exit(temple, allow)) {
				//假如该数不在数组里，则令概率增加
				double n =1.0/distance[current][temple];
				n = Math.pow(n, beta);
				double t = p[current][temple];
				t = Math.pow(t, alpha);
				sum =sum + n*t*1.0/a;
				
			}
		}
		return temple;
		
	}
	public double sum_single_possible(int [][]distance,double[][]p,int current,int[]allow) {
		//根据公式计算概率
		double sum=0;
		for(int i=0;i<48;i++) {
			if(not_exit(i, allow)) {
				double a =1.0/distance[current][i];
				a= Math.pow(a,beta);
				double b =p[current][i];
				b= Math.pow(b, alpha);
				sum = sum+a*b;
			}
		}
		return sum;
	}
	public boolean not_exit(int current,int []allow) {
		//判断当前数是否已经存在于走过的路径中
		boolean flag = true;
		for(int i=0;i<allow.length;i++) {
			if(current == allow[i])
				return false;
		}
		return true;
	}
	public double for_each_sum(int [][]distance,int i) {
		//辅助函数，帮助计算每行总值，I表达第I个结点
		double sum=0;
		for(int j = 0;j<48;j++)
		{
			sum = sum + distance[i][j];
		}
		return sum;
		}
	public int sum_path_length(int [][]distance,int [][]path,int current) {
		//辅助函数，计算蚂蚁走过路径总值
		int sum=0;
		for(int i=0;i<47;i++) {
			sum = sum + distance[path[current][i]][path[current][i+1]];
		}
		sum = sum + distance[path[current][47]][path[current][0]];
		return sum;
	}
	
	public static void main(String []args) throws IOException {
		bbtsp a = new bbtsp();
		int [][]distance = a.init("c://data.txt");
		ACA b =new ACA();
		double p[][] =b.init_p(distance);//产生概率
		int iter = 200;
		int i=1;
		int [][]path = new int[50][48];
		int min = Integer.MAX_VALUE;//保存最佳路径
		int best_path[]=new int[48];//保存最佳路径
		while(i<100) {
			for(int j=0;j<50;j++)//令每个蚂蚁去寻找路径
			{
				int[]allow = b.start(p,distance);//产生一个初始路径
				for(int m=0;m<48;m++) {//将此值保存在路径数组中用于处理
					path[j][m]=allow[m];
				}
			}
			//释放信息素
			for(int j=0;j<50;j++) {
				int current = j;//选中第J条路径
				int L = b.sum_path_length(distance, path, current);//计算每条路径长度
				if(L<min) {
					min = L;//更新最优解
					for(int k=0;k<48;k++)//保存最短路径
					{
						best_path[k]=path[current][k];
					}
			
				}
				for(int k=0;k<47;k++) {
					//释放信息素的值
					p[path[j][k]][path[j][k+1]]=p[path[j][k]][path[j][k+1]]+1.0/L;
				}
				p[path[j][47]][path[j][0]]=p[path[j][47]][path[j][0]]+1.0/L;
			}
			//挥发信息素
			for(int j=0;j<48;j++) {
				for(int k=0;k<48;k++) {
					p[j][k]=rho*p[j][k];
				}
			}
			i++;
			
		}
		System.out.println("最终路径：");
		for(int k=0;k<48;k++) {
			System.out.print(best_path[k]+1+" ");
		}
		System.out.print("最小距离：");
		System.out.println(min);
		/*int[]allow = b.start(p,distance); 
		for(int i=0;i<48;i++)
		{
			for(int j=0;j<48;j++) {
				if(allow[i]>allow[j]) {
					int temp=allow[i];
					allow[i]=allow[j];
					allow[j]=temp;
				}
			}
		}
		for(int j = 0;j<48;j++)
		{
			System.out.println(allow[j]);
		}*/
		
	}
	
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186

返回距离矩阵的类：

package aca;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

class bbtsp{
	int [][]distance;//距离矩阵
	int citynum = 48;
	public bbtsp(int [][]dis) {
		this.distance = dis;
	}
	public bbtsp() {
	}
	
	
	public int[][] 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坐标
		}
		data.close();
 
		// 计算距离矩阵
		// ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628
		for (int i = 0; i < citynum - 1; i++) {
			distance[i][i] = -1; // 对角线为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] = -1;
        return distance;
	}
	
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

运行结果及分析

这是我得到的11011的数据：11011
5 48 42 10 24 45 35 4 26 2 29 41 16 22 3 34
14 25 13 23 11 12 15 40 9 1 8 38 31 44 18 7
28 36 6 37 19 27 43 17 30 46 33 20 47 21
32 39
最优解为10628，误差值为0.03%，显然这个误差值是比较大的，但相对于贪婪算法13％的误差，这个值还能接受