下载掌阅APP，畅读海量书库
立即打开
崎岖性是衡量适应度地形中局部最优解的数量和分布的一种方式，其与适应度值整体的变化程度有关 [1] 。如果一个优化问题解空间的适应度值变化剧烈，换句话说，邻域解的适应度值与解本身的适应度值差异性很大，那么该优化问题的地形就可以被看成是崎岖的。与此相对应，如果一个优化问题解空间的适应度地形只有一个盆地/山峰，或者是没有任何特征的平原区域，那么该优化问题的适应度地形就不能被看成是崎岖的，或者说可以被看成是平坦的。从崎岖性的特性可以看出，如果一个优化问题的适应度地形是崎岖的，那么设计该优化问题的搜索算法时需要更加关注其跳出局部最优解的能力。图2-1给出四种不同崎岖程度的适应度地形，对于不同崎岖程度的适应度地形，其相应搜索策略的关注点不同，这也是适应度地形特征为优化算法设计提供指导性的意义所在。
图2-1 不同崎岖程度的适应度地形
在定性理解崎岖性概念的同时，如何定量定义和刻画地形的崎岖性，是一个值得关注的问题。Kauffman在研究过程中提出了NK地形模型 [2] ，该模型作为一种基准地形产生器，对于适应度地形的研究发挥了非常重要的作用，很多研究工作都是在NK地形的基础上开展的。在研究崎岖性时，可以通过调节NK地形的参数控制地形的崎岖性，进而生成具有不同崎岖程度的地形，为研究相应的崎岖性评价指标提供验证基准。相关性分析作为适应度地形分析的一种经典方法，从自相关分析 [3] 和距离相关性分析 [8] 的角度入手，分别从不同的角度反映了适应度地形的崎岖性。自相关分析侧重于从采样解的适应度值之间的关系入手，距离相关性考量的是当前解与全局最优解之间的关系。另外，Vassilev等人基于信息熵提出了评价问题适应度地形崎岖性的分析方法，该方法从采样解中提出包含的信息量，可以同时探讨地形的平坦性、崎岖性和中性等多个特征 [11] 。本书作者从适应度地形的时域分析角度出发，利用有向图及其中的坐标值定量描述地形的尖锐性，侧面反映地形的崎岖性。