路徑規(guī)劃畢業(yè)設(shè)計(jì)

1、<p><b>　　1引言</b></p><p>　　1.1 課題研究背景及意義</p><p>　　1.2 主要研究內(nèi)容及關(guān)鍵問題</p><p><b>　　2路徑規(guī)劃概述</b></p><p>　　路徑規(guī)劃是智能交通系統(tǒng)研究的重要內(nèi)容，同時也是車輛定位與導(dǎo)航系統(tǒng)的重要組成部分，智

2、能交通系統(tǒng)是包含若干子系統(tǒng)的復(fù)雜系統(tǒng)，其每個子系統(tǒng)都具有不同的功能，車輛定位與導(dǎo)航系統(tǒng)是智能交通系統(tǒng)的一個主要的應(yīng)用子系統(tǒng)而路徑規(guī)劃是車輛定位與導(dǎo)航系統(tǒng)的重要組成部分。所以可以用下圖來描述三者之間的關(guān)系。</p><p>　　2.1 路徑規(guī)劃的概念</p><p>　　路徑規(guī)劃是車輛定位系統(tǒng)與導(dǎo)航系統(tǒng)的重要組成部分，是它必不可少的核心功能之一。車輛定位與導(dǎo)航系統(tǒng)中的路徑規(guī)劃是在車輛行駛前或

3、行駛過程中為司機(jī)提供從起始點(diǎn)到目標(biāo)點(diǎn)的一條或若干條路線，來對司機(jī)的行車進(jìn)行導(dǎo)航。路徑規(guī)劃可分為單車輛路徑規(guī)劃和多車輛路徑規(guī)劃，單車輛路徑規(guī)劃是在一個特定的道路網(wǎng)上根據(jù)一個車輛的當(dāng)前位置和目標(biāo)給出單個路徑規(guī)劃，屬于用戶優(yōu)化問題；多車輛路徑規(guī)劃是在一個特定的道路網(wǎng)上為所有的車輛規(guī)劃各自的目標(biāo)路徑，屬于系統(tǒng)優(yōu)化問題。</p><p>　　在計(jì)算機(jī)科學(xué)中，通常把求解兩點(diǎn)之間一條路徑的問題和多源最短路徑問題，這些算法可視為

4、單車輛路徑規(guī)劃的問題，多車輛路徑規(guī)劃比單車輛路徑規(guī)劃更復(fù)雜，單用于解決單車輛路徑規(guī)劃問題的背景知識將有利于研究多車輛路徑規(guī)劃的情形。</p><p>　　2.2 路徑規(guī)劃問題的效率</p><p>　　針對一個特定的應(yīng)用，在進(jìn)行路徑規(guī)劃是可以采用多種標(biāo)準(zhǔn)來優(yōu)化路線，這取決于系統(tǒng)的設(shè)計(jì)和用戶的意愿。一條路徑的好壞取決于許多因素，有些司機(jī)可能選擇行駛距離最短的路徑，而有些司機(jī)寧愿行駛距離長些但

5、必須行車條件好一些。這些路徑選擇標(biāo)準(zhǔn)可由設(shè)計(jì)決定，也可由司機(jī)通過一個用戶界面來選定。在選擇最好路徑時，必須具備一個數(shù)字地圖，來挑選使屬性值如時間和距離最小的路徑。</p><p>　　計(jì)算機(jī)中存儲的具有拓補(bǔ)結(jié)構(gòu)的車市路網(wǎng)由節(jié)點(diǎn)、邊及相應(yīng)的拓補(bǔ)關(guān)系構(gòu)成。其中節(jié)點(diǎn)是道路的交叉點(diǎn)、端點(diǎn)，邊是兩節(jié)點(diǎn)間的一段道路，用于表示分段道路，邊的權(quán)值可以定義為道路的距離或距離與其它信息的綜合信息，此時可以將數(shù)字道路地圖轉(zhuǎn)化為帶權(quán)有向

6、圖，因此無論采用何種標(biāo)準(zhǔn)，求解路網(wǎng)中兩點(diǎn)之間的路徑問題就可以歸結(jié)為帶權(quán)有向圖的路徑問題。</p><p>　　在圖論中有許多比較成熟的最短路徑算法可供采用，但在車輛定位與導(dǎo)航系統(tǒng)中，這些算法通常不能直接使用，原因有兩個：一、對于實(shí)時車輛導(dǎo)航系統(tǒng)，路徑規(guī)劃必須在一定的時間內(nèi)完成，這就要求路徑規(guī)劃算法具有較高的運(yùn)算效率；二、對于車輛導(dǎo)航系統(tǒng)，負(fù)責(zé)路徑規(guī)劃的導(dǎo)航計(jì)算機(jī)系統(tǒng)受車載環(huán)境和成本制約，處理能力和存儲資糧十分有限

7、，而在實(shí)際應(yīng)用中的數(shù)字道路數(shù)據(jù)庫往往規(guī)模龐大。因此在車輛定位與導(dǎo)航系統(tǒng)中路徑規(guī)劃的研究目的和任務(wù)是改進(jìn)圖論中的算法或者構(gòu)造新的算法，實(shí)現(xiàn)在盡可能短的時間內(nèi)找到一條理想的路徑。只考慮了路徑規(guī)劃的時效性，可能導(dǎo)致規(guī)劃后的路徑不是最優(yōu)路徑，但卻是比較理想的次優(yōu)路徑，能夠被人們所接受，此時達(dá)到了時效性和最優(yōu)性的平衡。這也是車輛定位與導(dǎo)航系統(tǒng)所要求的。</p><p>　　2.3路徑規(guī)劃的研究現(xiàn)狀</p>&

