net版遗传算法解TSP问题.DOC

摘要：本文借助于遗传算法给出了旅行销售员问题较优解的求解方法，并用C#语言实现。 1. 旅行销售员问题的描述和相关定理 　　为了方便讨论旅行销售员问题（Traveling Saleman Problem，简称TSP），先给出图论 中相关的一些定义： 定义1 经过图G的每个顶点正好一次的圈，称为G的哈密尔顿圈，简称H圈。 定义2 在加权图G=（V，E）中 （1）最小的H圈称为最佳H圈； （2）经过每个顶点至少一次且权最小的闭通路称为最佳销售员回路。 　　本文要解决的问题就是求加权图的最佳销售员回路。而最佳销售员回路的问题可以转化 为最佳H圈问题。 设给定加权图G=（V，E），用它构造以V为顶点集的完全图G′=（V，E′），其中E′中每条 边（x，y）的权等于图G中顶点x到顶点y的最短路径的长度，即 对任意∈E′，权 图论中相关定理如下： 定理1 加权图G的最佳销售员回路的长度和G′的最佳H圈的长度相同。 定理2 在加权完全图中最佳H圈问题是NPC问题。 　　根据定理1我们可以把任意加权图的旅行销售员问题转化为其加权完全图上的最佳H圈问 题。根据定理2我们知道对该问题寻找多项式时间算法是不现实的，我们只能构造一些启发式 近似算法来求得问题的较优解。 2. 旅行销售员问题的遗传算法实现 2.1 用Floyd-Warshall算法求图中任意两顶点的最短路径 　　Floyd-Warshall算法步骤： STEP0 k=0；对于所有节点i和j，令 （可以认为 ）， ； STEP1 k=k+1；对于所有顶点i和j，若 ，则令 ；否则令 ； STEP2 如果k==n，结束；否则转STEP1。 其中代号意义如下： : 图G的顶点数目 ：图G中顶点i到j的弧的权值 ：图G中顶点i到j中间经过前k个顶点的最短路径的长度 ：图G中顶点i到j中间经过前k个顶点的最短路径的前一个顶点的标号 显然， 就是顶点i到j的最短路径的长度。 注：这个算法由命名空间TSP下的Floyd类来实现。 2.2 遗传算子的选择 　　在本文中，编码方案我们采用可能是对一个旅行最自然的表达-路径表达。例如，一个旅 行 5-1-7-8-9-4-6-2-3 可以简单地被表达成 （5 1 7 8 9 4 6 2 3）。 遗传算法的运算步骤： { 随机初始化种群P（0），t=0； 计算P（0）中个体的适应度； while(不满足中止条件) { for(k=0；kN；k+=2) //设N能被2整除 { 随机从P（t）中产生两个父体交叉操作后产生两个后代； 把这两个后代加入中间群体P′（t）中； } 对中间群体P′（t）中的每个个体进行变异操作； 从P（t）和P′（t）中进行选择操作得到N个个体赋予新群体P（t+1）中； 计算P（t+1）中每个个体的适应度； t++； } } 根据实测结果，我们仅从众多的遗传算子中选择几个性能较好的算子。 2.2.1 交叉算子 　　采用由Davis提出OX算子-通过从一个亲体中挑选一个子序列旅行并保存另一个亲体的城 市相对次序来构造后代。例如，两个亲体（切割点以|标记） p1=? 2 3 | 4 5 6 7 | 8 9） p2=（4 5 2 | 1 8 7 6 | 9 3） 将按照下面的方式产生后代。首先，切割点之间的片段被拷贝到后代里： o1=（x x x | 4 5 6 7 | x x） o2=（x x x | 1 8 7 6 | x x） 为了得到o1，我们只需要移走p2中已在o1中的城市4、5、6和7后，得到 2-1-8-9-3 该序列顺次放在o1中： o1=（2 1 8 | 4 5 6 7 | 9 3） 相似地，我们可以得到另一个后代： o2=（2 3 4 | 1 8 7 6 | 5 9） OX交叉开拓了路径表达的一个特性，即城市的次序（不是它们的位置）是重要的，即两个旅 行 5-1-7-8-9-4-6-2-3 8-9-4-6-2-3-5-1-7 实际上是相同的。 注：本算子由命名空间TSP中的类Ga中的公共成员函数CrossOX()来实现。 2.2.2 变异算子 　　对于变异算子我们采用倒置变异。倒置变异是在染色体上随机地选择两点，将两点间的 子串反转。说明如下： 原个体：（1 2 3 4 5 6 7 8 9） 随机选择两点：（1 2 | 3 4 5 6 | 7 8 9） 倒置后的个体：（1 2 | 6 5 4 3 | 7 8 9） 注：本算子由命名空间TSP中的类Ga中的公共成员函数MutateReverse()来实现。 2.2.3 选择算子 　　对于选择算子我们采用锦标赛选择算子。选择时，选随机地在群体中选择k个个体进行比 较，适应度最好的个体将被选择复制到下一代，参数k称为竞赛规模，常取k=2。 注：本算子由命名空间TSP中的类Ga中