新聞中心

EEPW首頁 > 醫(yī)療電子 > 設(shè)計(jì)應(yīng)用 > 小生境遺傳算法的移動(dòng)機(jī)器人路徑優(yōu)化技術(shù)探討

小生境遺傳算法的移動(dòng)機(jī)器人路徑優(yōu)化技術(shù)探討

作者: 時(shí)間:2017-06-07 來源:網(wǎng)絡(luò) 收藏

小生境的移動(dòng)技術(shù)

本文引用地址:http://m.butianyuan.cn/article/201706/350133.htm

移動(dòng)路徑規(guī)劃是學(xué)的一個(gè)重要研究領(lǐng)域,也是人工智能與機(jī)器人學(xué)的一個(gè)結(jié)合點(diǎn)。不論是哪種類別的移動(dòng)機(jī)器人,都要求根據(jù)某一準(zhǔn)則(如行走路線總長度最短,能量消耗最少等),在工作空間中沿一條最優(yōu)(或次優(yōu))的路徑行走。

路徑規(guī)劃的典型方法有圖搜索法、柵格法、人工勢場法等,這些算法都有一定局限性,易陷入局部最優(yōu)解,而在解決非線性問題上具有良好的適用性,已成為路徑規(guī)劃中使用較多的一種方法。但是標(biāo)準(zhǔn)的本身也存在著早熟,易陷入局部最優(yōu)解等缺陷,不能保證對路徑規(guī)劃上計(jì)算效率和可靠性的要求。為了提高路徑規(guī)劃的求解質(zhì)量和求解效率,提出一種基于預(yù)選擇機(jī)制小生境技術(shù)的改進(jìn)遺傳算法,并將其應(yīng)用于移動(dòng)機(jī)器人的路徑規(guī)劃,采用化復(fù)雜的二維坐標(biāo)為一維坐標(biāo)的編碼方式,有效降低了遺傳算法的搜索空間;根據(jù)移動(dòng)機(jī)器人的行走特點(diǎn),設(shè)計(jì)了自適應(yīng)交叉算子、自適應(yīng)變異算子、插入算子、刪除算子、擾動(dòng)算子和倒位算子。通過計(jì)算機(jī)仿真證明了改進(jìn)后的遺傳算法明顯提高了搜索效率和收斂速度,并能保證收斂到全局最優(yōu)解,克服了標(biāo)準(zhǔn)遺傳算法的缺點(diǎn),為機(jī)器人快速尋求一條無碰的最優(yōu)路徑。


1 基于遺傳算法的機(jī)器人路徑規(guī)劃算法的改進(jìn)與應(yīng)用

本文的移動(dòng)機(jī)器人路徑規(guī)劃,目標(biāo)是在一幅已知障礙物分布的二維地圖上尋找一條最優(yōu)路徑,使其到達(dá)目標(biāo)點(diǎn)的距離最短,同時(shí)盡可能地使其與障礙物的距離最大化。為了簡化討論,將移動(dòng)機(jī)器考慮為一個(gè)質(zhì)點(diǎn),而障礙物的邊界向外擴(kuò)張,這是移動(dòng)機(jī)器人的最大安全距離。

1.1 基于預(yù)選擇機(jī)制技術(shù)的小生境遺傳算法機(jī)理

由于簡單遺傳算法是一種隨機(jī)的方法,旨在對多個(gè)不同的個(gè)體進(jìn)行隱并行尋優(yōu),其運(yùn)行過程和實(shí)現(xiàn)方法在本質(zhì)上仍是串行的,這樣的進(jìn)化運(yùn)算過程相對緩慢;同時(shí),基本遺傳算法常在各個(gè)個(gè)體未達(dá)到最優(yōu)解之前就收斂于一個(gè)局部最優(yōu)點(diǎn),從而導(dǎo)致染色體趨于一致,即產(chǎn)生“早熟”現(xiàn)象。為了克服這些不足,引入了小生境遺傳機(jī)理,用基于預(yù)選擇機(jī)制技術(shù)的小生境方法維持群體的多樣性,避免群體內(nèi)個(gè)別個(gè)體的大量增加,實(shí)現(xiàn)解空間內(nèi)對局部最優(yōu)解和全局最優(yōu)解的尋優(yōu)。

小生境技術(shù)就是將每一代個(gè)體劃分為若干類,每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群,再在種群中以及不同種群之間,通過雜交、變異產(chǎn)生新一代個(gè)體群,同時(shí)采用預(yù)選擇機(jī)制完成選擇操作?;谶@種小生境技術(shù)的遺傳算法,可以更好地保持解的多樣性,同時(shí)具有很高的全局尋優(yōu)能力和收斂速度。

