In this article, the author claims that guiding evolution by novelty alone (without explicit goals) can solve problems even better than using explicit goals. In other words, using a novelty measure as a fitness function for a genetic algorithm works better than a goal-directed fitness function. How is that possible?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
As explained in an answer to this AI SE question, GAs are 'satisficers' rather than 'optimizers' and tend not to explore 'outlying' regions of the search space. Rather, the population tends to cluster in regions that are 'fairly good' according to the fitness function.
In contrast, I believe the thinking is that novelty affords a kind of dynamic fitness, tending to push the population away from previously discovered areas.
$\begingroup$
$\endgroup$
Novelty search selects for "novel behavior", by some domain-dependent definition of novelty. For example, novelty in a Maze-solving domain might be "difference of route explored". Eventually, networks that take every possible route through the maze will be found, and you could then select the fastest. This would work far better than a naive "objective", like distance to the goal, which could easily result in a local optima which never solves the maze.
From Abandoning Objectives: Evolution through the Search for Novelty Alone (emphasis mine):
In novelty search, instead of measuring overall progress with a traditional objective function, evolution employs a measure of behavioral novelty called a novelty metric. In effect, a search guided by such a metric performs explicitly what natural evolution does passively, i.e. gradually accumulating novel forms that ascend the complexity ladder.
For example, in a biped locomotion domain, initial attempts might simply fall down. The novelty metric would reward simply falling down in a different way, regardless of whether it is closer to the objective behavior or not. In contrast, an objective function may explicitly reward falling the farthest, which likely does not lead to the ultimate objective of walking and thus exemplifies a deceptive local optimum. In contrast, in the search for novelty, a set of instances are maintained that represent the most novel discoveries. Further search then jumps off from these representative behaviors. After a few ways to fall are discovered, the only way to be rewarded is to find a behavior that does not fall right away. In this way, behavioral complexity rises from the bottom up. Eventually, to do something new, the biped would have to successfully walk for some distance even though it is not an objective.
