基于解空間優(yōu)化的遺傳算法的路徑規(guī)劃

王堯山 朱毅 盧軍

摘要

針對傳統(tǒng)遺傳算法在移動機器人路徑規(guī)劃方面存在早熟收斂問題，對遺傳算法生成的初始種群和解空間進行研究，提出了一種基于解空間優(yōu)化的遺傳算法最后通過仿真實驗證明該優(yōu)化算法在一定程度上能解決此問題。

【關(guān)鍵詞】遺傳算法 機器人 路徑規(guī)劃 解空間優(yōu)化

1 引言

遺傳算法具有良好的全局搜索能力，可以快速地將解空間中的全體解搜索出，而不會陷入局部最優(yōu)解的快速下降陷阱;并且利用它的內(nèi)在并行性，可以方便地進行分布式計算，加快求解速度。但是遺傳算法的局部搜索能力較差，導(dǎo)致單純的遺傳算法比較費時，在進化后期搜索效率較低。在實際應(yīng)用中，遺傳算法容易產(chǎn)生早熟收斂的問題。采用何種選擇方法既要使優(yōu)良個體得以保留，又要維持群體的多樣性，一直是遺傳算法中較難解決的問題。

2 基于解空間優(yōu)化的遺傳算法

2.1 優(yōu)化初始種群

遺傳算法最終計算結(jié)果和達到收斂值的迭代次數(shù)，和初始生成的種群，有直接的關(guān)系。一般遺傳算法的初始種群都是隨機生成的，特定環(huán)境下，可以對初始種群中的個體，進行優(yōu)化。

假設(shè)圖1中ABCD四個導(dǎo)航點對應(yīng)的x坐標(biāo)分別為1、2、3、5。A-B-C是三個相鄰的導(dǎo)航點，那么，在路徑規(guī)劃中，A-B-C就是一段最優(yōu)子基因片段，D與A-B-C之間距離較遠，不算到一起。如果在個體中出現(xiàn)了A-C-B這樣的基因組合，那么這段基因組合，是最優(yōu)基因組合的概率，就比較低了。對于這種本身可能是最優(yōu)基因片段的，在生成隨機路徑的時候，把該片段當(dāng)成一個整體進行操作。如果按照傳統(tǒng)方法對其進行處理，那么會有12種不同的基因排列順序，產(chǎn)生很多無效個體，而如果把A-B-C基因片段看成一個整體A'，那么就可以得到一個非常好的個體A'D。

引入一個新的模型：每一個基因由基因序號、入口點和出口點組成。

定義：基因融合之后產(chǎn)生的新點的序號叫基因序號。進入該基因的第一個點叫入口點，離開該基因的第一個點，叫出口點。比如A'點的模型構(gòu)造為A'（A，C），D點生成新的D的模型構(gòu)造為D'（D，D）。

在將原來的需要遍歷的集合進行處理之后，我們可以很容易得到一個新的集合，在這個集合中，由于有出口點和入口點，所以，所有的路徑集合都變成了矢量，而非以前的標(biāo)量。在集合中任意兩個點M'和N'，M'N'之間的距離為：，也就是M基因的出口點到N點入口點的距離，加上M基因本身的長度。相對的，N'M'之間的距離為：

2.2 尋找最優(yōu)基因片段

（1）將所有點，按y坐標(biāo)從小到大進行排序。

（2）從Y坐標(biāo)最小的點y₁開始，判斷有沒有與其y坐標(biāo)相同的點，如果沒有，則將該點構(gòu)造成一個新的點，入口點和出口點都是本身。如果有，則將這些點按x坐標(biāo)的值，從小到大排列。

（3）從x值最小的點x₁開始，將其構(gòu)造為一個新的點X₁'，入口點為x₁，出口點為x₁，再查詢與其相鄰點x₂的距離，如果這個距離小于閾值，則將出口點替換為x₂.然后再查詢x₂下一個點x₃-若x₂和x₃之間的距離大于閾值，則X，'構(gòu)造完成，將x₃構(gòu)造成新點x₃'，重復(fù)之前步驟，終止條件為，x的下一個點查找為空。

（4）當(dāng)下一個點查找為空時，對y₂執(zhí)行相同操作，重復(fù)執(zhí)行，直到y(tǒng)的霞一個點查找為空。

最優(yōu)基因片段生成流程如圖2。

3 仿真實驗

對于改進后的遺傳算法，主要是對其生成種群時，結(jié)合特定條件進行了改進，并且這種改進，只針對于有最優(yōu)基因片段的情況，當(dāng)沒有最優(yōu)基因片段時，還是按照傳統(tǒng)方法進行計算。下面，假設(shè)導(dǎo)航點有29個，和出發(fā)點一起，共30個點，根據(jù)最優(yōu)基因片段的多少，進行30點TSP問題模擬實驗。

3.1 極端情況

此種情況假設(shè)所有的點均在一條直線上。數(shù)據(jù)融合以后，只剩下一個點A'，其距離為A'A'=A_outA_in+|A|'，路徑為P1-P30，不需要查找就可直接得出最優(yōu)結(jié)果。

而按照傳統(tǒng)的TSP處理過程需要經(jīng)過183次迭代后，才能得到最優(yōu)路徑。

顯然，當(dāng)處于極端情況時，優(yōu)化后的算法比傳統(tǒng)的算法有著極大的優(yōu)勢，所有點都集合成一個點，連查找過程都省略了。

3.2 理想情況

此種情況假設(shè)具有比較多的點可以融合成最優(yōu)基因片段，但是不像極端狀況那樣可以將初始集合的點數(shù)降低到只有幾個的程度。

用傳統(tǒng)方法直接計算，在351次迭代之后，達到最小值84.其查找過程如圖3傳統(tǒng)TSP搜索過程所示。經(jīng)過優(yōu)化算法后的新點集合為：

Q1（P1，P3），Q2（P4，P6），Q3（P7，P9），Q4（P10，P12），Q5（P13，P15），Q6（P16，P18），Q7（P19，P21），Q8（P22，P24），Q9（P25，P27），Q10（P28，P30）在經(jīng)歷5次迭代之后，找到最小值840其搜索過程如圖4優(yōu)化TSP搜索過程所示。

4 結(jié)論

本文對遺傳算法的種群初始化和解空間進行優(yōu)化，基于此提出了一種最優(yōu)基因片段生成方法。最后通過仿真實驗?zāi)M求解TSP問題，實驗結(jié)果證明所提方法優(yōu)于傳統(tǒng)遺傳算法，對解決室內(nèi)移動機器人路徑規(guī)劃問題有一定幫助。

參考文獻

[1]National Institute of Standards andTechnology，Valiated FIPS 140-1 andFIPS 140-2 Cryptographic Modules，2011.

[2]Holland J H.Adaptation in naturaland artificial systems.The Universityof Michigan Press，1975.

[3]李靜.基于改進遺傳算法的數(shù)據(jù)特征分類[J].現(xiàn)代電子技術(shù)，2018，14：1004-373.