Turkey Mikdam, Poli Riccardo
School of Computer Science, Electronic Engineering, University of Essex, Wivenhoe Park, Colchester, Essex, CO4 3SQ, U.K.
Evol Comput. 2014 Spring;22(1):159-88. doi: 10.1162/EVCO_a_00107. Epub 2013 Oct 30.
Several previous studies have focused on modelling and analysing the collective dynamic behaviour of population-based algorithms. However, an empirical approach for identifying and characterising such a behaviour is surprisingly lacking. In this paper, we present a new model to capture this collective behaviour, and to extract and quantify features associated with it. The proposed model studies the topological distribution of an algorithm's activity from both a genotypic and a phenotypic perspective, and represents population dynamics using multiple levels of abstraction. The model can have different instantiations. Here it has been implemented using a modified version of self-organising maps. These are used to represent and track the population motion in the fitness landscape as the algorithm operates on solving a problem. Based on this model, we developed a set of features that characterise the population's collective dynamic behaviour. By analysing them and revealing their dependency on fitness distributions, we were then able to define an indicator of the exploitation behaviour of an algorithm. This is an entropy-based measure that assesses the dependency on fitness distributions of different features of population dynamics. To test the proposed measures, evolutionary algorithms with different crossover operators, selection pressure levels and population handling techniques have been examined, which lead populations to exhibit a wide range of exploitation-exploration behaviours.
先前的几项研究聚焦于对基于群体的算法的集体动态行为进行建模和分析。然而，令人惊讶的是，缺乏一种用于识别和表征这种行为的实证方法。在本文中，我们提出了一种新模型来捕捉这种集体行为，并提取和量化与之相关的特征。所提出的模型从基因型和表型两个角度研究算法活动的拓扑分布，并使用多个抽象层次来表示群体动态。该模型可以有不同的实例化。在此，它是使用自组织映射的一个修改版本实现的。当算法在解决问题时，这些自组织映射用于在适应度景观中表示和跟踪群体运动。基于这个模型，我们开发了一组表征群体集体动态行为的特征。通过分析这些特征并揭示它们对适应度分布的依赖性，我们进而能够定义一种算法利用行为的指标。这是一种基于熵的度量，用于评估群体动态不同特征对适应度分布的依赖性。为了测试所提出的度量，我们研究了具有不同交叉算子、选择压力水平和群体处理技术的进化算法，这些算法使群体表现出广泛的利用 - 探索行为。
