Transcript Genetic Algorithms

Genetic
Algorithms
By: Anna Scheuler and Aaron Smittle
What is it?
● appeared in the 1950s and 1960s
● used to find approximations in search
problems
● use principles of natural selection to find
an optimized solution
● part of evolutionary algorithms
Evolutionary Algorithms
•
•
•
subset of evolutionary computation
generic, population based optimization
algorithms
uses aspects of biology
Biology → Genetic Algorithms
•
•
•
•
•
•
Gene = smallest unit of data
o
represented in binary
Genome = string of genes
Genome pool = set of genomes
o
represents the population
Mutation
Crossover
Inheritance
The Fitness Function
•
•
Loops through every gene of every
member
Two main classes:
o
o
no change
mutable
The Algorithm
1. Randomly generate an initial population
2. Run fitness function
3. Define parameters for “strong” members
4. Create new generation
5. Introduce mutation
6. Repeat
A simple algorithm runs in O(g*n*m)
GAs and Gaming
•
•
Opponent
adaptation
Towers of
Reus
Star Craft’s Evolution Chamber
•
•
Created in 2010 for
Zerg
user inputs goal and
the app generates
the build order
Card Problem Example
● There are 10 cards numbered 1-10.
● There must be two piles
○
○
The sum of the first pile must be as close as
possible to 36
The product of the second pile must be as close
as possible to 360
Card Problem cont.
● Genome is the way the cards are divided
● Algorithm begins by picking two genomes
at random
● They are compared with Fitness test
● Copy winner into loser and mutate with
random probability at each gene
Card Problem Fitness Function
Card Problem
● This problem used a Microbial GA
This type of genetic algorithm features ‘free’
elitism
○ Relatively simple core code
○
An example
http://rednuht.org/genetic_cars_2/
Issues
•
•
•
The fitness function must be carefully written
Members can get lost
Population can converge with similar traits
Questions?