基于遺傳規劃的迷宮問題高效求解

崔兆順

CUI Zhao-shun

（天水師范學院，天水 741000）

0 引言

進化算法是基于模擬自然進化的搜索過程而發展起來的一類隨機搜索技術。目前研究的進化算法主要有三種典型的算法：遺傳算法，進化規劃和進化策略。遺傳算法吸引了大量的研究者和探索者，并在許多工程領域的得到了應用，如管道線路優化，機器學習，模式識別，神經網絡結構參數優化，及權重學習，精調模糊邏輯控制器，飛船控制系統優化等。遺傳規劃是遺傳算法的擴展和延伸，它把不同領域的各種問題都看成程序歸納問題，也就是在可能的程序空間中尋找最優或滿意的計算機程序。在遺傳規劃算法研究方面，包括問題約束，個體表示，適應度定義，選擇策略和遺傳算子等具體過程；在理論研究方面包括借助適應度狀態圖和模式定理等遺傳規劃的自適應機理分析。

目前遺傳算法在迷宮問題上的主要解決方法都是優化路徑，對搜索到的迷宮路徑進行優化。本文用一組整數對程序進行編碼，借鑒二進制編碼的交叉，變異，并結合計算機程序的特點設計了遺傳操作。使用遺傳規劃優化了行走程序，指導迷宮機器人在迷宮中找到一條最優的路徑。實驗結果表明使用遺傳規劃求解迷宮問題是有效的。

1 迷宮問題描述

迷宮問題可以表述為：一個二維的網格，尋找從某一個給定的起始單元格出發，經由行相鄰或列相鄰的單元格（可以通過的），最終可以到達目標單元格的、所走過的單元格序列。在任一個單元格中，都只能看到與它鄰近的四個單元格；如果位于底邊，則只有三個；位于四個角上，則只有2個。迷宮設計為以方格標示邊界及障礙，空白標示可行路線，指定迷宮最左上角點為起點，最右下角為終點，對于隨機迷宮，能夠找到計算機程序來尋求路徑，并且用遺傳算法搜索到計算機程序，進行多次優化，能生成更好的程序。這與一般遺傳算法求解迷宮問題的方法也不同，不是直接對路徑進行探索優化。

2 基于遺傳規劃的迷宮問題高效求解

遺傳規劃的實現涉及到5個要素：染色體的編碼、初始群體的設定、評估函數即適應值函數的設計、遺傳操作的設計和算法控制參數的設定。

2.1 染色體編碼

采用遺傳算法，首先要考慮如何通過染色體的編碼把問題的解空間映射到編碼空間。這樣，對問題的解空間的搜索，就轉化為對編碼空間的搜索。我們對一組指令編碼，以一組指令作為一條染色體。這樣最終求解問題的解就是求得一組好的指令，能指導迷宮機器人從迷宮起點到終點的行走。用一條指令來具體說明：

一條指令有四個部分，除去指令編號（0）后的三個部分為主要部分，我們會用語句在在讀入一條指令時把具體操作（FIND）翻譯為數碼，加上后面操作成功與否后會轉向的兩部分（以數碼形式表示的部分）作為染色體一部分。優化后輸出到PathFinder_output.txt，又會需要將數碼翻譯為具體操作（FIND,GO,SAVE,LOAD）。一個指令集有n條指令（具體規模接收外界輸入指定），那么一條染色體長度就有3*n，指令編號從0到n-1。在該長度的染色體中，所有3*n（n=0，1，2，...,n-1）位上的數碼只能在{0，1，2，3}中選取，因為基本操作只有FIND,GO,SAVE,LOAD四種，而其余位上可以在數碼集{0，1，2...，n-1}中選取，表示檢測基本操作成功與否后會轉向的指令編號。對迷宮從起點到達終點的路徑的搜索就是對長度為3*n,由數碼0到n-1構成的數碼空間的搜索。這就構成了求解迷宮問題的遺傳算法的染色體。

2.2 初始群體設定

初始群體是隨機產生的，群體規模和最大代數可以由外部輸入指定。定義一個randomize函數，隨機生成一個長度為3*instruction.size的染色體。

2.3 適應值函數設計

評估函數是用來評估個體好壞的。在本問題中，迷宮機器人按照染色體（指令集）指導行走，我們考查到達的位置與終點位置的關系。前面已說到，每個位置以所在行、列數的有序對形式表示，我們在這里把它看為橫縱坐標。機器人當前位置是已知的，我們把其橫縱坐標各自與終點橫縱坐標的差的絕對值，求和，作為其適應值。設已知點坐標（Xi,Yi）,終點坐標（Xg,Yg），有如下計算公式：

