遗传算法求解TSP问题的具体方法及其时间复杂性研究

遗传算法求解TSP问题的具体方法及其时间复杂性研究邢冲(上海交通大学计算机系学号5010339138)摘要：首先介绍遗传算法解决TSP问题的基因表示方法以及相应的几种交叉变异方法。然后研究不同的方法与参数设置对于路径最优解，路径平均值以及所用处理器时间的影响，主要研究方向是在尽可能短的时间内求出TSP问题的次优解。得出结论：使用路径基因表示法，选择较大的变异率（0.3左右），使用倒置变异算法进行求解，能够得到较好的次优值（处理器时间：2000，100个城市，大致可以达到相距最优值1%-2%的效果），同时速度比较快。此研究针对那些只需次优解，但对时间要求比较高的问题有一定指导意义。关键字:遗传算法TSP联赛排序次优解时间复杂度引言：TSP(TravellingSalesmanProblem)是一个著名的NP组合优化问题.旅行商需要以尽可能少的路程遍历所有城市,回到出发点.TSP具有很大的广泛性,无论是城市交通问题,航空问题,还是集成电路制造问题都需要解决相应的TSP问题.对于TSP问题,穷举的时间复杂度为N!(N为城市数量),随着N增加时间以指数级增加,对于如今的硬件技术这样的时间复杂度是难以接受的.而利用遗传算法(GA)求解TSP是个不错的选择.GA是一种模拟生命进化的算法;它利用适者生存的进化原则,通过演化逐步逼近问题的最优解.本文将讨论使用GA求解TSP问题的各种具体方法和及其参数设置的影响.1.基因的表示方法TSP问题可以选择城市序列作为基因。首先对城市进行编号，比如10个城市0，1，……，9旅行序列：4-1-2-3-0-5-9-8-7-6则基因为（4，1，2，3，0，5，9，8，7，6）。这样的表示方法需要解决交叉的问题，普通的交叉方法会引起不合理的基因，比如父代一:(0,1,2,3,4,5,6,7,8,9)父代二:(9,8,7,1,2,3,4,5,6,0)子代的可能结果:(一点交叉,交叉位置假设5)(0,1,2,3,4,3,4,5,6,0)(9,8,7,1,2,5,6,7,8,9)这样的子代结果显然是不符合TSP问题要求的，而且这样方法使得不合理基因在子代中占绝对优势比例，为了解决这一问题，尝试以下两种方法：改变基因编码，使用Grefenstette等提出的一种新的巡回路线编码（以下简称G法）。编码描述如下：对于旅行商问题的城市列表W，假定对各个城市的一个访问顺序为T：T=(T1,T2...Tn)规定每访问完一个城市，就从城市列表W中将该城市去掉，则用第i(i=1,2,3...,n)个所访问的城市ti在所有未访问城市列表W-{t1,t2,...ti-1}中的对应位置序号gi(1=gi=n-i+1)就可表示具体访问哪个城市。G=(g1g2g3....gn)就可表示一条巡回路线。[1]这样编码交叉得出的就是合理基因，变异时只要保证gin-i得到的也将是合理基因。特点：父代交叉点之前的性状得到继承，交叉点之后的性状丢失。基因编码路径表达:就是上述提到的方法。现在通过改变交叉和变异方法来避免不合理基因的产生。交叉方法：1.PMX(PartiallyMatchedcrossover)。主要思想是首先按照两点交叉方法进行交换，然后根据两个基因交叉区域的映射关系，修改相应城市编号，使得子代基因合理化。特点：保留城市的绝对访问顺序。2.OX(OrderedCrossover)主要思想是从一个父代中挑选一个子序列并保存另一个父代其它城市的相应序列来构造子代。特点：保留相对访问顺序。3.CX(CycleCrossover)主要思想：两个父代之间可能组成一些不相交的循环回路，交换其中几个循环回路的城市编码就可产生新的基因。特点：保留城市的绝对位置。变异方法：1.倒置：选择基因中的两个位置，颠倒两个位置中间的字串如（0123|456|789）倒置结果：（0123|654|789）2.交换：交换两个随即位置处的基因。如（0123456789）交换结果：（随即位置1和5）：（0523416789）3.插入：随机选择一个城市插入一个随机位置。如（0123456789）插入结果：（随即选择位置4，随机插入位置8）：如（0123567849）2.各种基因表示法的效果比较变异率:0.2群体规模:50选择算法:排序选择变异:路径编码使用倒置方法,而G法使用普通的随即改变一位的方法.(本实验的城市如无特殊说明,即为分布在9*9矩形定点的100个城市，城市之间的路径为平面上两点的直线距离，相邻两城市的发距离定义为一个单位)进化代10003000500010000PMX均值:121.8108.16106.6106.46最优值:118105.8104.5104.14处理器时间:925248639957758OX均值:120.05106.87106.46105.79最优值:114.99104.9104.9103.13处理器时间:865235038197477CX均值:117.05107.42105.92105.13最优值:112.34104.97102.48104.14处理器时间:912248742228072G法均值:288.93273.39274.38277.37最优值:256.82251.02250.96247.72处理器时间:6010176022948656075从实验数据来看基因编码的路径表达无论从时间还是从最优值来看，都比G法好得多。从具体算法来看，G法在每次计算适应值时都需要对编码进行解码，比如：（2134321121）需要解码为城市序列：（1-0-4-6-5-3-2-7-9-8），这个过程时间较长，时间复杂度为O（群体规模*城市数量*城市数量），相比一般的路径表示法时间复杂度为O(群体规模*城市数量)，相差是十分明显的，实验结果也证实了这一点。从最优值与平均值来看，G法效果也比较差，10000代后离理论最优值相差超过100%，而其它路径表示基因的算法在10000代后离理论最优值相差4%。考虑一下算法思想，G法只继承了父代交叉点之前的性状，交叉点之后的性状完全丢失，导致结果较差。3.选择方法:联赛选择要优于排序选择.基于适应值的比例选择:也就是轮盘选择方案,这是一个使用比较普遍的选择方法,但是对于TSP的求解不太适合,因为一方面TSP求解的是最小值(最短路径),适应值需要转化（比例选择直接基于最大值问题）,同时当接近最优值时,路径相差很小,比例选择效果不好,要找到一个合理的转化函数将适应值的比例差距控制在有效的范围内非常困难.联赛选择(Tournament):确定一个联赛规模num,每次随即选择num数量个父代基因,选择出其中的最佳方案.排序选择(RankPower):对父代基因进行排序,然后利用排序结果名次(也可以是排序序列名次的幂次方)进行类似的轮盘选择.实验数据:参数:种群数量:50进化代数:2000变异率:0.5交叉算法:OX变异算法:倒置平均值最优值处理器时间RankPower(两次方)106.5104.14811Tournament(规模5)105.41103.31362参数:种群数量:50进化代数:5000变异率:0.5交叉算法:OX变异算法:倒置平均值最优值处理器时间RankPower(两次105.23103.352027方)Tournament(规模5)103.56101.65981参数:种群数量:50进化代数:10000变异率:0.5交叉算法:OX变异算法:倒置平均值最优值处理器时间RankPower(两次方)103.72101.654010Tournament(规模5)103.48101.651786从实验结果来看,RankPower与Tournament两种选择算法的收敛性相差无几,经过10000代,平均收敛值可以控制在误差3%,最佳收敛值控制在误差1.65%.但是其所用时间相差较大.联赛算法要大大优于排序选择算法.从时间复杂度上来看,(tournament:联赛规模.city_num:城市数量.n:种群规模(popsize).)Tournament选择算法的时间复杂度:O((tournamen_num+city_num)*n)RankPower由于必须排序,时间分为排序和选择两部分,若利用快速排序方法,时间复杂度为O(nlogn),则RankPower的时间复杂度:O(nlogn+n*city_num).(实验中使用的是冒泡排序,时间复杂性O(n^2));整个遗传算法各部分的时间复杂性如下：Init（初始化）:时间复杂度：O（n*city_num）,init只计算一次,对时间影响很小,可忽略.Fitness(求适应值):O(n*city_num)Crossover(交叉):O(n*city_num)Mutation(变异):O(n);从整个遗传过程来看,每一代进化排序选择时间较联赛长.如果群体规模比较大,那么差距将比较明显.4.变异方法的选择.参数,交叉:OX,选择:联赛,变异率:0.4,群体规模:50,1000代5000代10000代平均值最优值平均值最优值平均值最优值倒置108.74105.79105.30102.48104.22102.48交换158.16148.06143.14133.00137.79124.51插入247.36233.15163.99141.29140.88130.04变异方法对结果的影响从实验数据可以看出,倒置方法的效果要远比交换和插入好.5.变异率大小的选择100个城市分布在10*10方格顶点.(理论最优值100)参数:种群数量:50进化代数:3000交叉算法:OX选择算法:联赛变异算法:倒置变异率0.010.10.30.40.50.60.8平均值193.9109.8106.08105.38106.4114.08191.09最优值181105.8104.97102.48104.14111.34188.8变异率大小对结果的影响164个城市分布在8*8方格顶点.(理论最优值64)参数:种群数量:50进化代数:3000交叉算法:OX选择算法:联赛变异算法:倒置变异率0.010.10.30.40.50.60.8平均值90.2867.9366.9866.8966.5267.79101.38最优值83.3466.4864.8264.8264.8266.4897.77变异率大小对结果的影响264个城市分布在8*8方格顶点.(理论最优值64)参数:种群数量:50进化代数:100000交叉算法:OX选择算法:联赛变异算法:倒置变异率0.010.1平均值67.1465.90最优值65.6564.82变异率大小对结果的影响3实验结果表明当变异率在0.3--0.5之间,无论是最优值还是平均值都比较理想.一般遗传算法的变异率在0.001--0.1之间,然而实验结果表明0.001-0.1的变异率对于本问题显然不合适.如果变异率太小,收敛速度实在太慢,如果将变异率提高到0.3--0.5之间,时间上大大缩短,同时平均值和最优值也比较理想.结论:倘若问题是NP难解问题,因此发现最优旅行的多项式乘算法是不大可能的,更多注意力应放在只要求找到次优旅行的有效近似算法,快速算法.[2]本文研究了使用遗传算法解决TSP问题的几种方法及其参数设置,在保证得到次优解的前提下分析时间复杂度.对于TSP问题路径编码的方式较Grefenstette提出的巡回路线编码效果要好的多,在选择操作上使用联赛算法较排序选择算法快,变异方法使用倒置方法较其他方法好,同时变异率要相对大,选择0.3--0.5的变异率可以在保证达到较好的次优值的同时,使得收敛数度快.使用上述方法和参数，在2000处理器时间内，100个城市可以保持与最优值1-2%的差距，在300处理器时间内，与最优值保持5%左右的差距。这对于那些对时间要求比较高的组合优化问题有一定指导意义。参考文献：[1]周明孙树栋著遗传算法原理及应用国防工业出版社1999.6[2]z.米凯利维茨著周家驹何险峰译演化程序--遗传算法和数据编码的结合科学出版社200