PARALLEL RECOMBINATIVE SIMULATED ANNEALING - A GENETIC ALGORITHM
PARALLEL RECOMBINATIVE SIMULATED ANNEALING - A GENETIC ALGORITHM
复制标题
DOI：
10.1016/0167-8191(94)00071-h
复制
发表时间：
1995-01-01
影响因子：
1.4
通讯作者：
GOLDBERG, DE
中科院分区：
文献类型：
--
作者：
MAHFOUD, SW;GOLDBERG, DE
本文介绍并分析了一种并行的受激退火方法。借鉴遗传算法，开发了模拟退火和遗传算法的有效组合，称为并行重组模拟退火。这种新算法力求保留模拟退火所需的渐近收敛特性，同时添加遗传算法的群体方法和重组能力。该算法使用二元重组算子和一元邻域算子来迭代一组解决方案而不是单个解决方案。给出了该算法的两种变体的全局收敛性证明。检查收敛行为，并将经验分布与玻尔兹曼分布进行比较。并行重组模拟退火可以在 SIMD、MIMD 或共享内存机器上直接实现。该算法在 CM-5 上实现，在两个欺骗性问题上重复运行，以证明更大的群体规模可能带来的附加隐式并行性和更快的收敛性。
This paper introduces and analyzes a parallel method of stimulated annealing. Borrowing from genetic algorithms, an effective combination of simulated annealing and genetic algorithms, called parallel recombinative simulated annealing, is developed. This new algorithm strives to retain the desirable asymptotic convergence properties of simulated annealing, while adding the populations approach and recombinative power of genetic algorithms. The algorithm iterates a population of solutions rather than a single solution, employing a binary recombination operator as well as a unary neighborhood operator. Proofs of global convergence are given for two variations of the algorithm. Convergence behavior is examined, and empirical distributions are compared to Boltzmann distributions. Parallel recombinative simulated annealing is amenable to straightforward implementation on SIMD, MIMD, or shared-memory machines. The algorithm, implemented on the CM-5, is run repeatedly on two deceptive problems to demonstrate the added implicit parallelism and faster convergence which can result from larger population sizes.