求解旅行商问题的并行计算平台设计与实现

求解旅行商问题的并行计算平台设计与实现

董改芳， 付学良＊

【摘 要】 为有效提高混合优化算法对大规模旅行商问题实例的计算效果，开发了并行算法，提供了一个可视化并行计算平台.该平台可实现批量实例计算，调用Java相应的包实现SSH2协议，利用远程Linux命令实现任务提交，获取计算结果数据流，连接Excel实现计算结果统计，并将结果可视化.仿真结果表明：该方法可行，且性能优于相应的串行算法. 【期刊名称】宁夏大学学报（自然科学版） 【年(卷),期】2013(034)001 【总页数】5

【关键词】 组合优化；并行计算；旅行商问题；蚁群算法；遗传算法

蚁群算法和遗传算法的混合算法在求解国际库TSPLIB［1］的小规模货郎担问题实例时，体现了算法的优越性［2］.但对于城市规模稍大的实例来说，计算一次可花费几十分钟甚至更长（跟参数有关），算法的稳定性需要经过几十次的计算才能够确定，由此开发了并行程序，以提高算法的计算速度.

并行编程有多种不同的模式，其中使用较多的是MPI消息传递接口与Linux环境结合方式，由SSH客户端软件实现远程提交命令和传送文件.但这种模式存在缺陷，用户每提交一个计算任务需要在SSH客户端软件上输入一行Linux命令，而且计算结果不能以可视化的形式体现出来.对于在科学研究中需要统计大量计算数据并且要求计算结果以图形方式显示的情况来说，该模式不能满足要求.

旅 行 商 问 题 （traveling salesman problem，TSP）在国际标准库TSPLIB