Design and analysis of stochastic local search for the multiobjective traveling salesman problem

被引:39
作者
Paquete, Luis [1 ]
Stutzle, Thomas [2 ]
机构
[1] Univ Coimbra, Dept Informat Engn, CISUC, Coimbra, Portugal
[2] Univ Libre Bruxelles, CoDE, IRIDIA, Brussels, Belgium
关键词
Multiobjective combinatorial optimization; Meta-heuristics; PERFORMANCE ASSESSMENT; ALGORITHM; OPTIMIZERS;
D O I
10.1016/j.cor.2008.11.013
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Stochastic local search (SLS) algorithms are typically composed of a number of different components, each of which should contribute significantly to the final algorithm's performance. If the goal is to design and engineer effective SLS algorithms, the algorithm developer requires some insight into the importance and the behavior of possible algorithmic components. In this paper, we analyze algorithmic components of SLS algorithms for the multiobjective travelling salesman problem. The analysis is done using a careful experimental design for a generic class of SLS algorithms for multiobjective combinatorial optimization. Based on the insights gained, we engineer SLS algorithms for this problem. Experimental results show that these SLS algorithms, despite their conceptual simplicity, outperform a well-known memetic algorithm for a range of benchmark instances with two and three objectives. (C) 2008 Elsevier Ltd. All rights reserved.
引用
收藏
页码:2619 / 2631
页数:13
相关论文
共 51 条
  • [1] ak P. Czyzz., 1998, J. Multi-Criteria Dec., V7, P34, DOI [DOI 10.1002/(SICI)1099-1360(199801)7:13.0.CO
  • [2] 2-6, 10.1002/(sici)1099-1360(199801)7:1, DOI 10.1002/(SICI)1099-1360(199801)7:1]
  • [3] Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
    Angel, E
    Bampis, E
    Gourvés, L
    [J]. THEORETICAL COMPUTER SCIENCE, 2004, 310 (1-3) : 135 - 146
  • [4] [Anonymous], 1994, Lecture notes in computer science
  • [5] [Anonymous], 1986, Multiple criteria optimization: Theory, computation, and application
  • [6] [Anonymous], 2006, J. Math. Model. Algorithms
  • [7] [Anonymous], THESIS TU DARMSTADT
  • [8] Applegate David L, 2006, TRAVELING SALESMAN P
  • [9] Bentley J. L., 1992, ORSA Journal on Computing, V4, P387, DOI 10.1287/ijoc.4.4.387
  • [10] CHESS-Changing horizon efficient set search: A simple principle for multiobjective optimization
    Borges, PC
    [J]. JOURNAL OF HEURISTICS, 2000, 6 (03) : 405 - 418