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