在預(yù)選擇機(jī)制中,只有在子串的適應(yīng)度超過其父串的情況下,子串才能替換其父串,進(jìn)入下一代群體。這種方式趨向于替換與其本身相似的個(gè)體(父與子之間的性狀遺傳),因而能夠較好地維持群體的分布特性,即使在群體規(guī)模相對較小的情況下,仍可維持較高的群體分布特性。具體算法的實(shí)現(xiàn)步驟如下:

(1)初始化(建立初始群體,確定遺傳參數(shù));

(2)計(jì)算個(gè)體的適應(yīng)度;

(3)遺傳操作(選擇、交叉、變異);

(4)比較子串和父串的適應(yīng)度大小,如果子串的適應(yīng)度高于父串的適應(yīng)度,就替換父串;否則維持父串不變;

(5)如果沒有滿足算法的終止條件,則返回第(2)步;否則,算法終止。

1.2 路徑編碼

基因的編碼方式確定了問題在遺傳算法中的表現(xiàn)形式,也決定了所采用的遺傳進(jìn)化操作。每個(gè)染色體表示為給定符號集中的字符組成基因串。在早期的遺傳算法中,符號集僅限于二進(jìn)制數(shù),因此遺傳基因型是一個(gè)二進(jìn)制符號串,其優(yōu)點(diǎn)在于編碼、解碼的操作簡單,交叉、變異等的遺傳操作便于實(shí)現(xiàn);缺點(diǎn)是不便反映所求問題的特定知識,以及對一些連續(xù)函數(shù)的優(yōu)化問題等。由于遺傳算法的隨機(jī)特性使得其局部搜索能力較差,對于一些要求多維、高精度的連續(xù)函數(shù)優(yōu)化,二進(jìn)制編碼存在連續(xù)函數(shù)離散化時(shí)的映射誤差,當(dāng)個(gè)體編碼串較短時(shí),可能達(dá)不到精度要求;當(dāng)個(gè)體編碼串較長時(shí),雖然能提高精度,但卻會使算法的搜索空間急劇增大。

實(shí)數(shù)編碼適用于表示范圍大、精度高的數(shù),能有效地克服二進(jìn)制編碼的海明懸崖缺點(diǎn),且可直接采用真值編碼,便于與問題相關(guān)的啟發(fā)知識,可以提高算法的搜索效率。移動(dòng)機(jī)器人的路徑可以視為一系列坐標(biāo)點(diǎn)連接而成的線段,對移動(dòng)機(jī)器人的路徑規(guī)劃也就是對這些坐標(biāo)點(diǎn)做各種操作,以使它們符合移動(dòng)機(jī)器人行走的需要??紤]到移動(dòng)機(jī)器人自身的特點(diǎn)(不僅需要避開障礙物,還要保證路徑的平滑性),以及移動(dòng)機(jī)器人路徑中轉(zhuǎn)向點(diǎn)個(gè)數(shù)的不確定性,采用可變長染色體的實(shí)數(shù)編碼方式,用實(shí)數(shù)直接對路徑坐標(biāo)點(diǎn)進(jìn)行編碼,以便于對路徑點(diǎn)的靈活操作,從而避免在使用二進(jìn)制編碼時(shí),二進(jìn)制位串與直角坐標(biāo)點(diǎn)之間互相轉(zhuǎn)換的繁瑣操作,且易于進(jìn)行遺傳算子操作。

1.3 種群初始化

執(zhí)行遺傳算法的最優(yōu)路徑設(shè)計(jì)是必須對種群進(jìn)行初始化,由于初始路徑隨機(jī)產(chǎn)生,各轉(zhuǎn)向點(diǎn)坐標(biāo)可能分布在整個(gè)規(guī)劃區(qū)域范圍內(nèi),包括可行的和不可行的,這樣便增加了搜索范圍。這里在可行區(qū)域內(nèi)限制初始轉(zhuǎn)向點(diǎn),以加快遺傳算法的收斂速度。具體做法為:判斷該轉(zhuǎn)向點(diǎn)是否在可行區(qū)域內(nèi),如果不是,則重新選取,直到坐標(biāo)點(diǎn)符合條件為止。

