A PARALLEL SIMULATED ANNEALING ALGORITHM

被引：16

作者：

BOISSIN, N

LUTTON, JL

机构：

[1] France Telecom, Centre National d'Etudes des Télécommunications, PAA, 92131 Issy Les Moulineaux, 38, rue du General Leclerc

来源：

PARALLEL COMPUTING | 1993年 / 19卷 / 08期

关键词：

COMBINATORIAL OPTIMIZATION; SIMULATED ANNEALING; PARALLEL IMPLEMENTATIONS;

D O I：

10.1016/0167-8191(93)90070-2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we present a generalization of the sequential simulated annealing algorithm for combinatorial optimization problems. By performing a parallel study of the current solution neighbourhood we obtain an algorithm that can be very efficiently implemented on a massively parallel computer. We test the convergence and the quality of our algorithm by comparing it to the sequential algorithm for two classical problems: the minimization of an unconstrained 0-1 quadratic function and the quadratic sum assignment problem.

引用

页码：859 / 872

页数：14

共 17 条

[1]

Aarts E., 1989, SIMULATED ANNEALING

[2] PARALLEL IMPLEMENTATIONS OF THE STATISTICAL COOLING ALGORITHM [J].

AARTS, EHL ;

DEBONT, FMJ ;

HABERS, EHA ;

VANLAARHOVEN, PJM .

INTEGRATION-THE VLSI JOURNAL, 1986, 4 (03) :209-238

[3]

[Anonymous], 1979, MONTE CARLO METHODS

[4] THE N-CITY TRAVELING SALESMAN PROBLEM - STATISTICAL-MECHANICS AND THE METROPOLIS ALGORITHM [J].

BONOMI, E ;

LUTTON, JL .

SIAM REVIEW, 1984, 26 (04) :551-568

[5] THE ASYMPTOTIC-BEHAVIOR OF QUADRATIC SUM ASSIGNMENT PROBLEMS - A STATISTICAL-MECHANICS APPROACH [J].

BONOMI, E ;

LUTTON, JL .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1986, 26 (02) :295-300

[6] PARALLEL ALGORITHMS FOR CHIP PLACEMENT BY SIMULATED ANNEALING [J].

DAREMA, F ;

KIRKPATRICK, S ;

NORTON, VA .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1987, 31 (03) :391-402

[7] STOCHASTIC RELAXATION, GIBBS DISTRIBUTIONS, AND THE BAYESIAN RESTORATION OF IMAGES [J].

GEMAN, S ;

GEMAN, D .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1984, 6 (06) :721-741

[8] TIME-DEPENDENT STATISTICS OF ISING MODEL [J].

GLAUBER, RJ .

JOURNAL OF MATHEMATICAL PHYSICS, 1963, 4 (02) :294-&

[9] COOLING SCHEDULES FOR OPTIMAL ANNEALING [J].

HAJEK, B .

MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (02) :311-329

[10]

KIRKPATRICK S, 1982, RC9335 IBM TJ WATS C

← 1 2 →