04第四章 蟻群算法

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. 考慮如下情形：分頭沿著兩條長(zhǎng)度不同的路徑去食物源，當(dāng)?shù)竭_(dá)食物源時(shí) 哪條路徑會(huì)以較高的概率被其選擇？論證你的答案。解釋：本題考查蟻群算法中信息素的特點(diǎn)與作用。具體內(nèi)

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

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

4、用增強(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ù)反饋過程。A 選

5、項(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ù) 項(xiàng)錯(cuò)誤。越大，能見度作用的確定性越大，蟻群算法的隨機(jī)性越弱。D 選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í)刻已訪問過的所有城市，記為 J k 。每只螞蟻在選擇城市前，先檢索該表來確定下一步可能選擇的城市是否已經(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í)刻已訪問過的 所有城市，記為 J k 。B 選項(xiàng)正確。（3）在一個(gè)完整的行程

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

9、ax發(fā)系數(shù) 以及 、Q 等。建立禁忌列表 J k ，并保證此時(shí)表中沒有任何城市。 步驟 2：將 m 只螞蟻隨機(jī)放在各個(gè)城市上，每個(gè)城市至多分布一個(gè)螞蟻，并將 m 個(gè)螞蟻所在城市存入禁忌列表 Jk。步驟 3：所有螞蟻依據(jù)概率轉(zhuǎn)換規(guī)則選擇下一城市，并將選擇城市存入禁忌 列表。步驟 4：所有螞蟻遍歷完 n 個(gè)城市后在所經(jīng)過的路徑上更新信息素，并記錄 本次迭代過程中的最優(yōu)路徑和最優(yōu)路徑長(zhǎng)度。步驟 5：清空禁忌列表 Jk，重復(fù)步驟 3 和步驟 4直到每一只螞蟻完成N次max遍歷所有城市，最后輸出的路徑為最優(yōu)路徑。8. 簡(jiǎn)述蟻群算法中參數(shù) 和 的作用。解釋：本題考查蟻群算法參數(shù) 和 的作用。具體內(nèi)容請(qǐng)參考

10、課堂視頻“第 4 章蟻群算法”及其課件。答案：在下面的概率轉(zhuǎn)換規(guī)則公式中，pkij ij (t)il illJ0如果 j J k如果 j J k參數(shù) 表示殘留信息的相對(duì)重要程度，其大小反映了螞蟻在路徑搜索過程中隨機(jī)性因素作用的強(qiáng)弱；參數(shù) 表示能見度的相對(duì)重要程度，其大小反映了在路徑搜 索過程中確定性因素作用的強(qiáng)弱。9. 簡(jiǎn)述蟻群算法的特點(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è)分布式的多 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è)路徑上的信息素不