最優(yōu)行車路徑規(guī)劃算法的設(shè)計

楊東澤 賈萱 解明翰 馮麗茹 程慧

摘要：行車路徑規(guī)劃問題是城市智能交通的重要組成部分，它是一種行程路徑的設(shè)計與優(yōu)化。合理的行車路徑，一方面可以避免因路況不熟悉而造成停車使用者迷路的情況，減少車輛在復(fù)雜路網(wǎng)中的交通時長，優(yōu)化交通流在道路網(wǎng)絡(luò)中的分布，另一方面可以減少停車使用者因長時間找不到停車位，而選擇路邊非法停車，在一定程度上提高了交通安全。本文結(jié)合遺傳和蟻群算法的各自優(yōu)點，將兩種算法的尋優(yōu)過程循環(huán)多次結(jié)合。在蟻群算法的每一次循環(huán)迭代后，將蟻群算法產(chǎn)生的最優(yōu)解加入到遺傳算法中，用以加快遺傳算法的迭代速度。同時，將遺傳算法算出的解設(shè)為較優(yōu)路徑來更新蟻群算法中的信息素分配，實現(xiàn)參數(shù)調(diào)整。多次相互指導(dǎo)能有效解決蟻群算法前期效率低和遺傳算法后期冗余迭代問題。

1.遺傳算法

遺傳算法（Genetic algorithm，GA）是根據(jù)達(dá)爾文的進(jìn)化論提出的仿生學(xué)算法，通過適應(yīng)度函數(shù)對較優(yōu)個進(jìn)行不斷選擇的過程。同時為保持種群的多樣性和具有求全局最優(yōu)解的能力，較優(yōu)個體需進(jìn)行交叉和變異操作產(chǎn)生新的種群。通過不斷地選擇和迭代進(jìn)化，從而找到最優(yōu)個體，也就是最優(yōu)解。

2.基本原理

遺傳算法由一些問題的初始解表示最初的父代基礎(chǔ)種群，也就是算法的初代進(jìn)化種群，然后通過編碼將每一個初始解用基因編碼的形式表示，通常每一個個體稱作為基因碼或者染色體表示具體的一個有效解。生物學(xué)上的遺傳特性都在染色體上，即是多個基因特征的的集合，表現(xiàn)為基因碼的形式，它決定了個體的具體特征集合。因此，在算法的開始需要將具體需要解的特征用基因碼來表示，即算法過程中的編碼，由于個體特征較多，編碼過程較為復(fù)雜，因此常常根據(jù)實際解的需求選取主要特征要求，然后通過 0 或者 1 的二進(jìn)制碼來表示，以此來簡化編碼過程。編碼完成即產(chǎn)生初始種群，之后按照“適者生存和優(yōu)勝劣汰”生物進(jìn)化理論，對每一個個體進(jìn)行適應(yīng)度計算，逐代選取進(jìn)化產(chǎn)生的較優(yōu)解。整個過程的不斷迭代就像自然界中生物種群的進(jìn)化一樣，越靠后的種群將有更好的適應(yīng)能力，末代種群中的最優(yōu)個體經(jīng)過解碼，即可以作為符合求解問題的近似最優(yōu)解。

結(jié)語：相較于室內(nèi)路徑規(guī)劃，室外交通路網(wǎng)復(fù)雜很多，從平面圖看有“節(jié)點多”和“路況復(fù)雜”等特點。本章首先基本蟻群算法和遺傳算法原理、流程和步驟做了詳細(xì)介紹，并做了對比和分析。然后在分析了仿生學(xué)算法解決復(fù)雜路網(wǎng)最優(yōu)路徑問題的優(yōu)越性基礎(chǔ)上，結(jié)合遺傳、蟻群算法的特性和優(yōu)點，設(shè)計一種混合遺傳蟻群算法（GACHA）用于行車路徑規(guī)劃中。該算法從基本蟻群算法入手，將兩種算法的尋優(yōu)過程循環(huán)多次結(jié)合，并在蟻群算法的每一次循環(huán)迭代后將蟻群算法產(chǎn)生的最優(yōu)解加入到遺傳算法中，加快了遺傳算法的迭代速度。同時該算法將遺傳算法算出的解設(shè)為較優(yōu)路徑來更新蟻群算法中的信息素分配，實現(xiàn)參數(shù)調(diào)整。多次的相互指導(dǎo)有效解決了蟻群算法前期效率低和遺傳算法后期冗余迭代問題。實驗結(jié)果表明，GACHA算法具有良好的優(yōu)化和收斂性，能夠準(zhǔn)確地找到滿足路網(wǎng)綜合要求的最優(yōu)路徑。

參考文獻(xiàn)：

[1]任懷志.探析云計算和物聯(lián)網(wǎng)技術(shù)組合應(yīng)用.農(nóng)業(yè)網(wǎng)絡(luò)信息.2011，（11）：83--84

[2]J Dean， S Ghemawat. Map Reduce： Simplified Data Processing on Large Clusters. Communications of the ACM， 2016

[2]張海江，趙建民，朱信忠.基于云計算的物聯(lián)網(wǎng)數(shù)據(jù)挖掘.研究與設(shè)計.2012，28（6）：10--13

基金項目：2021年浙江省大學(xué)生科技創(chuàng)新活動計劃暨新苗人才計劃項目—基于Android的智能停車引導(dǎo)系統(tǒng)研究與實現(xiàn)（2021R435008）資助。