🏔️ 适应度景观分析

通过适应度景观分析表征优化问题的难度，研究 NK 景观模型以及算法与景观之间的相互作用。

适应度景观分析 (Fitness Landscape Analysis) 为理解为什么某些优化问题对特定算法具有挑战性提供了一个理论和经验框架。通过研究适应度景观（即解的表示与适应度值之间的映射关系）的几何和统计特性，我们可以预测算法行为、改进算法设计，并深入理解复杂优化问题的结构。

适应度景观核心概念

景观度量 (Landscape Metrics)

适应度景观度量从不同维度量化问题的难度。常见的度量包括：

  • 粗糙度 (Ruggedness)： 景观中局部最优解的数量及其分布情况。
  • 上位性 (Epistasis)： 一个变量对适应度的贡献在多大程度上取决于其他变量的值。
  • 自相关性 (Autocorrelation)： 相邻解适应度值之间的相关性，反映了景观的平滑程度。
  • 中性 (Neutrality)： 相邻解具有相同适应度值的比例，在景观中形成“中性网络”。
上位性与变量交互
上位性（即一个变量对适应度的贡献依赖于其他变量）是进化算法面临问题难度的主要来源。相关研究探讨了上位性如何影响不同算法（特别是 EDA）的性能，以及景观分析如何指导问题分解以简化搜索过程。

NK 景观模型

NK 模型

由 Stuart Kauffman 提出的 NK 景观模型提供了一个可调的基准，用于研究问题结构与算法性能之间的关系。参数 N 控制变量数量，K 控制变量间上位性交互的程度。随着 K 从 0 增加到 N-1，景观从平滑且单峰状态转变为高度粗糙且多峰状态。

我对 NK 景观的研究分析了其交互结构如何与 EDA 学习到的模型相关联，景观属性如何随不同交互拓扑而变化，以及神经网络如何为 NK 景观结构提供紧凑的表征。

多目标 NK 景观
将 NK 景观模型扩展到多目标框架，包括开发具有异构目标（不同目标具有不同上位性结构）的多目标 NK 景观。这些基准模型为在已知景观属性的问题上研究进化多目标算法的行为提供了一个可控环境。
GECCO 2022 →
NK 景观与贝叶斯网络
研究 NK 景观的上位性结构与 EDA 在解决这些问题时学习到的贝叶斯网络之间的关系。探讨了 EDA 识别 NK 景观真实交互结构的能力，以及这种能力如何与优化性能相关联。

景观分析方法

局部最优网络 (LON)
局部最优网络将景观中所有局部最优解的结构建模为一个图，其中节点是局部最优解，边表示它们之间可能的转换。研究组合问题的 LON 属性及其与算法性能（特别是 EDA 及其他基于种群的搜索方法）的关系。
适应度-距离相关性 (FDC)
分析 FDC 作为问题难度的预测指标。FDC 衡量解的适应度与其到最近全局最优解距离之间的相关性。研究了 FDC 在何种条件下能准确预测不同类别算法面临的问题难度。

算法与景观的交互

算法与景观的匹配
研究景观属性与特定算法性能之间的关系。目标是识别哪些景观特征使问题对特定算法变得容易或困难，从而实现基于景观分析的算法选择和配置。这将适应度景观分析与机器学习中的算法选择问题联系起来。
作为景观探测器的 EDA 模型
探讨 EDA 学习到的概率模型如何作为适应度景观的探测器。EDA 在每一代学习到的模型编码了关于对适应度有重要影响的变量间依赖关系的信息，捕获了景观结构的某些方面。研究如何提取并利用这些信息来增强对问题的理解。

景观的神经嵌入

回旋镖形神经嵌入
发现 NK 景观解的神经嵌入在投影到二维空间时呈现出特征性的“回旋镖”形状。这种几何结构源于景观的上位性结构与神经网络学到的表征之间的相互作用。研究探讨了这种结构的起源及其对理解景观几何学的意义。
GECCO 2022 →
用于景观表征的神经网络
利用神经网络学习适应度景观结构的紧凑表征，可用于景观表征、算法选择和算法性能预测。研究不同的网络架构和学习目标如何捕捉景观几何的不同方面。

精选论文