Podcast Beta
Questions and Answers
What type of crossover operator is used in the SGA approach?
What is the population size in the SGA approach?
What type of mutation operator is used in the SGA approach?
What is the purpose of the selection mechanism in the SGA approach?
Signup and view all the answers
How are the individuals represented in the SGA approach?
Signup and view all the answers
What is a shortcoming of the SGA approach?
Signup and view all the answers
What type of selection mechanism is used in the SGA approach?
Signup and view all the answers
What is the survivor selection mechanism used in the SGA approach?
Signup and view all the answers
What is the purpose of the initialization step in the SGA approach?
Signup and view all the answers
What is a key difference between classical AI approaches and evolutionary approaches to the EIGHT-QUEENS problem?
Signup and view all the answers
Study Notes
Simple Genetic Algorithm (SGA)
- Representation: Bit-Strings
- Recombination: 1-Point Crossover
- Mutation: Bit-Flip
- Parent Selection: Fitness Proportional - implemented by the Roulette-Wheel
- Survivor Selection: Generational
Reproduction Cycle of SGA
- Select parents (with duplication) for the mating pool (size of mating pool = population size)
- Shuffle the mating pool
- Apply crossover for each consecutive pair with probability pc (and the children replace the parents immediately)
- Apply mutation for each offspring (bit-flip with probability pm independently for each bit)
- Replace the whole population with the resulting offspring
Suitable Values for SGA Parameters
- Mutation rates: between 1/l and 1/μ
- Crossover probabilities: around 0.6 - 0.8
- Population sizes: in the fifties or low hundreds
Maximize x Problem
- Simple problem: maximize x^2 over the integers in the range {0, 1, ...}
- Can be solved using SGA
Evolutionary Algorithm Variants
- Genetic Programming
- Evolutionary Strategy
- Differential Evolution
- Swarm-Intelligence based algorithms:
- Ant Colony Optimisation
- Particle Swarm Optimisation
- Gravitational Search
- etc.
- Physics/Chemistry-based algorithms:
- Simulated Annealing
- etc.
- Bio-Inspired algorithms:
- Dolphin Echolocation
- Flower Pollination Algorithm
- etc.
Genetic Algorithms (GAs)
- Developed in the 1960s
- Initially conceived by J.Holland as a means of studying adaptive behavior
- Most widely known type of EAs
- Widely used for teaching EAs and is the first EA many people encounter
Shortcomings of SGA
- Representation is too restrictive
- Mutation & Crossover operators only applicable for bit-string & integer representations
- Selection Mechanisms are sensitive for converging populations with close fitness values
- The Generational Population Model can be improved with explicit survivor selection (for instance, elitism)
EIGHT-QUEENS Problem
- Can be solved using evolutionary approach
- Classical AI approaches to this problem work in a constructive, or incremental, fashion
- Evolutionary approach is drastically different because it is not incremental
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
This quiz explores the technical summary of Simple Genetic Algorithm (SGA) variants, including representation, recombination, mutation, and selection methods. Learn about the traditional workflow and reproduction cycle of SGA.
