微专业课，课程代码 22AS31104W。2026 春。授课教师：LFZ。
7 进化计算 (Evolutionary Calculation, EC)
基本思想和原理
设 \(G\)：基因型 (genotype)；\(P\)：表型 (phenotype)；\(I\)：所有环境序列的集合。那么生物演化的种类包括以下几种：
- \(f_1:I\times G\to P\)：表观遗传（在环境和基因共同影响下产生表型）；
- \(f_2:P\to P\)：自然选择（筛选优秀的表型）；
- \(f_3:P\to G\)：基因型存活（优秀的表型遗传给下一代）；
- \(f_4:G\to G\)：基因变异。
进化 = 最优化适应度 (fitness)，故可以借鉴其过程，解决最优化问题。
进化算法可以被看作是一种搜索程序，包括以下步骤：生成问题的潜在的解；测试每个解的适合性；生成新的解。
应用领域如：机器人控制、仪器设计、时序预测模型、博弈论生成策略。
问题需明确定义：一种解必须能够可以与其他解比较。
全局数值最优化
对于多维优化问题，初始的亲代从 \(\mathbb R^n\) 上选取，子代由亲代在各个维度上随机变异生成。
变异的方式：
- 突变 (mutate)：单个亲代 \(\to\) 子代；
- 重组 (recombine)：多个亲代 \(\to\) 子代。重组的方式：
- 交叉 (crossover)：\(x_1=(x_{11},\cdots,x_{1n}),x_2=(x_{21},\cdots,x_{2n})\)，选择 \(3\) 为交叉位点，则变为 \(x_1'=(x_{11},x_{12},x_{{\color{red}2}3},\cdots,x_{{\color{red}2}n}),x_2'=(x_{21},x_{22},x_{{\color{red}1}3},\cdots,x_{{\color{red}1}n})\)。
- 混合：取亲代的平均值 \(\left(\dfrac{x_{11}+x_{21}}2,\dfrac{x_{12}+x_{22}}2,\cdots,\dfrac{x_{1n}+x_{2n}}2\right)\)。
例 1 用进化算法最小化代价函数 \(f(x, y, z, k) = x^2 + y + 2yz + zk\)。亲代随机初始化为
\[\begin{gathered} (x_1, y_1, z_1, k_1) = (0, -1, 1, 1),\\ (x_2, y_2, z_2, k_2) = (1, 2, 1, -2),\\ (x_3, y_3, z_3, k_3) = (-1, 1, 0, -1). \end{gathered} \](1) 如果通过交叉重组生成子代，且交叉点为 \(3\)，计算所有可能的子代，并从这些子代中选择最优的一个。
(2) 如果通过对亲代两两混合重组生成子代，计算所有可能的子代，并从这些子代中选择最优的一个。
(1) （注意交换的区间包含交叉点。）
选择最佳点：\((0, -1, 1, -2)\)。
(2) 重组结果：
选择最佳点：\((-0.5, 0, 0.5, 0)\)。
例 2 考虑函数 \(f(x) = \sqrt{x} + \dfrac{1}{x}\) 的最小化问题，其中亲代选取为 \(x_1 = 5\) 和 \(x_2 = 6\)。找到一种通过交叉重组产生子代的方法，要求交叉点为 \(3\)。在子代中挑选出最优的一个。
- 将 \(x_1\) 和 \(x_2\) 转化为二进制：\(x_1 = 101, x_2 = 110\)。
- 第 \(3\) 点交叉：\(x'_1 = 100, x'_2 = 111\)。
- 转换回十进制：\(x'_1 = 4, x'_2 = 7\)。
- 分别代入：\(f(x'_1) = \dfrac{9}{4},f(x'_2) = \sqrt{7} + \dfrac{1}{7}\)。
- 最佳点：\(x = 4\)。
组合最优化
以旅行推销员问题 (Traveling Salesman Problem, TSP) 为例。这是一个 NP-Hard 问题，无法在多项式时间内解决。
其他组合问题：
- 神经网络中合适的神经元数量与结构；
- 模糊控制系统中隶属度函数的个数与形状；
- 可变大小的数据结构，如有限状态自动机和符号表达式树。
如何产生子代（变异）：
- 选择和替代 (select & replace)：随机选择两个城市，交换位置；
- 反向 (inversion)：随机选择两个城市，将他们之间的城市反向；——表现最好
- 保护和随机 (protect & randomize)：选择一段不变，其余随机。——表现最差
部分匹配交叉 (partially mapped crossover, PMX)
过程如下：
-
假设有两个亲代 \(\begin{array}c[3, 4, 8, 2, 7, 1, 6, 5] \\ [4, 2, 5, 1, 6, 8, 3, 7]\end{array}\)。
-
选择一部分保持不变并交换：\(\begin{array}c[+,+,+, \boldsymbol{1, 6, 8}, +,+] \\ [+,+,+, \boldsymbol{2, 7, 1}, +,+]\end{array}\)，获得映射关系 \(2\leftrightarrow1,7\leftrightarrow6,1\leftrightarrow8\)。
-
将其他数填回去，如果已存在当前数，则不断应用映射关系，直到找到还未出现的数，保证仍为一个全排列。
例如，先填入 \(\begin{array}c[3,4,{\color{red}+}, \boldsymbol{1, 6, 8}, +,5] \\ [4,+,5, \boldsymbol{2, 7, 1}, 3,+]\end{array}\)，考虑 \(\color{red}+\) 位置，应该是 \(8\)，但 \(8\) 出现过故应用映射关系填 \(1\)，\(1\) 也出现过故填 \(2\)。
-
最终的结果为 \(\begin{array}c[3,4,2, \boldsymbol{1, 6, 8}, 7,5] \\ [4,8,5, \boldsymbol{2, 7, 1}, 3,6]\end{array}\)。
实验证明，PMX + inversion 效果最好。
性能分析
收敛分析
马尔可夫链 (Markov chain, MC)。
数据表示
- 直观表达有用信息；
- 变异友好：具有对亲代进行或大或小改变的可能性，并且改变可控；
- 除非目标是探索一种新的表示的效果，否则利用已经研究过的表示和已经发表过的结果，可以进行更系统和有意义的比较。
选择
设有 \(\mu\) 个亲代。
-
增加/延续 (plus/comma)：
- \((\mu+\lambda)\)：\(\mu\) 个亲代生成 \(\lambda\) 个子代，从 \(\mu+\lambda\) 个数据中选择其中最优的 \(\mu\) 个个体作为下一代的亲代；
- \((\mu,\lambda)\)：\(\mu\) 个亲代生成 \(\lambda\) 个子代，从 \(\lambda\) 个数据中选择其中最优的 \(\mu\) 个个体作为下一代的亲代。
-
比例 (proportional)：与适应度成正比例选择亲代，即选择概率 \(p_i=\dfrac{f(i)}{\sum_{j=1}^\mu f(j)}\)。
-
锦标赛 (tournament)：选择一个大小为 \(q\) 的子集（通常 \(q=2\)），再选择其中最好的作为子代之一，如此重复直到种群被填满。
-
线性排序 (linear ranking)：将解排序后，根据公式计算被选择的概率。一种早期方法 [Baker, 1985] 为排名第 \(i\) 的个体分配的概率为
\[p_i=\frac{\eta^+-\dfrac{(\eta^+-\eta^-)(i-1)}{\mu-1}}{\mu}, \]其中 \(\eta^+,\eta^-\) 为参数。
变异
目的：在解空间中创造可被搜索的更好的解。
种类：二进制突变、高斯突变、一点或 \(n\) 点交叉、混合。取决于数据表示。
-
实数值变异：高斯突变 \(N(\mu,\sigma)\)。\(\mu=0\)：无偏搜索；\(\sigma\)：控制各维度搜索的幅度。
-
多亲代重组算子：
- 例如交叉和混合；
- 不局限于两个亲代；
- 一般地，越多的亲代参与混合，子代更趋向于种群的均值；
- 可能性：局部最优解 vs 更广泛搜索。
-
变量长度/结构变异：有限状态机，符号表达式，差分方程。
-
例如符号表达式（二叉树）：
-
约束条件
- 硬约束：如果违反了，就会使方案变得毫无价值。
- 软约束：可以违反，但违反后会有一些惩罚。
自适应
进化算法中的参数自调节。
1/5 规则：突变成功率要在 1/5 附近。对于标准高斯分布 \(N(0,\sigma)\)，如果成功率过低则调高 \(\sigma\)，反之调低 \(\sigma\)，通过乘除 \(0.85\) 实现。
实参数的元进化
对于每个维度 \(i=1,2,\cdots,n\)，分两步产生子代：
- 标准差的突变：\(\sigma'=\sigma_i\exp(\tau N(0,1)+\tau'N_i(0,1))\)，其中 \(\tau,\tau'\) 是与维度 \(n\) 有关的参数。
- 使用突变过的标准差产生子代：\(x_i'=x_i+N(0,\sigma_i')\)。
实例分析 2
自回归模型 (autoregressive model, AR)
- AR (1 阶)：\(y[t+1]=a_0y[t]+a_1y[t-1]\)；
- ARMA (AR + moving average)：\(y[t+1]=a_0y[t]+a_1y[t-1]+c_0e[t]+c_1e[t-1]\)，或简写为 \(A(q)y[t]=C(q)e[t]\)，其中 \(q\) 为位移算子，定义为 \(q^ky[t]=y[t+k]\)。
- ARMAX (ARMA + external inputs): 含有外部输入/控制项，\(A(q)y[t]=B(q)u[t]+C(q)e[t]\)。
Akaike 信息量标准 (Akaike information criterion, AIC)
信息量标准 (Information Criteria)：适应度 vs 复杂度。如：
- Akaike 信息量标准 (AIC)：极大似然估计 + 基于自由参数个数的惩罚项；
- 最小描述长度 (MDL)：寻找最优的结构大小，使得在信息论框架下对于观测数据有最短的描述；
- 预测均方误差 (PSE)：模型误差 + 误差的方程估计 + 基于自由参数个数的惩罚项。
例 极地 22kHz 海洋声纳信号的裂缝（信号），持续时间不到2.5毫秒，其中的三个被提取出来进行建模。使用 ARMA 模型来精确描述这段声学特征。
建模采用 ARMA 形式 \(A(q)y[t]=C(q)e[t]\)，形成 \(250\) 个备选模型。模型阶数在整数 \(1,\cdots,8\) 之间随机，参数在 \([-0.5,0.5]\) 之间随机。举例：参数组为 \([{\color{red}2},{\color{blue}3},-0.1,0.2,0.4,0.3,-0.02]\)，其中 \(\color{red}2\) 和 \(\color{blue}3\) 分别为 AR 和 MA 的阶数，对应
子代生成：以 \(0.5\) 的概率改变参数组；模型阶数服从泊松分布随机选取；参数更新通过加入高斯噪声，零均值，AIC 的倒数的一定比例作为方差。AIC 计算公式：
其中 \(L\) 是似然函数，评估了模型的拟合效果，如 MSE 等；\(k\) 是参数个数（惩罚项）。目标是最小化 AIC 的值。
8 蚁群算法 (Ant Colony Optimization, ACO)
自然界蚂蚁群体在寻找食物的过程中，通过一种被称为信息素 (pheromone) 的物质实现相互的间接通信，从而能够合作发现从蚁穴到食物源的最短路径。
蚁群算法
路径构建
对于每只蚂蚁 \(k\)，设蚂蚁 \(k\) 当前所在城市为 \(i\)，则其选择城市 \(j\) 作为下一个访问对象的概率为：
其中：
- 路径记忆向量 \(R^k\) 记录了 \(k\) 已经经过的城市构成的路径；
- \(J_k(i)\) 表示从城市 \(i\) 可以直接到达的、且又不在蚂蚁访问过的城市序列 \(R^k\) 中的城市集合；
- \(\tau(i,j)\) 表示边 \((i,j)\) 上的信息素量；
- \(\eta(i,j)\) 是一个启发式信息，通常由 \(\eta(i,j)=1/d_{ij}\) 直接计算；
- \(\alpha\) 和 \(\beta\) 为两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系：当 \(\alpha=0\) 时，为随机贪心算法，最近城市被选中的概率最大；当 \(\beta=0\) 时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，性能比较糟糕。
总之，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。
信息素更新
设 \(\tau(i,j)\) 表示边 \((i,j)\) 上的信息素量，每轮之后进行更新，更新规则为：
其中：
- \(m\) 是蚂蚁个数，\(\rho\) 是信息素的蒸发率（\(0<\rho<1\)）；
- \(\Delta\tau_k(i,j)\) 是本轮蚂蚁 \(k\) 在经过边 \((i,j)\) 时释放的信息素量，它等于本轮蚂蚁 \(k\) 构建路径长度的倒数（即第二个式子）；
- \(C_k\) 表示 \(R^k\) 中的路径总长度。
例题
例 用蚁群算法求解一个四城市（用 \(A,B,C,D\) 表示）的 TSP 问题，距离矩阵
\[W=(d_{ij})=\begin{bmatrix} \infty & 3 & 1 & 2 \\ 3 & \infty & 5 & 4 \\ 1 & 5 & \infty & 2 \\ 2 & 4 & 2 & \infty \end{bmatrix}. \]假设蚂蚁种群的规模 \(m=3\)，参数 \(\alpha=1,\beta=2,\rho=0.5\)。
-
初始化：从 \(A\) 出发，贪心得到路径 \(ACDBA\)，则 \(C^{nn}=1+2+4+3=10\)，初始化所有边上的信息素浓度 \(\tau_0=m/C^{nn}=0.3\)。为蚂蚁选择出发城市，例如 \(1\) 选择 \(A\)，\(2\) 选择 \(B\)，\(3\) 选择 \(D\)。
-
构造路径：为每只蚂蚁选择下个城市。
-
\(k=1\)， 位置 \(i=A\)，可以去的城市集合 \(J_1(i)=\{B,C,D\}\)，计算概率：
\[\tau_{AB}^\alpha\cdot\eta_{AB}^\beta=0.3^1\cdot(1/3)^2=0.033,\\ \tau_{AC}^\alpha\cdot\eta_{AC}^\beta=0.3^1\cdot(1/1)^2=0.3,\\ \tau_{AD}^\alpha\cdot\eta_{AD}^\beta=0.3^1\cdot(1/2)^2=0.075, \]加和得到 \(s=0.033+0.3+0.075=0.408\)，故
\[p_1(A,B)=0.033/0.408=0.081,\\ p_1(A,C)=0.3/0.408=0.74,\\ p_2(A,D)=0.075/0.408=0.18. \]用轮盘赌法则（蒙特卡洛方法）选择下个城市，假设产生的随机数为 \(q=U(0,1)=0.05\)，则选择城市 \(B\)。
同样地，为蚂蚁 2 和 3 选择下一城市，假设蚂蚁 2 选择城市 \(D\)，蚂蚁 3 选择城市 \(A\)。
-
\(k=1\)，位置 \(i=B\)，路径记忆向量 \(R^1=(AB)\)，可访问集合 \(J_1(i)=\{C,D\}\)，计算概率：
\[\tau_{BC}^\alpha\cdot\eta_{BC}^\beta=0.012,\quad\tau_{BD}^\alpha\cdot\eta_{BD}^\beta=0.019, \]从而
\[p_1(B,C)=0.012/(0.012+0.019)=0.39,\quad p_2(B,C)=0.019/(0.012+0.019)=0.61. \]用轮盘赌法则选择下个城市，假设产生的随机数为 \(q=U(0,1)=0.67\)，则选择城市 \(D\)。
同样地，为蚂蚁 2 和 3 选择下一城市，假设蚂蚁 2 选择城市 \(C\)，蚂蚁 3 选择城市 \(C\)。
-
只剩一个点没走过，故此时路径构造完毕，\(R^1=(ABDCA),R^2=(BDCAB),R^3=(DACBD)\)。
-
-
信息素更新：计算路径长度 \(C_1=3+4+2+1=10\)，同理 \(C_2=10\)，\(C_3=12\)。更新每条边上的信息素：
\[\begin{array}c \tau_{AB}=(1-\rho)\cdot\tau_{AB}+\sum_{k=1}^3\Delta\tau_{AB}^k=0.35,\\ \tau_{AC}=(1-\rho)\cdot\tau_{AC}+\sum_{k=1}^3\Delta\tau_{AC}^k=0.16,\\ \cdots\cdots. \end{array} \] -
结束：若满足条件，则输出全局最优结果并结束程序；否则，转向步骤 2.1 继续执行。
改进 1：精华蚂蚁搜索 (elite ant system, EAS)
增加了对至今最优路径的强化。
其中 \(T_b\) 为至今最优路径。
改进 2：基于排列的蚂蚁系统 (rank-based ant system, AS-rank)
给蚂蚁要释放的信息素大小加上一个权值，进一步加大各边信息素量的差异，以指导搜索。
具体来说，在每一轮所有蚂蚁构建完路径后，将它们按照路径的长短进行排名，只有生成了至今最优路径的蚂蚁和排名在前 \(\omega-1\) 的蚂蚁才被允许释放信息素，蚂蚁在边 \((i,j)\) 上释放的信息素的权值由蚂蚁的排名决定。
改进 3：最大最小蚂蚁系统 (min-max ant system, MMAS)
规则：
- 只允许本次迭代的迭代最优蚂蚁，或者至今最优蚂蚁释放信息素，二者交替使用。
- 信息素量被限制在一个区间 \([\tau_{\min},\tau_{\max}]\) 内。
当信息素浓度被限制在一个范围内以后，\(p_k(i,j)\) 也将被限制在一个区间内。有效避免了陷入停滞状态。 - \(\tau_0=\tau_{\max}\)，并伴随较小的蒸发率 \(\rho\)。
增强在初始阶段的探索能力，有助于蚂蚁「视野开阔地」进行全局搜索。随后逐渐缩小搜索范围。 - 每当系统进入停滞状态，所有边上的信息素量都会被重新初始化。
通过对信息素量的统计，或是观察算法在指定次数的迭代内至今最优路径有无被更新，来判断算法是否停滞。
蚁群系统 (ant colony system)
算法流程
- 初始化：设置每条路径上的初始信息素量 \(\tau_0\)。
- 迭代循环：
- 为每只蚂蚁随机选择出发城市。
- 逐个城市构建路径：
- 根据状态转移规则选择下一个城市。
- 执行信息素局部更新规则（ACS 特有）。
- 完成一轮后，执行信息素全局更新规则。
- 结束判定：满足停止条件则输出最优路径，否则继续迭代。
状态转移规则：伪随机比例规则
ACS 使用此规则来平衡开发 (Exploitation) 和 探索 (Exploration)。
蚂蚁选择下一个节点 \(j\) 的公式为：
其中：
- 开发 (\(q \leq q_0\))：直接选择信息素与启发式信息乘积最大的路径。
- 偏向探索 (\(q > q_0\))：按概率（轮盘赌）选择路径，增加发现新路径的可能性。
- \(q_0\)：调节因子，控制算法是集中于当前最优路径附近还是探索其他区域。
信息素更新规则
-
全局更新 (Global Update)：为了强化搜索到的最优路径，只对全局最优路径进行信息素增强。
\[\tau(i, j) = (1 - \rho) \cdot \tau(i, j) + \rho \cdot \Delta \tau_b(i, j), \quad \forall(i, j) \in T_b. \]其中：
- \(\Delta \tau_b(i, j) = 1/C_b\)（\(C_b\) 为最优路径长度）。
- 区别：AS 更新所有边，而 ACS 只更新属于“至今最优路径”的边。
-
局部更新 (Local Update)：蚂蚁每经过一条边，立即对其进行更新：
\[\tau(i, j) = (1 - \xi) \cdot \tau(i, j) + \xi \cdot \tau_0. \]- 目的：减小已走过路径的信息素浓度，增加其他未选路径的吸引力。
- 作用：增强探索能力，有效避免算法陷入停滞或局部最优。
关键参数设置建议
| 参数 | 定义 | ACS 参考设置 |
|---|---|---|
| \(m\) | 蚂蚁数目 | 通常取 \(10\) 左右较为合适 |
| \(\alpha, \beta\) | 信息素与启发式信息权重 | \(\alpha=1, \beta=2 \sim 5\) |
| \(\rho\) | 信息素挥发因子 | \(\rho=0.1\) |
| \(\tau_0\) | 初始信息素量 | \(\tau_0 = 1/(n \cdot C^{nn})\) （\(n\) 为城市数） |
| \(\xi\) | 局部挥发因子 | \(\xi=0.1\) |
| \(q_0\) | 伪随机因子 | \(q_0=0.1\) |
总结： ACS 通过局部更新“劝阻”蚂蚁走重复的路，通过全局更新“奖励”最优路径，并利用 \(q_0\) 灵活控制搜索重心，使其在求解复杂组合优化问题（如 TSP）时比传统 AS 性能更强。
9 粒子群算法 (Particle Swarm Optimization, PSO)
粒子群算法
粒子群算法是一种模拟自然界生物活动的随机搜索算法，通过群体中的协作与信息共享，寻找到问题的全局最优解。
- 鸟群 = 空间中一组有效解。
- 飞行速度 = 解的速度向量。
- 所在位置 = 解的位置向量。
- 找到食物 = 找到全局最优解。
基本原理
粒子通过不断更新自己的速度和位置来寻找最优解：
-
速度更新公式：对于粒子 \(i\)，设问题的规模为 \(D\) 维，则维护两个向量：速度向量 \(\boldsymbol v_i=[v_i^1,v_i^2,\cdots,v_i^D]\) 和位置向量 \(\boldsymbol x_i=[x_i^1,x_i^2,\cdots,x_i^D]\)。对于维数 \(d=1,2,\cdots,D\)：
\[v_i^d = \omega \cdot v_i^d + c_1 \cdot r_1^d \cdot (pBest_i^d - x_i^d) + c_2 \cdot r_2^d \cdot (gBest^d - x_i^d), \]其中：
- \(\omega\)：惯性权重，平衡探索和开发能力。
- \(c_1, c_2\)：加速系数（个体学习因子和社会学习因子）。
- \(r_1, r_2\)：\([0, 1]\) 之间的随机数。
- \(pBest_i\)：第 \(i\) 个粒子搜索到的历史最优位置。
- \(gBest\)：整个群体搜索到的全局最优位置。
-
位置更新公式：
\[x_i^d = x_i^d + v_i^d. \]
算法流程
- 初始化：随机生成粒子的初始速度和位置，并将当前位置设为个体的 \(pBest\)，群体中最优者设为 \(gBest\)。
- 评价：计算每个粒子的适应度函数值。
- 更新 \(pBest\)：如果当前适应度值优于历史最优值，则更新该粒子的 \(pBest\)。
- 更新 \(gBest\)：如果某个粒子的 \(pBest\) 优于全局最优值，则更新 \(gBest\)。
- 更新速度与位置：根据公式更新所有粒子的状态。
- 终止条件：检查是否达到最大迭代次数或误差要求，若未达到则返回步骤 2。
参数设置
-
种群规模 \(N\)：一般取 \(20\) 到 \(40\)，较难问题可取 \(100\) 到 \(200\)。
-
惯性权重 \(\omega\)：常采用从 \(0.9\) 线性递减到 \(0.4\) 的策略，也可以采用模糊控制的方式设定，或者在 \([0.5,1.0]\) 之间随机取值。
-
加速系数 \(c_1, c_2\)：通常均设为 \(2.0\)，使个体认知和社会影响同等重要。
-
最大速度 \(V_{max}\)：限制粒子飞行距离，防止搜索越界，通常取搜索空间的 \(10\%\) 到 \(20\%\)。
-
压缩因子 \(\chi\)：用于保证算法的有效收敛（Clerc 提出取值 \(0.729\)，同时 \(c_1,c_2\) 设为 \(2.05\)）。
\[v_i^d = \chi\cdot [ v_i^d + c_1\cdot r_1\cdot (pBest_i^d - x_i^d) + c_2\cdot r_2\cdot (gBest^d - x_i^d) ]. \]
例题
例 已知函数 \(y=f(x_1,x_2)=x_1^2+x_2^2\)，其中 \(-10\le x_1,x_2\le10\)。用粒子群优化算法求解 \(y\) 的最小值。
改进与拓扑结构
- 全局 PSO (GPSO)：所有粒子向全局最优学习，收敛快，但易陷入局部最优。
- 局部 PSO (LPSO)：粒子只向邻居学习，具有更好的多样性，一般不容易落入局部最优。
- 常见拓扑结构：星型、环型、齿型、冯·诺依曼结构。
- 邻域较小的拓扑结构在处理复杂的、多峰值的问题上具有优势，例如环型结构的 LPSO；
- 随着邻域的扩大，算法收敛速度加快，这对简单的、单峰值的问题非常有利，例如 GPSO。
- 更新方式：
- 同步更新：每代所有粒子更新完后统一评估。
- 异步更新：每一个粒子每更新一次位置立即评估并更新 \(gBest\)，信息传播更快。
算法特点与应用
- 特点：没有遗传算法的选择、交叉、变异等复杂步骤，效率更高，实现简单。
- 应用领域：优化与设计、调度与规划、机器学习训练、数据挖掘、生物医学等。
10 免疫算法 (Immune Algorithm)
主要会议：International Conference on Artificial Immune Systems, ICARIS.
免疫算法简介
免疫算法是模仿生物免疫系统（抗原识别、细胞分化、记忆、自我调节等功能）而设计的一种随机搜索优化算法。
| 免疫算法 | 遗传算法 | 概念 |
|---|---|---|
| 抗原 | 种群环境 | 要求解的问题 |
| 抗体 | 个体（染色体） | 可行解 |
| 适应度 | 适应度 | 目标函数值 |
| 细胞活化（免疫选择和亲和度成熟） | 选择、交叉、变异 | 拓展可行解多样性、保留优秀解 |
| 抗体克隆 | 个体繁殖 | 可行解的复制 |
| 抗体浓度 | 类似于种群大小 | 特定可行解的分布密度 |
| 亲和度 | / | 可行解之间的相似度 |
核心参数与定义
- 亲和力 (\(ax_v\))：表示抗体与抗原的结合程度（解的优劣）。
- 抗体浓度 (\(c_v\))：特定可行解在群体中的分布密度。
- 期望值 (\(e_v\))：综合考虑亲和力和浓度，用于决定个体的存活概率。算法倾向于保留高亲和力且低浓度的个体，以保持群体多样性。
- 记忆细胞：保存历代最优的抗体，若新抗体更优则进行替换。
算法流程
算法主要包含以下步骤：
-
识别抗原：明确目标函数和约束条件。
-
生成初始抗体：随机生成 \(N\) 个编码串，每个编码串含有 \(M\) 个编码（称为基因），编码的取值空间大小为 \(K\)。
-
计算亲和力：
-
抗体 \(v\) 与抗原亲和力：\(ax_v = \dfrac{1}{1 + opt_v}\)，其中 \(opt_v\) 为结合强度，可以理解为与最优解的相似程度。
-
抗体 \(v\) 与抗体 \(w\) 亲和力：\(ay_{v,w}=\dfrac1{1+E(2)}\)，其中 \(E(2)\) 是大小为 \(N=2\) 的抗体集合 \(\{v,w\}\) 的平均信息熵。计算方式：
- \(N\) 个抗体，每个抗体 \(M\) 个基因，第 \(j\) 个基因（共有 \(K\) 种取值）的信息熵为\[E_j(N)=\sum_{i=1}^N-p_{ij}\log_Kp_{ij},\quad E(N)=\frac1M\sum_{j=1}^ME_j(N). \]其中 \(p_{ij}\) 为第 \(i\) 个串的基因 \(j\)（第 \(j\) 位）在所有串中出现的概率（频率）。
- \(N\) 个抗体，每个抗体 \(M\) 个基因，第 \(j\) 个基因（共有 \(K\) 种取值）的信息熵为
-
-
记忆细胞分化：将高亲和力抗体存入记忆库。由于记忆细胞数目有限，因此新抗体将替代记忆细胞中和它有最大亲和力的抗体。
-
促进与抑制：消除低期望值的抗体，促进高亲和度、低密度的个体，抑制相似抗体，避免过早收敛。抗体 \(v\) 的期望：
\[e_v = \frac{ax_v}{c_v},\quad\text{其中抗体浓度 } c_v=-\frac{q_v}N. \]其中 \(q_k\) 表示和抗体 \(k\) 有较大亲和力的抗体。
-
产生新抗体：利用遗传算子（选择、交叉、变异），通常配合轮盘赌方法。
-
结束条件：判断是否达到满足要求的解或最大迭代次数。
一般的免疫算法中，求亲和度也可以用距离公式，常见的包括以下几种（\(ab_v\) 为抗体 \(v\)，\(ag\) 为抗原）：
- Euclidean 距离：\(D = \sqrt{\sum_{i=1}^M (ab_v^i - ag^i)^2}\)；
- Manhattan 距离：\(D = \sqrt{\sum_{i=1}^M |ab_v^i - ag^i|}\)；
- Hamming 距离：不同位的个数，即 \(D=\sum_{i=1}^M\delta_i\)，其中 \(\delta_i=\begin{cases}1,&\text{if }ab_v^i=a_g^i,\\0,&\text{otherwise}.\end{cases}\)
免疫遗传算法 (IGA)
免疫遗传算法在标准遗传算法的基础上增加了两个关键环节：
- 注射疫苗：引入先验知识，提高搜索效率。
- 免疫选择：通过免疫检测防止群体退化。
11 模拟退火与禁忌搜索
模拟退火 (Simulated Annealing, SA)
模拟退火算法采用类似于物理退火的过程，先在一个高温状态下（相当于算法随机搜索），然后逐渐退火，在每个温度下（相当于算法的每一次状态转移）徐徐冷却（相当于算法局部搜索），最终达到物理基态（相当于算法找到最优解）。
算法流程
其中：
- \(T\)：温度；
- \(k\)：迭代轮次；
- 解的能量 \(E\)：即要最小化的函数值。
例题
例 已知背包的装载量为 \(c=8\)，现有 \(n=5\) 个物品，它们的重量和价值分别是 \((2,3,5,1,4)\) 和 \((2,5,8,3,6)\)。试使用模拟退火算法求解该背包问题，写出关键的步骤。
用二进制串表示一个方案，第 \(i\) 位为 \(0/1\) 表示物品 \(i\) 选或不选。
禁忌搜索 (Tabu Search, TS)
禁忌搜索模仿了人类的记忆功能，在求解过程中，对已经搜索过的局部最优解进行标记，并且尽量避免重复相同的搜索（但不是完全隔绝），从而获得更广的搜索区间，有利于寻找到全局最优解。
相关概念
- 禁忌表 (Tabu List, TL)：用来存放（记忆）禁忌对象的表，是禁忌搜索得以进行的前提。禁忌表本身是有容量限制的。
- 禁忌对象 (Tabu Object, TO)：禁忌表中被禁的变化元素，根据具体问题制定选择规则。如在 TSP 问题中可以将交换的城市作为禁忌对象，也可以将总路径长度作为禁忌对象。
- 禁忌期限 (Tabu Tenure, TT)：也叫禁忌长度，指的是禁忌对象不能被选取的周期。禁忌期限过短容易出现循环，跳不出局部最优，长度过长会造成计算时间过长。
- 渴望准则 (Aspiration Criteria, AC)：也称为特赦规则。当所有的对象都被禁忌之后，可以让其中性能最好的解禁，或者当某个对象解禁会带来目标值的很大改进时，也可以使用特赦规则。
算法流程
例题
例 四城市 TSP 问题，城市设为 \(a,b,c,d\)。邻接矩阵
\[D=(d_{ij})=\begin{bmatrix} 0 & 1 & 0.5 & 1 \\ 1 & 0 & 1 & 1 \\ 1.5 & 5 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}. \]请分析使用禁忌搜索算法求解该问题的前面三代的过程与主要步骤。
为方便起见，假设邻域映射（生成新解的方式）定义为两个城市位置对换，而始点和终点城市都是 \(a\)。