GEP Book   Home   News   Author   Q&A   Tutorials   Downloads   GEP Biblio   Contacts   Visit Gepsoft

C. FERREIRA In A. Abraham, J. Ruiz-del-Solar, and M. Köppen (eds), Soft Computing Systems: Design, Management and Applications, pp. 153-162, IOS Press, Netherlands, 2002. Analyzing the Founder Effect in Simulated Evolutionary Processes Using Gene Expression Programming Introduction   Everybody agrees that, by and large, evolution relies on genetic variation coupled with some kind of selection and, in fact, all evolutionary algorithms explore these fundamental processes. However, there is no agreement concerning the best way to create genetic variation, with researchers divided between mutation and recombination [1, 4, 6, 7, 8, 9, 12]. This fact per se is extremely revealing, suggesting that existing artificial systems are fundamentally different from one another. Particularly interesting is that the evolvability of the system will depend heavily on the kind of genetic operator used to create variation. And the size and kind of initial populations is closely related to this question. In all evolutionary algorithms, an evolutionary epoch or run starts with an initial population. Initial populations, though, are generated in many different ways, and the performance and the costs (in terms of CPU time) of different algorithms depend greatly on the characteristics of initial populations. The simplest and less time consuming population is the totally random initial population. However, few evolutionary algorithms are able to use this kind of initial population due not only to structural constraints but also to the kind of genetic operators available to create genetic modification. The initial populations of gene expression programming (GEP) are totally random and consist of the linear genomes of the individuals of the population [4]. Gene expression programming is a genotype/phenotype system that evolves computer programs of different sizes and shapes (expression trees) encoded in linear chromosomes of fixed length. The genetic encoding used in GEP allows a totally unconstrained interplay between chromosomes and expression trees. This interplay brought about a tremendous increase in performance allowing, consequently, the undertaking of detailed, much needed analysis of fundamental evolutionary processes. One such analysis is the importance of the initial diversity in evolution. Ernst Mayr hypothesized that, in nature, small groups of founder individuals can give rise to a new species [10, 11]. This is only possible, however, due to the variety of genetic operators that continually introduce genetic modification in the population. The initial diversity question is extremely important in artificial evolutionary systems where founder events are created each time a run starts. And the efficiency of the system will depend, among other things, on how the system deals with evolutionary bottlenecks. Indeed, the evolutionary strategies followed by different artificial evolutionary systems depend greatly on the nature of their respective initial populations. In GEP, due to the existence of a truly functional and autonomous genome, the implementation of different genetic operators is extremely simplified and Ferreira [4] introduces seven. Furthermore, due to the high efficiency of the algorithm, the performance and the roles of all these operators can be easily and rigorously analyzed revealing the existence of two fundamental types of evolutionary dynamics: non-homogenizing dynamics found in populations undergoing mutation or other non-conservative operators, and homogenizing dynamics found in populations undergoing recombination alone [5]. Therefore, systems with different evolutionary behaviors can be easily simulated in GEP. In this work, the importance of the initial diversity is analyzed in two different systems. The first evolves under mutation and has a non-homogenizing dynamics characteristic of an efficient adaptation. The second evolves under recombination and has a homogenizing dynamics characteristic of poorly evolving systems. Home | Contents | Previous | Next