Bag of local landscape features for fitness landscape analysis
Bag of local landscape features for fitness landscape analysis
复制标题
DOI：
10.1007/s00500-016-2091-4
复制
发表时间：
2016-02
期刊：
影响因子：
4.1
通讯作者：
S. Shirakawa;T. Nagao
中科院分区：
文献类型：
--
作者：
S. Shirakawa;T. Nagao
进化计算是一个处理黑盒和复杂优化问题的研究领域，这些问题的适应度景观通常是事先未知的。尽管已有许多进化算法被开发出来，但由于黑盒设置的存在，很难对给定问题选择合适的进化算法和参数。在此背景下，提出了几种景观特征，并考察了它们对理解问题的有用性。在本文中，我们提出了一种新的特征向量，通过关注局部景观来表征适应度景观。提出的景观特征是一种矢量形式，由量化的局部景观特征直方图组成。本文介绍了这一概念的两种实现方法，即局部景观格局包（BoLLP）和可演化性包（BoEvo）。BoLLP使用某个候选解的邻居的适应度模式，BoEvo使用邻居中较好的候选解的数量作为局部景观特征。此外，BoLLP和BoEvo的分层版本，连接不同样本量的特征向量，被认为可以捕获不同分辨率的景观特征。从已知的连续优化基准函数和BBOB基准函数集中提取景观特征向量，研究它们的性质；对所提出的景观特征进行可视化、聚类和运行时间预测实验。然后根据实验结果，讨论了所提出的景观特征对适应度景观分析的有效性。
Evolutionary computation is a research field dealing with black-box and complex optimization problems whose fitness landscapes are usually unknown in advance. It is difficult to select an appropriate evolutionary algorithm and parameters for a given problem due to the black-box setting although many evolutionary algorithms have been developed. In this context, several landscape features have been proposed and their usefulness examined for understanding the problem. In this paper, we propose a novel feature vector by focusing on the local landscape in order to characterize the fitness landscape. The proposed landscape features are a vector form and composed of a histogram of quantized local landscape features. We introduce two implementation methods of this concept, called the bag of local landscape patterns (BoLLP) and the bag of evolvability (BoEvo). The BoLLP uses the fitness pattern of the neighbors of a certain candidate solution, and the BoEvo uses the number of better candidate solutions in the neighbors as the local landscape features. Furthermore, the hierarchical versions of the BoLLP and the BoEvo, concatenated feature vectors with different sample sizes, are considered to capture the landscape characteristic with various resolutions. We extract the proposed landscape feature vectors from well-known continuous optimization benchmark functions and the BBOB benchmark function set to investigate their properties; the visualization of the proposed landscape features, clustering and running time prediction experiments are conducted. Then the effectiveness of the proposed landscape features for the fitness landscape analysis is discussed based on the experimental results.