Ant system: optimization by a colony of cooperating agents Export

@article{citeulike:1857277, abstract = {An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). 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 the job-shop scheduling. Finally we discuss the salient characteristics-global data structure revision, distributed communication and probabilistic transitions of the AS}, author = {Dorigo, M. and Maniezzo, V. and Colorni, A.}, booktitle = {Systems, Man and Cybernetics, Part B, IEEE Transactions on}, citeulike-article-id = {1857277}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/3477.484436}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=484436}, day = {06}, doi = {10.1109/3477.484436}, journal = {Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on}, keywords = {1996, ant-system, ant\_colonies, metaheuristics, optimization}, month = {August}, number = {1}, pages = {29--41}, posted-at = {2009-10-20 17:02:39}, priority = {2}, title = {Ant system: optimization by a colony of cooperating agents}, url = {http://dx.doi.org/10.1109/3477.484436}, volume = {26}, year = {2002} }

TY - JOUR ID - citeulike:1857277 L3 - citeulike-article-id:1857277 N2 - An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). 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 the job-shop scheduling. Finally we discuss the salient characteristics-global data structure revision, distributed communication and probabilistic transitions of the AS IS - 1 JF - Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on EP - 41 TI - Ant system: optimization by a colony of cooperating agents VL - 26 T2 - Systems, Man and Cybernetics, Part B, IEEE Transactions on SP - 29 KW - 1996 KW - ant-system KW - ant_colonies KW - metaheuristics KW - optimization AU - Dorigo, M AU - Maniezzo, V AU - Colorni, A PY - 2002/08/06/ UR - http://dx.doi.org/10.1109/3477.484436 ER -