智能算法

方法与覆盖范围

这些方法的共同点是：把问题统一成（可带约束的）最优化任务，在“目标函数可能不可导、变量可能离散/组合、搜索空间多峰/非凸、模型是黑盒”的场景下，依赖随机性与启发式规则进行近似全局搜索，而不是依赖解析解或梯度。

从学术上，它们通常被归入“元启发式（metaheuristics）”。你可以把它们理解为：围绕“如何产生候选解 + 如何接受/保留候选解”的一套可复用框架，把大量不同工程/组合问题映射到同一类搜索过程里。

遗传算法

它到底是什么
遗传算法是典型的“群体演化”随机优化：维护一组候选解（种群），让高适应度个体更可能被保留/繁殖，并通过交叉与变异产生新个体，使种群在代际更新中逐步逼近高质量区域。其历史性专著被视为遗传算法与更广义遗传/进化计算思想的重要起点之一。

一般把问题写成

$$\underset{x\in \Omega }{\min }f(x)(\text{或 }\max f)$$

GA 的关键不是“从一个点沿梯度走”，而是：并行维护多个候选解 + 用概率规则重分配搜索资源。

适合什么问题
更“经典”的适配画像是：

1. 变量天然是编码串（0/1 选择、排列、分段拼接等）
2. 目标函数不可导/不连续/噪声大
3. 多峰、强非凸、局部最优多
4. 约束导致可行域很“碎”

核心对象与机制

• 个体/染色体：一个候选解的编码表示（可二进制、实数、排列等）
• 种群：同时搜索的候选解集合
• 适应度：由目标函数变换得到的“好坏分数”，用于选择压力
• 三个遗传操作：选择（selection）—交叉（crossover）—变异（mutation）。面向具体问题时，“表示/编码—交叉—变异”必须兼容，否则会大量产生非法解或破坏结构。

最常见失败模式

1. 早熟收敛：强选择压力 + 低多样性使种群很快同质化，后续交叉相当于“近亲繁殖”，搜索停滞。
2. 编码不匹配：例如 TSP 属于排列结构，若用不保持排列合法性的交叉/变异，往往产生不可行路径；因此 TSP 上发展出专门表示与算子。
3. 适应度/惩罚设计不当：约束优化中，惩罚项过强会把搜索“锁死”，过弱则长期在不可行域游走。

约束怎么处理（通用做法）
GA 处理约束最常见仍是惩罚函数、修复算子、可行性优先/分层比较等套路；这类方法在进化算法约束处理综述中被系统总结。

两个经典应用

• 作业车间调度（Job-Shop Scheduling）：GA 在 1980s 就被用于典型 NP-hard 调度，核心是把“工序顺序/机器分配”编码成染色体，并通过选择与重组搜索低完工期/低拖期方案。
• 旅行商问题（TSP）：TSP 是 GA 的“经典试验场”之一，但也恰恰展示了“表示/算子必须尊重排列结构”的重要性；相关综述系统讨论了表示方式与交叉、变异算子谱系。

一个简单例子：用 GA 最小化 $f(x)=x^2$
目标：

$$\underset{x\in [-5,5]}{\min }{x}^2$$

一种最直观的教学版实现是二进制编码（也可直接实数编码）：

1. 用长度 $L$ 的二进制串表示整数 $z\in \{0,\dots ,2^L-1\}$，再线性映射到 $[-5,5]$：

$$x=-5+\frac{10z}{2^L-1}$$

2. 初始化种群：随机生成 $N$ 个二进制串。
3. 适应度：因是最小化，可设

$$\text{fitness}(x)=\frac{1}{1+f(x)}=\frac{1}{1+x^2}$$

4. 选择：按适应度概率或锦标赛选择父代（适应度越高越容易被选中）。
5. 交叉：如单点交叉，把两父代的部分比特交换，产生子代。
6. 变异：以小概率翻转某些比特，维持多样性并避免早熟。
7. 形成新一代并迭代。最终，种群会逐步集中到 $x\approx 0$ 附近（全局最优）。

