SCALING FEATURES IN COMPLEX OPTIMIZATION PROBLEMS

被引：8

作者：

TAFELMAYER, R

HOFFMANN, KH

机构：

[1] Bereich Physik, Technische Universität Chemnitz-Zwickau

来源：

COMPUTER PHYSICS COMMUNICATIONS | 1995年 / 86卷 / 1-2期

关键词：

D O I：

10.1016/0010-4655(95)00004-Y

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We study the scaling behavior in the ensemble approach of simulated annealing and threshold accepting considering two examples of complex optimization problems, namely Grotschel's traveling salesman problem and a spin glass problem with Gaussian distributions of the couplings. If scaling is present it should allow for an estimation of the ground state energy. Our numerical results show a different qualitative behavior for the two kinds of problems. Whereas scaling is present in the spin glass problem it is widely absent in the traveling salesman problem.

引用

页码：81 / 90

页数：10

共 15 条

[1] THRESHOLD ACCEPTING - A GENERAL-PURPOSE OPTIMIZATION ALGORITHM APPEARING SUPERIOR TO SIMULATED ANNEALING [J].

DUECK, G ;

SCHEUER, T .

JOURNAL OF COMPUTATIONAL PHYSICS, 1990, 90 (01) :161-175

[2] PARALLEL SIMULATED ANNEALING TECHNIQUES [J].

GREENING, DR .

PHYSICA D, 1990, 42 (1-3) :293-306

[3]

GROSTSCHEL M, 1984, 38 U AUGSB PREPR

[4]

Hoffmann K. H., 1991, PARALLEL DISTRIBUTED, P154

[5] RELAXATION AND AGING IN SPIN-GLASSES AND OTHER COMPLEX-SYSTEMS [J].

HOFFMANN, KH ;

SIBANI, P .

ZEITSCHRIFT FUR PHYSIK B-CONDENSED MATTER, 1990, 80 (03) :429-438

[6]

HOFFMANN KH, 1990, APPL MATH LETT, V3, P53

[7]

JAKOBSEN MO, 1988, MODEL OPTIMIZATION E, V2, P361

[8] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680

[9] EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM [J].

LIN, S ;

KERNIGHAN, BW .

OPERATIONS RESEARCH, 1973, 21 (02) :498-516

[10]

MERZARD M, 1987, SPIN GLASS THEORY BE

← 1 2 →