计算智能期中题总结

# 填空题

旅行商问题的时间复杂度为 O(n!)。
对于最优化问题，其一般形式为：
min f(X)
s.t. {gi(X) ≥ 0 i=1,2,...,m
{h(X) = 0 j=1,2,...,l
其中 X = (x₁,x₂,...,xₙ)ᵀ ∈ Rⁿ 为 决策变量向量。
f (X) 为 目标函数，gi (X) ≥ 0, h (X) = 0 为 约束条件。
遗传算法的基本遗传操作包括选择，交叉，变异。
如果有如下染色体，其适应度值如下表所示：

Chromosome	Fitness value
Chromosome 1	5
Chromosome 2	3
Chromosome 3	2
Chromosome 4	1

采用轮盘赌法进行选择每个染色体的选择概率分别为：5/11,3/11,2/11,1/11。
5. 根据决策变量取值类型，作业车间调度问题属于离散优化问题。
6. 人工智能的学派有 逻辑主义， 联结主义， 行为主义，
7. 根据 决策变量 的取值类型，我们可以将最优化问题分为连续优化问题和组合优化问题。

# 判断题：

二进制编码存在的主要缺点是汉明悬崖。T
格雷编码有效地解决了汉明悬崖问题。T
对于函数优化问题，二进制编码是首选。F
实数编码适应于多维、高精度要求的连续函数优化问题。T
寻找集合中的最小元素的计算复杂度为 O (n)。T
对集合中的元素进行排序的计算复杂度为 O (nlogn)。T
背包问题的计算复杂度为 O (2ⁿ)。T
旅行商问题的计算复杂度为 O (2n)。F
计算智能算法是人工智能的一个分支，是联结主义的典型代表，又称为仿生学派或生理学派。T
计算智能是受大自然智慧和人类智慧启发而被设计出的一类算法的统称。T
计算智能算法在处理优化问题的时候，对求解问题需要严格的数学推导，而且有很好的全局搜索能力，具有普遍的适应性和求解的鲁棒性。F
计算智能方法采用启发式的随机搜索策略，在问题的全局空间中进行搜索寻优，能在可接受的时间内找到全局最优解或者可接受解。T

# 选择题

以下哪个不属于计算智能的特点（D）？
A. 不已达到某个最优条件或找到理论上的精确最优解为目标，而是更看重计算的速度和效率。
B. 对目标函数和约束条件函数的要求比较宽松，不需要满足可微可导性、连续性、凹凸性等要求。
C. 算法是以包含多个进化个体的种群为基础，寻优过程实际上就是种群的进化过程。
D. 算法有坚实的理论，保证算法一定能够收敛到最优解。
以下不是组合优化问题的是（D）
A. 背包问题
B. 整数规划问题
C. 0-1 规划问题
D. 神经网络权重优化
以下哪个不是 Matlab 绘三维图形的函数（A）
A. plot
B. surf
C. plot3
D. mesh
进化算法主要表现为全局搜索方式，以下错误的是（D）
A. 有指导搜索
B. 渐进式寻优
C. 并行式搜索
D. 严格数学推导
以下哪个不是遗传算法的基本遗传操作（B）
A. 选择
B. 重构
C. 变异
D. 交叉
以下哪个是 Matlab 绘三维图形的函数（B）
A. plot
B. surf
C. plot3
D. mesh
关于计算复杂度，以下错误的是（C）
A. 寻找如中两点最短路径的计算复杂度为 O (n²)
B. 对集合中的元素进行排序的计算复杂度为 O (nlogn)
C. 旅行商问题的计算复杂度为 O (2n)
D. 背包问题的计算复杂度为 O (2ⁿ)
以下不是组合优化问题的是（D）
A. 旅行商问题
B. 车间调度问题
C. 图着色问题
D. 神经网络权重优化
以下关于遗传算法的基本概念说法错误的是（D）
A. 种群是指用遗传算法求解问题时，初始给定的多个解的集合
B. 个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示
C. 适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数，其函数值是遗传算法实现优胜劣汰的主要依据。
D. 变异是通过两个解交叉原则产生一组新解的过程。
以下哪个一般不作为遗传算法停止的准则（D）
A. 在进行 X 次迭代之后，适应度值没有什么太大改变
B. 事先为算法定义的进化的代数或者评估的适应度计算次数
C. 当适应度值已经达到了预先定义的值
D. 随机产生一个数大于某一个阈值
以下哪个不是常用的编码方式（C）
A. 位串编码
B. 符号编码
C. 交叉编码
D. 实数编码
以下说法错误的是（A）
A. 人工神经网络模仿人类免疫系统的生理构造和信息处理的过程。
B. 模糊逻辑模仿人类语言和思维中的模糊性概念，模拟人类的智慧。
C. 进化计算模仿生物进化过程和群体智能过程，模拟大自然的智慧。
D. 计算智能不要求目标函数和约束条件具有连续性、凸性、可微可导性等，有时甚至都不要求有解析表达式，对计算中数据的不确定性也有很强的适应能力。
以下关于遗传算法说法错误的是（B）
A. 在基本遗传算法中，通常采用随机方法来产生初始群体的
B. 遗传算法需要个体数目很少
C. 适应度用来衡量字符串性能好坏，同时也决定了该个体被遗传到下一代群体中的概率大小
D. 适应度函数是遗传算法进化的驱动力
以下哪个不是适应度函数需要满足的条件（D）
A. 单值、非负
B. 能够正确反映问题解领域内的解空间分布情况
C. 具有较强的通用性
D. 需要进行尺度变换
以下哪个不是交叉的方式（D）
A. 多点交叉
B. 均匀交叉
C. 算术交叉
D. 突变交叉

# 简答题

进化算法常用的编码方式有哪些？3-57

位串编码 {二进制编码、Gery 编码、动态编码}、实数编码、符号编码、参数级联编码、多参数交叉编码
轮盘赌算法的具体实现是什么，请举例说明。3-21

轮盘赌算法又称为轮赌选择法。主要依据个体被选中的概率取决于该个体的相对适应度。具体实现如下：
1. 将染色体的适应度值转换成选择概率，
2. 累计每个染色体的概率值构成区间
3. 随机生成一个 [0,1] 之间的数
4. 落入该区间的染色体即为被选中的个体。
经典的人工免疫算法有哪些，分别都有哪些应用场景？7-13

经典的人工免疫算法包括负选择算法、克隆选择算法、免疫算法与智能计算，应用场景包括识别与分类问题、优化问题、机器人学习与控制、数据挖掘等等。
蚁群优化算法的基本原理是什么，它的改进版本有哪些，请简述为什么做这些改进，有什么益处？5-35

蚂蚁通过感知信息素浓度选择路径，偏向信息素较多的方向行进。较短路径上信息素积累更快，吸引更多蚂蚁，形成正反馈。最终所有蚂蚁集中在最短路径上，而其他路径信息素逐渐消散。
蚂蚁系统、精华蚂蚁系统、基于排列的蚂蚁系统、最大最小蚂蚁系统、蚁群系统、连续正交蚁群系统。
这些改进是为了提高蚁群算法的效率、避免陷入局部最优、加快收敛速度。精华蚂蚁系统强化最优路径，使算法更快收敛；最大最小蚂蚁系统限制信息素范围，防止过早收敛。基于排列和连续正交的改进则适应不同类型问题，提升全局搜索和局部搜索的平衡性。
多模态优化中的多模态指的是什么，为什么需要多模态？

多模态指的是全局中具有多个局部最优解的情况；多模态优化能有效避免陷入局部最优，寻找多个解更适用于复杂优化问题。
请简述在智能优化中处理多模态的典型的技术有哪些？

主要 niching 的技术：clearing、crowing、speciation、clustering
请简述粒子群优化算法的原理和关键步骤。

通过模拟生物群体的协作与信息共享迭代更新位置和速度寻求问题的最优解。
初始化、例子速度和位置的更新、评估粒子的适应度函数值。

粒子群优化算法是一种基于群体智能的随机优化算法，源于对鸟群捕食行为的模拟。算法通过让一群 "粒子" 在解空间中移动，寻求最优解。每个粒子代表一个潜在的解，粒子通过跟踪自己和邻居的最佳位置，不断调整其搜索方向和速度，以达到最优。
1. 初始化粒子群
2. 根据自身历史最优位置和全局最优位置更新每个粒子的速度和位置。
3. 评估粒子的适应度函数值。
4. 如果满足结束条件则输出全局最优结果并结束程序。
计算智能的主要研究方向和特点是什么？1
- 人工神经网络：模仿人脑的生理构造和信息处理的过程，模拟人类的智慧
- 模糊逻辑（模糊系统）：模仿人类语言和思维中的模糊性概念，模拟人类的智慧
- 进化计算：模仿生物进化过程和群体智能过程，模拟大自然的智慧
NP 问题和 P 问题分别是什么，P=NP？1

P 问题可以用一个确定性算法在多项式时间内判定或解出。而 NP 问题是可以用一个确定性算法在多项式时间内检查或验证出它们的解。比较 P 类问题和 NP 类问题的定义，我们很容易得到一个结论：P∈NP。
在算法设计中，常用的典型拓扑结构有哪些？ 6-21

静态拓扑结构：
全局：星形
局部：环形、齿形、冯诺依曼形、金字塔型
动态拓扑结构：
逐步增长、最小距离、重新组合、随机选择法
精英选择机制是什么？

直接将当前种群中最优的个体原封不动的保留到下一代，不对精英个体进行交叉变异操作。

精英选择机制指在每一代中保留适应度最高的个体，确保最优解不丢失。这样可以加速算法收敛并提高全局搜索能力，但可能导致多样性降低。
早熟现象是什么，是什么引起的，应该如何避免？

早熟现象是指算法在进化早期就收敛于局部最优解，失去继续探索的能力。因为个体过于集中或选择压力过大，导致算法很快就集中在局部最优解附近，无法探索到其他解空间。可以尝试增加多样性、动态调整参数、精英选择机制等方法来避免。
蚁群算法中信息素的更新规则是什么，不同的蚁群算法的更新规则为什么不同？
蚁群算法中信息素的更新规则：
1. 初始化时，所有边上的信息素设为 t0。
2. 每轮迭代中，信息素蒸发，所有边上的信息素乘以一个小于 1 的常数。
3. 蚂蚁根据路径长度在经过的边上释放信息素，路径越短，释放的信息素越多。
4. 重复步骤 2 和 3，直至算法终止。
精华蚂蚁系统（EAS）：在基础 AS 上增加对最优路径的强化，帮助更快收敛。
基于排列的蚂蚁系统（ASrank）：给信息素加权值，按路径长短排名，前 w-1 名蚂蚁释放信息素，放大信息素差异，指导搜索。
最大最小蚂蚁系统（MMAS）：改进包括只允许最优蚂蚁释放信息素、限制信息素范围、初始值设为上限、系统停滞时重新初始化信息素。
多样性和收敛性是什么意思？

多样性指种群中个体的差异性，代表搜索空间的覆盖范围。高多样性意味着个体分布广泛，能探索更多解空间，增加找到全局最优解的可能性，避免早熟收敛。收敛性指算法逐渐集中在一个最优解附近，最终收敛到一个解。种群会逐渐集中到适应度更高的区域，但过快的收敛可能忽视其他潜在的全局最优解。在优化问题中，多样性和收敛性相互矛盾，需要保持平衡。
蚁群算法有哪些参数，在参数设置时有哪些考虑？5-34

蚂蚁数目 m：通常取问题规模 n，或根据算法，如 ACS 中取 m=10。
信息素权重 α 和启发式信息权重 β：一般设定 α=1，β=2~5。
信息素挥发因子 ρ：AS、EAS 中 ρ=0.5；ASrank 中 ρ=0.1；MMAS 中 ρ=0.02；ACS 中 ρ=0.1。
初始信息素量 τ₀：根据算法公式计算，与问题规模相关。
释放信息素的蚂蚁数 w：在 ASrank 中设定 w=6。
进化停滞判定代数 rs：在 MMAS 中设置 rs=25。
信息素局部挥发因子 ξ：在 ACS 中设置 ξ=0.1。
伪随机因子 q₀：在 ACS 中设置 q₀=0.1。
进化策略的代表性算法是什么，它的思想设计是什么，它有哪些应用？
CMA-ES 是进化策略中最具代表性的算法之一，特别适合于解决多峰函数和高维数值优化问题。CMA-ES 的设计思想是基于 “协方差矩阵自适应” 的进化策略，即在进化过程中逐步调整协方差矩阵，以适应目标函数的形状和特征，帮助算法在搜索空间中更高效地找到极值点。
进化策略尤其适用于复杂、多峰、多变量的优化问题，例如机器学习模型优化、工业控制、机器人学、结构优化等。
全局粒子群算法和局部粒子群算法分别指什么？6-21
GPSO：每个粒子根据全局最优位置（全局最佳解）和自身的历史最优位置进行更新。所有粒子共享一个全局最优解，算法具有较强的全局搜索能力。GPSO 往往具有比 LPSO 更快的收敛速度。不过有时会陷入局部最优
LPSO：每个粒子只根据其局部邻域内的最优位置和自身的历史最优位置进行更新。粒子只与其邻域内的粒子交换信息，算法具有较强的局部搜索能力，有助于避免陷入局部最优。LPSO 由于具有更好的多样性，因此一般不容易落入局部最优
在处理多峰问题上具有更好的性能在实际应用中，可以根据具体问题选择具体的算法版本。
处理多模态优化的 niching 方法有哪些？
共享函数法（Sharing Function Method）
拥挤法（Crowding Method）
分离选择（Clearing Method）
拥挤距离排序（Crowding Distance Sorting）
多种群策略（Multiple Population Strategy）
聚类算法结合（Clustering Techniques）
递减半径法（Variable Radius Method）
分布估计算法（Estimation of Distribution Algorithms，EDA）
这些 niching 方法旨在：
维持种群多样性：防止早熟收敛，避免陷入局部最优。
同时发现多个最优解：满足多模态优化问题的需求。
提高算法性能：在多峰函数优化中获得更全面的解集。
请简述遗传算法的思想和步骤。3-47

遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。
个体编码 - 生成初始群体 - 计算适应度值 - 选择运算（轮盘赌）- 交叉运算 - 变异运算。

# 综合计算题

假如现有 5 个个体 A、B、C、D、E；它们的适应度分别为 3、5、1、4、2，这些个体在坐标轴上的坐标分别为 (5,2)、(3,3)、(3,1)、(3,2)、(1,2)，请实现清除半径为 2、生态容量为 2 的 clearing 算法。
步骤：
1. 初始化参数：
  半径 R=2
  生态容量 K=2
2. 排序个体：按照适应度从高到低对个体排序，以便优先保留适应度高的个体。
  排序后的个体：B (5), D (4), A (3), E (2), C (1)
3. 清除过程：
  从适应度最高的个体开始处理。若某个体的邻域（即半径为 R=2 的范围内）已经达到了生态容量 K=2，则清除该区域内的其他个体（即将它们的适应度设为 0）。
  - 处理个体 B (3,3)：
    邻域内有两个个体 D (3,2) 距离 1，A (5,2) 距离 2.24
    保留 B 和 D，其余个体适应度设置为 0。
  - 处理个体 D (3,2):
    邻域内个体：A (5,2),B (3,3)
    已经处理过了故不再处理。
  - 处理个体 A (5,2):
    邻域内个体：D (3,2),B (3,3)
    已经处理过了故不再处理。
  - 处理个体 E (1,2):
    邻域内没有其他个体，保留 E。
  - 处理个体 C (3,1):
    邻域内没有符合的保留空间，因此 C 的适应度设为 0。
  处理后的个体适应度值为：B:5 D:4 E:2 A:0 C:0
请给出用蚁群算法求解一个四个城市的 TSP 问题的执行步骤，四个城市 A、B、C、D 之间的距离矩阵如下：

W = dij = [∞ 3 1 2
           3 ∞ 5 4
           1 5 ∞ 2
           2 4 2 ∞]

假设蚂蚁种群的规模 m=3，参数 α=1，β=2，ρ=0.5。

请用遗传算法求解下面二元函数的最大值：

1
2
3

max     f(x1,x2)=x1²+x2²
s.t.    x1 ∈ {1,2,3,4,5,6,7}
        x2 ∈ {1,2,3,4,5,6,7}

要求包含个体编码，种群初始化，适应度计算，轮盘赌选择，交叉变异等操作，手推一个选择过程即可，注意步骤的完整性。

编码：
我们可以对 x1 和 x2 使用二进制编码来计算，由于都是整数且个体最大为 7，因此可以使用 2^3=8 及三位二进制数来表示，即 1=001，2=010，3=011...7=111。
每个个体可以用 6 位二进制数表示，其中前三位表示 x1，后三位表示 x2。
例如个体（3，5）可以表示为 011101。
初始化种群：
假设初始化四个个体：
个体 1：010101（2，5）
个体 2：011001（3，1）
个体 3：011011（3，3）
个体 4：101001（5，1）
计算适应度值：
个体 1:f (2,5)=2² + 5²=29
个体 2:f (3,1)=3² + 1²=10
个体 3:f (3,3)=3² + 3²=18
个体 4:f (5,1)=5² + 1²=26
轮盘赌选择:
总适应度 = 29+10+18+26=83
计算每个个体的选择概率
个体 1：29/83
个体 2：10/83
个体 3：18/83
个体 4：26/83
然后生成随机数选择两个个体，假设选择个体 1 和个体 4
交叉：
个体 1：010101
个体 4：101001
随机选择交叉位置，假设第 4 位交叉产生新个体：
子个体 1：010001
子个体 2：101101
变异：
随机变异每个个体的每个位，假设变异后的结果
子个体 1：010011（第 5 位）
子个体 2：111101（第 2 位）
更新种群：
子个体 1：010001
子个体 2：101101
子个体 3：010011
子个体 4：111101
然后重复步骤 2-6 直到满足最终条件

本文采用署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议，转载请注明出处。