張耀允，譚振江，周偉，方大甲

（1 吉林師范大學(xué) 計(jì)算機(jī)學(xué)院，吉林 四平 136000；2 吉林師范大學(xué) 數(shù)值模擬吉林省高校重點(diǎn)實(shí)驗(yàn)室，吉林 四平 136000；3 吉林師范大學(xué) 附屬機(jī)構(gòu)，吉林 四平 136000）

0 引言

遺傳算法［1］（Genetic Algorithm，GA）是一種模擬自然界進(jìn)化規(guī)律的數(shù)學(xué)計(jì)算模型。通過模擬自然界繁衍過程中優(yōu)秀的父代母代相交，得到更優(yōu)秀子代的方法，同樣是對(duì)“自然選擇，適者生存”原則的仿真過程。

該算法的主要特點(diǎn)是個(gè)體單元的選擇和相應(yīng)個(gè)體信息的交換和交集。與普通的搜索算法不同，遺傳算法從種群的初始解開始搜索過程［2］。其是一種建立在自然選擇學(xué)說和自然界遺傳機(jī)制基礎(chǔ)上的搜索算法。該算法模擬了自然界中生物的整個(gè)繁殖、雜交和有較小概率會(huì)發(fā)生的突變過程。一個(gè)待優(yōu)化問題的每一個(gè)可能解決方案都被編碼為一個(gè)“染色體”，也就是一個(gè)個(gè)體。每個(gè)個(gè)體在迭代過程中的不斷更新并保留前代優(yōu)秀部分的過程稱為遺傳。個(gè)體的優(yōu)缺點(diǎn)通常采用適應(yīng)度值來評(píng)價(jià)。算法開始后隨機(jī)生成一些初代，也就是初始解，通過適應(yīng)度函數(shù)，篩選出評(píng)價(jià)較高的個(gè)體進(jìn)行繁衍，而評(píng)價(jià)較差的個(gè)體則會(huì)被慢慢淘汰，則新產(chǎn)生的這一代的個(gè)體，在表現(xiàn)上理應(yīng)優(yōu)于上一代，因?yàn)槠淅^承了上一代的一些優(yōu)秀品質(zhì)。通過這種方式，逐漸走向一個(gè)相對(duì)較好的方向，問題的解也就慢慢趨向一個(gè)最優(yōu)解。此算法的優(yōu)點(diǎn)在于原理操作較為簡(jiǎn)單，魯棒性強(qiáng)，不易受限制條件的約束，具有一定的隱含并行性和較強(qiáng)的全局尋優(yōu)能力［3］。遺傳算法流程如圖1 所示。

圖1 遺傳算法流程圖Fig.1 Flow chart of genetic algorithm

目前，遺傳算法常用于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，以及搜索空間較大的組合優(yōu)化問題。例如在：旅行商［4］、裝箱、布局優(yōu)化、車間調(diào)度、生產(chǎn)線優(yōu)化［5］、生產(chǎn)調(diào)度等問題的求解中，起到了很大的作用。同時(shí)，遺傳算法也非常適合解決傳統(tǒng)的搜索算法難以適應(yīng)的非線性問題。在路徑規(guī)劃問題中，Yagvalkya Sharma［6］將遺傳算法與DijKstra’s算法進(jìn)行了對(duì)比，結(jié)果顯示遺傳算法在該類問題上的優(yōu)越性；在文獻(xiàn)［7］中，首先模擬多目標(biāo)游戲地圖作為實(shí)驗(yàn)平臺(tái)，然后以路徑長(zhǎng)度、路徑安全程度和對(duì)游戲角色的耗費(fèi)為評(píng)估目標(biāo)，提出了一種基于多目標(biāo)遺傳算法的路徑規(guī)劃方法；在機(jī)器人路徑規(guī)劃問題中，鄭美英［8］等驗(yàn)證了遺傳算法較蟻群算法更智能、更穩(wěn)定的優(yōu)點(diǎn)。

1 工作基礎(chǔ)

多數(shù)方法中，對(duì)于遺傳算法的適應(yīng)度函數(shù)均選擇使用曼哈頓式。在將地圖網(wǎng)格化后，若取A、B兩點(diǎn)分別作為起點(diǎn)和終點(diǎn)（如圖2），根據(jù)其計(jì)算公式：

