Effective Diversity Maintenance In Deceptive Domains

Diversity maintenance techniques in evolutionary computation are designed to mitigate the problem of deceptive local optima by encouraging exploration. However, as problems become more difficult, the heuristic of fitness may become increasingly uninformative. Thus, simply encouraging geno-typic diversity may fail to much increase the likelihood of evolving a solution. In such cases, diversity needs to be directed towards potentially useful structures. A representative example of such a search process is novelty search, which builds diversity by rewarding behavioral novelty. In this paper the effectiveness of fitness, novelty, and diversity maintenance objectives are compared in two evolutionary robotics domains. In a biped locomotion domain, geno-typic diversity maintenance helps evolve biped control policies that travel farther before falling. However, the best method is to optimize a fitness objective and a behavioral novelty objective together. In the more deceptive maze navigation domain, diversity maintenance is ineffective while a novelty objective still increases performance. The conclusion is that while genotypic diversity maintenance works in well-posed domains, a method more directed by phenotypic information, like novelty search, is necessary for highly deceptive ones. Copyright © 2013 ACM