Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study
Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study
复制标题
了解局部最优网络的相变：以数字划分为例
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Tomassini
中科院分区：
文献类型：
--
作者：
G. Ochoa;Nadarajen Veerapen;F. Daolio;M. Tomassini
相变在理解组合优化中的搜索困难方面起着重要的作用。然而，以前的尝试并没有发现一个明确的健身景观属性和相变之间的联系。我们探讨了数字划分问题的全局景观结构是否随相变而变化。使用局部最优网络模型，我们分析了一些实例之前，期间和之后的相变。我们计算相关的网络和中立性指标;重要的是，识别和可视化漏斗结构的方法（单调序列）的灵感来自理论化学。虽然大多数指标仍然忽略了相变，但我们的结果显示漏斗结构明显发生了变化。简单实例具有单个或少量主导漏斗，导致全局最优;困难实例具有大量次优漏斗，吸引搜索。我们的研究带来了新的见解和工具的相变组合优化的研究。
Phase transitions play an important role in understanding search difficulty in combinatorial optimisation. However, previous attempts have not revealed a clear link between fitness landscape properties and the phase transition. We explore whether the global landscape structure of the number partitioning problem changes with the phase transition. Using the local optima network model, we analyse a number of instances before, during, and after the phase transition. We compute relevant network and neutrality metrics; and importantly, identify and visualise the funnel structure with an approach (monotonic sequences) inspired by theoretical chemistry. While most metrics remain oblivious to the phase transition, our results reveal that the funnel structure clearly changes. Easy instances feature a single or a small number of dominant funnels leading to global optima; hard instances have a large number of suboptimal funnels attracting the search. Our study brings new insights and tools to the study of phase transitions in combinatorial optimisation.