8、lt;p>　　目前，國內(nèi)外對路徑規(guī)劃方法的研究主要有兩大類，傳統(tǒng)方法與智能方法。傳統(tǒng)方法主要包括：梯度法、柵格法、枚舉法、可視圖法、人工勢場法、自由空間法、A*算法、隨機(jī)搜索法等。其中人工勢場法、梯度法易陷入局部最小點(diǎn)，枚舉法、可視圖法不易用于高維的優(yōu)化問題。用于機(jī)器人路徑規(guī)劃的智能方法主要有：模糊邏輯、神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法、粒子群算法等。</p><p><b>　　3.蟻群算法概述&l

9、t;/b></p><p><b>　　3.1蟻群算法原理</b></p><p>　　在昆蟲世界中，螞蟻是一類群居昆蟲。它們具有高度組織的社會性，不僅可以借助觸覺和視覺的聯(lián)系彼此溝通，而且可以借助于信息素進(jìn)行大規(guī)模的協(xié)調(diào)行動。另外，螞蟻還能夠較快地適應(yīng)環(huán)境的變化，比如：螞蟻在搬運(yùn)食物的過程中，路上突然碰到障礙物時，螞蟻仍能夠很快重新找到到達(dá)蟻穴的最短路徑。螞蟻

10、究竟是如何完成這些復(fù)雜的任務(wù)呢?經(jīng)大量研究發(fā)現(xiàn)，螞蟻在發(fā)現(xiàn)食物后，如果食物較小則獨(dú)自搬運(yùn)，食物比較大時則會請求“外援”，同時，一路上會留下信息素，食物越大信息素的濃度越大，其它螞蟻逐漸向信息素濃的方向靠近，以至足夠多的螞蟻?zhàn)罱K找到食物并將食物搬回蟻穴。如果采用算法實(shí)現(xiàn)完成整個任務(wù)的過程，則遵循如下原則：</p><p>　　(1)活動范圍：螞蟻觀察到的范圍為一個方格形狀，螞蟻有一個速度半徑的參數(shù)(如果是n)，那么

11、它能觀察到的范圍就是n×n個方格世界，并且移動的距離也在此范圍內(nèi)。</p><p>　　(2)周圍環(huán)境：螞蟻所處環(huán)境是虛擬的，包含有障礙物、其它螞蟻以及信息素，信息素又有兩種，找到食物的螞蟻留下的食物信息素和找到蟻穴的螞蟻留下的蟻穴的信息素。每只螞蟻僅能感知其范圍內(nèi)的環(huán)境信息，同時信息素以一定速率在環(huán)境中揮發(fā)。 </p><p>　　(3)覓食規(guī)則：螞蟻在可感知的范圍內(nèi)尋找食物，

12、如果有則直接過去。否則看是否有信息素，并朝信息素濃的方向前進(jìn)，且每只螞蟻大多會以小概率犯錯誤，不一定往信息素最多的位置移動。螞蟻尋蟻穴的規(guī)則和此類似，只是它對蟻穴信息素有反應(yīng)，對食物信息素?zé)o反應(yīng)。 </p><p>　　(4)移動規(guī)則：每只螞蟻都朝信息素最濃的方向移動，當(dāng)周圍設(shè)有信息素誘導(dǎo)時，螞蟻按照自己原先運(yùn)動方向前進(jìn)，并在運(yùn)動的方向會有一個隨機(jī)的小的擾動。盡量避開剛走過的點(diǎn)以防止螞蟻原地轉(zhuǎn)圈。 </p&

13、gt;<p>　　(5)避障規(guī)則：當(dāng)螞蟻在移動的方向被障礙物擋住，它會隨機(jī)的選擇另一個方向，如果有信息素指引，它將遵循覓食的規(guī)則行走。 </p><p>　　(6)撒播信息素規(guī)則：每只螞蟻在剛找到食物或者窩的時候撒發(fā)的信息素最多，隨所走距離增加，撒播的信息素減少。依照以上規(guī)則，盡管螞蟻之間沒有直接關(guān)聯(lián)，但是通過信息素這個紐帶，可以把各只螞蟻協(xié)調(diào)起來。由此產(chǎn)生的成功覓食或找到蟻穴的算法則正是最小化搜索

14、食物的時間或找到蟻穴的最優(yōu)路徑。</p><p>　　3.2蟻群算法的基本思想</p><p>　　一群算法在解決一些組合優(yōu)化問題中取得了較好的效果，因此該算法逐漸引起了許多研究者的注意，并將蟻群算法應(yīng)用到實(shí)際問題中。在蟻群算法中，研究者們提出了人工群蟻的概念。人工蟻群與真實(shí)蟻群有很多相同之處，也有一些人工蟻群特有的本領(lǐng)。一方面，人工蟻群是真實(shí)蟻群行為特征的一種抽象，將真實(shí)蟻群覓食行為中核

