Behavior based approach for Genetic Programming

11:35 pm - 12:00 pm 24 Thursday


Genetic Programming

Evolutionary algorithms (EAs) are a broad family of search and optimization algorithms that are based on a simplified model of Neo-Darwinian evolution, with impressive results in many domains [1]. EAs are guided by an objective function and specially designed search operators, in this sense can be said that they are objective-based search (OS), this is a key difference with respect to natural evolution, an open-ended process that lacks a predefined purpose. Open-ended artificial evolution does not use an objective function to drive the search, at least not an explicit one. Only recently has open-ended search been proposed to solve mainstream problems, one promising algorithm is Novelty Search (NS) proposed by Lehman and Stanley [2].

The core idea behind NS is that using an objective function to determine fitness in challenging problems may mislead the search and prevent it from reaching the global optima. Therefore, the proposal of NS is to abandon the objective function, and instead determine selective pressure based on the novelty or “uniqueness” of each individual by considering a description of the behavior each individual exhibits. From the NS perspective, a behavior refers to a description of the interaction between a candidate solution and it’s domain-specific context. Even though, NS has achieved promising results in different areas of evolutionary robotics, such as navigation [2, 4], morphology design and gait control [3], has not been tested on machine learning problems.

This work makes the following contributions. We apply NS on a common machine learning problem; supervised classification with GP, while previously works have mostly focused on evolutionary robotics. The NS approach is tested on real-world datasets, and using two new versions of NS are proposed; Probabilistic NS (PNS), and a variant of Minimal Criteria NS (MCNS), and lastly a combination of both named as MCPNS. The former models the behavior of each solution as arandom vector and eliminates all the NS parameters while reducing the computational overhead of the NS algorithm; the latter uses a standard objective function to constrain and bias the search towards high performance solutions. The paper also discusses the effects of NS on GP search dynamics and code growth.

Table 1 shows results about the dataset Teaching Assistant Evaluation (TAE)1, we can note that in general, all NS algorithms are very competitive relative to OS.To illustrate the performance differences for the TAE dataset among the methods, Figure 1 shows both the average size evolution plot, and a box plot comparison of the test error from the best solution found in each run.

When we consider the average program size it is clear that all NS variants evolve much smaller populations.In particular NS and MCNS show an intrinsic bloat-control property in this domain. In summary, this work will help to establish the behavior-based approach with NS as a viable alternative for GP-based systems.


[1] John Koza. Human-competitive results produced by genetic programming.Genetic Programming and Evolvable Machines, 11(3):251–284, 2010.

[2] Joel Lehman and Kenneth O. Stanley. Exploiting open-endedness to solve problems through the search for novelty. InProceedings of the Eleventh International Conference on Artificial Life, Cambridge, MA,ALIFE XI. MIT Press, 2008.

[3] Joel Lehman and Kenneth O. Stanley. Abandoning objectives: Evolution through the search for novelty alone.Evol. Comput., 19(2):189–223, 2011.

[4] Paulo Urbano, Enrique Naredo, and Leonardo Trujillo. Generalization in maze navigation using grammatical evolution and novelty search. In Theory and Practice of Natural Computing, volume 8890 of Lecture Notes in Computer Science, pages 35–46. Springer International Publishing, 2014.

Enrique Naredo