師揚(yáng)松 成都市實(shí)驗(yàn)外國語學(xué)校西區(qū)2019屆

1 引言

蟻群優(yōu)化（Ant colony optimization，ACO）是一種模仿螞蟻覓食行為的智能仿生算法[1]。蟻群釋放特殊的化學(xué)物質(zhì)信息素來傳達(dá)信息，并通過感知信息素濃度來選擇前進(jìn)道路。通過研究這種行為，結(jié)合實(shí)際場景，可以解決很多難題并大大提高效率。蟻群算法是一種用來尋找優(yōu)化路徑的概率型算法[2-7]。這種算法具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是一種啟發(fā)式全局優(yōu)化算法。蟻群算法已經(jīng)在組合優(yōu)化、函數(shù)優(yōu)化、網(wǎng)絡(luò)路由、機(jī)器人路徑規(guī)劃、數(shù)據(jù)挖掘以及大規(guī)模集成電路的綜合布線設(shè)計(jì)等領(lǐng)域獲得了廣泛的應(yīng)用，并取得了較好的效果[8]。例如，在[9]中將蟻群算法的正反饋思想與分布式計(jì)算應(yīng)用到概率路由中，收集機(jī)會(huì)網(wǎng)絡(luò)的節(jié)點(diǎn)和拓?fù)湫畔?，并結(jié)合這些信息，設(shè)計(jì)基于蟻群算法的概率路由，可以提高機(jī)會(huì)網(wǎng)絡(luò)的消息傳輸性能。[10]中提出的改進(jìn)的蟻群聚類算法應(yīng)用在了學(xué)生成績評價(jià)中，基于實(shí)驗(yàn)數(shù)據(jù)，得到了聚類結(jié)果，并對聚類分析的結(jié)果做出相應(yīng)解釋，提出了針對性的策略和建議，證明了改進(jìn)的蟻群聚類算法的有效性。蟻群算法可以高效的向用戶提供最優(yōu)路徑，但是現(xiàn)有研究中蟻群算法收斂速度較慢而且容易發(fā)生停滯，一些文章中通過改進(jìn)蟻群算法，來彌補(bǔ)這些缺陷從而達(dá)到很好的效果[11-14]。例如，根據(jù)A*算法的啟發(fā)式信息改進(jìn)蟻群算法的路徑選擇策略，加快算法收斂速度[15]。

本文基于蟻群算法的優(yōu)點(diǎn)，將其應(yīng)用于一個(gè)簡易交通尋路模型中，為此模型提供一種快速尋路解決方法。該模型為一個(gè)點(diǎn)對點(diǎn)三條通路的模型，通過設(shè)置不同的站點(diǎn)人員數(shù)目和不同的節(jié)點(diǎn)之間的時(shí)間開銷來實(shí)現(xiàn)不同的交通路況。從該模型中抽象出一個(gè)站點(diǎn)人員數(shù)矩陣和一個(gè)節(jié)點(diǎn)間的時(shí)間開銷矩陣，輸出這兩個(gè)矩陣來觀察算法的運(yùn)算情況。通過設(shè)置相同的矩陣數(shù)據(jù)，對比常規(guī)方法與應(yīng)用螞蟻算法后的時(shí)間開銷，最終證明應(yīng)用算法后可以大大提高交通效率。該算法優(yōu)點(diǎn)在于可以根據(jù)模型不同變量生成一種尋路花費(fèi)時(shí)間最短的方案算法。在本文中第三部分通過與常規(guī)算法相比，證明了其可以大大減少時(shí)間開銷提高效率。在小區(qū)、游樂園或者大學(xué)校園的觀光車或通勤車有很大的應(yīng)用空間。

2 算法原理

首先，本文中提出了一個(gè)簡易的通勤車模型。模型中從起點(diǎn)Q到終點(diǎn)S有三條互不相通的路。三條路上設(shè)置不同的站點(diǎn)數(shù)目、每個(gè)站點(diǎn)等待人員數(shù)目和站與站之間的間距。將模型抽象成兩個(gè)矩陣，一個(gè)站點(diǎn)人員數(shù)目矩陣和一個(gè)時(shí)間開銷矩陣。通過觀察兩個(gè)矩陣的數(shù)據(jù)變化可以驗(yàn)證算法的優(yōu)劣。三條路上規(guī)定必有三輛車分別通過，接送人員。在每輛車通過本車路段到達(dá)終點(diǎn)后會(huì)釋放信息素。通過不同的信息素起點(diǎn)安排合適數(shù)目的車輛進(jìn)入相應(yīng)路段。

