足球機(jī)器人系統(tǒng)是一個典型的且非常具有挑戰(zhàn)性的多智能體系統(tǒng)。在足球機(jī)器人比賽中，路徑規(guī)劃的主要目的是在充滿對抗的賽場上規(guī)劃出一條滿足某項評價指標(biāo)的無碰撞路徑。路徑規(guī)劃主要應(yīng)用于機(jī)器人底層策略中。作為足球機(jī)器人基本動作實現(xiàn)的基礎(chǔ)，路徑規(guī)劃的優(yōu)劣將直接影響動作的實時性和準(zhǔn)確性。因此，每個足球機(jī)器人研究者都把它作為一個研究重點。全局路徑規(guī)劃一般包括環(huán)境建模和搜索策略2個子問題。其中環(huán)境建模的主要方法有：可視圖法、自由空間法和柵格法^[1]等。目前常用的搜索技術(shù)有：梯度法^[4][5]、 A*等圖搜索方法、枚舉法和隨機(jī)搜索法等。而這些方法也存在一些問題：梯度法易陷入局部最小點，圖搜索方法和枚舉法不能用于高維的優(yōu)化問題，隨機(jī)搜索法計算效率太低。本文將基于小生境的遺傳算法用于足球機(jī)器人路徑規(guī)劃中，改進(jìn)了傳統(tǒng)算法的性能,同時具有很高的全局尋優(yōu)能力和收斂速度，同時可進(jìn)一步提高解的精度。
1 小生境遺傳算法^[2][6]
　　在自然界中，特征、性狀相似的物種往往相聚在一起，并在同劣種交配繁衍后代。在基本的遺傳算法(SGA)中，交配完全是隨機(jī)的，雖然這種隨機(jī)化的雜交形式在尋優(yōu)的初級階段保持了解的多樣性，但在進(jìn)化的后期，大量個體集中于某一極值點上，它們的后代造成了近親繁殖。遺傳算法由于其強(qiáng)大的全局搜索能力，求解多峰值函數(shù)的優(yōu)化計算時，一般只能找到個別的幾個最優(yōu)解，甚至得到的是局部最優(yōu)解；由于搜索的隨機(jī)性，因而解的精度不高。為了使優(yōu)化算法能夠找到全部的最優(yōu)解，引進(jìn)小生境的概念。
　　本文使用一種可標(biāo)記進(jìn)化方向的小生境遺傳算法DRN-GA(Direction Record Niche Genetic Algorithm)，特點是：基于“分享機(jī)制”更好地保持解的多樣性，同時具有很高的全局尋優(yōu)能力和收斂速度；利用進(jìn)化過程中的有用信息，為每個個體標(biāo)記進(jìn)化方向。執(zhí)行DRN-GA算法后，若以每個個體為初始點，按標(biāo)記的進(jìn)化方向繼續(xù)局部尋優(yōu)，會進(jìn)一步提高解的精度。
1.1 個體編碼結(jié)構(gòu)
　　個體編碼中除應(yīng)包含決策變量的編碼外，還要有記憶進(jìn)化方向的部分。為適應(yīng)本算法，設(shè)計個體編碼方案如下示：

1.2 小生境實現(xiàn)原理及適應(yīng)度函數(shù)的確立
　　小生境技術(shù)就是將每一代個體劃分為若干類，每類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表組成一個種群，再在種群中以及不同種群之間通過雜交、變異產(chǎn)生新一代個體群，同時采用預(yù)選擇機(jī)制、排擠機(jī)制或分享機(jī)制完成選擇操作?；谶@種小生境技術(shù)的遺傳算法NGA(Niched Genetic Alogorithm)可以更好地保持解的多樣性，同時具有很高的全局尋優(yōu)能力和收斂速度，特別適用于復(fù)雜多峰函數(shù)的優(yōu)化問題。
　　在普通遺傳算法的進(jìn)化過程中，每一代進(jìn)行選擇、交叉、編譯操作之前加入如下操作：通過個體之間的相似程度的共享函數(shù)調(diào)整群體中個體的適應(yīng)度，從而在群體的進(jìn)化過程中，算法能依據(jù)該調(diào)整后的新適應(yīng)度進(jìn)行選擇操作，以維護(hù)群體的多樣性，創(chuàng)造出小生境的進(jìn)化環(huán)境。共享函數(shù)是表示群體中兩個個體之間密切關(guān)系程度的一個函數(shù)，可記為S(d_ij)，其中d_ij表示個體i和個體j之間的某種關(guān)系。適應(yīng)度共享函數(shù)的直接目的是將搜索空間的多個不同峰值在地理上區(qū)分開來，每個峰值處接受一定比例數(shù)目的個體，比例大小與峰值高度有關(guān)。為實現(xiàn)這樣的分布，共享法將個體的目標(biāo)適應(yīng)度降低，即適應(yīng)度值f_i除以一個niche計數(shù)m_i獲得共享函數(shù)，niche計數(shù)m_i作為個體鄰集密集程度的估計。m_i=其中，d[i，j]是個體i和j的距離，Sh[d]是共享函數(shù)，此函數(shù)遞減，Sh[0]=1和Sh[d≥σ_share]=0。
　　采用一種將海明距離測度(基因型差異)與適應(yīng)度距離(表現(xiàn)型差異)相結(jié)合的方法。若d₁(x_i，x_j)為任意兩個個體x_i和x_j的海明距離，d₂(x_i，x_j)是適應(yīng)度距離，這時共享函數(shù)可定義為：
　　
　　其中，σ₁和σ₂是niche的半徑，即分別為基因型和表現(xiàn)型的作為一個niche內(nèi)的個體最大距離。個體的適應(yīng)度函數(shù)在共享后變?yōu)槿缦滦问剑?BR>　　
1.3 進(jìn)化方向的確立
　　設(shè)單變量函數(shù)y=g(x)，且x₁-x₂〈ρ，ρ為一較小正數(shù)。設(shè)目標(biāo)函數(shù)為J=max[g(x)]。進(jìn)化示意圖如圖1所示。由圖1知，x₁比x₂更優(yōu)。根據(jù)x₁〈x₂，g(x₁)〉g(x₂)及x₁-x₂〈ρ可知，在x₁的一個鄰域內(nèi)g(x)是下降的，可推出，存在一很小正數(shù)ε，使得g(x₁-ε)〉g(x₁)，即x₁-ε比x₁更優(yōu)的點，所以x₁的進(jìn)化方向為-1。

