改進的進化算法于服務機器人仿真賽中的應用

李劍平，陳 瑋，陳樹斌

（廣東工業大學 自動化學院，廣東 廣州 510006）

0 引 言

家庭服務機器人仿真比賽立足于探索服務機器人的高層功能的，目前主要包括人機對話、自動規劃和推理等。將服務機器人實體抽象為3D 仿真機器人，并通過建立仿真的室內環境為測試環境，將人機交流抽象為自然語言或命令語言表達的任務描述，將機器人對環境的感知數據抽象為文件格式的場景描述，從而便于研究服務機器人的高層功能［1］。在比賽當中要求求解程序對比賽平臺提出的問題，根據其場景描述、任務描述、補充信息、約束信息等，在規定時間內自動規劃生成完成該任務的原子行動序列，比賽平臺將根據這些行動序列的性能給求解程序打分［2］。

在家庭服務機器人仿真比賽中，每次任務會有多個目標，機器人通過達到各個目標來達到服務效果，從而獲得比賽的分數。而完成同樣的任務可以有多種的方式，完成的順序不限，且可以在完成一個目標的過程中穿插完成其他目標。所以這就對機器人的規劃提出了要求，即如何用最少的動作，最簡潔的方式來完成任務，從而讓服務機器人的服務更加智能化，進而在比賽中取得更高的分數。

各參賽隊伍的規劃方式有很多種，如A＊算法、ASP回答集編程、貪心算法等等。這些算法各有優劣，A＊算法基于整個場景的狀態轉換計算，計算速度良好、可以得到較優的規劃，但其占用系統資源多，且不能良好地處理物品選擇問題；ASP 回答集編程利用窮舉法并加以篩選，規劃較為完善，但處理較長的任務時計算時間過長，有時不能在比賽規定時間范圍內完成規劃；貪心算法雖然計算速度快，但容易陷入局部最優值，不能得到全局最優解，規劃效果差。

1 進化算法

1.1 進化算法簡介

進化算法（evolutionary algorithm，EA）是一類隨機優化算法，其中包括遺傳算法（GA）、進化策略（ES）和進化規劃（EP）等。它們利用某些啟發式規則進行優化，其思想根源來自于進化論［3］。國內外許多大學及科研機構的研究人員正在努力從事這方面的研究，而對進化算法的改進也層出不窮，如混合混沌進化算法［4］、動態位置可變進化算法［5］、多智能體混合進化算法［6］等等。

1.2 進化算法一般步驟

（1）進行編碼，將待解決的問題轉化為進化算法便于計算的形式；

（2）產生初始種群；

（3）進行交叉、變異等計算產生新的個體；

（4）使用適應度函數對種群內的個體進行評價；

（5）選擇種群中優化程度更高的個體作為新一代種群；

（6）若未達到穩定的最優解則返回第三步再次進化；

（7）得到最優解后解碼輸出結果。

1.3 新結構建立的必要性

為了使家庭服務機器人的規劃問題轉化為便于進化算法的計算，需要找到一個合適的結構作來描述機器人的任務，從而以之作為基礎進行規劃。

在家庭服務機器人仿真比賽中，任務的目標多種多樣，為達到目標所需做出的動作也有很多的變化，下面給出某一個任務的例子和可能用來完成任務的一種方法，見表1。

表1 機器人規劃范例

例中目標數量為6，若以目標為規劃基礎，對其進行排序規劃，其情況種類較少，且不能在完成某個目標過程中穿插完成其他目標，因而規劃效果不佳。而動作輸出的條數和內容都不定，且動作較多，計算復雜度高，也不適合作為規劃的基礎。

可見，基于目標的規劃或者基于動作的規劃效果和效率不會很高，因此本文將引入一個介于兩者之間的新的結構，作為規劃的基礎。這個結構需要達到歸一化的效果，并能完整地表示任務中的信息，且有一定的操作空間，便于對其進行評價，適合以進化算法進行優化，最終還能方便地解析成動作序列。

2 算法的改進

本文利用傳統的進化算法進行改進，根據比賽需求建立新的編碼方式，采用獨特的交叉變異方法，使其在家庭服務機器人的行動規劃中發揮效用。

2.1 事件結構與編碼

本文把所有類型的目標都轉化為若干個四位結構，稱為事件或step。其結構如下：

step（getorput，objnum，objplace，inornot）

其中：getorput表示事件類型是一個拿取或放下小物體、又或與小物體無關的事件。

objnum 表示事件中涉及小物體的編號。

placenum 表示事件中涉及地點（大物體）的編號。

inornot表示是否存在一些內部包含的狀態。

而編碼即是把任務目標轉化為這種事件結構，例如：Puton（green can，teapoy）.其中green can的編號為17，初始位置為3，且在大物體內部，teapoy位置為7的話。那么其即可轉化為兩條事件結構即step0（getorput＝1，objnum＝17，placenum＝3，inornot＝1），step1（getorput＝－1，objnum＝17，placenum＝7，inornot＝0）.其他目標也可依照類似規則轉化為事件結構，于是規劃問題轉化為對事件結構的排序問題。

