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

第１２卷第２期　２０１　３年２月　软件导刊　Ｓｏｆｔｗａｒｅ　Ｇｕｉｄｅ　ＶＯ１．１２ＮＯ．２　Ｆｅｂ．２０ｌ３　遗传算法求解ＴＳ　Ｐ问题的实现与改进　周春辉　，胡适军　，文元桥　（１．武汉理工大学航运学院，湖北武汉４３００７；２．浙江交通职业技术学院，浙江杭州３１ｌｌ１２）　摘　要：旅行商问题（Ｔｒａｖｅｌｉｎｇ　Ｓａｌｅｓｍａｎ　Ｐｒｏｂｌｅｍ，简称ＴＳＰ）已经被证明为ＮＰ难题。通过应用遗传算法求解ＴＳＰ　问题，给出了遗传算法中各算子的实现方法，并用遗传算法（Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ，简称ＧＡ）和穷举法分别求解了１５个　城市的ＴＳＰ问题，结果表明，遗传算法具有明显的优越性。引入模拟退火的思想对遗传算法的变异算子进行改进，并　求解了５Ｏ个城市的ＴＳＰ，得到了满意的结果。　关键词：遗传算法；ＴＳＰ；模拟退火　中图分类号：ＴＰ３１２　文献标识码：Ａ　文章编号：１６７２—７８００（２０１３）００２—００５５－０３　能够存活并参与繁殖下一代。如果参与繁殖的父体都很　０　引言　本文在分析遗传算法的基础之上求解ＴＳＰ问题，并　与穷举法所得结果进行比较，表明了遗传算法在求解此问　题上的优越性。针对遗传算法的不足，结合模拟退火思想　对遗传算法进行改进，取得了理想的试验结果。　“好”，意味着种群里面的差异小，则很有可能会陷入局部　最优。　１．２算法的详细设计　１．２．１　解空间的表示方式　遗传算法对解空间的表示大多采用二进制编码形　式，但是二进制编码方式不适合ＴＳＰ问题的解的表示，　因为它要求特殊的修补算子来修复变化算子所产生的非　法路径（即不可行路径）。给出城市编号，用十进制数编　码来表示解更合适，例如：近邻表示、次序表示和路径表　示等等。　这里采用了最简单的路径表示法，它是最自然、最接　近人类思维的表示法。例如，有６个城市的ＴＳＰ问题，可　将６个城市从１～６编号，下面的路径（闭合的）：　５　１　２　４・３　６　５　１　算法设计　ＴＳＰ问题的模型是简单而易于描述的。实际应用中，　像印刷电路板工艺这样的应用可能是和模型比较接近的。　但是模型中的城市之间的距离代表的是某个解的耗费，实　际中不一定是欧氏距离，有可能点与点之间的耗费需要另　外用权值给出。而且在实际中，两个城市之间的消耗不一　定是对称的，例如乘船到另一城市和返回的费用可能是不　同的。　表示从城市５出发，经过１，２，４，３，６最后回到城市５　的一条路径，可以自然地用一维数组来表示：　（５，１，２，４，３，６）　这里对ＴＳＰ问题模型进行简化，在５００×５００的平面　内随机生成了一些点，用它们来代表城市。假设每个城市　和其它任意一个城市之间都以欧氏距离直接相连。　１．１遗传算法的总体框架　相应地，５０个城市的ＴＳＰ问题，如果种群规模为　５００，解空间就用二维数组来表示：ｐａｔｈＥ５００￣Ｅ５ｏ］。　１．２．２种群初始化　遗传算法简单通用的特点，主要是指其主要框架简单　通用，可以说是万变不离其中。其基本结构可以概括为：　①初始化种群；②对种群每个个体进行评估；③选择（竞争　生存机会）；④变化（重组、杂交与变异）；⑤如不满足终止　种群的规模选择应适当，盲目地增大种群规模不能使　算法得到改进，反而大大增加了计算的开销。例如，２Ｏ个　城市ＴＳＰ与５Ｏ个城市的ＴＳＰ问题，２０个城市的ＴＳＰ问　题可以选择小规模的种群（例如５００），而５Ｏ个城市则要　选大一些的种群（例如３　０００）。　条件，转②；否则结束。　其中变化算子的设计是最重要的，既要考虑保留种群　在演化中产生的好的基因，又不能使种群过早地局限于某　个局部。其次是选择算子，选择策略意味着什么样的个体　以２Ｏ个城市为例，说明初始化种群的方法：种群初始　化时，先产生１，２，…，２Ｏ的一条规则路径，然后在这条路　径中随机选两个数，将它们交换位置，这样做若干次（本文　基金项目：国家自然科学基金项目（５１２７９１５１）；浙江省交通运输厅科技计划项目（２０１ｌＷ０４）　作者简介：周春辉（１９７８一），男，博士，武汉理工大学航运学院讲师，研究方向为海事信息系统与航海仿真。　・５６・　软件导刊　２０１３年　采用５００次），保证这条路径变成了一条随机的路径。　以这条随机路径为基础，对一些随机的位，做两两交　换（做１００次两两交换），这样产生了一个个体；同样地产　生种群里其它的个体。　１．２．３　适应度函数与最优解的保存　用个体（一条闭合路径）的周长（平面欧氏距离）作为　该个体的适应值。求得种群中所有个体的适应值后，将适　应值最大的个体保存起来，到演化完毕时，这个个体就是　最后要求的解。　１．２．４选择（竞争）策略　这里采用了轮盘选择策略。但是因为这是一个最小　化问题，必须对适应值做相应调整以适应这种选择策略。　可以采用一个映射对适应值进行规范：　Ｆ　一Ｆ…一Ｆ　（１）　其中，Ｆ是适应度函数求出的适应值，Ｆ…为其中的　最大值，Ｆ　是规范后的适应值。然后，用Ｆ　来构造轮盘，　概率为：　Ｐ［　］一Ｆ，［　］／　：Ｆ　［彳］　（２）　表示了某一个体被选人下一代的概率。对Ｐ做逐级　累加存人数组ＰＥｉ］：　Ｐ［Ｏ］一０　Ｐ［　］一Ｐ［ｉ一１］＋Ｆ，［　］　（３）　这个ＰＥＧ正是构造好的轮盘。最后产生一个（０，１）　之间的随机数ｒ模拟轮盘转动，检查这个值落在Ｐ［　］的　哪个区段，如Ｐ［愚］＜ｒ＜Ｐ［尼＋１］，则选取个体尼进入下一　代。如此循环，保持种群的规模不变。　１．２．５　杂交算子　杂交是希望不同的个体在产生下一代时，能够结合各　自的优势基因，产生更好质量的下一代。在遗传算法里　面，可以用单体杂交、双体杂交和多体杂交。但要保证种　群的规模不变，须保证”个个体杂交产生　个后代，后代　产生之后要代替其父体的位置。　常用的杂交算子有ＰＭＸ、ＯＸ、ＣＸ等，这几个算子细　节见文献［１］。本试验实现了ＯＸ算子，采用了双体杂交，　每次选两个个体杂交，产生两个后代。　１．２．６　变异算子　变异可以看作是外界对种群的影响。变异是为了引　入新的因素，希望个体在外界的作用下，能够自我优化，产　生好的基因。　变异算子采用了简单的倒序变换，以８个城市为例，　随机产生两个小于８的整数，对某个个体进行分割，将分　割段倒序并放回原来的位置即可。　（１，３，ｌ　４，６，５，２，８，ｌ　７）　（１，３，ｌ　８，２，５，６，４，ｌ　７）　由于这种变异算子仍能保持个体中的路径片段，即倒　序前后这个切割段的路径是一样的，只是两端点与整个路　径的连接颠倒了，这使得变异不是漫无边际，而是有所取　舍的。这种简单反序可以保证后代仍然是一条合法途径。　１．２．７模拟退火的基本思想　模拟退火算法来源于固体退火原理，将固体加温至充　分高，再让其徐徐冷却。加温时，固体内部粒子随温升变　为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个　温度都达到平衡态，最后在常温时达到基态，内能减为最　小。在遗传算法中，引入模拟退火的思想，在变异算子中，　让变异的父体和变异产生的后代之间竞争生存机会。在　演化的前期，种群的质量较差，因此给变异产生的后代较　多的生存机会（从１向１／２递减），而随着演化向末期推　进，将他们的生存机会减到平衡状态（各占１／２）。　变异产生的后代的生存概率表示为：　１一Ｇｒ／（２＊Ｇ　）　（４）　其中，Ｇ　是遗传算法要演化的总代数，　是当前演化　到第几代。这样，在初始时，Ｇ　为０，后代获得的生存机会　为１，类似于温度高、能量大；向后推进时，父辈与子女的　生存机会差距逐渐减小；最后趋于平衡。　１．２．８算法的流程　引入模拟退火思想对遗传算法进行改进，算法的流程　如图１所示。　图１算法的流程　２试验分析　所有的试验在一台奔腾４（主频为２．４Ｇ）的ＷＩＮ—　ＤＯＷＳ平台的ＰＣ机上进行，这个算法计算量大（耗　ＣＰｕ），但只占用较少的内存。　对于解的质量，首先使用１５个城市的ＴＳＰ问题进行　分析。由于２０个以上城市的ＴＳＰ问题用穷举法在短时　间内无法求得，因此这里选择了１５个城市来做了穷举搜　索的尝试。　使用穷举搜索法（Ｅｘｈａｕｓｔｉｖｅ　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ，简称　ＥＳＡ），１５个城市的ＴＳＰ问题用４ｍｌ５Ｓ求得了最优解。如　图２所示，长度是８７５．６８９　１４９，解路径是：０，９，１２，６，１，　１Ｏ，１１，５，３，１４，８，４，１３，２，７。　使用遗传算法来求１５个城市的ＴＳＰ，在几秒钟内就　可以求得结果，而且得到最优解的概率也很大。图３为使　用ＯＸ算子，种群规模５００，演化６００代，在１ｓ内求得和穷　举法同样的最优解的情形。解的路径长度为　８７５．６８９　１４９，由于路径是闭合的环路，出发点在哪里不影　响解的质量，所以这条路径和穷举搜索法求出的解是一样　的。通过大量的试验观察还发现，最优解和较好的次优解