15、心的部分抽象給人工蟻群。另一方面，由于人工蟻群是需要解決問題中的復(fù)雜優(yōu)化問題，因此為了能夠使蟻群算法更加有效，人工蟻群還具備了一些真實(shí)蟻群所不具備的特有本領(lǐng)。</p><p>　　3.2.1真實(shí)蟻群與人工蟻群的共同點(diǎn)</p><p>　　人工蟻群大部分的行為特征都是來源于真實(shí)蟻群，他們具有的共同特征主要表現(xiàn)如下：</p><p>　?。?）人工蟻群與真實(shí)蟻群一樣，是

16、一群相互合作的群體。蟻群中的每只螞蟻都能建立一個解，螞蟻個體通過相互的協(xié)作在全局范圍內(nèi)找出問題較優(yōu)的解。</p><p>　?。?）人工蟻群和真實(shí)蟻群共同的任務(wù)是尋找起點(diǎn)（蟻穴）和終點(diǎn)（實(shí)物源）的最短路徑（最優(yōu)目標(biāo)）。</p><p>　?。?）人工蟻群與真實(shí)蟻群通過信息素進(jìn)行間接通訊。在人工蟻群算法中信息素軌跡是通過狀態(tài)變量來表示的。狀態(tài)變量是一個二維信息素矩陣τ來表示。矩陣中的元素τi

17、j表示在節(jié)點(diǎn)i選擇節(jié)點(diǎn)j為移動方向的期望值。初始狀態(tài)矩陣中的各元素設(shè)置初值，隨著螞蟻在所經(jīng)過路徑上釋放信息素的增多，矩陣中的相應(yīng)項(xiàng)的值也隨之改變。人工蟻群算法就是通過修改矩陣中元素的值，來模擬真是蟻群中信息素更新的過程。</p><p>　?。?）人工蟻群還應(yīng)用了真實(shí)蟻群覓食過程中的正反饋機(jī)制，似的使得問題的解向著全局最優(yōu)的方向不斷進(jìn)化，最終能夠有效的獲得相對較優(yōu)的解。</p><p>　

18、?。?）人工蟻群與真實(shí)蟻群都存在著一種信息素?fù)]發(fā)機(jī)制。這種機(jī)制可以使螞蟻忘記過去，不會受過去的經(jīng)驗(yàn)的過分束縛，這有利于指引螞蟻向著新的方向進(jìn)行搜索，避免過早收斂。</p><p>　?。?）人工蟻群與真實(shí)蟻群都是基于概率轉(zhuǎn)移的局部搜索策略。螞蟻在移動時，所應(yīng)用的策略在是時間上和空間上都是完全局部的。</p><p>　　3.2.2人工蟻群的特有功能</p><p>

19、　　從真實(shí)蟻群的行為中獲得的啟發(fā)來設(shè)計(jì)人工蟻群的更能還具備了真實(shí)蟻群不具有的一些特性：</p><p>　?。?）人工蟻群算法存在于一個離散的空間中，它們的移動是一個狀態(tài)到另一個狀態(tài)的轉(zhuǎn)換。</p><p>　　（2）人工蟻群算法具有一個記憶它本身過去行為的內(nèi)在狀態(tài)。</p><p>　?。?）人工蟻群釋放的信息素的量，是由蟻群所建立的問題解決方案優(yōu)劣程度函數(shù)決定的

20、。</p><p>　?。?）蟻群算法更新信息量的時機(jī)是隨不同問題而變化不反應(yīng)真實(shí)蟻群的行為。如：有的問題中蟻群算法在產(chǎn)生一個解后改變信息量，有的問題中則做出一步選擇就更改信息量，但無論哪一種辦法，信息量的更新并不是隨時可以進(jìn)行的。</p><p>　?。?）為了改變系統(tǒng)的性能，蟻群算法中可以增加一些性能，如：前瞻性、局部優(yōu)化、原路返回等。在很多應(yīng)用中蟻群算法可以再局部優(yōu)化過程總交換信息。

21、</p><p>　　3.3 基本蟻群算法的框架</p><p>　　基本蟻群算法的結(jié)構(gòu)流程</p><p>　　3.4 蟻群算法的數(shù)學(xué)模型</p><p>　　將m只螞蟻隨機(jī)放到n個連通的城市上，并使各路徑上信息素的濃度相等。t時刻位于城市i的螞蟻K傾向于選擇那些長度較短并且信息素濃度較高的路徑，并在某一時間更新路徑上的信息素濃度，當(dāng)所有螞

22、蟻都遍歷完n個城市以后，計(jì)算出此次遍歷的最短路徑。此后算法迭代至滿足終止條件后結(jié)束，找到遍歷整個城市的最短路徑。</p><p><b>　　螞蟻K轉(zhuǎn)移原則：</b></p><p>　　訪問未訪問過的城市。</p><p>　　選擇城市j為目標(biāo)城市的概率：</p><p>　　if j∈allowedk</p&g

23、t;<p>　　當(dāng)所有螞蟻完成一次遍歷后，更新路徑上的信息素濃度τ：</p><p><b>　　，其中：</b></p><p>　　3.5采用蟻群算法求解最優(yōu)路徑 </p><p>　　蟻群算法實(shí)質(zhì)上是采用信息正反饋機(jī)制，一旦具有正確 的初始信息素的引導(dǎo)，蟻群就能夠快速地收斂于最優(yōu)解。具體表示如下： </p>&

