A common feature of traditional GAs and GPs is that the ``fitness function'' evaluates the genomes in isolation from the other members of the population. The genomes interact only with the fitness function (and in some cases the data), but not with each other. This arrangement precludes the evolution of collective solutions to problems, which can be very powerful.
The example of Sims' creatures competing for possession of blocks is the first case we have considered where there is any direct interaction between the members of the evolving population(s). In this and the following sections we will consider other examples involving such interactions.
Hillis [10] used genetic algorithms to evolve algorithms for sorting lists of sixteen numbers. The fitness of these algorithms was evaluated on the basis of the percentage of test lists that they could sort correctly. He found this evolutionary process to be inefficient because fairly quickly, evolution produced sort algorithms that could correctly sort most lists. Therefore, most of the test lists produced no discrimination for selection to act on. Also there was a tendency for evolution to get stuck on ``local optima'' from which evolutionary hill climbing could not progress.
In an effort to improve the efficiency of the process, he allowed the test lists to be determined by a co-evolving set of genetic algorithms. The fitness of the test lists was the inverse of the fitness of the sort algorithms: the number of sort algorithms that could not correctly sort the list.
In the system where the sort algorithms and the test lists co-evolved, the evolution of the sort algorithms was much more efficient (in terms of the computational effort required), and was able to ultimately produce shorter sort algorithms than were produced without co-evolution. It was also noted that with co-evolution, the sort algorithms did not show a tendency to get stuck on local optima.