混合SPMD模拟退火算法及其应用

被引：10

作者：

都志辉

李三立

吴梦月

李树有

朱静

机构：

[1] 清华大学计算机科学与技术系!北京,清华大学计算机科学与技术系!北京,清华大学材料科学与工程学院!北京,清华大学材料科学与工程学院!北京,清华大学材料科学与工程学院!北京

来源：

计算机学报 | 2001年 / 01期

关键词：

模拟退火算法; 下山法; 多参数组合优化;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

模拟退火算法由于有很好的数学特性——以概率 1收敛于全局最优值 ,再加上其算法本身与特定的问题无关 ,因此被广泛地用于各种组合优化问题 .但是 ,模拟退火算法又具有收敛速度慢 ,执行时间长 ,算法性能与初始值有关及参数敏感等缺点 ,使得它在不少应用中成为一种低效甚至是不可行的算法 .文中提出一种混合 SPMD模拟退火算法 ,在克服经典模拟退火算法内在串行性的同时 ,进一步和下山法结合起来 ,并综合多种优化方法 ,在一定的处理机规模内取得了可扩展的并行效果 ,显著提高了算法的收敛速度 ,克服了算法性能对初始值和参数选择的过分依赖 ,在提高算法性能的同时 ,方便了算法的使用 .该算法已在一个机群系统 THNPSC- 1上得以实现 ,并在材料科学的一个定量电子晶体学研究问题中得到应用 ,降低了该问题的求解时间 ,提高了求解质量 .

引用

页码：91 / 98

页数：8

共 10 条

[1]

A parallel simulated annealing algorithm with low communication overhead. Tarek M Nabhan,Albert Y Zomaya. IEEE Transactions on Parallel and Distributed Systems . 1995

[2]

Genetic algorithms and very fast simulated reannealing: A comparison. Lester Ingber,Bruce Rosen. Mathematical Computer Modeling . 1992

[3]

Computers and intractability: A guide to the theory of NP-completeness. Garey M R,D S Johnson. . 1979

[4]

Optimization by simulated annealing. Kirkpatrick S,Gelatt C D,Vecchi M P. Science . 1983

[5]

U-Net: A User-level network interface of parallel and distributed computing. Von Eicken T. Basu A. Buch V. et al. Proc. of the 15th ACM Symposium of Operating Systems Principles . 1995

[6]

The annealing algorithm. Otten R H J M,van Ginneken L P P P. . 1989

[7]

Sangiov anni -Vincetelli A.A parallel simulated annealing algorithm for placement of Macro-Cells. Casotto A,Romeo F. IEEE Transactions on Computer Aided Design . 1987

[8]

Convergence of an annealing algorithm. Lundy M,Mess A. Mathematical Programming . 1986

[9]

Parallel genetic simulated annealing: A massively parallel SIMD algorithm. Hao Chen,Nicholas S Flann,Daniel W Watson. Parallel and Distributed Systems . 1998

[10]

Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing. Gunter Deck,Tobias Scheuer. Journal of Computational Physics . 1990

← 1 →