2.2 生成初始種群

傳統進化算法的初始種群產生方法為隨機產生，但這樣并不能保證全面性，特別是在家庭服務機器人仿真比賽中，需要規劃的參數較多，不僅是事件結構的順序，物品選擇方面也需要利用進化算法進行規劃，所以盡量在初始種群保持一定的全面性。

因此，本文采用了條件隨機生成的方式。在每種可能的物品選擇情況下，隨機產生若干個初始個體，個體內的事件結構隨機排序，并經過序列篩選（見2.4.1）作為進化算法的初始種群μ。

2.3 交叉與變異

交叉和變異是進化算法中種群進化的重要方式，通過交叉、變異計算，產生新的種群，從而豐富種群的多樣性，探索更優化的策略。通常進化算法中的交叉操作，是隨機取兩個染色體進行單點交叉操作［7］，而變異操作是指對個體編碼串隨機指定某一位或某幾位基因作變異運算［8］。

2.3.1 交叉進化

為了解決排序問題，本文把傳統的異體同位交叉轉化成為自體異位交叉的模式，即在進行交叉進化時，個體中的任意m個事件對以交叉概率p進行位置互換，從而產生新的個體。其中交叉事件對個數m和交叉概率p與當前個體的適應度有關。即

式中：p——單對事件發生交叉的概率；μ——交叉率，取值和進化速度及穩定性有關；S——該個體的代價值；n——一個個體中事件的個數。

圖1 交叉進化圖例

發生交叉進化的概率p 與交叉率μ和代價值S 正相關，與事件個數n 負相關。由于代價值S 與優化程度負相關，即代價值S 越小則說明該個體的優化程度越高，需要發生交叉的概率則越小，反之亦然。而代價值S的計算與事件個數n 有關，因而加入n 以消除事件數量對交叉發生概率的影響。交叉率μ的值越大則進化速度越快，同時穩定性降低，反之則進化速度降低，但穩定性增強，需根據情況進行選擇。

2.3.2 變異進化

物品選擇是機器人規劃中十分重要的一點，也是家庭服務機器人仿真比賽中必須考慮的部分。利用進化算法的變異進化可以有效地解決物品選擇的問題，當然也需要對其進行一定程度的改變。

由于是用于物品選擇，所以變異的參數以objnum為線索，其變異的范圍也是限定的，為可以完成目標的同類物品，其發生變異的概率為q。當某條事件的objnum 改變時，該事件內的placenum和inornot 也依照情況根據小物體的狀況而變化。且當仍有其他事件涉及同樣的小物體時，該事件的小物體也隨之而改變，即相當于一種成對變異的效果

式中：q——單個事件發生變異的概率；θ——變異率，取值和進化速度及穩定性有關；k［t］——目標小物體的可選擇個數；S——該個體的代價值；n——一個個體中事件的個數。

圖2 變異進化圖例

在公式中，θ、S、n的意義和選擇與交叉進化時相似，而k［t］則表示了該事件所用來完成的目標涉及的小物體的可選擇數量。當可選擇數量越多時，即k［t］越大時，需對變異進化進行促進，因而q越大，反之亦然。

由于交叉進化有可能會產生不能正確完成任務的事件序列，這部分序列會在序列的篩選中被刪除，因而要產生較多的下一代種群以備選擇，需要進行兩次獨立的進化產生2μ個子代種群，則整體種群數量變為3μ。

2.4 適應度函數與選擇

適應度函數是進化算法非常重要的組成部分，整個進化算法就是在適應度函數的引導下進行的，適應度函數對個體的評價直接影響了選擇，從而決定了整個群體的進化方向［9］。

2.4.1 序列的篩選

由于機器人的能力限制，以及一些動作之間固有的邏輯關系，通過隨機生成或經過進化的事件序列并不都是合法的，其中很大一部分會與規則或邏輯沖突。這部分序列是不能正確地完成任務的，對其進行適應度評價也毫無意義，因而要在評價前將其從種群中移除。

如：規則規定機器人同時只能攜帶兩個或兩個以下的小物體，因而違反此規定的事件序列視為違規，應予以刪除；當事件序列中涉及對同一物體的拿取事件和放下事件時，邏輯上拿取事件必須出現在放下事件之前，否則視為不合邏輯，應予以刪除。以及諸如此類其他違反規則或邏輯的事件序列都刪除處理，并且每次進化一代之后都進行一次序列的篩選。

2.4.2 適應度函數

本方法適應度函數采取代價累加的方式計算，根據事件結構的內容、機器人的狀態、場景狀態、需要維持的約束等等，結合類似罰函數的方法，計算出完成任務所需付出的代價（S）［10］。計算得出的代價值越高，則說明適應度越低，相反代價值越低，說明適應度越高。代價值計算具體公式如下

其中：S為該序列的代價值；

n為該序列包含的事件個數；

m、a、c為移動、動作、約束的代價權值；

x為特殊情況代價變化。

