蚁群算法笔记

    最近阅读论文，提到几种常见的搜索算法，于是对比学习一下。本文转载数据之巅大神文章对蚁群算法进行简单介绍，并用C++语言编码实现蚁群算法来解决旅行商（TSP）问题。

1 蚁群算法基本原理

1.1 算法综述

    对于TSP类问题,求解算法大致可分为精确算法和人工智能算法两大类。精确性算法基于严格的数学手段,在可以求解的情况下,解的质量较好。但是由于算法严格,运算量大,特别是大规模的问题几乎无法求解。所以其应用只能是小规模的确定性问题，面对中小规模问题,人工智能算法在精度上不占优势。但规模变大时,人工智能方法基本能在可接受时间里,找到可接受的满意解,这是精确算法难以做到的。由于的实际问题,各种约束错综复杂,人工智能算法显示出了巨大的优越性,也正因为如此,实际应用中,人工智能算法要更广泛。求解车辆路径调度问题的精确算法有动态规划法、分枝定界法等。并开始寻求所得结果可接受的启发式算法,以处理大规模实际问题，一些其他学科的新一代优化算法相继出现,如禁忌搜索算法,遗传算法,人工神经网络算法,以及现在研究较多的蚁群算法等。

1.2 群蚁算法的原理

    蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明：一群相互协作的蚂蚁能够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体之间的行为是相互作用相互影响的。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为信息素的物质,而此物质恰恰是蚂蚁个体之间信息传递交流的载体。蚂蚁在运动时能够感知这种物质,并且习惯于追踪此物质爬行,当然爬行过程中还会释放信息素。一条路上的信息素踪迹越浓,其它蚂蚁将以越高的概率跟随爬行此路径,从而该路径上的信息素踪迹会被加强,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。某一路径上走过的蚂蚁越多,则后来者选择该路径的可能性就越大。蚂蚁个体之间就是通过这种间接的通信机制实现协同搜索最短路径的目标的。我们举例简单说明蚂蚁觅食行为：

    如上图a,b,c的示意图：
    a图是原始状态，蚂蚁起始点为A，要到达E，中途有障碍物，要绕过才能到达。BC和BH是绕过障碍物的2条路径(假设只有2条)。各个路径的距离d已经标定。
    b图是t=0时刻蚂蚁状态，各个边上有相等的信息素浓度，假设为15；
    c图是t=1时刻蚂蚁经过后的状态，各个边的信息素浓度，有变化；因为大量蚂蚁的选择概率会不一样，而选择概率是和路径长度相关的。所以越短路径的浓度会越来越大，经过此短路径达到目的地的蚂蚁也会比其他路径多。这样大量的蚂蚁实践之后就找到了最短路径。所以这个过程本质可以概括为以下几点：
    1.路径概率选择机制信息素踪迹越浓的路径,被选中的概率越大
    2.信息素更新机制路径越短,路径上的信息素踪迹增长得越快
    3.协同工作机制蚂蚁个体通过信息素进行信息交流。
从蚂蚁觅食的原理可见,单个个体的行为非常简单蚂蚁只知道跟踪信息素爬行并释放信息素,但组合后的群体智能又非常高蚂蚁群能在复杂的地理分布的清况下,轻松找到蚁穴与食物源之间的最短路径。这种特点恰恰与元启发算法的特点相一致,蚁群优化算法正是受到这种生态学现象的启发后加以模仿并改进而来,觅食的蚂蚁由人工蚁替代,蚂蚁释放的信息素变成了人工信息素,蚂蚁爬行和信息素的蒸发不再是连续不断的,而是在离散的时空中进行。

   从深层意义上来讲,蚁群算法作为优化的方法之一,属于人工群集智能领域。人工群集智能,大都受自然群集智能如昆虫群和动物群等的启发而来。除了具有独特的强有力的合作搜索能力外,还可以利用一系列的计算代理对问题进行分布式处理,从而大大提高搜索效率。

2 蚁群算法的基本流程

    我们还是采用大连理工大学谷俊峰的PPT来说明问题，重要公式进行截图计算和解释，对PPT难以理解的地方进行单独解释：

2.1 基本数学模型

    首先看看基本TSP问题的基本数学模型：

    问题其实很简单，目标函数就是各个走过路径的总长度，注意的就是距离矩阵根据实际的问题不一样，长度是不一样的。

2.2 群蚁算法说明

    在说明群蚁算法流程之前，我们对算法原理和几个注意点进行描述：

        1.TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1. 信息素值也称信息素痕迹。2.可见度，即先验值。
        2.信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。
        3.蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。
        4.蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。

2.3 群蚁算法说明

   更加我们前面的原理和上述说明，群蚁算法的2个核心步骤是 路径构建 和 信息素更新。我们将重点对这2个步骤进行说明。

