04第四章 蟻群算法

上傳人:z**** 文檔編號(hào):109623525 上傳時(shí)間:2022-06-17 格式:DOC 頁數(shù):7 大?。?4KB
收藏 版權(quán)申訴 舉報(bào) 下載
04第四章 蟻群算法_第1頁
第1頁 / 共7頁
04第四章 蟻群算法_第2頁
第2頁 / 共7頁
04第四章 蟻群算法_第3頁
第3頁 / 共7頁

本資源只提供3頁預(yù)覽,全部文檔請(qǐng)下載后查看!喜歡就下載吧,查找使用更方便

15 積分

下載資源

資源描述:

《04第四章 蟻群算法》由會(huì)員分享,可在線閱讀,更多相關(guān)《04第四章 蟻群算法(7頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第四章 蟻群算法 習(xí)題與答案1. 填空題(1) 蟻群算法的縮寫是,它模擬了自然界中過程而提出,可以解決問題。(2) 蟻群算法需要一個(gè)記憶空間,稱為,表示已經(jīng)過的路徑。判斷選擇城市的主要依據(jù)有和,前者代表愿望,后者代表愿望,反映了問題求解過程中經(jīng)驗(yàn)的積累。解釋:本題考查蟻群算法的基礎(chǔ)知識(shí)。具體內(nèi)容請(qǐng)參考課堂視頻“第 4 章蟻群算法”及其課件。答案:(1) ACO,螞蟻覓食,組合優(yōu)化( 2)禁忌列表,能見度,虛擬信息素,啟發(fā)式,獲知式2. 考慮如下情形:分頭沿著兩條長度不同的路徑去食物源,當(dāng)?shù)竭_(dá)食物源時(shí) 哪條路徑會(huì)以較高的概率被其選擇?論證你的答案。解釋:本題考查蟻群算法中信息素的特點(diǎn)與作用。 具

2、體內(nèi)容請(qǐng)參考課堂視頻“第 4 章蟻群算法”及其課件。答案:路徑長度短的會(huì)以較高的概率被選擇。具體論證如下: 單位時(shí)間內(nèi)通過路徑短的螞蟻數(shù)量大于通過路徑長的螞蟻數(shù)量,這意味著短 路徑上遺留的信息素濃度比較髙,由于螞蟻傾向于朝著信息素濃度高的方向移動(dòng) 所以到后期選擇短路徑的螞蟻會(huì)越來越多。于是,蟻群的集體行為表現(xiàn)出一種信 息正反饋現(xiàn)象,即最短路徑上走過的螞蟻越多,信息素濃度也就越高,后來的螞 蟻選擇該路徑的概率就越大,螞蟻個(gè)體之間就是通過這種信息的交流尋找食物和 蟻穴之間最短路徑的。3. 探討在信息素釋放公式中遺忘因子的重要性。解釋:本題考查蟻群算法中信息素?fù)]發(fā)因子的作用。 具體內(nèi)容請(qǐng)參考課堂視頻

3、“第 4 章蟻群算法”及其課件。答案:參數(shù)P表示信息素?fù)]發(fā)因子,P的大小從另一個(gè)側(cè)面反映了螞蟻群體中個(gè)體 間相互影響的強(qiáng)弱,它直接關(guān)系到蟻群算法的全局搜索能力及收斂速度;參數(shù)1-P表示信息素殘留因子,反映了螞蟻個(gè)體之間相互影響的強(qiáng)弱。信息素殘留因 子的大小對(duì)蟻群算法的收斂性能影響非常大,一般取值在0.10.99范圍內(nèi),并 且1-P與進(jìn)化迭代次數(shù)近似成正比。若1-P很大,導(dǎo)致殘留信息素增多,進(jìn)而 信息的正反饋?zhàn)饔迷鰪?qiáng),使路徑上的殘留信息占主導(dǎo)地位,算法容易陷入一個(gè)范 圍窄小的搜索空間,從而使得算法搜索的隨機(jī)性減弱,此時(shí)雖然算法收斂速度加 快,但搜索質(zhì)量不高。若1-P很小,導(dǎo)致殘留信息素較少,進(jìn)而

