基于改進(jìn)遺傳與神經(jīng)網(wǎng)絡(luò)的同事合乘匹配混合算法研究

龔文浩 張 凱

(南京信息工程大學(xué)自動(dòng)化學(xué)院 江蘇 南京 210044)

0 引 言

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

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

而遺傳算法與神經(jīng)網(wǎng)絡(luò)的融合算法在路徑規(guī)劃各個(gè)方面均取得了很有價(jià)值的研究成果。文獻(xiàn)[9]使用兩者的混合算法優(yōu)化了交通網(wǎng)絡(luò)信號(hào)燈優(yōu)先級(jí)。文獻(xiàn)[10]使用兩者的混合算法使用出行者信息進(jìn)行路徑選擇。文獻(xiàn)[11]使用兩者的混合算法進(jìn)行機(jī)器人的移動(dòng)路徑規(guī)劃。文獻(xiàn)[12]使用兩者混合算法進(jìn)行動(dòng)態(tài)的路徑規(guī)劃。

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

1 GA-ANN算法

遺傳算法具有搜索范圍廣、自適應(yīng)能力強(qiáng)、自學(xué)習(xí)能力強(qiáng)等優(yōu)點(diǎn),并且在大規(guī)模種族的背景下不易陷入局部最優(yōu)解,但是種群世代的迭代過程占用大量的時(shí)間資源,所以結(jié)合人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練權(quán)重思想,將多次遺傳算法產(chǎn)生的最優(yōu)解基因組的權(quán)重載入網(wǎng)絡(luò),在規(guī)劃路徑時(shí),直接調(diào)用網(wǎng)絡(luò)結(jié)構(gòu),以達(dá)到在路徑規(guī)劃時(shí)具有足夠的快速性和及時(shí)性。

1.1 遺傳算法部分

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

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

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

編排方式2。單位同事的合乘不同于運(yùn)輸合乘問題,染色體并不是一輛車從開始到結(jié)束的地點(diǎn)集合,而是同一單位的多輛車的位移集合。每一個(gè)車的行駛路徑代表一個(gè)基因,多個(gè)基因組成一個(gè)染色體。一個(gè)基因由兩個(gè)實(shí)數(shù)組成,例如基因1-2代表處于第一個(gè)坐標(biāo)位置駕駛?cè)笋{車帶著第二個(gè)坐標(biāo)位置的同事前往公司,前面的實(shí)數(shù)1表示駕駛?cè)薼1所在位置,后者實(shí)數(shù)2表示乘坐人l2所在位置。

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

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

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

1.1.1初始種群的生成

初始種群的無條件隨機(jī)生成會(huì)降低遺傳算法的效率,因此我們選擇在生成初始種群時(shí)參考一些先驗(yàn)條件來優(yōu)化算法,提升算法的效率。考慮到駕駛?cè)说某鲂畜w驗(yàn),當(dāng)參與同事合乘行為時(shí),前進(jìn)方向應(yīng)當(dāng)與單位方向大致一致。因此,在執(zhí)行合乘操作時(shí),乘車人的經(jīng)緯度位置應(yīng)當(dāng)位于駕車人位置和單位所在地之間。以li表示駕車人的位置,以lj表示乘車人位置,li∈U,lj∈U且li≠lj,偏移量α、β、η、λ為微小值,當(dāng)滿足上述先驗(yàn)條件時(shí):

(1)

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

1.1.2適應(yīng)度函數(shù)

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

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

(2)

在遺傳算法中,個(gè)體的適應(yīng)度越大表示該個(gè)體對(duì)于環(huán)境適應(yīng)越強(qiáng),越接近最優(yōu)解,但就運(yùn)輸問題來說,路程越短代表越優(yōu),所以將染色體距離和加1的倒數(shù)當(dāng)做適應(yīng)度函數(shù),表示為:

(3)

1.1.3交叉過程

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

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

步驟2隨機(jī)選取交叉點(diǎn),但由于單個(gè)基因是兩個(gè)位置點(diǎn)構(gòu)成的,如1-2、3-4等,因此在選取交叉點(diǎn)時(shí),只可以選取偶數(shù)交叉點(diǎn),以達(dá)到不破壞原有基因的效果。假設(shè)去第一個(gè)偶數(shù)交叉點(diǎn)和最后一個(gè)偶數(shù)交叉點(diǎn),染色體1保留的基因?yàn)閤-x|3-4|5-6|x-x,染色體2保留的基因?yàn)閤-x|6-5|4-3|x-x。

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

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

1.1.4變異過程

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

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

步驟2隨機(jī)選取一個(gè)變異點(diǎn),從節(jié)點(diǎn)集合U中選取一個(gè)非原基因替代原基因。如染色體1-2|3-4|5-6|7-8,選取第3個(gè)基因位,用基因‘7’代替基因‘3’染色體變?yōu)?-2|7-4|5-6|7-8。

步驟3找到染色體中非變異點(diǎn)中與變異基因位基因相同的點(diǎn),用包含在節(jié)點(diǎn)集合中,不在染色體中的基因互換,如上述染色體1-2|7-4|5-6|7-8變?yōu)?-2|7-4|5-6|3-8。

當(dāng)節(jié)點(diǎn)集合U中的基因全部出現(xiàn)在染色體中時(shí),變異操作可以理解為將一條染色體中的兩個(gè)基因位進(jìn)行互換。

1.2 ANN算法部分

由于單位同事的合乘問題總體上歸于靜態(tài)合乘問題,同時(shí),由于各種臨時(shí)變化,合乘問題也要具備一定的即時(shí)性和靈活性,路徑規(guī)劃還需進(jìn)一步提升速度,所以引入人工神經(jīng)網(wǎng)絡(luò),對(duì)于零散的節(jié)點(diǎn)進(jìn)行二次規(guī)劃,提高規(guī)劃的速度及效率。

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

