Transcript The Genetic Algorithm - Villanova University

Monte Carlo Methods and
the Genetic Algorithm
Definitions and Considerations
John E. Nawn
MAT 5900
March 17th, 2011
What is the Genetic Algorithm?
Heuristic search method employing
randomness in order to determine the
optimal solution to a wide range of
problems
 Applications include:

◦
◦
◦
◦

Economics
Number Theory
Rankings
Path Length Determination (TSP, etc.)
Based in Neo-Darwinian theory
History of Genetic Algorithms
Operational Research (1940s and 1950s)
– birth of heuristics
 Evolutionsstrategie – Rechenberg and
Schwefel (1960s)
 Adaptation in Natural and Artificial Systems –
John Holland (1975)
 Increased computational complexity
(1990s – 2000s)

Evolution: A Survey
On the Origin of Species – Charles Darwin
(1859)
 Proposed natural selection – environment
creates selection pressure for individuals
in a species
 Selected advantages may be heritable:
provides method for determining fitness
of offspring
 What Darwin (and biologists) didn’t
know…

Genetics: A Survey
Gregor Mendel (1863)
 Individuals within a species carry
directions for their promulgation
 Segregation (First Law)
 Independent Assortment (Second Law)
 Increasing technology and the discovery
of mutations and crossovers
 Genotype and phenotype

Terminology

Population
◦ Set of possible solutions in any given
generation

Chromosomes
◦ Basic units that undergo reproduction in the
algorithm
◦ Two types: binary and non-binary
◦ Minimum size requirements
◦ Genes and alleles

Reproduction
Terminology

Mutation
◦ Process of changing allele values in a
chromosome
◦ Inversions
◦ How often?
◦ What type?

Crossover
◦ Process of combining parental chromosomes
to yield new chromosomes
◦ What type?
Terminology

Selection
◦ Criterion
◦ Fitness functions
◦ Reeves and Rowe:
 Tournament selection
 Ranking

Termination
◦ Diversity thresholds
◦ Generation limits
◦ Computational limits
Minimum String Length Requirements
Reeves, Colin R.; p. 28
Mutations
Simplicity of method
 Binary

◦ Reversal of alleles

Non-binary
◦ Stochastic selection of new alleles
◦ Differing mutation rates
◦ Selecting complete mutations and error repair
Crossovers (X)

Binary
◦ NX – N-point crossovers
◦ UX – Uniform crossover, or linear operator
“masks”

Non-Binary
◦ Difficulty in applying n-point crossovers
◦ PMX – Partially matched crossover
◦ UX – “in/out” order crossovers

Further possibilities – Fox/ McMahon and
Poon/ Carter
Fitness Functions
Method comparing gene success
 Roulette wheel model of selection
 Selection pressure =

individual fitness/ total fitness
Benefit of larger selection pressure
 Niches

Critiques of the Genetic Algorithm:
Biological and Philosophical Arguments
What is natural selection selecting for?
 Evolution as a theory or fact: Lisa Gatlin
 Individual genes and group interactions
 Lamarckian or Darwinian evolution?

Critiques of the Genetic Algorithm:
Mathematical Arguments
Lack of theory in heuristic applications
 Newton’s Method problem
 Best possible solution or best solution?
 Pseudo-randomness
 Similarities to Markov chains and
processes (a.k.a. t – 1 dependency)

What to Expect Next
Crossover possibilities
 Holland’s method - schemata approaches
 Three applications:

◦ General Path Problems or the Traveling
Salesman Problem (TSP)
◦ Ranking Styles
◦ Stock Selection
Selected Bibliography
Craig, Nancy L. et. al. Molecular Biology: Principles of
Genome Function. New York: Oxford University
Press, 2010. Print.
 Krzanowski, Roman and Jonathan Raper. Spatial
Evolutionary Modeling. New York: Oxford University,
Inc., 2001. Print.
 Reeves, Colin R. and Johathan E. Rowe. Genetic
Algorithms: Principles and Perspectives: A Guide to GA
Theory. Boston: Kluwer Academic Publishers,
2003. Print.
 Russell, Peter J. iGenetics: A Mendelian Approach. San
Francisco: Pearson Education, Inc., 2005. Print