24、lt;p>　　3.5.1信息素的表示 </p><p>　　“信息素”分布在每兩個相鄰柵格中心的連線上，通往障礙柵格的連線的信息素為0。螞蟻從起始柵格開始搜索，螞蟻的每一步搜索范圍是與其當(dāng)前所在柵格相鄰的上、下、左、右4個柵格上。t時刻每一自由柵格中心i到其相鄰自由柵格中心 的信息素的值為 (t)。 </p><p>　　3.5.2路徑點(diǎn)的選擇 </p><p&g

25、t;　　t時刻螞蟻k擇下一個城市的轉(zhuǎn)移概率由下式確定</p><p>　　if j∈allowedk</p><p>　　3.5.3“信息素”更新機(jī)制 </p><p>　　隨著時間的推移，以前留下的信息素逐漸消逝，用參數(shù)1 一p表示信息素消逝程度，經(jīng)過n個時刻，螞蟻完成一次循環(huán)，信息素濃度根據(jù)式調(diào)整，表示本次循環(huán)中路徑<i，j>上的信息素的增量。其中，

26、Q是常數(shù)， 表示第k只螞蟻在本次循環(huán)中所走過的路徑長度。</p><p>　　3.6 蟻群算法的簡單應(yīng)用—TSP問題求解</p><p>　　用蟻群優(yōu)化算法來解決旅行商問題的過程如下：首先，蟻群從同一地點(diǎn)或不同地點(diǎn)同時出發(fā)，按照按照下面的概率公式逐次訪問各個城市節(jié)點(diǎn) if j∈allowedk</p><p>　　其中禁忌列表Tabu 是保存了每只螞蟻k已經(jīng)訪問過的

27、城市的集合Jk ={N—Tabu }，α、β是系統(tǒng)參數(shù)，分別表示信息素、距離對螞蟻選擇路徑的影響程度；ηij表示由城市i到城市j的期望程度，可根據(jù)某種啟發(fā)算法具體確定，一般為1/d ij ；τ為邊L( )上的信息素強(qiáng)度。當(dāng)蟻群完成了所有的節(jié)點(diǎn)的訪問后，在原路返回的過程中，根據(jù)所得的解的好壞去修改路徑上的信息素強(qiáng)度，以此來引導(dǎo)其他螞蟻對該路徑的選擇，從而達(dá)到群體協(xié)作的目的，最后判斷系統(tǒng)是否滿足停止的條件(停止條件可以是最大的迭代次數(shù)，計(jì)算

28、機(jī)運(yùn)行時間，或者是達(dá)到系統(tǒng)所要達(dá)到的數(shù)據(jù)精度等)，如果條件不滿足，則蟻群又重新開始搜索路徑，建立新的解；否則，系統(tǒng)將退出運(yùn)行，將所得的結(jié)果輸出蟻群優(yōu)化算法的基本思想就是質(zhì)量越好的解和距離越短的路徑就越能吸引更多的螞蟻。蟻群正是通過這種反復(fù)記憶和學(xué)習(xí)的過程，得到了最短路徑，即全局最優(yōu)解。</p><p>　　3.6.1模型中蟻群算法指標(biāo)參數(shù)</p><p>　　模型中有四個重要的參數(shù)：信息啟

29、發(fā)式因子 ：反映了螞蟻在運(yùn)動過程中所累積的信量在指導(dǎo)螞蟻群搜索中的相對重要程度。期望啟發(fā)式因子 ：反映了期望啟發(fā)式信息在 指導(dǎo)蟻群在搜索過程中的相對重要程度。在蟻群算法模型中用參數(shù)P：表示信息素?fù)]發(fā)因子，則1一P就是信息素殘留因子。信息素強(qiáng)度Q：為螞蟻循環(huán)一周時釋放在所經(jīng)路徑上的信息素總量</p><p><b>　　3.6.2環(huán)境建模</b></p><p>　　T

30、SP (Traveling Salesman Problem)旅行商問題是一類典型的NP完全問題，遺傳算法是解決NP問題的一種較理想的方法。</p><p>　　3.6.3 算法的描述</p><p>　　建立的模型從功能上來說，主要包括以下幾點(diǎn)：①地圖上節(jié)點(diǎn)、路徑的顯示功能，②可以隨意添加或刪除節(jié)點(diǎn)，③選定的節(jié)點(diǎn)可以設(shè)置需求量約束，④可以手工調(diào)整相關(guān)參數(shù)，⑤能夠演示路徑變化將計(jì)算結(jié)果清晰

31、表示出來。</p><p>　　3.6.4算法的步驟</p><p><b>　　3．3算法步驟 </b></p><p>　　考慮機(jī)器人路徑規(guī)劃問題，機(jī)器人處于節(jié)點(diǎn)f時，其下一步選擇的節(jié)點(diǎn)必然是其周圍相鄰的8個節(jié)點(diǎn)中的非障礙節(jié)點(diǎn)。算法總體描述如下： </p><p>　　(1)初始化，將m只螞蟻放置在出發(fā)點(diǎn)gbegin

