HRL Laboratories, LLC, 3011 Malibu Canyon Rd, Malibu, CA, 90265, USA.
Sci Rep. 2018 Feb 5;8(1):2358. doi: 10.1038/s41598-018-20275-7.
Self-organized criticality (SOC) is a phenomenon observed in certain complex systems of multiple interacting components, e.g., neural networks, forest fires, and power grids, that produce power-law distributed avalanche sizes. Here, we report the surprising result that the avalanches from an SOC process can be used to solve non-convex optimization problems. To generate avalanches, we use the Abelian sandpile model on a graph that mirrors the graph of the optimization problem. For optimization, we map the avalanche areas onto search patterns for optimization, while the SOC process receives no feedback from the optimization itself. The resulting method can be applied without parameter tuning to a wide range of optimization problems, as demonstrated on three problems: finding the ground-state of an Ising spin glass, graph coloring, and image segmentation. We find that SOC search is more efficient compared to other random search methods, including simulated annealing, and unlike annealing, it is parameter free, thereby eliminating the time-consuming requirement to tune an annealing temperature schedule.
自组织临界性（SOC）是在某些具有多个相互作用组件的复杂系统中观察到的一种现象，例如神经网络、森林火灾和电网，这些系统会产生幂律分布的雪崩大小。在这里，我们报告了一个令人惊讶的结果，即 SOC 过程中的雪崩可以用于解决非凸优化问题。为了产生雪崩，我们在反映优化问题图的图上使用 Abelian 沙堆模型。对于优化，我们将雪崩区域映射到优化的搜索模式上，而 SOC 过程本身不会从优化中获得反馈。所得到的方法可以在无需参数调整的情况下应用于广泛的优化问题，我们在三个问题上进行了演示：寻找伊辛自旋玻璃的基态、图着色和图像分割。我们发现，与其他随机搜索方法（包括模拟退火）相比，SOC 搜索更为高效，并且与退火不同的是，它没有参数，从而消除了调整退火温度方案所需的耗时要求。
