基于改進遺傳與神經網絡的同事合乘匹配混合算法研究

龔文浩 張 凱

(南京信息工程大學自動化學院 江蘇 南京 210044)

0 引 言

為緩解交通擁堵情況,針對單位同事通勤合乘問題出現越來越多的討論,文獻[1]在2010年提出鄰里合乘的概念,以社區為單位,進行合乘。文獻[2]提出在2020年新冠疫情背景下的高效又安全的通勤合乘。但專門針對該問題的合乘匹配算法還未研究充分。

遺傳算法是常用的求解路徑選擇問題的常用算法,其具有效率高、全局求解性好、簡單通用等優勢。人工神經網絡由于其高效性、高度智能性,以及調用時的快速性,也在近些年在交通領域得到大規模應用。文獻[3]研究了自適應的遺傳算法求解滿足個體偏好的合乘匹配問題。文獻[4]混合遺傳算法和模擬退火算法優化了合乘末端路徑問題。文獻[5]使用改進遺傳算法解決路徑規劃偏角過大的問題。文獻[6]講述遺傳算法在規避障礙的路徑規劃問題中的使用。文獻[7]使用遺傳算法研究復雜地貌下的路徑規劃。文獻[8]使用遺傳和蟻群算法應急物資的路徑規劃進行研究。

而遺傳算法與神經網絡的融合算法在路徑規劃各個方面均取得了很有價值的研究成果。文獻[9]使用兩者的混合算法優化了交通網絡信號燈優先級。文獻[10]使用兩者的混合算法使用出行者信息進行路徑選擇。文獻[11]使用兩者的混合算法進行機器人的移動路徑規劃。文獻[12]使用兩者混合算法進行動態的路徑規劃。

針對現階段同事合乘整體出行效率較低,相關算法發展速度慢,并且沒有明確具體求解該問題算法的情況,本文提出一種基于遺傳算法和人工神經網絡的同事合乘路徑匹配混合算法(Genetic Algorithm-Artificial Neural Network,GA-ANN),利用遺傳算法全局求解性好,不易陷入局部最優解的優勢,來獲取區域內整體通勤效率最高的合乘匹配組合。通過對初始種群與交叉過程的改進進一步提升算法效率,再利用人工神經網絡讀取權值輸出的過程,提高算法的快速性。

1 GA-ANN算法

遺傳算法具有搜索范圍廣、自適應能力強、自學習能力強等優點,并且在大規模種族的背景下不易陷入局部最優解,但是種群世代的迭代過程占用大量的時間資源,所以結合人工神經網絡的訓練權重思想,將多次遺傳算法產生的最優解基因組的權重載入網絡,在規劃路徑時,直接調用網絡結構,以達到在路徑規劃時具有足夠的快速性和及時性。

1.1 遺傳算法部分

在單位同事合乘的尋徑方法中,由于約束條件的苛刻,傳統的遺傳算法,在初始化、交叉和變異階段會產生大量的不滿足實際需求的不可行解。對于上述情況,采用下文特定方式去按步驟產生初始種群以及執行交叉、變異操作,以產生可行解,提升算法的效率。

作出以下定義解釋該問題的基因編排方式以及約束條件。

編排方式1。將員工所在位置定義為節點,以li表示第i個員工所在的位置(i≥0),li表示工作單位所在位置,li中包含經、緯度兩個位置信息,li={lij,liw},節點集U包括所有的節點。

編排方式2。單位同事的合乘不同于運輸合乘問題,染色體并不是一輛車從開始到結束的地點集合,而是同一單位的多輛車的位移集合。每一個車的行駛路徑代表一個基因,多個基因組成一個染色體。一個基因由兩個實數組成,例如基因1-2代表處于第一個坐標位置駕駛人駕車帶著第二個坐標位置的同事前往公司,前面的實數1表示駕駛人l1所在位置,后者實數2表示乘坐人l2所在位置。

編排方式3。染色體由眾多基因組成,如染色體1-2|3-4|5-6|7-8|…,全部需要前往公司的車輛行駛位移組合基因組成了一條染色體。不同的組合情況,構成不同的染色體。

約束條件1。由于一個實數就代表一個員工參與到合乘行為中,故每一條染色體的基因具有不可重復性。

約束條件2。單位同事的合乘與普通順風車合乘模式有比較大的差別,駕駛發起人的駕駛體驗很重要,所以繞行的距離要控制在合理的范圍內。

1.1.1初始種群的生成

初始種群的無條件隨機生成會降低遺傳算法的效率,因此我們選擇在生成初始種群時參考一些先驗條件來優化算法,提升算法的效率?？紤]到駕駛人的出行體驗,當參與同事合乘行為時,前進方向應當與單位方向大致一致。因此,在執行合乘操作時,乘車人的經緯度位置應當位于駕車人位置和單位所在地之間。以li表示駕車人的位置,以lj表示乘車人位置,li∈U,lj∈U且li≠lj,偏移量α、β、η、λ為微小值,當滿足上述先驗條件時:

(1)

單個li-lj的組合構成基因,多個基因構成染色體,不同的多個染色體加上一輪輪盤賭的方法,可以生成具有優勢的第一代種群,從而提高遺傳算法的搜索效率。

1.1.2適應度函數

在生成種群之后,將每一條染色體上每一對基因組成的路程和作為評價染色體優劣的評價指標,路程和越短,染色體越優秀。每一對基因的路程是指駕車人位置到達乘車人位置的距離Hij加上駕車人位置到達單位位置Hj0的距離之和。由于合乘問題需要以實際的城區地圖為基礎,按照駕駛路程計算距離并同時需要考慮特殊道路例如單行道,禁左路口等因素,因此距離H通過調用高德地圖的API接口,計算實際需要的駕駛距離。

若一條染色體長度為n,則完整的染色體表示的距離和為:

(2)

在遺傳算法中,個體的適應度越大表示該個體對于環境適應越強,越接近最優解,但就運輸問題來說,路程越短代表越優,所以將染色體距離和加1的倒數當做適應度函數,表示為:

(3)

1.1.3交叉過程

遺傳算法常用的單點交叉、重組等交叉方法,而對于此問題會產生大量的不滿足約束條件1的染色體,不適用于此問題。因此,采用順序交叉的方式,具體過程如下:

步驟1首先從種群中隨機挑選出兩個染色體,如染色體1-2|3-4|5-6|7-8和染色體8-7|6-5|4-3|2-1。

步驟2隨機選取交叉點,但由于單個基因是兩個位置點構成的,如1-2、3-4等,因此在選取交叉點時,只可以選取偶數交叉點,以達到不破壞原有基因的效果。假設去第一個偶數交叉點和最后一個偶數交叉點,染色體1保留的基因為x-x|3-4|5-6|x-x,染色體2保留的基因為x-x|6-5|4-3|x-x。

步驟3選取好交叉點后,采用順序交叉法,對于染色體1,取出保留部分x-x|3-4|5-6|x-x,然后選取染色體2第二個偶數交叉因子后的部分組成編碼2-1|8-7|6-5|4-3,刪除與第一個染色體重復基因因子|3-4|5-6|,將剩下的因子2-1|8-7順序填入第一個染色體,染色體為8-7|3-4|5-6|2-1,同理染色體2變為1-2|6-5|4-3|7-8。

上述交叉過程可以有效地改變一部分基因,保留下一部分基因,從而生成染色體的同時可以保留下部分基因。

1.1.4變異過程

變異操作是防止遺傳算法陷入局部最優解以及豐富種群的重要操作。由于約束條件1的存在,染色體中一位基因的改變一定伴隨著其他基因的改變。具體過程如下:

步驟1從交叉完畢的種群中找出一條染色體。