1.2.1網(wǎng)絡(luò)搭建及權(quán)重載入

由于本文的合乘是一對(duì)一模式,故將單位人數(shù)n作為神經(jīng)網(wǎng)絡(luò)輸入層X神經(jīng)元個(gè)數(shù),同時(shí)將n作為神經(jīng)網(wǎng)絡(luò)隱層Y神經(jīng)元個(gè)數(shù),隱層為全連接層,輸出層為一對(duì)一的匹配結(jié)果。通過建立各節(jié)點(diǎn)之間對(duì)應(yīng)關(guān)系。網(wǎng)絡(luò)實(shí)現(xiàn)輸入值為某個(gè)節(jié)點(diǎn),輸出值為匹配結(jié)果。圖1為n為6時(shí)的單個(gè)神經(jīng)元網(wǎng)絡(luò)圖。

圖1 ANN單一節(jié)點(diǎn)的結(jié)構(gòu)圖

圖2 坐標(biāo)標(biāo)記圖

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

(4)

將兩層神經(jīng)元之間的連接權(quán)重設(shè)置為兩者對(duì)應(yīng)節(jié)點(diǎn)為因參與合乘產(chǎn)生的繞行距離rij(1≤i≤n,1≤j≤n),由于繞行距離與結(jié)果負(fù)相關(guān),所以修正權(quán)重wij=C-rij,權(quán)重w應(yīng)當(dāng)滿足條件:wij≥0。中間層的輸出為:

(5)

考慮到無論是駕駛?cè)嘶蛘叱塑嚾说某鲂畜w驗(yàn)是很重要的因素,因此中間層和輸出層的權(quán)重hij采用前期其他乘客對(duì)該駕駛?cè)笋{駛行為的評(píng)價(jià),由于wij和Yi均小于1,所以hij不宜過大,應(yīng)保證hij∈(0,0.5),輸出層的輸入公式為:

(6)

進(jìn)入輸出層神經(jīng)元后,神經(jīng)元做篩選操作,取出最大的值輸出,輸出值為Yi的下標(biāo)i,表示合乘匹配對(duì)象是第i個(gè)節(jié)點(diǎn)的同事。

1.2.2約束條件的分布化

對(duì)于合乘問題,在實(shí)踐中有諸多限制。首先,有時(shí)間約束條件,如出行的時(shí)間要與合乘執(zhí)行的時(shí)間有所重合。有司機(jī)選擇約束條件,如司機(jī)不愿意繞路太遠(yuǎn)。有乘客選擇約束條件,如不愿乘坐異性的車輛。這些不同的約束條件往往會(huì)使問題復(fù)雜化,而由于個(gè)體的差異性,對(duì)于不同對(duì)象,這些約束條件往往區(qū)別較大。

通過使用人工神經(jīng)網(wǎng)絡(luò)可以將這些個(gè)體的差異選擇與路徑規(guī)劃算法本身區(qū)分,神經(jīng)元本身帶有屬性,如司機(jī)性別、司機(jī)可接受的繞行距離等。只有滿足條件才可激活神經(jīng)元進(jìn)行選擇。

2 實(shí)驗(yàn)及結(jié)果分析

2.1 實(shí)驗(yàn)環(huán)境及測(cè)試目的

本文采用Python語言進(jìn)行改進(jìn)GA-ANN算法的實(shí)現(xiàn)與測(cè)試。測(cè)試節(jié)點(diǎn)配置為Inter(R) Core(TM) i5-4210M 2.6 GHz,內(nèi)存8 GB,操作系統(tǒng)64位Windows 8.1。

實(shí)驗(yàn)旨在測(cè)試改進(jìn)GA-ANN算法的有效性及匹配結(jié)果效率,以及對(duì)比傳統(tǒng)的遺傳算法和融入神經(jīng)網(wǎng)絡(luò)前后的算法效率。

2.2 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

通過調(diào)查走訪,得到南京一單位的33名職工的地址信息,并將地址信息轉(zhuǎn)化為經(jīng)緯度坐標(biāo)保存在TXT文件中。將這些地址信息作為基因,將地址編號(hào)的拼接組合作為染色體,測(cè)試試驗(yàn)中,種群初始數(shù)量為200個(gè),迭代次數(shù)為200次,交叉率為0.45,變異率為0.1。

2.3 實(shí)驗(yàn)測(cè)試及分析

2.3.1算法有效性測(cè)試

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

圖3 種族進(jìn)化曲線

圖4 駕駛路徑圖

因?yàn)楸疚乃惴▽⒕嚯x和倒數(shù)作為適應(yīng)度函數(shù),而不同組合的距離之和是非線性的,為了保證基因組合的多樣性,將適應(yīng)度函數(shù)大于0.004 5的組合作為滿足條件的染色體。經(jīng)過多次實(shí)驗(yàn),發(fā)現(xiàn)在算法第100代-第125代之間會(huì)找出優(yōu)秀的染色體,即多輛車輛合乘的組合表示。結(jié)果表明,改進(jìn)的GA對(duì)于同事合乘問題的求解具有有效性。

2.3.2算法效率對(duì)比測(cè)試

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

表1 運(yùn)算結(jié)果表

實(shí)驗(yàn)2是融合人工神經(jīng)網(wǎng)絡(luò)前后改進(jìn)GA的對(duì)比測(cè)試。

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

表2 運(yùn)算結(jié)果表

通過GA-ANN算法可以得出合乘對(duì)象的匹配結(jié)果,以輸入22、輸出8的結(jié)果為例,實(shí)際的意義為從編號(hào)22的起點(diǎn)出發(fā),途經(jīng)8號(hào)位置接上合乘的同事前往單位。

3 結(jié) 語

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

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