摘要：針對(duì)遺傳算法具有全局搜索和收斂速度快的特點(diǎn)，在機(jī)器人控制器中實(shí)現(xiàn)遺傳算法，使機(jī)器人自主學(xué)習(xí)，不斷進(jìn)化，最后成功通過(guò)一個(gè)隨機(jī)的迷宮。在遺傳算法中引入精英個(gè)體，在每次進(jìn)化逐漸降低變異率與交叉率實(shí)現(xiàn)二次啟發(fā)，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法與傳統(tǒng)遺傳算法相比具有更快的尋優(yōu)速度。

關(guān)鍵詞：遺傳算法；二次啟發(fā)式；機(jī)器人控制器

引言

90年代，學(xué)術(shù)界出現(xiàn)了很多以復(fù)雜問(wèn)題為對(duì)象的新范疇，如NPC類型的組合優(yōu)化問(wèn)題與非線性多模型，遺傳算法是求解多目標(biāo)函數(shù)的優(yōu)化問(wèn)題的最佳工具之一[1]。遺傳算法的搜索空間可以涵蓋解空間的許多點(diǎn)并能快速收斂，它的這種特點(diǎn)使得它在智能領(lǐng)域中占有越來(lái)越重要的地位。通過(guò)在真實(shí)世界應(yīng)用程序中實(shí)現(xiàn)遺傳算法，人們有可能解決傳統(tǒng)計(jì)算方法幾乎不能解決的問(wèn)題[2]。

1機(jī)器人控制器的設(shè)計(jì)原理

機(jī)器人控制器通過(guò)傳感器的指令去導(dǎo)航機(jī)器人，本文設(shè)計(jì)的機(jī)器人控制器有6個(gè)傳感器，兩個(gè)在兩側(cè)，三個(gè)在前面，一個(gè)在后面，當(dāng)傳感器檢測(cè)到墻時(shí)會(huì)激活，它可以執(zhí)行四種動(dòng)作，向前一步，左轉(zhuǎn)，右轉(zhuǎn)，或者什么也不做。

物理上評(píng)估上圖所示的機(jī)器人控制器很難，并且所需的時(shí)間非常長(zhǎng)，評(píng)估規(guī)模比較大的種群中每個(gè)個(gè)體任務(wù)異常艱巨[3]。因此本文對(duì)機(jī)器人控制器的評(píng)估方法是，建立物理機(jī)器人和環(huán)境（迷宮）的模擬模型，這樣就能在軟件上快速評(píng)估每個(gè)控制器。用迷宮作為一個(gè)復(fù)雜的環(huán)境去測(cè)試機(jī)器人控制器，該迷宮由墻構(gòu)成，機(jī)器人不能穿墻，這是希望機(jī)器人遵循的[4，5]。

在機(jī)器人每次穿行中，由于迷宮中的“墻”是固定的，6個(gè)傳感器在機(jī)器人下次穿行中通過(guò)相同位置的狀態(tài)是不變的。本文要解決的問(wèn)題是當(dāng)機(jī)器人在某個(gè)位置時(shí)，如何基于傳感器的指令做出正確的動(dòng)作。由于機(jī)器人穿過(guò)的迷宮不同，傳感器的指令也不同，針對(duì)所有可能的指令對(duì)動(dòng)作進(jìn)行編碼，利用遺傳算法得出的結(jié)果去設(shè)計(jì)機(jī)器人控制器，并將其應(yīng)用于真實(shí)環(huán)境中的物理機(jī)器人。

2二次啟發(fā)式遺傳算法的實(shí)現(xiàn)

2.1編碼

首先對(duì)機(jī)器人所做出的四個(gè)動(dòng)作用二進(jìn)制表示。“00”表示什么也不做，“01”表示前進(jìn)，“10”表示左轉(zhuǎn)，“11”表示右轉(zhuǎn)。用二進(jìn)制表示機(jī)器人控制器的指令集，用“1”表示傳感器激活，“0”表示傳感器未激活。若只有前傳感器和左傳感器被激活，那么控制器的指令集為000011，從左到右依次為后傳感器，右傳感器，左傳感器，右前傳感器，左前傳感器，前傳感器的狀態(tài)。64個(gè)二進(jìn)制指令集轉(zhuǎn)換成十進(jìn)制對(duì)應(yīng)著0到63中的某一位數(shù)，因此基于傳感器的指令集按“位”對(duì)動(dòng)作進(jìn)行編碼。編碼的染色體一共有64組“動(dòng)作”，每一組代表著機(jī)器人控制器基于某個(gè)傳感器指令所做出的動(dòng)作。

