足球機器人系統是一個典型的且非常具有挑戰性的多智能體系統。在足球機器人比賽中，路徑規劃的主要目的是在充滿對抗的賽場上規劃出一條滿足某項評價指標的無碰撞路徑。路徑規劃主要應用于機器人底層策略中。作為足球機器人基本動作實現的基礎，路徑規劃的優劣將直接影響動作的實時性和準確性。因此，每個足球機器人研究者都把它作為一個研究重點。全局路徑規劃一般包括環境建模和搜索策略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所示。