根據(jù)規(guī)劃環(huán)境的復(fù)雜度不同,最優(yōu)路徑中轉(zhuǎn)向點(diǎn)的個(gè)數(shù)也是不確定的,一般來說,環(huán)境越復(fù)雜,轉(zhuǎn)向點(diǎn)就越多,因此算法采用變長編碼技術(shù),通過對染色體進(jìn)行刪除、插入等操作,能夠確定合適的轉(zhuǎn)向點(diǎn)個(gè)數(shù),使路徑達(dá)到最優(yōu)。但是,轉(zhuǎn)向點(diǎn)數(shù)目太多,占用資源也就會太大,它將使運(yùn)算速度變慢。因此,在運(yùn)算過程中,設(shè)定最大轉(zhuǎn)向點(diǎn)為Nmax,種群中每個(gè)個(gè)體的長度n滿足2≤n≤Nmax。

采用小生境原理,將每一代個(gè)體劃分為若干類,每個(gè)類中選出若干適應(yīng)度較大的個(gè)體,作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群。

1.4 適應(yīng)度函數(shù)

所謂移動(dòng)機(jī)器人的路徑規(guī)劃,指在起點(diǎn)和終點(diǎn)之間找出一條最短的可行路徑,其約束條件是不與障礙物相交,同時(shí)移動(dòng)機(jī)器人在行走中的轉(zhuǎn)角不宜太大。該算法以兩個(gè)條件作為規(guī)劃路徑的可行性評價(jià)函數(shù),即路徑總長度和各轉(zhuǎn)向點(diǎn)拐角的平均大小,對于不可行的路徑,對其適應(yīng)度進(jìn)行懲罰,使它的適應(yīng)度差于可行路徑。

(1)路徑總長度。為了防止移動(dòng)機(jī)器人與障礙物碰撞,應(yīng)盡量使其與障礙物保持一定的安全距離。假設(shè)移動(dòng)機(jī)器人的安全半徑為r;移動(dòng)機(jī)器人與障礙物的距離為d,則路徑總長度Len由式(1)計(jì)算:

式中:d(pi-1,pi)為轉(zhuǎn)向點(diǎn)pi-1與pi之間的長度。如果pi-1與pi之間的路徑不可行,則使用懲罰函數(shù)法對其適應(yīng)度進(jìn)行懲罰。懲罰函數(shù)定義如下:

式中:ε為懲罰因子。路徑的評價(jià)函數(shù)可以寫為:


判斷兩點(diǎn)之間的路徑是否可行,只需判斷這兩點(diǎn)的連線與障礙物的各邊是否相交即可。根據(jù)幾何學(xué)原理,判斷兩條線段是否相交可由以下兩個(gè)步驟進(jìn)行確定:快速排斥試驗(yàn);跨立試驗(yàn)。鑒于文章篇幅,在此不再對這兩個(gè)試驗(yàn)進(jìn)行詳細(xì)闡述。

評價(jià)路徑是求路徑長度最短的問題,通過懲罰因子,可以使不可行路徑變長,從而降低它的適應(yīng)值。

(2)路徑平滑度。移動(dòng)機(jī)器人的特點(diǎn)決定了它在行走過程中不宜以過大拐角進(jìn)行轉(zhuǎn)向,因此整條行走路徑應(yīng)趨于平緩而光滑,即每一轉(zhuǎn)向點(diǎn)處的拐角值應(yīng)盡可能小。這里假設(shè)拐角最大值不能超過π/2,平滑度可以使用路徑的平均拐角值來計(jì)算:


式中:ξ為一個(gè)趨于零的常數(shù)(ξ>0);αi(0≤αi≤π,i=2,3,…,n-1)表示兩向量AC,CB之間的夾角,B,C點(diǎn)的坐標(biāo)分別為(xi-2,yi-1),(xi,yi),(xi-1,yi-1);k為αi中大于或等于π/2的個(gè)數(shù),即當(dāng)某一夾角大于或等于π/2時(shí),對適應(yīng)度進(jìn)行懲罰。當(dāng)n=2時(shí),路徑為起始點(diǎn)與終止點(diǎn)的連線。若其可行,則M值趨于0。可以看出,M值越小,路徑的平滑度越好。

