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

白曉++王婭

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

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

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

1 蟻群算法描述

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

螞蟻a從節(jié)點j移動至k的轉(zhuǎn)移概率可以從式（1）中獲?。?/p>

（1）

（2）

（3）

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

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

2.1 并行分布式計算

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

2.2 魯棒性

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

2.3 自組織性

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

2.4 正反饋性

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

2.5 易于實現(xiàn)

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

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

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

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

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

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

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

3.3 車輛路徑規(guī)劃

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

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

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

3.5 交通流量控制

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

參考文獻

[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].濟南：山東師范大學(xué)，2008：14-18

作者簡介

白曉（1979-），女。工學(xué)碩士學(xué)位。現(xiàn)供職于廈門軟件職業(yè)技術(shù)學(xué)院軟件工程系。主要研究方向為軟件工程、智能算法。

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

作者單位

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