这类玩具例子真正想让你看到的是：GA 的“数学核心”不是 $x^2$ 本身，而是**“编码—适应度—选择压力—重组—扰动”**这条链条是否能在你的问题上保留结构并累积改进。

模拟退火

它到底是什么
模拟退火（SA）把优化视为“在能量地形上随机游走并逐渐降温”。其关键是 Metropolis 接受准则：若新解更好则接受；若更差，也以一定概率接受，从而有机会跳出局部最优。经典论文明确给出：当代价变化 $\Delta E>0$ 时，以

$$P(\Delta E)=\exp (-\Delta E/(k_{B}T))$$

的概率接受劣解。

在优化语境里通常把 $E$ 直接替换为目标/代价函数 $f$，把 $T$ 当作控制参数（温度），形成“先高温充分探索、后低温精细开发”的过程。

适合什么问题
SA 的“甜点区”是：你能定义一个自然的邻域操作（从当前解做小改动得到新解），但局部最优太多；同时你更在意实现简单与稳健性，而不是超快收敛。

核心对象与机制

• 状态 $x$：当前候选解。
• 邻域 $N(x)$：从 $x$ 通过某种“扰动/交换/移动”得到的候选集。
• 温度 $T$ 与降温表（cooling schedule）：温度越高越容易接受劣解；温度下降后逐步趋向贪心。经典理论工作讨论了“收敛到全局最优所需的降温条件/必要充分条件”这类结果，反映 SA 对降温策略高度敏感。

最常见失败模式

1. 降温过快：很快退化成普通局部搜索，卡在局部最优。
2. 降温过慢：理论上更“稳”，但计算量爆炸，工程上不可承受。
3. 邻域设计不合理：邻域太小会走不出去，太大则“像随机重启”，难以细化；这在组合问题（如 TSP、排布）里尤其直观。

约束怎么处理
常见做法仍是：在邻域生成时强制可行（只产生可行解），或在代价函数里加入惩罚项；这与更广义进化/元启发式约束处理综述中的分类一致。

两个经典应用

• 旅行商问题（TSP）：SA 很早就被用于大规模 TSP 近似求解，并且成为检验全局跳出能力的典型测试场景；TSP 的邻域（2-opt/交换）非常适配 SA 的“微扰 + 接受准则”。
• VLSI 布局与布线（placement/routing）：在芯片物理设计中，模拟退火被系统化用于布局与全局布线，专著级别总结直接以此为主题，体现其“复杂代价函数 + 巨大组合空间”的强适配性。

一个简单例子：用 SA 最小化一元多峰函数 取一个常见教学用目标：

$$f(x)=x^2+10\sin x,x\in [0,10]$$

它有多处局部起伏，便于展示“接受劣解”。SA 步骤（教学版）：

1. 选初值 $x_0=7.0$，设初温 $T_0=1.0$。
2. 邻域：$x^{\prime }=x+ϵ$，其中 $ϵ\sim \text{Unif}(-0.5,0.5)$，并截断回 $[0,10]$。
3. 计算 $\Delta =f(x^{\prime })-f(x)$。若 $\Delta \le 0$ 则接受；若 $\Delta >0$，以概率 $\exp (-\Delta /T)$ 接受。
4. 降温：例如 $T_{k+1}=\alpha T_k$（几何降温），$\alpha \in (0,1)$；在每个温度下重复若干步使系统“近似平衡”。

你在纸上只要算一次“劣解被接受”的数值就够：比如某步 $\Delta =0.2$、$T=0.5$，则接受概率 $e^{-0.4}\approx 0.6703$，这就是 SA 跳出局部盆地的核心机制。

粒子群优化与差分进化

粒子群优化

它到底是什么
PSO 是群体搜索：每个粒子在连续空间中有位置与速度；速度更新由两类信息驱动：粒子自身历史最好位置（pbest）与群体最好位置（gbest 或局部最好），并带随机因子。经典早期论文给出“改变速度/再移动位置”的基本形式，并强调其参数化较少、实现简洁。

