“機(jī)器人”路徑改進(jìn)型單親遺傳算法規(guī)劃及其仿真

彭 麗，洪 亮

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

?

“機(jī)器人”路徑改進(jìn)型單親遺傳算法規(guī)劃及其仿真

彭 麗，洪 亮

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

在中國(guó)機(jī)器人大賽“機(jī)器人游中國(guó)”比賽項(xiàng)目的路徑規(guī)劃基礎(chǔ)上，為克服遺傳算法在有約束組合優(yōu)化問(wèn)題中計(jì)算效率不高的問(wèn)題，提出了改進(jìn)的單親遺傳算法.該算法在傳統(tǒng)單親遺傳算法的計(jì)算步驟中，引入了交換算子、提前算子和修復(fù)算子，較大程度地提高了單親遺傳算法的搜索效率.Matlab仿真試驗(yàn)表明，改進(jìn)的單親遺傳算法計(jì)算效率和路徑規(guī)劃能力得到大幅度提高.

單親遺傳算法；機(jī)器人；路徑規(guī)劃

“機(jī)器人游中國(guó)”比賽項(xiàng)目包含16個(gè)景點(diǎn)，其景點(diǎn)位置參照地圖放置，每個(gè)景點(diǎn)對(duì)應(yīng)不同的分值，分值的高低由到達(dá)該景點(diǎn)的難易程度決定.比賽要求“機(jī)器人”在60 s時(shí)間內(nèi)游歷至少1個(gè)景點(diǎn)后返回出發(fā)點(diǎn)，得分多者獲勝[1].要想在“機(jī)器人游中國(guó)”比賽中取得良好的成績(jī)，機(jī)器人的路徑規(guī)劃能力是比賽獲勝的關(guān)鍵.

遺傳算法是一種常用的路徑規(guī)劃方法，適合解決無(wú)約束的函數(shù)優(yōu)化問(wèn)題.然而，對(duì)于“機(jī)器人游中國(guó)”路徑規(guī)劃這樣有約束的組合優(yōu)化問(wèn)題，其計(jì)算效率不高.文獻(xiàn)[2]中提出了單親遺傳算法概念，其遺傳操作中沒(méi)有交叉算子，所有操作只作用于單個(gè)染色體，與其他染色體沒(méi)有關(guān)系.序號(hào)編碼的遺傳算法采用交叉操作，出現(xiàn)基因重復(fù)或者基因缺失的現(xiàn)象[3-4].單親遺傳算法正好彌補(bǔ)這一缺陷，在處理復(fù)雜的工程優(yōu)化問(wèn)題時(shí)，單親遺傳算法能快捷地處理約束條件.

1 基于路徑規(guī)劃的遺傳算法

1.1 環(huán)境信息的表示

圖1 “機(jī)器人游中國(guó)”競(jìng)賽地圖

組委會(huì)提供的“機(jī)器人游中國(guó)”競(jìng)賽地圖如圖1所示.對(duì)競(jìng)賽地圖中景點(diǎn)之間的距離進(jìn)行量化，制作景點(diǎn)之間的計(jì)算距離表[1].

1.2 路徑編碼

路徑編碼影響遺傳算法的計(jì)算性能.“機(jī)器人游中國(guó)”比賽項(xiàng)目的路徑規(guī)劃問(wèn)題將采用序列號(hào)進(jìn)行編碼，先對(duì)每個(gè)景點(diǎn)進(jìn)行編號(hào)，之后對(duì)編號(hào)進(jìn)行無(wú)重復(fù)隨機(jī)排列，其個(gè)體即為移動(dòng)機(jī)器人從開(kāi)始出發(fā)并游完某些景點(diǎn)再回到出發(fā)點(diǎn)的一條路徑.

1.3 目標(biāo)函數(shù)和適應(yīng)度函數(shù)

根據(jù)組委會(huì)的比賽規(guī)則可得到參賽機(jī)器人得分公式[5]，該公式即為路徑優(yōu)化問(wèn)題的目標(biāo)函數(shù).算法的約束條件為比賽時(shí)間60 s，參賽“機(jī)器人”的目的是在這60 s內(nèi)得到盡量多的分值，每個(gè)個(gè)體的適應(yīng)度大小就是所得到的分值.得分公式既是目標(biāo)函數(shù)，也是個(gè)體適應(yīng)度函數(shù).適應(yīng)度越高，得分越高.高分的個(gè)體將留下來(lái)繼續(xù)進(jìn)行迭代，低分的個(gè)體則被淘汰.

2 改進(jìn)的單親遺傳算法

2.1 交換算子

