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

1.2 小生境實(shí)現(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),。為實(shí)現(xiàn)這樣的分布,，共享法將個體的目標(biāo)適應(yīng)度降低，即適應(yīng)度值f_i除以一個niche計(jì)數(shù)m_i獲得共享函數(shù),，niche計(jì)數(shù)m_i作為個體鄰集密集程度的估計(jì),。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)的點(diǎn),，所以x₁的進(jìn)化方向?yàn)?1。

2 小生境遺傳操作步驟
　　小生境遺傳操作步驟：(1)根據(jù)編碼方案,，把路徑點(diǎn)編碼成位串形式,，轉(zhuǎn)化為染色體(路徑)。(2)選擇合適的參數(shù)：群體的大小(所含個體數(shù)目),、交叉概率P_c和變異概率P_m,。(3)隨機(jī)產(chǎn)生一個初始群體即N條路徑。(4)根據(jù)適應(yīng)值函數(shù)計(jì)算每條路徑的適應(yīng)值f(p_i(t)),，為適應(yīng)度較大者標(biāo)記進(jìn)化方向,，根據(jù)個體的適應(yīng)度按比例選擇N個個體。(5)選擇：計(jì)算每一條路徑的選擇概率P=及累計(jì)概率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)值最大的路徑點(diǎn),；如果d≠g(g是設(shè)定的代數(shù))，則轉(zhuǎn)向第(4)步,，否則選用g代替f中最優(yōu)的路徑上的點(diǎn),。
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ù)及其仿真圖形驗(yàn)證。函數(shù)精度為0.01,，每個變量所占的二進(jìn)制編碼長度為9,，個體編碼為20位，種群數(shù)目為100,，終止代數(shù)為100,，交叉概率為P_c=0.6，變異概率P_m=0.002,，運(yùn)行次數(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]²?；贑haos-cat mapping函數(shù)和小生境算法的尋優(yōu)曲線和個體進(jìn)化過程曲線分別如圖7～圖10所示,。

?

?

?

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