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 条
  • [31] Solving Travelling Salesman Problem by Using Optimization Algorithms
    Saud, Suhair
    Kodaz, Halife
    Babaoglu, Ismail
    9TH INTERNATIONAL CONFERENCE ON ADVANCES IN INFORMATION TECHNOLOGY (IAIT-2017), 2018, : 17 - 32
  • [32] A class of exponential neighbourhoods for the quadratic travelling salesman problem
    Brad D. Woods
    Abraham P. Punnen
    Journal of Combinatorial Optimization, 2020, 40 : 303 - 332
  • [33] A Biologically Inspired Solution for Fuzzy Travelling Salesman Problem
    Pezhhan, Elham
    Mansoori, Eghbal
    ARTIFICIAL INTELLIGENCE AND SIGNAL PROCESSING, AISP 2013, 2014, 427 : 277 - 287
  • [34] Chaotic ant swarm for the traveling salesman problem
    Wei, Zhen
    Ge, Fangzhen
    Lu, Yang
    Li, Lixiang
    Yang, Yixian
    NONLINEAR DYNAMICS, 2011, 65 (03) : 271 - 281
  • [35] The Maximum Travelling Salesman Problem on symmetric Demidenko matrices
    Deineko, VG
    Woeginger, GJ
    DISCRETE APPLIED MATHEMATICS, 2000, 99 (1-3) : 413 - 425
  • [36] Multistage extremal optimization for hard travelling salesman problem
    Zeng, Guo-Qiang
    Lu, Yong-Zai
    Mao, Wei-Jie
    PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS, 2010, 389 (21) : 5037 - 5044
  • [37] COMPLEXITY INDICES FOR THE TRAVELLING SALESMAN PROBLEM AND DATA MINING
    Cvetkovic, Dragos
    TRANSACTIONS ON COMBINATORICS, 2012, 1 (01) : 35 - 43
  • [38] POLYNOMIAL RANDOMIZED ALGORITHM FOR THE ASYMMETRIC TRAVELLING SALESMAN PROBLEM
    Barketau, Maksim S.
    DOKLADY NATSIONALNOI AKADEMII NAUK BELARUSI, 2022, 66 (05): : 489 - 494
  • [39] A class of exponential neighbourhoods for the quadratic travelling salesman problem
    Woods, Brad D.
    Punnen, Abraham P.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (02) : 303 - 332
  • [40] GLS Optimization Algorithm for Solving Travelling Salesman Problem
    Neissi, Nourolhoda Alemi
    Mazloom, Masoud
    SECOND INTERNATIONAL CONFERENCE ON COMPUTER AND ELECTRICAL ENGINEERING, VOL 1, PROCEEDINGS, 2009, : 291 - +
12345