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

所需积分/C币:22 2014-05-05 22:42:14 247KB PDF

文章应用遗传算法求解图论 中的最短路径问题,并提出了该算法在解决这一问题 中的一些处理方法·使用该算法可以很快地求出一批最短路径集。文中最后给出了算法运行结果及总结。
114 合肥工业大学学报(自然科学版) 1996年第19卷(3) 将被选中的两个染色体进行交叉操作的过程是先产生一个随机数确定交叉点位于 染色体的第几位基因上然后在此位置进行部分基因交换。变异操作是将染色体中某位基 因逆变,即由1变为0,或反之变异的意义为在某条路径上去掉或增加某顶点,但这样做的 结果并不一定能使路径的长度减少。也就是说有可能使各代中产生的比较好的方案在遗 传过程中丢失迟缓了获得最优解的速度。 为了使算法尽可能快地获得更好的解·改善遗传算法的收敛性·在变异操作时增加 了个体求优的自学习过程。即在某位基因变异后计算新产生的染色体的适应函数值,若 适应函数值更小,即获得的路径更短则保留;否则保持原来的解不变。如果有连续N/3 次没有得到更好的解则该过程结束其中N表示从起点到终点的顶点数。 解最短路径问题的遗传算法如下 generate「Kc)]; evaluate [th)]; repeat noof Generations times Select p( h)form以n-1); Crossover and mutation *: j learning lf(2)] evaluate lt(: 1 )J end 其中:eect纵n)fomn-1)表小从 图!1个顶点加权有向图 前一代群体中选择一对双亲用于交叉变异操作。纵n)代表第n代群体。 generate [p(n)]表示在程序开始时要首先产生一个群体 evaluate I(n)]表示计算每个个体适应度 3算法实现与结果 3.1原始数据对解的影响 交叉率不可选择过小,否则,延缓获得最优解的过程,本题选择A=0.9。 变异率()的选择对规模大的优化问题影响很大,本题选A=0.009 群体中的个体数的选取是算法中一个很重要的参数群体中的个体数目越大算法就 越能找到更好的解。个体数目过小有可能找不到最优解。 3.2算例 (1)求图1中从1点到15点间的最短路径。图中v到v的数值代表两点间的路径长度 对该例用本算法求得的最短路径集为 →3→4→6→12→15 1→-2→11→13→15 1→2→11→13→14-15 1→3 13→15 1→3→4→1314→15; 第3期 曹鲁寅等:用遗传算法求解最短路径问题 115 最短路径的长度为14 (2)图2给出了60个顶点的例子 20253 27 54 12 Is 0 51 10 o1 2 --3-5 图260个顶点加权有向图 上图用坐标给出了60个顶点的位置,若两点vv之间有连线.则权值dv,v)取两点 间的距离;否则d(v,v)取一个大数。求解过程中,迭代次数与计算结果关系见表1。 对图2,求得的最短路径为: 1→4→14-35→49→57-60 最短路径长度为12.936 表1退传算法优化过程 遗传算法在最初几次迭代选代次数路 径盾应函数 中,个体的出现是良莠并存的,个 1→2→3→4→14→17→19→22→24→26→27 1100.04 体的适应度也不高,随着迭代次 →36→40-4849~5157→60 数的增加适应度高的个体将被 81→4→10→16→41→56-60 205.890 遗传出来。表1中的结果也说明了 121→13~18→29→40→48-57→60 这点 171→4→14→35→49-57→60 12.936 4总结 通过用遗传算法解题,可知 遗传算法明显的优点:(1)算法是使用参数的编码集参数的选择十分方便;(2)遗传算法是 在点详中寻优;(3)它仅使用问题本身所具有的目标数据进行工作,而不需其它任何先决 条件或辅助信息;(4)它使用的是随机规则 116 合肥工业大学学报(自然科学版 1996年第19卷(3) 本文是遗传算法一个应用·在用该算法解题时,增加了个体的自学习过程因而克服 了简单的遗传算法存在的收效速度慢的缺点改善了算法的收敛性,目前,对GA的理论 研充还在深入,应用领域也在不断地开拓,相信用遗传算法解决的问题将越来越多。 参考文献 「美E米涅卡·网络和图的优化算法中国铁道出版社.198 Thavil B Fogel. An Introduction to Simulated Evlutionary ()timization IEFE Trans. Neural Networks. 1994.5(1) 3 Q Xiaofeng. Palmieri Francesco. Theoretical Analysis of Evolutionary Algorithms wi ii aIM Infinite Population Size in Continuous Space. Part I basis properties IEEE Tian:. Neural Networks. 1994.5(1) 陈根社·陈新海.遗传算法鸬研与谁展.信息与控制.19:、22÷) A GENETIC ALGORITHM FOR FINDING SHORTEST PATHS Cass laryn JaN) &n Ong Mi L r Anhui Univcrsry) Hfc Univer sty of Technolog) Abstract This paper presents the application of genetic algorithm to finding the shortest paths in a graph. A number of issues of genetic algorithm for solving this problem are presented. A series of shortest paths can be obtained quickly by using this algorithm At the end of this pa per. the calculation resultes of the algorithm and the conclusion are shown Key Worls ut'tic algorithm, shortest paths, adjacency matrix 姓名曾鲁安出生于1963年4月1987年毕业 于安徵大学电子系学位硕士职称讲师 主要研究方向ⅥSI计算机铺助设计 联系地址安徴大学电子系邮编230039 (本文责任编辑涂捷)

...展开详情
试读 5P 用遗传算法求解最短路径问题
img
zh1234qwer

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    用遗传算法求解最短路径问题 22积分/C币 立即下载
    1/5
    用遗传算法求解最短路径问题第1页
    用遗传算法求解最短路径问题第2页

    试读已结束,剩余3页未读...

    22积分/C币 立即下载 >