2.3.1 路径构建

   每个蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选 择下一个要到达的城市。随机概率是按照下列公式来进行计算的：

   上述公式就是计算 当前点 到 每一个可能的下一个节点 的概率。分子是 信息素强度 和 能见度 的幂乘积，而分母则是所有 分子的和值。这个刚开始是很不容易理解的，我们在最后实例计算的时候，可以看得很清楚，再反过来理解公式。注意每次选择好节点后，就要从可用节点中移除选择的节点。

2.3.2 信息素更新

   信息素更新是群蚁算法的核心。也是整个算法的核心所在。算法在初始期间有一个固定的浓度值，在每一次迭代完成之后，所有出去的蚂蚁回来后，会对所走过的路线进行计算，然后更新相应的边的信息素浓度。很明显，这个数值肯定是和蚂蚁所走的长度有关系的，经过一次次的迭代， 近距离的线路的浓度会很高，从而得到近似最优解。那我们看看信息素更新的过程。
　　   初始化信息素浓度C(0)，如果太小，算法容易早熟，蚂蚁会很快集中到一条局部最优路径上来，因为可以想想，太小C值，使得和每次挥发和增强的值都差不多，那么 随机情况下，一些小概率的事件发生就会增加非最优路径的信息素浓度；如果C太大，信息素对搜索方向的指导性作用减低，影响算法性能。一般情况下，我们可以使用贪婪算法获取一个路径值Cnn，然后根据蚂蚁个数来计算C(0) = m/Cnn ,m为蚂蚁个数。
　　   每一轮过后，问题空间中的所有路径上的信息素都会发生蒸发,然后，所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素，公式如下：
　　
　　 信息素更新的作用：
     1.信息素挥发(evaporation)信息素痕迹的挥发过程是每个连接上的 信息素痕迹的浓度自动逐渐减弱的过程，这个挥发过程主要用于避 免算法过快地向局部最优区域集中，有助于搜索区域的扩展。
     2.信息素增强(reinforcement)增强过程是蚁群优化算法中可选的部 分，称为离线更新方式（还有在线更新方式）。这种方式可以实现 由单个蚂蚁无法实现的集中行动。基本蚁群算法的离线更新方式是 在蚁群中的m只蚂蚁全部完成n城市的访问后，统一对残留信息进行 更新处理。

2.3.3 迭代与停止

   迭代停止的条件可以选择合适的迭代次数后停止，输出最优路径，也可以看是否满足指定最优条件，找到满足的解后停止。最重要的是，我刚开始理解这个算法的时候，以为每一只蚂蚁走一条边就是一次迭代，其实是错的。这里算法每一次迭代的意义是：每次迭代的m只蚂蚁都完成了自己的路径过程，回到原点后的整个过程。

3 群蚁算法计算实例

  使用PPT中的一个案例，非常直观，对几个符号错误进行了修改，主要是计算概率的乘号，结果没有错误：



  过程总体还是比较简单的，注意理解公式，然后把公式和实例结合起来看，最好是拿笔自己手动画一画，容易理解。下面我们来看看如何编程实现TSP问题的群蚁算法代码。

4 TSP问题的群蚁算法C++代码实现

  原文是C#实现，本文改为C++实现。其中数据集采用的是tsplib上的数据att48 。数据与代码分别如下：

1 6734 1453
2 2233 10
3 5530 1424
4 401 841
5 3082 1644
6 7608 4458
7 7573 3716
8 7265 1268
9 6898 1885
10 1112 2049
11 5468 2606
12 5989 2873
13 4706 2674
14 4612 2035
15 6347 2683
16 6107 669
17 7611 5184
18 7462 3590
19 7732 4723
20 5900 3561
21 4483 3369
22 6101 1110
23 5199 2182
24 1633 2809
25 4307 2322
26 675 1006
27 7555 4819
28 7541 3981
29 3177 756
30 7352 4506
31 7545 2801
32 3245 3305
33 6426 3173
34 4608 1198
35 23 2216
36 7248 3779
37 7762 4595
38 7392 2244
39 3484 2829
40 6271 2135
41 4985 140
42 1916 1569
43 7280 4899
44 7509 3239
45 10 2676
46 6807 2993
47 5185 3258
48 3023 1942

