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

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

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

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

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

5、必須行車(chē)條件好一些。這些路徑選擇標(biāo)準(zhǔn)可由設(shè)計(jì)決定，也可由司機(jī)通過(guò)一個(gè)用戶(hù)界面來(lái)選定。在選擇最好路徑時(shí)，必須具備一個(gè)數(shù)字地圖，來(lái)挑選使屬性值如時(shí)間和距離最小的路徑。</p><p>　　計(jì)算機(jī)中存儲(chǔ)的具有拓補(bǔ)結(jié)構(gòu)的車(chē)市路網(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í)可以將數(shù)字道路地圖轉(zhuǎn)化為帶權(quán)有向

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

22、蟻都遍歷完n個(gè)城市以后，計(jì)算出此次遍歷的最短路徑。此后算法迭代至滿(mǎn)足終止條件后結(jié)束，找到遍歷整個(gè)城市的最短路徑。</p><p><b>　　螞蟻K轉(zhuǎn)移原則：</b></p><p>　　訪問(wèn)未訪問(wèn)過(guò)的城市。</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>　　“信息素”分布在每?jī)蓚€(gè)相鄰柵格中心的連線上，通往障礙柵格的連線的信息素為0。螞蟻從起始柵格開(kāi)始搜索，螞蟻的每一步搜索范圍是與其當(dāng)前所在柵格相鄰的上、下、左、右4個(gè)柵格上。t時(shí)刻每一自由柵格中心i到其相鄰自由柵格中心 的信息素的值為 (t)。 </p><p>　　3.5.2路徑點(diǎn)的選擇 </p><p&g

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

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

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

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

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

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

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

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

33、存在可行域，用式(9)找出螞蟻k在節(jié)點(diǎn)i處可行域內(nèi)能被感覺(jué)的節(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無(wú)可行域，說(shuō)明螞蟻進(jìn)入一條死路，此時(shí)實(shí)施回退策略，即將螞蟻回退到前一記憶節(jié)點(diǎn)，且標(biāo)記節(jié)點(diǎn)i為障礙格。 </p><p>　　(4)將螞蟻k分配在

34、節(jié)點(diǎn)j上，同時(shí)將節(jié)點(diǎn)j加入tabu k，若,P++，并按式(5)進(jìn)行g(shù)感覺(jué)適應(yīng)操作，按(6)式作局部信息素更新。若 k<m，k++，返回(2)。否則，轉(zhuǎn)到(5)。 </p><p>　　(5)檢查是否有g(shù) end∈}，若無(wú)，令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ù)上述過(guò)程，直到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)化問(wèn)題。蟻群算法是一種結(jié)合了分布式計(jì)算、正反饋機(jī)制和貪婪式搜索的算法。在求解復(fù)雜優(yōu)化問(wèn)題中，蟻群算法具有很強(qiáng)的搜索較優(yōu)解的能力。正反饋機(jī)制，使得蟻群可以快速的發(fā)現(xiàn)較優(yōu)的解。分布式計(jì)算避免了蟻群算法出現(xiàn)的早熟收斂。而貪婪式搜索有助于在搜索工程中早期就找出可接受的解，提高系統(tǒng)的運(yùn)行效率。</p>&

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

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

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

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

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

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

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

44、屬于最優(yōu)路徑的邊與屬于最差路徑的邊之間信息素濃度差 異增大，從而使螞蟻集中于最優(yōu)解的附近進(jìn)行搜索活動(dòng)。</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é)束語(yǔ)</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>　　% 蟻群算法動(dòng)態(tài)尋路算法</p><p><b>　　% 輸入?yún)?shù)列表</b></p><p>　　% G 地形圖為01矩陣，如果為1表示障礙物</p><p>　　% Tau 初始信息素矩陣（認(rèn)為前面的覓食活動(dòng)中有殘留的信息素）<

48、;/p><p>　　% K 迭代次數(shù)（指螞蟻出動(dòng)多少波）</p><p>　　% M 螞蟻個(gè)數(shù)（每一波螞蟻有多少個(gè)）</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 每一代的每一只螞蟻的爬行路線長(zhǎng)度</p><p>　　% Tau 輸出動(dòng)態(tài)修正過(guò)的信息素</p><p>　　%% --------------------變

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

52、);</p><p>　　a=1;%小方格象素的邊長(zhǎng)</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)存儲(chǔ)每一代的每一只螞蟻的爬行路線</p><p>　　PL=zeros(K,M);%用矩陣存儲(chǔ)每一代的每一只螞蟻的爬行路線長(zhǎng)度</p><p>　　%% -----------啟動(dòng)K輪螞蟻覓食活動(dòng)，每輪派出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;%爬行路線長(zhǎng)度初始化</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)的個(gè)數(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);%路徑長(zhǎng)度增加</p><p>　　W=to_visit;%螞蟻移到下一個(gè)節(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;%已訪問(wèn)過(guò)的節(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)的個(gè)數(shù)</p><p><b>　　end</b></p><p>　　%% 第五步：記下每一代每一只螞蟻的覓食路線和路線長(zhǎng)度</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('收斂曲線（平均路徑長(zhǎng)度和最小路徑長(zhǎng)度）');</p><p>　　xlabel('迭代次數(shù)');</p><p>　　ylabel('路徑長(zhǎng)度');</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