访问【WRITE-BUG数字空间】_[内附完整源码和文档]
该项目主要是利用局部搜索算法（LS）和模拟退火算法（SA）解决 TSP 问题。先是使用 LS 求解 TSP 问题，再尝试 SA 问题，比较两者，在效率上 SA 更占有。最后再在 LS 的基础上使用 SA，再优化 SA 部分算法，尝试求解 TSP 问题。选用的 TSP 测例为 eil101（有 101 个城市）。代码使用 python 语言编写，因此运算速度因为语言特性比编程语言要低。
摘要
该项目主要是利用局部搜索算法（LS）和模拟退火算法（SA）解决 TSP 问题。先是使用 LS 求解 TSP 问题，再尝试 SA 问题，比较两者，在效率上 SA 更占有。最后再在 LS 的基础上使用 SA，再优化 SA 部分算法，尝试求解 TSP 问题。选用的 TSP 测例为 eil101（有 101 个城市）。代码使用 python 语言编写，因此运算速度因为语言特性比编程语言要低。
导言
旅行商问题，即 TSP 问题（Traveling Salesman Problem），是求最短路径的问题，即“已给一个 n 个点的完全图，每条边都有一个长度，求总长度最短的经过每个顶点正好一次的封闭回路”。TSP 是组合优化问题，可以被证明具有 NPC 计算复杂性。如果希望暴力搜索其最佳解，其复杂度将是 O(n!)，其计算量随着 n 的增加将轻易超过目前计算机的可能算力。因此我们需要用更智能的方法求解。
于是我们先考虑局部搜索算法。局部搜索算法是贪心算法，他往往往邻域中最好的状态搜索，因此容易进入局部最优结果，而无法跳出局部最优的区域。
第二部分使用模拟退火算法。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法比起局部搜索算法，赋予了一定跳出局部最优解的能力，但能否跳出局部最优解依然依赖随机性。
实验过程
首先使用两种不同的局部搜索算法。
第一种选择邻域的方法是随机交换两个城市在序列中的顺序。每次循环中产生的候选序列为城市数（以下用 Cs 表示）*10，并从中选择一个最优的（距离最短的）作为下一步。
第二种选择邻域的方法是随机交换三个城市在序列中的顺序。每次循环中产生的候选序列为 Cs*10，并从中选择一个最优的（距离最短的）作为下一步。
这两种算法都按以下步骤实现：
录入初始状态，并打乱顺序产生一组随机状态，从这组状态（包括初始状态）
中选最佳的状态作为起点；
Repeat:产生一个集合 S
Repeat 10 * Cs times: