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

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

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

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

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

4、操作，随机选择染色体上两个位置，将他们的优先权进行交换，如图4所示。选择：根据每条染色体的适应值，从父代和子代中选择路径最短的n条染色体，作为父代，进入下一代繁殖，其中n为种群规模。结论将以上算法用matlab实现(程序见5，将节点⑤加入到当前路径中，当前3+5+2+2=12。附录)，我们找到对应于我们算例的最路径变为①—③—⑤；遗传过程短路为：①—③—④—⑦—⑨，路径总与⑤相连且不在当前路径上的节交叉算子：基于位置的杂交运长度为6。点有⑥和⑧，其中节点⑧的权较大，为算。首先将所有染色体进行两两随机此外，不难发现，使用遗传算法9，将节点⑧加入到当前路径中，当前配对，对每一对染色体，

5、随机生成若干来进行全局寻优，基本上不需要关于问路径变为①—③—⑤—⑧；数字构成集合H，则子代1的获取方法题本身的信息，这使得遗传算法的应用与⑧相连且不在当前路径上的节为：在父代1上找到属于集合H中的数可以扩展到模拟技术、非线性规划问题点有⑥和⑨，其中节点⑨的权较大，为字，让其保持不变，其余位置上的数等领域，具有广阔的前景。8，将节点⑨加入到当前路径中，当前字用父代2上不属于H中的数字依次替作者单位：张书源——上海电视大学郭聪——上海财经大学物流管理路径变为①—③—⑤—⑧—⑨。代，从而得到子代1；子代2的获得方法专业至此，我们根据染色体找到了一相同，如图3所示。条路径①—③—⑤—⑧—

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

7、应值即为此路径的长度：2009年第12期(6月下)《交通世界》105