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

《模拟退火算法的并行分析与应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、模拟退火算法的并行分析与应用11阮宏玮，李文(1.内蒙古大学计算机学院计算机科学系,内蒙古呼和浩特010021）摘要:对模拟退火算法进行并行性分析，并且提出了模拟退火算法的并行策略。在这篇文章中我们利用了并行模拟退火算法解决了TSP(TravelingSalesmanProblem)应用问题，理论分析和实验结果表明并行的TSP算法能够加快搜索效率和收敛性。该并行TSP保持了原有算法的搜索特性，在一定精度范围内可以快速完成大规模搜索。关键词:模拟退火；并行；MPI；TSPParallelismAnalysisandApplicationofSimulatedAnnealingA

2、lgorithm11HongweiRuan,WenLi(1.Dept.ofComputerScience,InnerMongoliaUniversity,HohhotInnerMongolia010021,China)Abstract:Theparallismofsimulatedannealingalgorithmisanalyzed.Furthermore,theparallelstrategyofsimulatedannealingalgorithmisproposed.TSP(TravelingSalesmanProblem)issolvedwithparallels

3、imulatedannealingalgorithminthispaper.TheoreticalanalysisandexperimentalresultsshowthattheconvergenceandsearchefficiencyofTSPcanbeaccelerated.ThesearchcharacteristicsofTSParestillheldintheparallelTSP.Inacertainprecision,large-scalesearchcanbecompletedquicklywithparallelTSP.Keywords:Simulate

4、dAnnealingAlgorithm;Parallel;MPI;TSP1模拟退火算法概述式随机搜索过程。它模拟固体物质退火过程的热平衡问题与随机搜索寻优问题的相似性来达到寻找组合优化是当今重要的研究与应用领域。一般全局最优或近似全局最优的目的。不同于来说，该类问题包含NP完全问题，因此，精确地Metropolis算法，仿真退火法中的温度是随着退火求解全局最优解一般是不可能的。模拟退火算法的时候有所改变，因此如何对温度作有效的调整就(SimulatedAnnealing)模拟物理规律，已在解决变成整个模拟退火法最重要的一环。在搜索最优解诸多典型组合优化问题中显示了良好的性能和

5、效的过程中，模拟退火法除了可以接受优化解外，还果。模拟退火算法俗称固体降温，来源于固体退火有一个随机接受准则(Metropolis准则)有限度地原理，模仿自然界的物理行为来求解函数最小值的接受恶化解，并且接受恶化解的概率慢慢趋向于0，方法。退火是一种物理过程，一种金属物体再加热这使得算法有可能从局部极值区域中跳出，即可能至一定的温度后，它的所有分子在状态空间中自由找到全局最优解，并保证了算法的收敛性。这就是运动。随着温度的下降，这些分子逐渐停留在不同回火技术(降温后以一定概率升温)，引入产生函数的状态。在温度最低时，分子重新以一定的结构排扰动因子，来控制搜寻全局最优值的范围列

6、，而分子的分布也就是波兹曼(Boltzamnn)概率模拟退火算法就是这样一个将退火过程中系[1]分布。统熵值类比为目标函数值F，来模拟这个退火系统算法的计算过程可视为重复递减控制参数值的算法。(温度)进行蒙特卡罗(Metropolis)算法的迭代过程。一次Metropolis算法是指，对于控制参数t2模拟退火算法的模型的每一取值，算法在马尔科夫(Markov)链长度内模拟退火算法的物理意义在于先把固体加热持续进行“产生新解—判断—接受/舍弃”的迭·至足够高温，使固体中所有粒子处于无序的状态代过程，对应着固体在某一恒定温度下趋于热平(最高的熵值)，然后将温度缓慢下降，粒子渐渐有

7、衡的过程。算法终止时的当前解为所得近似最优序(熵值下降)，这样只要温度上升得足够高，冷却解，这是基于Metropolis迭代求解法的一种启发过程足够慢，·1本工作得到了国家自然科学基金（60303033），内蒙古大学513人才计划项目，内蒙古大学博士科研启动基金的资助。则所有粒子最终会处于最低能态(最低的熵)。基于限制是每个城市只能拜访一次，而且最后要回到原[5]此，对应的算法基本思想为：来出发的城市。路径的选择目标是要求得的路程为(1)初始化：初始温度T(充分大)，初始解状所有路径之中的最小值。态S(