搜索
1目录1引言........................................................................................................................22问题描述................................................................................................................23基于遗传算法TSP算法........................................................................................33.1基于遗传算法的TSP算法总体框架........................................................33.2算法的详细设计........................................................................................43.2.1解空间的表示方式.............................................................................53.2.2种群初始化.........................................................................................53.2.3适应度函数.........................................................................................53.2.4选择操作.............................................................................................63.2.5交叉操作.............................................................................................63.2.6变异操作.............................................................................................73.3实验结果分析............................................................................................74遗传算法优缺点.....................................................................................................85结语.........................................................................................................................9论文题目：基于遗传算法的TSP算法求解20大城市最短旅途论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以为给定20个城市制定最短旅途为例，利用基于遗传算法的TSP算法求解20个点的最短路线问题.本论文给出了遗传算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于java的实现机制．利用java软件编程，运行出结果，并对基于遗传算法的TSP算法结果描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优解.关键词：遗传算法；TSP；最短路径；21引言TSP问题为组合优化中的经典问题，已经证明为一NP完全问题，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长，到目前为止不能找到一个多项式时间的有效算法。TSP问题可描述为:已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短。TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义。本文中的TSP算法主要采用遗传算法。遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则。遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉以及等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解。2问题描述本案例为20个城市，分别为1-20，根据全程路径最短为目的，制定最优的顺序依次经过这20个城市。这类问题就由TSP算法来解决，寻找出一条最短遍历这20个城市的路径。随机给出20个城市坐标，下表为这20个城市的位置坐标如表2-1所示。3表2-120个城市的位置坐标城市编号X坐标Y坐标城市编号X坐标Y坐标160200111801002180200126080380180131208041401801418060520160152040610016016100407200160172004081401401820209401201960201010012020160203基于遗传算法TSP算法3.1基于遗传算法的TSP算法总体框架TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、变异操作设定、选择操作设定、交叉操作设定以及终止条件设定。为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都直接相连.遗传算法TSP问题的流程图如图2-1所示4开始随机产生初始种群执行选择操作执行交叉操作MutationRate0.015执行变异操作繁殖代数=100结束否是是否进化种群图2-1算法流程框架图3.2算法的详细设计53.2.1解空间的表示方式遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP问题的解的表示，要是给出城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等.这里采用了最简单的路径表示法。它是最自然、最接近人类思维的表示法.因此对20个城市依次编号为1-20。例如，下面的路径（闭合的）：10-4-2-8-1-7-6-20-16-17-13-11-18-15-14-19-12-9-5-3-10表示从城市10出发，经过1-20个城市最后回到城市10的一条路径，可以自然地用一维数组来表示：（10，4，2，8，1，7，6，20，16，17，13，11，18，15，14，19，12，9，5，3，10）20个旅游城市的TSP问题，如果将种群规模设为50，则解空间就用二维数组来表示：tour[50][20]。3.2.2种群初始化种群的规模选择应适当，盲目的增大种群规模不能使算法得到改进，反而大大增加了计算的开销.20个城市TSP问题，可以选择小规模的种群（例如50），种群初始化时，先产生1，2，…，20的一条规则路径，然后用Collections.shuffle将他们打乱顺序，保证这条路径变成了一条随机的路径，这样产生了一个个体；同样地产生种群里其它的个体.3.2.3适应度函数适应度表明个体或解的优劣性[10]，不同的问题，适应度函数的定义6方式也不同，若设K1、K2....K20为一个采用整数编码的染色体，适应度函数为恰好走遍20个城市，在回到出发城市的总距离的倒数。优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质。求得种群中所有个体的适应值后，将适应值最大的个体保存起来，到演化完毕时，这个个体就是最后要求的最优解。3.2.4选择操作选择操作的目的是为了从当前群体中以一定的概率选择优良个体到新群体中，将选择算子作用于群体，从而使优化的个体有机会直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代；个体被选中的概率与适应度值有关，适应度值越大，被选中的概率也就越大，而适应度值越大的染色体越优质。本案例中是先产生一个淘汰组，然后随机挑选若干个体加入淘汰组，在淘汰组中直接选择适应值最大的个体。3.2.5交叉操作交叉操作是遗传算法中最主要的遗传操作，通过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特性，交叉体现了信息交换的思想。利用不同映射杂交，确定交叉操作的父代，将父代样本两两分组，每组重复以下过程：Parents7先随机的选取Parent1的一部分，然后安装Parent2对应位置中，Parent2中的其他部分顺序不变，遗传下去Chlid这个交叉过程保证了城市的唯一性，避免了冲突。3.2.6变异操作变异可以看作是外界对种群的影响。变异是为了引入新的因素，希望个体在外界的作用下，能够实现自我优化，生好的基因。将变异算子作用于群体，即是对群体中的个体串的某些基因位置上的基因值作变动。变异算子采用了简单的倒序变换，以20城市为例，随机的产生两个小于20的整数，对某个个体进行分割，假设随机产生的两个整数位3和8，将分割段倒序并放回原来的位置即可，如下数组所示：由于这种变异算子仍能保持个体中的路径片段，即倒序前后这个切割段的路径是一样的，只是两端点与整个路径的连接颠倒了，这使得变异不是漫无边际，而是有所取舍的。这种简单反序可以保证后代仍然是一条合法途径。3.3实验结果分析8初始种群中的一个随机值:10-4-2-8-1-7-6-20-16-17-13-11-18-15-14-19-12-9-5-3-10总距离：1759优化后的最优解:3-4-2-7-6-10-8-11-14-17-20-13-16-19-18-15-12-9-5-1-3总距离：9484遗传算法优缺点遗传算法优点：（1）对可行解表示的广泛性；（2）群体搜索特性；（3）不需要辅助信息；（4）内在启发式随机搜索特性；（5）遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪音的情况下，也能以很大的概率找到全局最优解；（6）遗传算法具有固有的并行性和并行计算能力；（7）遗传算法具有可扩展性，易于同别的技术混合．遗传算法缺点：9（1）编码不规则或编码存在表示的不规则性；（2）单一的遗传算法编码不能全面的将优化问题的约束表示出来；（3）遗传算法通常的效率比比其他传统的优化方法低；（4）遗传算法容易出现过早收敛；（5）遗传算法对算法的精度，可信度，计算复杂性等方面，还没有有效的定量分析方法．5结语遗传算法利用自然界的“物竞天择、适者生存”的演化法则，把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体.实践证明，遗传算法在搜索优秀解的过程中模拟生物遗传，实现优中选优的过程，在解空间中快速收敛到优秀解。遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能.