智能算法的TSP算法求解文献综述

文献综述题目：智能算法的TSP算法求解文献综述学生姓名：系别：数学物理系专业年级：2012级信息与计算科学学号：20120702015年6月30日智能算法的TSP算法求解1简介TSP问题为组合优化中的经典问题，已经证明为一NP完全问题，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长，到目前为止不能找到一个多项式时间的有效算法。遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则。遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解。2基于遗传算法TSP算法2.1基于遗传算法的TSP算法总体框架TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都以欧氏距离，直接相连.遗传算法TSP问题的流程图如图1所示。.NY图1算法流程框架图实际问题参数集编码初始种群计算适应度选择适应度高的染色体变异交叉进化逆转新种群代数满足终止条件解决实际问题解码2.2算法的详细设计2.2.1解空间的表示方式遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP问题的解的表示，因为它要求特殊的修补算子来修复变化算子所产生的非法路径（即不可行路径）.给出城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等.这里采用了最简单的路径表示法.它是最自然、最接近人类思维的表示法。2.2.2种群初始化种群的规模选择应适当，盲目的增大种群规模不能使算法得到改进，反而大大增加了计算的开销。2.2.3适应度函数适应度表明个体或解的优劣性，不同的问题，适应度函数的定义方式也不同，优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质.求得种群中所有个体的适应值后，将适应值最大的个体保存起来，到演化完毕时，这个个体就是最后要求的最优解。3.2.4选择操作选择操作的目的是为了从当前群体中以一定的概率选择优良个体到新群体中，将选择算子作用于群体，从而使优化的个体有机会直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代；个体被选中的概率与适应度值有关，适应度值越大，被选中的概率也就越大，而适应度值越大的染色体越优质.本案例选择轮盘赌法，即基于适应度比例的选择策略，个体i被选中的概率为：1iiNjjFpF其中，iF为个体i的适应度值；N为种群个体数目。3.2.5交叉操作交叉操作是遗传算法中最主要的遗传操作，通过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特性，交叉体现了信息交换的思想．利用不同映射杂交，确定交叉操作的父代，将父代样本两两分组，每组重复以下过程：（1）产生两个[1，10]区间的随机整数1r和2r，确定两个位置，对两个位置的中间数据进行交叉，如14r，27r5124367981010623589417交叉为：*123589**1010*24367*1*（2）交叉后，对同一个个体中有重复的城市编号，不重复的数字保留，有冲突的数字（带*的位置）采用部分映射的方法消除冲突，即利用中间段的对应关系进行映射.结果为：4123589671010524367819交叉是希望不同的个体在产生下一代时，能够结合各自的优势基因，产生更好质量的下一代。3.2.6变异操作变异可以看作是外界对种群的影响.变异是为了引入新的因素，希望个体在外界的作用下，能够实现自我优化，生好的基因.将变异算子作用于群体。即是对群体中的个体串的某些基因位置上的基因值作变动。变异算子采用了简单的倒序变换，由于这种变异算子仍能保持个体中的路径片段，即倒序前后这个切割段的路径是一样的，只是两端点与整个路径的连接颠倒了，这使得变异不是漫无边际，而是有所取舍的。这种简单反序可以保证后代仍然是一条合法途径。3.2.7进化逆转操作为了改善遗传算法的局部搜索能力，在选择、交叉、变异之后引进连续多次的进化逆转操作，这里的“进化”是指逆转算子的单方向性，即只有经逆转后，适应度值有所提高的才接受下来，否则逆转无效。对每个个体进行交叉变异，然后代入适应度函数进行评估，x选择出适应值大的个体进行下一代交叉和变异以及进化逆转操作循环操作：判断是否满足设定的最大遗传代数MAXGEN，不满足则跳入适应度值计算；否则结束遗传操作。4遗传算法优缺点4.1遗传算法优点：（1）对可行解表示的广泛性，具有群体搜索特性，不需要辅助信息；（4）内在启发式随机搜索特性；（5）遗传算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的，非规则的或有噪音的情况下，也能以很大的概率找到全局最优解；（6）遗传算法具有固有的并行性和并行计算能力；（7）遗传算法具有可扩展性，易于同别的技术混合。4.2遗传算法缺点：（1）编码不规则或编码存在表示的不规则性；（2）单一的遗传算法编码不能全面的将优化问题的约束表示出来；（3）遗传算法通常的效率比比其他传统的优化方法低，容易出现过早收敛；（４）遗传算法对算法的精度，可信度，计算复杂性等方面，还没有有效的定量分析方法。6总结遗传算法利用自然界的“物竞天择、适者生存”的演化法则，把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法在搜索优秀解的过程中模拟生物遗传，实现优中选优的过程，在解空间中快速收敛到优秀解。遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能。参考文献[1]储理才.基于MATLAB的遗传算法程序设计及TSP问题求解[J].集美大学学报：2001，6（01）:14-19.[2]代桂平,王勇,侯亚荣.基于遗传算法的TSP问题求解算法及其系统[J].微计算机信息，2010（04）:15-16,19.[3]张春霞,王蕊.基于遗传算法求解TSP问题的算法设计[J].安阳工学院学报．2007.[4]李飞,白艳萍.用遗传算法求解旅行商问题[J].中北大学学报．2007.