共计 1034 个字符，预计需要花费 3 分钟才能阅读完成。
拜访【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:
