蟻群算法在智能交通領(lǐng)域的應(yīng)用

白曉++王婭

摘 要 智能交通是將電子信息技術(shù)與傳統(tǒng)的交通運(yùn)輸產(chǎn)業(yè)相結(jié)合而產(chǎn)生的服務(wù)系統(tǒng)，它以信息技術(shù)、控制技術(shù)等技術(shù)為基礎(chǔ)，借助新一代電子信息技術(shù)的發(fā)展，提供了高效的、適應(yīng)現(xiàn)代發(fā)展的交通運(yùn)輸管理系統(tǒng)。智能交通系統(tǒng)涉及到交通領(lǐng)域的多個(gè)方面，其中最優(yōu)路徑選擇是智能交通系統(tǒng)的一個(gè)典型問(wèn)題，適合采用蟻群算法求解。

【關(guān)鍵詞】智能交通系統(tǒng) 蟻群算法 信息素 最優(yōu)路徑 組合優(yōu)化

交通運(yùn)輸?shù)默F(xiàn)代化使人們享受便利的同時(shí)，也面臨道路擁堵、事故頻發(fā)等問(wèn)題。近年來(lái)，智能交通系統(tǒng)越來(lái)越受到人們的重視，它涉及到交通領(lǐng)域諸多方面，如最優(yōu)路徑選擇、車輛路徑規(guī)劃、動(dòng)態(tài)車輛調(diào)度、交通流量控制等。其中一個(gè)重要的應(yīng)用是一類典型的以數(shù)學(xué)理論為基礎(chǔ)的組合優(yōu)化問(wèn)題，而蟻群算法具有內(nèi)在的搜索機(jī)制及正反饋性，適合求解一系列的組合優(yōu)化問(wèn)題。

1 蟻群算法描述

蟻群算法源于20世紀(jì)90年代初意大利學(xué)者M(jìn).Dorigo首次提出的螞蟻系統(tǒng)。它是基于種群的啟發(fā)式放生進(jìn)化系統(tǒng)，是通過(guò)對(duì)蟻群覓食過(guò)程中其行為的研究而得出的一種算法。主要思路是螞蟻借助自己路徑尋優(yōu)的能力可以找到巢穴與食物之間最短的途徑。在尋找過(guò)程中主要依靠的是每個(gè)螞蟻在行進(jìn)過(guò)程中留下的揮發(fā)性分泌物——信息素，依靠信息素，蟻群的螞蟻之間可以相互合作，相互配合，因此形成的正反饋可以使每只螞蟻找到所有路徑中最短的路徑。

螞蟻a從節(jié)點(diǎn)j移動(dòng)至k的轉(zhuǎn)移概率可以從式（1）中獲取：

（1）

（2）

（3）

2 蟻群算法的應(yīng)用優(yōu)勢(shì)

蟻群算法，又名螞蟻算法，螞蟻可以利用信息素的濃度大小從而尋找到覓食的最優(yōu)路徑。該算法的優(yōu)點(diǎn)可以總結(jié)為：

2.1 并行分布式計(jì)算

每個(gè)螞蟻都是獨(dú)立的個(gè)體，在覓食過(guò)程中屬于多起點(diǎn)同時(shí)啟動(dòng)，互不影響，從根本上分析該過(guò)程屬于分布式的多Agent系統(tǒng)，整體蟻群最終任務(wù)的順利完成不會(huì)由于某些個(gè)體的缺陷而受到影響。該算法具有真實(shí)可用性，并且可用于解決對(duì)單目標(biāo)的優(yōu)化或者對(duì)多目標(biāo)的優(yōu)化等重要問(wèn)題。此外，螞蟻算法還可進(jìn)行并行計(jì)算。

2.2 魯棒性

蟻群算法的最終結(jié)果與螞蟻?zhàn)畛踹x擇的路徑無(wú)太大關(guān)系，在利用人工仿真螞蟻進(jìn)行問(wèn)題求解過(guò)程中，不需要對(duì)其進(jìn)行人工的修整。把問(wèn)題簡(jiǎn)單化，可以和其他算法相互結(jié)合求解最優(yōu)問(wèn)題。