我們選擇這樣一個評估函數，而不是去考查所處位置與終點位置的絕對位置，用畢達哥拉斯定理（即勾股定理，有計算公式fitness（x）’）計算二者之間距離，好處有下列兩點：

1）計算簡單，避免出現浮點數，減少計算開銷；

2）多個計算結果相比較，互相之間的差距與勾股定理計算結果互相之間的差距相比，更直觀明顯，增大了選擇壓力。迷宮機器人行走到某個位置，其適應值函數值越小，表明離終點越近，也就越是我們希望的結果。求迷宮問題的解轉化為找適應值為0的個體，也就是說適應值為0的個體為最優個體。

2.4 遺傳操作的設計

1）交叉算子的設計

前面提到雜交有多種方式，這里簡單進行一下說明。

（1）一點交叉：

是由Holland提出的最基本的雜交方式，操作信息量比較小，雜交點位置的選擇可能帶來較大偏差。按照Holland的意思，一點交叉算子不利于長距離的保留和重組，而且位串末尾的重要基因總是被交換。

（2）兩點交叉：

兩點交叉對于短距模式破壞概率較大，對于長距模式破壞概率較小，滿足提高低階短距模式的重組機會，保證高階長距模式的生存機會的搜索要求，因此在實踐中大量采用。

（3）多點交叉：與兩點交叉類似，但是更利于模式的重組。

（4）均勻交叉：染色體位上的每一位按相同的概率進行隨機均勻交叉。

Spears和De Jong認為均勻交叉優于多點交叉，并提出了一種帶偏置概率參數的均勻交叉（概率在0.5—0.8之間），不存在多點交叉算子操作引起的位置偏差，任意基因在均勻交叉作用下均可以重組，并遺傳給下一子代個體。我們選擇的是偏置概率為0.5的均勻交叉，即指對于選定的兩個染色體，每一對基因位有50%的概率發生交換。這樣的概率致使算法探索力度最大。例如，1234和4321時兩個染色體串，對第一對基因位1和4而言，有50%的概率發生交換，成為4234和1321；后面三對基因位以此類推。在本文中，雜交操作是發生在隨機選取的兩條染色體之間，具體的操作、成功與否轉向的下一步操作發生，操作互換交換，下一步操作指令編號互換。

2）變異算子的設計

隨機選取一個染色體，對它的某個操作進行變異或是對下一步指令編號變異，對每一代的每個染色體，都進行了與種群規模大小一樣次數的變異。

3 仿真實驗與分析

本算法參數定義種群規模population_size，算法運行最大代數max_generation，指令規模（指令條數）program_size，偏置概率（設定為0.5）。種群規模影響遺傳算法的有效性。規模太小，算法會很差或根本找不出問題的解，因為太小的種群數目不能提供足夠的采樣點；規模太大，會增加計算量，使收斂時間增大。一般種群規模定在30到160之間比較合適。在本文中一般定為100。最大代數也需要找到一個合適值，一方面是算法有效，另一方面盡量減小計算開銷。在本設計中一般定為100。指令條數同樣有上述考慮，一般為5—10條為宜。

圖1 迷宮機器人完成行走

最后，設計了若干組實驗考察了算法的重要參數設置（指令規模，種群規模，迷宮規模）對優化效果的影響，大致得出如下結論：

1）在其他參數不變的前提下，優化后指令的好壞程度隨指令規模增大而增大，而迷宮規模會影響其程度。另外，測試證明運行時間會隨指令規模增大而增大

2）在其他參數不變的前提下，種群規模定在100會得到更讓人滿意的優化結果。這也印證了理論中種群大小在30—160之間為合適。另外，測試證明運行時間隨種群規模增大而增大。

4 結論

綜和以上實驗，我們可以得出，使用遺傳規劃算法解決迷宮問題，需要對各個參數進行適當設置，既要考慮算法效率，同時也要顧及計算開銷，以求兩方面有很好的平衡。而實驗結果也證明本設計的算法是有效的，能夠實際的解決迷宮問題，說明這個算法是有效的。

[1].De Jong K.Learning with Genetic Algorithms,An Overview.Machine Learning,1988,3（2,3）：121-138.

[2]劉勇,康立山,陳毓屏.非數值并行算法（第二冊）[M].遺傳算法.科技出版社,2003.

[3]De Jong and Spears,W.M.A formal analysis of the role of multi-point crossover in genetic algorithms.Annals of Mathematics and Artificial Intelligence,1992,5（1）：1-26.

[4]Jenking,W.M.Structural optimization with the genetic algorithm.Structural Engineer,1991,69（24）：408-422.

[5]Kadaba,N.Nygard,K.E.,and Juell,P.L.Integration of adaptive machine learning and knowledge-cased systems for routing and scheduling applications.Expert Systems with Applications,Vol 2,No.1,1991：15-27.