早期形式可以概括为（按维度 $d$）：

$$v_d\leftarrow v_d+c_1{r}_1(pbes{t}_d-x_d)+c_2{r}_2(gbes{t}_d-x_d),x_d\leftarrow x_d+v_d$$

其中 $r_1,r_2\sim U(0,1)$，文中以加速常数与随机项表达同一思想。

适合什么问题
PSO 更偏向连续参数优化：你能把决策变量直接表示成实数向量，目标函数可黑盒、可非凸；你希望快速得到一个“足够好”的近似解。

最常见失败模式

1. 群体塌缩/早熟：粒子过快聚到某个区域，后续速度趋零，探索能力丢失。
2. 参数不稳导致爆炸或振荡：速度更新本质上是动力系统，稳定性分析与参数选择研究显示参数会显著改变收敛/发散倾向。

约束怎么处理
工程上常见：越界投影/反弹、罚函数、可行性规则等；整体分类与 evolutionary/metaheuristic 约束处理综述一致。

两个经典应用

• 神经网络权重训练：早期论文直接讨论了用 PSO 来训练神经网络连接权重，并报告其在若干数据集上的可行性与表现。
• 电力系统经济调度（Economic Dispatch）：在非线性、非凸约束下的机组出力分配中，PSO 被大量用于求近似最优调度方案，形成了较成熟的应用谱系与综述/回顾。

一个简单例子：用 PSO 最小化 $f(x)=(x-3{)}^2$（一维）
设 3 个粒子，初始化：

• 粒子 1：$x=0$，$v=0.5$
• 粒子 2：$x=6$，$v=-0.3$
• 粒子 3：$x=4$，$v=0.1$

此时 $pbest$ 初始等于各自当前位置，$gbest$ 为使 $f$ 最小的粒子位置（这里是 $x=4$，因为 $f(4)=1$ 最小）。

取 $c_1=c_2=2$（早期论文常用“2×rand()”形式表达），随机数例如 $r_1=0.4,r_2=0.7$。对粒子 1：

$$v\leftarrow 0.5+2(0.4)(pbest-x)+2(0.7)(gbest-x)=0.5+0+2(0.7)(4-0)=0.5+5.6=6.1$$ $$x\leftarrow 0+6.1=6.1$$

这一步会“飞过”最优点 $x=3$，随后若 $gbest$ 更新、粒子会被拉回并逐步收敛；这种“过冲 + 拉回”的行为在早期论文讨论中就是 PSO 能探索未知区域的重要原因之一。

差分进化

它到底是什么
DE 也是群体进化算法，但其变异不是“随机小扰动”，而是利用个体差向量构造新候选：把两个个体的差 $(x_{r2}-x_{r3})$ 乘以缩放因子 $F$，加到第三个个体上得到变异向量；再与目标向量按概率交叉，最后用贪心选择保留更优者。原始论文明确给出：

• 变异（以 $DE/rand/1/bin$ 为例）：$v_{i,G+1}=x_{r1,G}+F(x_{r2,G}-x_{r3,G})$，且 $F\in [0,2]$。
• 交叉：用交叉率 $CR\in [0,1]$ 决定每一维来自 $v$ 还是 $x_i$，并保证至少一维来自 $v$。
• 选择：若试验向量更优则替换目标向量。

适合什么问题
DE 被广泛视为连续空间全局优化的强基线：对不可导、非线性、多峰函数具有稳健性，且“控制参数少、易实现”。

最常见失败模式

1. 参数敏感：$F$、$CR$、种群规模 $NP$ 会显著影响探索/开发平衡；因此出现了大量自适应/变体研究。
2. 高维退化：维度升高时差向量的有效信息可能变“稀”，需要更大种群或策略改造，否则会慢或不稳。

约束怎么处理
同样常用：罚函数、可行性规则、越界修复/投影；并可与“先生成—再修复”的流程结合。

