广东工大团队利用MPI并行模拟退火算法优化TSP问题

本文档主要探讨了广东工业大学计算机学院工一717实验室参赛团队在PAC2015复赛中，使用基于模拟退火算法的策略优化TSP问题的项目。TSP（Traveling Salesman Problem）是一个经典的组合优化问题，涉及旅行商如何以最短路径访问所有城市并返回起点。团队成员包括周俊豪、纪伟、金赖晓斌，他们利用模拟退火算法的原理来解决这个问题。 模拟退火算法是一种启发式搜索方法，灵感来源于固体物理学的退火过程。在高温下，固体中的粒子处于无序状态，随着温度逐渐降低，系统趋向于更低能量的状态，最终达到平衡和最低能量。模拟退火算法将这一过程应用于求解复杂问题，通过设定一个初始温度，然后逐步降低温度，允许在局部最优解周围进行“热”跳跃，增加找到全局最优解的概率。 在应用程序的实现中，首先，团队读取包含城市信息的目标文件，生成一个随机的初始解，然后计算新序列与初始解之间的转移概率。当满足特定的停止条件（如温度低于某个阈值）时，更新初始解为新序列，并重复这个过程。整个流程中，关键的函数包括调用函数P和Neighbour，其中： 1. 函数P：负责计算接受新解的概率，这通常基于新解与当前解的距离和当前温度。 2. 函数Neighbour：用于生成新的解决方案，它可能涉及到对现有路径进行微小的调整，如交换两个城市的位置，以寻找可能的更优解。 程序运行在高性能计算环境，如元超级计算机，配置有64GB DDR3内存和Red Hat Enterprise Linux Server操作系统。使用的软件环境包括Red Hat 4.4.6-4，Linux内核2.6.32-279.e16.x86_64，以及Intel编译器和MPI并行编程工具。 应用程序的分析部分详细描述了整个流程，从简述模拟退火解决TSP问题的基本步骤，到深入剖析模拟退火函数的关键组成部分，以及原始TSP问题的程序设计图。这些细节展示了团队如何有效地利用模拟退火算法的特性来优化TSP问题，以期在比赛中获得理想的结果。