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

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

引言

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

1機器人控制器的設計原理

機器人控制器通過傳感器的指令去導航機器人，本文設計的機器人控制器有6個傳感器，兩個在兩側，三個在前面，一個在后面，當傳感器檢測到墻時會激活，它可以執(zhí)行四種動作，向前一步，左轉，右轉，或者什么也不做。

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

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

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

2.1編碼

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

2.2初始化種群

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

2.3評估并保留精英個體

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

2.4 終止檢查

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

2.5 選擇

采用“輪盤賭”的方法選擇親代參與交叉。根據(jù)種群中每個個體的適應度值，將他們放置在一個假想的輪盤上，個體的適應度值越高它在輪盤所占的空間越多。本文采用反向實現(xiàn)輪盤賭的選擇方法，我們在輪盤上“標記”一個位置，然后旋轉輪盤等待“個體”落入。

2.6 交叉

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

2.7 變異

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

2.2.6 二次啟發(fā)

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

3 實驗調試與結果分析

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

3.1算法參數(shù)

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

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

initializeMaze；

3.2實驗結果分析

參數(shù)設置：

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

迷宮對象：10*10d的矩陣

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

3.2.1實驗結果分析

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

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

4.結論

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

參考文獻

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

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

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

[4]周明，孫樹棟，彭炎午. 使用遺傳算法規(guī)劃移動機器人路徑[ J ]. 西北工業(yè)大學學報，1998

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

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

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

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

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

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