04第四章 蚁群算法

1、第四章 蚁群算法 习题与答案1. 填空题（1）蚁群算法的缩写是 ，它模拟了自然界中过程而提出，可以解决问题。（2）蚁群算法需要一个记忆空间，称为 ，表示已经过的路径。判断选择城市的主要依据有和 ，前者代表愿望，后者代表解释：愿望，反映了问题求解过程中经验的积累。本题考查蚁群算法的基础知识。具体内容请参考课堂视频“第 4 章蚁群算法”及其课件。答案：（1）ACO，蚂蚁觅食，组合优化（2）禁忌列表，能见度，虚拟信息素，启发式，获知式2. 考虑如下情形：分头沿着两条长度不同的路径去食物源，当到达食物源时 哪条路径会以较高的概率被其选择？论证你的答案。解释：本题考查蚁群算法中信息素的特点与作用。具体内

2、容请参考课堂视频“第 4 章蚁群算法”及其课件。答案：路径长度短的会以较高的概率被选择。具体论证如下：单位时间内通过路径短的蚂蚁数量大于通过路径长的蚂蚁数量，这意味着短 路径上遗留的信息素浓度比较髙，由于蚂蚁倾向于朝着信息素浓度高的方向移动， 所以到后期选择短路径的蚂蚁会越来越多。于是，蚁群的集体行为表现出一种信 息正反馈现象，即最短路径上走过的蚂蚁越多，信息素浓度也就越高，后来的蚂 蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流寻找食物和 蚁穴之间最短路径的。3. 探讨在信息素释放公式中遗忘因子的重要性。解释：本题考查蚁群算法中信息素挥发因子的作用。具体内容请参考课堂视频“第

3、4 章蚁群算法”及其课件。答案：参数 表示信息素挥发因子， 的大小从另一个侧面反映了蚂蚁群体中个体间相互影响的强弱，它直接关系到蚁群算法的全局搜索能力及收敛速度；参数1 表示信息素残留因子，反映了蚂蚁个体之间相互影响的强弱。信息素残留因子的大小对蚁群算法的收敛性能影响非常大，一般取值在 0.10.99 范围内，并且 1 与进化迭代次数近似成正比。若 1 很大，导致残留信息素增多，进而信息的正反馈作用增强，使路径上的残留信息占主导地位，算法容易陷入一个范 围窄小的搜索空间，从而使得算法搜索的随机性减弱，此时虽然算法收敛速度加快，但搜索质量不高。若 1 很小，导致残留信息素较少，进而信息的负反馈作

4、用增强，使算法搜索的随机性随之增强，此时虽然有利于搜索到更多潜在的最优 解以及提高算法的搜索质量，但会使算法的收敛速度降低。4. 下列关于蚁群算法说明错误的是（ ）。A）信息素的积累是正反馈过程，信息素的挥发是负反馈过程。B）TSP 问题中禁忌列表是为了防止同一城市出现多次。C）概率转换规则中参数 越小，蚁群算法的随机性越强。D）概率转换规则中参数 解释：越大，蚁群算法的随机性越强。 本题考查蚁群算法的特点。具体内容请参考课堂视频“第 4 章蚁群算法”及其课件。答案：D（1）路径上信息素的越多，会吸引越多的蚂蚁到该路径上来，所以信息素 的积累是正反馈过程；反之，信息素的挥发是负反馈过程。A 选

5、项正确。（2）TSP 问题要求蚂蚁必须经过所有 n个不同的城市，为了避免蚂蚁重复走入同一个城市，AS 算法为每只蚂蚁配备一个记忆空间，即在具体算法实现中 设计一个数据结构，由这些数据结构组成的表（矩阵）称为禁忌列表。B 选项正 确。（3）参数 越小，信息素积累的作用越小，蚂蚁越偏向于随机搜索，所以 蚁群算法的随机性越强。C 选项正确。（4）参数 项错误。越大，能见度作用的确定性越大，蚁群算法的随机性越弱。D 选5. 请分析 TSP 问题中禁忌列表的作用。解释：本题考查蚁群算法中禁忌列表的作用。具体内容请参考课堂视频“第 4 章蚁群算法”及其课件。答案：TSP 问题要求蚂蚁必须经过所有 n个不同

