崔兆順

CUI Zhao-shun

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

0 引言

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

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

1 迷宮問題描述

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

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

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

2.1 染色體編碼

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

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

2.2 初始群體設(shè)定

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

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

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

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

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

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

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

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

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

（1）一點(diǎn)交叉：

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

（2）兩點(diǎn)交叉：

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與分析

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

圖1 迷宮機(jī)器人完成行走

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

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

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

4 結(jié)論

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

[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.