Title

Efficiently Evolving Programs Through The Search For Novelty

Keywords

Genetic programming; Novelty search; Premature convergence; Program bloat

Abstract

A significant challenge in genetic programming is premature convergence to local optima, which often prevents evolution from solving problems. This paper introduces to genetic programming a method that originated in neuroevolution (i.e. the evolution of artificial neural networks) that circumvents the problem of deceptive local optima. The main idea is to search only for behavioral novelty instead of for higher fitness values. Although such novelty search abandons following the gradient of the fitness function, if such gradients are deceptive they may actually occlude paths through the search space towards the objective. Because there are only so many ways to behave, the search for behavioral novelty is often computationally feasible and differs significantly from random search. Counterintuitively, in both a deceptive maze navigation task and the artificial ant benchmark task, genetic programming with novelty search, which ignores the objective, outperforms traditional genetic programming that directly searches for optimal behavior. Additionally, novelty search evolves smaller program trees in every variation of the test domains. Novelty search thus appears less susceptible to bloat, another significant problem in genetic programming. The conclusion is that novelty search is a viable new tool for efficiently solving some deceptive problems in genetic programming. Copyright 2010 ACM.

Publication Date

8-27-2010

Publication Title

Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10

Number of Pages

837-844

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/1830483.1830638

Socpus ID

77955883428 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/77955883428

This document is currently not available here.

Share

COinS