适应值曲面研究方法综述摘要：适应值曲面分析是一种研究优化问题难度的方法，而优化问题难度研究则是进化算法研究的一个重要分支。本文简要介绍了适应值曲面分析的五种方法及其近年来的研究进展，不仅包括适应度距离关联测试法、关联长度测试法、异位显性差异和异位相关性测试法等三种常见的适应值曲面分析方法近年的研究进展之外，还包括空间关联测试法和面自动机等两种适应值曲面分析方法。关键词：空间关联性；关联长度；异位相关性中图分类号：0221.4文献标识码：A文章编号：1674-7712(2012)12-0141-02一、引言进化算法是智能优化算法的重要分支，但是其应用范E不仅局限于优化领域，在图像处理、人工智能、工业设计、自动控制等领域都有广泛的应用。进化算法研究的一个重要分支，自上世纪八十年代起人们开始在进化计算框架下研究优化问题的难度，而适应值曲面分析则是其中的重要方法之一。适应值曲面是指将优化问题的所有可行解的适应值按照某种邻域规则排列在一起形成的曲面。分析适应值曲面的特征有助于了解问题的难度，为进化算法的设计和改进提供依据。一般认为，适应值曲面的崎岖程度与优化问题的难度正相关，大部分适应值II曲面测试方法大多是从不同的角度描述适应值曲面的崎岖程度。目前，国内对适应值曲面分析方法的资料较少且对缺乏对近期研究进展的跟进，因此本文简要介绍了几种适应值曲面分析方法，包括适应度距离关联(FitnessDistanceCorrelation,FDC)测试法、空间关联(SpatialCorrelation,SC)测试法、曲面自动机(LandscapeStateMachine,LSM)、关联长度(CorrelationLength,CL)测试法、异位显性差异(EpistasisVariance，EPV)和异位相关性(EpistasisCorrelation,EPC)测试等六种适应值曲面分析方法。二、适应度距离关联测试方法Jones和Forrest[1]的适应度距离关联(FitnessDistanceCorre1ation,FDC)测试法是较早出现的一种适应值曲面测试方法。这种方法通过测试适应值与距离之间的相关系数描述适应值曲面的特性。fdcp的计算公式：其中，P表示在适应值曲面上进行的随机取样集合，和分别表示P的适应值均值和所有点到适应值最优点的距离均值。fdcpe[-1，1]反映适应值的变化趋势与适应值曲面的变化趋势之间的关系，fdcp趋近于-1则与最优解距离越远的点适应值越小；fdcp趋近于1则与最优解距离越远的点适应值越大。求最小值问题,fdcp趋近于-1时难度较大，趋近于1时难度较小，求最大值问题的情况则相反。显然，相同问题的fdcp值的差别仅存在于因样本集P的选取所产生的误差中，与fdcp的计算方法本身没有任何关系。三、关联长度测试法Weinberger[2]的关联长度(CorrelationLength,CL)测试法是通过随机游走函数在适应值曲面上产生一个随机游走序列｛f(xt)｝，通过对这个序列计算相关性相关长度，判断适应值曲面的崎岖程度。适应值曲面上的邻域规则是连接适应值方法和进化算法之间的纽带，若选取的邻域规则与进化算子的作用方式越一致，则得到的结果与进化算法的性能表现越接近。适应度距离关联测试法采用的较常见的欧氏距离，但是关联长度测试法采用的是不确定性邻域规则，其邻域规则由随机游走函数决定。Hauschild[3]等对适应值曲面上的邻域规则做了比较深入的研究，提出两种新的适应值曲面上的邻域定义：固定划分(FixedPartition)邻域和随机划分(RandomPartition)邻域，一个个体的固定划分邻域是其二进制编码串的某个确定的子块中反转任意的二进制位可以产生的所有新二进制串组成的集合，随机划分邻域是其二进制编码串中随机改变其中不超过X位能产生的所有新二进制串组成的集合。Borenstein[4]等提出信息曲面(InformationLandscape)的概念实际上是对适应值曲面的一种改进，以使之能够适应“探索利用平衡理论”等较新II分析测试颖的优化算法理论研究成果。信息曲面包括三个参数(X，，t)，其中X表示全部可行解组成的集合,？表示邻域、距离、集合X的可到迗性，t表示一个随机信息映射，将X中两个元素的相互关系映射到［0,1］区间内。四、空间关联分析法Gibbs［5］等提出基于空间关联的适应值曲面分析方法，计算空间关联系数Rs(d)的公式如下：其中，n表示在适应值曲面上随机抽取的样...