2.2初始化種群

本文采用隨機(jī)的方法初始化種群，種群中每個(gè)個(gè)體將被隨機(jī)初始化，每個(gè)染色體由隨機(jī)產(chǎn)生1或0的128個(gè)基因構(gòu)成。

2.3評(píng)估并保留精英個(gè)體

在Java語(yǔ)言里，Maze類中的scoreRoute方法來(lái)對(duì)機(jī)器人的行走路線創(chuàng)建適應(yīng)度函數(shù)，機(jī)器人每經(jīng)過(guò)一次“3”位置，就可以增加個(gè)體的適應(yīng)度。calcfitness方法將Individual類（操作個(gè)體的類），Maze類，與Robot類聯(lián)系在一起，對(duì)機(jī)器人的行走路線進(jìn)行評(píng)分，并保存為個(gè)體的適應(yīng)度，并對(duì)種群中每個(gè)個(gè)體基于適應(yīng)度進(jìn)行排序，選出“精英個(gè)體”。

2.4 終止檢查

本文中的二次啟發(fā)式遺傳算法的終止條件有兩個(gè)。其一是迷宮中機(jī)器人最佳的行走路線被完全探索后終止，輸出最優(yōu)個(gè)體。另一個(gè)終止條件為允許算法運(yùn)行的最大世代數(shù)。

2.5 選擇

采用“輪盤賭”的方法選擇親代參與交叉。根據(jù)種群中每個(gè)個(gè)體的適應(yīng)度值，將他們放置在一個(gè)假想的輪盤上，個(gè)體的適應(yīng)度值越高它在輪盤所占的空間越多。本文采用反向?qū)崿F(xiàn)輪盤賭的選擇方法，我們?cè)谳啽P上“標(biāo)記”一個(gè)位置，然后旋轉(zhuǎn)輪盤等待“個(gè)體”落入。

2.6 交叉

在交叉過(guò)程中，種群的個(gè)體交換他們的遺傳信息創(chuàng)建一個(gè)新的個(gè)體，包含親代基因中最好的部分。本文采用的交叉方式為兩點(diǎn)交叉，在這種方法中，隨機(jī)選取基因組的兩個(gè)位置，確定哪些基因來(lái)自哪個(gè)親代。

2.7 變異

變異算子在二次啟發(fā)式遺傳算法中起到逃離局部最優(yōu)和取得接近最優(yōu)解的作用。本文采用“位翻轉(zhuǎn)”的變異方法完成對(duì)個(gè)體的變異，根據(jù)位的初始值，將1翻轉(zhuǎn)為0，將0翻轉(zhuǎn)為1。

2.2.6 二次啟發(fā)

在算法中更新變異率與交叉率實(shí)現(xiàn)二次啟發(fā)。從較高的比率開(kāi)始，隨著算法的進(jìn)行，逐漸降低變異率和交叉率[8]。

3 實(shí)驗(yàn)調(diào)試與結(jié)果分析

基于二次啟發(fā)式遺傳算法設(shè)計(jì)機(jī)器人控制器的原理，采用Java語(yǔ)言對(duì)算法進(jìn)行設(shè)計(jì)與實(shí)現(xiàn)。

3.1算法參數(shù)

Input：，迷宮實(shí)例，種群規(guī)模populationSize，變異率mutationRate，交叉率crossoverRate，精英個(gè)體的數(shù)量elitismCount，冷卻率coolingRate。

Output：每代種群中最優(yōu)個(gè)體的遺傳信息及適應(yīng)度值，完成進(jìn)化經(jīng)過(guò)的世代數(shù)，最優(yōu)個(gè)體的遺傳信息及其適應(yīng)度值。

initializeMaze；

3.2實(shí)驗(yàn)結(jié)果分析