圖2 曼哈頓距離與最短距離Fig.2 Manhattan distance and shortest distance

其中，x、y分別是兩點(diǎn)的橫坐標(biāo)與縱坐標(biāo)值。

選用曼哈頓式得出的最優(yōu)路徑則為a路徑，其路徑長(zhǎng)度較A、B兩點(diǎn)間的直線距離b路徑要大一些。因此，若使用兩點(diǎn)間直線距離作為路徑規(guī)劃過程中的適應(yīng)度函數(shù)，得出的路徑應(yīng)較使用曼哈頓式得出的路徑所費(fèi)代價(jià)更低。

2 算法設(shè)計(jì)

根據(jù)上述算法思想基礎(chǔ)，將常用的適應(yīng)度函數(shù)由曼哈頓式改進(jìn)為以最短距離公式為核心的新的適應(yīng)度函數(shù)。進(jìn)而以傳統(tǒng)遺傳算法為基礎(chǔ)，經(jīng)過遺傳算法中的交叉、變異、產(chǎn)生新子代等過程，對(duì)隨機(jī)路徑進(jìn)行優(yōu)化。優(yōu)化算法實(shí)現(xiàn)過程如下：

2.1 初始化基因庫(kù)

定義一個(gè)新的基因類，即初始化一個(gè)基因庫(kù)，作為遺傳的初代?；虻膬?nèi)容在可行解范圍內(nèi)隨機(jī)選取，在這里初代即為所要優(yōu)化的搜索路徑，enerateOnePath 即是已完成的一個(gè)起點(diǎn)為S終點(diǎn)為E的尋找可行路徑的函數(shù)。

2.2 適應(yīng)度函數(shù)的選擇

由于適應(yīng)度函數(shù)的選取直接影響整個(gè)算法的遺傳優(yōu)化性能，并且尋路中可能涉及到左上、左下、右上、右下4 個(gè)方向，所以選取更為簡(jiǎn)單直觀的兩點(diǎn)間的直線距離作為尋路算法的適應(yīng)度函數(shù)。根據(jù)距離公式，利用函數(shù)將其計(jì)算出來并轉(zhuǎn)換為坐標(biāo)值。

2.3 編碼

遺傳算法是根據(jù)問題的內(nèi)容和屬性對(duì)問題中的變量進(jìn)行編碼，常用的編碼方法有二進(jìn)制編碼、實(shí)數(shù)編碼、整數(shù)編碼、數(shù)據(jù)結(jié)構(gòu)編碼等。若使用二進(jìn)制編碼表示個(gè)體，則二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)的解碼公式為：

路徑優(yōu)化過程中的主要變量即是每次前進(jìn)的方向，在二維地圖中，可以大致將每一步的方向概括為上、下、左、右、左上、右上、左下、右下8 個(gè)方向，采取整數(shù)編碼方式，將這8 個(gè)方向編碼存入數(shù)組中可得：［（－1，－1），（0，－1），（1，－1），（－1，0），（1，0），（－1，1），（0，1），（1，1）］。

2.4 遺傳操作

遺傳操作是將問題代代優(yōu)化，最終找到滿足要求的最佳后代。其可以分為選擇、交叉和變異3 個(gè)基本操作過程。前兩種方法可以實(shí)現(xiàn)遺傳算法的大部分優(yōu)化功能，變異操作則提高了遺傳算法的尋優(yōu)能力。

2.4.1 選擇

