模拟退火与蚁群混合并行算法解旅行商问题

ａｓ
ｏｆｔｅｎ
ｉｍｐｏｓｓｉｂｌｅ ｔｏ ｍｅｅｔ ｐｅｏｐｌｅ’Ｓ ｎｅｅｄ
ｔｏ
ｔｈｅ ｓｃａｌｅ ｏｆ ＴＳＰ ｉｎｃｒｅａｓｅ ｇｒａｄｕａｌｌｙ．Ｆｏｒ ｔｈｅ ｐｒｏｂｌｅｍ，ｔｈｉｓ ｐａｐｅｒ ｄｉｓｃｕｓｓｅｄ
ｔｈｅ ｐａｒａｌｌｅｌ ｍｅｔｈｏｄｓ
ａ
ｉｍｐｌｅｍｅｎｔ ｔｈｅ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ
通过表３与表１、表２比较，可以得到以下结论：蚁群算法有非常好的时间效率，但是寻最优解的能力 有待提高；模拟退火算法具有非常好的寻找最优解的能力，但足时间复杂度太高；混合算法综合了蚁群算法 和模拟退火算法的优点，解决了蚁群算法中寻最优解能力不强和模拟退火搜索中时间效率过低的问题，得到 了很好的效果．在处理机为两台并行时，各种算法的并行效率都非常好，基本可以达到８０％以上． 并行混合算法同样存在着随着处理机台数的增加，算法的并行效率有所下降的问题，但是这是由于并行 算法的本质决定的．在混合算法已经对蚁群算法和模拟退火算法的缺点进行一定程度的改善之后，并行混合 算法则将两种算法的并行优点体现的更加明显．但是混合算法的并行效率没有蚁群算法和模拟退火算法高， 主要是因为在混合算法的设计中，有两次需要进程间通信，浪费了大量的通信时间．但混合算法的效率还是 可以接受的．
ＦＯＲ（／＝０；ｉ＜Ｎｘ宰Ⅳｌ；卅）
∥内层循环，控制在一个温度下循环的次数，由于只是蚁群算法提供初始解 ∥因此在混合算法中，将循环次数设置为城市个数的平方 由新状态产生函数２－ＯＰＴ，产生新状态＆
计算代价函数以ｓＩ），计算增量Ａｔ＝ＡＳｇ－ＡＳ）；
ＩＦ（Ａｔ＜０） 接受新状态为当前最优解；
ＥＬＳＥ
按照新状态接受函数确定是否接受新状态为当前最优解；
Ａｂｓｔｒａｃｔ Ｔｈｅ ｉｎｔｅｌｌｉｇｅｎｔ ｏｐｔｉｍｉｚａｔｉｏｎ
ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｓｏｌｖｉｎｇ ＴＳＰ ｍａｉｎｌｙ ｉｎｃｌｕｄｅ ａｎｔ ｃｏｌｏｎｙ
ａｌｇｏｒｉｔｈｍ ａｎｄ ｓｉｍｕｌａｔｅｄ
ａｎ－
ｎｅａｌｉｎｇ，ｅｔｃ．Ｔｈｅｓｅ
ｉｓ
ａｌｇｏｒｉｔｈｍｓ ｈａｖｅ ｓｉｇｎｉｆｉｃａｎｔ ａｄｖａｎｔａｇｅｓ ａｎｄ ｒｕｎ ｆａｓｔｅｒ ｔｈａｎ ｔｒａｄｉｔｉｏｎａｌ ｅｘａｃｔ ａｌｇｏｒｉｔｈｍｓ．Ｂｕｔ，ｔｈｅ ｓｐｅｅｄ
第３９卷第２期
、，０１．３９ Ｎｏ．２
河北工业大学学报
ＪＯＵＲＮＡＬ ０Ｆ ＨＥＢＥＩ ＵＮｌＶＥＲＳＩＴＹ ＯＦ ＴＥＣＨＮＯＬＯＧＹ
２０１０年４月
Ａｐｒｉｌ ２０１０
文章编号：１００７—２３７３（２０１０）０２—００４８—０４
模拟退火与蚁群混合并行算法解旅行商问题
许智宏，宋 勃，郭艳艳
（河北工业大学计算机科学与软件学院，天津３００４０１）
ＥＮＤＩＦ ＥＮＤＦＯＲ ＥＮＤＦＯＲ
ＭＰＩ Ｂａｒｒｉｅｒ ０使用路障机制同步集合中的所有进程； ＭＰＩ Ｒｅｄｕｃｅ（）使用规约操作收集各处理机上的模拟退火搜索的初始解； ＭＰＩ—Ｂｃａｓｔ ０使用广播操作统一各处理机上的模拟退火搜索的初始解；
蚁群算法的系统初始化 初始化蚂蚁数量ｍ，设置迭代次数Ⅳ２； 设置根据模拟退火算法提供的初始解，蚁群系统基本参数ａ，声，Ｐ，ｑｏ； 设置各个处理机中蚁群中蚂蚁的起始位置； 设置最优路径长度模拟退火算法提供的初始解； ＷＨＩＬＥ（迭代次数＜Ⅳ２）
摘要求解ＴＳＰ问题的智能优化算法主要包括蚁群算法和模拟退火算法等，这些算法求解ＴＳＰ问题的速度比传 统的精确求解算法有很大改进，但在问题的求解空间逐渐增加时，串行执行速度往往还是无法满足人们的需求． 针对此问题，研究了蚁群算法、模拟退火算法以及两者的混合算法的并行实现方法，建立了ＰＣ机群实验平台， 基于ＭＰＩ环境对蚁群算法、模拟退火算法以及混合算法的并行算法进行了测试．根据理论研究和实际测试的结 果，比较了并行算法和传统串行算法的性能差异，总结了利用ＰＣ机群系统求解旅行商问题的并行求解的可行性， 得出了关于并行效率等方面的一些有意义的结论． 关键词旅行商问题；模拟退火算法；蚁群算法；混合算法；并行计算 中图分类号ＴＰｌ８３ 文献标识码Ａ
Ｕｓｉｎｇ Ａｎｔ Ｃｏｌｏｎｙ Ａｌｇｏｒｉｔｈｍ ａｎｄ Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ Ｐａｒａｌｌｅｌ
Ａｌｇｏｒｉｔｈｍ
ｔｏ
Ｓｏｌｖｅ Ｔｒａｖｅｌｉｎｇ Ｓａｌｅｓｍａｎ Ｐｒｏｂｌｅｍ
ＸＵ Ｚｈｉ．ｈｏｎｇ，ＳＯＮＧ Ｂｏ，ＧＵＯ Ｙａｎ．ｙａｎ
（Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｈｅｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｔｉａｎｊｉｎ ３００１３０，Ｃｈｉｎａ）
ｆｏｒｍａｎｃｅ ｄｉｆｆｅｒｅｎｃｅｓ ｂｅｔｗｅｅｎ ｐａｒａｌｌｅｌ ａｌｇｏｒｉｔｈｍｓ ａｎｄ ｔｒａｄｉｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍｓ ｗｅｒｅ ｐａｒａｌｌｅｌ
ａｌｇｏｒｉｔｈｍ
ｔｏ
ｓｏｌｖｅ ＴＳＰ ｉｎ ｃｌｕｓｔｅｒ ｏｆＰＣｓ ＷａＳ ｄｉｓｃｕｓｓｅｄ ａｎｄ ｓｏｍｅ
ｍｅａｎｉｎｇｆｕｌ ｃｏｎｃｌｕｓｉｏｎｓ ａｂｏｕｔ ｐａｒａｌｌｅｌ ｅｆｆｉｃｉｅｎｃｙ
收稿日期：２００９－０７—０９ 作者简介：许智宏（１９７０一）。女（汉族），副教授，博士
－
万方数据
第２期
许智宏，等：模拟退火与蚁群混合并行算法解旅行商问题
４９
１蚁群算法和模拟退火算法的并行实现 模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却．加温时，固体内部粒子随
升温变为无序状，内能增大；而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基 态，内能减为最小．用固体退火模拟组合优化问题啪，将内能Ｅ模拟为目标函数值＾温度丁演化成控制参 数ｔ，即得到解组合优化问题的模拟退火算法．由初始解ｆ和控制参数初值ｔ开始，对当前解重复“产生新 解一计算目标函数差一接受或舍弃”的迭代，并逐步衰减ｆ值，算法终止时的当前解即为所得近似最优解． 在自然界中，蚁群在没有视觉的情况下通过个体之间交换信息素，能够在较短的时间内找到食物和蚁巢 之间的最短路径．在这个过程中，每个蚂蚁通过感知信息素的存在和强度，倾向于向信息素浓度大的方向移 动，使得整个蚁群的集体行为构成了信息素的正反馈过程，从而找到较好路径．在蚁群算法求解ＴＳＰ问题时， 初始分布在各节点之间路径上的信息素相同，表示各节点作为第一个被经过的节点的概率相同，根据各蚂蚁 对每个节点选中的次数进行信息素的调整，以遍历所有节点的路径最短为优化目标川． 根据传统蚁群算法和模拟退火算法，分别设计并行蚁群算法、并行模拟退火算法，并将其应用于求解国 际通用的ＴＳＰ数据库ＴＳＰＬｌＢ中的ｃｉｔｙ３１，ａｔｔ４８，ｐｒ７６和ｃｈｌ３０的ＴＳＰ问题．每种算法在各个规模的旅行商问 题上做１０次实验，得到如表ｌ、表２所示结果．
万方数据
第２期
许智宏，等：模拟退火与蚁群混合并行算法解旅行商问题
５１
当前最优解，否则就拒绝；
ＥＮＤＦＯＲ
检索本次循环中找到的最优路径，比较并修改全局最优路径； 应用全局更新规则对当前最优及最差路径上的信息素作全局调整；
ＭＰＩ—Ｂａｒｔｉｅｒ ０使用路障机制同步集合中的所有进程；
ＭＰＩ—Ｒｅｄｕｃｅ（）使用规约操作收集各进程的路径上的信息素； ＭＰＩ Ｂｃａｓｔ ０使用广播操作统一各进程的路径上的信息素； ＥＮＤＷＨＩＬＥ
ＭＰＩ Ｒｅｄｕｃｅ ０使用规约操作获取当前进程集合搜索到的最优路径；
由最优路径的进程输出全局最优路径长度；
ＥＮＤ
３实验结果及分析比较
将并行混合算法应用于求解ａｔｔ４８，ｐｒ７的ＴＳＰ问题，得到如表３所示结果．
表３并行混合算法与串行混合算法的实验结果
Ｔａｂ．３ Ｒｅｓｕｌｔ ｏｆ ｔｈｅ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｎｄ ａｎｔ ｃｏｌｏｎｙ ｈｙｂｒｉｄ ａｌｇｏｒｉｔｈｍ
由于模拟退火算法的时间复杂度非常高，所以用空间来解决时间问题，在并行算法中将前一温度下所有 处理机中搜索到的最优解通知各处理机，减少单独一台处理机上搜索的次数，保证搜索的次数的总和，以加 快搜索速度．但是，随着处理机台数的增加，算法的并行效率也有所下降．
万方数据
河北工业大学学报
第３９卷
２模拟退火蚁群算法的混合算法的并行实现
通过对模拟退火算法和蚁群算法的基本算法研究可知，模拟退火算法具有大范围快速全局搜索能力，但 对系统中的反馈信息利用不够，当求解到一定范围时往往做大量的无为的冗余迭代，求精确解效率低．蚁群 算法原理是一种正反馈机制，但初期信息素匮乏，求解速度慢Ｍ．基于两种基本算法的优缺点，采用模拟退 火算法生成信息素分布，利用蚁群算法求解精确解，优势互补． 经过前面的分析，模拟退火算法和蚁群算法并行的可行性已经得到证明．由于蚁群算法的生态属性及设 计思想决定了它具有内在并行性，在混合算法中，主要基于蚁群算法的并行性．首先各台处理机由模拟退火 算法产生较优解初始解，统一各个蚁群的初始解，较优解的路径留下信息素，其他的不改变；然后按照并行 蚁群算法得到最优解．对混合算法实现并行化的基本设计模型如下：
述而难于求解．求解ＴＳＰ问题的智能优化算法主要包括蚁群算法和模拟退火算法等，这些算法求解ＴＳＰ问题 的速度比传统的精确求解算法有很大改进，但在问题的求解空间逐渐增加时，串行执行速度往往还是无法满 足人们的需求［Ｉ－２］．本文在机群环境下，基于ＭＰＩ，设计了蚁群算法、模拟退火算法及两者混合的并行算法， 来实现对ＴＳＰ问题的求解，提高了算法的执行效率．
ＦＯＲ＠＝Ｐ幸ｍ／Ｑ；尼＜（Ｐ＋１）木ｍ／Ｑ；Ｊ叶）
初始化搜索禁忌表： ＷＨＩＬＥ（存在不属于搜索禁忌表的节点） 根据基本蚁群算法中的概率函数，蚂蚁选择目标节点并移动，修改搜索禁忌表； 应用局部更新规则，对路径上的信息素作局部调整； ＥＮＤＷＨＩＬＥ 各个蚁群在各自的当前最优解的邻域内找另外一个解，若路径长度差Ａｔ＜ｅ，则接受新解为自己蚁群的