圖1 算法流程圖

當(dāng)每輛車到達(dá)站點(diǎn)后根據(jù)車上的空余座位和站點(diǎn)人數(shù)作對比，可得出離開站點(diǎn)所剩人員和空車位數(shù)目。到終點(diǎn)后發(fā)出信息素，依據(jù)濃度判斷派出車輛數(shù)目，直到每個(gè)站點(diǎn)人員接送完畢。算法的流程圖如圖1所示。

每個(gè)站點(diǎn)之間都有不同的時(shí)間開銷，在一個(gè)設(shè)定好的模型里，即間距和人員分布一樣，在應(yīng)用本文提出的算法和普通情況下做出對比。本文算法可以大大提高效率。此模型雖然簡單，但是有很多應(yīng)用，除了在小區(qū)校區(qū)通勤車的尋路中應(yīng)用外，還可以在游戲中使用。是一個(gè)非常實(shí)用的算法模型。

3 仿真實(shí)現(xiàn)

按上述流程圖，用Dev-C++實(shí)現(xiàn)算法，創(chuàng)建一個(gè)簡易交通模型如圖2所示。通過常規(guī)方案可以得出初始的總時(shí)間開銷。然后在同樣的模型下應(yīng)用螞蟻算法后得出的時(shí)間開銷會(huì)小很多。通過數(shù)據(jù)對比，可以證明應(yīng)用了提出的算法后可以大大提高尋路的效率。

圖2 簡易交通模型圖。

在仿真中輸出了常規(guī)算法下設(shè)置的站點(diǎn)數(shù)、站點(diǎn)間開銷站點(diǎn)人員數(shù)目和每個(gè)時(shí)間點(diǎn)通過站點(diǎn)后的人員分布結(jié)果與總時(shí)間開銷如圖3所示。此處使用矩陣形式展示。并且在每個(gè)時(shí)間單位都會(huì)輸出站點(diǎn)人

圖3 常規(guī)算法下的仿真結(jié)果

員矩陣，實(shí)時(shí)觀察矩陣變化，直到人員接送完畢為止。最后算法出總時(shí)間開銷。在輸入設(shè)置過程中，因?yàn)榫仃嚩x的是三行四列矩陣，可以在某個(gè)點(diǎn)設(shè)置為0，同樣對應(yīng)的時(shí)間開銷設(shè)置成0，這樣可以表示此處沒有站點(diǎn)，并不消耗空余座位和時(shí)間開銷。在關(guān)于路程或之間開銷上，每條路上的車通過所有站點(diǎn)到達(dá)終點(diǎn)后就會(huì)將人員送下車。此時(shí)車上全部是空余座位，如果沒有結(jié)束運(yùn)送，則車會(huì)從終點(diǎn)返回起始點(diǎn)，同起始點(diǎn)按照算法安排的車一起進(jìn)入尋路中。從終點(diǎn)到起點(diǎn)的返回車輛所花費(fèi)的開銷會(huì)根據(jù)設(shè)置的站點(diǎn)間距不同而不同，相當(dāng)于是原路返回。如此可以較為完善的模擬實(shí)際過程中的交通情況。

圖4所示為應(yīng)用螞蟻算法后的仿真結(jié)果。同樣的模型下最后總的時(shí)間開銷應(yīng)用算法后比應(yīng)用常規(guī)方法要少很多。這證明了應(yīng)用螞蟻算法后可以大大提高效率。

圖4 改進(jìn)算法后的仿真結(jié)果

4 總結(jié)

本文基于蟻群算法的優(yōu)點(diǎn)，通過在一個(gè)簡易通勤車尋路模型中實(shí)際使用并仿真驗(yàn)證，應(yīng)用蟻群算法后可以提高效率。為此模型提供一種快速尋路解決方法。該模型雖然簡單，但是在很多實(shí)際應(yīng)用中都會(huì)存在。而該算法優(yōu)點(diǎn)在于可以根據(jù)模型不同變量生成一種尋路花費(fèi)時(shí)間最短的方案算法。在小區(qū)、游樂園或者大學(xué)校園的觀光車或通勤車有很大的應(yīng)用空間。

