Vol.28No.11李擎等：一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A“算法的比较·1083· 采用文献刁中的方法.具体过程为：从起始点出 出现断路. 发，随机选取与起始点直接相连的一个点作为下 15交叉和变异概率的在线自适应调整策略 一个节点，如此反复直到找到终点为止.在路径 交叉概率和变异概率的选取对遗传算法的影 的产生过程中为了避免出现环路，规定在一条路 响非常大.为了更好地使用遗传算法对路径进行 径中当一个节点被选中以后，给该节点一个标记， 规划，本文提出了一种新的基于模糊控制的交叉 只有没有标记过的节点才能被选作新的路径节 概率和变异概率在线自适应调节策略.其中，模 点，每条路径选择完后标记全部刷新. 糊控制器的输入变量为相邻两代群体平均适应度 13适应度函数 函数值的变化量△∫ag(k)和相邻两代群体之间 为方便计算，适应度函数取为： 标准差的变化量△σ(k),输出变量为下一代交叉 f(xi)=Distance(xi),i=1,2,.,M (1) 概率和变异概率的变化量△p。(k+1)和 其中，x表示第i个个体，Distance(x:)表示个体 △pm(k+1). x:所代表路径的长度，M表示种群规模.从适应 △fawg(k)的计算公式如下： 度函数可以看出：最短路径将具有最小的适应度 △fwg(k)=fawg(k-1)-fmg(k)(k=2,3,…) 函数值. (2) 1.4交叉和变异算子 其中，∫g(k)为第k代种群的平均适应度函数 采用文献[9]中的交叉算子和变异算子.其 值，它代表了该代群体的整体水平，计算公式为： 中当交叉运算应用于父代个体V1和'2时，操作 过程为： 人女会阳 (3) (1)列举出V1和V2中均含有的节点集合 式中，M仍表示种群规模fi(k)(i=1,2,…,M) N(不包括起始节点和目标节点)： 则代表第k代群体中各个体的适应度函数值. (2)从Ne中随机选择一个节点i∈Ne作为 同理，△σ(k)的计算公式为： 交叉点； △G(k)=G(k-1)-G(k)(k=2,3,)(4) (3)检查V1和？中节点i之前或之后的 其中，σ(k)表示第k代种群的标准差，它描述了 内容是否相同，如相同，则取消本次交叉操作：否 该代群体中各个体的分散程度（即种群的多样 则，进行下一步； 性)，其计算公式为： (4)通过交换交叉点后的所有节点得到交叉 M 后新的子代个体； (k)= f后(k)-fag(k】2 (5) (⑤)若交叉后的子代个体中存在环路，则按 为了增加在线自适应调节算法的通用性需 文献[8的方法进行处理. 要对输入变量进行归一化处理，△∫g(k)对应的 变异操作过程为： 归一化公式为： (1)从待变异父代个体V中随机选择变异 节点i(i=2,…,M-1),其中M为待变异个体 a △fg(k) 的编码长度； fwg(k)≤favg(k-1) (2)找出所有和节点i(i=2,…,M-1)直 △fg(k)= (6) 接相连的节点集合Nm(不包括起始节点和目标 △fsk)_fmk-D-l, favg(k)favg (k) 节点)： favg(k favg (k-1) (3)从中Nm随机选择一个节点j,j∈Nm; △σ(k)归一化公式为： (4)应用A*算法产生从一条从起始节点到 节点j的准最短路径r1(因为A算法在实际应 1 △G(k) 用过程中未必一定能够找到最短路径)： G(k)≤G(k-1) (5)再次应用A算法产生从一条从节j点 △σ*(k)= △a(k)=k-D-1, (1) 到目标节点的准最短路径r2: 6(k) a(k) (6)如果r1和r2中存在重复节点（节点j 6(k>G(k-1) 除外)，则放弃路径.不进行变异，防止出现环路； 为了提高路径规划算法的搜索速度，采用模 否吧，接两段路径组成变异后的新个体保证不。P糊控制套询表方式进行模糊推稞条过计算得到i采用文献[ 7] 中的方法.具体过程为 :从起始点出 发,随机选取与起始点直接相连的一个点作为下 一个节点, 如此反复直到找到终点为止.在路径 的产生过程中为了避免出现环路, 规定在一条路 径中当一个节点被选中以后, 给该节点一个标记, 只有没有标记过的节点才能被选作新的路径节 点,每条路径选择完后标记全部刷新. 1.3 适应度函数 为方便计算 ,适应度函数取为 : f(xi)=Distance(x i), i =1 , 2 , …, M (1) 其中, xi 表示第 i 个个体, Distance(xi)表示个体 x i 所代表路径的长度, M 表示种群规模 .从适应 度函数可以看出:最短路径将具有最小的适应度 函数值. 1.4 交叉和变异算子 采用文献[ 9] 中的交叉算子和变异算子 .其 中当交叉运算应用于父代个体 V 1 和 V2 时, 操作 过程为: (1)列举出 V 1 和 V2 中均含有的节点集合 Nc(不包括起始节点和目标节点); (2)从 Nc 中随机选择一个节点 i ∈ Nc 作为 交叉点; (3)检查 V 1 和 V2 中节点 i 之前或之后的 内容是否相同 ,如相同, 则取消本次交叉操作 ;否 则,进行下一步 ; (4)通过交换交叉点后的所有节点得到交叉 后新的子代个体 ; (5)若交叉后的子代个体中存在环路, 则按 文献[ 8] 的方法进行处理 . 变异操作过程为 : (1)从待变异父代个体 V 中随机选择变异 节点i(i =2 , … , M -1),其中 M 为待变异个体 的编码长度; (2)找出所有和节点 i(i =2 , … , M -1)直 接相连的节点集合 N m (不包括起始节点和目标 节点); (3)从中 N m 随机选择一个节点j , j ∈ N m ; (4)应用 A ＊算法产生从一条从起始节点到 节点 j 的准最短路径 r 1(因为 A ＊算法在实际应 用过程中未必一定能够找到最短路径); (5)再次应用 A ＊算法产生从一条从节 j 点 到目标节点的准最短路径 r 2 ; (6)如果 r 1 和 r 2 中存在重复节点(节点 j 除外), 则放弃路径, 不进行变异, 防止出现环路; 否则 ,连接两段路径组成变异后的新个体,保证不 出现断路 . 1.5 交叉和变异概率的在线自适应调整策略 交叉概率和变异概率的选取对遗传算法的影 响非常大 .为了更好地使用遗传算法对路径进行 规划, 本文提出了一种新的基于模糊控制的交叉 概率和变异概率在线自适应调节策略 .其中, 模 糊控制器的输入变量为相邻两代群体平均适应度 函数值的变化量 Δf avg(k)和相邻两代群体之间 标准差的变化量 Δσ(k),输出变量为下一代交叉 概率 和 变 异 概 率 的变 化 量 Δp c (k +1)和 Δp m(k +1). Δf avg(k)的计算公式如下 : Δf avg(k)=f avg(k -1)-f av g(k) (k =2 , 3 , …) (2) 其中 , f av g(k)为第 k 代种群的平均适应度函数 值,它代表了该代群体的整体水平 ,计算公式为: f av g(k)= 1 M ∑ M i =1 fi(k) (3) 式中 , M 仍表示种群规模, fi(k)(i =1 , 2 , … , M) 则代表第 k 代群体中各个体的适应度函数值. 同理 ,Δσ(k)的计算公式为 : Δσ(k)=σ(k -1)-σ(k) (k =2 , 3 , …)(4) 其中, σ(k)表示第 k 代种群的标准差 ,它描述了 该代群体中各个体的分散程度(即种群的多样 性), 其计算公式为: σ(k)= 1 M ∑ M i =1 [ fi(k)-f avg(k)] 2 (5) 为了增加在线自适应调节算法的通用性, 需 要对输入变量进行归一化处理, Δf avg(k)对应的 归一化公式为 : Δf ＊ avg(k)= Δf avg(k) f avg(k -1)=1 - f avg(k) f avg(k -1), f avg(k)≤f avg(k -1) Δf avg(k) f av g(k) = f av g(k -1) f avg(k) -1 , f avg(k)>f avg(k -1) (6) Δσ(k)归一化公式为 : Δσ ＊(k)= Δσ(k) σ(k -1) =1 - σ(k) σ(k -1) , σ(k)≤σ(k -1) Δσ(k) σ(k) = σ(k -1) σ(k) -1 , σ(k)>σ(k -1) (7) 为了提高路径规划算法的搜索速度, 采用模 糊控制查询表方式进行模糊推理, 经过计算得到 Vol.28 No.11 李 擎等:一种用于车辆最短路径规划的自适应遗传算法及其与 Dijkstra 和 A ＊算法的比较 · 1083 ·