Genetic Algorithms I: Core Mechanics
Genetic Algorithms
What Is a Genetic Algorithm?
A genetic algorithm is an evolutionary method that typically uses selection, crossover, and mutation on a population of encoded solutions. It is especially common for discrete or combinatorial problems, though it can also handle continuous variables.
GA Components
Encoding Choices
Binary encoding is classic, but many modern GAs use integer, permutation, or real-valued encodings depending on the problem structure. Good encoding makes valid solutions easier to produce and evaluate.
Canonical GA Pseudocode
-
1
Step 1: Initialize a population of encoded chromosomes.
-
2
Step 2: Evaluate each chromosome's fitness.
-
3
Step 3: Select parents from the population.
-
4
Step 4: Apply crossover to create offspring.
-
5
Step 5: Mutate offspring.
-
6
Step 6: Replace part or all of the population.
-
7
Step 7: Repeat until a stopping condition is met.
Mutation vs Crossover
Mutation
- Introduces new variation
- Works on one parent at a time
- Helps escape local optima
Crossover
- Mixes information from two parents
- Exploits useful building blocks
- Depends on a meaningful encoding
Which operation combines information from two parents?
Crossover recombines parent information into offspring.
Correct answer: Crossover
What is one reason encoding matters in a GA?
A good representation supports efficient search.
Correct answer: It affects whether valid and useful solutions are easy to produce.
Which is most likely to be a chromosome in a GA for the traveling salesperson problem?
TSP solutions are commonly represented as permutations.
Correct answer: A permutation of cities
Practical Tip
When crossover frequently creates invalid offspring, improve the representation or use specialized repair operators.
Simple GA Example
Suppose we maximize over a bounded integer range. A GA may encode as a bit string, decode it to an integer, evaluate , and prefer candidates with larger values.