而為了檢驗(yàn)本文提出的算法，本文所做模型是從實(shí)際生活中抽象出的簡易模型。模型可以做出更進(jìn)一步的改進(jìn)，使路況復(fù)雜化。在路與路之間做聯(lián)通路徑結(jié)合成網(wǎng)狀，這樣產(chǎn)生的路就會(huì)變得多樣化、復(fù)雜化，從起始點(diǎn)到終點(diǎn)的路不再單一。而且車輛的分配也不會(huì)按照單線路運(yùn)行。通過判斷信息素的濃度和當(dāng)前路線的狀況，排列每種路線的優(yōu)先級(jí)，使就近的車輛跨線到另外一條路線，先完成優(yōu)先級(jí)高的路線。以上都是點(diǎn)對點(diǎn)的情況，這種模型不僅適合于交通或者游戲模型，同時(shí)也可以模擬點(diǎn)對點(diǎn)通信。假如將終點(diǎn)設(shè)置為多個(gè)，則會(huì)變成一對多的情況，假如應(yīng)用蟻群算法在樹形結(jié)構(gòu)中收索，同時(shí)每個(gè)節(jié)點(diǎn)設(shè)置不同權(quán)重，每個(gè)節(jié)點(diǎn)之間設(shè)置不同開銷，就是該模型該進(jìn)程一對多的情況。更進(jìn)一步可以設(shè)置為多對多模型、三維立體模型，不同模型可以用于不同實(shí)際情況，可以分析或?qū)嵱迷谏钌a(chǎn)中。

[1]王藝睿.蟻群算法在動(dòng)態(tài)優(yōu)化問題上的應(yīng)用研究[D].東華大學(xué)，2017.

[2]游戲引擎最短路徑搜索優(yōu)化遺傳算法設(shè)計(jì)[J].黎忠文，覃志東，王全宇，倪仲余.計(jì)算機(jī)應(yīng)用研究.2014(01).

[3]Dijkstra算法中的多鄰接點(diǎn)與多條最短路徑問題[J].王樹西，李安渝.計(jì)算機(jī)科學(xué).2014(06).

[4]喻環(huán).改進(jìn)蟻群算法在機(jī)器人路徑規(guī)劃上的應(yīng)用研究[D].安徽大學(xué)，2017.

[5]劉建華，楊建國，劉華平，耿鵬，高蒙.基于勢場蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015，46(09)：18-27.

[6]基于Laguerre圖的自優(yōu)化A-Star無人機(jī)航路規(guī)劃算法[J].魏瑞軒，許卓凡，王樹磊，呂明海.系統(tǒng)工程與電子技術(shù).2015(03).

[7]遺傳算法改進(jìn)策略研究[J].夏季.信息與電腦(理論版).2012(11).

[8]楊劍峰.蟻群算法及其應(yīng)用研究[D].浙江大學(xué)，2007.

[9]賈磊磊.機(jī)會(huì)網(wǎng)絡(luò)中基于蟻群算法的概率路由的設(shè)計(jì)與實(shí)現(xiàn)[D].內(nèi)蒙古大學(xué)，2017.

[10]周穎.基于蟻群算法的聚類分析在學(xué)生成績中的研究[D].南昌大學(xué)，2015.

[11]張家善.基于改進(jìn)蟻群算法的物流配送車輛路徑優(yōu)化研究[D].遼寧工程技術(shù)大學(xué)，2014.

[12]曹潔，耿振節(jié).一種改進(jìn)蟻群算法在撿球機(jī)器人多目標(biāo)路徑規(guī)劃中的應(yīng)用[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36(10)：2384-2389.

[13]左敏，許華榮.基于改進(jìn)蟻群算法的智能小車路徑規(guī)劃[J].心智與計(jì)算，2011，5(02)：60-68

[14]裴振兵，陳雪波.改進(jìn)蟻群算法及其在機(jī)器人避障中的應(yīng)用[J].智能系統(tǒng)學(xué)報(bào)，2015，10(01)：90-96.

[15]張志協(xié)，曹陽.基于改進(jìn)型蟻群算法的最優(yōu)路徑問題求解[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21(10)：76-80.