群体智能优化算法之蚁群优化算法(ACO)

5.4.2 蚁量系统模型

该模型中，一只蚂蚁经过路径（i，j）上释放的信息素量为常数Q/d_ij，即

5.5 改进的蚁群优化算法

5.5.1 带精英策略的蚂蚁系统

带精英策略的蚂蚁系统（Ant System with elitist strategy，ASelite），为了使当前的最优解在下一循环中对蚂蚁更有吸引力，在每次循环后给予最优解以额外的信息素，这个最优解就是全局最优解，找到该解的蚂蚁为精英蚂蚁，信息素更新公式如下：

5.5.3 蚁群系统

蚁群系统（Ant Colony System，ACS）[7]是由Dorigo和Gambardella在1996年提出的，用于改善蚂蚁系统的性能。蚁群系统在蚂蚁系统的基础上主要做了三个方面的改进：
（1）状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法。

蚁群系统使用双重决策：既可以利用关于问题的先验知识和以信息素形式存储的已经获得信息，又可以进行有向性的探索。通过调节参数q0，可以调节探索新路径的程度和是否使蚂蚁的搜索活动集中于最优解的空间邻域内。

（2）全局更新规则只应用于最优的蚂蚁路径上

在蚁群系统中，每次循环后只对最优蚂蚁经历的路径进行信息素的增强，其他路径由于挥发机制信息素会逐渐减少，这就增大了最优路径和最差路径在信息素上的差异，使得蚂蚁更倾向于选择最优路径中的边，从而使得其搜索行为能够很快地集中造最优路径附近，提高了算法的搜索效率。

（3）建立问题解决方案的过程中，应用局部信息素更新规则

蚂蚁在构造路径的同时进行局部更新，类似于蚁密和蚁量模型中的局部更新，而在每次循环后再对路径进行一次全局的更新。

5.5.3.1 蚁群系统状态转移规则

蚁群系统在构造候选解时使用了伪随机比例规则，位于节点i的蚂蚁通过下式确定选择下一个城市j的概率：

5.5.3.3 蚁群系统局部更新规则

若一条路径的信息素轨迹明显高于其他路径，停滞现象就会发生，因为在这种情况下蚂蚁更倾向于选择该路径，正反馈机制使得该路径的信息素进一步增强，从而蚂蚁将重复地建立同一个解，对搜索空间的探索停止。因此最大-最小蚂蚁系统对信息素轨迹的最大值和最小值分别施加了τ_min和τ_max限制，从而有

参考文献

1. Dorigo, M., Optimization, Learning and Natural Algorithms (in Italian), in Dipartimento di Elettronica e Informazione. 1992, Politecnico di Milano: Milan, Italy.
2. H. Papadimitriou, C. and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Vol. 32. 1982.
3. Deneubourg, J.-L., et al., The dynamics of collective sorting robot-like ants and ant-like robots. 1990. 356-363.
4. Deneubourg, J.L., et al., The self-organizing exploratory pattern of the argentine ant. Journal of Insect Behavior, 1990. 3(2): p. 159-168.
5. López-Ibá?ez, M., T. Stützle, and M. Dorigo, Ant Colony Optimization: A Component-Wise Overview, in Handbook of Heuristics, R. Martí, P. Panos, and M.G.C. Resende, Editors. 2016, Springer International Publishing: Cham. p. 1-37.
6. Dorigo, M., V. Maniezzo, and A. Colorni, Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996. 26(1): p. 29-41.
7. Dorigo, M. and L.M. Gambardella, Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1997. 1(1): p. 53-66.
8. Stutzle, T. and H. Hoos. MAX-MIN Ant System and local search for the traveling salesman problem. in Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC ’97). 1997.
9. Dorigo, M., M. Birattari, and T. Stützle, Ant Colony Optimization: Artificial Ants as a Computational Intelligence Technique. IEEE Computational Intelligence Magazine, 2006. 1: p. 28-39.

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览34471 人正在系统学习中