Abandoning Objectives: Evolution Through the Search for Novelty Alone
Abandoning Objectives: Evolution Through the Search for Novelty Alone
复制标题
DOI：
10.1162/evco_a_00025
复制
发表时间：
2011-06-01
影响因子：
6.8
通讯作者：
Stanley, Kenneth O.
中科院分区：
文献类型：
--
作者：
Lehman, Joel;Stanley, Kenneth O.
在进化计算中，适应度函数通常测量搜索空间中目标的进展，有效地充当目标函数。通过欺骗，这种目标函数实际上可能会阻止目标的实现。虽然存在减轻欺骗的方法，但它们没有处理潜在的病理：目标函数本身可能会主动将搜索引向死胡同。本文提出了一种规避欺骗的方法，也为开放式进化提供了新的视角。我们的想法不是明确地寻求目标或模拟自然进化来捕捉开放性，而是简单地寻找行为新颖性。即使在基于目标的问题中，这种新颖性搜索也会忽略目标。由于搜索空间中的许多点都崩溃为单一行为，因此对新颖性的搜索通常是可行的。此外，由于简单的行为只有这么多，对新奇事物的追求会导致复杂性的增加。通过将开放式搜索与人工生活世界解耦，对新颖性的搜索适用于现实世界的问题。与直觉相反，在本文的迷宫导航和双足步行任务中，新颖性搜索显着优于基于目标的搜索，这表明了一个奇怪的结论，即某些问题最好通过忽略目标的方法来解决。主要的教训是基于目标的范式的固有局限性以及通过其他方式指导搜索的未开发机会。
In evolutionary computation, the fitness function normally measures progress toward an objective in the search space, effectively acting as an objective function. Through deception, such objective functions may actually prevent the objective from being reached. While methods exist to mitigate deception, they leave the underlying pathology untreated: Objective functions themselves may actively misdirect search toward dead ends. This paper proposes an approach to circumventing deception that also yields a new perspective on open-ended evolution. Instead of either explicitly seeking an objective or modeling natural evolution to capture open-endedness, the idea is to simply search for behavioral novelty. Even in an objective-based problem, such novelty search ignores the objective. Because many points in the search space collapse to a single behavior, the search for novelty is often feasible. Furthermore, because there are only so many simple behaviors, the search for novelty leads to increasing complexity. By decoupling open-ended search from artificial life worlds, the search for novelty is applicable to real world problems. Counterintuitively, in the maze navigation and biped walking tasks in this paper, novelty search significantly outperforms objective-based search, suggesting the strange conclusion that some problems are best solved by methods that ignore the objective. The main lesson is the inherent limitation of the objective-based paradigm and the unexploited opportunity to guide search through other means.