。1084· 北京科技大学学报 2006年第11期 的交叉概率和变异概率模糊控制查询表分别如表1和表2所示. 表1交叉概率△P(k+1)模糊控制查询表 Table 1 Fuzzy control inquiry table for crossover probability Ap(k+1) △f(k) △a"(k) -08 -06 -04 -02 0 02 04 06 08 -08 0 002 0.02 004 004 006 0.06 008 008 -06 0 0 002 002 004 004 0.06 006 008 -04 -002 0 0 002 002 004 0.04 006 0.06 -02 -0.02 -002 0 0 002 002 0.04 004 0.06 0 一004 -002 一002 0 004 002 0.02 0.04 004 02 -004 -004 -0.02 -002 0 0 0.02 002 004 04 -006 -004 -004 -002 一002 0 0 002 002 06 -006 -006 -004 -004 -002 -002 0 0 002 08 -008 -006 -006 -004 -004 -002 -0.02 0 0 表2变异概率△Pm(k十1)模糊控制查询表 Table 2 Fuzzy control inquiry table for mutation probability p(1) △f(k) △a"(k) -08 -06 -04 -02 0 02 04 06 08 -08 -0008 -0.006 -0006 一0004 -0004 -0002 -0002 0 0 -06 -0.006 -0006 -0004 -0004 -0002 -0002 0 0 0002 -04 -0.006 -0004 -0004 -0002 -0002 0 0 0002 0002 -02 -0004 -0004 -0002 -0002 0 0 0002 0002 0004 0 -0.004 -0002 -0002 0 0004 0002 0002 0004 0004 02 -0002 -0002 0 0 0002 0002 0004 0004 0006 04 -0.002 0 0002 0002 0004 0004 0006 0006 06 0 0 0002 0002 0.004 Q004 0006 0006 0008 08 0 0.002 0002 0004 0.004 Q006 0006 0008 0.008 根据第k代的△f(k)和△o*(k),通过查 为10，最大迭代代数设为50.初始交叉概率取为 询表1即可得到第k十1代交叉概率的变化量 05,初始变异概率取为0.1，之后二者将根据所 △p(k+1,从而得到第k十1代交叉概率 给出的控制查询表在线进行调节.采用赌轮法进 Pe(k十I)的值为： 行选择操作，采用所给出的交叉和变异算子进行 pe(k+1)=pe(k+△pe(k+1)(k=2,3,…) 相应的进化操作，进化结束的条件设定为各代中 (8) 的最优个体连续5代不发生变化或达到所设定的 同理，通过查询表2可以得到第k十1代变 最大迭代代数.此外，为了提高搜索速度，还采用 异概率的变化量△pm(k十I),从而得到第k十1 了最优个体保留策略. 代变异概率pm(k十I)的值为： 经过16代进化，遗传算法收敛，得到的最短 pm(k+1)=pm(k)十△pm(k+1)(k=2,3,…) 路径为(A,C,F,J,M,O,P),该路径的长度为 I83.Dikstra算法的搜索结果验证了它确实是 (9) 一条从起始节点A到目标节点P的最短路径. 1.6应用实例 以图1中从起始节点A到目标节点P的最 2 遗传算法与Dijkstra及A算法 短路径的求取过程为例，说明本文提出的遗传算 的比较 法是如何进行路径寻优的 Dijkstra算法是一种基于图论理论的遍历算 (C遗转算法的参数选取恕下：种群规模eM取e Publishing Housereserved.即nki.net的交叉概率和变异概率模糊控制查询表分别如表 1 和表 2 所示 . 表1 交叉概率 Δp c(k +1)模糊控制查询表 Table 1 Fuzzy control inquiry tabl e for crossover probability Δpc(k +1) Δσ＊(k) Δf ＊ avg(k) -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 -0.8 0 0.02 0.02 0.04 0.04 0.06 0.06 0.08 0.08 -0.6 0 0 0.02 0.02 0.04 0.04 0.06 0.06 0.08 -0.4 -0.02 0 0 0.02 0.02 0.04 0.04 0.06 0.06 -0.2 -0.02 -0.02 0 0 0.02 0.02 0.04 0.04 0.06 0 -0.04 -0.02 -0.02 0 0.04 0.02 0.02 0.04 0.04 0.2 -0.04 -0.04 -0.02 -0.02 0 0 0.02 0.02 0.04 0.4 -0.06 -0.04 -0.04 -0.02 -0.02 0 0 0.02 0.02 0.6 -0.06 -0.06 -0.04 -0.04 -0.02 -0.02 0 0 0.02 0.8 -0.08 -0.06 -0.06 -0.04 -0.04 -0.02 -0.02 0 0 表 2 变异概率 Δp m(k +1)模糊控制查询表 Tabl e 2 Fuzzy control inquiry table for mutation probability Δpm(k +1) Δσ＊(k) Δf ＊ avg(k) -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 -0.8 -0.008 -0.006 -0.006 -0.004 -0.004 -0.002 -0.002 0 0 -0.6 -0.006 -0.006 -0.004 -0.004 -0.002 -0.002 0 0 0.002 -0.4 -0.006 -0.004 -0.004 -0.002 -0.002 0 0 0.002 0.002 -0.2 -0.004 -0.004 -0.002 -0.002 0 0 0.002 0.002 0.004 0 -0.004 -0.002 -0.002 0 0.004 0.002 0.002 0.004 0.004 0.2 -0.002 -0.002 0 0 0.002 0.002 0.004 0.004 0.006 0.4 -0.002 0 0 0.002 0.002 0.004 0.004 0.006 0.006 0.6 0 0 0.002 0.002 0.004 0.004 0.006 0.006 0.008 0.8 0 0.002 0.002 0.004 0.004 0.006 0.006 0.008 0.008 根据第 k 代的 Δf ＊ avg(k)和 Δσ ＊(k),通过查 询表 1 即可得到第 k +1 代交叉概率的变化量 Δp c(k +1), 从而 得到第 k +1 代 交叉概率 pc(k +1)的值为 : pc(k +1)=pc(k)+Δpc(k +1) (k =2 , 3 , …) (8) 同理, 通过查询表 2 可以得到第 k +1 代变 异概率的变化量 Δpm(k +1), 从而得到第 k +1 代变异概率 pm(k +1)的值为 : pm(k +1)=pm(k)+Δpm(k +1) (k =2 , 3 , …) (9) 1.6 应用实例 以图 1 中从起始节点 A 到目标节点 P 的最 短路径的求取过程为例 ,说明本文提出的遗传算 法是如何进行路径寻优的 . 遗传算法的参数选取如下:种群规模 M 取 为 10 ,最大迭代代数设为 50 .初始交叉概率取为 0.5 ,初始变异概率取为 0.1 , 之后二者将根据所 给出的控制查询表在线进行调节 .采用赌轮法进 行选择操作 ,采用所给出的交叉和变异算子进行 相应的进化操作, 进化结束的条件设定为各代中 的最优个体连续 5 代不发生变化或达到所设定的 最大迭代代数 .此外 ,为了提高搜索速度 ,还采用 了最优个体保留策略 . 经过 16 代进化 , 遗传算法收敛 ,得到的最短 路径为(A , C , F , J , M , O , P), 该路径的长度为 18.3 .Dijkstra 算法的搜索结果验证了它确实是 一条从起始节点 A 到目标节点P 的最短路径 . 2 遗传算法与 Dijkstra 及 A ＊算法 的比较 Dijkstra 算法是一种基于图论理论的遍历算 · 1084 · 北 京 科 技 大 学 学 报 2006 年第 11 期