The Genetic Algorithm in Computer Science - MIT Mathematics

The Genetic Algorithm in Computer Science Eric Krevice Prebys Abstract. The genetic algorithm is described, including its three main steps: selection, crossover, and mutation. This description is used in the presentation of two methods for analyzing genetic algorithms: schema analysis and mathematical modeling. The discus- sion of schema analysis focuses on the Schema Theorem. Following it, an exact mathe- matical model is described. First, the model is presented assuming an in nite population. Then the model is made more accurate

by assuming a nite population. 1. Introduction. All life on Earth is thought to evolve. Genetic algorithms are com- puting algorithms constructed in analogy with the process of evolution [1]. Genetic algorithms seem to be useful for searching very general spaces and poorly de ned spaces. It is hoped that, through more rigorous theoretical study, we will determine what sorts of spaces genetic algorithms can search e ciently. In biology, the gene is the basic unit of genetic storage [5]. Within cells, genes are strung together to form chromosomes. The simplest possible sexual reproduction is between single-cell organisms. The two cells fuse to produce a cell with two sets of chromosomes, called a diploid cell. The diploid cell immediately undergoes meiosis. In meiosis, each of the chromosomes in the diploid cell makes an exact copy of itself. Then the chromosome groups (original and copy) undergo crossover with the corresponding groups, mixing the genes somewhat. Finally the chromosomes separate twice, giving four haploid cells. Mutation can occur at any stage, and any mutation in the chromo- somes will be inheritable. Mutation is essential for evolution. There are three types relevant to genetic algorithms: point mutations where a single gene is changed, chromo- somal mutations where some number of genes are lost completely, and inversion where a segment of the chromosome becomes ipped. ThispaperfollowsMelanieMitchell’sbook[3]. Wewillintroduceasimpli edgenetic algorithm using the notions of sexual reproduction. This algorithm captures most of the essential components of every genetic algorithm, so we will call it the Standard Genetic Algorithm. A simple way to view the Standard Genetic Algorithm is provided by schema. With them we can understand the Schema Theorem. It explains how crossover allows a genetic algorithm to zero in on an optimal solution. However, schema are inadequate in determining some characteristics of the population. Speci cally, in determining the speed of population convergence, and the distribution of the population over time. To deal with these issues, we will develop an exact mathematical model, rst assuming an in nite population, and then a nite population. This model was originally presented by Michael Vose and G.E. Liepins in [2] and [7]. More details are found in two papers by Allen Nix and Michael Vose, [4] and [8]. In practice, the genetic algorithms used are much more complex then the Standard Genetic Algorithm. Consequently, the analyses presented in this paper have some major weaknesses. Speci cally, schema analysis...

Website: www-math.mit.edu | Filesize: -
No of Page(s): 6
Download The Genetic Algorithm in Computer Science - MIT Mathematics.pdf