4、信息的負(fù)反饋?zhàn)?用增強(qiáng),使算法搜索的隨機(jī)性隨之增強(qiáng),此時(shí)雖然有利于搜索到更多潛在的最優(yōu) 解以及提高算法的搜索質(zhì)量,但會(huì)使算法的收斂速度降低。4. 下列關(guān)于蟻群算法說明錯(cuò)誤的是( )。A)信息素的積累是正反饋過程,信息素的揮發(fā)是負(fù)反饋過程。B)TSP 問題中禁忌列表是為了防止同一城市出現(xiàn)多次。C)概率轉(zhuǎn)換規(guī)則中參數(shù)越小,蟻群算法的隨機(jī)性越強(qiáng)。D)概率轉(zhuǎn)換規(guī)則中參數(shù)越大,蟻群算法的隨機(jī)性越強(qiáng)。解釋:本題考查蟻群算法的特點(diǎn)。具體內(nèi)容請(qǐng)參考課堂視頻“第 4 章蟻群算法”及其課件答案:D(1)路徑上信息素的越多,會(huì)吸引越多的螞蟻到該路徑上來,所以信息素 的積累是正反饋過程;反之,信息素的揮發(fā)是負(fù)反饋過程

5、。A選項(xiàng)正確。(2)TSP問題要求螞蟻必須經(jīng)過所有n個(gè)不同的城市,為了避免螞蟻重復(fù) 走入同一個(gè)城市, AS 算法為每只螞蟻配備一個(gè)記憶空間,即在具體算法實(shí)現(xiàn)中 設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu),由這些數(shù)據(jù)結(jié)構(gòu)組成的表(矩陣)稱為禁忌列表。 B 選項(xiàng)正 確。(3)參數(shù)越小,信息素積累的作用越小,螞蟻越偏向于隨機(jī)搜索,所以 蟻群算法的隨機(jī)性越強(qiáng)。 C 選項(xiàng)正確。(4)參數(shù)0越大,能見度作用的確定性越大,蟻群算法的隨機(jī)性越弱。D選 項(xiàng)錯(cuò)誤。5. 請(qǐng)分析TSP問題中禁忌列表的作用。解釋:本題考查蟻群算法中禁忌列表的作用。 具體內(nèi)容請(qǐng)參考課堂視頻“第4章蟻群算法”及其課件。答案:TSP問題要求螞蟻必須經(jīng)過所有n個(gè)不同的

6、城市,為了避免螞蟻重復(fù)走入同 一個(gè)城市, AS 算法為每只螞蟻配備一個(gè)記憶空間,即在具體算法實(shí)現(xiàn)中設(shè)計(jì)一 個(gè)數(shù)據(jù)結(jié)構(gòu),由這些數(shù)據(jù)結(jié)構(gòu)組成的表(矩陣)稱為禁忌列表。該表中的第k行 (或列)用于存儲(chǔ)第k只螞蟻在當(dāng)前時(shí)刻已訪問過的所有城市,記為Jk。每只螞 蟻在選擇城市前,先檢索該表來確定下一步可能選擇的城市是否已經(jīng)走過,如果 走過則不在選擇的范圍內(nèi),這樣可以避免重復(fù)訪問同一個(gè)城市。當(dāng)?shù)趉只螞蟻在 當(dāng)前城市i選擇了下一個(gè)城市j,則在Jk的相應(yīng)位置加入城市j,因此在一個(gè)完 整的行程中,禁忌列表首先是空的,當(dāng)選擇所要經(jīng)過的城市后算法將在線更新禁 忌列表,并在完成 n 個(gè)城市的遍歷形成一條完整路徑后,清空

7、禁忌列表,等待下 一次的迭代。6. 下列關(guān)于禁忌列表的說法錯(cuò)誤的是( )。A)禁忌列表的作用是為了避免重復(fù)訪問同一城市。B)禁忌列表記錄的是螞蟻當(dāng)前訪問過的城市序號(hào)。C)初始禁忌列表是空的。D)遍歷所有城市后,禁忌列表不需要清空。解釋:本題考查蟻群算法中禁忌列表的作用。 具體內(nèi)容請(qǐng)參考課堂視頻“第 4 章蟻群算法”及其課件。答案:D(1)TSP問題要求螞蟻必須經(jīng)過所有n個(gè)不同的城市,為了避免螞蟻重復(fù) 走同一個(gè)城市,需要建立禁忌列表。A選項(xiàng)正確。(2)禁忌列表的第k行(或列)用于存儲(chǔ)第k只螞蟻在當(dāng)前時(shí)刻已訪問過的 所有城市,記為Jk。B選項(xiàng)正確。(3)在一個(gè)完整的行程中,禁忌列表首先是空的。 C

