代婷婷，董延壽

（昭通學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，云南 昭通 657000）

在日常生活中機(jī)器人無處不在地影響著我們，給生活帶來了許多方便和精彩，在很多領(lǐng)域發(fā)揮著重要的不可替代的作用，特別是在節(jié)省人力、物力方面發(fā)揮的作用日益突出。對它主要研究其通用性和適應(yīng)性[1-2]。為了滿足人類的各種需求，必須深入分析復(fù)雜多變的環(huán)境，設(shè)計(jì)合理的算法程序?qū)崿F(xiàn)其自主導(dǎo)航運(yùn)動目標(biāo)，而路徑規(guī)劃是移動機(jī)器人實(shí)現(xiàn)這一目標(biāo)的核心技術(shù)，在研究領(lǐng)域是熱點(diǎn)關(guān)注的地方[3]。機(jī)器人的智能水平越高表示它的路徑規(guī)劃水平較高。因此，尋找高效的機(jī)器人路徑規(guī)劃方法顯得非常有意義[4]。盡管蟻群算法在收斂速度等方面有不足和局限，可在求解機(jī)器人路徑規(guī)劃方面由于它具有的諸如正反饋性、強(qiáng)魯棒性、并行性等很多優(yōu)點(diǎn)可以得到充分利用，使得該算法在很多智能化領(lǐng)域被深入研究和廣泛應(yīng)用。為了充分利用蟻群算法的優(yōu)勢，挖掘文獻(xiàn)[5]和文獻(xiàn)[6]中改進(jìn)蟻群算的技巧原理，巧妙地柔和兩種改進(jìn)的優(yōu)點(diǎn)得出了另外一種新的改進(jìn)蟻群算法。將得到的融合雙因子改進(jìn)蟻群算法與遺傳算法于機(jī)器人路徑規(guī)劃實(shí)驗(yàn)的不同階段混合使用得到了良好效果，選擇柵格法在不同規(guī)模的柵格上使用MATLAB2019 進(jìn)行機(jī)器人路徑規(guī)劃實(shí)驗(yàn)進(jìn)一步突出混合算法的優(yōu)勢。

1 相關(guān)理論

1.1 遺傳算法

遺傳算法是一種廣為人知的智能算法，因?yàn)槠渚哂袕?qiáng)魯棒性、獨(dú)立性、可操作性等優(yōu)點(diǎn)，使得該算法的應(yīng)用相當(dāng)廣泛，物理、數(shù)學(xué)、計(jì)算機(jī)、化學(xué)等領(lǐng)域都有涉及[7-8]。其主要原理：產(chǎn)生初始種群后，這些種群通過雜交會逐代演化產(chǎn)生適應(yīng)生存環(huán)境的優(yōu)秀子代，而這個優(yōu)秀的子代就可以看成是遺傳算法的最優(yōu)化的近似解，按照達(dá)爾文的進(jìn)化論適者生存優(yōu)勝劣汰的大自然生物學(xué)原理將優(yōu)秀的個體選擇出來，交配挑選出來的個體。在每一代中，按照自然遺傳學(xué)的相關(guān)理論找出相應(yīng)的算子，然后依據(jù)算子原理進(jìn)行讓種群之間進(jìn)行交叉，在組合交叉的過程中會產(chǎn)變異的種群，一代又一代的種群按照此種方法交叉變異，最后就會產(chǎn)生適應(yīng)環(huán)境能力強(qiáng)的種群，即最為優(yōu)秀的個體就會產(chǎn)生，當(dāng)最優(yōu)秀的個體通過解碼后就會對應(yīng)優(yōu)化問題的最優(yōu)解，則代表新的解集就會得到。由于國內(nèi)外的學(xué)者對此方法的研究很深入，在各方面都取得了不錯的成就，這使得遺傳算法的性能逐步被提高很多，從而使得該算法的應(yīng)用領(lǐng)域越來越廣泛[9-10]。

1.2 關(guān)于遺傳算法的路徑規(guī)劃

基于以上關(guān)于遺傳算法的理論可以得到遺傳算法在路徑規(guī)劃中的實(shí)現(xiàn)步驟[11]:

（1）隨機(jī)產(chǎn)生一定數(shù)目的很多條路經(jīng)，將這些隨機(jī)產(chǎn)生的路徑看成初始種群，機(jī)器人在柵格上行走；

