改进的禁忌搜索算法在旅行商问题中的应用

"这篇硕士学位论文主要探讨了基于节约算法和移动方向的禁忌搜索算法在解决优化问题中的应用，特别是针对旅行商问题(TSP)的解决方案。作者郭娜在曹晓东教授指导下，针对禁忌搜索算法的初始解依赖性和多样性搜索不足的问题进行了改进，通过结合e-w节约算法获取高质量初始解，并通过调整禁忌表存储结构和引入概率函数来增强算法的灵活性和多样性。" 在优化算法领域，禁忌搜索(Tabu Search, TS)作为一种智能优化算法，自1986年由Glover教授提出以来，因其独特性而备受关注。TS在解决组合优化和函数优化问题时展现出高效性，但同时也存在一些挑战，如对初始解的强烈依赖和在保持搜索多样性上的不足。 郭娜的研究中，首先针对禁忌搜索的弱点，引入e-w节约算法生成初始解。e-w节约算法是一种经典的路径规划方法，能有效生成较优解，为TS提供了一个更有力的起点，从而改善了搜索过程的收敛速度。通过这种方法，搜索过程的集中性得到了增强，有助于更快找到高质量解。 其次，为了提升TS的多样性，论文提出了两方面的改进。一是改进禁忌表的存储结构，不仅记录最近的搜索路径，还记录这些路径的改进情况。这样可以更好地反映解的改变程度，使搜索决策更倾向于有利于改进的方向。二是引入概率因素，根据移动信息动态调整评价函数，将确定性的选择过程转变为概率性，从而拓宽搜索领域，增加算法的灵活性。 旅行商问题(TSP)作为一个经典的组合优化问题，其求解一直是研究的重点。郭娜的应用部分，将改进后的禁忌搜索算法应用于TSP，设计出一种有效解决TSP的形式。这种方法有望在实际工程背景下，如物流配送、路线规划等领域，提供更高效的解决方案。 关键词涉及的主要概念包括禁忌搜索、e-w节约算法以及多样性搜索。这些技术的结合使用，旨在提高算法的性能和适应性，以应对复杂优化问题的挑战。这项研究为优化算法领域的理论研究和实践应用提供了有价值的贡献。