MAX-MIN Ant System

被引:1780
作者
Stützle, T
Hoos, HH
机构
[1] Free Univ Brussels, IRIDIA, B-1050 Brussels, Belgium
[2] Univ British Columbia, Dept Comp Sci, Vancouver, BC V6T 1Z4, Canada
来源
FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE | 2000年 / 16卷 / 08期
关键词
Ant Colony Optimization; search space analysis; traveling salesman problem; quadratic assignment problem; combinatorial optimization;
D O I
10.1016/S0167-739X(00)00043-1
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Ant System, the first Ant Colony Optimization algorithm, showed to be a viable method for attacking hard combinatorial optimization problems. Yet, its performance, when compared to more fine-tuned algorithms, was rather poor for large instances of traditional benchmark problems like the Traveling Salesman Problem. To show that Ant Colony Optimization algorithms could be good alternatives to existing algorithms for hard combinatorial optimization problems, recent research in this area has mainly focused on the development of algorithmic variants which achieve better performance than Ant System. In this paper, we present MAX-MIN Ant System (MMAS), an Ant Colony Optimization algorithm derived from Ant System. MMAS differs from Ant System in several important aspects, whose usefulness we demonstrate by means of an experimental study. Additionally, we relate one of the characteristics specific to MMAS - that of using a greedier search than Ant System - to results from the search space analysis of the combinatorial optimization problems attacked in this paper. Our computational results on the Traveling Salesman Problem and the Quadratic Assignment Problem show that MMAS is currently among the best performing algorithms for these problems. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:889 / 914
页数:26
相关论文
共 48 条
  • [1] [Anonymous], P 7 INT C GEN ALG
  • [2] [Anonymous], 1991, ANT SYSTEM AUTOCATAL
  • [3] [Anonymous], DIMACS SERIES DISCRE
  • [4] [Anonymous], 1992, OPTIMIZATION LEARNIN
  • [5] Bentley J. L., 1992, ORSA Journal on Computing, V4, P387, DOI 10.1287/ijoc.4.4.387
  • [6] Results of the first international contest on evolutionary optimisation (1st ICEO)
    Bersini, H
    Dorigo, M
    Langerman, S
    Seront, G
    Gambardella, L
    [J]. 1996 IEEE INTERNATIONAL CONFERENCE ON EVOLUTIONARY COMPUTATION (ICEC '96), PROCEEDINGS OF, 1996, : 611 - 615
  • [7] Boese K. D., 1996, THESIS U CALIFORNIA
  • [8] A NEW ADAPTIVE MULTI-START TECHNIQUE FOR COMBINATORIAL GLOBAL OPTIMIZATIONS
    BOESE, KD
    KAHNG, AB
    MUDDU, S
    [J]. OPERATIONS RESEARCH LETTERS, 1994, 16 (02) : 101 - 113
  • [9] An improved ant system algorithm for the vehicle routing problem
    Bullnheimer, B
    Hartl, RF
    Strauss, C
    [J]. ANNALS OF OPERATIONS RESEARCH, 1999, 89 (0) : 319 - 328
  • [10] Bullnheimer B., 1999, CENTRAL EUROPEAN J O, V7, P25