基于遗传算法的最短路径问题及其MATLAB实现.docx

基于遗传算法的最短路径问题及其MATLAB实现.docx

ID:59073207

大小:433.53 KB

页数:2页

时间:2020-10-29

基于遗传算法的最短路径问题及其MATLAB实现.docx_第1页
基于遗传算法的最短路径问题及其MATLAB实现.docx_第2页
资源描述:

《基于遗传算法的最短路径问题及其MATLAB实现.docx》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、C特别企划OLUMNS基于遗传算法的最短路径问题及其MATLAB实现文/张书源郭聪前言法。根据生物进化过程中的选择机制,操作以及一条染色体的变异操作。在现实生活中,我们经常遇到最在问题的解空间中进行选择,实现“物评价与选择短路问题,例如寻找两点之间总长度最竞天择,适者生存”。在遗传算法中,对每条染色体计算其适应值,用短或者费用最低的路径。在运输、物一条染色体代表问题的一个可行解,该以评价染色体的优劣,从而从父代和子流、设施选址以及人员调度问题中,最染色体的适应值即为对应于该可行解的代中选择较优的染色体,进入下一代的短路径是很常见的问题。解决最短路问函数值。一般来说,遗传算法包括以

2、下繁殖。题的方法有很多,例如迪杰斯特拉算几个主要组成部分。初试种群的创建方法法、福特算法。在这里我们介绍基于遗编码其作为问题可行解的集合。初始传算法的最短路径问题的解决方案。即将问题的解表示成一个编码串种群中染色体个数称为种群规模。(染色体),每一染色体对应问题的一遗传算法的流程图如图1所示。模型个解。算法过程如下:遗传算法基本模型遗传过程第一步初始化种群p(t);遗传算法是模仿生物进化过程,对染色体进行操作,以产生新的第二步对种群进行评价;针对复杂问题开发出来的非常有效的方染色体,通常有不同染色体之间的交叉第三步利用交叉和变异重组p(t)以产生c(t)第四步评价c(t),从p(

3、t)和c(t)选择出p(t+1),令t=t+1;若达到繁殖代数,转第五步;否则,回第四步;第五步返回结果。问题描述在图2所示的算例中,我们要找到从节点①到节点⑨的最短路径。基于优先权的编码方式例如,一条可能的染色体如表1。路径生长路径生长即为根据一条染色体来得到其对应的一条路。在表1的例子中,路径生长的过程如下:初试路径上只有节点①;与①相连且不在当前路径上的节点有②和③,其中节点③的权较大,为6,将节点③加入当前路径,当前路径变为:①—③;与③相连且不在当前路径上的节图2点有④和⑤,其中节点⑤的权较大,为104TRANSPOWORLD2009No.12(Jun)5,将节点⑤加入

4、到当前路径中,当前3+5+2+2=12。路径变为①—③—⑤;遗传过程与⑤相连且不在当前路径上的节交叉算子:基于位置的杂交运点有⑥和⑧,其中节点⑧的权较大,为算。首先将所有染色体进行两两随机9,将节点⑧加入到当前路径中,当前配对,对每一对染色体,随机生成若干路径变为①—③—⑤—⑧;数字构成集合H,则子代1的获取方法与⑧相连且不在当前路径上的节为:在父代1上找到属于集合H中的数点有⑥和⑨,其中节点⑨的权较大,为字,让其保持不变,其余位置上的数8,将节点⑨加入到当前路径中,当前字用父代2上不属于H中的数字依次替路径变为①—③—⑤—⑧—⑨。代,从而得到子代1;子代2的获得方法至此,我们根

5、据染色体找到了一相同,如图3所示。条路径①—③—⑤—⑧—⑨,这条路径的长度为12。但是,需要注意的是,并不是根据优先权编码的染色体都对应一条路,例如表2染色体。路径生长过程如下:初试路径上只有节点①;与①相连且不在当前路径上的节点有②和③,其中节点②的权较大,为6,将节点②加入当前路径,当前路径变为:①—②;重复此过程,我们会找到路径①—②—④—⑥—⑤—③,已经没有与③相连且不在当前路径的节点,从而找不到从①到⑨的一条路。当出现这种情况时,我们抛弃这条染色体,用一条合法染色体去取代它。染色体的适应值染色体的适应值是我们选择较优染色体的依据。这里染色体的适应值即为我们得到的路径长度

6、。由于我们得到的路径为①—③—⑤—⑧—⑨,因此该染色体的适应值即为此路径的长度:变异算子:采用交换变异操作,随机选择染色体上两个位置,将他们的优先权进行交换,如图4所示。选择:根据每条染色体的适应值,从父代和子代中选择路径最短的n条染色体,作为父代,进入下一代繁殖,其中n为种群规模。结论将以上算法用matlab实现(程序见附录),我们找到对应于我们算例的最短路为:①—③—④—⑦—⑨,路径总长度为6。此外,不难发现,使用遗传算法来进行全局寻优,基本上不需要关于问题本身的信息,这使得遗传算法的应用可以扩展到模拟技术、非线性规划问题等领域,具有广阔的前景。作者单位:张书源——上海电视

7、大学郭聪——上海财经大学物流管理专业2009年第12期(6月下)《交通世界》105

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。