Transcript Genetic Search Algorithms

Genetic Search
Algorithms
Matt Herbster
Why Another Search?
 Designed in the 1950s, heavily
implemented under John Holland (1970s)
 Genetic search is intended to simulate
natural systems
 Works best on continuous and discrete
combinatorial problems
 It will only take eight minutes of your time
Definitions






Chromosome
Gene
Allele
Locus
Genotype
Phenotype






String
Feature, character
Feature value
String position
Structure
Parameter set
Characteristics
 Reproduction
 Crossover
 Mutation
 Rarely used
Mutation Operations
Generative
Swap Sequence
Swap Node
Destructive
Crossover Operations
Order based
Single point
Other Representations




Array, matrix
Tree
String of bits
Any other data structure
Implementation
1. Start with an initial gene pool
2. Generate successors (either randomly
or deterministically) to create the first
generation pool
3. Each node is evaluated by a fitness
function and sorted accordingly
4. Create new generations with the better
most likely to reproduce
What is the meaning of
the word better?
 As determined by fitness function
(essentially a heuristic)
 Nodes with desired genes are
predetermined
 Can often approach local maxima rather
than the global optimal solution
 Assisted by random-restart hill climbing
Variations
 Genetic algorithms produce optimal
results for many problems, eventually …
 Speciation – Two nodes will reproduce
only if closely related
 Technique helps improve speed
 Parallel populations – simulates physical
separation with possible migration
Applications
 Traveling salesman problem
 Drilling of printed circuit boards
 Planning bus routes
 Scheduling
 Computer games – represent an
evolution of players’ strategies
 Stock market trading – data fitting, trend
spotting, budgeting
Questions