Exploiting Open-Endedness to Solve Problems Through the Search for
Novelty
J. Lehman, and K. Stanley. ALIFE XI: Proc. 11th Int'l Conf. on Artificial
Life, page 329--336. Winchester, UK, MIT Press, (2008)
Abstract
This paper establishes a link between the challenge of solving highly
ambitious problems in machine learning and the goal of reproducing
the dynamics of open-ended evolution in artificial life. A major
problem with the objective function in machine learning is that through
deception it may actually prevent the objective from being reached.
In a similar way, selection in evolution may sometimes act to discourage
increasing complexity. This paper proposes a single idea that both
overcomes the obstacle of deception and suggests a simple new approach
to open-ended evolution: Instead of either explicitly seeking an
objective or modeling a domain to capture the open-endedness of natural
evolution, the idea is to simply search for novelty. Even in an objective-based
problem, such novelty search ignores the objective and searches for
behavioral novelty. Yet because many points in the search space collapse
to the same point in behavior space, it turns out that the search
for novelty is computationally feasible. Furthermore, because there
are only so many simple behaviors, the search for novelty leads to
increasing complexity. In fact, on the way up the ladder of complexity,
the search is likely to encounter at least one solution. In this
way, by decoupling the idea of open-ended search from only artificial
life worlds, the raw search for novelty can be applied to real world
problems. Counterintuitively, in the deceptive maze navigation task
in this paper, novelty search significantly outperforms objective-based
search, suggesting a surprising new approach to machine learning.
%0 Conference Paper
%1 Lehman:2008:alife
%A Lehman, Joel
%A Stanley, Kenneth O.
%B ALIFE XI: Proc. 11th Int'l Conf. on Artificial
Life
%C Winchester, UK
%D 2008
%E Bullock, Seth
%E Noble, Jason
%E Watson, Richard
%E Bedau, Mark A.
%I MIT Press
%K imported thesis
%P 329--336
%T Exploiting Open-Endedness to Solve Problems Through the Search for
Novelty
%U http://eplex.cs.ucf.edu/papers/lehman_alife08.pdf
%X This paper establishes a link between the challenge of solving highly
ambitious problems in machine learning and the goal of reproducing
the dynamics of open-ended evolution in artificial life. A major
problem with the objective function in machine learning is that through
deception it may actually prevent the objective from being reached.
In a similar way, selection in evolution may sometimes act to discourage
increasing complexity. This paper proposes a single idea that both
overcomes the obstacle of deception and suggests a simple new approach
to open-ended evolution: Instead of either explicitly seeking an
objective or modeling a domain to capture the open-endedness of natural
evolution, the idea is to simply search for novelty. Even in an objective-based
problem, such novelty search ignores the objective and searches for
behavioral novelty. Yet because many points in the search space collapse
to the same point in behavior space, it turns out that the search
for novelty is computationally feasible. Furthermore, because there
are only so many simple behaviors, the search for novelty leads to
increasing complexity. In fact, on the way up the ladder of complexity,
the search is likely to encounter at least one solution. In this
way, by decoupling the idea of open-ended search from only artificial
life worlds, the raw search for novelty can be applied to real world
problems. Counterintuitively, in the deceptive maze navigation task
in this paper, novelty search significantly outperforms objective-based
search, suggesting a surprising new approach to machine learning.
%@ 978-0-262-75017-2
@inproceedings{Lehman:2008:alife,
abstract = {This paper establishes a link between the challenge of solving highly
ambitious problems in machine learning and the goal of reproducing
the dynamics of open-ended evolution in artificial life. A major
problem with the objective function in machine learning is that through
deception it may actually prevent the objective from being reached.
In a similar way, selection in evolution may sometimes act to discourage
increasing complexity. This paper proposes a single idea that both
overcomes the obstacle of deception and suggests a simple new approach
to open-ended evolution: Instead of either explicitly seeking an
objective or modeling a domain to capture the open-endedness of natural
evolution, the idea is to simply search for novelty. Even in an objective-based
problem, such novelty search ignores the objective and searches for
behavioral novelty. Yet because many points in the search space collapse
to the same point in behavior space, it turns out that the search
for novelty is computationally feasible. Furthermore, because there
are only so many simple behaviors, the search for novelty leads to
increasing complexity. In fact, on the way up the ladder of complexity,
the search is likely to encounter at least one solution. In this
way, by decoupling the idea of open-ended search from only artificial
life worlds, the raw search for novelty can be applied to real world
problems. Counterintuitively, in the deceptive maze navigation task
in this paper, novelty search significantly outperforms objective-based
search, suggesting a surprising new approach to machine learning.},
added-at = {2017-03-16T11:50:55.000+0100},
address = {Winchester, UK},
author = {Lehman, Joel and Stanley, Kenneth O.},
biburl = {https://www.bibsonomy.org/bibtex/27ecd79167434e679d9b3a5ccf42a94cf/krevelen},
booktitle = {ALIFE XI: Proc. 11th Int'l Conf. on Artificial
Life},
editor = {Bullock, Seth and Noble, Jason and Watson, Richard and Bedau, Mark A.},
interhash = {01a4cd05ff185369c76757f064ce7188},
intrahash = {7ecd79167434e679d9b3a5ccf42a94cf},
isbn = {978-0-262-75017-2},
keywords = {imported thesis},
owner = {Rick},
pages = {329--336},
publisher = {MIT Press},
publisher_address = {Cambridge, MA, USA},
timestamp = {2017-03-16T11:54:14.000+0100},
title = {Exploiting Open-Endedness to Solve Problems Through the Search for
Novelty},
url = {http://eplex.cs.ucf.edu/papers/lehman_alife08.pdf},
year = 2008
}