TSP的几种求解方法及其优缺点
15页1、、什么是 TSP 问题旅行商问题,简称TSP,即给定n个城 市和两两城市之间的距离,要求确定一条 经过各城市当且仅当一次的最短路线。其 图论描述为:给定图G= (V, A),其中VIJJJJ为顶点集, A 为各顶点相互连接组成的边 集,设D= (dij)是由顶点i和顶点j之间 的距离所组成的距离矩阵,要求确定一条 长度最短的Hamilton回路,即遍历所有顶 点当且仅当一次的最短距离。旅行商问题可分为如下两类: 1)对称旅行商问题(dij=dji,ni,j=1,2, 3, n);2)非对称旅行商问题(dijHdji,i, j=1, 2, 3, n)。非对称旅行商问题较难求解,我们一 般是探讨对称旅行商问题的求解。若对于城市V=v1,个访问顺序为T=t1,t2,V2, V3, Vn的一 t3, ti,tn,其中 tiV (i=l,2,3,n),且记 tn+1=ti,则旅行商问题的数学模型为:minL=。TSP 是一个典型的组合优化问题,并 且是一个 NP 完全难题,是诸多领域内出 现的多种复杂问题的集中概括和简化形 式,并且已成为各种启发式的搜索、优化 算法的间接比较标准。因此,快速、有
2、效 地解决TSP有着重要的理论价值和极高的 实际应用价值。二、主要求解方法基于 TSP 的问题特性,构造型算法成 为最先开发的求解算法,如最近邻点、最 近合并、最近插入、最远插入、最近添加、 贪婪插入等。但是,由于构造型算法优化 质量较差,迄今为止已开发了许多性能较好的改进型搜索算法,主要有:1)模拟退火算法3)Hopfield 神经网络优化算法4)蚁群算法5)遗传算法6)混合优化策略模拟退火算法方法1)编码选择:采用描述 TSP 解的最 常用的一种策略路径编码。2)SA 状态产生函数的设计:对于基 于路径编码的 SA 状态产生函数操作,可 将其设计为:互换操作(SWAP);逆 序操作(INV);插入操作(INS)。Ill3)SA 状态接受函数的设计: min1, exp ( /t) random0, 1准则是作为接 受新状态的条件最常用的方案,其中为 新旧状态的目标值差, t 为”温度”。IIIIII4)初温和初始状态:最常用且可理 解的初温确定方案是,首先随机产生一组 状态,确定两两状态间的最大目标值差:| Amax|,然后由式 t0= A max/lnpr,其中 pr 为初始接受
3、概率(理论上应接近 1,实 际设计时也可以取)。初始状态可采用启 发式算法(如2opt方法)快速得到一个解, 并以此为 SA 的初始状态。IIIIIIIIIIII5)退温函数的设计:指数退温函数 是最常用的退温策略(tk=入tk1 ,入为退 温速率)。6)温度修改准则和算法终止准则的设计:可采用阈值法设计的”温度修改” 和”算法终止”两准则。禁忌搜索算法 基于禁忌搜索算法的一般设计原则, 对典型的组合优化问题TSP,其算法可以 按如下方案实现:1) 初始解:可随机产生也可基于问 题信息借助一些启发式方法产生以保证一定的初始性能。2) 邻域结构:常用方法是互换(SWAP)、插入(INSERT)、逆序(INVERSE)等操作。3) 候选解的选择:通常取当前解的 邻域解集的一个子集作为候选解集,而取 其中的满足藐视准则或非禁忌的最优状 态为最佳候选解。4) 禁忌表及其长度:建议尝试自适 应长度法,譬如根据目标值更新的情况或 禁忌频率信息来适当增加或缩短禁忌表 长度。5) 藐视准则:采用若某个状态的性能优于” bestsofar”状态,则忽视其禁忌属性,直接选取它为当前状态。6)集中搜索和分散
4、搜索策略:分别 采用在一定步数的迭代后基于最佳状态 进行重新初始化并对其邻域进行多步趋 化性搜索和对算法的重新随机初始化或 是根据频率信息对一些已知对象进行惩 罚。7)终止条件:给定最优状态连续保持不变的最大持续迭代步数。大量研究表 明禁忌搜索算法具有模拟退火、遗传算法 等智能优化算法相当的性能,甚至更优 越。Hopfield 神经网络优化算法在用 Hopfield 网络求解优化问题之 前,必须将问题映射为相应的神经网络。 对 TSP 的求解,首先将问题的合法解映射为一个置换矩阵,并给出相应的能量函数,然后将满足置换矩阵要求的能量函数l=Jl=l的最小值与问题的最优解相对应。若以 X,I三l=lY表示城市,i表示第几次访问,dXY表示 城市间的距离, VXi 表示矩阵中的第 X 行 第 i 列的元素,则可构造出能量函数为: = E E +卡 E E E 叫几 +X /2 J X YHX刀刀卩阳亠厂+* g若工可匕冲+忖+ 1丿 网络的动态方程可表示为; 少七-簣計一i 十 tailD,缶丫f+i十#耳1丿vxt 仏 芯 J这是nXn个神经元状态方程的通用 表达式。为求得 TSP 的优化
《TSP的几种求解方法及其优缺点》由会员s9****2分享,可在线阅读,更多相关《TSP的几种求解方法及其优缺点》请在金锄头文库上搜索。
品康光波康复理疗仪
《生物入侵者》
物业电工管理制度与物业电梯的安全操作规程
公司行政事务管理制度
七年级英语下册 Unit 10 I’d like some noodles Section B第4课时导学案 人教新目标版
道路、排水、绿化、交通设施、照明工程施组方案
电子信息专业实习报告集合五篇
高考数学文大一轮复习检测:第六章 不等式、推理与证明 课时作业40 Word版含答案
二跨简支板桥施工组织设计方案和对策
教师的年度总结与评价标准范文(二篇).doc
【北师大版】七年级下册数学6.3等可能事件的概率第4课时教学设计
国税局副主任个人工作总结
2022年高一上学期第一次月考英语试题 Word版含答案
感动中考满分作文500字_20
监委会工作计划
幼儿教学学期总结范文锦集七篇
无手机课堂总结
企业应急预案的内容框架
8必修2原子核外电子排布与元素周期律
这儿真美小学作文11篇
2022-08-31 7页
2024-01-10 2页
2023-09-03 6页
2023-08-24 8页
2023-01-19 11页
2023-05-02 15页
2022-12-20 17页
2022-12-24 21页
2022-11-06 7页
2022-09-04 2页