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

《遗传算法求解tsp问题的具体方法及其时间复杂性研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遗传算法求解TSP问题的具体方法及其时间复杂性研究邢冲(上海交通大学计算机系学号5010339138)摘要：首先介绍遗传算法解决TSP问题的基因表示方法以及相应的几种交叉变异方法。然后研究不同的方法与参数设置对于路径最优解，路径平均值以及所用处理器时间的影响，主要研究方向是在尽可能短的时间内求出TSP问题的次优解。得出结论：使用路径基因表示法，选择较大的变异率（0.3左右），使用倒置变异算法进行求解，能够得到较好的次优值（处理器时间：2000，100个城市，大致可以达到相距最优值1%-2%的效果），同时速度比较快。此研究针对那些只需次优解，但对时间要求比较高的问题有一定指导意

2、义。关键字:遗传算法TSP联赛排序次优解时间复杂度引言：TSP(TravellingSalesmanProblem)是一个著名的NP组合优化问题.旅行商需要以尽可能少的路程遍历所有城市,回到出发点.TSP具有很大的广泛性,无论是城市交通问题,航空问题,还是集成电路制造问题都需要解决相应的TSP问题.对于TSP问题,穷举的时间复杂度为N!(N为城市数量),随着N增加时间以指数级增加,对于如今的硬件技术这样的时间复杂度是难以接受的.而利用遗传算法(GA)求解TSP是个不错的选择.GA是一种模拟生命进化的算法;它利用适者生存的进化原则,通过演化逐步逼近问题的最优解.本文将讨论使用G

3、A求解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)这样的子代结果显然是不符合

4、TSP问题要求的，而且这样方法使得不合理基因在子代中占绝对优势比例，为了解决这一问题，尝试以下两种方法：l改变基因编码，使用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)就可表示一条巡回路

5、线。[1]这样编码交叉得出的就是合理基因，变异时只要保证gi

6、。特点：保留相对访问顺序。3.CX(CycleCrossover)主要思想：两个父代之间可能组成一些不相交的循环回路，交换其中几个循环回路的城市编码就可产生新的基因。特点：保留城市的绝对位置。变异方法：1.倒置：选择基因中的两个位置，颠倒两个位置中间的字串如（0123

7、456

8、789）倒置结果：（0123

9、654

10、789）2.交换：交换两个随即位置处的基因。如（0123456789）交换结果：（随即位置1和5）：（0523416789）3.插入：随机选择一个城市插入一个随机位置。如（0123456789）插入结果：（随即选择位置4，随机插入位置8）：如（0123567849）

11、1.各种基因表示法的效果比较变异率:0.2群体规模:50选择算法:排序选择变异:路径编码使用倒置方法,而G法使用普通的随即改变一位的方法.(本实验的城市如无特殊说明,即为分布在9*9矩形定点的100个城市，城市之间的路径为平面上两点的直线距离，相邻两城市的发距离定义为一个单位)进化代10003000500010000PMX均值:121.8108.16106.6106.46最优值:118105.8104.5104.14处理器时间:925248639957758OX均值:120.05106.87106.46