得到了以上兩個(gè)條件的評價(jià)函數(shù),就可以獲得整條路徑的適應(yīng)度函數(shù)。采用各項(xiàng)評價(jià)函數(shù)加權(quán)求和是常用的確定適應(yīng)度函數(shù)的方法。因?yàn)楦鱾€(gè)加權(quán)系數(shù)不是恒定不變的,而是隨路徑和障礙物的情況變化而變化的,所以這種情況下各個(gè)加權(quán)系數(shù)就很難調(diào)整和確定。因此,在確定適應(yīng)度函數(shù)時(shí),盡量使適應(yīng)度函數(shù)的項(xiàng)數(shù)最少,但又必須把路徑規(guī)劃的兩個(gè)條件融合在遺傳優(yōu)化過程中。這里采用評價(jià)函數(shù)相乘的形式,如式(6)所示。

f=1/(ML) (6)

以f作為選擇操作的依據(jù),則路徑的長度和平均拐角越小,其適應(yīng)度越好。

1.5 遺傳算子

(1)選擇算子。使用錦標(biāo)賽選擇法和精英保留法相結(jié)合的選擇策略。采用在錦標(biāo)賽選擇法選擇時(shí),先隨機(jī)在群體中選擇K個(gè)個(gè)體進(jìn)行比較,適應(yīng)度最好的個(gè)體將被選擇作為生成下一代的父體,參數(shù)K稱為競賽規(guī)模。這種選擇方式能使種群中適應(yīng)度好的個(gè)體具有較大的“生存”機(jī)會。同時(shí),由于它只使用適應(yīng)度的相對值作為選擇的標(biāo)準(zhǔn),而與適應(yīng)度的數(shù)值大小不成直接比例,從而避免了超級個(gè)體的影響,在一定程度上避免了過早收斂和停滯現(xiàn)象的發(fā)生。精英保留法是當(dāng)前種群中適應(yīng)度最好的個(gè)體,它不參加遺傳操作,可直接復(fù)制到下一代,替換經(jīng)交叉和變異操作產(chǎn)生的子種群中適應(yīng)度最差的個(gè)體,其優(yōu)點(diǎn)是在搜索過程中可以使某一代最優(yōu)個(gè)體不被遺傳操作所破壞,這樣可保證遺傳算法以概率收斂到最優(yōu)解。經(jīng)驗(yàn)證明,保留占種群總體2%~5%數(shù)量的個(gè)體,效果最為理想。

(2)交叉算子。采用單點(diǎn)交叉法,在兩個(gè)父體上分別隨機(jī)選取一個(gè)交叉點(diǎn)(起點(diǎn)和終點(diǎn)除外),交換兩個(gè)個(gè)體在各自交叉點(diǎn)之后的染色體。考慮到規(guī)劃路徑的長度是可變的,為了防止交叉操作后出現(xiàn)過于繁瑣或簡單的路徑,對生成的新個(gè)體長度進(jìn)行限制,即最大長度不能超過Nmax,并且不能產(chǎn)生回路,若不符合要求,重新獲取兩個(gè)父個(gè)體的交叉點(diǎn)。

(3)插入算子。設(shè)計(jì)了兩種插入算子。第一種是有針對性的,即在連線穿過障礙物的兩個(gè)轉(zhuǎn)向點(diǎn)之間插入一個(gè)或多個(gè)轉(zhuǎn)向點(diǎn),使產(chǎn)生的路徑避開障礙物,如圖1(a)所示;第二種是一般意義上的插入,以一定概率插入一個(gè)隨機(jī)產(chǎn)生的轉(zhuǎn)向點(diǎn),如圖1(b)所示。

(4)擾動(dòng)算子。同樣設(shè)計(jì)了兩種擾動(dòng)算子,第一種只選取路徑不可行的轉(zhuǎn)向點(diǎn)來進(jìn)行小范圍的調(diào)整,使其路徑可行,如圖1(c)所示;第二種是不管路徑是否可行,任意選取一個(gè)位置,以概率pm對其轉(zhuǎn)向點(diǎn)坐標(biāo)進(jìn)行調(diào)整。在進(jìn)化初期,不可行的解數(shù)量較多,調(diào)整的范圍大一些。在進(jìn)化后期調(diào)整范圍逐漸縮小,如圖1(d)所示。

(5)刪除算子。建立一個(gè)存儲空間REC,在一條路徑中,如果點(diǎn)(xi-1,yi-1)與點(diǎn)(xi,yi)的連線經(jīng)過障礙物,但(xi-1,yi-1)與(xi+1,yi-1)的連線不經(jīng)過障礙物,則將點(diǎn)(xi,yi)添加到REC中。如果REC不為空,則從中隨機(jī)選取一點(diǎn)刪除(見圖1(e));否則,在路徑中任意選取一個(gè)路徑點(diǎn),以概率pd進(jìn)行刪除,如圖1(f)所示。

