第2章 蚁群优化方法概述
2.1 蚁群算法的思想起源
蚂蚁作为一种社会昆虫，其食物搜索行为具有非常高的协作性。研究发现，当蚂蚁在蚁穴和食物源之间行走时，会释放一种称为信息素的物质，这些物质形成一条指示轨迹。由于蚂蚁在较长路径上行走时需要更多的时间，而信息素是随着时间挥发的，因此较短路径上的信息素强度（intensity）高于较长路径上的强度。蚂蚁可以感知到环境中这种物质的存在及其强度，并在移动时，倾向于选择信息素强度高的轨迹。最终它会从初始的随机路径搜索，逐步稳定到最短路径上来。蚂蚁对环境中的刺激物作出反应，并产生新的刺激物，这些刺激物既作用于自己，也对群体中的其他个体产生影响。这种间接的通信方式形成了一种行为协作方式。它具有两个突出特点：一是通信个体通过释放信息素修正其对所处环境的物理状态；二是信息素只能被访问该局部状态的通信个体感应到。这种以环境状态的物理修正为媒介，而且只能被局部接收的通信方式称为Stigmergy。
1989年，Gross等[1]利用一群蚂蚁做了如下实验：在蚁穴与食物源之间架设二分支桥。每次移动时，蚂蚁只能选择两个分支之一往返于蚁穴与食物源。实验观察发现，在很短时间内，大多数蚂蚁将会选择路径较短的桥，并且蚁群选择短分支的概率随着两个分支之间的长度比例增加而增大。
随后，Dorigo等[2]做了如图2-1所示的经典实验。图中A是蚁穴，E是食物源，HC为一障碍物。蚂蚁在没有障碍的时候，可以通过如图2-1（a）所示路径到达食物源。但是由于障碍的存在，蚂蚁只能经H或C由A到达E（图2-1（b）），其路径选择受先前经过的蚂蚁留下的信息素强度的影响。右边的路径短，蚂蚁在其上留下的信息素强度高，该路径被其他蚂蚁选择的概率就高。随着信息素的积累，蚂蚁趋向于选择右边的路径（图2-1（c））。
图2-1 蚂蚁觅食躲避障碍示意图
Dorigo等将真实蚂蚁的行为模型化，用加权弧段表示实际的路径，其中权值如图2-2（a）所示。设t=0时刻有30只蚂蚁由A到达B，另有30只蚂蚁由E到达D，蚂蚁每次经过后留下的信息素强度为1。为方便起见，设该物质经过一个时间单位后完全挥发。在初始时刻，由于路径BH、BC、DH、DC上均无信息素存在，位于B和D的蚂蚁随机地选择路径。从统计的角度可以认为它们以相同的概率选择BH、BC、DH、DC（图2-2（b））。经过一个时间单位后，在路径BCD上的信息素量是路径BHD上信息素量的两倍。在t=1时刻，将有20只蚂蚁由B和D到达C，有10只蚂蚁由B和D到达H（图2-2（c））。随着时间的推移，蚂蚁会以越来越大的概率选择路径BCD，最终完全选择路径BCD，从而找到由蚁穴到食物源的最短路径。
图2-2 模型化距离
受真实蚂蚁觅食行为的启发，Dorigo等开创性地提出了蚁群算法，其基本思想是利用一群人工蚂蚁模拟真实蚂蚁的觅食行为求解问题。人工蚂蚁和真实蚂蚁既有联系又有区别[3]，通过比较两者的特点，有助于了解蚁群算法的工作机理，对蚁群算法的研究也有一定的指导意义。
人工蚂蚁绝大部分行为特征来源于真实蚂蚁，它们的共同特征主要有以下5点。
1）人工蚂蚁和真实蚂蚁都是一群相互合作的个体
它们可以通过全局范围内相互合作找出问题较好的解。虽然每只人工蚂蚁构造可行解的行为往往比较复杂，但是高质量的解也是整个蚁群合作的结果。
2）人工蚂蚁和真实蚂蚁都通过信息素进行间接通信
真实蚂蚁在经过的路径上留下信息素，而人工蚂蚁改变其经过路径上存储的数字信息，该信息记录了蚂蚁当前解和历史解的性能状态，而且可以被以后经过该路径的蚂蚁读写。蚁群通过这种方式改变了当前人工蚂蚁所经过的路径周围的环境，同时也改变了整个蚁群所存储的历史信息。另外，蚁群算法中还有一个信息素挥发机制，它模拟真实信息素挥发，逐渐改变信息素。挥发机制使得人工蚂蚁和真实蚂蚁一样可以逐渐忘记历史遗留信息，从而使人工蚂蚁在进行路径选择时不局限于先前蚂蚁所留下的经验。
3）人工蚂蚁和真实蚂蚁都利用了正反馈机制
人工蚂蚁受真实蚂蚁觅食行为的启发，利用了正反馈机制（自催化机制）和解的隐性评价（implicit solution evaluation）[3]。解的隐性评价意味着路径越短可以越快地被人工蚂蚁经过，从而较短的路径可以接收更多的信息素。而正反馈意味着路径越短则信息素越多，从而被更多的蚂蚁选取的可能性越大。如果合理利用，正反馈可以成为基于群体的优化算法的一个有效机制。但是，在应用正反馈时应避免早熟收敛。
4）人工蚂蚁和真实蚂蚁都有一个共同的任务，并且只能局部移动
人工蚂蚁与真实蚂蚁有共同的任务，即寻找连接起点（蚁穴）到终点（食物源）的最短（最小代价）路径。真实蚂蚁不能跳跃，它们只能在相邻区域内行走；而人工蚂蚁也只能一步步地沿着问题的相邻状态移动。
5）人工蚂蚁和真实蚂蚁都采用随机的、近视的（myopic）状态转移策略
与真实蚂蚁类似，人工蚂蚁在构造解时按照一种随机决策策略在相邻状态间移动，而且它们只是利用了局部信息而没有利用前瞻性预测未来状态。因此，它们所采用的策略在时间和空间上都是局部的。这个策略既与问题特有先验信息有关，又与由蚂蚁引起的环境局部改变有关。
人工蚂蚁还具有真实蚂蚁所不具备的行为特征，主要有以下几点：
（1）人工蚂蚁生活在一个离散空间中，它们的移动是由一个离散状态到另一个离散状态的跃迁；而真实蚂蚁是在一个连续的空间爬行。
（2）人工蚂蚁具有一定的记忆能力，它能保存蚂蚁过去的状态。而真实蚂蚁没有表现出这方面的能力。
（3）人工蚂蚁释放信息素的时机可以依据具体问题而定，而真实蚂蚁是在移动的同时释放信息素。
（4）为了提高系统的优化性能，人工蚂蚁可以增加一些额外的本领，如预测能力、局部优化、回退等。而这些本领是真实蚂蚁所不具备的。
总之，蚁群算法是真实蚁群觅食行为的一种抽象。同时，为了能有效解决实际优化问题，它赋予了人工蚂蚁一些真实蚂蚁所不具备的本领。