(2)交叉算子。采用单点交叉法，在两个父体上分别随机选取一个交叉点(起点和终点除外)，交换两个个体在各自交叉点之后的染色体。考虑到规划路径的长度是可变的，为了防止交叉操作后出现过于繁琐或简单的路径，对生成的新个体长度进行限制，即最大长度不能超过Nmax，并且不能产生回路，若不符合要求，重新获取两个父个体的交叉点。

(3)插入算子。设计了两种插入算子。第一种是有针对性的，即在连线穿过障碍物的两个转向点之间插入一个或多个转向点，使产生的路径避开障碍物，如图1(a)所示；第二种是一般意义上的插入，以一定概率插入一个随机产生的转向点，如图1(b)所示。

(4)扰动算子。同样设计了两种扰动算子，第一种只选取路径不可行的转向点来进行小范围的调整，使其路径可行，如图1(c)所示；第二种是不管路径是否可行，任意选取一个位置，以概率pm对其转向点坐标进行调整。在进化初期，不可行的解数量较多，调整的范围大一些。在进化后期调整范围逐渐缩小，如图1(d)所示。



(5)删除算子。建立一个存储空间REC，在一条路径中，如果点(x_i-1，y_i-1)与点(x_i，y_i)的连线经过障碍物，但(x_i-1，y_i-1)与(x_i+1，y_i-1)的连线不经过障碍物，则将点(x_i，y_i)添加到REC中。如果REC不为空，则从中随机选取一点删除(见图1(e))；否则，在路径中任意选取一个路径点，以概率p_d进行删除，如图1(f)所示。

(6)平滑算子。平滑算子只对可行路径中最大的拐角进行操作，如图1(g)所示。删除拐角α的顶点p_j，依次连接点p_j-1，p₁，p₂，p_j+1构成可行路径段序列p_j-1p₁→p₁p₂→p₂p_j+1。

(7)倒位算子。随机选取路径中两个中间转向点，颠倒之间的转向点。倒位算子可使路径发生急剧变化，对于转向点较多的路径会有积极的意义。通常的交叉和变异算子不易取得此种效果，而且倒位算子能修正遗传进化过程中可能出现的基因误差，如图1(h)所示。

1.6 遗传算子概率选择

选择合适的遗传算子执行概率是遗传算法能否收敛到最优解的关键之一。在进化过程的前期，群体中存在大量的不可行解，因而交叉算子、扰动算子的概率应该取得较大些，而平滑算子取较小的概率；随着进化过程的推进，可行解增多，应适当提高平滑算子的概率，以提高可行解的平滑性能。同时，为了防止交叉算子和扰动算子对可行解的破坏，需降低其执行概率，并取较小的扰动概率对可行解的形状进行微调。其中，扰动算子(1)和插入算子(1)是对路径转向点的启发式操作，都是针对不可行路径的优化调整，对于这些算子应当始终选择较高的概率。插入算子(2)会使路径的转向点数量增加，应当取较小的概率。

1.7 终止条件

一般在对问题无知的情况下，可以在目标函数达到一个可以承受的范围内之后，即终止算法。另外，还可设置最大进化代数，在给定的进化代数之内强行终止算法，从而保证运算时间的要求。为了实用起见，在此采取最大进化代数终止准则，并选取适应度最好的可行路径。

1.8 算法流程

改进后的基于小生境遗传算法流程如图2所示。具体算法描述如下：

(1)初始化种群，沿起点和终点连线方向等距离选取N个点，在这些点的垂直线上随机选取转向点的纵坐标，并且使这些转向点不在障碍物内；

(2)将每一代个体划分为n个类，每个类中选出若干适应度较大的个体，作为一个类的优秀代表，组成一个种群。种群规模Gi(i=1，2，…，n+1)；

(3)计算种群中所有个体的适应度，将其最好的个体保留，然后采用锦标赛选择法，挑选父个体，以执行交叉操作，并且检查获得的子代个体染色体长度是否超过N，如果没有超过，则保留，否则丢弃。

(4)以设定的概率对新产生的子代个体进行变异、插入、扰动、删除、平滑的操作。此过程中，采取预选择机制，比较子串和父串适应度的大小，如果子串的适应度高于父串的适应度，就替换父串；否则维持父串不变；