（2）在機(jī)器人行走中需要連續(xù)的路徑，為了將上述間斷的路徑改成連續(xù)的路徑需要對相鄰的柵格做連續(xù)性判斷，按照上下左右的順序取相鄰柵格，將無障礙的柵格插入不相鄰的柵格，不斷調(diào)整直到所有的柵格路徑連續(xù)為止；

（3）按照個體適應(yīng)度函數(shù)求解個體所占的比率從而選擇出需要的優(yōu)秀個體，為了防止算法陷入局部死循環(huán)，采用輪盤賭的方式進(jìn)行；

（4）在路徑規(guī)劃中進(jìn)行交叉操作，在挑選出兩條相同路徑的交點(diǎn)時采用單點(diǎn)交叉的方式進(jìn)行，依此點(diǎn)為目標(biāo)點(diǎn)將后面的路徑進(jìn)行交叉，同時對路徑的連續(xù)性進(jìn)行判斷，不斷修改判斷知道完成所有的交叉操作。

（5）比較變異概率和特定的數(shù)值，當(dāng)變異概率大于給定的數(shù)字時，那么路徑上的兩個柵格隨機(jī)選取，并對相鄰的情況做出判斷，使用產(chǎn)生初始種群的方法調(diào)整柵格的連續(xù)性，直到所有柵格連續(xù)完成變異操作。

1.3 改進(jìn)的蟻群算法

1.3.1 改進(jìn)啟發(fā)函數(shù)

基于基本蟻群算法的原理分析以及結(jié)合相關(guān)的參考文獻(xiàn)，發(fā)現(xiàn)影響最短路徑計(jì)算結(jié)果的主要原因就是節(jié)點(diǎn)之間的概率轉(zhuǎn)移以及螞蟻行走路徑上不斷更新變化的信息素濃度。而轉(zhuǎn)移概率對最短路徑的影響主要是通過它里面的啟發(fā)函數(shù)起作用的。常規(guī)遺傳算法的概率轉(zhuǎn)移取相鄰節(jié)點(diǎn)i 與j的歐氏距離倒數(shù)作啟發(fā)函數(shù)使用。在最初搜索的時候，行走路徑上的螞蟻數(shù)量較少，釋放的信息素較少，造成其他螞蟻偏離正確尋找路徑的概率較大，這樣很容易形成局部的最優(yōu)解或者產(chǎn)生無效解甚至進(jìn)入死循環(huán)求不出結(jié)果[12]。于是文獻(xiàn)[5]在啟發(fā)函數(shù)中引入了當(dāng)前和目標(biāo)節(jié)點(diǎn)的歐氏距離，從而使兩個節(jié)點(diǎn)的聯(lián)系更加的緊密，改進(jìn)啟發(fā)函數(shù)的數(shù)學(xué)表達(dá)式如公式（1）所示：

在上面的（1）式中dij表示節(jié)點(diǎn)i 與j 的歐氏距離；djE是節(jié)點(diǎn)j 和目標(biāo)節(jié) 點(diǎn)E 之間的歐氏距離,于是搜索路徑的方向性被加強(qiáng)，加強(qiáng)的方向性使得漫無目的的搜尋的時間大大減少，這一改進(jìn)從時間上來說就比原有的算法具有優(yōu)勢，計(jì)算的效率明顯提高。

1.3.2 改進(jìn)的信息素濃度更新方式

大量文獻(xiàn)和實(shí)驗(yàn)表明，螞蟻對信息素濃度的更新會對蟻群算法的運(yùn)行時間、運(yùn)行效率以及算法的準(zhǔn)確性都會產(chǎn)生深遠(yuǎn)的影響，即信息素濃度的不同更新方式對蟻群算法的計(jì)算效果影響是非常巨大的[13]。文獻(xiàn)[6]給出了一種特別湊效的方法，避開信息素?fù)]發(fā)因子ρ的隨機(jī)性，對信息素的濃度進(jìn)行動態(tài)的控制。即在算法開始的時候，用統(tǒng)一的方式對所有螞蟻進(jìn)行信息素更新，當(dāng)?shù)_(dá)到設(shè)定的次數(shù)之后執(zhí)行不同的更新策略在不同的螞蟻身上。對表現(xiàn)優(yōu)秀的螞蟻進(jìn)行獎勵，給予正反饋的激勵加強(qiáng)它的信息素濃度。相反，對表現(xiàn)不好的螞蟻進(jìn)行懲罰，適當(dāng)?shù)臏p少其信息素的濃度，防止對后面螞蟻的路徑選擇產(chǎn)生誤導(dǎo)引起收斂過快只找到局部的最優(yōu)解。將前面提到的設(shè)定次數(shù)記為N,在前N 次的循環(huán)中增加和 減少最優(yōu)最差路徑的信息素按照（2）式進(jìn)行計(jì)算。

