Simulated annealing versus metropolis for a TSP instance

被引：47

作者：

Meer, Klaus ^{[1
]}

机构：

[1] Syddansk Univ Odense, Dept Math & Comp Sci, DK-5230 Odense M, Denmark

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 104卷 / 06期

关键词：

analysis of algorithms; simulated annealing; metropolis algorithm; 2-Opt heuristic for TSP;

D O I：

10.1016/j.ipl.2007.06.016

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In a recent paper [I. Wegener, Simulated Annealing beats Metropolis in combinatorial optimization, in: L. Caires, G.F. Italiano, L. Monteiro, C. Palamidessi, M. Yung (Eds.), Proc. ICALP 2005, in: LNCS, vol. 3580, 2005, pp. 589-601] Wegener gave a first natural example of a combinatorial optimization problem where for certain instances a Simulated Annealing algorithm provably performs better than the Metropolis algorithm for any fixed temperature. Wegener's example deals with a special instance of the Minimum Spanning Tree problem. In this short note we show that Wegener's technique as well can be used to prove a similar result for another important problem in combinatorial optimization, namely the Traveling Salesman Problem. The main task is to construct a suitable TSP instance for which SA outperforms MA when using the well known 2-Opt local search heuristic. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：216 / 219

页数：4