(6)平滑算子。平滑算子只對可行路徑中最大的拐角進(jìn)行操作,如圖1(g)所示。刪除拐角α的頂點(diǎn)pj,依次連接點(diǎn)pj-1,p1,p2,pj+1構(gòu)成可行路徑段序列pj-1p1→p1p2→p2pj+1。

(7)倒位算子。隨機(jī)選取路徑中兩個(gè)中間轉(zhuǎn)向點(diǎn),顛倒之間的轉(zhuǎn)向點(diǎn)。倒位算子可使路徑發(fā)生急劇變化,對于轉(zhuǎn)向點(diǎn)較多的路徑會有積極的意義。通常的交叉和變異算子不易取得此種效果,而且倒位算子能修正遺傳進(jìn)化過程中可能出現(xiàn)的基因誤差,如圖1(h)所示。

1.6 遺傳算子概率選擇

選擇合適的遺傳算子執(zhí)行概率是遺傳算法能否收斂到最優(yōu)解的關(guān)鍵之一。在進(jìn)化過程的前期,群體中存在大量的不可行解,因而交叉算子、擾動(dòng)算子的概率應(yīng)該取得較大些,而平滑算子取較小的概率;隨著進(jìn)化過程的推進(jìn),可行解增多,應(yīng)適當(dāng)提高平滑算子的概率,以提高可行解的平滑性能。同時(shí),為了防止交叉算子和擾動(dòng)算子對可行解的破壞,需降低其執(zhí)行概率,并取較小的擾動(dòng)概率對可行解的形狀進(jìn)行微調(diào)。其中,擾動(dòng)算子(1)和插入算子(1)是對路徑轉(zhuǎn)向點(diǎn)的啟發(fā)式操作,都是針對不可行路徑的優(yōu)化調(diào)整,對于這些算子應(yīng)當(dāng)始終選擇較高的概率。插入算子(2)會使路徑的轉(zhuǎn)向點(diǎn)數(shù)量增加,應(yīng)當(dāng)取較小的概率。

1.7 終止條件

一般在對問題無知的情況下,可以在目標(biāo)函數(shù)達(dá)到一個(gè)可以承受的范圍內(nèi)之后,即終止算法。另外,還可設(shè)置最大進(jìn)化代數(shù),在給定的進(jìn)化代數(shù)之內(nèi)強(qiáng)行終止算法,從而保證運(yùn)算時(shí)間的要求。為了實(shí)用起見,在此采取最大進(jìn)化代數(shù)終止準(zhǔn)則,并選取適應(yīng)度最好的可行路徑。

1.8 算法流程

改進(jìn)后的基于小生境遺傳算法流程如圖2所示。具體算法描述如下:

(1)初始化種群,沿起點(diǎn)和終點(diǎn)連線方向等距離選取N個(gè)點(diǎn),在這些點(diǎn)的垂直線上隨機(jī)選取轉(zhuǎn)向點(diǎn)的縱坐標(biāo),并且使這些轉(zhuǎn)向點(diǎn)不在障礙物內(nèi);

(2)將每一代個(gè)體劃分為n個(gè)類,每個(gè)類中選出若干適應(yīng)度較大的個(gè)體,作為一個(gè)類的優(yōu)秀代表,組成一個(gè)種群。種群規(guī)模Gi(i=1,2,…,n+1);

(3)計(jì)算種群中所有個(gè)體的適應(yīng)度,將其最好的個(gè)體保留,然后采用錦標(biāo)賽選擇法,挑選父個(gè)體,以執(zhí)行交叉操作,并且檢查獲得的子代個(gè)體染色體長度是否超過N,如果沒有超過,則保留,否則丟棄。

(4)以設(shè)定的概率對新產(chǎn)生的子代個(gè)體進(jìn)行變異、插入、擾動(dòng)、刪除、平滑的操作。此過程中,采取預(yù)選擇機(jī)制,比較子串和父串適應(yīng)度的大小,如果子串的適應(yīng)度高于父串的適應(yīng)度,就替換父串;否則維持父串不變;

(5)重復(fù)第(3)和第(4)步直到獲得的新個(gè)體數(shù)量與父代群體數(shù)量相等;

(6)用保留的上一代最優(yōu)個(gè)體替換新種群中適應(yīng)度最差的個(gè)體;

