极值优化（EO）是一种用于组合优化的元启发式算法，由Stefan Boettcher和Allon G. Percus于1999年提出。它受Bak-Snppen自组织临界模型的启发，该模型描述了自然界中的系统如何通过反复移除最不适应的组件而演化到临界状态。在优化中，EO通过从一组二元或取值变量构建候选解来解决问题，然后迭代选择局部适应度最差的变量并将其替换为随机值，从而通过有偏的极值过程探索解空间。
该算法以简单性著称，并且在不依赖梯度信息的情况下，能在困难问题上获得高质量解。它属于更广泛的进化计算方法类别，但与使用种群繁殖和交叉的遗传算法不同。相反，EO使用单一解，并通过幂律选择概率进行操作，从而在解空间中实现偶尔的大跳跃。这种随机行为有助于逃离局部最优，并且通常能找到接近最优的结果，尤其是在旅行商问题、图划分和自旋玻璃基态问题等问题上。
历史发展
该方法由Boiss和Percus于1999年首次提出，并以“极值优化：源自共同进化的方法”为题发表在期刊《物理评论快报》上。他们的工作动机是观察到自然界中的系统，如沙堆和生物生态系统，通过消除表现不佳的元素而自组织到临界状态。这导致了简单、基于突变的启发式方法的发展，与更复杂的、种群驱动的方法形成对比。早期实验表明，EO在大规模NP难问题上能够匹配或超越模拟退火的性能，从而在优化文献中确立了其地位。
自提出以来，EO已被扩展并应用于多个领域，包括二路图划分、图着色，以及最近在机器学习中的特征选择。变体提出了处理约束问题和通过自适应概率分布改善收敛性的方法。研究还将EO与自组织临界动力学联系起来，为其行为提供了理论依据。
核心算法与机制
基本EO算法的工作原理如下：
- 定义问题，其搜索空间由一组变量（或自旋）组成，每个变量具有赋值。
- 对每个变量，根据其对整体成本或适应度的贡献计算局部适应度值。
- 在每次迭代中，选择局部适应度最差（最低）的变量，称为极值变量。然后为其赋予一个新的随机值，该值可以从可能的赋值域中选择。
- 通常使用与幂律成比例的概率分布来选择要更新的变量，以避免仅选择最差变量而陷入困境。对于排名为r的变量（其中r=1为最差），典型的选择概率为p(r) ~ r^-τ，τ通常设置为约1的值。
- 每次更新后，重新计算受影响变量的局部适应度，并重复该过程，直到达到固定迭代次数或满足停止条件。
一个显著特点是EO不使用任何显式的局部搜索步骤或爬山法。相反，单一突变和tau参数提供了探索与利用之间的平衡。较小的τ导致更随机的变化，而较大的τ则将选择偏向于最差中的最佳，这在只有少数坏组件导致问题时可能有用。最终解的质量是运行期间观察到的最高局部适应度值，通常会被跟踪。
在计算系统中的应用
EO已应用于一系列优化挑战。在Artificial intelligence领域，它被用于进化神经网络拓扑和调整超参数，提供了基于梯度方法的替代方案。在Machine learning中，它被应用于特征选择，目标是从预测变量中选择最佳子集；EO表现良好，因为特征可以被视为组件，其局部适应度基于对验证准确率的贡献。
此外，EO常用于解决组合优化实例，如装箱问题、作业车间调度和纠错码的构造。它还用于并行和分布式系统的设计，例如，将任务分配给处理器以最小化完工时间。由于不依赖梯度信息，它可以应用于目标函数不连续或离散的问题。当应用于图二划分时，EO已被证明能产生出色的社区检测结果，与领先的图划分算法相匹配。
与其他元启发式算法的关系
EO与遗传算法和模拟退火有家族相似性，但使用不同的机制。遗传算法维护一个解种群并使用重组和突变；EO使用单一解。模拟退火通过随机扰动修改整个解，并根据温度接受变化；EO仅修改最差的组件，由局部适应度引导。关键区别在于，EO选择要修改的组件是基于排名（确定性或幂律随机），而不是基于整个解的目标函数值。
与自组织临界性（SOC）的理论联系意味着EO再现了自然系统中看到的幂律波动，这使其对多种景观类型具有鲁棒性。在经典基准（旅行商问题）上的比较中，EO与模拟退火具有竞争力，但通常需要更少的函数评估。实际上，对于邻域由组件适应度排名定义的问题，EO即使使用简单实现也能高效运行。
扩展与变体
研究已产生许多变体。最常见的是tau-EO，其中参数tau控制选择更高排名变量的概率。tau的值和幂律尾部的范围可以调整以改善一致性。另一种变体是概率爬山法，带有尾部引入的抖动。另一种方法共同进化处理具有交互组件的问题，其中基于共同适应突变多个变量。最近，该算法已与局部搜索启发式方法结合，产生混合EO，在EO发现阶段后进行额外微调。
在Deep learning应用中，一种EO形式已被用于自动调整模型架构，特别是在Neural network搜索中，尽管它已被更复杂的方法取代。EO不需要梯度，使其适用于梯度不可用或成本高昂的模型，例如不可微损失。它也适用于在强化学习问题中探索离散空间。
局限性与开放研究
EO的一个关键挑战是设置tau参数和幂律的值范围。选择不当的tau可能导致收敛性差甚至混乱。此外，由于它每次只修改一个变量，对于高度约束的问题或变量间存在依赖关系的问题，需要仔细形式化适应度以避免高计算成本。
开放研究集中在使EO更具适应性，例如动态估计tau或使用tau的退火调度。还有工作涉及更高级的变量随机值替换方法，以及在分布式环境中使用EO。
尽管EO的理论理解不如其他元启发式算法成熟，但它是组合优化和自然启发计算工具集中的重要概念，因为它易于实现且对多种困难问题具有鲁棒性。未来可能会看到更多与专门优化器的集成，以及对其幂律统计在实用调度和设计中的进一步研究。
关键研究者与影响
原始作者Stefan Boettke和All Percus（当时均在圣塔菲研究所）将SOC视角引入优化。后续其他团队的工作，包括Xerox Parc和Berkeley AI Research，扩展了该方法框架和分析。虽然它不在现代机器学习工具的前沿，但仍是自然启发启发式方法中的参考，并常被纳入进化计算课程材料中。
总之，极值优化提供了一种极简、非梯度、随机的框架，用于近似解决困难的组合问题，并且在理论研究和问题可分解为具有独立适应度值的组件的应用中，它作为概念和算法持续具有价值。
局限性与注意事项
对于实际使用，尝试者应注意该方法不保证全局最优性，某些问题可能需要调整选择概率分布。在适当设置下，它可以是一个简单而有效的优化工具。