人工智能导论第 5 版 思考题 第六章

6.1 遗传算法的基本步骤和主要特点是什么？

遗传算法的基本步骤：

1. 实用随机方法或者其他方法，产生一个有N个染色体的初始群体；

2. 对群体中的每一个染色体计算适应值；

3. 若满足停止条件、则算法停止，否则以概率 pi 从群体中随机选择一些染色体构成一个新的群体；

4. 以概率 pc 进行交叉产生一些新的染色体，得到一个新的种群；

5. 以一个较小的概率 pm 使染色体的一个基因发生变异，产生一个新群体，返回步骤二。

主要特点：

1. 可以直接对结构对象进行操作；

2. 遗传算法不是无方向的随机搜索，而是一个利用随机技术来指导对一个编码的参数空间进行高效率搜索的方法；

3. 遗传算法采用群体搜索策略，采用同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估；

4. 遗传算法的适应度函数不受连续可微的约束，定义域也可以任意设定。

6.2 适应度函数在遗传算法中的作用是什么？试举例说明如何构造适应度函数。

适应度函数是用来区分群体中个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。

6.3 选择的基本思想是什么？

选择的基本思想是从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。

6.4 简述多种群遗传算法与基本遗传算法的异同。

多种群遗传算法是在遗传算法的基础上经过改进并引入多种群的概念。

主要有以下的改进: 

1. 把单个种群改变为多个种群，每个种群都有着可控制的参数，例如交叉，变异概率。给予不同的数值能够产生不同的搜索结果。

2. 通过特定的操作因子来控制各种群之间的联系与协同进化，例如设定移民算子，可以得出所有种群最优的进化结果。

3. 多种群的收敛条件可以根据每个种群进化的最优个体的数目来测定，各个种群中的最优个体可以增加人工选择算子来进行保留。

6.5 简述多倍体遗传算法与基本遗传算法的异同。

基于种群保留遗传算法，引入了多倍体的概念，给出了一种基于种群保留的多倍体遗传算法.当该算法运行时，种群个体将由单倍体变为多倍体。

6.6 群智能算法的基本思想是什么？

初始一个种群，选择种群中适应度高的个体进行交叉变异。然后再将适应度低的个体淘汰，留下适应度高的个体进行繁殖，这样不断的进化，最终留下的都是优秀的个体。

6.7 群智能算法的主要特点是什么？

特点是表现生物学上的现象与对应的仿生智能计算的关系。

6.8 列举几种典型的群智能算法，分析它们的主要优点、缺点。

包括：粒子群优化算法、蚁群算法和人工免疫算法。

6.9 简述群智能算法与进化算法的异同。

这两种算法都是受自然现象的启发，两者都是基于种群的方法，且种群中的个体之间、个体与环境之间存在相互作用。两者都是一种元启发式随机搜索方法。

不同之处：EC 方法强调种群的达尔文的进化模型，而 SI 优化方法则注重对群体中个体之间的相互作用与分布式协同的模拟。

6.10 简述粒子群算法的流程。

1. 初始化每个粒子，即在允许范围内随机设置每个粒子的初始位置和速度。

2. 评价每个粒子的适应度，计算每个粒子的目标函数。

3. 设置每个粒子的 pi 。对每个粒子，将其适应度与其经历过的最好位置 pi 进行比较，如果

优于pi ，则将其作为该粒子的最好位置 pi 。

4. 设置全局最优值 pg 。对每个粒子，将其适应度与群体经历过的最好位置 p 进行比较，如

果优于 pg ，则将其作为当前群体的最好位置 pg 。

5. 检查终止条件。如果未达到设定条件（预设误差或者迭代的次数），则返回第 2 步。

6.11 简述粒子群算法位置更新方程中各部分的影响。

只有第 1 部分：φ1=φ2=0：粒子将一直以当前的速度飞行，直至到达边界；由于它智能搜索有限的区域，所以很难找到好解。

没有第 1 部分：ω=0：速度只取决于粒子当前位置和其历史最好位置 Pi，Pg，速度本身没有记忆性。

没有第 2 部分：φ1=0：粒子没有认知能力，“只有社会模型”；在粒子的互相作用下，有能力达到新的搜索空间，但对复杂问题，容易陷入局部最优解。

没有第 3 部分：φ2=0：粒子间没有社会共享信息，也就是“只有认知模型”。因为个体间没有交互，一个规模为 M 的群体等价于 M 个单个粒子的运行，因而得到最优解的几率非常小。

6.12 举例说明粒子群算法的搜索原理，并简要叙述粒子群算法有哪些特点。

粒子群算法的基本原理是粒子种群在搜索空间以一定的速度飞行， 每个粒子在搜索时，考虑自己搜索到的历史最优位置和种群内其他粒子的历史最优位置， 在此基础上进行位置的变化。

粒子群算法的特点是简单易行，收敛速度快，设置参数少

6.13 粒子群算法的寻优过程包含哪几个阶段？寻优的准则有哪些？

6.14 粒子群算法中的参数如何选择？

粒子群算法的参数通过模糊系统进行调节。

6.15 举例说明蚁群算法的搜索原理，并简要叙述蚁群算法的特点。

蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径问题，其原理是一种正反馈机制或称增强型学习系统；它通过“最优路径上蚂蚁数量的添加 → 信息素强度添加 → 后来蚂蚁选择概率增大 → 最优路径上蚂蚁数量更大添加”达到终于收敛于最优路径上 L

它是一种通用型随机优化方法，它吸收了蚂蚁的行为特（内在搜索机制），它是使用人工蚂蚁仿真（也称蚂蚁系统）来求解问题 L 但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能 L 人工蚂蚁有一定的记忆; 人工蚂蚁不全然是瞎的; 人工蚂蚁生活的时空是离散的 L

它是一种分布式的优化方法，不仅适合眼下的串行计算机，并且适合未来的并行计算机 L

它是一种全局优化的方法，不仅可用于求解单目标优化问题，并且可用于求解多目标优化问题L

它是一种启示式算法, 计算复杂性为 o (Nc*n2*m)，当中 Nc 是迭代次数，m 是蚂蚁数目，n 是目的节点数目 L

6.16 蚁群算法的寻优过程包含哪几个阶段？寻优的准则有哪些？

6.17 蚁群算法中的参数如何选择？

确定蚂蚁数目，根据节点规模 / 蚂蚁数目≈1.5 来确定大概的蚂蚁数目；

参数粗调，即调整信息启发式因子 、期望启发式因子 和信息素强度 Q 等参数；

参数微调，即调整信息挥发因子。

目前蚁群算法参数的选择在理论上没有依据，主要依经验而定。