32、,相應(yīng)地，設(shè)置m個禁忌表，記為tabu (K=1，2…．，m)，以記憶螞蟻所走過的節(jié)點(diǎn)。設(shè)置迭代計(jì)數(shù)器n=0，最大代數(shù)為MAX。。 設(shè)定螞蟻的初始感覺刺激閾值A(chǔ)ST=0，高強(qiáng)度信息素閾值為 ，高強(qiáng)度信息素節(jié)點(diǎn)行走步數(shù)P=0。 </p><p>　　(2)找出可行域，對于處于節(jié)點(diǎn)i的螞蟻k，按式(8)找出可行域：alowedi= （8）</p><p>　　(3)節(jié)點(diǎn)選擇，分為兩種情況：①若

33、存在可行域，用式(9)找出螞蟻k在節(jié)點(diǎn)i處可行域內(nèi)能被感覺的節(jié)點(diǎn)集合 (9) </p><p>　　若，按式(10)進(jìn)行節(jié)點(diǎn)選擇(10),若，按式(11)進(jìn)行節(jié)點(diǎn)選擇，式中，g為區(qū)間[0，1)的隨機(jī)數(shù)；q0、q 為區(qū)間[0，1)的常數(shù)。②若螞蟻k無可行域，說明螞蟻進(jìn)入一條死路，此時實(shí)施回退策略，即將螞蟻回退到前一記憶節(jié)點(diǎn)，且標(biāo)記節(jié)點(diǎn)i為障礙格。 </p><p>　　(4)將螞蟻k分配在

34、節(jié)點(diǎn)j上，同時將節(jié)點(diǎn)j加入tabu k，若,P++，并按式(5)進(jìn)行g(shù)感覺適應(yīng)操作，按(6)式作局部信息素更新。若 k<m，k++，返回(2)。否則，轉(zhuǎn)到(5)。 </p><p>　　(5)檢查是否有g(shù) end∈}，若無，令K=1，返回(2)。否則,保存本次路徑為path，并與已保存的歷史最優(yōu)路徑bestpath比較，若path<bestpath，令bestpath=path。 </p>

35、<p>　　(6)按式(7)做全局信息素更新。 </p><p>　　(7)令迭代計(jì)數(shù)器n++，若不等于MAX，清空禁忌表(k=1，2…．m )，重復(fù)上述過程，直到n=MAX為止。bestpath即為最優(yōu)路徑。</p><p>　　3.6.4 基于MATLAB的仿真實(shí)驗(yàn)及結(jié)果分析</p><p>　　3.7蟻群算法的優(yōu)點(diǎn)缺點(diǎn)及其改進(jìn)</p>

36、<p>　　3.7.1蟻群算法的優(yōu)點(diǎn)：</p><p>　?。?）蟻群算法能較好地解決復(fù)雜優(yōu)化問題。蟻群算法是一種結(jié)合了分布式計(jì)算、正反饋機(jī)制和貪婪式搜索的算法。在求解復(fù)雜優(yōu)化問題中，蟻群算法具有很強(qiáng)的搜索較優(yōu)解的能力。正反饋機(jī)制，使得蟻群可以快速的發(fā)現(xiàn)較優(yōu)的解。分布式計(jì)算避免了蟻群算法出現(xiàn)的早熟收斂。而貪婪式搜索有助于在搜索工程中早期就找出可接受的解，提高系統(tǒng)的運(yùn)行效率。</p>&

37、lt;p>　　（2）蟻群算法具有很強(qiáng)的并行性。蟻群算法適用于并行操作，在求解復(fù)雜優(yōu)化問題時，不僅可以從算法自身的改進(jìn)出發(fā)來提高求解效率，也可以從算法的執(zhí)行模式出發(fā)來進(jìn)行優(yōu)化。</p><p>　?。?）蟻群算法具有很好的可擴(kuò)充性。因?yàn)橄伻核惴梢圆煌ㄟ^螞蟻個體之間直接通信，而是通過信息素進(jìn)行間接通信，所以蟻群算法就具有很好的可擴(kuò)充性。</p><p>　?。?）蟻群算法具有較強(qiáng)的魯棒

38、性。蟻群算法模型稍加改進(jìn)，就可以應(yīng)用于其他問題中。在研究蟻群算法的過程中，許多研究者都通過了求解TSP問題來研究蟻群算法。</p><p>　　（5）蟻群算法還具有易于與其他方法融合的特性。如可以將蟻群算法與遺傳算法和模擬退火算法相結(jié)合。而且這種融合可以改善算法的性能，是蟻群算法優(yōu)化方法中的一種。</p><p>　　3.7.2蟻群算法的缺點(diǎn)：</p><p>　　

39、（1）對于大規(guī)模復(fù)雜優(yōu)化問題，蟻群算法需要較長的搜索時間。蟻群中螞蟻個體的運(yùn)動時隨機(jī)的，雖然通過信息素的間接協(xié)調(diào)，能夠讓蟻群向較優(yōu)的路徑，但是當(dāng)問題規(guī)模很大時，蟻群很難在較短時間內(nèi)從大量雜亂無章的路徑中找出一條較好的路徑。這主要是因?yàn)樵谙伻核阉髟缙诟鱾€路徑上的信息素濃度明顯高于其他路徑上的信息素濃度。所以對于大規(guī)模復(fù)雜優(yōu)化問題，算法的收斂需要較長時間。</p><p>　　（2）蟻群容易出現(xiàn)停滯現(xiàn)象，出現(xiàn)早熟收斂

