论文部分内容阅读
摘 要：论述了蚁群算法的原理，通过双桥实验对蚁群算法的模型进行了讨论，分析了蚁群算法的工作机制，与启发式图搜索、蒙特卡罗模拟、神经网络、进化计算和随机学习自动机等算法进行了比较，并对蚁群算法今后的研究方向指出了自己的看法。
关键词：蚁群算法 启发式图搜索 蒙特卡罗 神经网络 进化计算 随机学习自动机
1 引言（Introduction）
20世纪90年代初，意大利学者M.Dorigo等人提出了一种新型的模拟进化算法——蚁群算法（ant colony algorithm， ACA）[1， 2]，该算法首先用于求解著名的解旅行商问题（traveling salesman problem， TSP），实验结果表明蚁群算法具有较强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等。针对该算法的不足，一些学者提出了改进的蚁群算法如蚁群系统 （ant colony system， ACS） [3]、最大-最小蚂蚁系统（max-min ant system， MMAS）[4，5]和基于排序的蚂蚁系统（rank-based version of ant system， ASrank）[6]等。這些改进算法在性能上有了极大的提高，很大程度上消除了搜索中的停滞现象，使蚁群算法更适合求解高维NP-Hard问题。继成功求解TSP问题之后，许多学者利用蚁群算法求解其它组合优化问题[2，7-11]如二次指派问题（quadratic assignment problem， QAP）、车间作业调度问题（job-shop scheduling problem， JSP）、车辆路径问题（vehicle routing problem， VRP）、图着色问题（graph coloring problem， GCP）、通讯网络路由问题（network routing problem， NRP）、背包问题（knapsack problem， KP）、交通分配问题（transportation allocation problem， TAP）、最小生成树（minimum spanning tree， MST）问题、机器人路径规划问题和大规模集成电路（VLSI）设计问题等等。近年来，一些学者提出了蚁群优化元启发式（ant colony optimization meta heuristic， ACO-MH），ACO-MH给蚁群算法提供了一个统一的框架，为蚁群算法的设计工作提供了技术上的保障，并为蚁群算法的理论研究打下了坚实的基础。
2 蚁群算法原理与模型
象蚂蚁这类群居动物，虽然个体的行为极其简单，但由这些简单个体所组成的蚁群却表现出极其复杂的行为特征，能够完成复杂的任务；不仅如此，蚂蚁还能够适应环境的变化，如图1所示，在蚁群运动路线上出现障碍物时，蚂蚁能够很快地重新找到最优路径。蚁群是如何完成这些复杂任务的呢？人们经过大量研究发现，蚂蚁个体之间是通过一种称之为外激素（pheromone）的物质进行信息交流、相互协作来完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁能够感知这种物质的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间正是通过这种信息的交流达到发现最优路径的目的。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名的旅行商问题之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即：通过蚂蚁个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题。（图1）
蚁群觅食行为实际上是一种分布式的协同优化机制。单只蚂蚁虽然能够找到从蚁巢到食物源的路径，但找到最短路径的概率非常小。只有当多只蚂蚁组成蚁群时，其集体行为才突现出蚂蚁的智能——发现最短路径的能力。在寻找最短路径的过程中，蚁群使用了一种间接的通信方式，即通过向所经过的路径上释放一定量的外激素，其它蚂蚁通过感知这种物质的强弱来选择下一步要走的路径。
在蚁群的觅食行为中，另一个重要的方面是自催化机制（正反馈机制）和解的隐式评估。自催化机制和解的隐式评估的组合，极大地提高了问题的求解效率，即对于越短的路径，蚂蚁将会越早走完，从而使更多的蚂蚁将会选择该路径。自催化机制在基于群体的算法中非常有效，如在遗传算法中，通过选择和复制机制来实现。因为它奖励好的个体，可以指导搜索方向。当然在使用自催化机制时，要努力避免早熟现象。在人工蚁群算法中，使用外激素的蒸发和随即状态转移来弥补自催化机制的缺陷。
3 蚁群算法与其它算法的关系
作为一种新型的模拟进化算法，蚁群算法与启发式图搜索、蒙特卡罗算法、神经网络、进化计算和随机学习自动机有许多相似之处，同时也存在着差别。下面是蚁群算法与这些算法的比较。
3.1 启发式图搜索（Heuristic Graph Search， HGS）
在蚁群算法中，每只蚂蚁在问题的解空间中按启发式图进行搜索。蚂蚁按概率决策准则选择下一个要到的节点。其中，概率决策准使用启发式评估函数来指导蚂蚁选择更有希望的节点。
3.2 蒙特卡罗（Mente Carlo， MC）模拟
可以将蚁群算法解释为并行的重复蒙特卡罗系统。蒙特卡罗系统是通用的随机模拟系统，即通过利用随机状态采样和转移准则，对问题进行重复的采样实验。实验所得的结果对问题的统计知识和感兴趣变量的估计值进行更新。反过来，可以重复地使用知识以减少感兴趣变量的不一致性，从而指导模拟过程向感兴趣的状态空间转移。与此相似，在蚁群算法中，蚂蚁利用随机决策机制在问题的解空间中逐步发现问题的可行解。每只蚂蚁自适应地修改问题的局部统计信息（即蚁群留下的外激素），通过stigmergy机制指导蚂蚁沿着有希望的解空间向最优解靠近，从而节约了算法的搜索时间，避免资源的浪费。 3.3 神经网络（Neural Network， NN）
由许多并发、局部交互的单元（人工蚂蚁）组成的蚁群，可以看成是一种“连接”系统。“连接”系统最具代表性的例子是神经网络。从结构上看，蚁群算法与通常的神经网络具有类似的并行机制。蚂蚁访问的每一个状态i对应于神经网络中的神经元i，与问题相关的状态i的邻域结构与神经元i中的突触连接相对应。蚂蚁本身可看成输入信号，并发传播通过神经网络并修改突触与神经元之间的连接强度。信号经过随机转换函数的局部反传，使用的突触越多，两个神经元之间的连接越强。蚁群算法中的学习规则可解释为一种后天性的规则，即质量较好的解包含连接信号的强度高于质量较差的解。
3.4 进化计算（Evolutionary Computation， EC）
蚁群算法与进化计算之间有许多相似之处。首先，两种算法都采用群体表示问题的解；其次，新群体通过包含在群体中与问题相关的知识来生成。两者的主要差异是在进化计算中，所有问题的知识都包含在当前群体中；而在蚁群算法中，代表过去所学的知识保存在信息素的迹中。
与蚁群算法最相似的EC算法是Baluja等人提出的基于群体的增量学习（pupulation based incremental learning， PBIL）算法。在PBIL中维持一个实数向量，该向量与遗传算法中的种群具有相似的作用。从该向量开始，随机生成一个二进制串种群，并按某一概率将种群中的每个二进制串的第i位设置为1，其中的概率值为向量第i位的函数。一旦生成解的群体，将对群体中的解进行评估，评估结果用来增加/减少生成向量的各相应分量对应的概率值，以使将来好（坏）解将能以较高（低）的概率产生。显然，在蚁群算法中，外激素的迹与生成向量具有相同的功能，外激素迹的更新与PBIL中生成向量的更新相对应。蚁群算法与PBIL的主要差别在于PBIL算法中所有概率向量的分量度的计算独立进行，致使PBIL算法只适用于问题中解的每一个元素是相互分离的。
3.5 随机学习自动机（Stochastic Learning Automata， SLA）
SLA是最古老的机器学习方法之一。自动机可定义为一组可能的操作和一个相关的概率向量，一组连续的输入和一个学习算法用来学习输入-输出之间的关系。自动机与一个正反馈的环境相关联，同时还定义了一组环境对行为的惩罚信号。SLA与蚁群算法的相似性为：在蚁群算法中，每条弧/链路上的信息素的迹可看成并发的随机学习过程，蚂蚁扮演環境信号的角色，其中外激素的更新规则相当于自动机的学习规则。两者的主要差别在于蚁群算法中的环境信号是一种随机的、通过概率转移规则的偏差，学习过程沿着搜索空间中最感兴趣的部分进行，即整个环境扮演了一个关键的角色，以此来学习好的解空间。
4 结论（Conclusions）
蚁群算法在各领域的应用说明该算法有着广泛的适应性。但由于该算法出现较晚，对算法的许多特性，如收敛性，参数设定等都来自大量实验统计结果，同时，对算法的理论研究、并行性研究的文献也较少，而并行性正好是提高算法收敛速度的有效途径。现在，蚁群优化思想在启发式方法范畴内已逐渐成为一个独立的分支，在有关国际会议上多次作为专题加以讨论。1998年在比利时布鲁塞尔大学召开了第一届蚁群优化国际研讨会，2000年、2002年仍在原地召开第二、三届会议（Ants’ 2000，Ant’ 2002）。尽管蚁群算法的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景，更多深入细致的工作还有待于进一步展开。
参考文献：
[1]A. Colorni， M. Dorigo， and V. Maniezzo. Distributed optimization by ant colonies[P]. In Proceedings of the First European Conference on Artificial Life， pages 134-142 Elsevier， 1992.
[2]M. Dorigo， V. Maniezzo and A. Colorni. The ant system： Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， Man， and Cybernetics Part B， 26（1）： 29-41， 1996.
[3]M. Dorigo and L.M.Gambardella. Ant Colony System： A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transactions on Evolutionary Computations， 1（1）： 53-66，1997.
[4]T. Stützle and H.H. Hoos. Improvements on the Ant System： Introducing the MAX-MIN Ant System[J]. In R.F. Albrecht G. D. Smith， N.C. Steele， editor， Artificial Neural Networks and Genetic Algorithms， pages 245-249.Springer Verlag，Wien New York， 1998.
[5]T. Stützle and H.H. Hoos. The MAX-MIN Ant System and Local Search for Traveling Salesman Problem[P]. In T. Baeck， Z. Michalewicz， and X. Yao， editors， Proceedings of the IEEE International Conference on Evolutionary Computation （ICEC’97）， pages 309-314，1997. [6]B. Bullnheimer， R.F. Hartl， and C. Strauss. A New Rank Based Version of the Ant System — A Computational Study[J]. Central European Journal for Operations Research and Economics.
[7]L. M. Gambardella， E. D. Taillard， and M. Dorigo. Ant colonies for the QAP[J]. Journal of the Operational Research Society （JORS）， 50 （2）： 167-1176，1999.
[8]A. Colorni， M. Dorigo， V. Maniezzo， and M. Trubian. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research， Statistics and Computer Science （JORBEL）， 34：39-53， 1994.
[9]B. Bullnheimer， R. F. Hartl， and C. Strauss. Applying the ant system to the vehicle routing problem[J]. IN I. H. Osman S. Vo， S. Martello and C. Roucairol， editors， Meta-Heuristics： Advances and Trends in Local Search Paradigms for Optimization， pages 109-120. Kluwer Academics， 1998.
[10]D. Costa and A. Hertz. Ants can color graphs[J]. Journal of the Operational Research Society， 48： 295-305， 1997.
[11]Lu Guoying， Liu Zemin. Qos Multicast Routing Based on Ant Algorithm in Internet[J]， The Journal of China Universities of Posts ant Telecommunication. Vol.7， No. 4， Dec. 2000.
关键词：蚁群算法 启发式图搜索 蒙特卡罗 神经网络 进化计算 随机学习自动机
1 引言（Introduction）
20世纪90年代初，意大利学者M.Dorigo等人提出了一种新型的模拟进化算法——蚁群算法（ant colony algorithm， ACA）[1， 2]，该算法首先用于求解著名的解旅行商问题（traveling salesman problem， TSP），实验结果表明蚁群算法具有较强的鲁棒性和发现较好解的能力，但同时也存在一些缺陷，如收敛速度慢、易出现停滞现象等。针对该算法的不足，一些学者提出了改进的蚁群算法如蚁群系统 （ant colony system， ACS） [3]、最大-最小蚂蚁系统（max-min ant system， MMAS）[4，5]和基于排序的蚂蚁系统（rank-based version of ant system， ASrank）[6]等。這些改进算法在性能上有了极大的提高，很大程度上消除了搜索中的停滞现象，使蚁群算法更适合求解高维NP-Hard问题。继成功求解TSP问题之后，许多学者利用蚁群算法求解其它组合优化问题[2，7-11]如二次指派问题（quadratic assignment problem， QAP）、车间作业调度问题（job-shop scheduling problem， JSP）、车辆路径问题（vehicle routing problem， VRP）、图着色问题（graph coloring problem， GCP）、通讯网络路由问题（network routing problem， NRP）、背包问题（knapsack problem， KP）、交通分配问题（transportation allocation problem， TAP）、最小生成树（minimum spanning tree， MST）问题、机器人路径规划问题和大规模集成电路（VLSI）设计问题等等。近年来，一些学者提出了蚁群优化元启发式（ant colony optimization meta heuristic， ACO-MH），ACO-MH给蚁群算法提供了一个统一的框架，为蚁群算法的设计工作提供了技术上的保障，并为蚁群算法的理论研究打下了坚实的基础。
2 蚁群算法原理与模型
象蚂蚁这类群居动物，虽然个体的行为极其简单，但由这些简单个体所组成的蚁群却表现出极其复杂的行为特征，能够完成复杂的任务；不仅如此，蚂蚁还能够适应环境的变化，如图1所示，在蚁群运动路线上出现障碍物时，蚂蚁能够很快地重新找到最优路径。蚁群是如何完成这些复杂任务的呢？人们经过大量研究发现，蚂蚁个体之间是通过一种称之为外激素（pheromone）的物质进行信息交流、相互协作来完成复杂的任务。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁能够感知这种物质的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着该物质强度高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间正是通过这种信息的交流达到发现最优路径的目的。M.Dorigo等人充分利用了蚁群搜索食物的过程与著名的旅行商问题之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即：通过蚂蚁个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径）来求解TSP问题。（图1）
蚁群觅食行为实际上是一种分布式的协同优化机制。单只蚂蚁虽然能够找到从蚁巢到食物源的路径，但找到最短路径的概率非常小。只有当多只蚂蚁组成蚁群时，其集体行为才突现出蚂蚁的智能——发现最短路径的能力。在寻找最短路径的过程中，蚁群使用了一种间接的通信方式，即通过向所经过的路径上释放一定量的外激素，其它蚂蚁通过感知这种物质的强弱来选择下一步要走的路径。
在蚁群的觅食行为中，另一个重要的方面是自催化机制（正反馈机制）和解的隐式评估。自催化机制和解的隐式评估的组合，极大地提高了问题的求解效率，即对于越短的路径，蚂蚁将会越早走完，从而使更多的蚂蚁将会选择该路径。自催化机制在基于群体的算法中非常有效，如在遗传算法中，通过选择和复制机制来实现。因为它奖励好的个体，可以指导搜索方向。当然在使用自催化机制时，要努力避免早熟现象。在人工蚁群算法中，使用外激素的蒸发和随即状态转移来弥补自催化机制的缺陷。
3 蚁群算法与其它算法的关系
作为一种新型的模拟进化算法，蚁群算法与启发式图搜索、蒙特卡罗算法、神经网络、进化计算和随机学习自动机有许多相似之处，同时也存在着差别。下面是蚁群算法与这些算法的比较。
3.1 启发式图搜索（Heuristic Graph Search， HGS）
在蚁群算法中，每只蚂蚁在问题的解空间中按启发式图进行搜索。蚂蚁按概率决策准则选择下一个要到的节点。其中，概率决策准使用启发式评估函数来指导蚂蚁选择更有希望的节点。
3.2 蒙特卡罗（Mente Carlo， MC）模拟
可以将蚁群算法解释为并行的重复蒙特卡罗系统。蒙特卡罗系统是通用的随机模拟系统，即通过利用随机状态采样和转移准则，对问题进行重复的采样实验。实验所得的结果对问题的统计知识和感兴趣变量的估计值进行更新。反过来，可以重复地使用知识以减少感兴趣变量的不一致性，从而指导模拟过程向感兴趣的状态空间转移。与此相似，在蚁群算法中，蚂蚁利用随机决策机制在问题的解空间中逐步发现问题的可行解。每只蚂蚁自适应地修改问题的局部统计信息（即蚁群留下的外激素），通过stigmergy机制指导蚂蚁沿着有希望的解空间向最优解靠近，从而节约了算法的搜索时间，避免资源的浪费。 3.3 神经网络（Neural Network， NN）
由许多并发、局部交互的单元（人工蚂蚁）组成的蚁群，可以看成是一种“连接”系统。“连接”系统最具代表性的例子是神经网络。从结构上看，蚁群算法与通常的神经网络具有类似的并行机制。蚂蚁访问的每一个状态i对应于神经网络中的神经元i，与问题相关的状态i的邻域结构与神经元i中的突触连接相对应。蚂蚁本身可看成输入信号，并发传播通过神经网络并修改突触与神经元之间的连接强度。信号经过随机转换函数的局部反传，使用的突触越多，两个神经元之间的连接越强。蚁群算法中的学习规则可解释为一种后天性的规则，即质量较好的解包含连接信号的强度高于质量较差的解。
3.4 进化计算（Evolutionary Computation， EC）
蚁群算法与进化计算之间有许多相似之处。首先，两种算法都采用群体表示问题的解；其次，新群体通过包含在群体中与问题相关的知识来生成。两者的主要差异是在进化计算中，所有问题的知识都包含在当前群体中；而在蚁群算法中，代表过去所学的知识保存在信息素的迹中。
与蚁群算法最相似的EC算法是Baluja等人提出的基于群体的增量学习（pupulation based incremental learning， PBIL）算法。在PBIL中维持一个实数向量，该向量与遗传算法中的种群具有相似的作用。从该向量开始，随机生成一个二进制串种群，并按某一概率将种群中的每个二进制串的第i位设置为1，其中的概率值为向量第i位的函数。一旦生成解的群体，将对群体中的解进行评估，评估结果用来增加/减少生成向量的各相应分量对应的概率值，以使将来好（坏）解将能以较高（低）的概率产生。显然，在蚁群算法中，外激素的迹与生成向量具有相同的功能，外激素迹的更新与PBIL中生成向量的更新相对应。蚁群算法与PBIL的主要差别在于PBIL算法中所有概率向量的分量度的计算独立进行，致使PBIL算法只适用于问题中解的每一个元素是相互分离的。
3.5 随机学习自动机（Stochastic Learning Automata， SLA）
SLA是最古老的机器学习方法之一。自动机可定义为一组可能的操作和一个相关的概率向量，一组连续的输入和一个学习算法用来学习输入-输出之间的关系。自动机与一个正反馈的环境相关联，同时还定义了一组环境对行为的惩罚信号。SLA与蚁群算法的相似性为：在蚁群算法中，每条弧/链路上的信息素的迹可看成并发的随机学习过程，蚂蚁扮演環境信号的角色，其中外激素的更新规则相当于自动机的学习规则。两者的主要差别在于蚁群算法中的环境信号是一种随机的、通过概率转移规则的偏差，学习过程沿着搜索空间中最感兴趣的部分进行，即整个环境扮演了一个关键的角色，以此来学习好的解空间。
4 结论（Conclusions）
蚁群算法在各领域的应用说明该算法有着广泛的适应性。但由于该算法出现较晚，对算法的许多特性，如收敛性，参数设定等都来自大量实验统计结果，同时，对算法的理论研究、并行性研究的文献也较少，而并行性正好是提高算法收敛速度的有效途径。现在，蚁群优化思想在启发式方法范畴内已逐渐成为一个独立的分支，在有关国际会议上多次作为专题加以讨论。1998年在比利时布鲁塞尔大学召开了第一届蚁群优化国际研讨会，2000年、2002年仍在原地召开第二、三届会议（Ants’ 2000，Ant’ 2002）。尽管蚁群算法的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景，更多深入细致的工作还有待于进一步展开。
参考文献：
[1]A. Colorni， M. Dorigo， and V. Maniezzo. Distributed optimization by ant colonies[P]. In Proceedings of the First European Conference on Artificial Life， pages 134-142 Elsevier， 1992.
[2]M. Dorigo， V. Maniezzo and A. Colorni. The ant system： Optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems， Man， and Cybernetics Part B， 26（1）： 29-41， 1996.
[3]M. Dorigo and L.M.Gambardella. Ant Colony System： A Cooperative Learning Approach to the Traveling Salesman Problem[J]. IEEE Transactions on Evolutionary Computations， 1（1）： 53-66，1997.
[4]T. Stützle and H.H. Hoos. Improvements on the Ant System： Introducing the MAX-MIN Ant System[J]. In R.F. Albrecht G. D. Smith， N.C. Steele， editor， Artificial Neural Networks and Genetic Algorithms， pages 245-249.Springer Verlag，Wien New York， 1998.
[5]T. Stützle and H.H. Hoos. The MAX-MIN Ant System and Local Search for Traveling Salesman Problem[P]. In T. Baeck， Z. Michalewicz， and X. Yao， editors， Proceedings of the IEEE International Conference on Evolutionary Computation （ICEC’97）， pages 309-314，1997. [6]B. Bullnheimer， R.F. Hartl， and C. Strauss. A New Rank Based Version of the Ant System — A Computational Study[J]. Central European Journal for Operations Research and Economics.
[7]L. M. Gambardella， E. D. Taillard， and M. Dorigo. Ant colonies for the QAP[J]. Journal of the Operational Research Society （JORS）， 50 （2）： 167-1176，1999.
[8]A. Colorni， M. Dorigo， V. Maniezzo， and M. Trubian. Ant system for job-shop scheduling[J]. Belgian Journal of Operations Research， Statistics and Computer Science （JORBEL）， 34：39-53， 1994.
[9]B. Bullnheimer， R. F. Hartl， and C. Strauss. Applying the ant system to the vehicle routing problem[J]. IN I. H. Osman S. Vo， S. Martello and C. Roucairol， editors， Meta-Heuristics： Advances and Trends in Local Search Paradigms for Optimization， pages 109-120. Kluwer Academics， 1998.
[10]D. Costa and A. Hertz. Ants can color graphs[J]. Journal of the Operational Research Society， 48： 295-305， 1997.
[11]Lu Guoying， Liu Zemin. Qos Multicast Routing Based on Ant Algorithm in Internet[J]， The Journal of China Universities of Posts ant Telecommunication. Vol.7， No. 4， Dec. 2000.