两个经典应用

• 电磁/天线综合与设计优化：天线几何/馈电参数往往形成高成本仿真黑盒，DE 及其代理模型辅助版本在该领域非常常见。
• 系统辨识/参数估计：把动力学/结构系统参数估计写成非线性多峰优化，DE 能在噪声与有限观测下做鲁棒估计，形成稳定应用路线。

一个简单例子：用 DE 最小化 $f(x)=(x-1{)}^2$（一维）
设种群规模 $NP=4$，当前代个体：

$$x_1=3,x_2=0,x_3=-2,x_4=1.5$$

对目标个体 $x_1$，随机选 $r1=2,r2=4,r3=3$，取 $F=0.5$：

$$v=x_{r1}+F(x_{r2}-x_{r3})=0+0.5(1.5-(-2))=1.75$$

交叉：一维情形下试验向量就是 $u=v$（或以概率决定取 $v$ 还是 $x_1$，但“至少一维来自 $v$”使一维必来自 $v$）。
选择：比较 $f(1.75)=0.5625$ 与 $f(3)=4$，保留更优的 1.75 替换 $x_1$。

这一步清晰展示了 DE 的“差分驱动”：步长方向来自群体差异而不是固定分布的小扰动。

禁忌搜索与蚁群算法

禁忌搜索

它到底是什么
TS 属于“增强型局部搜索/轨迹法”：每一步从邻域里挑当前最优/最有希望的移动，但用短期记忆（tabu list / tabu conditions）把某些移动暂时禁止，以避免在局部最优附近反复循环；同时设置“特赦准则（aspiration criteria）”允许在特殊情况下破禁（例如能产生当前最佳解）。经典论文给出简单 TS 的结构化描述，并强调其“通过记忆机制实现约束与引导”的本质。

一个非常核心、也非常工程化的观点是：TS 往往不执着于“只走下降步”，而是持续走“当前允许的最好步”，并用禁忌机制控制回退与循环。

适合什么问题
TS 的强项是组合优化：你能明确定义邻域（交换、插入、翻转等），并且希望在很有限的计算资源下持续产生改进解。

最常见失败模式

1. 禁忌期限设置不当（tabu tenure）：太短会循环，太长会抑制必要移动，搜索变僵。
2. 邻域太弱：若邻域结构无法跨越关键结构障碍，即便有禁忌也只是“更聪明地局部徘徊”。

约束怎么处理
TS 可以把约束内化为：只允许可行移动；或允许临时不可行但在代价函数中惩罚（经典 TS 论文也明确提到把 $X$ 取为可行集的超集、用惩罚代价引导回可行域）。

两个经典应用

• 作业车间调度（Job-Shop）：TS 在调度领域形成了非常强的经典结果，例如快速禁忌算法成为该类问题的代表性方法之一。
• 车辆路径规划（VRP）：TABUROUTE 这类工作把 TS 系统化用于容量/里程约束下的车辆路径规划，并允许不可行解在搜索中出现以增强探索。

一个简单例子：用 TS 解 4 城市 TSP（演示禁忌的意义）
设城市集合 $\{A,B,C,D\}$，距离矩阵略。用路径表示解，如 $A\to B\to C\to D\to A$。邻域操作：交换路径中的两座城市（swap）。

• 初始解 $x_0=A-B-C-D-A$。
• 在邻域里枚举 swap 得到候选，比如 swap(B,C) 得 $A-C-B-D-A$，计算长度。
• 选择“当前允许的最好移动”，即便它可能略变差也可以走（这与 SA 的“概率接受劣解”不同，TS 更常见是“规则性地允许非改进走法”）。
• 将刚做过的 swap（或其逆操作）记入 tabu list，持续 $t$ 步禁止，从而避免立即 swap 回去导致两步循环。
• 若某个 tabu 移动能产生迄今最优解，则用 aspiration 放行。

