TSP的几种求解方法及其优缺点
以下为《TSP的几种求解方法及其优缺点》的无排版文字预览，完整内容请下载
一、什么是TSP问题
旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边某某，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。
旅行商问题可分为如下两类：
1）对称旅行商问题（dij=dji，Πi，j=1，2，3，?，n）；
2）非对称旅行商问题（dij≠dji，?i，j=1，2，3，?，n）。
非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。
若对于城市V={v1，v2，v3，?，vn}的一个访问顺序为T={t1，t2，t3，?，ti，?，tn}，其中ti∈V（i=1，2，3，?，n），且记tn+1=t1，则旅行商问题的数学模型为：minL=。
TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较标准。因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。
二、主要求解方法
基于TSP的问题特性，构造型算法成为最先开发的求解算法，如最近邻点、最近合并、最近插入、最远插入、最近添加、贪婪插入等。但是，由于构造型算法优化质量较差，迄今为止已开发了许多性能较好的改进型搜索算法，主要有：
1）模拟退火算法
2）禁忌搜索算法
3）Hopfield神经网络优化算法
4）蚁群算法
5）遗传算法
6）混合优化策略
模拟退火算法方法
1）编码选择：采用描述TSP解的最常用的一种策略——路径编码。
2）SA状态产生函数的设计：对于基于路径编码的SA状态产生函数操作，可将其设计为：①互换操作（SWAP）；②逆序操作（INV）；③插入操作（INS）。
3）SA状态接受函数的设计：min{1，exp（-△/t）}>random[0，1]准则是作为接受新状态的条件最常用的方案，其中△为新旧状态的目标值差，t为”温度”。
4）初温和初始状态：最常用且可理解的初温确定方案是，首先随机产生一组状态，确定两两状态间的最大目标值差：|Δmax|，然后由式t0=-Δmax/lnpr，其中pr为初始接受概率（理论上应接近1，实际设计时也可以取）。初始状态可采用启发式算法（如2opt方法）快速得到一个解，并以此为SA的初始状态。
5）退温函数的设计：指数退温函数是最常用的退温策略（tk=λtk-1，λ为退温速率）。
6）温度修改准则和算法终止准则的设计：可采用阈值法设计的”温度修改”和”算法终止”两准则。
禁忌搜索算法
基于禁忌搜索算法的一般设计原则，对典型的组合优化问题TSP，其算法可以按如下方案实现：
1）初始解：可随机产生也可基于问题信息借助一些启发
式方法产生以保证一定的初始性能。
2）邻域结构：常用方法是互换（SWAP）、插入
（INSERT）、逆序（INVERSE）等操作。
3）候选解的选择：通常取当前解的邻域解集的一个子集作为候选解集，而取其中的满足藐视准则或非禁忌的最优状态为最佳候选解。
4）禁忌表及其长度：建议尝试自适应长度法，譬如根据目标值更新的情况或禁忌频率信息来适当增加或缩短禁忌表长度。
5）藐视准则：采用若某个状态的性能优于”bestsofar”状态，则忽视其禁忌属性，直接选取它为当前状态。
6）集中搜索和分散搜索策略：分别采用在一定步数的迭代后基于最佳状态进行重新初始化并对其邻域进行多步趋化性搜索和对算法 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 SP实例则需要采用启发式方法。
为了进一步提高算法的全局优化能力，避免搜索过程陷入局部极小，现已提出的改进策略主要有：并行多邻域搜索，平滑优化曲面形状，引进重升温、熵抽样等高级技术等。对于复杂优化问题，单一机制的优化算法很难实现全局优化，且效率较低。多种优化机制和邻域搜索结构相混合，是能较大程度提高全局优化度和鲁棒性的有力途径，并可一定程度上放松对单一算法参数选择的苛刻性。所以混合优化策略会是一种趋势。
对于TSP的求解，我认为以后在以下几个方面可能会有很好的进展：
1）新的方法的提出；
2）基于目前各种方法的改进；
3）混合优化策略的发展等。我们希望最终人们能找到一种求解TSP的完美方法。
[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。
- 数学建模（cumcm）历届竞赛赛题基本解法
- 人教版小学数学一年级下册说课稿
- 校园安全工作会议记录3.17
- 问题学生帮扶措施
- 党员干部负面清单
- 淘宝销量突然下降时的对策
- 民主生活会领导班子剖析材料
- 钱包开通状态同步技术方案V0.1
- 幼儿园中班第2周游戏活动计划
- 植树问题教学设计
- 专题组织生活会意见建议梳理情况
- 防范风险要处理好六大关系
- 用连除方法解决问题的教学设计
- 作业2：成功解决学生心理健康问题的案例故事
- 三小赵燕研修计划
- 幼儿园工程建设专项资金及其他各类资金使用的自查报告
- 反洗钱培训素材
以上为《TSP的几种求解方法及其优缺点》的无排版文字预览，完整内容请下载
TSP的几种求解方法及其优缺点由用户“jiangniuniu1”分享发布，转载请注明出处