蚁群(ACO)算法求解TSP问题（附C#，Java代码及注释）
蚁群(ACO)算法求解TSP问题（附C#，Java代码及注释）
前言
各位读者大家好，今天我们来讲讲蚁群算法。
在写这篇蚁群算法推文期间，小编曾一度崩溃，只是换掉原文算例，即将“60个城市随机生成距离”换成Oliver30等标准实例，跑出来的结果就惨不忍睹，实是被按在地上摩擦。正如鲁迅先生《狂人日记》中所写：凡事总须研究，才会明白。小编怀着一颗虔诚滴心，遍查全网，亲身试验诸般方法，尽管最终由于学识浅薄，还是没有成功解决，但对启发式算法的了解却也加深了几分。
蚁群算法在求解TSP中取得了较好的效果，但相对于遗传算法等优化方法，其缺少系统的理论指导，特别是参数的设置，通常是根据经验或反复试验来选取合适的参数值。
我翻开Internet一查，这Internet不分年代。长长短短的每页上都写着“参数设置”几个字，我横竖睡不着，仔细看了半夜，才从字缝里看出来，满纸上都写着四个字“反复实验”。
言归正传，
蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法最早是由意大利学者Colorni A., Dorigo M. 等于1991年提出。
蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。如图所示：
关于蚁群算法的具体介绍详见之前推文干货|十分钟快速get蚁群算法（附代码）
本文将解决 TSP 的一个实例，其目标是找到访问60个城市中每一个城市的最短路径。演示程序使用四只蚂蚁; 每只蚂蚁代表一个潜在的解决方案。ACO 需要指定几个参数，例如信息启发式因子(alpha)和信息挥发因子(rho)。这四只蚂蚁在60个城市中被初始化为随机路径; 初始化后，最好的蚂蚁的最短路径长度为260.0个单位。蚁群算法的核心思想是利用模拟信息素，吸引蚂蚁在图中寻找更好的路径。主处理循环在根据当前信息素值更新蚂蚁行踪和根据新行踪更新信息素之间交替进行。在通过主处理循环的最大次数(1000次)之后，程序显示找到的最佳路径及其对应的长度(61.0个单位)。
这个60个城市的图表是人工构建的，每个城市都与其他城市相连，任意两个城市之间的距离是1.0到8.0任意单位(英里，公里等等)之间的随机值。求解 TSP 问题没有简单的方法。对于60个城市，假设你可以从任何一个城市开始，向前或向后，并且所有的城市都是相连的，那么总共有
个可能的解。即使你可以每秒估计10亿个可能的解，也需要
年才能检查完，这比宇宙的估计年龄要长很多倍。
“各参数： m——蚂蚁数目 α——信息素的相对重要程度 β——启发式因子的相对重要程度 ρ——信息素蒸发系数 Q——信息素增加系数
参数设置对蚁群算法性能的影响非常大， α值越大，蚂蚁选择以前经过的路线的可能性越大，但过大会使搜索过早陷于局部最小解； β值越大，蚂蚁选择离它近的城市的可能性也越大； ρ如果取值不恰当，得到的结果会很差。
故其存在下列不足： （1）如果参数a、β、p、m、Q等设置不当，会导致求解速度很慢且所得解的质量特别差； （2）基本蚁群算法计算量大，求解所需的时间较长； （3）基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环次数的条件下很难实现这种情况。
Part 1 代码结构
import java.util.Random;
import java.util.Scanner;
public class AntColonyProgram {
private static Random random = new Random(2);
/** influence of pheromone on direction */
private static final int alpha = 3;
/** influence of adjacent node distance */
private static final int beta = 2;
/** pheromone decrease factor */
private static final double rho = 0.01;
/** pheromone increase factor */
private static final double Q = 2.0;
public static void main(String[] args) {
try {
System.out.println("\nBegin Ant Colony Optimization demo\n");
int numCities = 60;
int numAnts = 4;
int maxTime = 1000;
System.out.println("Number cities in problem = " + numCities);
System.out.println("\nNumber ants = " + numAnts);
System.out.println("Maximum time = " + maxTime);
System.out.println("\nAlpha (pheromone influence) = " + alpha);
System.out.println("Beta (local node influence) = " + beta);
System.out.println("Rho (pheromone evaporation coefficient) = " + rho);
System.out.println("Q (pheromone deposit factor) = " + Q);
System.out.println("\nInitialing dummy graph distances");
int[][] dists = MakeGraphDistances(numCities);
System.out.println("\nInitialing ants to random trails\n");
int[][] ants = InitAnts(numAnts, numCities);
// initialize ants to random trails
ShowAnts(ants, dists);
// determine the best initial trail
int[] bestTrail = AntColonyProgram.BestTrail(ants, dists);
// the length of the best trail
double bestlength = length(bestTrail, dists);
System.out.print("\nBest initial trail length: " + bestlength + "\n");
// Display(bestTrail);
System.out.println("\nInitializing pheromones on trails");
double[][] pheromones = InitPheromones(numCities);
int time = 0;
System.out.println("\nEntering UpdateAnts - UpdatePheromones loop\n");
while (time < maxTime) {
UpdateAnts(ants, pheromones, dists);
UpdatePheromones(pheromones, ants, dists);
int[] currBestTrail = AntColonyProgram.BestTrail(ants, dists);
double currBestlength = length(currBestTrail, dists);
if (currBestlength < bestlength) {
bestlength = currBestlength;
bestTrail = currBestTrail;
System.out.println("New best length of " + bestlength + " found at time " + time);
}
time += 1;
}
System.out.println("\nTime complete");
System.out.println("\nBest trail found:");
Display(bestTrail);
System.out.println("\nlength of best trail found: " + bestlength);
System.out.println("\nEnd Ant Colony Optimization demo\n");
Scanner sc = new Scanner(System.in);
sc.nextLine();
} catch (Exception ex) {
System.out.println(ex.getMessage());
Scanner sc = new Scanner(System.in);
sc.nextLine();
}
}
// Main
// --------------------------------------------------------------------------------------------
private static int[][] InitAnts(int numAnts, int numCities) throws Exception {..}
public static int[] RandomTrail(int start, int numCities) throws Exception {..}
private static int IndexOfTarget(int[] trail, int target) throws Exception {..}
private static double length(int[] trail, int[][] dists) {..}
// --------------------------------------------------------------------------------------------
private static int[] BestTrail(int[][] ants, int[][] dists) {..}
// --------------------------------------------------------------------------------------------
private static double[][] InitPheromones(int numCities) {..}
// --------------------------------------------------------------------------------------------
private static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists) throws Exception {..}
private static int[] BuildTrail(int k, int start, double[][] pheromones, int[][] dists) throws Exception {..}
private static int NextCity(int k, int cityX, boolean[] visited, double[][] pheromones, int[][] dists) throws Exception {..}
private static double[] MoveProbs(int k, int cityX, boolean[] visited, double[][] pheromones, int[][] dists) {..}
// --------------------------------------------------------------------------------------------
private static void UpdatePheromones(double[][] pheromones, int[][] ants, int[][] dists) throws Exception {..}
private static boolean EdgeInTrail(int cityX, int cityY, int[] trail) throws Exception {..}
// --------------------------------------------------------------------------------------------
private static int[][] MakeGraphDistances(int numCities) {..}
private static double Distance(int cityX, int cityY, int[][] dists) {..}
// --------------------------------------------------------------------------------------------
private static void Display(int[] trail) {..}
private static void ShowAnts(int[][] ants, int[][] dists) {..}
private static void Display(double[][] pheromones) {..}
}
两个关键的方法是 UpdateAnts 和 UpdatePheromones。方法 UpdateAnts 调用方法BuildTrail，它调用 NextCity，后者调用 MoveProbs。方法 UpdatePheromones 调用 EdgeInTrail，它调用 IndexOfTarget。
Part 2 建立邻接表
使用 MakeGraphDistances 方法建立了一个邻接图表:
private static int[][] MakeGraphDistances(int numCities) {
int[][] dists = new int[numCities][];
for (int i = 0; i <= dists.length - 1; i++) {
dists[i] = new int[numCities];
}
for (int i = 0; i <= numCities - 1; i++) {
for (int j = i + 1; j <= numCities - 1; j++) {
int d = random.nextInt(8) + 1; // [1,8]
dists[i][j] = d;
dists[j][i] = d;
}
}
return dists;
}
通过创建一个二维数组模拟了一个图形，其中行索引 i 表示 from-city，列索引 j 表示 to-city。注意，所有的城市都是相连的，距离是对称的，从一个城市到它自己的距离是0。
Part 3初始化
ant 只是一组 int 值，表示从初始城市到所有其他城市的路径顺序。
private static int[][] InitAnts(int numAnts, int numCities) throws Exception {
int[][] ants = new int[numAnts][];
for (int k = 0; k <= numAnts - 1; k++) {
int start = random.nextInt(numCities);
ants[k] = RandomTrail(start, numCities);
}
return ants;
}
初始化方法为每只蚂蚁的踪迹分配一行，随机选择一个开始城市，然后调用方法 RandomTrail:
public static int[] RandomTrail(int start, int numCities) throws Exception {
// helper for InitAnts
int[] trail = new int[numCities];
// sequential
for (int i = 0; i <= numCities - 1; i++) {
trail[i] = i;
}
// Fisher-Yates shuffle
for (int i = 0; i <= numCities - 1; i++) {
int r = random.nextInt(numCities - i) + i;
int tmp = trail[r];
trail[r] = trail[i];
trail[i] = tmp;
}
int idx = IndexOfTarget(trail, start);
// put start at [0]
int temp = trail[0];
trail[0] = trail[idx];
trail[idx] = temp;
return trail;
}
RandomTrail 分配一条路径，并将其初始化为0,1,2，... numCities-1。其次，该方法使用 Fisher-Yates 洗牌算法随机打乱城市顺序。然后将指定的起始城市交换到当前路径的位置[0]中。
信息素是蚂蚁在它们的路径上放置的化学物质; 它们吸引其他蚂蚁。更多的蚂蚁会选择一条较短的路径前往食物来源，并且比选择较长的路径存储更多的信息素。信息素随着时间慢慢蒸发。以下是InitPheromones方法：
private static double[][] InitPheromones(int numCities) {
double[][] pheromones = new double[numCities][];
for (int i = 0; i <= numCities - 1; i++) {
pheromones[i] = new double[numCities];
}
for (int i = 0; i <= pheromones.length - 1; i++) {
for (int j = 0; j <= pheromones[i].length - 1; j++) {
pheromones[i][j] = 0.01;
// otherwise first call to UpdateAnts -> BuiuldTrail -> NextNode -> MoveProbs => all 0.0 => throws
}
}
return pheromones;
}
信息素信息存储在对称矩阵中，其中行索引 i 是 from-city，列索引 j 是 to-city。所有值最初都被设置为一个任意小的值(0.01) ，以便启动 UpdateAnts-UpdatePheromones 循环。
Part 4 更新蚂蚁
蚁群优化算法的关键是通过构造一个更新蚂蚁及其轨迹的过程，希望能够更好地利用信息素和距离信息。如下图，假设我们现在只有五个城市。在图中，一只蚂蚁的新路径正在建立中。从城市1开始，然后到城市3，update算法确定下一个城市。现在假设信息素和距离信息如图所示。确定下一个城市的第一步是构建一个数组，称为“taueta”。taueta的值计算公式是
回想一下，alpha 和 beta 是必须指定的全局常量。这里我假定alpha是3，beta是2。城市1和城市3的 taueta 值没有计算，因为它们已经在当前路径中。注意，信息素和taueta成正比，距离和taueta成反比。
在计算完所有 taueta 值之后，下一步是将这些值转换为概率，并将它们放置在数组 probs 中。算法对taueta值进行求和，得到82.26，然后用求和除每个taueta值。此时，city 0被选中的概率为0.09，以此类推。接下来，算法需要根据计算出的概率选择下一个城市。正如我前面提到的，我在本文中介绍的 ACO 算法使用了一种称为轮盘赌选择的方式。现构建了一个叫做 cumul 的数组，它可以存储的累加和，其大小比数组 probs 多一个元素，cumul[0]的值为0.0。在构建了 cumul 数组之后，将生成一个介于0.0和1.0之间的随机数 p。假设 p = 0.538，如图所示。该 p 值位于 cumul 数组中位于[2]和[3]之间，这意味着city 2被选为下一个城市。
UpdateAnts方法：
private static void UpdateAnts(int[][] ants, double[][] pheromones, int[][] dists) throws Exception {
int numCities = pheromones.length;
for (int k = 0; k <= ants.length - 1; k++) {
int start = random.nextInt(numCities);
int[] newTrail = BuildTrail(k, start, pheromones, dists);
ants[k] = newTrail;
}
}
注意，每个蚂蚁都被分配到一个新的、随机的起始城市，而不是保留旧的起始城市。大部分实际工作是由方法 BuildTrail 执行的，如下所示。
private static int[] BuildTrail(int k, int start, double[][] pheromones, int[][] dists) throws Exception {
int numCities = pheromones.length;
int[] trail = new int[numCities];
boolean[] visited = new boolean[numCities];
trail[0] = start;
visited[start] = true;
for (int i = 0; i <= numCities - 2; i++) {
int cityX = trail[i];
int next = NextCity(k, cityX, visited, pheromones, dists);
trail[i + 1] = next;
visited[next] = true;
}
return trail;
}
BuildTrail 有一个布尔数组visited，这样创建的路径就不会包含重复的城市。Trail[0]是开始城市，然后每个城市依次通过方法 NextCity 添加，如下所示。
private static int NextCity(int k, int cityX, boolean[] visited, double[][] pheromones, int[][] dists) throws Exception {
// for ant k (with visited[]), at nodeX, what is next node in trail?
double[] probs = MoveProbs(k, cityX, visited, pheromones, dists);
double[] cumul = new double[probs.length + 1];
for (int i = 0; i <= probs.length - 1; i++) {
cumul[i + 1] = cumul[i] + probs[i];
// consider setting cumul[cuml.length-1] to 1.00
}
double p = random.nextDouble();
for (int i = 0; i <= cumul.length - 2; i++) {
if (p >= cumul[i] && p < cumul[i + 1]) {
return i;
}
}
throw new Exception("Failure to return valid city in NextCity");
}
part 5 更新信息素
更新信息素比更新蚂蚁的轨迹容易得多。方法中的关键代码是:
double decrease = (1.0 - rho) * pheromones[i][j];
double increase = 0.0;
if (EdgeInTrail(i, j, ants[k])) {
increase = (Q / length);
}
pheromones[i][j] = decrease + increase;
信息素值降低，模拟蒸发，增加模拟蚂蚁在路径上的信息素沉积。减少的效果是由当前信息素值乘以一个小于1.0的值，这取决于全局参数 ρ。Rho 越大，信息素值的下降越大。增加的效果是通过增加当前蚂蚁的总尾长的比例，其中这个比例是由全局参数 Q 决定的。 Q 值越大，信息素的添加量就越大。方法 UpdatePheromones 调用 EdgeTrail方法，它确定两个城市之间的一个片段是否在蚂蚁当前的轨迹上。
欲下载本文相关代码，请移步留言区
参考内容：
1）Test Run - Ant Colony Optimization | Microsoft Docs
2）叶志伟、郑肇葆 蚁群算法中参数 α、β 、ρ设置的研究 ——以 TSP 问题为例 武 汉 大 学 学 报 · 信 息 科 学 版
3）严小燕，夏桂林 蚁群算法求解TSP中的参数设置 ISSN 1009-3044
-The End-