文档介绍：重庆大学
硕士学位论文
关于旅行商问题的改进遗传算法
姓名:李玮
申请学位级别:硕士
专业:检测技术与自动化装置
指导教师:陈今润
20040508
要摘复办法——矩阵变异,在它的作用下,将存在的非法个体转化为合法个体,并扩提出了一种新的编码方式——矩阵编码,它比边编码更形象、直观地描述旅行商侍馐亲楹嫌呕煊蛑械囊桓龅湫臀侍猓婕扒蠖喔霰淞康暮数的最小值。虽然它陈述起来很简单,但求解却很困难,并且已经被证明是完全问题。但它确实广泛存在,且是诸多领域内出现的多种复杂问题的集中概括和简化形式。快速、有效地解决侍庥凶沤细叩睦砺垡庖搴褪导视τ眉壑担近代科学技术发展的显著特点之一是生命科学与工程技术的相互交叉、相互渗透和相互促进。本文根据侍獾奶氐愫偷鼻把芯壳榭觯∮靡糯惴ɡ炊它进行求解。论文首先介绍了遗传算法的原理及基本实现技术,并着重阐述了遗传算法的特性,再具体地针对传统遗传算法进行相应的改进。传统遗传算法在求解侍馐蓖ǔ2捎贸鞘写涡虮嗦敕ê捅弑嗦敕ā1疚象,比城市遍历编码法更稳定,并且更容易判断个体的合法性和计算其适应度。针对编码产生的大量非法个体,根据矩阵编码的特殊形式,提出了一种较好的修大了搜索空间,保证了个体的多样性,最终收敛到最优解。最后用进行仿真,实验结果表明,本文提出的改进遗传算法在寻优时间上优于传统的边编码的遗传算法,并且收敛到全局最优解的几率高。关键词:慕糯惴ǎ卣蟊嗦耄卣蠼徊妫卣蟊湟欤视Χ群就是本文提出的用改进遗传算法求解侍獾哪康摹中文摘要重庆大学硕士学位论文】
瑃瓸甌瑃.,琒,;甅.,,甌..:,甀琤甋,’..甀篺疭,,,
嘞令,为赋权完全图,,ā琻6サ慵珽为边集,∑.≤狪芼//∑~髀∑,然后回到出发点,求其最短行程,即寻找一条巡回路径卜甽,,⋯芼。,这里,旅行推销员问题Ⅲ蚣荰甅岢鲆岳矗岩鸶髁煊蛐矶嘌芯空叩男巳ぁK亲楹鲜е幸桓龉爬而又困难的问题,也是组合优化中研究最多的问题之一,但至今尚未彻底解决。其描述为:一推销员要到若干城市推销货物,从城市龇ⅲ溆喔鞒鞘幸沟孟铝心勘旰钚。型上式中3鞘泻牛≈翟到之间的自然数,,表示城市城市涞木嗬耄杂诙猿剖絋,有,瑃。用图论的语言描述为:在一个赋权完全图中,找出一个最小权的哈密顿圈。各顶点间距离诩褐琩琲,设边,.,谧钣怕废呱其它则氖P汀’可写成如下的线形规划形式∈,.<蟂中所含图亩サ愀鍪G懊媪礁鲈际馕蹲哦悦扛龆点而言,仅有一条边进和一条边出,后一条约束则保证了没有任何子回路解的产生。于是,满足上述约束条件的解构成了一条遍历所有顶点的哈密顿回路。重庆大学硕士学位论文蔞琷陃
挠τ煤图壑都是对称的,假设城市统鞘校涞木嗬胛0欤碙唬杂Φ氖峭悸壑的无向图;另一类是两个城市间的距离是非对称的,即幽≠杂Φ氖峭悸研究领域带来了生机,并指导了未来的工作。他领域都有着有趣的应用。一个经典的例子是如何安排机器在一块电路板或其他链式启发式样算法来优化整个电路链式狵加启发式算法的改进版可以解决各种各样的硬币收集问题,因为从问题对应到图的类型,侍饪梢苑殖闪嚼唷R焕嗍侨瘟礁龀鞘形实木嗬中的有向图:为了简单起见,我们在这里讨论的侍馐嵌猿频腡。许多关于墓ぷ鞑⒉皇怯捎τ弥苯油贫模且蛭猅为其他一般的各类算法提供了思想方法平台,而这些算法广泛地应用于各种离散优化问题:然而,这并不是说薹ㄔ谛矶嗔煊蛘业狡溆τ谩F涫担琓大量的直接应用给茏匀坏刈魑4罅康脑耸浜秃笄谟τ玫囊桓鲎游侍馓岢觥@纾涸谛G内如何安排校车路线接送学生的问题,因为它对二十世纪四十年代初一位研究南惹的研究提供了源动力,所以这个运输应用对凶重要的历史意义。从开始牡诙鲇τ冒ù幽车卦耸渑└璞傅搅硪个地方去检测土壤,。更多新近的应用包括电报公司中呼叫服务的时序安排,货舱中栈式起重机的路线安排,收邮包的卡车行车路线安排等等。虽然运输问题是钭匀坏挠τ茫捎谄淠P偷募虻バ裕沟肨在其物体上钻孔,其中需要钻的孔可以看成是各个城市,而旅行的费用就是钻头从一个孔移到下一个孔所花的时间,虽然钻孔的技术不断发展,但无论何时,只要钻机设备的移动时间在制造业的过程中占据显著的地位,诩跎俜延蒙暇桶缪了一个非常重要的角色。以下给出一些当前挠τ谩景疲半导体制造厂家使用恢种饕S糜诩扑鉚的程序代码的扫描链路。用来检测的扫描链路包含在一个芯片当中,它可以最小化时间或者能量的消耗。示意图如左:牧硪桓鲇τ檬窃谝桓龈ǖ那蛑校排收集投币式公用电话中的硬币。中单行道的存在以及城市交通中的其他问题使得从結的旅行费用和从絰的旅行费用相等的假设变的不切实际,所以需要改进来解决这些问题。示意图如左:重庆大学硕士学位论文髀
、有效地解决侍庥凶偶ǜ叩氖导视τ眉壑担簿