#include<bits/stdc++.h>
#define Read() freopen("data.in","r",stdin)
#define Write() freopen("autocomplete.out","w",stdout)using namespace std;const int City_Num = 48;//城市数目
const int Ant_Num = 20;//蚂蚁数目
const int Total_Num = 2000;//迭代次数double Distance[City_Num+5][City_Num+5];//保存距离
vector<int> Edge[City_Num+5][City_Num+5];//保存每条边有哪些蚂蚁走过
double Ant_length[Ant_Num+5];//保存每只蚂蚁一轮后走过的路径长度
double Edge_Info[City_Num+5][City_Num+5];//保存每条边的信息素
vector<int> Ant[Ant_Num+5];//保存每个蚂蚁的路径
int vis[Ant_Num+5][City_Num+5];//标记每个蚂蚁走过哪个城市
double Total_Length[Ant_Num+5];//记录每轮迭代后每只蚂蚁走的总路长
vector<int> Min_Path;double Alpha = 1.0;
double Beta = 5.0;
double Rho = 0.5;
double Min_Length = 0x3f3f3f3f;struct node
{int x, y;
}Node[City_Num+5];double Get_distance(node a, node b)
{return sqrt((1.0*(a.x-b.x)*(a.x-b.x) + 1.0*(a.y-b.y)*(a.y-b.y))/10.0);
}void Init()
{for(int i = 0; i < City_Num; i++){Distance[i][i] = 0;Edge_Info[i][i] = 0;for(int j = i+1; j < City_Num; j++){Distance[i][j] = Get_distance(Node[i], Node[j]);Distance[j][i] = Distance[i][j];Edge_Info[i][j] = 0.1;Edge_Info[j][i] = 0.1;}}
}int Rand()
{return rand()%48;
}double Rand_Double()
{return (rand()%10000)/10000.0;
}void Build_Path()
{for(int i = 0; i < Ant_Num; i++){while(Ant[i].size() != City_Num){double sum = 0.0;double p_go[City_Num+5];//计算访问下一个城市的概率memset(p_go, 0, sizeof(p_go));int total_pos = Ant[i].size();int now_pos = Ant[i][total_pos-1];for(int j = 0; j < City_Num; j++){if(vis[i][j]) continue;p_go[j] = pow(Edge_Info[now_pos][j], Alpha)*pow((1.0/Distance[now_pos][j]), Beta);sum += p_go[j];}double p = Rand_Double();double p_total = 0;for(int j = 0; j < City_Num; j++){if(vis[i][j]) continue;if(p_total+(p_go[j]/sum) >= p)//下一个访问的城市是j{vis[i][j] = 1;//标记该城市已经走过Ant[i].push_back(j);//把这个城市加到城市列表中Total_Length[i] += Distance[now_pos][j];//计算第i只蚂蚁当前一共走的距离Edge[now_pos][j].push_back(i);//记录走过这条边的蚂蚁，用来更新信息素矩阵break;}else{p_total += (p_go[j]/sum);}}}Total_Length[i] += Distance[Ant[i][City_Num-1]][Ant[i][0]];//将终点到起点的路长加入到总路长中Edge[Ant[i][City_Num-1]][Ant[i][0]].push_back(i);//终点指向起点的路的蚂蚁记录一下if(Min_Length > Total_Length[i])//寻找全局最短路径,并记录路径{Min_Length = Total_Length[i];Min_Path.clear();for(int k = 0; k < City_Num; k++)Min_Path.push_back(Ant[i][k]);Min_Path.push_back(Ant[i][0]);}}
}double Get_Edge_P(int x, int y)
{int n = Edge[x][y].size();double sum = 0.0;for(int i = 0; i < n; i++){int ant = Edge[x][y][i];sum += 1.0/Total_Length[ant];}return sum;
}void Change_Info()
{for(int i = 0; i < City_Num; i++){for(int j = i+1; j < City_Num; j++){double edge_p = Get_Edge_P(i, j);Edge_Info[i][j] = (1.0-Rho)*Edge_Info[i][j] + edge_p;Edge_Info[i][j] = Edge_Info[j][i];}}
}void Print()
{cout<<Min_Length<<endl;for(int i = 0; i < City_Num; i++)cout<<Min_Path[i]<<"-->";cout<<Min_Path[City_Num]<<endl;
}int main()
{srand(time(NULL));Read();for(int i = 0; i < City_Num; i++){int num, x, y;cin >>num>>x>>y;Node[i].x = x;Node[i].y = y;}for(int i = 0; i < 48; i++)cout<<i+1<<" "<<Node[i].x<<" "<<Node[i].y<<endl;cout<<endl<<endl;Init();int T = Total_Num;while(T--){memset(vis, 0, sizeof(vis));for(int i = 0; i < Ant_Num; i++){Ant[i].clear();Total_Length[i] = 0;}for(int i = 0; i < Ant_Num; i++){int start_city = Rand();vis[i][start_city] = 1;Ant[i].push_back(start_city);}Build_Path();//构建路径Change_Info();//信息素更新}Print();//打印最优路径return 0;
}

5 致谢

  再次感谢数据之巅大神的文章，让我对蚁群算法有了清晰的认识，并快速实现。