优化理论

一、优化问题的基本概念

优化（Optimization） 指在给定约束条件下，寻找使目标函数达到最优（最小或最大）的决策变量值。

一般形式：

$$\begin{aligned} &\min_{x \in S} \; f(x) \\ &\text{s.t.}\quad g_i(x) \le 0,\; i=1,\dots,m \\ &\qquad\;\;\; h_j(x) = 0,\; j=1,\dots,p \end{aligned}$$

其中 $x=[x_1,\dots,x_n]^\top$ 为决策变量，$f(x)$ 为目标函数，$S$ 为可行域。

---

二、优化问题的分类

优化问题可从多个维度划分：

维度	主要类型	说明
① 目标数量	单目标、多目标	一个或多个需优化的目标
② 变量类型	连续、离散、混合	决策变量取值域
③ 约束条件	无约束、有约束	是否存在限制条件
④ 函数特性	凸/非凸、单/多模态	函数形态及极值结构
⑤ 动态性	静态、动态	问题是否随时间变化
⑥ 随机性	确定性、随机	是否含噪声或不确定性
⑦ 维度规模	低维、高维	变量数量与复杂度
⑧ 可导性	可微、黑箱	是否可求导

---

三、求解方法与运用原则

（一）数学规划（Mathematical Programming）

以数学分析为基础，利用凸性、导数或 KKT 条件等精确求解。

类型	特点	代表方法
线性规划	线性目标与约束	单纯形法、内点法
非线性规划	可微函数	梯度法、牛顿法
整数/混合整数规划	离散/混合变量	分支定界、割平面
动态规划	多阶段决策	贝尔曼方程
凸优化	任意局部最优即全局最优	内点法、投影梯度

优缺点：
✅ 理论严谨、结果精确；❌ 依赖可微/凸性与规则结构。

（二）进化计算（Evolutionary Computation）

以自然进化、群体智能或物理机制为启发，通过随机搜索近似全局最优。

类别	启发机制	代表算法
进化算法	生物进化	GA、ES、EP、DE
群体智能	群体协同	PSO、ACO、ABC
物理启发	物理过程	SA、FA
混合/自适应	组合与参数自调	CMA-ES、Memetic、BO+EC

优缺点：
✅ 不需梯度，适于非凸/离散/黑箱；❌ 随机性强、收敛速率依参数而异。

（三）比较与融合

对比项	数学规划	进化计算
搜索方式	确定性、梯度驱动	随机性、群体驱动
适用问题	凸、连续、可微	非凸、离散、黑箱
结果性质	精确解	近似解
典型优势	可证明的最优性	全局探索与鲁棒性

融合趋势（Hybrid）：用进化法找“好起点”，再以数学规划局部精修；或用代理模型/贝叶斯优化辅助昂贵评估。

---

四、搜索优化算法的一般流程（八步法）

适用于 GA/PSO/DE/SA/ACO 等通用“搜索—评价—记忆—迭代”范式。

步骤1：优化问题建模

完成三要素的数学表达，并明确可计算方式：

• 决策变量：$x \in \mathbb{R}^n$ 或 $x \in \mathbb{Z}^n$ 或混合。
• 目标函数：$f(x)$（或多目标 $F(x)=[f_1,\dots,f_k]$），给出数值评估路径（解析、仿真、实验）。
• 约束函数：$g_i(x)\le 0,\; h_j(x)=0$，确定可行性判定与惩罚/修复策略。
• 注意：若为黑箱/噪声评估，说明采样次数、复评估/方差估计与缓存复用策略。

步骤2：确定解的编／解码方法

将“数学解”与“算法内部表示”互相映射：

• 编码：实数向量、二进制串、排列、混合基因等。
• 解码：从表示还原到可评估的 $x$，必要时做可行化修复（投影、启发式纠偏）。
• 建议：选择闭合性强（算子作用后仍有效）、表达力足、便于邻域操作的表示。

步骤3：确定解的评价方法

定义适应度/质量评分与约束处理：

• 单目标：$\text{fitness}(x) = f(x)$ 或其单调变换（越小越好/越大越好统一）。
• 多目标：帕累托支配、拥挤距离、加权和或 $\epsilon$-约束等。
• 约束处理：罚函数 $F(x)=f(x)+\rho\cdot\text{violation}(x)$、可行性优先、分级排序、修复算子。
• 噪声：多次评估求均值/置信区间；使用方差自适应采样；启用评价记忆（见步骤4）。

步骤4：建立记忆信息的数据结构

存储搜索状态与知识，提升效率与稳定性：

• 历史最优：全局最优 $x^\ast$ 与其 $f(x^\ast)$；多目标存档（Pareto Archive）。
• 个体级记忆：PSO 的个体最优、禁忌搜索的禁忌表、SA 的当前解等。
• 多样性/重复检测：哈希集合、KD-Tree/LSH 近似查重。
• 评价缓存（Memoization）：键为编码或解码后 $x$ 的哈希，值为评估结果（含方差/时间戳）。

步骤5：生成初始解并评价，更新记忆

• 初始化：随机均匀采样、拉丁超立方、问题特定启发式、可行化构造。
• 首轮评价：计算适应度并写入缓存；对多目标填充分布良好的初始前沿。
• 更新记忆：刷新全局/个体最优、存档、统计量（均值、方差、协方差矩阵用于自适应算子）。

步骤6：为搜索算子选择作用对象

• 个体选择：锦标赛、轮盘赌、排序选择、基于等级/拥挤距离的选择。
• 邻域/交互选择：拓扑结构（全连通/环形/网格）、亲和度/相似度配对、精英与探索者分工。
• 目标导向：利用记忆信息（如档案、领导者集）决定被操作的解子集。

步骤7：运用搜索算子迭代生成新解，并评价与更新记忆

• 生成：交叉/变异（GA/DE）、速度与位置更新（PSO）、外加扰动（SA）、信息素更新（ACO）。
• 约束处理：产生后立即修复/投影，或在评价时采用罚函数。
• 自适应/自调参：如 CMA-ES 协方差学习、DE 的 $F$/$CR$ 调节、退火温度日程、学习率退火。
• 评价与写回：对新解进行（去重后）评估，更新缓存与记忆；维护多样性（拥挤距离/熵度量/重采样）。
• 生存选择：$(\mu+\lambda)$、$(\mu,\lambda)$、精英保留、年龄淘汰、档案裁剪等策略。

步骤8：终止判断与输出

• 判据：达到最大评估次数/代数；目标函数改进停滞；达到阈值；预算/时间上限。
• 输出：单目标输出当前最佳解 $x^\ast$ 与 $f(x^\ast)$；多目标输出近似帕累托前沿及代表解集。
• 可复现实验信息：随机种子、参数配置、评估次数、收敛曲线与档案。

---