你需要抓住的要点只有一个：TS 把“避免来回折返”显式编码进规则里，这在组合空间里往往比“纯随机扰动”更高效。

蚁群算法

它到底是什么
ACO 把解的构造过程视为“在图上逐步选组件（边/节点/分配项）”。每只人工蚂蚁按概率选择下一步，概率由两类信息共同决定：信息素（历史经验）与启发式信息（如距离的倒数）。经典 TSP 论文给出了选择概率分布，并说明信息素通过局部/全局更新改变，从而形成正反馈与蒸发/抑制机制。

在 TSP 语境中，其转移概率可写成（用论文符号 $\tau ,\eta ,\beta$ 表达）：

$$p_k(r,s)=\frac{\tau (r,s)[\eta (r,s){]}^{\beta }}{{\sum }_{u\in M_k}\tau (r,u)[\eta (r,u){]}^{\beta }}$$

并辅以局部更新、全局更新：

$$\tau (r,s)\leftarrow (1-\alpha )\tau (r,s)+\alpha \Delta \tau (r,s)$$

其中 $\Delta \tau$ 与最短巡回长度成反比；局部更新还用 ${\tau }_0$ 抑制过强边被所有蚂蚁垄断。

适合什么问题
本质上，ACO 很适合“图上的构造型组合优化”：路径、路由、调度/分配等，因为你可以自然地把“部分解”看成“已走的路径/已选的组件”，并让信息素把“好结构”跨代累积。

最常见失败模式

1. 信息素停滞（stagnation）：早期某条路径信息素过强导致几乎所有蚂蚁走同一路，探索停止。局部更新/蒸发就是为缓解这一点。
2. 启发式权重不平衡：$\beta$（启发式权重）过大时退化成近似贪心；过小时缺乏局部引导、收敛变慢。

约束怎么处理
常见做法是：在构造过程中只允许满足约束的下一步（硬约束内化为可选集合），或对违反约束的边/组件施加惩罚，使其概率被压低；其思路与元启发式约束处理的“可行性优先/惩罚”框架一致。

两个经典应用

• 旅行商问题（TSP）：蚁群最著名的起家应用之一，经典论文以 TSP 为例完整给出了转移概率与信息素更新机制。
• 网络路由（Routing, AntNet 系列）：ACO 框架被用于分组网络的自适应路由，利用“探索蚂蚁”收集网络延迟等信息并更新路由偏好，是其最常被引用的工程应用方向之一。

一个简单例子：用 ACO 在 4 城市图上找短巡回（概念演示）
假设 4 城市完全图，启发式信息设为 $\eta (r,s)=\frac{1}{\text{dist}(r,s)}$。

1. 初始化所有边信息素 $\tau (r,s)={\tau }_0$。
2. 每只蚂蚁从随机起点出发，按上式概率选下一城市，直到形成巡回（构造解）。
3. 完成一轮后：对本轮最短巡回的边做“全局强化”（$\Delta \tau \propto 1/\text{tour length}$），并同时蒸发/局部更新抑制过度集中。

你可以把它看成：用概率方式做“带记忆的重复构造”，记忆由信息素实现。

人工蜂群与进化策略

人工蜂群

它到底是什么
ABC（Artificial Bee Colony）把候选解看成蜜源，蜂群分为雇佣蜂、观察蜂、侦察蜂等角色：雇佣蜂围绕当前蜜源做局部搜索，观察蜂在蜜源之间按质量分配搜索资源，侦察蜂负责随机探索以补充多样性。其代表性论文将其明确定位为“数值函数优化”的高效算法之一。

适合什么问题
ABC 通常用于连续黑盒函数优化，尤其在多峰、噪声或不可导问题上较常见；同时也被改造用于聚类、覆盖、组合等。

最常见失败模式

1. 局部开发不足或过强：若邻域扰动/选择压力设计不当，要么像随机搜索，要么过早围绕某个蜜源打转。
2. “limit”/侦察机制设置不当：侦察过频会破坏已积累的好结构，过少会导致停滞；相关工作常把它作为关键超参数讨论。