步驟2隨機選取一個變異點,從節點集合U中選取一個非原基因替代原基因。如染色體1-2|3-4|5-6|7-8,選取第3個基因位,用基因‘7’代替基因‘3’染色體變為1-2|7-4|5-6|7-8。

步驟3找到染色體中非變異點中與變異基因位基因相同的點,用包含在節點集合中,不在染色體中的基因互換,如上述染色體1-2|7-4|5-6|7-8變為1-2|7-4|5-6|3-8。

當節點集合U中的基因全部出現在染色體中時,變異操作可以理解為將一條染色體中的兩個基因位進行互換。

1.2 ANN算法部分

由于單位同事的合乘問題總體上歸于靜態合乘問題,同時,由于各種臨時變化,合乘問題也要具備一定的即時性和靈活性,路徑規劃還需進一步提升速度,所以引入人工神經網絡,對于零散的節點進行二次規劃,提高規劃的速度及效率。

神經網絡是模仿人神經元的工作,具體操作流程是先搭建網絡,然后前向傳播,之后根據損失函數反向修正權重,使神經網絡模型能夠快速準確地執行任務。但是人工神經網絡根據損失函數采用梯度下降法,所以在訓練過程中有收斂慢、易產生局部最優解等問題,因此用遺傳算法的迭代過程代替人工神經網絡的參數調整過程,用遺傳算法迭代后的優選種族匹配組合概率代替人工神經網絡調整的權值參數。利用神經網絡強大的非線性組合映射能力,可以快速地給出路徑選擇,從而大幅度提高整體算法的運行速度以及效率。

1.2.1網絡搭建及權重載入

由于本文的合乘是一對一模式,故將單位人數n作為神經網絡輸入層X神經元個數,同時將n作為神經網絡隱層Y神經元個數,隱層為全連接層,輸出層為一對一的匹配結果。通過建立各節點之間對應關系。網絡實現輸入值為某個節點,輸出值為匹配結果。圖1為n為6時的單個神經元網絡圖。

圖1 ANN單一節點的結構圖

圖2 坐標標記圖

使用前面多組遺傳算法運行后產生染色體,將整條染色體切割成一對一的形如1-2、3-4的基因組,將滿足約束條件二中規定繞行距離C的基因組以首位和尾位分別歸類統計,首位為駕駛位,代表選擇駕車出行的節點,尾位為乘坐位,代表選擇乘車出行的節點。兩種模式網絡相同,區別在于載入的網絡權重。以前者為例,篩選出首位相同,但尾位不同的不同基因組出現的概率作為中間層神經元Yi(1≤i≤n)的值,如節點數為6染色體中首位1的基因組1-2、1-5出現的概率分別為0.2、0.8,其他為0。則Yi(1≤i≤6)為0、0.2、0、0、0.8、0。神經元數值Yi(1≤i≤n)應滿足下列約束條件:

(4)

將兩層神經元之間的連接權重設置為兩者對應節點為因參與合乘產生的繞行距離rij(1≤i≤n,1≤j≤n),由于繞行距離與結果負相關,所以修正權重wij=C-rij,權重w應當滿足條件:wij≥0。中間層的輸出為:

(5)

考慮到無論是駕駛人或者乘車人的出行體驗是很重要的因素,因此中間層和輸出層的權重hij采用前期其他乘客對該駕駛人駕駛行為的評價,由于wij和Yi均小于1,所以hij不宜過大,應保證hij∈(0,0.5),輸出層的輸入公式為:

(6)

進入輸出層神經元后,神經元做篩選操作,取出最大的值輸出,輸出值為Yi的下標i,表示合乘匹配對象是第i個節點的同事。

1.2.2約束條件的分布化

對于合乘問題,在實踐中有諸多限制。首先,有時間約束條件,如出行的時間要與合乘執行的時間有所重合。有司機選擇約束條件,如司機不愿意繞路太遠。有乘客選擇約束條件,如不愿乘坐異性的車輛。這些不同的約束條件往往會使問題復雜化,而由于個體的差異性,對于不同對象,這些約束條件往往區別較大。

