The Ant System: Optimization by a colony of cooperating agents
The Ant System: Optimization by a colony of cooperating agents
复制标题
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
M. Dorigo;V. Maniezzo;A. Colorni
中科院分区：
文献类型：
--
作者：
M. Dorigo;V. Maniezzo;A. Colorni
与蚁群功能的方式进行类比，提出了一种新的计算范式的定义，我们称之为蚂蚁系统。我们提出它作为一个可行的新方法，随机组合优化。该模型的主要特点是正反馈、分布式计算和构造性贪婪启发式的使用。正反馈可快速发现好的解，分布式计算可避免过早收敛，贪婪启发式可帮助在搜索过程的早期阶段找到可接受的解。我们将所提出的方法应用于经典的旅行商问题（TSP），并报告模拟结果。讨论了模型的参数选择和模型的初始设置，并与禁忌搜索和模拟退火算法进行了比较。为了证明该方法的鲁棒性，我们展示了如何蚂蚁系统（AS）可以应用到其他优化问题，如非对称旅行商，二次分配和车间作业调度。最后，我们讨论了AS的显著特点-全局数据结构修改，分布式通信和概率转换。
An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call Ant System . We propose it as a viable new approach to stochastic combinatorial optimization. The main characteristics of this model are positive feedback, distributed computation, and the use of a constructive greedy heuristic. Positive feedback accounts for rapid discovery of good solutions, distributed computation avoids premature convergence, and the greedy heuristic helps find acceptable solutions in the early stages of the search process. We apply the proposed methodology to the classical Traveling Salesman Problem (TSP), and report simulation results. We also discuss parameter selection and the early setups of the model, and compare it with tabu search and simulated annealing using TSP. To demonstrate the robustness of the approach, we show how the Ant System (AS) can be applied to other optimization problems like the asymmetric traveling salesman, the quadratic assignment and job-shop scheduling. Finally we discuss the salient characteristics – global data structure revision, distributed communication and probabilistic transitions of the AS.