蚁群算法在三维球面TSP中的性能评估与比较

本文探讨了蚁群算法在三维球面旅行商问题（System Non-Euclidean Traveling Salesman Problem, SNTSP）中的应用，由Hüseyin Eldema和Erkan Ülker两位学者合作完成，他们在Karamanoglu Mehmetbey大学和Selçuk大学的计算机科学系分别任职。TSP是一个经典的组合优化问题，涉及寻找一条路径，使一位旅行商能够访问所有城市并返回起点，同时最小化总旅行成本。 蚁群优化（Ant Colony Optimization, ACO）作为一种元启发式算法，被用于解决这个问题。在SNTSP中，由于城市的分布遵循球面几何特性，研究者使用了七个不同规模的点集进行实验，评估了最大最小蚂蚁系统（Maximum-Minimum Ant System, MMAS）在处理非欧几里得距离下的性能。实验中，MMAS与文献中的离散切比雪夫搜索算法（Discrete Chebyshev Search, DCS）和遗传算法（Genetic Algorithm, GA）进行了对比，以衡量其在求解球形TSP问题上的效率。 研究指出，蚁群算法在处理球面TSP时展现出了良好的性能，特别是在解决非对称性问题上，由于城市间的距离不均等，这使得蚁群算法的局部搜索和信息共享机制显得尤为重要。精确方法如分支定界法和精确剪枝算法虽然能保证找到全局最优解，但计算复杂度较高，而启发式算法如蚁群优化则提供了相对高效的近似解。 该研究发表于2017年的国际期刊《工程科学与技术》第20卷，通过一系列实验验证了蚁群算法在球面旅行商问题中的应用潜力，并展示了其在实际问题解决中的竞争力。此外，文章还遵循了Creative Commons Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND) 许可证，允许读者在非商业且不改变原作的情况下分享和使用研究成果。 总结来说，这项工作不仅为解决具有特殊几何约束的旅行商问题提供了新的解决方案，也为其他领域的非欧几里得优化问题提供了有价值的经验和参考。