Catalogue of Artificial Intelligence Techniques
Keywords: algorithm, allele, binary string, canonical, chromosome, constant, elitism, evolution, fitness value, generation, genetic, genotype, hybridisation, mating pool, mutated, phenotype, population, random crossover, recombination, simple
Author(s): Rachael Smith
Genetic algorithms (GAs) are evolution based search algorithms, which are typically used for finding approximate solutions to complex problems where there are too many potential solutions to consider in a reasonable amount of time. A solution is found by using the best solutions found so far to generate improved solutions. Solutions (individuals) are generally represented as binary strings. The string represents a genotype (combination of alleles) in natural evolution, with the value of each digit being an allele (DNA sequence). The meaning of the string (or chromosome) is called the phenotype. A Canonical/Simple GA performs a sequence of steps. First it initialises the genotype of each individual with random alleles then evaluates the corresponding phenotype,giving it a fitness value (a rating of how well it solves the problem). This value determines how many copies of the individual are placed in the “mating pool” with the “fittest” individuals having the most copies, making them more likely to be selected and, therefore, directing the search towards the better solutions. Two parents are randomly selected and random crossover is used to generate offspring composed of elements from each of the parents (this corresponds to potential solutions being combined and is also called recombination). An example of the result of random crossover between the parents with genotypes 11111 and 00000 would be the children with genotypes 11100 and 00011. The parents are then discarded, keeping the population constant. With a low probability, the children are mutated, this usually means changing one allele, creating greater variability in the population (e.g. 11100 becomes 11101). Offspring are generated until the population is filled, then the process is repeated until a solution is found or it has been run for the specified maximum number of generations. More advanced GAs are needed to find solutions to difficult problems. These can involve hybridisation and elitism, where fit individuals can survive for more than one generation. The closer the algorithm becomes to natural evolution, the more difficult the problems it can solve.
- William M. Spears, Evolutionary Algorithms. The Role of Mutation and Recombination, Springer, 2000.
- Zbigniew Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1999.
- Thomas Bäck, ed., Proceedings of the seventh International conference on Genetic Algorithms, Morgan Kaufman Publishers, 1997.
- Peter J. Bentley, David W. Corne, ed., Creative Evolutionary Systems, Morgan Kaufman Publishers, 2002.