极限优化

极限优化（EO）是一种优化启发式方法，其灵感来自统计物理学领域的自组织临界性的Bak-Sneppen模型。这种启发式方法最初是为了解决组合优化问题，如旅行推销员问题和自旋眼镜，尽管该技术已被证明可以在优化领域发挥作用。

自组织临界性（SOC）是一个统计物理学概念，用来描述一类以临界点为吸引子的动力系统。具体来说，这些是非平衡系统，通过变化和耗散的雪崩来演化，一直到系统的最高尺度。

该难题的另一个部分是关于计算复杂性的工作，特别是临界点已被证明存在于NP-complete问题中，在这些问题中，接近最优的解决方案被广泛分散，并被搜索空间中的障碍物隔开，导致局部搜索算法被卡住或受到严重阻碍。正是Bak和Sneppen的进化自组织临界点模型以及对组合优化问题中临界点的观察，导致了StefanBoettcher和AllonPercus对xxx优化的开发。EO技术被设计为一种用于组合优化问题的局部搜索算法。与遗传算法不同的是，EO演化出一个单一的解决方案，并对最差的部分进行局部修改，而遗传算法的工作对象是一群候选解决方案。这需要选择一个合适的表示方法，允许给单个解决方案的组成部分分配一个质量度量（健身）。这与蚁群优化和进化计算等整体方法不同，后者是根据对目标函数的集体评价，为解决方案的所有组成部分分配同等的适合度。该算法以一个初始解决方案初始化，该解决方案可以随机构建，也可以从其他搜索过程中获得。该技术是一种细粒度的搜索，表面上类似于爬坡（局部搜索）技术。更详细的检查显示了一些有趣的原则，这些原则可能具有适用性，甚至与更广泛的基于群体的方法（进化计算和人工免疫系统）有一些相似之处。这个算法背后的管理原则是通过有选择地去除低质量的组件，并用随机选择的组件取代它们来进行改进。

这显然与遗传算法不一致，遗传算法是典型的进化计算算法，它选择好的解决方案，试图制造更好的解决方案。这个简单的原则所产生的动力首先是一个强大的爬坡搜索行为，其次是一个类似于多次重启搜索的多样性机制。将整体解决方案的质量随时间（算法迭代）变化的图形化显示，在质量崩溃（雪崩）之后的改进期，非常类似于惩罚性平衡所描述的方式。正是这些崩溃或搜索空间中的戏剧性跳跃，使算法摆脱了局部优化，并将这种方法与其他局部搜索程序区分开来。尽管这种间断平衡行为可以被设计或硬编码，但应该强调的是这是该算法基本的负成分选择原则的一种突发效应。EO主要被应用于组合问题，如图形分割和旅行推销员问题，以及统计物理学中的问题，如自旋眼镜。

广义极值优化（GEO）被开发出来，用于操作位串，其中组件质量由位的xxx变化率决定，或位对整体解决方案质量的贡献。这项工作包括对标准函数优化问题以及工程问题领域的应用。另一个与EO类似的扩展是连续极值优化（CEO）。EO已被应用于图像栅格化，并在使用蚁群优化后作为局部搜索。EO已被用于识别复杂网络中的结构。EO已被用于多目标跟踪问题。最后，在研究用于控制选择的概率分布方面也做了一些工作。