TRANSPOWORLD 2009 No.12
(Jun)
104前言
在现实生活中，我们经常遇到最短路问题，例如寻找两点之间总长度最短或者费用最低的路径。

在运输、物流、设施选址以及人员调度问题中，最短路径是很常见的问题。

解决最短路问题的方法有很多，例如迪杰斯特拉算法、福特算法。

在这里我们介绍基于遗传算法的最短路径问题的解决方案。

模型
遗传算法基本模型
遗传算法是模仿生物进化过程，针对复杂问题开发出来的非常有效的方
基于遗传算法的最短路径问题及其MATLAB 实现
文/张书源 郭 聪
法。

根据生物进化过程中的选择机制，在问题的解空间中进行选择，实现“物竞天择，适者生存”。

在遗传算法中，一条染色体代表问题的一个可行解，该染色体的适应值即为对应于该可行解的函数值。

一般来说，遗传算法包括以下几个主要组成部分。

编码
即将问题的解表示成一个编码串（染色体），每一染色体对应问题的一
个解。

遗传过程
对染色体进行操作，以产生新的染色体，通常有不同染色体之间的交叉
操作以及一条染色体的变异操作。

评价与选择
对每条染色体计算其适应值，用以评价染色体的优劣，从而从父代和子代中选择较优的染色体，进入下一代的繁殖。

初试种群的创建方法
其作为问题可行解的集合。

初始种群中染色体个数称为种群规模。

遗传算法的流程图如图1所示。

算法过程如下:
第一步初始化种群p(t)；第二步对种群进行评价；
第三步利用交叉和变异重组p(t)以产生c(t)
第四步评价c(t)，从p(t)和c(t)选择出p(t+1)，令t=t+1；若达到繁殖代数，转第五步；否则，回第四步；
第五步返回结果。

问题描述
在图2所示的算例中，我们要找到从节点①到节点⑨的最短路径。

基于优先权的编码方式
例如，一条可能的染色体如表1。

路径生长
路径生长即为根据一条染色体来得到其对应的一条路。

在表1的例子中，路径生长的过程如下：
初试路径上只有节点①； 与①相连且不在当前路径上的节点有②和③，其中节点③的权较大，为6，将节点③加入当前路径，当前路径变为：①—③；
与③相连且不在当前路径上的节
点有④和⑤，其中节点⑤的权较大，为
图2
C
OLUMNS
特别企划
105
2009年第12期 《交通世界》(6月下)5，将节点⑤加入到当前路径中，当前路径变为①—③—⑤；
与⑤相连且不在当前路径上的节点有⑥和⑧，其中节点⑧的权较大，为9，将节点⑧加入到当前路径中，当前路径变为①—③—⑤—⑧；
与⑧相连且不在当前路径上的节点有⑥和⑨，其中节点⑨的权较大，为8，将节点⑨加入到当前路径中，当前路径变为①—③—⑤—⑧—⑨。

至此，我们根据染色体找到了一条路径①—③—⑤—⑧—⑨，这条路径的长度为12。

但是，需要注意的是，并不是根据优先权编码的染色体都对应一条路，例如表2染色体。

路径生长过程如下： 初试路径上只有节点①； 与①相连且不在当前路径上的节点有②和③，其中节点②的权较大，为6，将节点②加入当前路径，当前路径变为：①—②；
重复此过程，我们会找到路径①—②—④—⑥—⑤—③，已经没有与③相连且不在当前路径的节点，从而找不到从①到⑨的一条路。

当出现这种情况时，我们抛弃这条染色体，用一条合法染色体去取代它。

染色体的适应值
染色体的适应值是我们选择较优染色体的依据。

这里染色体的适应值即为我们得到的路径长度。

由于我们得到的路径为①—③—⑤—⑧—⑨，因此该染色体的适应值即为此路径的长度：
3+5+2+2=12。

遗传过程
交叉算子：基于位置的杂交运算。

首先将所有染色体进行两两随机配对，对每一对染色体，随机生成若干数字构成集合H，则子代1的获取方法为：在父代1上找到属于集合H中的数字，让其保持不变，其余位置上的数字用父代2上不属于H中的数字依次替代，从而得到子代1；子代2的获得方法相同，如图3所示。

变异算子：采用交换变异操作，随机选择染色体上两个位置，将他们的优先权进行交换，如图4所示。

选择：根据每条染色体的适应值，从父代和子代中选择路径最短的n条染色体，作为父代，进入下一代繁殖，其中n为种群规模。

结论
将以上算法用matlab实现(程序见
附录)，我们找到对应于我们算例的最短路为：①—③—④—⑦—⑨，路径总长度为6。

此外，不难发现，使用遗传算法来进行全局寻优，基本上不需要关于问题本身的信息，这使得遗传算法的应用可以扩展到模拟技术、非线性规划问题等领域，具有广阔的前景。

作者单位：张书源——上海电视大学
郭 聪——上海财经大学物流管理 专业。