基因交換算子是基因之間進(jìn)行位置交換的一種遺傳操作.它有3種交換方式：基因片段的內(nèi)部交換(圖2)，內(nèi)部的基因“5”和基因“7”進(jìn)行位置交換；基因片段的外部交換(圖3)，基因片段“5，6，7”和基因“c4”進(jìn)行位置交換；基因片段的整體交換(圖4)，基因片段“5，6，7”和基因片段“c1，c2，c3，c4”進(jìn)行整體交換.2.2 提前算子

提前算子先確定個(gè)體中某些被提前的優(yōu)良基因片段，并對(duì)其進(jìn)行保護(hù)，最后進(jìn)行適當(dāng)?shù)奶崆安僮?圖5).因此，提前算子有保護(hù)和提前2個(gè)操作步驟.提前算子使優(yōu)良基因被利用起來(lái)，能更好地提高計(jì)算效率.

2.3 修復(fù)算子

某些個(gè)體經(jīng)歷了很多操作后，可能變成不可行解，修復(fù)算子能對(duì)這樣的個(gè)體進(jìn)行修復(fù)操作，使被淘汰個(gè)體重新回到種群中，從而大大提高計(jì)算效率.

3 Matlab仿真測(cè)試

3.1 遺傳算法仿真

圖6 旅行路徑1

遺傳算法的初始種群一般是由計(jì)算機(jī)隨機(jī)生成的.針對(duì)“機(jī)器人游中國(guó)”比賽項(xiàng)目，計(jì)算機(jī)隨機(jī)生成的初始種群將出現(xiàn)某些個(gè)體中有重復(fù)序號(hào)現(xiàn)象，這些個(gè)體將直接成為不可行解.因此，初始群體只能由所有序號(hào)進(jìn)行無(wú)重復(fù)隨機(jī)排列來(lái)產(chǎn)生，種群大小一般取20個(gè)左右.運(yùn)用比例選擇算子進(jìn)行選擇運(yùn)算時(shí)，采用先“繁殖”后選擇的方式進(jìn)行，這種方式計(jì)算效率更高.遺傳算子選用比例選擇算子和CX交叉算子[5]進(jìn)行變異操作，交叉概率可以取0.7～0.9，變異概率一般取0.1左右.采用傳統(tǒng)遺傳算法進(jìn)行多次仿真的最優(yōu)結(jié)果見(jiàn)圖6.由圖6可知，最佳“機(jī)器人”共經(jīng)過(guò)了12個(gè)景點(diǎn)，旅途中花費(fèi)時(shí)間累計(jì)54 s，得分271分.

改變初始種群，加入文獻(xiàn)[1]中由啟發(fā)式路徑規(guī)劃算法得到的最優(yōu)解(291分)，遺傳算法的計(jì)算步驟、終止條件和遺傳操作都不變.再運(yùn)行Matlab仿真，仿真結(jié)果表明，經(jīng)過(guò)多次迭代，得到的最好結(jié)果還是由啟發(fā)式路徑規(guī)劃算法得到的最優(yōu)解(291分)，即沒(méi)能產(chǎn)生更優(yōu)秀的個(gè)體，沒(méi)有完成路徑規(guī)劃問(wèn)題的優(yōu)化.

3.2 單親遺傳算法仿真

圖7 旅行路徑2

采用無(wú)重復(fù)序號(hào)隨機(jī)排列方式產(chǎn)生初始種群，并使用新構(gòu)造的3種遺傳算子更新種群中的個(gè)體.在進(jìn)行交換操作時(shí)，取基因整體交換概率為0.1，基因內(nèi)部交換和外部交換概率為0.45，即每次迭代時(shí)只使用3種交換方式中的一種.由于基因整體交換對(duì)提高搜索效率意義不大，因此基因整體交換概率取得比較小.提前算子針對(duì)優(yōu)良基因片段進(jìn)行保護(hù)并適當(dāng)提前.經(jīng)多次實(shí)驗(yàn)，基因片段提前概率取0.7左右比較合適.需要修復(fù)的染色體無(wú)法預(yù)判，為保險(xiǎn)起見(jiàn)取修復(fù)概率為0.99，迭代次數(shù)G=1 000.這樣對(duì)每個(gè)個(gè)體進(jìn)行修復(fù)操作時(shí)，及早迭代產(chǎn)生優(yōu)良個(gè)體，從而提高計(jì)算效率.

采用改進(jìn)的單親遺傳算法進(jìn)行多次仿真的最優(yōu)結(jié)果如圖7所示.由圖7可知，游歷11個(gè)景點(diǎn)共用時(shí)58 s，得分301分.同樣對(duì)初始種群進(jìn)行變換，在原來(lái)的初始種群中加入優(yōu)良個(gè)體，單親遺傳算法的其他條件都不變，對(duì)新初始種群的改進(jìn)單親遺傳算法進(jìn)行仿真實(shí)驗(yàn)，得到最優(yōu)解的旅行路徑和沒(méi)有改變初始種群時(shí)所得到的旅行路徑完全相同(圖7)，得分也是301分.當(dāng)初始種群中包含優(yōu)良個(gè)體時(shí)，迭代次數(shù)大大減少，計(jì)算時(shí)間縮短了，也就在一定程度上提高了計(jì)算效率.

