改进的遗传算法求解TSP问题

1星(超过10%的资源)
所需积分/C币:34 2013-03-25 19:04:59 550KB PDF
56
收藏 收藏
举报

旅行商问题是一个NP 完全问题,目前任何NP 完全问题都不能用任何已知的 多项式算法求解;若任何一个NP 完全问题有多项式算法,则一切NP 完全问题都 有多项式算法。 由此,不少人猜测任何NP 完全问题都没有多项式算法,但至今无人证明。事 实上,人们普遍认为,不发展全新的数学技术就证明不了这个猜想。这样一种认 识的实际意义就在于许多人相信,难计算是这样一类问题的固有性质,因此它们 不可能用有效算法求解,而所有能精确求解NP 完全问题的算法,在最坏情况下都 需要指数级的时间。
3.1.3旅行商问题的扩展 旅行商问题的研究经过几|年发展,取得了一系列的成果。除了经典的旅行 商问题外,目前已引申出许多扩展形式,常见的有: ①最小哈密尔顿链的问题 这是起点和终点不同的旅行商问题,前面提到的许多算法都可略作修改,用 于求解该类问题。 ②瓶颈问题 日标函数为Max…,且i≠j∈G的旅行商问题 ③非对称旅行商问题 距离知阵非对称的旅行商问题。 ④多人旅行商问题 由多人完成环游的旅行尚问题。该问题可转换成等价的单人问题,只需将点1 改为m个虚拟点(,2,…m)其间用边连接,距离为充分大M∑∑c,各虚拟点 到j的距离c=c1,对新问题求解其旅行商问题后,从虚拟点门进入原网络再回到 虚拟点的那段路线即是m人中某一个的环游路线。 多目标旅行商问题 若各边弧上有m个权值,则使得哈密尔顿圈上相应的m个目标值都尽可能小 的解就称为多目标旅行商问题的( Pareto)有效解。如实际问题屮常常需要考虑:路 程最短、时间最少、费用最省、风险最小等等多方面的因素。由于多目标意义下 的所谓最优解是一种“折衷解”、“非劣解”,因此,多目标旅行商问题解的含义为 假定有一哈密尔顿圈的解H,若不存在任何其它回路解Q,使得 7(Q)≤Z(H),=12,…m,其中至少有一个不等式严格成立(为相应的日标函 数值),则H为 Pareto斛。 依次排序问题 这类问题是非对称旅行商问题,在给定的一系列顶点和距离矩阵下,寻找最 短从顶点1到顶点n哈密尔顿链,同吋满足限制:某些顶点要在另·些顶点之前 被连接。 ⑦载货量受限制的选径问题 给定n-1个顶点和一个仓库,已知顶点和顶点、顶点和仓库的距离。卡车的 载货量受限制,卡车每次在部分顶点和仓库之间往返,寻求一条经过所有顶点的 最短路线。 一般来说,这些扩展问题都有特殊的不同于对称型旅行商问题的求解方法, 但也可将它们转化成对称型旅行商问题求解 C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct 3.1.4研究旅行商问题的意义 旅行问题是一个NP完全问题,目前任何NP完全问题都不能用任何已知的 多项式算法求解;石任何一个NP完全问题有多项式算法,则一切NP完全问题都 有多项式算法。 由此,不少人猜测仁何NP完全问题都没有多项式算法,但至今无人证明。事 实上,人们普遍认为,不发展全新的数学技术就证明不了这个猜想。这样一种认 识的实际意义就在于许多人相信,难计算是这样一类问题的固有性质,因此它们 不可能用有效算法求解,而所有能精确求解NP完全问题的算法,在最坏情况下都 需要指数级的时间。 另外,旅行商问题是一个理想化的问题,大多数对于此问题的研究都不是为 了直接的实际应用,但这些研究可以经转化后用于许多现实的组合优化问题。很 自然地可以想到,旅行商问题的成果可以应用于运输和物流冋题。旅行商问题最 早的应用是在上个世纪的四|午代,应用于校车路线的优化。现在,旅行茼问题 在越来越多的领域得到应用。 电路板钻孔进度的安排。在这个应用当中,电路板上的孔代表旅行商问 题中的城市,钻头从一个钻孔移动到另一个钻孔。寻找最短路径变成了 寻找最省时的钻头移动时问。尽管目前钻机的工艺技术发展很块,但钻 头的移动时间仍然是一个令人头疼的问题。 ②基因测序。 Concorde是一种求解旅行商问题的程序。美国国家卫生机构 的研究人员利用这一程序来进行基因测序。在这一应用中,局部的基区 图谱作为城市,城市与城市的距离代表某张图谱与其它图谱相连的可能 性。研究人员试图寻找一种可能性最高的连接方式把这些局部的图谱合 成为整张基因图谱。 ③半导体的线路设计。一家半导体生产厂家应用 Concorde程序来优化半导 体的线路设计,这样可以节省刻制半导体的时间,也能减少半导体电路 消耗的能量。 ④光缆的线路设计。贝尔电话公司利用 Concorde程序米设计光缆的铺设线 路,同样的方法也应用于电话和电力线路的铺设当屮。 ⑤在机器人控制等其它方面,旅行商问题也有许多应用。 3.2旅行商问题的求解 3.2.1旅行商问题的精确解法 ①可解特殊旅行商问题的精桷算法 对于旅行商问题的一些特殊情况,业已研究出一系列非常完美的结果,如: C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct 机器排序问题等。由于可解情形的结果都是成熟的定理,因此严格来说口不属算 法研究的范畴 ②线性规划算法 这是求解旅行商问题的最早的一种算法,主要是采用整数规划中的割平面法, 即先求解模型屮由前二个约束构成的松驰线性规划问题,然后通过增加不等式约 束产生割平面,逐渐收敛到最优解。 Dantzig等人早在1954年就求解过n=42的旅行商问题最优解。70年代屮期 对于TS多面体理论的研究,产生了一些比较有效的不等式约束,如:子回路消去 不等式、梳子不等式等等。 日前,常用的方法是先用近似算法来求得近似解,再将此近似解作为下限, 用线性规划方法来精确求解或证明此下限为最优解。 ③动态规划算法 由于动态规划算法的时间复杂度为Omn2),空间复杂度为O(n2"),故除了 很小规模的问题外,几乎不予采用。 ④分支定界算法 分攴定界法是一种应用范围很广的搜索算法,它通过有效的约東界限米控制 搜索进程,使之能向着状态空间树上有最优解的分支推进,以便尽快找出一个最 优解。该方法的关键在于约東界限的选取,不同的约束界限,可形成不同的分支 定界法。 1)以分派问题为界 通过求解相应的分派问题,得到旅行商问题的一个下界,以此进行分支定界搜 索。这是一种使用较多的分支定界算法。 2)以匹配问题为界 通过求解相应的匹配问题,得到旅行商问题的一个下界,以此进行分支定界 搜索。该方法适用于对称型旅行商问题。 3)以最小权1生成树问题为界 通过求解相应的最小权1生成树问题,得到旅行商问题的一个下界,以此进 行分支定界搜索。在此基础上,Held和Karp(1970)曾将问题加以转换,得到更紧 的下界,有时甚至能将搜索树整个显示出来 虽说分支定界法对于较大规模的问题并不十分有效,可有时却被用来求解近 似解。而且,将分支定界法与一些启发式算法相结合,常常能获得一些意外的成 功 3.22旅行商问题的近似解法 由于精确式算法所能求解的问题规模非常有限,实际中使川的往往都是多项 C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct 式阶数的近似算法或启发式算法。算法的好坏用C/C≤E来衡量,C为近似算法 所得到的总行程,C*为最优总行程,E为最坏情况下,近似解与最优解的总行程 之比所不超过的上界值 ①插入型启发式算法 插入型算法可按插入规则的不同而分为若干类,其一般思想为∷ Step I通过某种插入方式选择插入边(,j)和插入点k,将k插入i和j之间, 形成{…,,k,,…}; Stcp2依次进行直至形成回路解。 适用范围:对称的三角型旅行商问题。 具体实施中,可以将出发点取遍V中各点而得到多个解,从中选择最好的 个,但此时的时间复杂度增加了n倍。常见的插入型算法有 1)最近插入法 最坏情况:E=2:时间复杂度:O(n2)。 2)最小插入法 最坏情况:E-2;时间复杂度:O(n2lnn) 3)任意插入法 最坏情况:E=21gn+0.16;时间复杂度:O(n 4)最远插入法 最坏情况:E=21gn+0.16;时间复杂度:O(n2) )凸核插入法 最坏情况:E一未知;时间复杂度:O(n2n) 最邻近算法 Step1任取一出发点 Sep2依次取最近的点加入当前解中直至形成回路解。 适用范围:对称的三角型旅行商问题。 具体实施中,可以将出发点取遍Ⅴ中各点而得到多个解,从中选择最好的 个,时间复杂度增加了n倍。但此时最坏情况:E=(gn+1)2;时间复杂度:O(n2) ③ Clark& Wright算法 Step l任取一出发点p,计算s=dn+dn-d; Step2将各s,由大到小排列; Stcp3将排好后的各配对顶点位}依次适当连接,形成回路解。 适川范围:对称的三角型旅行商问题。 具体实施中,可将出发点p取遍V中各点而得到多个解,从中选择最好的 个,但此时的时间复杂度增加了n倍。最坏情况:E-21gn7+5/21;时间复杂度: C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct ④双生成树启发式算法 Step l首先求出最小生成树 Step2将树中各边都添一重复边并求出其 Euler回路; Step3在 Euler回路点序列屮去除重复点,形成回路解 适用范围:对称的三角型旅行商问题。最坏情况:E=2;时问复杂度:O(n2)。 ⑤ Christofides算法 Stcp1首先求出最小生成树 Stcp2对树中所有奇项点解最小权匹配问题 Step3将匹配边添入生成树并求出其 Euler叫路; Step4在 Euler回路点序列中去除重复点,形成回路解。 适用范围对称的三角型旅行商问题。最坏情况:E=3/2:时问复杂度:O(n3) ⑥ropt算法 该方法是种局部改进搜索算法,由Lin等人(1965)提出。适用范围:对称型 旅行商问题。 Step1根据一定的规则求出每个顶点的候选顶点集,人为地规定该顶点只 能和候选集屮的顶点相连接 Step2产生初始路线; Step3对每一个顶点轮流进行ropt交换,直到无法改进当前解为止; Step4输出当前的解作为结果。 最坏情况:F-2(n≥8,r≤n/4);时间复杂度:O(n)。 合成算法 用某个近似算法求得初始鮮解,然后借助一个或若十个ropt算法对解加以改进。 这种合成型的算法往往能获得较好的解,但也很耗时,一般仪在对解有较高要求 时采用。 ⑧概率算法 该算法能对任意给定的E>0,在1+E之内几乎处处解决对称型旅行商问题。 假定G位于单位正方形内,函数tn)映射到正有理数,满足:a:t~log2(log2n); b:对所有n,n/t是完全平方。则有: Step1以r(n)/n]2为尺寸构成网格,将单位正方形分成n/t(n)个正方形,将 G也分成n/t(n)个子图; Step2用动态规划方法求解每个子图的最优回路 Step3将n/t(m)个子图各自收缩为一点,其间距离定义为原子图的最优子 路间最短距离,并对新构成的图求最小生成树T; C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct Step4将Tυ{各子图的最优子回路}视为一可能有点、边重复的闭回路,根 据三角形不等式条件,归约重复点或边,得旅行商问题回路。 适用范围:对称型旅行商问题 最坏情况:E=1+(任意给定正数);时间复杂度:O(nln)。 ⑨神经网络算法 八十年代屮后期,美、日等国家出现了一股神经网络热潮,许多从事脑科学 心理学、计算机科学以及电子学等方面的专家都在积极合作,开展这一领域的研 究。其早期思想源于四十年代,由于受 Von neuman串行处理体系的限制,一直 进展不大,直到八十年代,美国生物物理学家 Hopfield提出人工神经网络(ANN) 模型,才被认为是一个重大突破。 人工神经网终( Artificial neural network,ANN),也称为神经网络( Neural Networks,NN),是由大量处理单元即神经元( Neurons)互相连接而成的网络,通 过反映人脑的基本特性,对人脑进行抽象、简化和模拟的一种工程系统。人工神 经网络算法成为近年来的热点研究领域,涉及到电子科学与技术、电气工程、控 制科学与技术等诸多学科,其应用领域包括了健模、时间序列分析、模式识别和 控制等,并且仍然在不断扩展。 作为神经网络的基本单元,神经元模型具备三个基本要素。其一是具有一组 突触或连接,常用υ,表示神经元i和神经元j之间的联接强度,或称之为权值,取 值可在负值和正值之间;其二是具有反映生物神经元时空整合功能的输入信号累 加器;其三是具有一个激励函数用于限制神经元的输出 根据信息流向和网终的拓扑结构,可以将神经网终模型分成以下几大类: 1)前馈神经网终。2)反馈神经网终。3)随机神经网终。4)竞争神经网终 而 Hopfield和Tank(1985)用ANN方法求斛旅行商问题获得成功以来,更是引 起了极大的关注,国内也报导了求解数百个结点旅行问题的有关结果。方法的 思想是通过对神经网络引入适当的能量函数,使之与旅行商问题的目标函数相 致来确定神经元之间的连接权,随着网绺状态的变化,其能量不断减少,最后达 到平衡时,即收敛到一个局部最优解。目前,前述的几种神经网络都有在旅行商 问题商的应用实例,且取得了一定的成功,但还存在着严重缺点,而且就一般实 际问题而言,无法与其它近似算法相比。因此,该算法的适用范围很可能在于非 欧空间或不可度量的旅行商问题方面。 ⑩0模拟退火算法 这是一种源于五十年代、基于 Monte carlo迭代求解思想的随机搜索算法,八 十年代才开始应川于组合优化领域,其出发点是将组合优化问题与统计力学的热 平衡作类比,把优化的日标函数视作能量函数,模仿物理学中同体物质的退火处 C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct 理,先加温使之具有足够高的能量,然后再逐渐降温,其内部能量也相应下降, 在热平衡条件下,物体内部处于不同状态的概率服从 Boltzmann分布,若退火步骤 恰当,则最终会形成最低能量的基态。这种算法思想在求解优化问题时,不但接 受对目标函数(能量函数)有改进的状态,还以某种概率接受使目标函数恶化的状 态,从而可使之避免过早收敛到某个局部极值点,也正是这种概率性的扰动能够 使之跳岀局部极值点,故而得到的解常常很好。经典的模拟退火算法流程为 Step l选择初始状态H(初始解)、初始温度、降温次数; Stcp2生成H的邻域状态H',并计算Z(H)-z(H); Stcp3按接受概率置换H; Step4重复Step2直全停机条件满足。 模拟退火法所得解的好坏与初始状态、温度函数等都有一定的联系,降温较 快的效果不一定很好,效果好的,其降温过程又极其缓慢。但由于该方法适用氾 围广,并且可以人为控制迭代次薮,反复求解,因此具有很强的实用性。 ①遗传算法 它是种来自生物进化理论中“适者生存”的自然选择原则的搜索(寻优)算法, 它基于生物学的自然选择原理和自然遗传机制模拟生命的进化,这种新近发展起 来的完全异于传统思想的搜索和优化方法自 John holland等(1975)提出以来,获得 了广泛的应用。尤其是在人工智能领域,取得了极大的成功,对于许多复杂困难 问题的解决提供了强有力的处理办法。 遗传算法用于优化问题时,其最主要特征就是:它不在单点上寻优,而是从 整个种群( Population)中选择生命力强的个体产生新的种群;它使用随机转换原理 而不是确定性规则来工作。遗传算法中常用的遗传操作包括三个基本算子:复制 ( Reproduction)、交义( Crossover)、变异( lutation)。其中,繁媜算子用于从旧种群 生成新种群,交叉算子用于从父母代生成子代,变异算子用于对子代作某种变异。 这里,复制和交叉操作是遗传算法的有效性所在,但有时会丢失一些重要的遗传 信息,适当的变异操作可保证这些有用信息的引入。 ⑩其它算法 除了前面提及的一些典型的旅行商问题算法之外,还有其它许多方法可供使 用,如, norback等人(197)的几何图解法、极小代数算(1990)、归约算汯(1991)、 遗传退火法、蚂蚁算法等等。还有一种使用效果也相当不错的棼忌搜索法,它采 用了类似爬山法的移动原理,将最近若干步内所得到的解储存在禁忌列表中,从 而强制避免再次重复搜索表中的解,该方法在九十年代曾求解过几十万个顶点的 大型旅行商问题。 C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct 旅行商问题是经典的组合问题,在现实生活生产实践中有着广泛的应用。木 章先介绍了旅行商问题的定义、分类、扩展的形式、研究的难点和应用领域等, 然后介绍了旅行商问题的基本算法,其中重点介绍了目前最有发展潜力的神经网 络、遗传算法等。 C1994-2010chinaAcadcmicJOurnalElcctronicPublishingHousc.Allrightsrcscrved.http://www.cnki.nct

...展开详情
试读 11P 改进的遗传算法求解TSP问题
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
myyf9999 被标题骗了啊!所谓的改进的遗传算法呢?所谓的将大规模旅行商问题分为若干个城市群呢?我需要的是这么多传统的算法吗??
2020-06-09
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
上传资源赚钱or赚积分
最新推荐
改进的遗传算法求解TSP问题 34积分/C币 立即下载
1/11
改进的遗传算法求解TSP问题第1页
改进的遗传算法求解TSP问题第2页
改进的遗传算法求解TSP问题第3页

试读结束, 可继续读1页

34积分/C币 立即下载