Abstract: Traditional simulated annealing (SA) algorithm suffers from the problems of slow convergence, lack of memory in random sample and dependence on specific issues. This paper proposes a parallel SA algorithm based on particle swarm optimization (PSO) algorithm to solve the problems. By including the individual’s memory of PSO, the proposed algorithm can enhance the exploitation capability. In order to maintain diversity, a new opposition rotation learning strategy is introduced on the basis of opposition-based learning (OBL) algorithm. With the natural parallelism of PSO, the shortcoming of problem-dependence of SA is solved. In addition, the proposed algorithm runs on cluster to achieve coevolutions. Experiments conducted with protein structure prediction based on Toy models show that the proposed algorithm outperforms both in convergence speed and solution quality

Key words: Agent, simulated annealing, particle swarm optimization, opposition-based learning, parallel computing

摘要： 针对模拟退火（simulated annealing，SA）算法收敛速度慢，随机采样策略缺乏记忆能力，算法内在的串行性使其具有并行化问题依赖等缺点，提出了基于粒子群优化（particle swarm optimization，PSO）算法的并行模拟退火算法。该算法利用粒子群优化算法中个体的记忆功能引导算法在解空间中开展精细搜索，在反向学习算法基础上设计新的反向转动操作机制增加了算法的多样性，借助PSO的天然并行性克服了SA的并行问题依赖性，并在集群上实现了多Agent协同进化的改进算法。对Toy模型的蛋白质结构预测问题进行了仿真实验，结果表明该算法能有效提高求解问题的质量和效率。

关键词: Agent, 模拟退火, 粒子群优化, 反向学习, 并行计算