Title

On the Performance of Indirect Encoding Across the Continuum of Regularity

Authors

Authors

J. Clune; K. O. Stanley; R. T. Pennock;C. Ofria

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

IEEE Trans. Evol. Comput.

Keywords

Artificial neural networks; developmental encodings; generative; encodings; HyperNEAT; indirect encodings; regularity; NEURAL-NETWORKS; AUTONOMOUS EVOLUTION; OBSTACLE-AVOIDANCE; CONTROLLERS; LOCOMOTION; ROBOTS; Computer Science, Artificial Intelligence; Computer Science, Theory &; Methods

Abstract

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.

Journal Title

Ieee Transactions on Evolutionary Computation

Volume

15

Issue/Number

3

Publication Date

1-1-2011

Document Type

Article

Language

English

First Page

346

Last Page

367

WOS Identifier

WOS:000292110600004

ISSN

1089-778X

Share

COinS