除此之外，為了促使路徑朝著最優(yōu)化的方向前進(jìn)，在每次循環(huán)中將本次迭代中最佳路徑上的信息素進(jìn)一步加強(qiáng)，增強(qiáng)值具體依據(jù)公式（3）的表達(dá)式計(jì)算，使得蟻群算法的正反饋機(jī)制得到充分的利用。

結(jié)合以上兩種改進(jìn)算法的優(yōu)勢，在基本蟻群算法中同時使用文獻(xiàn)[5]的啟發(fā)函數(shù)改進(jìn)與文獻(xiàn)[6]的信息素濃度更新方式改進(jìn)，于是就得到了雙因子改進(jìn)蟻群算法。

2 雙因子改進(jìn)蟻群算法與遺傳算法的混合

2.1 混合智能算法原理

結(jié)合遺傳算法的優(yōu)點(diǎn)，將上文中通過同時改進(jìn)啟發(fā)函數(shù)和信息素濃度的更新方式形成的改進(jìn)蟻群算法結(jié)合，構(gòu)造出了一種新的智能優(yōu)化算法.為了充分利用這兩種算法的優(yōu)點(diǎn)，本文中的混合算法在算法的初期選擇遺傳算法，在后期選用蟻群算法，兩種算法在整個混合算法中的總體趨勢如圖1：

圖1 速度-時間曲線圖Fig.1 Speed-time curve

2.2 新智能算法步驟

通過圖1 可以發(fā)現(xiàn)，在機(jī)器人路徑規(guī)劃尋優(yōu)實(shí)驗(yàn)中前半段使用 遺傳算法，而后半段使用文獻(xiàn)[5]和文獻(xiàn)[6]結(jié)合得到改進(jìn)蟻群算法，可以使得混合算法的效率達(dá)到最大。基于此理論可得到兩種算法結(jié)合混合算法的步驟如下：

Step1：對遺傳算法的各個參數(shù)進(jìn)行初始化；

Step2：尋找出初始的路徑，依據(jù)遺傳算法的理論隨機(jī)生成初始種群;

Step3：通過適應(yīng)度函數(shù)對每一個體所占的比率逐個計(jì)算，根據(jù)比率值的大小找出當(dāng)代中最優(yōu)個體；

Step4：選擇規(guī)劃路徑中的各值進(jìn)行交叉變異，找到更好的下一代種群最優(yōu)路徑；

Step5：適應(yīng)度值的計(jì)算，計(jì)算完之后與當(dāng)前的最優(yōu)值對比，對當(dāng)前最優(yōu)個體是否更新；

Step6：判斷遺傳算法停止的條件最大循環(huán)次數(shù)N是否出現(xiàn)，若是轉(zhuǎn)向步驟7執(zhí)行改進(jìn)蟻群算法，否則轉(zhuǎn)步驟4；

Step7：放置所有螞蟻在初始點(diǎn)，運(yùn)用遺傳算法得到最優(yōu)路徑長度lmax，把lmax作為改進(jìn)蟻群算法的信息素部分初值；

Step8：所有螞蟻都從S 點(diǎn)出發(fā)，隨后將S 加入到禁忌表中；

Step9：依據(jù)公式（1）尋找下一個節(jié)點(diǎn)，將找到屬于可行節(jié)點(diǎn)集合的節(jié)點(diǎn)作為下一個可行節(jié)點(diǎn)，并且將其放入到禁忌表中；

Step10：對螞蟻當(dāng)前的行走路徑做標(biāo)記，判斷螞蟻是否已到終點(diǎn)，如果否，返回至Step9；若是螞蟻到達(dá)了終點(diǎn)，接對是否已走完全程進(jìn)行判斷，若是全部走完則執(zhí)行Step11，否則返回到Step8 安排另外一只螞蟻重新出發(fā)；

