On the Performance of Indirect Encoding Across the Continuum of Regularity
On the Performance of Indirect Encoding Across the Continuum of Regularity
复制标题
DOI：
10.1109/tevc.2010.2104157
复制
发表时间：
2011-06-01
影响因子：
14.3
通讯作者：
Ofria, Charles
中科院分区：
文献类型：
--
作者：
Clune, Jeff;Stanley, Kenneth O.;Ofria, Charles
本文研究了具有间接编码的进化算法如何利用表型规律性的特性，表型规律性是自然生物和工程设计中发现的重要设计原则。我们提出的第一项综合研究表明，随着问题规律性的增加，这种表型规律性使得间接编码能够优于直接编码控制。如果进化算法要扩展到高维现实世界问题（通常包含许多已知和未识别的规律），那么产生能够利用问题规律性的规律解决方案的能力是一个重要的先决条件。本案例研究中的间接编码是 HyperNEAT，它以受生物发展概念启发的方式演化人工神经网络 (ANN)。我们证明，与两种直接编码控制相比，HyperNEAT 会产生常规行为和常规 ANN，这使得随着三个问题域中规律性的增加，HyperNEAT 的性能显着优于直接编码。我们还表明，HyperNEAT 产生的规律类型可能是有偏差的，允许将领域知识和偏好注入到搜索中。最后，我们研究了偏向规律性的缺点。即使解决方案主要是规则的，也可能需要一些不规则性来完善其功能。这种见解通过一种名为 HybrID 的新算法得到了体现，该算法混合了间接和直接编码，该算法与 HyperNEAT 在常规问题上的性能相匹配，但在某些不规则问题上的性能优于 HyperNEAT。 HybrID 改进 HyperNEAT 性能的能力提出了一个问题：间接编码最终是否可能不是作为独立算法而表现出色，而是通过与进一步的细化过程混合，其中间接编码产生利用问题规律性的模式，而细化过程会修改该模式以捕获不规则性。因此，本文描绘了比先前研究更完整的间接编码图景，因为它分析了不规则性和规则性之间的连续体对此类编码性能的影响，并最终提出了一条将间接编码与单独的细化过程相结合的前进道路。
This paper investigates how an evolutionary algorithm with an indirect encoding exploits the property of phenotypic regularity, an important design principle found in natural organisms and engineered designs. We present the first comprehensive study showing that such phenotypic regularity enables an indirect encoding to outperform direct encoding controls as problem regularity increases. Such an ability to produce regular solutions that can exploit the regularity of problems is an important prerequisite if evolutionary algorithms are to scale to high-dimensional real-world problems, which typically contain many regularities, both known and unrecognized. The indirect encoding in this case study is HyperNEAT, which evolves artificial neural networks (ANNs) in a manner inspired by concepts from biological development. We demonstrate that, in contrast to two direct encoding controls, HyperNEAT produces both regular behaviors and regular ANNs, which enables HyperNEAT to significantly outperform the direct encodings as regularity increases in three problem domains. We also show that the types of regularities HyperNEAT produces can be biased, allowing domain knowledge and preferences to be injected into the search. Finally, we examine the downside of a bias toward regularity. Even when a solution is mainly regular, some irregularity may be needed to perfect its functionality. This insight is illustrated by a new algorithm called HybrID that hybridizes indirect and direct encodings, which matched HyperNEAT's performance on regular problems yet outperformed it on problems with some irregularity. HybrID's ability to improve upon the performance of HyperNEAT raises the question of whether indirect encodings may ultimately excel not as stand-alone algorithms, but by being hybridized with a further process of refinement, wherein the indirect encoding produces patterns that exploit problem regularity and the refining process modifies that pattern to capture irregularities. This paper thus paints a more complete picture of indirect encodings than prior studies because it analyzes the impact of the continuum between irregularity and regularity on the performance of such encodings, and ultimately suggests a path forward that combines indirect encodings with a separate process of refinement.