极值优化（EO）

名称

极值优化（Extremal Optimization, EO）

分类

查看分类思维导图

极值优化是一种受自然启发的优化技术，属于计算智能与随机优化这一更广泛的研究范畴。它与模拟退火、遗传算法等优化方法具有密切关联。

• 计算智能
  • 随机优化
    • 自然启发算法
      • 极值优化

策略

极值优化受到复杂系统中“自组织临界性”概念的启发。该概念认为，系统会自然演化到一种临界状态，并呈现幂律分布特征。在 EO 中，优化过程并非直接围绕整体解质量展开，而是通过迭代地改进解中表现最差的组成部分来推动搜索。

解的表示

在 EO 中，一个解通常表示为若干组成部分的集合，每个组成部分都会对解的整体适应度或代价产生贡献。具体表示方式依赖于所求解问题的性质，例如可以采用二进制串、排列，或实值向量等形式。

适应度评估

EO 会对解中每个组成部分的适应度进行独立评估，从而识别出表现最差的部分。相较于对整个解的全局适应度进行统一评估的其他优化方法，这种局部适应度评估机制是 EO 的一个关键特征。

迭代改进

在每次迭代中，EO 选取表现最差的组成部分（或其中的一部分），并将其替换为新的随机生成值。通过持续替换适应度最低的部分，算法逐步推动解向更优状态演化。

接受准则

当新生成的解优于当前解时，算法接受该新解。一些 EO 变体还会引入类似模拟退火中的接受概率函数，从而以一定概率接受较差解，以帮助算法跳出局部最优。

过程

1. 初始化：
   1. 随机生成初始解，或利用问题相关启发式方法构造初始解。
   2. 评估解中各组成部分的适应度。
2. 重复执行，直到满足终止条件：
   1. 根据各组成部分的个体适应度，识别出表现最差的组成部分。
   2. 用新随机生成的值替换这些最差组成部分。
   3. 评估修改后解的适应度。
   4. 若新解优于当前解，则将其接受为当前解。
   5. 更新受影响组成部分的适应度值。
3. 返回搜索过程中找到的最优解。

数据结构

• 解（Solution）：表示一个候选解，通常为由若干组成部分构成的数组或向量。
• 组成部分适应度（Component Fitness）：用于存储解中各组成部分个体适应度值的数组或向量。

参数

• 种群规模（Population Size）：优化过程中维护的候选解数量（可选，因为 EO 通常作用于单个解）。
• 替换率（Replacement Rate）：每次迭代中被替换的最差组成部分的数量或比例。
• 终止条件（Termination Criteria）：用于停止优化过程的条件，例如最大迭代次数、目标适应度值或时间限制。

注意事项

优点

• 简洁性：与许多其他优化算法相比，EO 在概念上较为简单，也更易于实现。
• 灵活性：只要能够定义合适的解表示方式和适应度评估机制，EO 就可应用于多种优化问题。
• 局部搜索能力：EO 聚焦于改进表现最差的组成部分，因此能够实施有针对性的局部搜索，这在跳出局部最优方面可能较为有效。

缺点

• 参数敏感性：EO 的性能可能对参数选择较为敏感，例如替换率通常需要针对具体问题进行调节。
• 多样性不足：由于 EO 通常只围绕单个解进行搜索，因此可能缺乏像遗传算法这类群体算法所具有的种群多样性。
• 收敛速度：在适应度景观较为复杂的问题上，EO 的收敛速度可能慢于某些其他优化方法。

启发式建议

替换率

• 可从较低的替换率开始，例如每次仅替换单个最差组成部分，并在优化过程中逐步提高替换率，以平衡探索与开发。
• 对于组成部分数量较多的问题，可考虑按固定比例替换最差组成部分，而不是每次替换固定数量。

初始化

• 若具备问题相关先验知识，应优先利用这些知识生成更接近最优解的初始解，而非完全随机初始化。
• 若问题具有已知约束条件，应保证初始解满足约束，以避免将计算资源浪费在不可行解上。

适应度评估

• 若适应度评估代价较高，可考虑缓存各组成部分的适应度值，并仅在必要时（即组成部分发生修改后）重新计算。
• 对于组成部分数量较多的问题，可考虑采用近似适应度模型或代理模型，以降低评估成本。

终止条件

• 可结合多种终止条件，例如最大迭代次数与目标适应度值，以确保在找到满意解或进一步改进不太可能时停止优化过程。
• 可监测解适应度的改进速率；若该速率低于某一给定阈值，则可考虑终止优化，以表明算法已趋于收敛。

变异算子

• 可结合问题特定的变异算子，例如局部搜索启发式或专门设计的变异机制，以提高优化过程的效率与效果。
• 可尝试不同替换策略，例如不是用纯随机值替换最差组成部分，而是从特定概率分布中采样生成替换值。