參數(shù)設(shè)置：

種群規(guī)模：150，交叉率：0.85，變異率：0.04，精英個(gè)體數(shù)量：2，冷卻率：0.005，染色體長(zhǎng)度：128。

迷宮對(duì)象：10*10d的矩陣

程序代碼在idea軟件上運(yùn)行。輸入相應(yīng)的參數(shù)，多次運(yùn)行程序，。

3.2.1實(shí)驗(yàn)結(jié)果分析

取得或勝的染色體，將它編程寫入一個(gè)物理機(jī)器人，該傳感器控制器會(huì)做出適當(dāng)?shù)膭?dòng)作，在迷宮中穿行，并且在任何迷宮中，都不會(huì)撞墻，成功通過(guò)迷宮。

在本次實(shí)驗(yàn)的迷宮中，正確的位置“3”一共有34處，因此，最優(yōu)個(gè)體的適應(yīng)度應(yīng)為“34”，采用二次啟發(fā)的遺傳算法會(huì)加快尋優(yōu)速度，可以在更快更少的時(shí)間里找到最好的解。

4.結(jié)論

本文利用軟件模擬機(jī)器人及其環(huán)境，從而節(jié)省時(shí)間，也避免了人工設(shè)計(jì)的困難。利用改進(jìn)后的遺傳算法對(duì)機(jī)器人控制器進(jìn)行設(shè)計(jì)，引入“精英個(gè)體”的概念，在每次進(jìn)化中保留最適合的個(gè)體，直接加入到下一代種群中，使種群中最優(yōu)秀的遺傳信息不會(huì)在交叉與變異中丟失，同時(shí)在每次進(jìn)化中降低種群中兩個(gè)重要參數(shù)（交叉率和變異率）實(shí)現(xiàn)二次啟發(fā)，最初值較高的兩個(gè)參數(shù)，使得算法始終搜索解空間的大塊區(qū)域，隨著參數(shù)值降低，算法開(kāi)始專注搜索解空間中適應(yīng)度較高的區(qū)域。實(shí)驗(yàn)對(duì)比結(jié)果表明，改進(jìn)后的算法具有較快的尋優(yōu)速度。當(dāng)機(jī)器人傳感器數(shù)量增多，編碼任務(wù)會(huì)變得艱巨，種群規(guī)模變大，會(huì)使得進(jìn)化代數(shù)較多，運(yùn)行時(shí)間較長(zhǎng)，在今后的工作中應(yīng)加以改進(jìn)。

參考文獻(xiàn)

[1]劉曙光，費(fèi)佩燕，侯志敏.生物進(jìn)化論與人工智能中的遺傳算法[J].自然辯證法研究，1999

[2]David A.Grossman，Ophir Frieder.最新算法與啟發(fā)式算法[M].北京：人民郵電出版社，2010

[3]Lee Jacobson，Burak Kanber.Java遺傳算法編程[M]. 北京：人民郵電出版社，2016

[4]周明，孫樹(shù)棟，彭炎午. 使用遺傳算法規(guī)劃移動(dòng)機(jī)器人路徑[ J ]. 西北工業(yè)大學(xué)學(xué)報(bào)，1998

[5]孟慶鑫，王曉東.機(jī)器人技術(shù)基礎(chǔ)[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2006（9）：52-66

[6]孫樹(shù)棟，林茂.基于遺傳算法的多移動(dòng)機(jī)器人協(xié)調(diào)路徑規(guī) 劃[J].自動(dòng)化學(xué)報(bào)，2000，26（5）：672-676.

[7]唐飛，滕弘飛.一種改進(jìn)的遺傳算法及其在布局優(yōu)化中的應(yīng)用 [ J ] .軟件學(xué)報(bào)，1999，10（10）：1096-1102.

[8]周明，孫樹(shù)棟，彭炎午，基于遺傳模擬退火算法的機(jī)器人路徑規(guī)劃[J].航空學(xué)報(bào)，1998，19（1）：115-120.

作者簡(jiǎn)介：王迪，男，1994年8月5日，吉林省白山市，研究方向：物聯(lián)網(wǎng)。

（作者單位：西南民族大學(xué)電氣信息工程學(xué)院）