《04第四章 蟻群算法》由會員分享，可在線閱讀，更多相關(guān)《04第四章 蟻群算法（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

3、放公式中遺忘因子的重要性。 解釋： 本題考查蟻群算法中信息素揮發(fā)因子的作用。 具體內(nèi)容請參考課堂視頻“第 4 章蟻群算法”及其課件。 答案： 參數(shù)P表示信息素揮發(fā)因子，P的大小從另一個側(cè)面反映了螞蟻群體中個體 間相互影響的強弱，它直接關(guān)系到蟻群算法的全局搜索能力及收斂速度；參數(shù) 1-P表示信息素殘留因子，反映了螞蟻個體之間相互影響的強弱。信息素殘留因 子的大小對蟻群算法的收斂性能影響非常大，一般取值在0.1?0.99范圍內(nèi)，并 且1-P與進化迭代次數(shù)近似成正比。若1-P很大，導(dǎo)致殘留信息素增多，進而 信息的正反饋作用增強，使路徑上的殘留信息占主導(dǎo)地位，算法容易陷入一個范 圍窄小的搜索

4、空間，從而使得算法搜索的隨機性減弱，此時雖然算法收斂速度加 快，但搜索質(zhì)量不高。若1-P很小，導(dǎo)致殘留信息素較少，進而信息的負反饋作 用增強，使算法搜索的隨機性隨之增強，此時雖然有利于搜索到更多潛在的最優(yōu) 解以及提高算法的搜索質(zhì)量，但會使算法的收斂速度降低。 4. 下列關(guān)于蟻群算法說明錯誤的是（ ）。 A） 信息素的積累是正反饋過程，信息素的揮發(fā)是負反饋過程。 B） TSP 問題中禁忌列表是為了防止同一城市出現(xiàn)多次。 C） 概率轉(zhuǎn)換規(guī)則中參數(shù)?越小，蟻群算法的隨機性越強。 D） 概率轉(zhuǎn)換規(guī)則中參數(shù)越大，蟻群算法的隨機性越強。 解釋： 本題考查蟻群算法的特點。 具體內(nèi)容請參考課堂

5、視頻“第 4 章蟻群算法”及其課件 答案：D （1）路徑上信息素的越多，會吸引越多的螞蟻到該路徑上來，所以信息素 的積累是正反饋過程；反之，信息素的揮發(fā)是負反饋過程。A選項正確。 （2） TSP問題要求螞蟻必須經(jīng)過所有n個不同的城市，為了避免螞蟻重復(fù) 走入同一個城市， AS 算法為每只螞蟻配備一個記憶空間，即在具體算法實現(xiàn)中 設(shè)計一個數(shù)據(jù)結(jié)構(gòu)，由這些數(shù)據(jù)結(jié)構(gòu)組成的表（矩陣）稱為禁忌列表。 B 選項正 確。 （3） 參數(shù)?越小，信息素積累的作用越小，螞蟻越偏向于隨機搜索，所以 蟻群算法的隨機性越強。 C 選項正確。 （4） 參數(shù)0越大，能見度作用的確定性越大，蟻群算法的隨機性越弱。D選

6、 項錯誤。 5. 請分析TSP問題中禁忌列表的作用。 解釋： 本題考查蟻群算法中禁忌列表的作用。 具體內(nèi)容請參考課堂視頻“第4章蟻群算法”及其課件。 答案： TSP問題要求螞蟻必須經(jīng)過所有n個不同的城市，為了避免螞蟻重復(fù)走入同 一個城市， AS 算法為每只螞蟻配備一個記憶空間，即在具體算法實現(xiàn)中設(shè)計一 個數(shù)據(jù)結(jié)構(gòu)，由這些數(shù)據(jù)結(jié)構(gòu)組成的表（矩陣）稱為禁忌列表。該表中的第k行 （或列）用于存儲第k只螞蟻在當(dāng)前時刻已訪問過的所有城市，記為Jk。每只螞 蟻在選擇城市前，先檢索該表來確定下一步可能選擇的城市是否已經(jīng)走過，如果 走過則不在選擇的范圍內(nèi)，這樣可以避免重復(fù)訪問同一個城市。當(dāng)?shù)趉只螞蟻

