用遗传算法求解最短路径问题

《用遗传算法求解最短路径问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第19卷第3期合肥工业大学学报泊然科学版)Vbl.19附31996.9J()URNAIJOF卜IErEIUN’l、下RSllY()F刃叹俐叫()1灭)子YSePt.1996用遗传算法求解最短路径问题曹鲁寅罗斌钦明浩(安徽大学)(合肥工业大学),摘要文章应用遗传算法求解图论中的最短路径问题并提出了该算法在解决这一问题中的一些处理方法·使用该算法可以很快地求出一批最短路径集。文中最后给出了算法运行结果及总结。;;关键词最短路径遗传算法邻接矩阵0.5中图分类号157¹最短路径问题和遗传算法所谓最短路径问题就是在给定的起始点,,S到终止点的通路集合中寻求长度最小的,。通路这样的通路称为S

2、点到t点的最短路径,,在寻找最短路径问题上有时人们不仅要知道两个指定的顶点间的最短路径还需要知道某个顶点到其它任意顶点间的最短路径。用遗传算法解这类问题,没有太多的约束条,。件和有关解的限制因而可以很快地求出任意两点间的最短路径以及一批次短路径,.GerithjmGA)是新近遗传算法(netic灿go简写发展起来的一种模拟生命进化机制的,。.搜索和优化方法是把自然遗传学和计算机科学结合起来的优化方程1975年land在Ho其专著中指出了GA的概念和方法,因其有很强的解决问题的能力和广泛的适应性,因而近年来渗透到研究与工程的各个领域.取得了良好的效果。下面:介绍遗传算法的几个基本概

3、念.。(1)染色(o:体Chrmosome)在使用遗传算法时需要把问题的解编成一个适合的码子这种具有固定结构的符号串即是染色体.符号串的每一位代表一个基因。符号串的总位数称为染色体的长度。一个染色体就代表问题的一个解,每个染色体也被称为一个个体。a:,(2)群体(P叩ultion)每代所产生的染色体总数称为群体一个群体包含了该问题在这一代的一些解的集合。:,(3)适应度(Fitnes)对群体中每个染色体进行编码后每个个体对应一个具体问题,。,的解而每个解对应于一个函数值该函数值即适应函数就是衡量染色体对环境适应度,。的指标也是反映实际问题的目标函数:一一¹收稿日期一9960505

4、:第3期曹鲁寅等用遗传算法求解最短路径问题113,:在前代群体的基础上产生新一代群体的工作称为遗传操作基本的遗传操作有·:(1)选择(段lect)按一定的概率从上代群体中选择M对个体作为双亲直接拷贝到下,。一代染色体不发生变化。r:,,、(2)交叉(Cr二ve)对于选中进行繁殖的两个染色体XY以XY为双亲作交叉操作·从而产生两个后代X‘、丫。o:,(3)变异(Mutatin)对于选中的群体中的个体‘染色体)随机选取某一位进行取反运算.即将该染色体码反转。用遗传算法求解的过程是根据待解问题的参数集进行编码,随机产生一个种群·计算适应函数和选择率,进行选择、交叉、变异操作·如果满足迭

5、代收敛条件,此种群为最好个体·否则,对产生的新一代群体重新进行选择,交叉、变异、操作,循环往复直到满足条件。2求最短路径问题的遗传算法的表示与实现用遗传算法求解一个优化问题.就是对该优化问题存在许多解二.计算每个二对应的.,。。适应函数关优化的过程就是要寻找这样的端使得与之对应的f(二)最大或最小2.1最短路径问题的图论描述,....:VVv一v,求最短路径问题用图论术语描述如下在图仅由中表示顶点集合(跳,⋯,。)对.马).二.马).G·vj).G中的某一条边(v,相应地有一个数d(如果中不存在边气,,,,.则令d(vivj)一的如把d(vivj)认为是边(认马)的长度(也可认为

6、是边(:、:必的费用或。),则路的长度权定义为组成路的各条边的长度的总和,,。顶点vivj之间是否有边相连由邻接矩阵来决定:,尸vv邻接矩阵A对一个具有V个顶点条边的图G的邻接矩阵A~〔aij〕是一个又阶,,,,。方阵其中aij一1表示劝和vj邻接a,j一。表示劝和vj不相邻接(或i一j)2.2染色体编码,,对于一个给定的图模型将图中各顶点按顶点号自然排序然后按此顺序将每个待选,,,顶点作为染色体的一个基因当基因值为1时表示相应的顶点被选人该条路径中否则反之。此染色体中的基因排列顺序即为各顶点在此条通路中出现的先后顺序,染色体的长度应等于该图中的顶点个数。2.3适应函数f(i)二

7、,,,,,对具有个顶点的图已知各顶点(v.vj)的边长度d(劝vj)把vi到vjn间的一条通路劝;,:,,:针⋯vin的路径长度定义为适应函数,f(*)一贰、vir十1)艺,,对该优化问题就是要寻找解寿使f(寿)值最小2.4选择操作,,,选择作为交叉的双亲是根据前代染色体的适应函数值所确定的质量好的个体即从起点到终点路径长度短的个体被选中的概率较大。2.5交叉与变异操作114合肥工业大学学报(自然科学版)1996年第19卷(3),,将被选中的两个染色体进行交叉操作的过程是先产生一