基于并行模拟退火算法的TSP问题求解

郏宣耀：基于并行模拟退火算法的 TSP 问题求解
准则六部分。 从理论上分析，为了使算法最终得到全局最优，应把初始温度设置尽量大，温度下降尽量缓慢。但这导致算法收敛速度 过慢，优化效率降低。实际应用中，通常随机产生一组解，计算其目标函数值的方差作为初始温度。鉴于计算的方便，温度 更新函数一般取指数退温，即 Ti 1 Ti , (0,1) 。为使温度下降不至过快，λ取值一般接近于 1。 状态产生函数的功能是产生一新解，它应尽可能使产生的候选解遍布整个解空间。候选解通常在当前状态的邻域结构内 以一定概率方式产生。其中领域函数与概率方式由问题的性质决定。候选解产生之后若优于当前解则接受其并取代当前解， 若劣于当前解，则由状态接受函数决定是否接受。通常采用 min[1, exp( C / t )] 作为状态接受函数。可见，随着温度的降低， 接受劣解的概率也随之降低以使算法最终收敛到全局最优。 内循环终止准则亦即 Metropolis 抽样稳定准则，它决定当前温度下抽样的次数。理论上每个温度下应使相应的 Markov 链达到平稳概率分布， 但实际应用时显然是无法实现的。 因此， 通常以其它条件代替。 如判断是否达到局部平衡， 控制 Markov 链长等。外循环终止准则即算法终止准则，它决定算法何时结束，理论上要求终止温度趋于 0，但实际上是不实用的。一般 可以设置终止温度的阈值、设置外循环迭代次数、检验系统熵是否稳定等。 基此，模拟退火算法的基本流程可以描述如图 1：
本文首先用一个 20 个城市 TSP 实例进行数值实验， 该 20 个城市的坐标信息如表 1。 文献[8]利用改进遗传算法得到路径 长度为 24.38 的最优解。本文利用多种群并行模拟退火算法运行 20 次，所有 20 次运行中均得到该最优路径，平均 4.218 秒 得到该最优解。 而对该实例使用传统模拟退火算法时平均消耗 6.298 秒才得到最优解， 因此该并行算法显示出了良好的效果。 同时，本文对 35-TSP 实例与 70-TSP 实例分别应用传统模拟退火算法和并行模拟退火算法进行求解，结果如表 2。 表 1 20 个城市的坐标信息 城市序号 表 2 并行 SA 与 SA 算法性能对比
5 结束语
模拟退火算法是一种尤其适用于求解组合优化问题的随机寻优算法，它对于搜索行为具有很强的控制能力，但由于仅对 一个解进行串行优化，因而对搜索过程的把握与控制能力显得薄弱。利用遗传算法中多种群群体进化机制可有效改善算法对 搜索过程的控制，从而使并行模拟退火算法的效率比传统模拟退火算法有了较大改进。
体优化的并行机制。该机制通过将单个解的串行优化转化为许多个解同时进行的并行优化来提高算法的整体优化 效率。利用该算法求解 TSP 问题能够显著提高优化效率，仿真结果表明该算法是有效的。 关键词：并行优化；多种群；模拟退火；旅行商问题；组合优化 中图分类号：TP301.6 1 引言 模拟退火算法是 20 世纪 80 年代初提出的一种基于蒙特卡罗（Mente Carlo）迭代求解策略的启发式随机优化算法。[1] 它通过 Metropolis 接受准则概率接受劣化解并以此跳出局部最优， 通过温度更新函数的退温过程进行趋化式搜索并最终进入 全局最优解集。 但模拟退火算法在某一温度下为了达到解的平稳必须使采样次数尽可能的大， 即尽量增大对应 Markov 链长， 且为了优化过程的平滑必须使退温速度尽量缓慢，这使得模拟退火算法的优化效率很难提高。为此，许多学者提出了各种改 进方法，如改进状态产生函数、[2][3]改进固定的退温策略和状态接受函数，[4]将算法的寻优过程由串行转化为并行[5][6][7]等。 其中，并行机制的引入能从根本上提高算法寻优和收敛速度，改善优化效率。基于多处理器的并行机制研究和应用的较为普 遍，[5][6]该方法通过若干台主从式或对称式处理器协同计算来提高算法执行效率。本文则基于多种群群体优化，实现算法本 身的并行性。 TSP 是组合优化问题中最为典型的 NP 难题之一， 精确解算法的时间是关于问题规模的指数函数， 存在指数爆炸的问题， 实际求解一般使用近似解算法。传统的算法有动态规划法、分支定界法、最近邻法、最近插入法、双极小树生成法等。但这 些算法的时间性能仍不理想（如动态规划、分支定界等）或寻优性能不佳，易于求得局部最优解（如最近邻法等） 。模拟退 火算法等现代启发式随机优化算法是求解此类问题的有效方法。这里仅讨论对称 TSP，即 d i , j d j ,i 。应用本文的并行模拟 退火算法对 TSP 问题的仿真实验结果表明了该算法的有效性。 2 模拟退火算法原理及要素 模拟退火算法的思想来源于统计热力学中固体物质的退火过程。初始时系统温度较高，高温液态物质存在非均匀状态， 热运动较激烈。为了使系统在每一温度下均达到平衡状态，最终达到固体的基态，退温过程必须缓慢进行。当温度降至较低 时，粒子仅围绕晶体格点做微弱运动，逐渐凝固成固态。 组合优化问题和物理退火过程有其相似性。组合优化问题中的目标函数类似于物理退火过程中系统的能量，其解集相当 于粒子状态，最优解则对应于能量最低态。结合物理退火过程的抽样过程、接受准则、退火控制等，就构成适用于组合优化 问题的模拟退火算法。 模拟退火算法由某一较高初温开始，采用具有概率突跳特性的 Metropolis 接受准则在解空间进行随机搜索，随着温度的 下降重复抽样过程，直到各温度下的抽样稳定，最终得到问题的全局最优解。 2.2 关键组成部分 模拟退火算法的实质结构为内外两层循环。外循环控制温度的下降，内循环则在当前温度下重复抽样过程，直到抽样稳 定为止。算法中的关键组成因素为初始温度、温度更新函数、状态产生函数、状态接受函数、内循环终止准则和外循环终止 ────────── 基金项目：浙江大学宁波理工学院青年创新基金（2004-11） 收稿日期：2005-03-09 作者简介：郏宣耀（1982-） ，男，浙江舟山人，浙江大学宁波理工学院信息科学与工程分院教师，研究方向为计算智能，优 化理论与算法。 - 50 2.1 设计思想及原理 文献标识码：A 文章编号：1009-9115（2005）05-0050-04
图 1 标准模拟退火算法的流程图
3 并行机制及其实现
模拟退火算法是在某一当前状态 i 的邻域 Ni 中随机产生一个新状态 j 并以一定概率接受的。可见，接受概率仅依赖于新 状态和当前状态，即下一个状态的产生只和上一个状态有关，这从本质上决定了模拟退火算法是一种串行的随机优化过程。 这对算法的优化效率产生了影响。 在对 TSP 的求解中，遗传算法以其隐并行性显示出了较高的优化效率。[8]其改进形式多种群群体进化策略给模拟退火算 法的应用带来启示。标准模拟退火算法仅对一个解进行串行优化，算法优化效率很难提高。因此，考虑将多种群群体优化机 。 制引入模拟退火算法，构造并行模拟退火算法（PSA） 在 PSA 中，算法首先由初始化过程随机产生 K 个规模为 N 的进化种群，并计算种群中每个解的目标函数值，将每个种 群中的最优解保存后由状态产生函数在每个解的领域结构内产生 KN 个候选解，并计算候选解的目标函数值。若候选解的目 标函数值大于当前解则取代之，否则根据接受准则判断是否接受。这样形成了新一代种群。若 K 个新种群中有优于原历史 最优解的个体则保留该个体。随后继续重复抽样过程直到当前温度下的抽样稳定后进行退温操作，当温度低于某个终止温度 时算法结束。再从 K 个种群最优解中选出一个最优解作为最终得到的全局最优解。 这种多种群群体优化机制实现了个体解优化的并行性，与单个解串行优化相比效率大为提高。尽管由于所处理的解个数 - 51 -
第 27 卷第 5 期 Vol. 27 No.5
唐山师范学院学报 Journal of Tangshan Teachers College
2005 年 9 月 Sep. 2005
基于并行模拟退火算法的 TSP 问题求解
郏宣耀
（浙江大学 宁波理工学院信息科学与工程分院，浙江 宁波 摘 315100）
要：针对标准模拟退火算法串行优化单个解，优化过程较长、效率较低的弱点，提出一种基于多种群群
100 100 100 97.2 98.9 83.7
4.218 6.298 15.112 34.231 47.712 112.366
传统的模拟退火算法尽管最终得到的最优解不依赖于初始解的质量，但初始解的质量却对算法的寻优性能产生重要影响。 因此在单个解的串行模拟退火算法中经常使用一个快速优化算法来生成一个较高质量的初始解。但这使得算法在初始化过程中 消耗一部分的时间。 多种群并行模拟退火算法尽管也增加了额外解的计算时间， 但其解集覆盖率使算法的效率得到了显著提高。 同时，在对不同 TSP 问题实例的分析中发现，针对不同的问题，种群个数及种群规模的设置也不是确定的。一般，种 群个数可取 2 至 5 之间， 种群规模可取 20 至 60 之间。 种群规模过小会使算法退化为串行， 过大则增加了不必要的计算开销。 设置多个种群是为了增强算法跳出局部最优的能力，若个数过小则导致概率突跳性降低，算法容易陷入局部最优，若过大也 无助于算法突跳能力的进一步增加，具体应视目标函数形状中波峰或波谷的个数而定。
第 27 卷第 5 期
唐山师范学院学报
2005 年第 5 期
的增加而增大了计算量，但由于多种群中多个解覆盖解空间的面积增大，跳出局部最优和探索全局最优解的效率大为增加， 因而使算法整体效率得到改善。 并行模拟退火算法的步骤可描述如下：
S1：初始化：设置控制参数，产生 K 个规模为 N 的种群； S2：计算每个解的目标函数值并保留各种群的最优解； S3：While(T>Te) //Te 为终止温度 S3.1：While(抽样过程未达到稳定) S3.1.1：for(i=1;i<=KN;i++) S3.1.1.1：在当前解的领域结构内产生一个候选解； S3.1.1.2：计算候选解的目标函数并由接受准则判断是否接受； S3.1.2：检查各种群是否出现历史最优解，若有则保留之； S3.1.3：判断当前温度下是否达到抽样稳定；若稳定则跳出本层循环； S3.2：退温操作； S3.3：判断当前温度是否等于或低于终止温度，若是则跳出本层循环； S4：在 K 个历史最优解中选出最优的一个解； S5：输出结果，算法结束。 4 仿真结果分析