從隊(duì)伍中選出最優(yōu)淘汰弱者，這種方法是基于適應(yīng)度評(píng)價(jià)的。適應(yīng)度越大，則被選擇的可能性就越大，被選擇的個(gè)體被分配進(jìn)入設(shè)置好的數(shù)組或配對(duì)數(shù)據(jù)庫(kù)中，等待進(jìn)一步的操作。目前常用的選擇方法有輪盤賭法、最佳個(gè)體保留法、期望值法、排名選擇法、競(jìng)賽法、線性標(biāo)準(zhǔn)化法等，其中輪盤賭法是最實(shí)用、最方便的方法，也是最常用的方法。若要在父代中進(jìn)行隨機(jī)選取并開始繁衍，正常情況下進(jìn)化方向是由選擇這一步驟所決定的，而雜交以及變異是不會(huì)過度影響當(dāng)前種群的整體進(jìn)化方向的。為了滿足“越優(yōu)秀被選到的概率越大”的原則，選取最符合條件的賭輪選擇法。每個(gè)個(gè)體被選擇的概率與其適應(yīng)度大小成正比，輪盤上面積代表對(duì)應(yīng)父代基因的適應(yīng)度，適應(yīng)度越大的區(qū)域被選中作為父代的概率就越大。計(jì)算適應(yīng)度的實(shí)現(xiàn)過程中，為方便之后的比較以及其它操作，將適應(yīng)度數(shù)值添加到數(shù)組中。根據(jù)適應(yīng)度函數(shù)計(jì)算，當(dāng)前點(diǎn)四周8 個(gè)方向的適應(yīng)度值分別與其和做商，結(jié)果存入pArr 數(shù)組中。在選擇過程中隨機(jī)選出一個(gè)小數(shù)作為概率，pArr 數(shù)組中的結(jié)果大于這個(gè)概率的就會(huì)被選中。

2.4.2 交叉

如圖3 所示，雜交是指將雙親個(gè)體的一部分結(jié)構(gòu)重新組合，其目的是從優(yōu)良父母中選出一部分優(yōu)良基因，共同形成新一代的個(gè)體。交叉是遺傳算法獲得優(yōu)良個(gè)體最重要的操作。交叉操作是按照一定的交叉概率在數(shù)組或數(shù)據(jù)庫(kù)中隨機(jī)的選取兩個(gè)個(gè)體進(jìn)行的，交叉位置也是隨機(jī)的，可根據(jù)一定概率隨機(jī)選取。交叉概率一般取得很大，大致范圍在0.6～0.9。本文中，根據(jù)交叉原理判斷后，在滿足交叉條件cross_p＝0.6（一般在實(shí)現(xiàn)過程中隨機(jī)生成）的前提下，可在基因上隨機(jī)確定一個(gè)交叉點(diǎn)index1，并把父代交叉點(diǎn)前后的基因相互交叉，組成一個(gè)新的子代。新生成的子代就可能同時(shí)保留了父代的優(yōu)點(diǎn)，若出現(xiàn)自交等特殊情況，可以直接將父代基因存入子代，等待下一輪交叉。

圖3 交叉過程Fig.3 Cross process

2.4.3 變異

變異是以很小的變異概率Pm，隨機(jī)地改變種群中個(gè)體的某些基因值，利用隨機(jī)數(shù)函數(shù)產(chǎn)生一個(gè)［0，1］之間的隨機(jī)數(shù)rand，若rand ＜Pm，則進(jìn)行變異操作。變異因其加強(qiáng)了算法的隨機(jī)性，可使算法維持種群多樣性，在接近最優(yōu)解時(shí)可以加速向最優(yōu)解收斂。但是，變異的概率一定要取一個(gè)較小的值，因當(dāng)概率大于0.5時(shí)使得算法隨機(jī)性大大增加，遺傳算法就退化為隨機(jī)搜索。本文中，在交叉結(jié)束后，對(duì)新產(chǎn)生的子代基因進(jìn)行變異操作，若子代基因滿足預(yù)先設(shè)定的變異概率條件mutation_p＝0.4，則進(jìn)行變異。如，選取隨機(jī)數(shù)r，并與給定概率0.4 進(jìn)行大小的比較，在r ＜mutation_p（0.4）的情況下，隨機(jī)選取一個(gè)變異點(diǎn)index2 進(jìn)行變異，變異規(guī)則是將變異節(jié)點(diǎn)處的基因值改變?yōu)樵蛑档南喾磾?shù)，若為0，則基因不變，進(jìn)一步降低了變異后隨機(jī)性。

3 實(shí)例分析

針對(duì)一個(gè)隨機(jī)生成的路徑，對(duì)新算法進(jìn)行測(cè)試，在分別對(duì)算法中的重要程序段進(jìn)行解釋說明的基礎(chǔ)上，選取并編寫相應(yīng)的程序?qū)嶒?yàn)環(huán)境，對(duì)算法效率進(jìn)行測(cè)試。

