第四节 蚁群算法

一、导言

蚁群算法（Ant System, AS）是20世纪90年代发展起来的一种模仿蚂蚁群体行为的新的智能化算法。该算法引入正反馈并行机制，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点。目前蚁群算法已经渗透到多个应用领域，从一维静态优化问题到多维动态优化问题，从离散问题到连续问题，蚁群算法都展现出优异的性能和广阔的发展前景，成为国内外学者竞相关注的研究热点和课题。

二、蚁群觅食的特性

在自然界中蚂蚁是如何觅食的呢？为什么蚁群总能找到一条从蚁巢到食物源的最短路径？

蚂蚁会分泌一种叫作信息素（Pheromone）的化学物质，蚂蚁的许多行为受信息素的调控。蚂蚁在运动过程中，能够在其经过的路径上留下信息素，而且能感知这种物质的存在及其浓度，以此指导自己的运动方向。蚂蚁倾向于朝着信息素浓度高的方向移动。图2-3给出了蚁群的觅食过程。

图2-3中的蚁群发现食物源在D点，它们总是会选择最短的直线路径AD来搬运食物，如图2-3（a）所示。如果搬运路线上突然出现障碍物，不管路径长短，蚂蚁按相同的概率选择在图中B点或C点绕过障碍物，如图2-3（b）所示。由于路径ABD的长度小于路径ACD的长度，单位时间内通过路径ABD的蚂蚁数量大于通过路径ACD的蚂蚁数量，则在路径ABD上遗留的信息素浓度比较高，因为蚂蚁倾向于朝着信息素浓度高的方向移动，所以选择路径ABD的蚂蚁随之增多，如图2-3（c）所示。于是，蚁群的集体行为表现出一种信息正反馈现象，即最短路径上走过的蚂蚁越多，则后来的蚂蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流达到寻找食物和蚁穴之间最短路径的目的，如图2-3（d）所示。

三、蚁群算法的基本步骤

（1）初始化参数。时间t=0，循环次数 NC=0，设置最大循环次数，令路径（i, j）的初始化信息量τij（t）=const，初始时刻Δτij（0）=0；

（2）将m只蚂蚁随机放在n个城市上；

（3）循环次数NC←NC+1；

（4）令蚂蚁禁忌表索引号k=1；

（5）k=k+1；

（6）根据状态转移概率

计算蚂蚁选择城市j的概率，j∈{C-tabuk}；

（7）选择具有最大状态转移概率的城市，将蚂蚁移动到该城市，并把该城市记入禁忌表中；

（8）若没有访问完集合C中的所有城市，则k＜m，跳转到（5）；否则，跳转到（9）；

（9）根据式ηij（t）= 1dij、τij（t+n）=（1-ρ）·τij（t）+Δτij（t）以及Δτi j（t）=（t）来更新每条路径上的信息量；

（10）若满足结束条件，循环结束输出计算结果；否则清空禁忌表并跳转到（3）。

四、批量计划问题的蚁群算法

在现有文献中，Pitakaso等人采用蚁群算法求解了具有一般结构的无资源和有资源约束批量计划问题。

（一）编码方式

解的编码方式与其他算法相同，都是采用0—1二进制矩阵方式来表达。

（二）求解过程

在用蚁群算法求解批量计划问题时，需先确定一个物料顺序，之后采用RCWW算法以该物料顺序进行生产计划的安排。

（三）蚁群算法的计算步骤

Step 1：产生初始解集、初始化信息素和各种参数信息；

While终止条件未满足；

Step 2：采用基本蚁群算法构建物料顺序；

Step 3：选择RCWW算法的参数；

Step 4：采用RCWW评价物料顺序。