2 小生境遺傳操作步驟
　　小生境遺傳操作步驟：(1)根據(jù)編碼方案，把路徑點編碼成位串形式，轉(zhuǎn)化為染色體(路徑)。(2)選擇合適的參數(shù)：群體的大小(所含個體數(shù)目)、交叉概率P_c和變異概率P_m。(3)隨機(jī)產(chǎn)生一個初始群體即N條路徑。(4)根據(jù)適應(yīng)值函數(shù)計算每條路徑的適應(yīng)值f(p_i(t))，為適應(yīng)度較大者標(biāo)記進(jìn)化方向，根據(jù)個體的適應(yīng)度按比例選擇N個個體。(5)選擇：計算每一條路徑的選擇概率P=及累計概率q_i=∑p_j，j=1，…，i。(6)交叉：對每條路徑產(chǎn)生[0，1]間隨機(jī)數(shù)r，如果r〈P_c,則該條路徑參加交叉操作，如此選出參加交叉的一組路徑后，隨機(jī)配對；對每一對，產(chǎn)生[0，1]間的隨機(jī)數(shù)以確定交叉的位置。(7)變異：如果變異概率為P_m，則可能變異的位數(shù)的期望值為P·n·N(n為染色體串長，N為群體)。(8)如果新個體數(shù)未達(dá)到M，則轉(zhuǎn)向第(5)步繼續(xù)進(jìn)行遺傳操作，否則代數(shù)加1，d=d+1；將新群體的M 條路徑的適應(yīng)值由大到小進(jìn)行排序，保存適應(yīng)值最大的路徑點；如果d≠g(g是設(shè)定的代數(shù))，則轉(zhuǎn)向第(4)步，否則選用g代替f中最優(yōu)的路徑上的點。
3 精確優(yōu)化
　　DRN-GA執(zhí)行后，得到的種群每個個體中都保存了進(jìn)化方向。局部尋優(yōu)沿進(jìn)化方向以步長step尋找更優(yōu)解， 對每個個體沿進(jìn)化方向繼續(xù)搜索，可進(jìn)一步提高解的精度。兩算法可串行執(zhí)行。精確優(yōu)化結(jié)構(gòu)示意圖如圖2所示。

4 仿真
　　算法的搜索能力和優(yōu)化精度在路徑規(guī)劃中的應(yīng)用性能，可以通過下述函數(shù)及其仿真圖形驗證。函數(shù)精度為0.01，每個變量所占的二進(jìn)制編碼長度為9，個體編碼為20位，種群數(shù)目為100，終止代數(shù)為100，交叉概率為P_c=0.6，變異概率P_m=0.002，運行次數(shù)為40。
　　(1)Gauss函數(shù)
　　選取函數(shù)：
　　f₁(x，y)=xsin(4πx)-ysin(4πy+π)+1
　　x，y∈[-1，2]，f₁^*(1.6289，1.6289)=4.2539
　　采用高斯函數(shù)和基于小生境算法的尋優(yōu)曲線及其個體的進(jìn)化過程曲線分別如圖3～圖6所示。
　　小生境遺傳算法與基本遺傳算法的性能對比如表1所示。

　　(2)Chaos-cat mapping函數(shù)^[3]
　　選取函數(shù)：
　　X是一個兩輸入向量，[X₁，X₂]∈[0，100]²。基于Chaos-cat mapping函數(shù)和小生境算法的尋優(yōu)曲線和個體進(jìn)化過程曲線分別如圖7～圖10所示。

?

?

?

　　改進(jìn)算法與基本遺傳算法的性能對比如表2所示。