(7)檢查算法停止條件。符合則中止,否則跳轉(zhuǎn)至第(3)步,算法繼續(xù)進(jìn)行。


2 仿真

移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃設(shè)計(jì)的環(huán)境信息主要包括移動(dòng)機(jī)器人活動(dòng)區(qū)域內(nèi)的各種障礙物信息識別。本文視各種障礙物都為不可行區(qū)域,并以任意形狀的多邊形來表示。在VC 2005環(huán)境中,對以上算法進(jìn)行仿真。選取算法參數(shù)為路徑最大轉(zhuǎn)向點(diǎn)數(shù)30,初始轉(zhuǎn)向點(diǎn)數(shù)20,種群大小100,錦標(biāo)賽規(guī)模取5,最大進(jìn)化代數(shù)G=80。在算法的前20代中,交叉概率pc=0.6,擾動(dòng)概率pm=0.6,插入算子2pi=0.6,平滑算子概率ps=0.1;在20代以后pc=0.1,pm=0.2,pi=0.01,ps=0.7。

在算法的初始階段,由于轉(zhuǎn)向點(diǎn)較多,因此刪除概率應(yīng)當(dāng)取大一些,這樣可以使轉(zhuǎn)向點(diǎn)數(shù)量減少,從而縮小路徑的長度;但在算法后期,路徑點(diǎn)已經(jīng)較少,再使用較大的刪除概率,容易使算法陷入局部解,且收斂到最優(yōu)解的概率大大減少,因此進(jìn)化后期的刪除概率應(yīng)減少,保證路徑的多樣性。初始刪除概率選0.8,大約20代以后,選取0.1,而擾動(dòng)算子1和插入算子1的概率始終為0.8。選取兩種不同的環(huán)境(見圖3),分別運(yùn)行上述算法各10次,選出效果最好的路徑顯示在圖3(a)、圖3(b)中。從圖3中可以看出,改進(jìn)后的遺傳算法對各種環(huán)境都有良好的適應(yīng)性。其中,圖3(a)的情況最簡單,只用了19代就得到了最優(yōu)結(jié)果;圖3(b)進(jìn)化了36代后;收斂到最優(yōu)解。

為了與標(biāo)準(zhǔn)遺傳算法的性能進(jìn)行對比,分別使用本文算法和標(biāo)準(zhǔn)遺傳算子對環(huán)境一和二進(jìn)行實(shí)驗(yàn)。標(biāo)準(zhǔn)遺傳算法的選擇采用錦標(biāo)賽選擇法,其交叉概率、變異概率與本文算法相同,運(yùn)行結(jié)果如表1和表2所示。

從表1,表2中數(shù)據(jù)可以看出,不管是運(yùn)行時(shí)間,還是收斂的路徑長度,本文算法都優(yōu)于標(biāo)準(zhǔn)遺傳算法。主要是由于本文算法針對規(guī)劃路徑有針對性地設(shè)計(jì)了新的遺傳算子,從而加快了進(jìn)化的速度,更容易收斂到最優(yōu)解。

3 結(jié) 語

采用基于預(yù)選擇機(jī)制的小生境技術(shù),且基于啟發(fā)式知識來設(shè)計(jì)遺傳算子。對標(biāo)準(zhǔn)遺傳算法進(jìn)行了改進(jìn)和擴(kuò)充,并應(yīng)用于移動(dòng)機(jī)器人行走的路徑規(guī)劃。該算法同時(shí)兼顧了遺傳進(jìn)化的快速性和群體的多樣性,有效地抑制了“早熟”現(xiàn)象的發(fā)生,能很好地搜索局部最優(yōu)解和全局最優(yōu)解。實(shí)驗(yàn)證明,該算法在不同的環(huán)境中都能夠在較小的進(jìn)化代數(shù)內(nèi)收斂到最優(yōu)解,算法的執(zhí)行速度和成功率明顯高于標(biāo)準(zhǔn)的遺傳算法。另外,在進(jìn)化的不同階段選取合適的交叉和變異概率對于進(jìn)化結(jié)果有著關(guān)鍵性的影響,本文將算法分成了兩個(gè)階段,分別設(shè)定了不同的遺傳操作概率,這種方式還比較簡單,不能完全適應(yīng)種群的變化情況。如何讓算法根據(jù)種群進(jìn)化情況自動(dòng)調(diào)整和優(yōu)化這些參數(shù),還需進(jìn)一步的研究和改進(jìn)。

.



評論


相關(guān)推薦

技術(shù)專區(qū)

關(guān)閉