2 Genetic Programming Distributed Models

Much of the effort in distributed models in genetic programming focus on increasing efficiency or adding computational resources by means of parallelisation. Andre and Koza (1996) used a transputer architecture for the Even-5-Parity problem where each processor was responsible for the fitness evaluation and breeding of a subpopulation. This work is representative of the author's many large scale parallel implementations, e.g. [Koza et al., 1999]. Tongchim and Chongstitvatana (2000) compared a parallel implementation with a coarse grain island model for a robot control problem, comparing synchronous and asynchronous versions. The authors previously showed that the standard island model gave a near linear speedup with the increase of processors, with degradation arising from communication and the synchronous issues [Tongchim and Chongstitvatana, 1999]. Fernandez et al. (2000, 2001, 2003) studied various control parameters for multipopulation models. Populations were homogeneous and migration selection and replacement were based on fitness, where migrants were copies, increasing selection pressure. Results highlighted the need of subpopulations to be have enough individuals to perform effective search.

Punch (1998) looked at conflicting reports of the effectiveness of multiple populations for genetic programming, extending earlier work by Punch et al. (1996) where multiple population on the Ant and Royal Tree problems showed little improvement. Andre and Koza (1996) previously showed super linear speedup on the Even-5-Parity problem. Problems with multiple solutions, such as the Parity problem, are thought to be good for multiple population models. However, deceptive problems are thought to be harder for multiple population models that evenly divide the total population over several processors. Punch tested this hypothesis on a sequencing problem and showed the negative effects deception can cause with multipopulation models. Stoffel and Spector (1996) showed improved results on a regression problem using a stack representation with the population evenly distributed across processors. Lastly, Iwashita and Iba (2002) proposed an island model using two types of crossover, depth dependent and standard, to simulate local and global search. New individuals in an island undergo depth-dependent crossover to prevent the destructive effects of standard crossover.

Juill$\acute{e}$ and Pollack (1996) used a parallel deme model of genetic programming. The island model consisted of a 2-D wrap-around mesh. Parents were selected locally and offspring replaced the least fit individual. Migrants were chosen from the subpopulation randomly. Poli and Page (2000) used demes to solve high-order Boolean Parity problems. To maintain diversity while increasing efficiency, the model only kept individuals with different fitnesses. An elitist approach distributed individuals with high fitness quickly among different demes. Langdon (1998a) used demes similar to Collins (1992) in a stepping stone model. The author reported that the deme implementation provided better results than panmictic genetic programming when evolving a queue and a list and on the balanced bracket problem. Tackett and Carmi (1994) studied different forms of breeding and population configurations for classification of the donut problem. Demes were formed by distributing the population over a grid. This model was shown to improve the generalization of solutions.

D'haeseleer and Bluming (1994) used genetic programming in an ALife scenario to study population dynamics. A tank problem, where tanks compete against each other for survival and participate in breeding and selection, allowed the authors to track genotypes and witness the emergence of demes. The authors pointed out that:

``Whereas the concepts of natural selection and survival of the fittest are commonly referred to in evolutionary programming literature, the role of sub population isolation in species differentiation is cited less frequently. Identifying the environment of an individual, including the members of its local population, as a primary influence on the continued development of the local sub population as well as the species as a whole is an important step toward more realistic modelling of evolutionary mechanics.''

Each individual produced a behavior signature (for phenotype diversity) that described their performance after competing against thirteen seed tanks. A genotypic diversity was measured by comparing the frequency of terminals and functions in individuals. The tank individuals competing against neighbors showed the emergence of demes, where a deme is a local population, by means of a correlation measure for phenotypes and genotypes. Parents and offspring were selected and inserted locally.