通過使用人工神經網絡可以將這些個體的差異選擇與路徑規劃算法本身區分,神經元本身帶有屬性,如司機性別、司機可接受的繞行距離等。只有滿足條件才可激活神經元進行選擇。

2 實驗及結果分析

2.1 實驗環境及測試目的

本文采用Python語言進行改進GA-ANN算法的實現與測試。測試節點配置為Inter(R) Core(TM) i5-4210M 2.6 GHz,內存8 GB,操作系統64位Windows 8.1。

實驗旨在測試改進GA-ANN算法的有效性及匹配結果效率,以及對比傳統的遺傳算法和融入神經網絡前后的算法效率。

2.2 實驗數據及參數設置

通過調查走訪,得到南京一單位的33名職工的地址信息,并將地址信息轉化為經緯度坐標保存在TXT文件中。將這些地址信息作為基因,將地址編號的拼接組合作為染色體,測試試驗中,種群初始數量為200個,迭代次數為200次,交叉率為0.45,變異率為0.1。

2.3 實驗測試及分析

2.3.1算法有效性測試

采用前期調查的文本坐標數據對本文算法進行驗證。圖3為隨機抽取的一幅適應度函數最大值、平均值曲線圖,可以看出遺傳算法在進入60代前快速收斂,75代左右收斂變慢,但隨后種族繼續得到優化并在150代附近獲得近似的最優解。

圖3 種族進化曲線

圖4 駕駛路徑圖

因為本文算法將距離和倒數作為適應度函數,而不同組合的距離之和是非線性的,為了保證基因組合的多樣性,將適應度函數大于0.004 5的組合作為滿足條件的染色體。經過多次實驗,發現在算法第100代-第125代之間會找出優秀的染色體,即多輛車輛合乘的組合表示。結果表明,改進的GA對于同事合乘問題的求解具有有效性。

2.3.2算法效率對比測試

實驗1是改進GA與限制繞行距離合乘搜索算法的對比測試。由于傳統的合乘搜索算法在進行搜索時,會由于繞行約束距離的限制,導致出現合乘的效率不高,但搜索速度足夠。而對于改進的GA,通過種群世代的迭代過程,大幅度地提升了適應度,減少了出行總距離。從結果來看,改進的GA得出的較優解染色體中的基因,從整體來看,近似最優解的結果要優于合乘搜索算法得出的解。同時,由于在生成初始種群的時候加入了先驗條件,相對隨機生成初始種群,在迭代次數上也會有一定的降低,提升了效率。

表1 運算結果表

實驗2是融合人工神經網絡前后改進GA的對比測試。

融合人工神經網絡前,改進的GA在結果上已經可以得到較好的解,但是由于合乘問題對于求解時間的要求,在算法速度上還需要進一步突破。同時。在實際運用中,常常是點對點的具有約束條件的搜索,為了使算法具有實際的實用性,融入ANN神經網絡,加快整體的算法運行速度。

表2 運算結果表

通過GA-ANN算法可以得出合乘對象的匹配結果,以輸入22、輸出8的結果為例,實際的意義為從編號22的起點出發,途經8號位置接上合乘的同事前往單位。

3 結 語

同事合乘是緩解上下班通勤擁堵的解決辦法之一,可以有效地減少上路車輛,減少一個單位所有員工駕車出行的總距離,從而達到節能減排、減少擁堵等效果。本文提出的遺傳算法和人工神經網相融合的合乘匹配算法,通過帶先驗條件的初始種群生成,特殊的交叉、變異操作后,可以有效地得出結果,再加上人工神經網絡的部分以提高算法整體的快速性。

從結果來看,該算法可以快速、有效地找到合乘的優勢組合,從整體上將出行距離充分縮短,提高出行效率,降低出行成本。