基于遗传算法的最短路径研究与编程实践.docx

《基于遗传算法的最短路径研究与编程实践.docx》由会员分享，可在线阅读，更多相关《基于遗传算法的最短路径研究与编程实践.docx（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于遗传算法的最短路径研究与编程实践 摘 要最短路径问题的存储结构通常是采纳针对图论中的带权图的邻接矩阵。依据权的性质,这个问题的解可以是任何意义的最佳,如经济最省、时间最快、路程短、或者是其它意义上的“最优”。本文在最小成本计算、最佳地址选择等问题的基础上,同时进行了编程实践。 关键词 最短路径 遗传算法 编程 算法描述 一、遗传算法求解最短路径思路 遗传算法的基本思想是基于达尔文进化论和孟德尔的遗传变异理论的。遗传算法把问题的解表示成基因串,每一个基因串都是一个假设解。然后,把假设解置于问题空间(群体)中,以适应度函数(或日标函数)为依据,通过对个体施加遗传操作实现群体内个体结构重组的迭代

2、处理过程,最终收敛到最适应环境的个体上,它就是问题的最优解。遗传算法主要考虑六个要素:一是染色体编码,由于遗传算法不能干脆处理解空间的数据,因此必需通过编码将它们表示成遗传空间的基因型串结构数据。基本遗传算法运用固定长度的二进制符号串来表示群体中的个体,其等位基因是由二值符号集0,1组成;二是初始种群的生成,由于遗传算法的群体操作须要,所以进化起先前必需打算一个由若干初始解组成的初始群体;三是适应度评价,遗传算法在进化过程中一般不须要其它外部信息,仅用评价函数值来评估个体或解的优劣,并作为遗传操作的依据;四是遗传算子这个要素,基本遗传算法运用三种遗传算子:选择运算: 比例选择。选择运算的目的是

3、为了从当前群体中选出优良的个体,使它们有机会作为父代繁殖后代子孙。推断个体优劣的准则是个体的适应度值。选择运算模拟了达尔文适者生存、优胜劣汰原则,个体适应度越高,被选择的机会也就越多;交叉运算:单点交叉。交叉运算相当于生物进化过程中的有性繁殖的基因重组过程;变异运算:基本位变异。变异运算模拟了生物进化过程中的基因突变方法,将某个基因座上的基因变异为其等位基因;选择运算不产生新的个体,交叉运算和变异运算都产生新的个体,因此,选择运算完成的是复制操作,而交叉运算和变异运算则完成繁殖操作。五是遗传终止条件,终止条件就是遗传进化结束的条件。基本遗传算法的终止条件可以是最大进化代数或最优解所需满意的精度

4、;六是相关运行参数,基本遗传算法主要有群体规模、交叉概率PC、变异概率。 详细遗传算法的基本运算过程如下:设解空间为I,个体为Pi (1Vs) then begin TV:=MAX_INT; V:=MAX_INT; SV:=0; end; end; /考查Vs,Vk:=Vs; for L:=1 To N-1 do begin For m:=1 To N do / If Sm= 0 | WVk,m + then If TVmPVk+WVk,Vm Then begin TVm=PVk+WVk,Vm; (Vm)=Vk; End; / min:=MAX_INT; For Vj:=1 To N do b

5、egin If SVj 1 and minTVj then begin Min:=TVj; Vk:=Vj;/下一次考查的点 End; End; / If minMAX_INT then begin SVk:=1; PVk:=TVk; End; end; /Dijkstra算法到此结束. 最终用Delphi编写成算法软件,输入数值即可求解: 四、结论 通过上面的编程实践,初步找到了一种比较好的最短路径描述算法,即用遗传思想来描述算法,既简洁清晰,又使后面的编程实现变得简洁直观好用,再利用Delphi编程工具编成软件,使该算法在生产实际中的应用价值大大提高了。 参 考 文 献 1 运筹学教材编写组编.运筹学(修订版).清华高校出版社 2 林同曾编.运筹学.机械工业出版社 3 胡运权主编.运筹学基础及应用.哈尔滨工业高校出版社 第4页 共4页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页第 4 页 共 4 页