Ant colonies for the travelling salesman problem

被引：1471
|
作者：
Dorigo, M [1 ]
Gambardella, LM [1 ]
机构：
[1] IDSIA, CH-6900 LUGANO, SWITZERLAND
来源：
BIOSYSTEMS | 1997年 / 43卷 / 02期
关键词：
ant colony optimization; computational intelligence; artificial life; adaptive behavior; combinatorial optimization; reinforcement learning;
D O I：
10.1016/S0303-2647(97)01708-5
中图分类号：
Q [生物科学];
学科分类号：
07 ; 0710 ; 09 ;
摘要：
We describe an artificial ant colony capable of solving the travelling salesman problem (TSP). Ants of the artificial colony are able to generate successively shorter feasible tours by using information accumulated in the form of a pheromone trail deposited on the edges of the TSP graph. Computer simulations demonstrate that the artificial ant colony is capable of generating good solutions to both symmetric and asymmetric instances of the TSP. The method is an example, like simulated annealing, neural networks and evolutionary computation, of the successful use of a natural metaphor to design an optimization algorithm. (C) 1997 Elsevier Science Ireland Ltd.
引用
收藏
页码：73 / 81
页数：9
相关论文
共 50 条
  • [1] An Ant Colony System Solving the Travelling Salesman Region Problem
    Lammel, Benjamin
    Gryzlak, Karin
    Dornberger, Rolf
    Hanne, Thomas
    2016 4TH INTERNATIONAL SYMPOSIUM ON COMPUTATIONAL AND BUSINESS INTELLIGENCE (ISCBI), 2016, : 125 - 131
  • [2] Experimental analysis of ant system on travelling salesman problem dataset TSPLIB
    Thirugnanasambandam K.
    Raghav R.S.
    Saravanan D.
    Prabu U.
    Rajeswari M.
    EAI Endorsed Transactions on Pervasive Health and Technology, 2019, 5 (19):
  • [3] A memetic ant colony optimization algorithm for the dynamic travelling salesman problem
    Michalis Mavrovouniotis
    Shengxiang Yang
    Soft Computing, 2011, 15 : 1405 - 1425
  • [4] New Heuristic Function in Ant Colony System for the Travelling Salesman Problem
    Alobaedy, Mustafa Muwafak
    Ku-Mahamud, Ku Ruhana
    2012 7TH INTERNATIONAL CONFERENCE ON COMPUTING AND CONVERGENCE TECHNOLOGY (ICCCT2012), 2012, : 965 - 969
  • [5] A memetic ant colony optimization algorithm for the dynamic travelling salesman problem
    Mavrovouniotis, Michalis
    Yang, Shengxiang
    SOFT COMPUTING, 2011, 15 (07) : 1405 - 1425
  • [6] Modified Ant Colony Optimization with Pheromone Mutation for Travelling Salesman Problem
    Ratanavilisagul, Chiabwoot
    2017 14TH INTERNATIONAL CONFERENCE ON ELECTRICAL ENGINEERING/ELECTRONICS, COMPUTER, TELECOMMUNICATIONS AND INFORMATION TECHNOLOGY (ECTI-CON), 2017, : 411 - 414
  • [7] Variation of Ant Colony Optimization Parameters for Solving the Travelling Salesman Problem
    Cheong, Pui Yue
    Aggarwal, Deepa
    Hanne, Thomas
    Dornberger, Rolf
    2017 IEEE 4TH INTERNATIONAL CONFERENCE ON SOFT COMPUTING & MACHINE INTELLIGENCE (ISCMI), 2017, : 60 - 65
  • [8] Frequency Graphs for Travelling Salesman Problem Based on Ant Colony Optimization
    Wang, Yong
    Wu, Yiwen
    INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE AND APPLICATIONS, 2019, 18 (03)
  • [9] Ant Colony Optimization for Time-Dependent Travelling Salesman Problem
    Tomanova, Petra
    Holy, Vladimir
    2020 4TH INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS, METAHEURISTICS & SWARM INTELLIGENCE (ISMSI 2020), 2020, : 47 - 51
  • [10] Deep Intelligent Ant Colony Optimization for Solving Travelling Salesman Problem
    Wang Y.
    Chen M.
    Xing L.
    Wu Y.
    Ma W.
    Zhao H.
    1600, Science Press (58): : 1586 - 1598
12345