Critical factors in the performance of novelty search
Critical factors in the performance of novelty search
复制标题
新颖性搜索性能的关键因素
DOI：
10.1145/2001576.2001708
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Shimon Whiteson
中科院分区：
文献类型：
--
作者：
S. Kistemaker;Shimon Whiteson
新奇搜索是最近提出的一种进化计算方法，旨在避免欺骗的问题，其中的适应度函数引导搜索过程远离全局最优。新奇搜索用新颖性选择取代了基于适应度的选择，新颖性是通过将个体的行为与当前人群和过去新奇个体的档案进行比较来衡量的。虽然有大量的证据表明，新奇搜索可以克服欺骗的问题，其性能的关键因素仍然知之甚少。本文通过分析将每个基因型映射到行为的行为函数如何影响绩效，来帮助弥合这一差距。我们提出了后代适应度概率（DFP）的概念，它描述了基因型的后代有多大可能具有一定的适应度，并根据这些变化对行为和DFP的影响，制定了两个关于行为函数的变化何时会提高新奇搜索性能的假设。在人工和欺骗性迷宫领域的实验为这些假设提供了大量的经验支持。
Novelty search is a recently proposed method for evolutionary computation designed to avoid the problem of deception, in which the fitness function guides the search process away from global optima. Novelty search replaces fitness-based selection with novelty-based selection, where novelty is measured by comparing an individual's behavior to that of the current population and an archive of past novel individuals. Though there is substantial evidence that novelty search can overcome the problem of deception, the critical factors in its performance remain poorly understood. This paper helps to bridge this gap by analyzing how the behavior function, which maps each genotype to a behavior, affects performance. We propose the notion of descendant fitness probability (DFP), which describes how likely a genotype's descendants are to have a certain fitness, and formulate two hypotheses about when changes to the behavior function will improve novelty search's performance, based on the effect of those changes on behavior and DFP. Experiments in both artificial and deceptive maze domains provide substantial empirical support for these hypotheses.