文档介绍：2 0 0 6 . 1 2 计算机工程与应用 1 前言求解无向图中任意两节点间 k 条最优路径问题普遍存在于网络设计、城市规划、交通咨询系统等领域。图论中通常把两节点之间的最小权称为两节点之间的距离, 权可以是距离、数量、费用等。在实际应用中把求解两个指定节点之间具有最小权的路径称为最短路径问题。经典的狄克斯特拉( D i j k s t r a ) 算法[1 ] 是求解最短路径问题的常用方法。 D i j k s t r a 算法在求解最小权的过程中, 由于搜索了许多与最短路径无关的节点, 当节点和边的数量较多时, 显得效率不够高。后来人们利用所求解问题的特点, 通过减少搜索节点, 对 D i j k s t r a 算法进行改进, 提出了许多更有效的 D i j k s t r a 优化算法[2 ~ 4 ] 。在一些实际问题中, 不仅需要求解赋权图 G = ( V , E ) 上两点之间的最短路径, 还需要知道次最短, 次次最短等多条最优路径。比如, 在城市道路交通中, 根据出行的需要, 从所在地到目的地之间的各个线路中, 要知道多条最优线路以供选择。在一个网络中求出任意两点间最短路径及其多条最优路径的问题被称为 k 条最优路径问题。文献[ 4 ] 提出了一种先求图 G 的最短路径, 然后由图 G 生成子图集, 再对子图应用 D i j k s t r a 算法求解相应子图的最短路径, 这样不断进行, 从而构成求解图 G 的前 N 条最短路径的方法。由于 D i j k s t r a 算法的复杂度为 O ( n 2 ) 数量级, n 为节点数, 对于节点数和边数比较大的大规模图 G , 当 N 比较大时, 该算法所需计算机的时间资源与空间资源将急剧增加。遗传算法( G e n e t i c A l g o r i t h m s , G A ) 是基于生物的遗传和进化思想提出的计算模型[5 6 ] , 由于其隐含并行性和鲁棒性, 在复杂的非结构化问题的数值优化及组合优化等领域得到了广泛应用。遗传算法把问题可行解的空间, 映射成染色体集合的搜索空间; 然后通过染色体之间的交叉操作, 染色体基因的变异操作, 环境适应能力的选择操作等实现种群的遗传与进化; 把进化后种群中的最优染色体还原成问题的一个可行解作为问题的最优解。由于遗传算法的上述特性, 非常适合于求解 k 条最优路径问题。本文提出的遗传算法将染色体的编码设计成与节点的自然路径相同的形式, 在遗传算子中, 根据可连接节点实现路径块的交叉操作; 将数个可连接节点作为变异基因块, 进行变异操作。通过仿真实验验证了本文算法的有效性。 2 最短路径遗传算法应用遗传算法求解问题时, 必须首先通过编码把问题的一个可行解映射成一个字符串。本文把节点连接构成的路径表示形式设计成染色体的编码, 并设计了相应的交叉方法与变异方法。 2 . 1 染色体编码设无向离散图 G = ( V , E ) , V 表示节点的集合, E 表示边的集合, 各边赋予权值 C : E | → R + 。用自然数表示图的节点, 从初始节点 v 0 到目标节点 v t 的路径用所经过节点的顺序连接表示。图 1 是一个网络的拓扑结构示例, 设从节点 1 到节点 2 6 的一条路径为: 1 → 5 → 1 2 → 1 9 → 2 6 设