基于遺傳規(guī)劃的迷宮問題高效求解

崔兆順

CUI Zhao-shun

（天水師范學(xué)院，天水 741000）

0 引言

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

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

1 迷宮問題描述

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

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

遺傳規(guī)劃的實現(xiàn)涉及到5個要素：染色體的編碼、初始群體的設(shè)定、評估函數(shù)即適應(yīng)值函數(shù)的設(shè)計、遺傳操作的設(shè)計和算法控制參數(shù)的設(shè)定。

2.1 染色體編碼

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

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

2.2 初始群體設(shè)定

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

2.3 適應(yīng)值函數(shù)設(shè)計

評估函數(shù)是用來評估個體好壞的。在本問題中，迷宮機器人按照染色體（指令集）指導(dǎo)行走，我們考查到達的位置與終點位置的關(guān)系。前面已說到，每個位置以所在行、列數(shù)的有序?qū)π问奖硎荆覀冊谶@里把它看為橫縱坐標(biāo)。機器人當(dāng)前位置是已知的，我們把其橫縱坐標(biāo)各自與終點橫縱坐標(biāo)的差的絕對值，求和，作為其適應(yīng)值。設(shè)已知點坐標(biāo)（Xi,Yi）,終點坐標(biāo)（Xg,Yg），有如下計算公式：

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

1）計算簡單，避免出現(xiàn)浮點數(shù)，減少計算開銷；

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

2.4 遺傳操作的設(shè)計

1）交叉算子的設(shè)計

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

（1）一點交叉：

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

（2）兩點交叉：

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

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

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

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

2）變異算子的設(shè)計

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

3 仿真實驗與分析

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

圖1 迷宮機器人完成行走

最后，設(shè)計了若干組實驗考察了算法的重要參數(shù)設(shè)置（指令規(guī)模，種群規(guī)模，迷宮規(guī)模）對優(yōu)化效果的影響，大致得出如下結(jié)論：

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

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

4 結(jié)論

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

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

[2]劉勇,康立山,陳毓屏.非數(shù)值并行算法（第二冊）[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.