模拟退火算法的并行分析与应用.pdfVIP

模拟退火算法的并行分析与应用 1 1 阮宏玮 ，李文 (1.内蒙古大学计算机学院 计算机科学系,内蒙古 呼和浩特 010021） 摘 要:对模拟退火算法进行并行性分析，并且提出了模拟退火算法的并行策略。在这篇文章中我们利用了并行模拟退火 算法解决了TSP(Traveling Salesman Problem)应用问题，理论分析和实验结果表明并行的TSP 算法能够加快有哪些信誉好的足球投注网站效率和收 敛性。该并行TSP 保持了原有算法的有哪些信誉好的足球投注网站特性，在一定精度范围内可以快速完成大规模有哪些信誉好的足球投注网站。 关键词: 模拟退火；并行；MPI ；TSP Parallelism Analysis and Application of Simulated Annealing Algorithm Hongwei Ruan 1, Wen Li 1 (1. Dept. of Computer Science, Inner Mongolia University, Hohhot Inner Mongolia 010021, China) Abstract: The parallism of simulated annealing algorithm is analyzed. Furthermore, the parallel strategy of simulated annealing algorithm is proposed. TSP ( Traveling Salesman Problem) is solved with parallel simulated annealing algorithm in this paper. Theoretical analysis and experimental results show that the convergence and search efficiency of TSP can be accelerated. The search characteristics of TSP are still held in the parallel TSP. In a certain precision, large-scale search can be completed quickly with parallel TSP. Key words: Simulated Annealing Algorithm; Parallel; MPI; TSP 1 模拟退火算法概述 式随机有哪些信誉好的足球投注网站过程。它模拟固体物质退火过程的热平 衡问题与随机有哪些信誉好的足球投注网站寻优问题的相似性来达到寻找 组合优化是当今重要的研究与应用领域。一般 全局最优或近似全局最优的目的。不同于 来说，该类问题包含 NP 完全问题，因此，精确地 Metropolis 算法，仿真退火法中的温度是随着退火 求解全局最优解一般是不可能的。模拟退火算法 的时候有所改变，因此如何对温度作有效的调整就 (Simulated Annealing)模拟物理规律，已在解决 变成整个模拟退火法最重要的一环。在有哪些信誉好的足球投注网站最优解 诸多典型组合优化问题中显示了良好的性能和效 的过程中，模拟退火法除了可以接受优化解外，还 果。模拟退火算法俗称固体降温，来源于固体退火 有一个随机接受准则(Metropolis 准则)有限度地 原理，模仿自然界的物理行为来求解函数最小值的 接受恶化解，并且接受恶化解的概率慢慢趋向于0， 方法。退火是一种物理过程，一种金属物体再加热 这使得算法有可能从局部极值区域中跳出，即可能 至一定的温度后，它的所有分子在状态空间中自由