足球机器人系统是一个典型的且非常具有挑战性的多智能体系统。在足球机器人比赛中，路径规划的主要目的是在充满对抗的赛场上规划出一条满足某项评价指标的无碰撞路径。路径规划主要应用于机器人底层策略中。作为足球机器人基本动作实现的基础，路径规划的优劣将直接影响动作的实时性和准确性。因此，每个足球机器人研究者都把它作为一个研究重点。全局路径规划一般包括环境建模和搜索策略2个子问题。其中环境建模的主要方法有：可视图法、自由空间法和栅格法^[1]等。目前常用的搜索技术有：梯度法^[4][5]、 A*等图搜索方法、枚举法和随机搜索法等。而这些方法也存在一些问题：梯度法易陷入局部最小点，图搜索方法和枚举法不能用于高维的优化问题，随机搜索法计算效率太低。本文将基于小生境的遗传算法用于足球机器人路径规划中，改进了传统算法的性能,同时具有很高的全局寻优能力和收敛速度，同时可进一步提高解的精度。
1 小生境遗传算法^[2][6]
　　在自然界中，特征、性状相似的物种往往相聚在一起，并在同劣种交配繁衍后代。在基本的遗传算法(SGA)中，交配完全是随机的，虽然这种随机化的杂交形式在寻优的初级阶段保持了解的多样性，但在进化的后期，大量个体集中于某一极值点上，它们的后代造成了近亲繁殖。遗传算法由于其强大的全局搜索能力，求解多峰值函数的优化计算时，一般只能找到个别的几个最优解，甚至得到的是局部最优解；由于搜索的随机性，因而解的精度不高。为了使优化算法能够找到全部的最优解，引进小生境的概念。
　　本文使用一种可标记进化方向的小生境遗传算法DRN-GA(Direction Record Niche Genetic Algorithm)，特点是：基于“分享机制”更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度；利用进化过程中的有用信息，为每个个体标记进化方向。执行DRN-GA算法后，若以每个个体为初始点，按标记的进化方向继续局部寻优，会进一步提高解的精度。
1.1 个体编码结构
　　个体编码中除应包含决策变量的编码外，还要有记忆进化方向的部分。为适应本算法，设计个体编码方案如下示：

1.2 小生境实现原理及适应度函数的确立
　　小生境技术就是将每一代个体划分为若干类，每类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间通过杂交、变异产生新一代个体群，同时采用预选择机制、排挤机制或分享机制完成选择操作。基于这种小生境技术的遗传算法NGA(Niched Genetic Alogorithm)可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度，特别适用于复杂多峰函数的优化问题。
　　在普通遗传算法的进化过程中，每一代进行选择、交叉、编译操作之前加入如下操作：通过个体之间的相似程度的共享函数调整群体中个体的适应度，从而在群体的进化过程中，算法能依据该调整后的新适应度进行选择操作，以维护群体的多样性，创造出小生境的进化环境。共享函数是表示群体中两个个体之间密切关系程度的一个函数，可记为S(d_ij)，其中d_ij表示个体i和个体j之间的某种关系。适应度共享函数的直接目的是将搜索空间的多个不同峰值在地理上区分开来，每个峰值处接受一定比例数目的个体，比例大小与峰值高度有关。为实现这样的分布，共享法将个体的目标适应度降低，即适应度值f_i除以一个niche计数m_i获得共享函数，niche计数m_i作为个体邻集密集程度的估计。m_i=其中，d[i，j]是个体i和j的距离，Sh[d]是共享函数，此函数递减，Sh[0]=1和Sh[d≥σ_share]=0。
　　采用一种将海明距离测度(基因型差异)与适应度距离(表现型差异)相结合的方法。若d₁(x_i，x_j)为任意两个个体x_i和x_j的海明距离，d₂(x_i，x_j)是适应度距离，这时共享函数可定义为：
　　
　　其中，σ₁和σ₂是niche的半径，即分别为基因型和表现型的作为一个niche内的个体最大距离。个体的适应度函数在共享后变为如下形式：
　　
1.3 进化方向的确立
　　设单变量函数y=g(x)，且x₁-x₂〈ρ，ρ为一较小正数。设目标函数为J=max[g(x)]。进化示意图如图1所示。由图1知，x₁比x₂更优。根据x₁〈x₂，g(x₁)〉g(x₂)及x₁-x₂〈ρ可知，在x₁的一个邻域内g(x)是下降的，可推出，存在一很小正数ε，使得g(x₁-ε)〉g(x₁)，即x₁-ε比x₁更优的点，所以x₁的进化方向为-1。

2 小生境遗传操作步骤
　　小生境遗传操作步骤：(1)根据编码方案，把路径点编码成位串形式，转化为染色体(路径)。(2)选择合适的参数：群体的大小(所含个体数目)、交叉概率P_c和变异概率P_m。(3)随机产生一个初始群体即N条路径。(4)根据适应值函数计算每条路径的适应值f(p_i(t))，为适应度较大者标记进化方向，根据个体的适应度按比例选择N个个体。(5)选择：计算每一条路径的选择概率P=及累计概率q_i=∑p_j，j=1，…，i。(6)交叉：对每条路径产生[0，1]间随机数r，如果r〈P_c,则该条路径参加交叉操作，如此选出参加交叉的一组路径后，随机配对；对每一对，产生[0，1]间的随机数以确定交叉的位置。(7)变异：如果变异概率为P_m，则可能变异的位数的期望值为P·n·N(n为染色体串长，N为群体)。(8)如果新个体数未达到M，则转向第(5)步继续进行遗传操作，否则代数加1，d=d+1；将新群体的M 条路径的适应值由大到小进行排序，保存适应值最大的路径点；如果d≠g(g是设定的代数)，则转向第(4)步，否则选用g代替f中最优的路径上的点。
3 精确优化
　　DRN-GA执行后，得到的种群每个个体中都保存了进化方向。局部寻优沿进化方向以步长step寻找更优解， 对每个个体沿进化方向继续搜索，可进一步提高解的精度。两算法可串行执行。精确优化结构示意图如图2所示。

4 仿真
　　算法的搜索能力和优化精度在路径规划中的应用性能，可以通过下述函数及其仿真图形验证。函数精度为0.01，每个变量所占的二进制编码长度为9，个体编码为20位，种群数目为100，终止代数为100，交叉概率为P_c=0.6，变异概率P_m=0.002，运行次数为40。
　　(1)Gauss函数
　　选取函数：
　　f₁(x，y)=xsin(4πx)-ysin(4πy+π)+1
　　x，y∈[-1，2]，f₁^*(1.6289，1.6289)=4.2539
　　采用高斯函数和基于小生境算法的寻优曲线及其个体的进化过程曲线分别如图3～图6所示。
　　小生境遗传算法与基本遗传算法的性能对比如表1所示。

　　(2)Chaos-cat mapping函数^[3]
　　选取函数：
　　X是一个两输入向量，[X₁，X₂]∈[0，100]²。基于Chaos-cat mapping函数和小生境算法的寻优曲线和个体进化过程曲线分别如图7～图10所示。

　　改进算法与基本遗传算法的性能对比如表2所示。