8、 選項(xiàng)正確。(4)當(dāng)選擇所要經(jīng)過的城市后算法將在線更新禁忌列表,并在完成n個(gè)城 市的遍歷形成一條完整路徑后,清空禁忌列表,等待下一次的迭代。D選項(xiàng)錯(cuò)誤。7. 以蟻周模型為例,簡述蟻群算法解決TSP問題的步驟。解釋:本題考查蟻群算法求解TSP問題的過程。具體內(nèi)容請(qǐng)參考課堂視頻“第 4章蟻群算法”及其課件。答案:AS算法求解TSP的具體操作步驟如下。步驟1:初始化,首先設(shè)定相關(guān)參數(shù):所需遍歷城市數(shù)n、螞蟻數(shù)m、初始時(shí)各路徑信息素1 (0)二T、m只螞蟻遍歷(循環(huán))次數(shù)的最大值n 、信息素?fù)]i , j0 max發(fā)系數(shù)P以及a、卩、Q等。建立禁忌列表Jk,并保證此時(shí)表中沒有任何城市。 步驟2:將m只螞

9、蟻隨機(jī)放在各個(gè)城市上,每個(gè)城市至多分布一個(gè)螞蟻,并 將m個(gè)螞蟻所在城市存入禁忌列表Jk。步驟 3:所有螞蟻依據(jù)概率轉(zhuǎn)換規(guī)則選擇下一城市,并將選擇城市存入禁忌 列表。步驟4:所有螞蟻遍歷完n個(gè)城市后在所經(jīng)過的路徑上更新信息素,并記錄 本次迭代過程中的最優(yōu)路徑和最優(yōu)路徑長度。步驟5:清空禁忌列表Jk,重復(fù)步驟3和步驟4直到每一只螞蟻完成n 次max遍歷所有城市,最后輸出的路徑為最優(yōu)路徑。8. 簡述蟻群算法中參數(shù)a和卩的作用。解釋:本題考查蟻群算法參數(shù)a和卩的作用。具體內(nèi)容請(qǐng)參考課堂視頻“第4章蟻群算法”及其課件答案:在下面的概率轉(zhuǎn)換規(guī)則公式中Pk (t)=ij工 It (t)P -Lq Jpil

10、il lJi0如果j電Jk如果j e Jk參數(shù)a表示殘留信息的相對(duì)重要程度,其大小反映了螞蟻在路徑搜索過程中隨機(jī) 性因素作用的強(qiáng)弱;參數(shù)卩表示能見度的相對(duì)重要程度,其大小反映了在路徑搜 索過程中確定性因素作用的強(qiáng)弱。9. 簡述蟻群算法的特點(diǎn)。解釋:本題考查對(duì)蟻群算法特點(diǎn)的總結(jié)。具體內(nèi)容請(qǐng)參考課堂視頻“第 4 章蟻群算法”及其課件。答案:1蟻群算法是一種自組織的優(yōu)化算法。自組織就是在沒有外界作用下使得 系統(tǒng)熵減小的過程(即系統(tǒng)從無序到有序的變化過程),蟻群算法充分體現(xiàn)了這 個(gè)過程。2蟻群算法是一種分布式計(jì)算的優(yōu)化算法。每只螞蟻搜索的過程彼此獨(dú)立, 僅通過信息素進(jìn)行通信。所以蟻群算法可以看作是一個(gè)

11、分布式的多 Agent 系統(tǒng), 它在問題空間的多點(diǎn)同時(shí)開始進(jìn)行獨(dú)立的解搜索,這不僅提高了算法的效率和可 靠性,也使得算法具有較強(qiáng)的全局搜索能力。蟻群算法具有的分布式計(jì)算能力使 其易于并行實(shí)現(xiàn)。3蟻群算法是一種具有正反饋機(jī)制的優(yōu)化算法。對(duì)蟻群算法來說,初始狀 態(tài)時(shí)各個(gè)路徑存在完全相同的信息素,算法采用的反饋方式是較優(yōu)的路徑上留下 更多的信息素,而更多的信息素又吸引了更多的螞蟻選擇這條路徑,這個(gè)正反饋 的過程使得這個(gè)路徑上的信息素不斷增多,引導(dǎo)整個(gè)系統(tǒng)向最優(yōu)解的方向進(jìn)化。 因此,正反饋加快了算法的進(jìn)化過程,最終使算法收斂到最優(yōu)解。4蟻群算法具有較強(qiáng)的魯棒性。相對(duì)于其它算法,蟻群算法對(duì)初始路線要 求不高,即蟻群算法的求解結(jié)果不依賴于初始路線的選擇,而且在搜索過程中不 需要進(jìn)行人工的調(diào)整。其次,蟻群算法的參數(shù)數(shù)目少,設(shè)置簡單,易于蟻群算法 應(yīng)用到其他組合優(yōu)化問題的求解中。

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!