40、。也就是當(dāng)搜索進(jìn)行到一定時間后，所有螞蟻個體所發(fā)現(xiàn)的解完全一致，不能進(jìn)一步對解進(jìn)行搜索，所以不利于發(fā)現(xiàn)更好的解。因此很多研究者對蟻群算法進(jìn)行改進(jìn)，以期望避免算法早熟收斂，以搜索更優(yōu)的解。</p><p>　?。?）蟻群算法還沒有嚴(yán)格的數(shù)學(xué)解釋。目前還未能提出一種完善的理論分析，對蟻群算法的有效性進(jìn)行論證。蟻群算法作為一種模擬進(jìn)化算法，其研究也才剛剛開始，有很多問題有待進(jìn)一步的研究，如算法的收斂性和理論依據(jù)等。&l

41、t;/p><p>　　3.7.3.改進(jìn)的蟻群算法及其應(yīng)用 </p><p>　　針對蟻群算法的不足，大批學(xué)者圍繞如何改進(jìn)蟻群算法，提高算法的性能做了大量工作。其中應(yīng)用廣泛且具有代表性的改進(jìn)蟻群算法主要有： </p><p>　　帶精英策略的螞蟻系統(tǒng)（ASelite)。它是最早的改進(jìn)螞蟻系統(tǒng)。因?yàn)樵谀承┓矫嫠愃朴谶z傳算法中的帶精英策略，因此把它稱作帶精英策略的螞蟻系統(tǒng)。

42、</p><p>　　基于排序的螞蟻系統(tǒng)。它是將遺傳算法中排序的概念擴(kuò)展應(yīng)用到螞蟻系統(tǒng)中得到的?；舅枷胧牵合仁歉鶕?jù)適應(yīng)度對種群進(jìn)行分 類，然后被選擇的概率取決于個體的排序。適應(yīng)度越高，個體在種群中 的排名越靠前，被選擇概率越大。 </p><p>　　(3)蟻群系統(tǒng)(ACs)，它是As算法的改進(jìn)型版本，它與As算法的主 要區(qū)別是：在選擇下一座城市時，ACS算法更多地利用當(dāng)前的較好解；當(dāng)

43、螞蟻從城市m爬行到城市n時，m城市邊上的信息素將會適當(dāng)?shù)臏p少。 但Acs算法的缺點(diǎn)是搜索效率低、質(zhì)量差。 </p><p>　　(4)最大一最小螞蟻系統(tǒng)(MMAs) 。它是通過對AS算法改進(jìn)后得到的，是目前求解1、sP和QAP等問題最好的蟻群算法模型。與其他尋優(yōu)算法相比，仍然屬于最好的方法之一。 </p><p>　　(5)最優(yōu)一最差螞蟻系統(tǒng)。該算法的思想是對最優(yōu)解增強(qiáng)，對最差 解削弱，使

44、屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間信息素濃度差 異增大，從而使螞蟻集中于最優(yōu)解的附近進(jìn)行搜索活動。</p><p>　　4基于蟻群算法的路徑規(guī)劃</p><p><b>　　4.1環(huán)境建模</b></p><p><b>　　4.2算法的描述</b></p><p><b>　　4.3

45、算法的步驟</b></p><p>　　5仿真實(shí)驗(yàn)與結(jié)果分析</p><p><b>　　5.1仿真實(shí)驗(yàn)</b></p><p><b>　　5.2 結(jié)果分析</b></p><p><b>　　6 結(jié)束語</b></p><p><b

46、>　　參考文獻(xiàn)</b></p><p><b>　　致謝</b></p><p>　　附錄A 基于蟻群算法路徑規(guī)劃</p><p><b>　　Matlab程序</b></p><p>　　function [ROUTES,PL,Tau]=ACASP(G,Tau,K,M,S,E,A

47、lpha,Beta,Rho,Q)</p><p>　　% 蟻群算法動態(tài)尋路算法</p><p><b>　　% 輸入?yún)?shù)列表</b></p><p>　　% G 地形圖為01矩陣，如果為1表示障礙物</p><p>　　% Tau 初始信息素矩陣（認(rèn)為前面的覓食活動中有殘留的信息素）<

48、;/p><p>　　% K 迭代次數(shù)（指螞蟻出動多少波）</p><p>　　% M 螞蟻個數(shù)（每一波螞蟻有多少個）</p><p>　　% S 起始點(diǎn)（最短路徑的起始點(diǎn)）</p><p>　　% E 終止點(diǎn)（最短路徑的目的點(diǎn)）</p><p>　　% Al

49、pha 表征信息素重要程度的參數(shù)</p><p>　　% Beta 表征啟發(fā)式因子重要程度的參數(shù)</p><p>　　% Rho 信息素蒸發(fā)系數(shù)</p><p>　　% Q 信息素增加強(qiáng)度系數(shù)</p><p><b>　　%</b></p><p>&l

