next up previous
Next: Learning to Play Games Up: Background and Related Work Previous: Coevolution

Too Many Fitness Evaluations

The need to evaluate the fitness of a large number of individuals is a critical factor that restricts the range of application of GA's. In many domains, a computer can do these evaluations very fast; but in others, the time spent by this process may render the GA solution impractical. Examples of the latter case include a computer playing a game with people and trying to learn from experience or a robot attempting to complete a task in the physical world.

Robots that are reliable enough can run repeated trials of the same experiment over a long time in order to learn using evolutionary computation techniques. Floreano and Mondada [37,38] run their robots for several days in order to evolve controllers for basic tasks. Most evolutionary roboticists have preferred to rely on computer simulations to provide them with faster evaluations, but the crafting of appropriate simulators is also very difficult [98].

Evolution through interaction with humans faces similar difficulties. ``Blind watchmaker'' systems, where the user ranks every generation manually, have been successfully used to evolve shapes [30,86]; even with the extreme limitations imposed by the need to evaluate each individual manually (minimal population sizes, small number of generations) those results prove the great potential of evolution in a human-generated landscape.

But with a human in the loop, it is impossible to attain the large numbers of generations and evaluations employed in evolutionary experiments. Humans -- unlike robots -- get tired of repetitive tasks. Moreover, humans act irregularly; they may react differently each time when faced with the same situation more than once. If users provide fitness evaluations, adaptive software would need to be able to filter out such sources of ``noise'' provided naturally by human users.

We believe that the Internet, with millions of human users, could be fertile ground for the evolution of interactive adaptive software. Instead of relying on a few selected testers, the whole community of users together constitutes a viable gauge of fitness for an evolutionary algorithm that is searching to optimize its behavior.


next up previous
Next: Learning to Play Games Up: Background and Related Work Previous: Coevolution
Pablo Funes
2001-05-08