6、的城市，为了避免蚂蚁重复走入同一个城市，AS 算法为每只蚂蚁配备一个记忆空间，即在具体算法实现中设计一 个数据结构，由这些数据结构组成的表（矩阵）称为禁忌列表。该表中的第k 行（或列）用于存储第k只蚂蚁在当前时刻已访问过的所有城市，记为 J k 。每只蚂蚁在选择城市前，先检索该表来确定下一步可能选择的城市是否已经走过，如果 走过则不在选择的范围内，这样可以避免重复访问同一个城市。当第k 只蚂蚁在当前城市 i选择了下一个城市 j ，则在 Jk的相应位置加入城市 j，因此在一个完整的行程中，禁忌列表首先是空的，当选择所要经过的城市后算法将在线更新禁忌列表，并在完成 n 一次的迭代。个城市的遍历形成

7、一条完整路径后，清空禁忌列表，等待下6. 下列关于禁忌列表的说法错误的是（ ）。A）禁忌列表的作用是为了避免重复访问同一城市。 B）禁忌列表记录的是蚂蚁当前访问过的城市序号。 C）初始禁忌列表是空的。D）遍历所有城市后，禁忌列表不需要清空。解释：本题考查蚁群算法中禁忌列表的作用。具体内容请参考课堂视频“第 4 章蚁群算法”及其课件。答案：D（1）TSP 问题要求蚂蚁必须经过所有 n个不同的城市，为了避免蚂蚁重复走同一个城市，需要建立禁忌列表。A 选项正确。（2）禁忌列表的第 k 行（或列）用于存储第 k 只蚂蚁在当前时刻已访问过的 所有城市，记为 J k 。B 选项正确。（3）在一个完整的行程

8、中，禁忌列表首先是空的。C 选项正确。（4 ）当选择所要经过的城市后算法将在线更新禁忌列表，并在完成 n个城市的遍历形成一条完整路径后，清空禁忌列表，等待下一次的迭代。D 选项错误。7. 以蚁周模型为例，简述蚁群算法解决 TSP 问题的步骤。解释：本题考查蚁群算法求解 TSP 问题的过程。具体内容请参考课堂视频“第 4 章蚁群算法”及其课件。答案：AS 算法求解 TSP 的具体操作步骤如下。 ( t ) ij ( t ) k i 步骤 1：初始化，首先设定相关参数：所需遍历城市数 n 、蚂蚁数 m 、初始时各路径信息素 (0) i , j0、 m 只蚂蚁遍历（循环）次数的最大值N、信息素挥 m

9、ax发系数 以及 、Q 等。建立禁忌列表 J k ，并保证此时表中没有任何城市。 步骤 2：将 m 只蚂蚁随机放在各个城市上，每个城市至多分布一个蚂蚁，并将 m 个蚂蚁所在城市存入禁忌列表 Jk。步骤 3：所有蚂蚁依据概率转换规则选择下一城市，并将选择城市存入禁忌 列表。步骤 4：所有蚂蚁遍历完 n 个城市后在所经过的路径上更新信息素，并记录 本次迭代过程中的最优路径和最优路径长度。步骤 5：清空禁忌列表 Jk，重复步骤 3 和步骤 4直到每一只蚂蚁完成N次max遍历所有城市，最后输出的路径为最优路径。8. 简述蚁群算法中参数 和 的作用。解释：本题考查蚁群算法参数 和 的作用。具体内容请参考

10、课堂视频“第 4 章蚁群算法”及其课件。答案：在下面的概率转换规则公式中，pkij ij (t)il illJ0如果 j J k如果 j J k参数 表示残留信息的相对重要程度，其大小反映了蚂蚁在路径搜索过程中随机性因素作用的强弱；参数 表示能见度的相对重要程度，其大小反映了在路径搜 索过程中确定性因素作用的强弱。9. 简述蚁群算法的特点。解释：本题考查对蚁群算法特点的总结。具体内容请参考课堂视频“第 4 章蚁群算法”及其课件。答案：1蚁群算法是一种自组织的优化算法。自组织就是在没有外界作用下使得 系统熵减小的过程（即系统从无序到有序的变化过程），蚁群算法充分体现了这 个过程。2蚁群算法是一种分布式计算的优化算法。每只蚂蚁搜索的过程彼此独立， 仅通过信息素进行通信。所以蚁群算法可以看作是一个分布式的多 Agent 系统， 它在问题空间的多点同时开始进行独立的解搜索，这不仅提高了算法的效率和可 靠性，也使得算法具有较强的全局搜索能力。蚁群算法具有的分布式计算能力使 其易于并行实现。3蚁群算法是一种具有正反馈机制的优化算法。对蚁群算法来说，初始状 态时各个路径存在完全相同的信息素，算法采用的反馈方式是较优的路径上留下 更多的信息素，而更多的信息素又吸引了更多的蚂蚁选择这条路径，这个正反馈 的过程使得这个路径上的信息素不