50、t;b>　　% 輸出參數(shù)列表</b></p><p>　　% ROUTES 每一代的每一只螞蟻的爬行路線</p><p>　　% PL 每一代的每一只螞蟻的爬行路線長度</p><p>　　% Tau 輸出動態(tài)修正過的信息素</p><p>　　%% --------------------變

51、量初始化----------------------------------</p><p><b>　　%load</b></p><p><b>　　D=G2D(G);</b></p><p>　　N=size(D,1);%N表示問題的規(guī)模（象素個數(shù)）</p><p>　　MM=size(G,1

52、);</p><p>　　a=1;%小方格象素的邊長</p><p>　　Ex=a*(mod(E,MM)-0.5);%終止點(diǎn)橫坐標(biāo)</p><p>　　if Ex==-0.5</p><p>　　Ex=MM-0.5;</p><p><b>　　end</b></p><p&g

53、t;　　Ey=a*(MM+0.5-ceil(E/MM));%終止點(diǎn)縱坐標(biāo)</p><p>　　Eta=zeros(1,N);%啟發(fā)式信息，取為至目標(biāo)點(diǎn)的直線距離的倒數(shù)</p><p>　　%下面構(gòu)造啟發(fā)式信息矩陣</p><p><b>　　for i=1:N</b></p><p>　　if ix==-0.5</

54、p><p>　　ix=MM-0.5;</p><p><b>　　end</b></p><p>　　iy=a*(MM+0.5-ceil(i/MM)); </p><p><b>　　if i~=E</b></p><p>　　Eta(1,i)=1/((ix-Ex)^2+(i

55、y-Ey)^2)^0.5;</p><p><b>　　else</b></p><p>　　Eta(1,i)=100;</p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　ROUTES=cell(

56、K,M);%用細(xì)胞結(jié)構(gòu)存儲每一代的每一只螞蟻的爬行路線</p><p>　　PL=zeros(K,M);%用矩陣存儲每一代的每一只螞蟻的爬行路線長度</p><p>　　%% -----------啟動K輪螞蟻覓食活動，每輪派出M只螞蟻--------------------</p><p><b>　　for k=1:K</b></p&

57、gt;<p><b>　　disp(k);</b></p><p><b>　　for m=1:M</b></p><p>　　%% 第一步：狀態(tài)初始化</p><p>　　W=S;%當(dāng)前節(jié)點(diǎn)初始化為起始點(diǎn)</p><p>　　Path=S;%爬行路線初始化</p>

58、<p>　　PLkm=0;%爬行路線長度初始化</p><p>　　TABUkm=ones(1,N);%禁忌表初始化</p><p>　　TABUkm(S)=0;%已經(jīng)在初始點(diǎn)了，因此要排除</p><p>　　DD=D;%鄰接矩陣初始化</p><p>　　%% 第二步：下一步可以前往的節(jié)點(diǎn)</p>&l

59、t;p>　　DW=DD(W,:);</p><p>　　DW1=find(DW</p><p>　　for j=1:length(DW1)</p><p>　　if TABUkm(DW1(j))==0</p><p>　　DW(j)=inf;</p><p><b>　　end</b><

60、;/p><p><b>　　end</b></p><p>　　LJD=find(DW)</p><p>　　Len_LJD=length(LJD);%可選節(jié)點(diǎn)的個數(shù)</p><p>　　%% 覓食停止條件：螞蟻未遇到食物或者陷入死胡同</p><p>　　while W~=E&&am

61、p;Len_LJD>=1</p><p>　　%% 第三步：轉(zhuǎn)輪賭法選擇下一步怎么走</p><p>　　PP=zeros(1,Len_LJD);</p><p>　　for i=1:Len_LJD</p><p>　　PP(i)=(Tau(W,LJD(i))^Alpha)*(Eta(LJD(i))^Beta);<

62、/p><p><b>　　end</b></p><p>　　PP=PP/(sum(PP));%建立概率分布</p><p>　　Pcum=cumsum(PP);</p><p>　　Select=find(Pcum>=rand);</p><p>　　%% 第四步：狀態(tài)更新和記

63、錄</p><p>　　Path=[Path,to_visit];%路徑增加</p><p>　　PLkm=PLkm+DD(W,to_visit);%路徑長度增加</p><p>　　W=to_visit;%螞蟻移到下一個節(jié)點(diǎn)</p><p>　　for kk=1:N</p><p>　　if TABUkm(kk)==

64、0</p><p>　　DD(W,kk)=inf;</p><p>　　DD(kk,W)=inf;</p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　TABUkm(W)=0;%已訪問過的節(jié)點(diǎn)從禁忌表中刪除</p&

65、gt;<p>　　for j=1:length(DW1)</p><p>　　if TABUkm(DW1(j))==0</p><p>　　DW(j)=inf;</p><p><b>　　end</b></p><p><b>　　end</b></p><p&g

66、t;　　LJD=find(DW</p><p>　　Len_LJD=length(LJD);%可選節(jié)點(diǎn)的個數(shù)</p><p><b>　　end</b></p><p>　　%% 第五步：記下每一代每一只螞蟻的覓食路線和路線長度</p><p>　　ROUTES{k,m}=Path;</p><

67、;p>　　if Path(end)==E</p><p>　　PL(k,m)=PLkm;</p><p><b>　　else</b></p><p>　　PL(k,m)=inf;</p><p><b>　　end</b></p><p><b>　　end

68、</b></p><p>　　%% 第六步：更新信息素</p><p>　　Delta_Tau=zeros(N,N);%更新量初始化</p><p><b>　　for m=1:M</b></p><p>　　if PL(k,m) ROUT=ROUTES{k,m};</p>

69、<p>　　TS=length(ROUT)-1;%跳數(shù)</p><p>　　PL_km=PL(k,m);</p><p>　　for s=1:TS</p><p>　　x=ROUT(s);</p><p>　　Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;</p><p>　　

70、Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;</p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　Tau=(1-Rho).*Tau+Delta_T

71、au;%信息素?fù)]發(fā)一部分，新增加一部分</p><p><b>　　end</b></p><p>　　%% ---------------------------繪圖--------------------------------</p><p>　　plotif=1;%是否繪圖的控制參數(shù)</p><p>　　if p