Step11：等到全部螞蟻到達(dá)目標(biāo)節(jié)點(diǎn)之后，求解出螞蟻行走過的路徑中的最優(yōu)和最差路徑，然后增加迭代次數(shù)并對信息素更新；

Step12：在迭代次數(shù)最大時輸出最短路徑，否則轉(zhuǎn)到Step8。

3 實(shí)證分析

雖然從理論上講混合的智能算法綜合了遺傳算法和改進(jìn)蟻群算法的優(yōu)點(diǎn)，但是方法的優(yōu)劣最終需要在實(shí)際案例中驗(yàn)證，使用得到的混合智能算法在規(guī)模為20×20 和30×30 的機(jī)器人規(guī)劃路徑問題上，實(shí)驗(yàn)的具體操作是尋找路徑的開始階段要用到遺傳算法，因此需要對該算法的實(shí)驗(yàn)參數(shù)進(jìn)行設(shè)置，即初始化遺傳改進(jìn)蟻群混合算法的各個參數(shù)，下面的表1 是具體的參數(shù)設(shè)置。

表1 遺傳改進(jìn)蟻群混合算法的參數(shù)設(shè)置Tab.1 Parameter setting of genetically improved ant colony hybrid algorithm

設(shè)置完遺傳改進(jìn)蟻群混合算法的參數(shù)之后，在規(guī)模為20×20 和30×30 柵格的環(huán)境地圖中應(yīng)用混合遺傳改進(jìn)蟻群算法進(jìn)行實(shí)驗(yàn)，設(shè)置相同的迭代次數(shù)，從尋找最短路徑所用的時間上尋找該方法的優(yōu)勢。兩種環(huán)境下機(jī)器人從起點(diǎn)到終點(diǎn)無碰撞的尋找最短路的實(shí)驗(yàn)結(jié)果如圖2 和圖3所示。

圖2 20×20 柵格下混 合算法的收斂曲線Fig.2 Convergence curve of hybrid algorithm under grid

圖3 30×30 柵格下混合 算法的收斂曲線Fig.3 Convergence curve of hybrid algorithm under grid

由圖2 和圖3 可以看出，應(yīng)用遺傳改進(jìn)蟻群混合算法使機(jī)器人在20×20 柵格環(huán)境中尋找最優(yōu)路徑時，在第3 次迭代時算法就會收斂即可得到最短路徑；在30×30 柵格環(huán)境下，第5 次迭代時算法收斂就會得到最短路徑。這只時說明了此算法在求解機(jī)器人路徑規(guī)劃方面具有較快的速度，大大縮短了求解最優(yōu)解的時間。通過文獻(xiàn)[5]和文獻(xiàn)[6]可知改進(jìn)的蟻群算法比基本的蟻群算法具有優(yōu)勢，所以要說明混合了遺傳算法的改進(jìn)蟻群算法比其他方法優(yōu)秀，只需要與改進(jìn)的蟻群算法在相同的實(shí)驗(yàn)和環(huán)境下作如表2 的比較。

表2 改進(jìn)蟻群算法與混合智能算法求解結(jié)果比較Tab.2 Comparison of the solution results of the improved ant colony algorithm and the hybrid intelligent algorithm

由表2 可以看出混合算法可以用較少的迭代次數(shù)求解出最短路徑，算法的復(fù)雜度較低，也更節(jié)省時間。

4 結(jié)束語

本文主要內(nèi)容是闡述遺傳算法的原理以及如何得到改進(jìn)的蟻群算法，并且將兩種智能算法結(jié)合起來形成一種解決機(jī)器人路徑規(guī)劃的問題的遺傳改進(jìn)蟻群混合算法，其原理是在整體求解過程中先采用遺傳算法求解最短路，對于雙因子改進(jìn)蟻群算法信息素的部分初值使用最短路的長度，這樣加強(qiáng)了改進(jìn)蟻群算法的方向性，減少了搜索的盲目性。這對螞蟻盡快找到最優(yōu)路徑起到了促進(jìn)作用。將這種混合的算法分別使用于20×20 柵格和30×30 柵格環(huán)境下對機(jī)器人規(guī)劃路徑問題進(jìn)行了求解，得到結(jié)果顯示此方法的求解結(jié)果更令人滿意。