研究背景与意义

  适应度地形（Fitness Landscape）是演化计算中的关键概念，用于描述基因型和表现型之间的关系，帮助研究者理解优化问题的结构，并设计有效的算法以找到最优解。这种关系在一维、二维问题下非常直观，下图是2维情况下10个组件的GMPB问题，我们可以清楚的看到解在决策空间下的位置对应的适应值的大小，能够清楚地观察到问题的模态数、崎岖程度、哪些地方更优，但这也仅限于二维优化问题。

  如果问题的维度大于2，则无法在现有的空间绘制出适应度地形图，由于高维优化问题适应度景观的复杂性，所以对其进行分析和可视化始终具有挑战性。传统的适应度景观分析方法（FLA）往往依赖于算法、操作符或随机游走生成的样本，这些方法仅能获取局部的景观特征，难以保持问题的整体结构。为了弥补上述缺点，研究小组内的刁义雅师姐提出了一种最近-更优网络（Nearest-Better Network, NBN）来分析适应度地形，NBN方法基于无偏样本，能够在3D可视化中展现问题特征，适用于高维优化问题。

Nearest-Better Network

NBN的定义

  NBN定义了一种基于无偏样本的网络结构，用于保持适应度景观中的特征，如平坦性、崎岖性、多模性和吸引域等。NBN被定义为一个有向图$G=(V,E)$，其中顶点集$V$是从搜索空间中采样的解集$X_N$，边集$E$是基于优化问题中每个样本点的“最近-更优”关系构建，对于一个解$x$，其最近-更优解$\beta(x)$是指集合中所有比$x$适应度更高的解中，距离最近的那个解：
$$\beta(x) = \arg \min_{y \in \{y | y \in X_N, f(y) > f(x)\}} \|y - x\|$$
$f$表示适应度函数，边集$E$表示每个解到其最近-更优解的关系的集合。

NBN的计算

  这一部分省略，有兴趣可以查看论文理解，我觉得有些抽象，不好理解，我只会用遍历的方式生成NBN，时间复杂度为$O(n^2)$

NBN提供的特性

多模特性

  基于最近-更优距离$\|x - \beta(x)\|$判断局部或全局最优解。
$$\|x - \beta(x)\| > 3 \cdot \frac{\sum_{y \in X_N} \|y - \beta(y)\|}{|X_N|}$$

吸引域

  吸引域 $B(x)$ 是直接或间接连接到解$x$的最近更优解的集合。
$$B(x) = \bigcup_{y \in Bd(x)} B(y) \cup Bd(x) $$
其中，$Bd(x)$ 是直接被 $x$ 吸引的解集合。

崎岖性

  通过最近-更优距离的方差来测量适应度地形的崎岖性。
$$I_r = \sqrt{\sum_{x \in X_N} d(x)^2}, \quad d(x) = \|x - \beta(x)\|$$

平坦性

  通过计算平坦区域的最大尺寸来评估适应度地形的平坦性。
$$I_n = \max_{x \in X_N} |B_{neu}(x)|$$

NBN的三维可视化

  TODO