下载掌阅APP，畅读海量书库
立即打开
实际中的优化问题往往非常复杂，元启发式算法在解决这些问题时取得了较好的效果，但是在解决某一特定问题时，选择何种算法和如何进行参数设置给研究人员带来了巨大挑战。解决这一困境的方法是在确定算法前，利用适应度地形理论分析了解问题的特性，为算法设计提供先验知识。对于多数优化问题，都存在一个适应度函数来反映问题所要解决的目标。适应度函数决定了问题潜在解的适应度值，并由此衡量解的优劣。
适应度地形的概念来源于生物学，最早由Wright在1932年提出 [22] ，作为基因型和适应度值的一种映射关系。基因型可以通过变异的方式变化到邻近基因型，而适应度地形则自然地由每个基因型的适应度值组成。适应度地形的拓扑结构特征对于观察解空间的动态演进具有重要意义，便于解释随着演进过程的推进，基因型的变化规律。另一方面，随着算法的迭代，适应度地形表面的演进路径也往往成为关注的重点，它由一系列连续生成的基因型组成，刻画了种群中的基因型从低适应度值区域到高适应度值区域的演进过程。
适应度地形以适应度函数为基础，它将解空间中的解按照某种邻域方式排列，并由每个解的适应度值组成适应度地形。一般的适应度地形由三个元素确定：问题的解空间
X
，基于
X
的邻域、最小距离或可达性定义
，以及适应度函数
f
（
x
）：
。按照
规定的顺序将解的适应度值表示成一维数组的形式，即得到适应度向量。将
X
中的解视为离散点，按照
定义的顺序排列作为横坐标，适应度向量作为纵坐标绘制二维曲线，即得到适应度地形图。这是以静态适应度地形为例，其可以表示为：
式中，
X
为解空间；
N
（
x
）为邻域结构，它决定了每个解
x
∈
X
的邻域解；
f
（
x
）：
为适应度函数，它决定了每个解的适应度值并以此衡量解的质量。
以邻域结构相连接的解空间表达了“位置”的概念，而适应度值是从位置衍生出的正投影，表达了“海拔”或“高度”的概念，并为每个“位置”赋予了其最重要的特征。适应度值往往是一个单一的参数，但它有可能由多维高度值表征。
适应度地形的相关理论在20世纪90年代才得到关注并发展，其发展过程如图1-1所示。
图1-1 适应度地形理论的发展过程
目前，适应度地形理论在地形拓扑结构、特征参数以及对算法设计的指导等方面取得了一些研究成果。针对不同的适应度地形特征建立相应的参数描述体系是适应度地形理论发展的一个主要方向。参数描述体系是对适应度地形进行定性和定量刻画的一个基础，它通过描述地形的形状、崎岖性、可演进性等性质，反映问题的困难程度等特征。由于优化问题可分为静态优化问题和动态优化问题，因此参数描述体系也相应地分为静态和动态两类。相关研究的分类和指标如图1-2所示，在后续章节中将进行详细的介绍。
图1-2 适应度地形的分类和指标
研究人员对于静态适应度地形的研究起步较早，经过长时间的探索与改进，有关静态适应度地形的评价参数已较为丰富，其研究过程主要分为以下几个基本阶段。在80年代后期到90年代中期，相关研究主要集中在地形崎岖性的分析。地形崎岖性是指地形的波动程度，它与局优解的数目和分布密切相关。衡量地形崎岖性的评价参数较多，Weinberger [23] 提出了自相关函数和相关长度的概念，它通过随机游走在地形中获得一系列适应度值，然后计算这些值与一段距离之外的同样数目的适应度值的相关性，相关性越小，地形越崎岖。Lip-sitch [24] 提出了相关长度的另一种计算方式，简化了自相关函数的计算。这些评价只能在地形统计各向同性的前提下使用。几年后，Vassilev [25] 等人提出了第一熵和第二熵测量，他们通过计算与序列中崎岖元素的概率分布有关的信息熵，获得一个图表来反映地形崎岖性。此外，Hordijk [26] 另辟蹊径，通过幅度谱反映地形的整体特征，利用傅里叶变换和拉普拉斯矩阵，将适应度地形分解为子地形，并获得相关长度信息。
在同一时期，地形间的依赖性也引起了学者的广泛关注。依赖性是指变量间的依赖程度，当优化问题中的各变量相互依赖时，就意味着不可能只通过独立地调节一个变量获得最优解。衡量依赖性的典型方法有依赖方差和按位依赖性。依赖方差是由Davidor提出的用于遗传算法的评价参数 [27] ，它通过一个字符串的适应度值的一系列线性计算，得到预测字符串值，该字符串的适应度值和预测值的方差就是依赖方差的大小。按位依赖是由Fonlupt等人提出的另一种衡量依赖性的方法 [28] ，它按位比较基因型中每位为0和1时的适应度值的差值，计算这些差值的方差。
在90年代后期，一些学者投入到中性特征的研究中。中性是与崎岖性相对应的一个特征，它表征了地形中解的适应度值相同或相近的某一区域，能揭示局优解的信息并暗示搜索算法成功的可能性。Reidys [29] 提出了一种基于离散空间的中性游走，它从起始点开始，寻找使总距离（距起始点的距离）增大的中性邻居，直到不存在使总距离增加的中性邻居，最终获得中性游走的步数。该方法在边缘相关性较大时会有较大的偏差，且需事先明确邻域的定义，只能用于离散空间。Verel等人 [30] 由局优网络分析适应度地形的中性结构，但该方法需要通过枚举获得全部解空间。
2000年以后，可演进性成为适应度地形研究的主流。可演进性是指能使搜索过程移动到更好区域的能力，这个更好的区域具有更好的适应度值。与其他评价指标不同，可演进性与算法相关，只有当明确特定搜索策略时才有意义。Smith等人提出了适应度可演进图 [31] ，它通过计算子代适应度值大于等于父代适应度值的概率、子代平均适应度值等一系列可演进性指标，获得适应度值相同解的平均度量，并以此建立适应度可演进图。适应度云 [32] 是衡量可演进性的另一种方法，它将父代适应度值所对应的子代适应度值在演进图中绘制出来，以此描述父代与子代适应度值之间的关系。Vanneschi [33] 等人在适应度云的基础上又提出了负斜率系数，它将适应度云分成离散的几部分，并定义线段作为相邻部分的中心距，计算线段间的负斜率之和即可得到负斜率系数。此外，Lu等人提出了适应度概率云 [34] ，基于个体的适应度值和逃脱率研究地形的可演进性，它改进了适应度云的不足，不依赖地形间相关性的变化。
除了以上提到的研究地形特征的方法外，还有其他一些地形评价参数。比如，欺骗性是地形的一种特征，它是指地形中存在误导算法搜索的信息，并且与特定算法有关。Deb提出了在基因算法中衡量欺骗性的参数，即基因欺骗性 [35] ，它将欺骗程度分为完全欺骗和部分欺骗，并给出了每种欺骗程度的定义和条件。该方法计算量不大，但只给出了充分条件，不满足这些条件的地形也有可能具有欺骗性。全局地形结构是地形的另一特征 [36] ，它是指由集中的局优解组成的全局盆地形状。离差度量是衡量全局地形结构的一种方法，它通过计算采样点中最好部分点之间的两两距离平均值，衡量采样点之间的邻近程度，进而反映地形特征。
以上评价参数衡量了地形各方面的特征，但均是针对静态适应度地形提出的。自2013年以来，学者们将目光逐步投向了动态地形评价参数的研究，并获得了一些研究成果。Rohlfshagen给出了动态适应度地形的基本定义与数学描述 [37] ，并给出了动态中立性以及崎岖性的基本描述。在评价指标方面，动态适应度距离相关是衡量搜索困难程度的一种方法 [38] ，它首先计算每个变化周期内的适应度距离相关性，然后计算这些适应度距离相关性与初始地形的平均差值。平均最优适应度值通过计算最优解在连续变化周期内的平均变化差值，反映最优解适应度值的变化。
主要亚稳状态间的平均距离由Tinós提出 [38] ，它衡量了主要亚稳状态在连续变化周期内的平均欧式距离。主要亚稳状态是指搜索空间的收敛点，它的计算与算法有关，不同的优化算法具有不同的计算方式。与主要亚稳状态有关的另一评价参数是达到亚稳状态的平均时间百分比，它是指种群向量到达亚稳状态的平均时间，即所需的进化代数。这两种评价参数计算较为复杂，并且依赖于特定算法，不具有一般性。
综上所述，目前的适应度地形参数大部分都是针对某一领域特定的静态问题开展的研究，基于动态适应度地形分析的参数较少。如衡量崎岖性的评价指标与动态适应度距离相关，在计算时需要最优解的先验信息，且变量必须为二元正态分布。衡量依赖性的典型方法，如依赖方差和按位依赖性是针对遗传算法提出的，不适用于其他算法。衡量中性的方法，如中性游走、局优网络分析需要依赖邻域距离的定义方式或需要解空间的全枚举，限制了它们的使用范围。可演进性指标反映了算法产生更优子代的能力，只有明确了特定算法、特定操作算子后才有意义，并不能通过适应度地形直接反映问题特性。因此，适应度地形理论本身处于发展完善的过程，相应的特征参数、分析手段无法完全适用于各种问题的解空间特性分析。
适应度地形的研究为了解问题特性提供了一种手段，利用适应度地形的研究成果指导优化算法设计，成为目前和未来发展的主要趋势。目前，在优化领域中已经出现了一些研究成果。Cotta [39] 用以调度规则为基础的启发式算法，发现产品调度问题的适应度地形存在大山谷和高原，局部最优解很多，进而说明初始化的重要性。华中科技大学高亮教授团队针对静态单目标车间调度问题开展了研究工作，文峰 [40] 提出了一种基于Logistic模型的适应度地形研究方法。Lu [41] 针对单目标测试任务调度问题提出了基于编辑距离的适应度地形分析方法。Verel [42] 重点分析多目标组合优化算法的行为，提出一种考虑各目标函数间相关性的多目标地形。该研究考虑了问题的维度、非线性程度、目标个数、各目标Pareto前沿的相关性等因素。Fabre [43] 重点研究基于原始目标函数分解的多目标优化理论，并针对多目标优化提出相应的适应度地形理论和中立性分析方法。He [44] 提出利用适应度地形指导进化计算领域中标准测试函数的设计，并对适应度函数的难易程度进行了理论分析和评估方法研究。Bas-seur [45] 重点关注爬山组合优化问题，考虑了问题的大小、地形的崎岖度和中立性等因素，同时提出一种预测机制帮助爬山算法快速进入最优状态。Huang [46] 分析了基于认知无线电系统的多用户OFDM（Orthogonal Frequeny Dirision Multiple Xing）系统资源分配问题的适应度地形，研究利用适应度地形的分析来指导算法中遗传操作的选择。Lu等 [47] 将适应度地形分析引入到算法的参数控制，通过适应度地形调整所提出方法的参数，从而进一步提升算法求解测试任务调度问题的能力。