用遗传算法解决旅行商问题

《用遗传算法解决旅行商问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、用遗传算法解决旅行商问题用遗传算法解决旅行商问题关键词：旅行商问题，遗传算法，交叉，变异，1.引言假如有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城的路径并且这条路径必须经过所有城市，不重复，且要求最短，那该如何呢？2.问题概述所谓旅行商问题是最短路径问题就是在给定的起始点S到终止点T的通路集合中，寻求距离最小的通路，这样的通路成为S点到T点的最短路径。在寻找最短路径问题上，有时不仅要知道两个指定顶点间的最短路径，还需要知道某个顶点到其他任意顶点间的最短路径。用遗传算法解决这类问题，没有太多的约束条件和有关

2、解的限制，因而可以很快地求出任意两点间的最短路径。如图所示红点为城市。从某城市出发，一直到走完所有城市，要求是不重复，路径要求段。解决此问题要用遗传算法3．遗传算法1）遗传算法的介绍遗传算法是一种模拟生命进化机制的搜索和优化方法，是把自然遗传学和计算机科学结合起来的优化方程，有很强的解决问题的能力和广泛的适应性。其假设常描述为二进制位串，位串的含义依赖于具体应用。搜索合适的假设从若干初始假设的群体集合开始。当前种群成员通过模仿生物进化的方式来产生下一代群体，如随机变异和交叉。每一步，根据给定的适应度评估当前群体的假设，而后

3、使用概率方法选出适应度最高的假设作为产生下一代的种子。遗传算法的基本概念：（1）染色体：在使用遗传算法时，需要把问题的解编成一个适合的码子。这种具有固定结构的符号串既是染色体，符号串的每一位代表一个基因。符号串的总位数成为染色体的长度，一个染色体就代表问题的一个解，每个染色体也被称为一个个体。（2）群体：每代所产生的染色体总数成为群体，一个群体包含了该问题在这一代的一些解的集合。用遗传算法解决旅行商问题（3）适应度：对群体中每个染色体进行编码后，每个个体对应一个具体问题的解，而每个解对应于一个函数值。该函数值即适应函数，就

4、是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数基本的遗传操作有：（1）选择：按一定的概率从上代群体中选择M对个体作为双亲，直接拷贝到下一代，染色体不发生变化。（2）交叉：对于选中进行繁殖的两个染色体X，Y，以X，Y为双亲作交叉操作，从而产生两个后代X1，Y1.（3）变异：对于选中的群体中的个体（染色体），随机选取某一位进行取反运算，即将该染色体码翻转。用遗传算法求解的过程是根据待解决问题的参数集进行编码，随机产生一个种群，计算适应函数和选择率，进行选择、交叉、变异操作。如果满足收敛条件，此种群为最好个体，否则，

5、对产生的新一代群体重新进行选择、交叉、变异操作，循环往复直到满足条件。2）遗传算法原型：GA(Fitness,Fitness_threshold,p,r,m)Fitness:适应度评分函数,为给定假设赋予一个评估分数Fitness_threshold:指定终止判据的阈值p:群体中包含的假设数量r:每一步中通过交叉取代群体成员的比例m:变异率l初始化群体:P←随机产生的p个假设l评估:对于P中的每一个h,计算Fitness(h)l当[maxFitness(h)]

6、择:用概率方法选择P的(1-r)p个成员加入Ps.从P中选择假设hi的概率用下面公式计算:2.交叉:根据上面给出的,从P中按概率选择r(p/2)对假设.对于每对假设,应用交叉算子产生两个后代.把所有的后代加入Ps3.变异:使用均匀的概率从Ps中选择m%的成员.对于选出的每个成员,在它表示中随机选择一个为取反4.更新:P←Ps5.评估:对于P中的每个h计算Fitness(h)从P中返回适应度最高的假设4．问题分析旅行商问题要从图G的所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!

7、条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有n!个子集合(n!>O())。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。5．问题的遗传算法设计用遗传算法解决旅行商问题问题的图论描述•求最短路径问题，用图论术语描述如下：在图G(V,A)中，V表示顶点集合，V=(v1,v2,…,vn)•对G中的某一边(,)，相应的有一个数d(,)，如果G中不存在边(,)，则令d

8、(,)无穷大，如果把d(,)认为是边(,)的长度，则通路的长度定义为组成路的各条边的长度总和。•顶点,之间是否有边相连，由邻接矩阵来决定。•邻接矩阵A：对一个具有v个顶点，e条边的图G的邻接矩阵A=[]是一个v×v阶方阵，其中=1，表示和邻接，=0表示vi和vj不相邻接（或i=j）染色体编码对于一个给定