约束怎么处理
经典仍是惩罚、修复、可行性优先；ABC 也存在面向约束的专门变体与应用实践。

两个经典应用

• 数值函数优化（benchmark/连续优化）：ABC 的代表性论文就是以多种测试函数展示其在数值优化上的效率与竞争力。
• 数据聚类（Clustering）：将聚类中心/划分作为蜜源编码，利用蜂群机制在非凸目标下搜索较优聚类结果，是 ABC 常见的应用方向之一。

一个简单例子：用 ABC 最小化 $f(x)=(x-2{)}^2$
把每个蜜源看作一个标量 $x$。

1. 初始化若干蜜源 $x_i\sim U([-5,5])$。
2. 雇佣蜂局部扰动：从另一个蜜源 $x_k$ 借差异产生新候选（典型 ABC 用“随机系数 × 差分”构造邻域），若更优则替换。
3. 观察蜂按蜜源质量分配搜索次数（好的蜜源被更多追随）。
4. 若某蜜源长期不改进，触发侦察蜂随机重置该蜜源，恢复多样性。

直观结果：蜂群会在 $x\approx 2$ 附近聚集（全局最优）。

进化策略与 CMA-ES

它到底是什么
进化策略（ES）是进化计算的重要分支，面向实数参数优化，以“变异 + 选择”为核心，并逐步发展出自适应策略参数（步长、分布形状等）。综述性介绍明确指出 ES 的历史可追溯到 1960s–1970s 的工程优化背景。

CMA-ES（协方差矩阵自适应进化策略）把搜索视为在多元正态分布中采样：

$$x\sim \mathcal{N}(m,{\sigma }^{2}C)$$

并通过优秀样本更新均值 $m$，同时自适应更新协方差矩阵 $C$ 来学习变量间相关性，从而在非线性、非凸、病态尺度问题上保持强鲁棒性。其经典论文与后续教程系统解释了“去随机化、自适应、协方差学习”等关键机制。

适合什么问题
当你面对“连续黑盒 + 变量耦合强 + 尺度差异大 + 梯度不可用或不可靠”时，CMA-ES 常被认为是极有竞争力的基线之一。教程明确将其定位为面向非线性、非凸连续域优化的随机方法。

最常见失败模式

1. 维度很高时的计算代价：协方差矩阵更新带来 $O(n^2)$ 或更高的成本，高维会吃紧。
2. 预算极小的场景：当函数评估次数极少时，自适应学习不足，优势难充分体现。

约束怎么处理
常见工程实践：投影/修复、罚函数，或把约束通过变量变换内化；整体仍落在元启发式约束处理大框架里。

两个经典应用

• 工程连续参数优化（包含早期工程优化传统）：ES 的发展本身就与工程设计寻优紧密相关；后续综述与教材把 ES 作为工程黑盒优化的重要路线总结。
• 控制器参数整定/机器人控制中的黑盒调参：把控制增益整定视为黑盒优化任务，使用 CMA-ES（含重启策略等）进行实验驱动的参数校准，是近年来非常典型的落地方式之一。

一个简单例子：用 CMA-ES 最小化二维椭圆函数
取

$$f(x,y)=(x-1{)}^2+10(y+1{)}^2$$

它具有明显尺度差异（$y$ 方向更“陡”），适合说明“协方差/尺度自适应”的意义。

1. 初始化 $m_0=(0,0)$、步长 ${\sigma }_0>0$、$C_0=I$。
2. 每代从 $\mathcal{N}(m,{\sigma }^{2}C)$ 采样 $\lambda$ 个点，计算 $f$。
3. 选出最好的 $\mu$ 个样本做加权平均更新 $m$，并据样本分布更新 $C$（学习相关性与尺度）。

你应当得到的直觉是：如果变量之间存在相关性或尺度差异，CMA-ES 会把搜索分布从“圆形”逐步学成“倾斜的椭圆形”，沿着更有效的方向伸展。