蟻群算法及其在智能交通中的應(yīng)用.pdf

1、隨著經(jīng)濟(jì)的快速發(fā)展和汽車數(shù)量的不斷增加，日益嚴(yán)重的交通問題已經(jīng)成為束縛各國城市發(fā)展的瓶頸，我國的情況尤為嚴(yán)重。智能交通系統(tǒng)(Intelligent Transportation System，ITS)是解決現(xiàn)代社會(huì)交通需求與供給之間矛盾的重要途徑之一，是解決交通基礎(chǔ)設(shè)施建設(shè)增長緩慢與機(jī)動(dòng)車數(shù)量迅速增長之間矛盾的最佳手段。近幾年來，智能交通系統(tǒng)越來越受到人們的重視，它是以當(dāng)代飛速發(fā)展的科學(xué)技術(shù)為支撐，將先進(jìn)的計(jì)算機(jī)技術(shù)、通信技術(shù)、數(shù)據(jù)庫技

2、術(shù)、人工智能技術(shù)等運(yùn)用于交通運(yùn)輸中，以達(dá)到緩解交通擁擠、保證交通安全、提高交通網(wǎng)絡(luò)使用效率等目的。智能交通系統(tǒng)涉及到交通領(lǐng)域的許多方面,最優(yōu)路徑的選擇就是其重要應(yīng)用之一，是一類典型的組合優(yōu)化問題，適合采用蟻群算法(ACA)求解。 組合優(yōu)化技術(shù)是一種以數(shù)學(xué)理論為基礎(chǔ)，用于求解各種工程問題優(yōu)化解的應(yīng)用技術(shù)。隨著計(jì)算機(jī)技術(shù)的發(fā)展，以蟻群算法為代表的智能啟發(fā)算法得到了迅速發(fā)展和廣泛應(yīng)用。蟻群算法是模仿自然界的螞蟻行為而發(fā)展起來的一種隨機(jī)

3、搜索算法。由于以信息素作為間接通信方式，使蟻群算法具有其他常規(guī)優(yōu)化算法無法獲得的優(yōu)點(diǎn)。算法采用了正反饋并行自適應(yīng)機(jī)制，良好的分布式計(jì)算機(jī)制，具有較強(qiáng)的魯棒性，易于與其他啟發(fā)式算法相結(jié)合。 蟻群算法通過其內(nèi)在的搜索機(jī)制和TF反饋特性，在一系列困難的組合優(yōu)化阿題中取得了成效，這已經(jīng)是被大量研究成果證明了的。但是蟻群算法也存在著一些缺陷。在螞蟻的移動(dòng)過程中，路徑選擇雖然受到信息素和啟發(fā)信息的指導(dǎo)，但仍具有隨機(jī)性，特別是當(dāng)問題規(guī)模較大時(shí)

4、，路徑的選擇通常需要較長的搜索時(shí)間。此外，由于個(gè)別路徑上的信息素可能被過于強(qiáng)化，容易使算法陷入局部最優(yōu)解。 目前我國對(duì)智能交通系統(tǒng)的研究水平還比較低，而蟻群算法也是一種比較新的仿生算法。因此，需要對(duì)蟻群算法進(jìn)行改進(jìn)和完善，使其更廣泛地應(yīng)用于智能交通系統(tǒng)。 論文的主要研究內(nèi)容及創(chuàng)新點(diǎn)如下： (1)回顧了國內(nèi)外智能交通系統(tǒng)的研究與發(fā)展?fàn)顩r，詳細(xì)介紹了我國智能交通系統(tǒng)的構(gòu)成和重要作用。 (2)系統(tǒng)闡述了蟻群算法

5、的理論基礎(chǔ)、算法模型和實(shí)現(xiàn)步驟。通過對(duì)算法的分析，得出算法的時(shí)間復(fù)雜度為O(Nc·n2·m)，空間復(fù)雜度為O(n2)+O(n·m)。此外還分析了影響算法性能的各種因素，特別是參數(shù)a、β、p，并通過仿真實(shí)驗(yàn)加以說明。最后總結(jié)了蟻群算法的特點(diǎn)和研究應(yīng)用現(xiàn)狀。 (3)本文從以下四個(gè)方面對(duì)基本蟻群算法進(jìn)行了改進(jìn)：信息素更新策略、參數(shù)β、參數(shù)p和引入探索因子gn。仿真實(shí)驗(yàn)表明，算法的性能得到了提高。 (4)將遺傳算法融入蟻群算法，

6、提出了基于獎(jiǎng)懲機(jī)制的遺傳蟻群算法(RP-GA-ACA)。詳細(xì)介紹了該算法的主要思想、算法模型、實(shí)現(xiàn)步驟和時(shí)間復(fù)雜度。仿真實(shí)驗(yàn)表明，RP-GA-ACA算法在時(shí)間效率上優(yōu)于蟻群算法，在求精效率上優(yōu)于遺傳算法。 (5)對(duì)交通道路網(wǎng)進(jìn)行了較深入的研究，提出了交通道路網(wǎng)的表示方法和權(quán)重的確定方法. (6)將改進(jìn)的蟻群算法應(yīng)用到車輛路徑問題(VRP)，提出了求解VRP問題的改進(jìn)蟻群算法(VRP-ACA)。詳細(xì)闡述了該算法的主要思想、