公式中的m、a、c權值是根據比賽規則對移動、動作、約束的評分系統而設定的，分別設為3、1、5。αi表示該事件是否有進行移動的需求，其為0或1二值，與機器人的當前位置和事件發生地點有關；βi 表示為完成該事件所需做出動作的復雜度，與事件的內容、機器人的狀態、環境狀態有關，是強非線性的映射關系；γi表示本次事件違反約束的量，需要根據事件本身的內容和約束列表得出。變量x為某些特殊情況對整體代價值的影響，例如事件結束時機器人狀態剛好位于goto任務目標地點等等。

由此方法計算出的代價值與適應度成負相關，相關使用和操作也與適應度相反。

2.5 種群的選擇

依照此規則對種群中每個個體進行計算以測試新種群，選擇其中w 值最高的μ個個體作為下一代的初始種群。

2.6 終止條件與解碼

本算法利用代價計算函數作為終止條件，當連續三代種群最低代價相同時，即視為達到相對最優解，隨即終止進化，當前種群中的最佳個體作為規劃結果。

當進化過程結束，選出了相對最優解之后，即進入解碼過程。將排好序的事件結構結合機器人狀態、場景狀態等，轉化成機器人最終執行的動作序列，見表2。

表2 解碼范例

至此，整個機器人規劃過程結束。

3 實驗與結果

實驗素材為2011中國服務機器人大賽指令語言仿真組和自然語言仿真組比賽用題，每組包含兩個階段（stage），每個階段50個任務，每個任務包含若干個目標和約束等，算法應用于我校GDUT＿TiJi隊，并取8個其他學校參賽隊為參照系，各參賽隊采用A＊算法、ASP 回答集編程等完全獨立的方法。其中stage1只包含目標，而stage2包含目標及約束，更為復雜，對規劃的要求更高。實驗結果包含整組題目的對照情況，以及對具體單個題目比較的統計數據。

表3中score為各隊單個階段得分，higher為該隊單題得分超過我隊的題目數，lower為該隊單題得分低于我隊的題目數，different為單個階段得分差，rank為該隊在比賽中的排名。

由實驗結果可以看出，該結構算法在家庭服務機器人仿真比賽中應用良好，得分高于其他隊的題目很多，而得分低于其他隊的題目則相對較少，且在狀況更復雜的第二階段能取得更好的成績，成功達到規劃效果。使用這個方法，我校GDUT＿TiJi隊在2012中國服務機器人大賽中取得了指令語言組季軍、自然語言組亞軍的成績，再一次證明了這個方法的實用性。

4 結束語

本方法提出了事件結構描述家庭服務機器人的任務，構建了一種代價函數還對機器人的行動進行評價，且改進了進化算法的進化方式以適應這種事件結構。并通過實驗和比賽也驗證了這個方法的穩定性和有效性。

其算法還有很多方面有待進一步探討，比如事件結構的細化優化、參數的選取、加入啟發式搜索方法等等，需要在今后的研究中繼續探索。

表3 實驗結果

［1］RoboCup＠home Rule 2011［Z］.2011（in Chinese）.［2011中國服務機器人大賽仿真比賽規則［Z］.2011.］

［2］JI Jianmin.Several ways of improve the ASP efficiency and application on service robot［D］.Hefei：University of Science and Technology of China，2010（in Chinese）.［吉建民.提高ASP效率的若干途徑及服務機器人上應用［D］.合肥：中國科學技術大學，2010.］

［3］HUANG Han，LIN Zhiyong.Convergence analysis and comparison of evolutionary algorithms based on relation model［J］.Chinese Journal of Computers，2011，34（5）：801－811（in Chinese）.［黃翰，林智勇.基于關系模型的進化算法收斂性分析與對比［J］.計算機學報，2011，34（5）：801－811.］

［4］HAO C Y M Z C.A hybrid chaotic quantum evolutionary algorithm［J］.Intelligent Computing and Intelligent Systems，2010：771－776.

［5］Woldesenbet Y G Y G G.Dynamic evolutionary algorithm with variable relocation［J］.Evolutionary Computation，2009.13（3）：500－513.

［6］ZHENG X G J.Multi－agent based hybrid evolutionary algorithm［J］.Natural Computation，2011（2）：1106－1110.

［7］DENG Zexi，CAO Dunqian.New differential evolution algorithm［J］.Computer Engineering and Applications，2008，44（24）：40－42（in Chinese）.［鄧澤喜，曹敦虔.一種新的差分進化算法［J］.計算機工程與應用，2008，44（24）：40－42.］

［8］WANG Shuaiqiang.A novel method for behavioral model refinement and learning to rank based on evolutionary algorithm［D］.Jinan：Shandong University，2009（in Chinese）.［王帥強.基于進化計算的行為模型自動精化和排序學習方法的研究［D］.濟南：山東大學，2009.］

［9］Majig M A，Fukushima M.Adaptive fitness function for evolutionary algorithm and its applications［C］／／International Conference on Informatics Education and Research for Knowledge－Circulating Society，2008：119－124.

［10］LIU Bo，WANG Ling.Advances in differential evolution［J］.Control and Decision，2007，22（7）：721－729（in Chinese）.［劉波，王凌.差分進化算法研究進展［J］.控制與決策，2007，22（7）：721－729.］