首先，生成一個(gè)長(zhǎng)和寬都是100 個(gè)單位的正方形地圖，并在該地圖中隨機(jī)抽取2 個(gè)點(diǎn)，分別作為路徑的起點(diǎn)S和終點(diǎn)E。在此使用以智能路徑算法中常用的曼哈頓距離作為從起點(diǎn)到目標(biāo)點(diǎn)的適應(yīng)度函數(shù)，在周圍8 個(gè)方向上隨機(jī)抽取一個(gè)節(jié)點(diǎn)后，比較該節(jié)點(diǎn)與起點(diǎn)距離終點(diǎn)的曼哈頓距離，若小于起點(diǎn)則將該節(jié)點(diǎn)直接加入路徑，并作為下一個(gè)起點(diǎn)加入進(jìn)一步的搜索過程，否則重復(fù)上述過程直到節(jié)點(diǎn)中尋到終點(diǎn)。

（1）根據(jù)最短距離公式，編寫計(jì)算適應(yīng)度的函數(shù)

（3）遺傳操作中的交叉與變異過程

在交叉結(jié)束后，對(duì)新產(chǎn)生的子代基因進(jìn)行變異操作，若子代基因滿足預(yù)先設(shè)定的變異概率條件，則進(jìn)行變異。抽取到的隨機(jī)數(shù)與給定概率的大小比較方法如下；

在滿足條件的情況下隨機(jī)選取一個(gè)變異點(diǎn)進(jìn)行變異。

實(shí)驗(yàn)結(jié)果顯示，初始路徑經(jīng)過64 次移動(dòng)結(jié)束尋路抵達(dá)終點(diǎn)，而經(jīng)過本文改進(jìn)后的算法優(yōu)化后，得出的新路徑僅需進(jìn)行56 次移動(dòng)即可成功抵達(dá)路徑目標(biāo)，較優(yōu)化前的初始路徑大幅提升了效率。

4 結(jié)束語

經(jīng)過使用兩點(diǎn)間距離作為適應(yīng)度函數(shù)的遺傳算法對(duì)初始路徑進(jìn)行優(yōu)化后，明顯減少了尋路的搜索次數(shù)，進(jìn)而加強(qiáng)了尋路的效率。當(dāng)?shù)貓D數(shù)據(jù)量過于復(fù)雜時(shí)，想要找到所需路徑時(shí)間會(huì)很長(zhǎng)，只有通過多代遺傳來尋找最優(yōu)解，遺傳代數(shù)往往會(huì)變得很大，有時(shí)會(huì)出現(xiàn)程序無限制的循環(huán)，為了限制這種情況，只能強(qiáng)行限制遺傳代數(shù)，超過限制則被視為無解。同時(shí)，受限于遺傳算法的新空間搜索能力有限，在搜索后期效率會(huì)出現(xiàn)下降，有時(shí)只能得到局部最優(yōu)解，進(jìn)而無法得到所需的全局最優(yōu)。在計(jì)算中，眾多的隨機(jī)數(shù)，如交叉率、變異率等參數(shù)也干擾了路徑的選取方式，進(jìn)而使得在程序中會(huì)出現(xiàn)反向搜索，需要通過限制變異率的數(shù)值來使其無法演變?yōu)殡S機(jī)搜索，來控制這種情況的發(fā)生。

由于遺傳算法中的編碼由簡(jiǎn)單的數(shù)字編碼構(gòu)成，不能完全、準(zhǔn)確的表達(dá)復(fù)雜問題的復(fù)雜屬性。受編碼的屬性影響，尋路算法中無法針對(duì)帶有復(fù)雜地形、復(fù)雜障礙物等結(jié)構(gòu)復(fù)雜的地圖進(jìn)行搜索優(yōu)化。隨著越來越多的復(fù)雜3D 場(chǎng) 景的不斷涌現(xiàn)，原有傳統(tǒng)的智能尋路技術(shù)難以適應(yīng)3D 場(chǎng)景的復(fù)雜性［9］，特別是在復(fù)雜環(huán)境下，往往需要耗費(fèi)大量時(shí)間才能規(guī)劃出可行路徑［10］。隨著深度學(xué)習(xí)、人工神經(jīng)網(wǎng)絡(luò)等智能優(yōu)化算法的發(fā)展，將遺傳算法與最前沿的優(yōu)秀算法思想結(jié)合，傳統(tǒng)遺傳算法的各個(gè)缺陷也會(huì)得到相對(duì)應(yīng)的優(yōu)化，進(jìn)而使得該算法在更多的領(lǐng)域中獲得更廣闊的發(fā)展。