MOLECULAR-CONFORMATION ON THE CM-5 BY PARALLEL 2-LEVEL SIMULATED ANNEALING

被引:27
作者
XUE, GL
机构
[1] UNIV MINNESOTA,ARMY HIGH PERFORMANCE COMP RES CTR,MINNEAPOLIS,MN 55415
[2] UNIV VERMONT,DEPT COMP SCI & ELECT ENGN,BURLINGTON,VT 05405
关键词
MOLECULAR CONFORMATION; GLOBAL OPTIMIZATION; SIMULATED ANNEALING; PARALLEL ALGORITHMS;
D O I
10.1007/BF01096722
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In this paper, we propose a new kind of simulated annealing algorithm called two-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space. Extensive computational results on Thinking Machines CM-5 are presented. With the full Lennard-Jones potential function, we were able to get satisfactory results for problems for cluster sizes as large as 100, 000. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of size as large as these have never been reported before.
引用
收藏
页码:187 / 208
页数:22
相关论文
共 35 条