遗传算法与神经网络最短路径 1

(唐立新 ,1998 ) ; 本文提出了一种全新的插入式交
2 遗传算法求解最短路径
遗传算法是通过对群体中的多个个体的迭代 搜索来逐步找出问题的最优解 ,它的操作对象是对 解空间中解的编码串 ,其迭代运算是由其遗传算子 来实现的 。遗传算法的基本要素有三个 : 编码方 式、 遗传算子 、 适应度函数 。其中编码是将问题的 解转换成编码串的方式来模拟生物的染色体进行 遗传运算 ; 算子是一系列操作的集合 , 模拟个体的 生存环境 ; 适应度函数是评价个体生存能力的准则 度量函数 。除了三个基本要素之外 ,遗传算法还涉 及到控制其要素作用度的几个参数 , 即群体大小 、 交叉概率 、 变异概率 、 遗传代数等 。有关遗传算法 的详细理论和运算过程参见文献 ( 周明等 ,1999) 。 遗传算法求解最短路径 ,首先要将路径表达成 编码串的方式 , 再设计相关的选择 、 交叉和变异算 子 ,以及适应度函数 , 本文就这几个方面作详细的 论述 。 2. 1 遗传编码 遗传算法的编码将待求问题的解的形式变换 成遗传算法所面对的基本编码串对象 ,以便于遗传 运算 。对于最短路径问题 ,其可行解的形式一般为 结点下标连接成的数字串 ,因此在遗传算法中的个 体编码方式一般为符号编码 。具体可以分为以下 几种 : 近邻编码 、 序编码 ( Grefenstette 编码) 、 边编码 、 自然编码等 ( 周明等 ,1999) 。本文在对比序编码和 自然编码后 ,选用自然编码方案来进行最短路径的 算法设计 。考虑到路径存在变长的情况 ,故在自然 编码设计时将采用等长可变染色体的方式 。若点
© 1995-2004 Tsinghua TongfBiblioteka Baidung Optical Disc Co., Ltd. All rights reserved.
第 2 期 徐琼等 : 基于遗传算法最短路径问题的探讨
169
(2) 求给定点 P0到图 G 中其余各点之间的最
min Σ A i 3 Ei
i =1
n
s . t . A i ∈A Ei ∈E
最短路径问题的存储结构通常是采用针对图 论中的带权图的邻接矩阵 ,如图 1 所示 。而 GIS 中 最短路径分析则通常针对的是带权图 ( 网 ) 。根据 权的性质 , 这个问题的解可以是任何意义的最佳 , 如经济最省 、 时间最快 、 路程短 、 或者是其它意义上 ( 王正志等 , 的 “最优” ,因此也有文献涵盖为 “最佳” 2000) 。最短路径分析是 GIS 网络分析的重要内容 之一 , 而且也是网络分析中诸如最小成本计算 、 最 佳地址选择等问题的基础 。在 GIS 中 , 这个问题有 着各种实用的意义 ,其中最为常见的是求网络图的 最短路径问题 。
叉算子 ( 简称为 IX 算子) 。在此加以详细介绍 。
IX 算子的基本思想 : 插入交叉是启发于传统 Dijstra 算法 ,就是计算在每两个顶点之间是否可以
插入一个顶点 ,使得路径的距离变短 。下面以 7 个 顶点的网络的邻接矩阵为例来说明设计原则 。网 络的邻接矩阵如表 1 所示 , 现在要求解 2 到 7 之间 的最短路径 。
第 26 卷 第2期 华 东 地 质 学 院 学 报 2003 年 6 月 JOURNAL OF EAST CHINA GEOLOGICAL INSTITUTE
Vol126 No12 Jun. 2003
基于遗传算法最短路径问题的探讨
徐 琼 陈荣清 官云兰 陶国强
b 。最短路径问题本质上是一个求最小值的问题 。
k
IX 算子的设计步骤如下 。
步骤 1 : 判断在 ( 2 ,5) 之间是否可以插入 3 。因 为 ( 2 ,5) > ( 2 ,3) + ( 3 ,5) ,所以 ,在 ( 2 ,5) 之间可以插 入 3 ,则 p1 中删除 3 的基因座 。 o1 = ( 2 , 3 , 5 , 3 , 3 , 3 , 3 ) , p11 = ( 2 ,5 ,6 ,4 ,7 ,1) ; 步骤 2 : ( 5 ,6) < ( 5 ,4) + ( 4 ,6) ,在 ( 5 ,6) 之间不 能插入 4 ,则 o1 = ( 2 ,3 ,5 ,6 , 3 , 3 , 3 ) ; p12 = ( 2 ,5 ,6 ,4 ,7 ,1) ; 步骤 3 : 以此反复迭代 , 则得父代个体 p1 的子 代为 o1 = ( 2 ,3 ,6 ,5 ,4 ,7 ,1) ; 步骤 4 : 按此规律在 p2 中插入 p1 ,则可得父代 个体 p2 的子代为 o2 = ( 2 ,3 ,5 ,4 ,1 ,6 ,7) ; 运用 IX 算子所得的子代个体一般要优于其两 个父代个体 , 比较多的继承了两个父代个体的优 点 ,而且由于两个子代个体依据同一规律求得 , 所 以没有太大变异存在 , 收敛速度比较快 , 寻优性能 较佳 。 ( 3) 变异算子 路径问题中的变异算子是针对不同的编码方 式设计的 。对于 Grefenstette 编码方式可以用常规 的基本位变异 ,而对于那些采用基本位变异会产生 非法个体的编码方式 ,就要设计一些特定的变异算 子 。几个常用的变异算子有 : 倒位变异算子 、 交换 变异算子 、 插入变异算子 。本文中采用的是交换变 异算子 , 即随机选择两交换点 , 将两交换点之间的 编码串反转 。 除了上述三种基本算子之外 ,在求解最短路径 问题中为了赋予遗传算法一定的知识 ,经常设计一 些特别的算子以改善算法的性能 。在本文的实验 中还采用了剪切算子 。另外 ,在算子设计中运用了 最佳个体保存策略 ,即当产生新的群体中没有适应 度大于上一代群体最优个体适应度时 ,要保留一个 上一代的最优个体 。 2. 3 适应度计算 最短路径问题适应度计算不同于一般遗传算 法中的适应度计算 。由于在一条路径表达中相邻 两点之间可能没有直接连通 , 所以其距离为无穷 大 。因此 ,在计算适应度前应把个体进行整合 , 使
表1 网络邻接矩阵
Tab. 1 Adjacency matrix of network
0 2 3 5 9 8 2 3 0 6 6 7 3 0 5 1 0 2 2 4 1 9 4 8 0 3 6 4 7 6 4 4 0 2 6 1 7 6 3 3 0 7 6 9 9 6 4 5 9
设两个交叉个体为 : p1 = ( 2 ,5 ,6 ,3 ,4 ,7 ,1) ;
( 东华理工学院 ,江西 抚州 344000)
摘 要 : 对用遗传算法求解最短路径问题作了有益的尝试 ,详细分析了求解最佳路径的遗传算法的构成要素 , 提出了一种 新的交叉算子 ,并且论证了算法参数对结果的影响 。通过仿真实验 , 给出了算法的主要性能参数 , 证明了算法的可行性 , 并指出了遗传算法求解最短路径问题的不足之处 。 关键词 : 遗传算法 ; 最短路径分析 ; 遗传算子 ; 参数选择 中图分类号 :O236 文献标识码 :A 文章编号 :100022251 (2003) 022168205
1 GIS 最短路径分析
最短路径分析是 GIS 空间建模最具代表性的 问题之一 , 它涉及到组合优化 、 排列决策等问题 。 根据图论理论可知 : 设图 G 由非空点集合 V = { V 1 , V2 ,Λ V n} 和边集合 E = { e1 , e2 , Λ em } 组成 , 其中 ei =
( Pi1 , Pi2且 ei ∈E , 若 ( Pi1 , Pi2 ) ≠( Pi2 , Pi1 ) , 则 G 为
图1 带权图 ( 网) 及其邻接矩阵
Fig. 1 Adjacency matrix and network with weights
一个有向图 ; 又设 ei 的值为 ai , A = { a1 , a2 , Λam } , 故 G 可表示为一个三元组 : G = { P , E , A} 则求最短路径的数学模型可以描述为 :
短路径 ,即常说的单源最短路径问题 。 (3) 求图 G 中每两个顶点对之间的最短路径 , 即多源最短路径问题 。 最短路径分析问题是一个典型的组合优化问 题 ,且是一个 NP 难题 。其可能的路径数目随顶点 数目的增加成指数增长 。当前许多算法是针对第 二种和第三种提法求解的 ,这些算法基本上是基于 经典的 Dijstra 算法和 Floyd 算法 , 并附以某一领域 特定知识构造而成 。而对于第一种提法目前尚无 可行的算法 。这种算法的详细实现过程在相关的 文献资料中都可以找到 ,本文不再赘述 。这里将详 细探讨利用遗传算法的理论来设计解决这一问题 的算法 。
收稿日期 :2003203224
传统上最短路径通常有以下三种提法 : (1) 求出给定的两点之间的最短路径 , 看似最 简单的一种 。
基金项目 :国家重点实验室开放基金资助项目 (010302) ,江西省教育厅资助项目 (204020)
) ,女 ,助理工程师 ,主要从事实验室技术管理 。 作者简介 :徐 琼 (1969 —
其相邻两点间直接相通的点尽量排在染色体的前 段 ,使其成为合法的个体 。 对于最短路径问题 , 设网络邻接矩阵为 P , 个 体为 X , 求 a 到 b 的最短路径 , 则数学描述为 :路径 长度 Ci = ∑P ( x i , x i + 1) , 其中 x 1 , x i + 1 ∈X , X ( k ) = i =1
遗传算法是基于生物进化原理的一种全局性 优化算法 ,是借鉴生物的自然选择和遗传进化机制 而开发出的一种全局优化自适应概率搜索算法 ,是 生物遗传技术和计算机技术结合的产物 ( 周明等 , 1999) 。它采用的是启发性知识的智能搜索算法 , 在高空间复杂问题上比以往有更好的结果 。它提 供给我们的是一种通用的算法框架 ,具有很强的适 应性 ,对特殊问题提供了极大的灵活性 。遗传算法 是一门新发展起来的学科 , 其理论 、 方法在实际中 的应用随着具体问题的变化而不同 。 GIS 领域中所涉及的很多有关最优化问题的算 法具备了遗传算法的结构特征 ,这些问题包括最佳 路径分析 、 资源分配 、 连通分析 、 流分析以及决策支 持系统中的决策理论等 ( 熊盛武等 ,2002) 。本文选 择了其中最富有代表性的最短路径问题 ,着重探讨 遗传算法求解最短路径问题的可行性 。
© 1995-2004 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
170
华 东 地 质 学 院 学 报 2003 年
p2 = ( 2 ,3 ,4 ,5 ,1 ,6 ,7) ;
数 n = 9 ,求 2 到点 4 的路径 ,编码串 ( 2 ,3 ,6 ,5 ,9 ,8 , 4 ,7 ,1) 代表的个体为 ( 2 ,3 ,6 ,5 ,9 ,8 ,4) ,编码的最后 两位用来进行算子的运算 。
2. 2 算子设计
因为本文主要采用自然编码方案进行算法的 设计 ,所以除介绍在路径表达中常用的几种算子之 外 ,重点将放在自然编码方面的算子设计上 。 ( 1) 选择算子 在路径设计中 ,选择算子一般采用比例选择算 子 。具体办法如下 : 计算所有个体的适应度值 Fi 和总体适应度值 ∑Fi , 计算每个个体的适应度百分 比 FCi = Fi / ∑Fi , 然后计算每个个体在 ( 0 , 1 ) 区间 上的子区间 ( ECi - 1 , FCi - 1 + FCi ) , 按随机数策略计 算选择各个子区间的个体数 , 将这些个体保留到下 一代 。 ( 2) 交叉算子 自然编码的染色体在单点一致交叉算子的运 算下将会产生非法的个体 ,故一般都要设计特殊的 交叉算子来解决这个问题 。周明等 ( 1999) 认为 , 在 路径问题求解中效果比较好的几种交叉算子是部 分映射交叉 ( PMX) 、 序交叉 ( OX) 、 循环交叉 ( CX) 和 基于序的交叉 ( CX) ( 周明等 ,1999) ; 另外一种称之 为两交换启发式交叉 ( HX) 算子的效果也比较好