2.3 自組織性

蟻群算法組織指令的來(lái)源為系統(tǒng)內(nèi)部，它不受外界環(huán)境的干擾，因此該算法具有自組織性。

2.4 正反饋性

螞蟻對(duì)于最優(yōu)路徑的選擇主要依靠路徑上信息素濃度的多少，信息素的堆積是正反饋的過(guò)程，路徑上信息素的含量越多則該路徑被選擇的幾率就會(huì)越大，正反饋的作用是使整體能夠更快的尋找到最優(yōu)途徑，正反饋在蟻群算法中處于重要地位。

2.5 易于實(shí)現(xiàn)

它是一種啟發(fā)示算法，其計(jì)算復(fù)雜性為，整個(gè)算法的空間復(fù)雜度是：。

3 蟻群算法在智能交通領(lǐng)域的應(yīng)用空間

蟻群算法在解決組合優(yōu)化問(wèn)題方面有著明顯的優(yōu)勢(shì)，從而在智能交通領(lǐng)域也有著廣泛的應(yīng)用空間。

3.1 車輛路徑導(dǎo)航

根據(jù)行車人員的需要，根據(jù)對(duì)實(shí)時(shí)路況信息的統(tǒng)計(jì)，系統(tǒng)可以智能的為其推薦最優(yōu)路徑，節(jié)省時(shí)間，節(jié)省資源。

3.2 動(dòng)態(tài)車輛調(diào)度

當(dāng)客戶需要調(diào)度中心為其進(jìn)行車輛服務(wù)時(shí)，調(diào)度中心要考慮到客戶的情況，要考慮到效率的問(wèn)題，要考慮到行車路線、行駛時(shí)間等問(wèn)題。蟻群算法便可迅速得到合理的解決方案，使客戶和調(diào)度中心均可受益。

3.3 車輛路徑規(guī)劃

面對(duì)多個(gè)客戶不同的要求時(shí)，配送中心要根據(jù)實(shí)際情況進(jìn)行車輛的配送，通過(guò)蟻群算法系統(tǒng)獲取整體的最優(yōu)路線，根據(jù)路線規(guī)劃，及時(shí)進(jìn)行車輛出發(fā)以滿足客戶要求，同時(shí)充分利用了道路資源和車輛資源。

3.4 公共交通智能化調(diào)度

利用先進(jìn)的技術(shù)手段、大型數(shù)據(jù)庫(kù)技術(shù)等動(dòng)態(tài)地獲取實(shí)時(shí)交通信息，實(shí)現(xiàn)對(duì)車輛的實(shí)時(shí)監(jiān)控和調(diào)度，最終建立集運(yùn)營(yíng)指揮調(diào)度、綜合業(yè)務(wù)通信及信息服務(wù)等為一體的智能化管理系統(tǒng)。

3.5 交通流量控制

通過(guò)蟻群算法簡(jiǎn)化復(fù)雜的道路交通網(wǎng)絡(luò)，盡量使交通流量在各個(gè)道路上分布均勻，避免因流量過(guò)大而造成車輛的阻塞。及時(shí)了解交通流量情況，緩解了交通擁擠，降低了交通事故的發(fā)生率。

參考文獻(xiàn)

[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41

[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999

[3]楊海.蟻群算法及其在智能交通中的應(yīng)用[D].濟(jì)南：山東師范大學(xué)，2008：14-18

作者簡(jiǎn)介

白曉（1979-），女。工學(xué)碩士學(xué)位。現(xiàn)供職于廈門軟件職業(yè)技術(shù)學(xué)院軟件工程系。主要研究方向?yàn)檐浖こ獭⒅悄芩惴ā?/p>

王婭（1983-），女。工學(xué)碩士學(xué)位。現(xiàn)供職于廈門軟件職業(yè)技術(shù)學(xué)院軟件工程系。主要研究方向?yàn)榫W(wǎng)絡(luò)工程，軟件設(shè)計(jì)。

作者單位

廈門軟件職業(yè)技術(shù)學(xué)院軟件工程系 福建省廈門市 361009