72、lotif==1</p><p><b>　　%繪收斂曲線</b></p><p>　　meanPL=zeros(1,K);</p><p>　　minPL=zeros(1,K);</p><p><b>　　for i=1:K</b></p><p>　　PLK=PL(i,

73、:);</p><p>　　Nonzero=find(PLK</p><p>　　PLKPLK=PLK(Nonzero);</p><p>　　meanPL(i)=mean(PLKPLK);</p><p>　　minPL(i)=min(PLKPLK);</p><p><b>　　end</b>

74、</p><p><b>　　figure(1)</b></p><p>　　plot(minPL);</p><p><b>　　hold on</b></p><p>　　plot(meanPL);</p><p><b>　　grid on</b>

75、</p><p>　　title('收斂曲線（平均路徑長度和最小路徑長度）');</p><p>　　xlabel('迭代次數(shù)');</p><p>　　ylabel('路徑長度');</p><p><b>　　%繪爬行圖</b></p><p>

76、<b>　　figure(2)</b></p><p>　　axis([0,MM,0,MM])</p><p>　　for i=1:MM</p><p>　　for j=1:MM</p><p>　　if G(i,j)==1</p><p>　　x1=j-1;y1=MM-i;</p>

77、<p>　　x2=j;y2=MM-i;</p><p>　　x3=j;y3=MM-i+1;</p><p>　　x4=j-1;y4=MM-i+1;</p><p>　　fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);</p><p><b>　　hold on</b&

78、gt;</p><p><b>　　else</b></p><p>　　x1=j-1;y1=MM-i;</p><p>　　x2=j;y2=MM-i;</p><p>　　x3=j;y3=MM-i+1;</p><p>　　x4=j-1;y4=MM-i+1;</p><p&g

79、t;　　fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);</p><p><b>　　hold on</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　end

80、</b></p><p><b>　　hold on</b></p><p>　　ROUT=ROUTES{K,M};</p><p>　　LENROUT=length(ROUT);</p><p><b>　　Rx=ROUT;</b></p><p><b&

81、gt;　　Ry=ROUT;</b></p><p>　　for ii=1:LENROUT</p><p>　　Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);</p><p>　　if Rx(ii)==-0.5</p><p>　　Rx(ii)=MM-0.5;</p><p><b&g

82、t;　　end</b></p><p>　　Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM));</p><p><b>　　end</b></p><p>　　plot(Rx,Ry)</p><p><b>　　end</b></p><p>

83、;　　plotif2=1;%繪各代螞蟻爬行圖</p><p>　　if plotif2==1</p><p><b>　　figure(3)</b></p><p>　　axis([0,MM,0,MM])</p><p>　　for i=1:MM</p><p>　　for j=1:MM</

84、p><p>　　if G(i,j)==1</p><p>　　x1=j-1;y1=MM-i;</p><p>　　x2=j;y2=MM-i;</p><p>　　x3=j;y3=MM-i+1;</p><p>　　x4=j-1;y4=MM-i+1;</p><p>　　fill([x1,x2,x3,

85、x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);</p><p><b>　　hold on</b></p><p><b>　　else</b></p><p>　　x1=j-1;y1=MM-i;</p><p>　　x2=j;y2=MM-i;</p><p&

86、gt;　　x3=j;y3=MM-i+1;</p><p>　　x4=j-1;y4=MM-i+1;</p><p>　　fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);</p><p><b>　　hold on</b></p><p><b>　　end</b>&

87、lt;/p><p><b>　　end</b></p><p><b>　　end</b></p><p><b>　　for k=1:K</b></p><p>　　PLK=PL(k,:);</p><p>　　minPLK=min(PLK);</p

88、><p>　　pos=find(PLK==minPLK);</p><p><b>　　m=pos(1);</b></p><p>　　ROUT=ROUTES{k,m};</p><p>　　LENROUT=length(ROUT);</p><p><b>　　Rx=ROUT;</b

89、></p><p><b>　　Ry=ROUT;</b></p><p>　　for ii=1:LENROUT</p><p>　　Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);</p><p>　　if Rx(ii)==-0.5</p><p>　　Rx(ii)=MM-0

90、.5;</p><p><b>　　end</b></p><p>　　Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM));</p><p><b>　　end</b></p><p>　　plot(Rx,Ry)</p><p><b>　　ho