Hildebrandt Torsten, Branke Jürgen
Bremer Institut für Produktion und Logistik GmbH (BIBA) an der Universität Bremen, Bremen, Germany
Warwick Business School, University of Warwick, CV4 7AL Coventry, UK
Evol Comput. 2015 Fall;23(3):343-67. doi: 10.1162/EVCO_a_00133. Epub 2014 Nov 24.
One way to accelerate evolutionary algorithms with expensive fitness evaluations is to combine them with surrogate models. Surrogate models are efficiently computable approximations of the fitness function, derived by means of statistical or machine learning techniques from samples of fully evaluated solutions. But these models usually require a numerical representation, and therefore cannot be used with the tree representation of genetic programming (GP). In this paper, we present a new way to use surrogate models with GP. Rather than using the genotype directly as input to the surrogate model, we propose using a phenotypic characterization. This phenotypic characterization can be computed efficiently and allows us to define approximate measures of equivalence and similarity. Using a stochastic, dynamic job shop scenario as an example of simulation-based GP with an expensive fitness evaluation, we show how these ideas can be used to construct surrogate models and improve the convergence speed and solution quality of GP.
加速具有昂贵适应度评估的进化算法的一种方法是将它们与代理模型相结合。代理模型是适应度函数的高效可计算近似，通过统计或机器学习技术从完全评估解的样本中推导得出。但这些模型通常需要数值表示，因此不能与遗传编程（GP）的树表示一起使用。在本文中，我们提出了一种将代理模型与GP一起使用的新方法。我们不是直接将基因型用作代理模型的输入，而是建议使用表型特征。这种表型特征可以高效计算，并使我们能够定义等价性和相似性的近似度量。以随机动态作业车间场景为例，作为具有昂贵适应度评估的基于模拟的GP，我们展示了如何使用这些思想来构建代理模型并提高GP的收敛速度和求解质量。