3.3 仿真結(jié)果分析

在無(wú)重復(fù)序號(hào)隨機(jī)排列所產(chǎn)生的初始種群中，改進(jìn)的單親遺傳算法和傳統(tǒng)遺傳算法的仿真計(jì)算結(jié)果分別為301分和271分；當(dāng)初始種群中加入優(yōu)良個(gè)體時(shí)，改進(jìn)的單親遺傳算法和遺傳算法的仿真結(jié)果分別為301分和291分.仿真結(jié)果表明：傳統(tǒng)的遺傳算法在解決路徑規(guī)劃問(wèn)題時(shí)，雖能發(fā)揮其作用，但效果并不理想.究其原因是，常規(guī)變異算子和交叉算子不適合序號(hào)編碼的傳統(tǒng)遺傳算法，且計(jì)算效率很低，經(jīng)過(guò)多次迭代才能搜索到一個(gè)得分無(wú)明顯優(yōu)勢(shì)的可行解.因此，傳統(tǒng)遺傳算法所得最優(yōu)解(非全局最優(yōu)解)在比賽中沒(méi)有競(jìng)爭(zhēng)力.當(dāng)初始群體中有較好的可行解時(shí)，傳統(tǒng)遺傳算法優(yōu)化作用不能凸現(xiàn)出來(lái)，而改進(jìn)的單親遺傳算法不論在初始群體中有無(wú)優(yōu)良個(gè)體，都能通過(guò)各種遺傳操作搜索到問(wèn)題的最優(yōu)解.

4 結(jié)語(yǔ)

針對(duì)“機(jī)器人游中國(guó)”的實(shí)際路徑規(guī)劃問(wèn)題提出的改進(jìn)單親遺傳算法，不但繼承了傳統(tǒng)遺傳算法的優(yōu)良性能，而且有其自身獨(dú)特的高效搜索能力.構(gòu)造的3種遺傳算子能提高搜索效率，且算法的所有遺傳操作只針對(duì)一個(gè)個(gè)體，操作簡(jiǎn)單，它能搜索到最優(yōu)解，從而達(dá)到路徑規(guī)劃的目的.Matlab仿真結(jié)果驗(yàn)證了改進(jìn)的單親遺傳算法針對(duì)“機(jī)器人游中國(guó)”所設(shè)計(jì)的遺傳算子解決路徑規(guī)劃問(wèn)題的有效性和合理性.

[1] 彭 麗，李茂軍.“機(jī)器人游中國(guó)”路徑優(yōu)化方法[J].工業(yè)控制計(jì)算機(jī)，2012，25(12):1-3.

[2] 李茂軍.單親遺傳算法理論及應(yīng)用[D].長(zhǎng)沙：湖南大學(xué)電氣與信息工程學(xué)院,2002:13-23.

[3] 彭 麗.基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)電氣與信息工程學(xué)院,2013:25-37.

[4] 姜明洋.基于遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃方法的研究[D].沈陽(yáng)：沈陽(yáng)理工大學(xué)信息學(xué)院，2008：6-42.

[5] TIAN Lianfang，COLLINS C.An Effective Robot Trajectory Planning Method Using a Genetic Algorithm[J].Mechatronics,2004，14(5)：455-470.

(責(zé)任編輯 陳炳權(quán))

Robot Path Planning Based on Improved Partheno-Genetic Algorithm

PENG Li,HONG Liang

(College of Information Science and Engineering,Jishou University,Jishou 416000,Hunan China)

The improved partheno-genetic algorithm is proposed based on the path planning in the Chinese Robot Competition “Robot Tourism in China”,which is aimed at the problem of low computational efficiency of constrained combinational optimization.Three genetic operators of partheno-genetic algorithm-commutating operator,operator in advance,and repair operator,were established without changing the calculation steps of traditional partheno-genetic algorithm;as a result,the search efficiency of partheno-genetic algorithm is largely improved.Simulation experiment shows that compared with genetic algorithm，the proposed improved partheno-genetic algorithm has greatly increased computation efficiency and path planning ability.

partheno-genetic algorithm；robot；path planning

1007-2985(2015)04-0037-03

彭 麗(1987—)，女，湖南益陽(yáng)人，吉首大學(xué)信息科學(xué)與工程學(xué)院教師，碩士，主要從事智能控制和機(jī)器人研究.

TP249

A

10.3969/j.issn.1007-2985.2015.04.010