Boettcher S, Percus A G
Physics Department, Emory University, Atlanta, Georgia 30322, USA.
Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Aug;64(2 Pt 2):026114. doi: 10.1103/PhysRevE.64.026114. Epub 2001 Jul 20.
Extremal optimization is a new general-purpose method for approximating solutions to hard optimization problems. We study the method in detail by way of the computationally hard (NP-hard) graph partitioning problem. We discuss the scaling behavior of extremal optimization, focusing on the convergence of the average run as a function of run time and system size. The method has a single free parameter, which we determine numerically and justify using a simple argument. On random graphs, our numerical results demonstrate that extremal optimization maintains consistent accuracy for increasing system sizes, with an approximation error decreasing over run time roughly as a power law t(-0.4). On geometrically structured graphs, the scaling of results from the average run suggests that these are far from optimal with large fluctuations between individual trials. But when only the best runs are considered, results consistent with theoretical arguments are recovered.
极值优化是一种用于逼近难解优化问题解的新型通用方法。我们通过计算上困难的（NP 难）图划分问题来详细研究该方法。我们讨论了极值优化的缩放行为，重点关注平均运行的收敛性与运行时间和系统规模的函数关系。该方法有一个自由参数，我们通过数值方法确定它，并使用一个简单的论据进行论证。在随机图上，我们的数值结果表明，对于不断增加的系统规模，极值优化保持一致的精度，近似误差随运行时间大致以幂律 t^(-0.4) 减小。在几何结构的图上，平均运行结果的缩放表明这些结果远非最优且各次试验之间波动很大。但当只考虑最佳运行时，就能得到与理论论据一致的结果。