7、在 當(dāng)前城市i選擇了下一個城市j，則在Jk的相應(yīng)位置加入城市j,因此在一個完 整的行程中，禁忌列表首先是空的，當(dāng)選擇所要經(jīng)過的城市后算法將在線更新禁 忌列表，并在完成 n 個城市的遍歷形成一條完整路徑后，清空禁忌列表，等待下 一次的迭代。 6. 下列關(guān)于禁忌列表的說法錯誤的是（ ）。 A） 禁忌列表的作用是為了避免重復(fù)訪問同一城市。 B） 禁忌列表記錄的是螞蟻當(dāng)前訪問過的城市序號。 C） 初始禁忌列表是空的。 D） 遍歷所有城市后，禁忌列表不需要清空。 解釋： 本題考查蟻群算法中禁忌列表的作用。 具體內(nèi)容請參考課堂視頻“第 4 章蟻群算法”及其課件。 答案：D （1） TSP

8、問題要求螞蟻必須經(jīng)過所有n個不同的城市，為了避免螞蟻重復(fù) 走同一個城市，需要建立禁忌列表。A選項正確。 （2） 禁忌列表的第k行（或列）用于存儲第k只螞蟻在當(dāng)前時刻已訪問過的 所有城市，記為Jk。B選項正確。 （3） 在一個完整的行程中，禁忌列表首先是空的。 C 選項正確。 （4） 當(dāng)選擇所要經(jīng)過的城市后算法將在線更新禁忌列表，并在完成n個城 市的遍歷形成一條完整路徑后,清空禁忌列表，等待下一次的迭代。D選項錯誤。 7. 以蟻周模型為例，簡述蟻群算法解決TSP問題的步驟。 解釋： 本題考查蟻群算法求解TSP問題的過程。 具體內(nèi)容請參考課堂視頻“第 4章蟻群算法”及其課件。 答案

9、： AS算法求解TSP的具體操作步驟如下。步驟1：初始化，首先設(shè)定相關(guān)參數(shù)：所需遍歷城市數(shù)n、螞蟻數(shù)m、初始時 各路徑信息素1 (0)二T、m只螞蟻遍歷(循環(huán))次數(shù)的最大值n 、信息素揮 i , j 0 max 發(fā)系數(shù)P以及a、卩、Q等。建立禁忌列表Jk，并保證此時表中沒有任何城市。 步驟2：將m只螞蟻隨機放在各個城市上，每個城市至多分布一個螞蟻，并 將m個螞蟻所在城市存入禁忌列表Jk。 步驟 3：所有螞蟻依據(jù)概率轉(zhuǎn)換規(guī)則選擇下一城市，并將選擇城市存入禁忌 列表。 步驟4：所有螞蟻遍歷完n個城市后在所經(jīng)過的路徑上更新信息素，并記錄 本次迭代過程中的最優(yōu)路徑和最優(yōu)路徑長度。 步驟5

10、：清空禁忌列表Jk，重復(fù)步驟3和步驟4直到每一只螞蟻完成n 次 max 遍歷所有城市，最后輸出的路徑為最優(yōu)路徑。 8. 簡述蟻群算法中參數(shù)a和卩的作用。 解釋： 本題考查蟻群算法參數(shù)a和卩的作用。 具體內(nèi)容請參考課堂視頻“第4章蟻群算法”及其課件 答案： 在下面的概率轉(zhuǎn)換規(guī)則公式中 Pk (t)= ij 工 It (t)P -Lq Jp il il lJ i 0 如果j電Jk 如果j e Jk 參數(shù)a表示殘留信息的相對重要程度，其大小反映了螞蟻在路徑搜索過程中隨機 性因素作用的強弱；參數(shù)卩表示能見度的相對重要程度，其大小反映了在路徑搜 索過程中確定性因素作

11、用的強弱。 9. 簡述蟻群算法的特點。 解釋： 本題考查對蟻群算法特點的總結(jié)。 具體內(nèi)容請參考課堂視頻“第 4 章蟻群算法”及其課件。 答案： 1．蟻群算法是一種自組織的優(yōu)化算法。自組織就是在沒有外界作用下使得 系統(tǒng)熵減小的過程（即系統(tǒng)從無序到有序的變化過程），蟻群算法充分體現(xiàn)了這 個過程。 2．蟻群算法是一種分布式計算的優(yōu)化算法。每只螞蟻搜索的過程彼此獨立， 僅通過信息素進行通信。所以蟻群算法可以看作是一個分布式的多 Agent 系統(tǒng)， 它在問題空間的多點同時開始進行獨立的解搜索，這不僅提高了算法的效率和可 靠性，也使得算法具有較強的全局搜索能力。蟻群算法具有的分布式計算能力使

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