计算智能题库 蚁群算法

第四章 蚁群算法 习题与答案

1. 填空题

（1）蚁群算法的缩写是          ，它模拟了自然界中           过程而提出，可以解决               问题。

（2）蚁群算法需要一个记忆空间，称为           ，表示已经过的路径。判断选择城市的主要依据有           和         ，前者代表          愿望，后者代表          愿望，反映了问题求解过程中经验的积累。

解释：

本题考查蚁群算法的基础知识。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：

（1）ACO，蚂蚁觅食，组合优化

（2）禁忌列表，能见度，虚拟信息素，启发式，获知式

2. 考虑如下情形：分头沿着两条长度不同的路径去食物源，当到达食物源时哪条路径会以较高的概率被其选择？论证你的答案。

解释：

本题考查蚁群算法中信息素的特点与作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：

路径长度短的会以较高的概率被选择。

具体论证如下：

单位时间内通过路径短的蚂蚁数量大于通过路径长的蚂蚁数量，这意味着短路径上遗留的信息素浓度比较髙，由于蚂蚁倾向于朝着信息素浓度高的方向移动，所以到后期选择短路径的蚂蚁会越来越多。于是，蚁群的集体行为表现出一种信息正反馈现象，即最短路径上走过的蚂蚁越多，信息素浓度也就越高，后来的蚂蚁选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流寻找食物和蚁穴之间最短路径的。

3. 探讨在信息素释放公式中遗忘因子的重要性。

解释：

本题考查蚁群算法中信息素挥发因子的作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：

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

4. 下列关于蚁群算法说明错误的是（ ）。

A）信息素的积累是正反馈过程，信息素的挥发是负反馈过程。

B）TSP问题中禁忌列表是为了防止同一城市出现多次。

C）概率转换规则中参数越小，蚁群算法的随机性越强。

D）概率转换规则中参数越大，蚁群算法的随机性越强。

解释：

本题考查蚁群算法的特点。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：D

（1）路径上信息素的越多，会吸引越多的蚂蚁到该路径上来，所以信息素的积累是正反馈过程；反之，信息素的挥发是负反馈过程。A选项正确。

（2）TSP问题要求蚂蚁必须经过所有n个不同的城市，为了避免蚂蚁重复走入同一个城市，AS算法为每只蚂蚁配备一个记忆空间，即在具体算法实现中设计一个数据结构，由这些数据结构组成的表（矩阵）称为禁忌列表。B选项正确。

（3）参数越小，信息素积累的作用越小，蚂蚁越偏向于随机搜索，所以蚁群算法的随机性越强。C选项正确。

（4）参数越大，能见度作用的确定性越大，蚁群算法的随机性越弱。D选项错误。

5. 请分析TSP问题中禁忌列表的作用。

解释：

本题考查蚁群算法中禁忌列表的作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：

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

6. 下列关于禁忌列表的说法错误的是（ ）。

A）禁忌列表的作用是为了避免重复访问同一城市。

B）禁忌列表记录的是蚂蚁当前访问过的城市序号。

C）初始禁忌列表是空的。

D）遍历所有城市后，禁忌列表不需要清空。

解释：

本题考查蚁群算法中禁忌列表的作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：D

（1）TSP问题要求蚂蚁必须经过所有n个不同的城市，为了避免蚂蚁重复走同一个城市，需要建立禁忌列表。A选项正确。

（2）禁忌列表的第k行（或列）用于存储第k只蚂蚁在当前时刻已访问过的所有城市，记为。B选项正确。

（3）在一个完整的行程中，禁忌列表首先是空的。C选项正确。

（4）当选择所要经过的城市后算法将在线更新禁忌列表，并在完成n个城市的遍历形成一条完整路径后，清空禁忌列表，等待下一次的迭代。D选项错误。

7. 以蚁周模型为例，简述蚁群算法解决TSP问题的步骤。

解释：

本题考查蚁群算法求解TSP问题的过程。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：

AS算法求解TSP的具体操作步骤如下。

步骤1：初始化，首先设定相关参数：所需遍历城市数、蚂蚁数、初始时各路径信息素、m只蚂蚁遍历（循环）次数的最大值、信息素挥发系数。建立禁忌列表，并保证此时表中没有任何城市。

步骤2：将m只蚂蚁随机放在各个城市上，每个城市至多分布一个蚂蚁，并将m个蚂蚁所在城市存入禁忌列表。

步骤3：所有蚂蚁依据概率转换规则选择下一城市，并将选择城市存入禁忌列表。

步骤4：所有蚂蚁遍历完n个城市后在所经过的路径上更新信息素，并记录本次迭代过程中的最优路径和最优路径长度。

步骤5：清空禁忌列表，重复步骤3和步骤4直到每一只蚂蚁完成次遍历所有城市，最后输出的路径为最优路径。

8. 简述蚁群算法中参数的作用。

解释：

本题考查蚁群算法参数的作用。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案： 

在下面的概率转换规则公式中，

参数表示残留信息的相对重要程度，其大小反映了蚂蚁在路径搜索过程中随机性因素作用的强弱；参数表示能见度的相对重要程度，其大小反映了在路径搜索过程中确定性因素作用的强弱。

9. 简述蚁群算法的特点。

解释：

本题考查对蚁群算法特点的总结。

具体内容请参考课堂视频“第4章蚁群算法”及其课件。

答案：

1．蚁群算法是一种自组织的优化算法。自组织就是在没有外界作用下使得系统熵减小的过程（即系统从无序到有序的变化过程），蚁群算法充分体现了这个过程。

2．蚁群算法是一种分布式计算的优化算法。每只蚂蚁搜索的过程彼此独立，仅通过信息素进行通信。所以蚁群算法可以看作是一个分布式的多Agent系统，它在问题空间的多点同时开始进行独立的解搜索，这不仅提高了算法的效率和可靠性，也使得算法具有较强的全局搜索能力。蚁群算法具有的分布式计算能力使其易于并行实现。

3．蚁群算法是一种具有正反馈机制的优化算法。对蚁群算法来说，初始状态时各个路径存在完全相同的信息素，算法采用的反馈方式是较优的路径上留下更多的信息素，而更多的信息素又吸引了更多的蚂蚁选择这条路径，这个正反馈的过程使得这个路径上的信息素不断增多，引导整个系统向最优解的方向进化。因此，正反馈加快了算法的进化过程，最终使算法收敛到最优解。

4．蚁群算法具有较强的鲁棒性。相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其他组合优化问题的求解中。