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

（1 吉林師范大學 計算機學院，吉林 四平 136000；2 吉林師范大學 數(shù)值模擬吉林省高校重點實驗室，吉林 四平 136000；3 吉林師范大學 附屬機構(gòu)，吉林 四平 136000）

0 引言

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

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

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

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

1 工作基礎(chǔ)

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

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

其中，x、y分別是兩點的橫坐標與縱坐標值。

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

2 算法設(shè)計

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

2.1 初始化基因庫

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

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

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

2.3 編碼

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

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

2.4 遺傳操作

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

2.4.1 選擇

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

2.4.2 交叉

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

圖3 交叉過程Fig.3 Cross process

2.4.3 變異

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

3 實例分析

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

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

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

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

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

在滿足條件的情況下隨機選取一個變異點進行變異。

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

4 結(jié)束語

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

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