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

《基于遗传算法的最短路径问题及其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