正在加载图片...
,320 北京科技大学学报 第30卷 1.3.3连通节点对处一点交叉 集合N(45,35,34,33,43,53)中，只有节点45满足 如果两个父代个体中既不存在相同节点也不存 要求.由于节点45和节点26以及节点48均连通， 在潜在节点，则需要查看两个父代个体中是否存在 所以节点45可以作为变异后的节点，此时生成的 连通节点对，所谓连通节点对，是指分属于两个不 子代个体V'为： 同父代个体，但它们之间却可以直接连通的两个节 子代个体V′(0,4,26,45,48,98,99) 点.，其对应的交叉操作就是直接将连通节点对当作 关于变异操作，需要强调指出：(1)变异操作主 共有节点，然后按照共有节点一点交叉方式处理即可 要是增加种群的多样性，严格讲并不要求变异后个 设图1中的一对父代个体V1和V2为： 体的适应度值一定要低于变异前个体的适应度值 父代个体V1(0,4,26,46,47,88,99); (对于最短路径规划问题，其适应度函数值越小越 父代个体V2(0,5,35,33,83,99) 好)，由于这里引入了启发式搜索技术，即要求变异 可以看出，除起始节点和目标节点外，两父代个 后的节点必须在路径的前进方向上；所以本文的变 体中既不存在共有节点也不存在潜在节点，但检查 异操作不仅能增加种群的多样性，而且能降低个体 发现父代个体V1中的节点46和父代个体V2中的 的适应度函数值.(2)要求变异后的节点必须在待 节点35是连通的，所以将节点46和节点35作为连 变异节点相邻的自由区域内选择，这充分利用了局 通节点对进行一点交叉操作，此时产生的子代个体 部搜索技术；而变异后节点与待变异节点之前和之 V1和V2分别为： 后节点连通性的检查则又保证了变异后所生成新路 子代个体V1(0,4,26,46,35,33,83,99): 径的连通性， 子代个体V2(0,5,35,46,47,88,99). 1.5求精算子和删除算子 需要指出的是，这种交叉操作往往会造成子代 1.5.1求精算子 个体平均适应度值上升 为了防止路径在躲避障碍区域拐直角弯，提出 1.4变异算子 了求精算子，其基本思路是用三角形的斜边代替两 为了增加种群的多样性，防止得到局部最优解， 条直角边，以减小路径长度，其具体操作过程如下： 发生早熟收敛现象，路径规划算法中必须引入变异 Step1利用各节点对应的坐标计算路径中每 算子，但这里同样不能像传统遗传算法那样采用随 两段线段之间的夹角； 机变异操作，因为这样同样容易产生断路现象。针 Step2找出使两段线段夹角为90的节点i; 对路径规划的具体需要，本文将局部搜索技术引入 Step3在以节点i为终点的线段上确定在地 到变异操作中，主要是为了和全局搜索相配合，以提 理位置上直接相邻的节点； 高解的质量和算法收敛的快速性，路径变异过程 Step4在以节点i为起点的线段上确定在地 如下： 理位置上直接相邻的节点k; Step1从待变异父代个体V中随机选择一个 Step5在待求精路径中节点i前插入节点j, 作为待变异节点（不包括起始节点和目标节点） 在节点i后插入节点k,并去掉节点i: Step2调出所有和待变异节点在地理位置上 Step6重复Step2~Step5直到将所有拐直角 直接相邻的自由节点的集合N(可离线存储) 弯的节点处理完， Step3根据路径的前进方向（可以通过起始 设图1中的一个父代个体V为： 节点和目标节点之间坐标的对比确定)从集合N中 父代个体V(0,5,35,33,83,99). 随机选择一个节点作为变异后的节点 经检查发现，节点5、节点35以及节点33均为 Step4检查变异后的节点和待变异节点之前 拐直角弯的节点，经过三次求精算子操作后得到的 和之后的节点是否连通，如连通，则用变异后的节 子代个体V为： 点替换待变异节点形成一条连通的新路径；否则重 子代个体V(0,4,15,25,34,43,83,99) 复Step3和Step4,直至找到合适的变异节点或搜索 求精算子只有在交叉和变异操作完成后才允许 遍所有符合要求的节点为止 使用 设待变异父代个体V为： 1.5.2删除算子 父代个体V(0,4,26,44,48,98,99). 为了减小最终路径的编码长度，提出了删除算 随机选择节点44作为待变异节点，根据路径 子，其基本思路是如果路径中某两个不相邻节点是 的前进方向可知，在和节点44直接相邻的自由节点 连通的，则这两个不相邻节点之间的中间节点是多1∙3∙3 连通节点对处一点交叉 如果两个父代个体中既不存在相同节点也不存 在潜在节点则需要查看两个父代个体中是否存在 连通节点对．所谓连通节点对是指分属于两个不 同父代个体但它们之间却可以直接连通的两个节 点．其对应的交叉操作就是直接将连通节点对当作 共有节点然后按照共有节点一点交叉方式处理即可． 设图1中的一对父代个体 V1 和 V2 为： 父代个体 V1 （042646478899）； 父代个体 V2 （0535338399）． 可以看出除起始节点和目标节点外两父代个 体中既不存在共有节点也不存在潜在节点但检查 发现父代个体 V1 中的节点46和父代个体 V2 中的 节点35是连通的所以将节点46和节点35作为连 通节点对进行一点交叉操作此时产生的子代个体 V′1 和 V′2 分别为： 子代个体 V′1 （04264635338399）； 子代个体 V′2 （053546478899）． 需要指出的是这种交叉操作往往会造成子代 个体平均适应度值上升． 1∙4 变异算子 为了增加种群的多样性防止得到局部最优解 发生早熟收敛现象路径规划算法中必须引入变异 算子．但这里同样不能像传统遗传算法那样采用随 机变异操作因为这样同样容易产生断路现象．针 对路径规划的具体需要本文将局部搜索技术引入 到变异操作中主要是为了和全局搜索相配合以提 高解的质量和算法收敛的快速性．路径变异过程 如下： Step1 从待变异父代个体 V 中随机选择一个 作为待变异节点（不包括起始节点和目标节点）． Step2 调出所有和待变异节点在地理位置上 直接相邻的自由节点的集合 N（可离线存储）． Step3 根据路径的前进方向（可以通过起始 节点和目标节点之间坐标的对比确定）从集合 N 中 随机选择一个节点作为变异后的节点． Step4 检查变异后的节点和待变异节点之前 和之后的节点是否连通．如连通则用变异后的节 点替换待变异节点形成一条连通的新路径；否则重 复 Step3和 Step4直至找到合适的变异节点或搜索 遍所有符合要求的节点为止． 设待变异父代个体 V 为： 父代个体 V （042644489899）． 随机选择节点44作为待变异节点．根据路径 的前进方向可知在和节点44直接相邻的自由节点 集合 N（453534334353）中只有节点45满足 要求．由于节点45和节点26以及节点48均连通 所以节点45可以作为变异后的节点．此时生成的 子代个体 V′为： 子代个体 V′ （042645489899）． 关于变异操作需要强调指出：（1）变异操作主 要是增加种群的多样性严格讲并不要求变异后个 体的适应度值一定要低于变异前个体的适应度值 （对于最短路径规划问题其适应度函数值越小越 好）．由于这里引入了启发式搜索技术即要求变异 后的节点必须在路径的前进方向上；所以本文的变 异操作不仅能增加种群的多样性而且能降低个体 的适应度函数值．（2）要求变异后的节点必须在待 变异节点相邻的自由区域内选择这充分利用了局 部搜索技术；而变异后节点与待变异节点之前和之 后节点连通性的检查则又保证了变异后所生成新路 径的连通性． 1∙5 求精算子和删除算子 1∙5∙1 求精算子 为了防止路径在躲避障碍区域拐直角弯提出 了求精算子．其基本思路是用三角形的斜边代替两 条直角边以减小路径长度．其具体操作过程如下： Step1 利用各节点对应的坐标计算路径中每 两段线段之间的夹角； Step2 找出使两段线段夹角为90°的节点 i； Step3 在以节点 i 为终点的线段上确定在地 理位置上直接相邻的节点 j； Step4 在以节点 i 为起点的线段上确定在地 理位置上直接相邻的节点 k； Step5 在待求精路径中节点 i 前插入节点 j 在节点 i 后插入节点 k并去掉节点 i； Step6 重复 Step2～Step5直到将所有拐直角 弯的节点处理完． 设图1中的一个父代个体 V 为： 父代个体 V （0535338399）． 经检查发现节点5、节点35以及节点33均为 拐直角弯的节点．经过三次求精算子操作后得到的 子代个体 V′为： 子代个体 V′ （04152534438399）． 求精算子只有在交叉和变异操作完成后才允许 使用． 1∙5∙2 删除算子 为了减小最终路径的编码长度提出了删除算 子．其基本思路是如果路径中某两个不相邻节点是 连通的则这两个不相邻节点之间的中间节点是多 ·320· 北 京 科 技 大 学 学 报 第30卷