Lab 04
Genetic Algorithms
Overview of the lab
- Introduction to Genetic Algorithms
- Main steps in Genetic Algorithms
- GA in action: Travelling Salesman Problem
💡 Words like chromosome or selection pressure are key terms — hover or tap them for a definition.
Introduction to Genetic Algorithms
- A search and optimization technique inspired by natural evolution.
- Uses the principles of selection, crossover, and mutation.
- Evolves a population of possible solutions to find the best (fittest) one.
Each solution (often called an individual or chromosome) is represented by a set of parameters — similar to genes in biology. The fitness of each individual measures how well it solves the problem at hand.
Key concepts
Gene
A single parameter or feature that defines part of a solution.
Example: weight, value, or decision variable
Chromosome
A complete set of genes; represents one potential solution.
Example: [x₁, x₂, x₃, …]
Population
A group of chromosomes; represents many solutions being tested at once.
Main steps in Genetic Algorithms
Initialization (Population) → Selection (Fitness Function) → Crossover → Mutation — repeated generation after generation until the population converges.
Selection
Selection is the stage of a genetic algorithm in which individual chromosomes are chosen from a population for later breeding (using the crossover operator).
In genetic algorithms, selection pressure refers to how strongly the algorithm favors the best-performing individuals when choosing who gets to reproduce and create the next generation — the degree of bias towards fitter individuals in the selection process.
High selection pressure
Strongly favors the best individuals → faster convergence, but risk of premature convergence (loss of diversity, stuck in local optima).
Low selection pressure
Individuals are chosen more randomly → slower convergence, but better exploration of the search space (more genetic diversity).
All examples below use the same population: A–E with fitness 10, 20, 30, 25, 15 (higher is better).
Roulette Wheel 🎯
Chromosomes are selected with a probability proportional to their fitness. Imagine a roulette wheel where each chromosome has a slot size corresponding to its fitness value; fitter individuals have larger slots and are more likely to be selected.
probability = individual fitness / total fitness
- Calculate the total fitness of the population.
- Compute each individual's selection probability = (individual fitness / total fitness).
- Spin the wheel (generate a random number) to select individuals based on these probabilities.
| Pros | Cons |
|---|---|
| Simple | Premature convergence if a single individual is overwhelmingly fit (takes over the wheel). |
| Works well when fitness differences are moderate. | Sensitive to scaling: small differences in fitness can have a large effect. |
Stochastic Universal Sampling (SUS) 🎲
A variation of roulette wheel selection that ensures a more even and consistent spread of selected individuals. Imagine the roulette wheel as before, but instead of one spin, place multiple evenly spaced pointers on it (equal to the number of parents needed). Spin the wheel once — all pointers select individuals simultaneously.
| Pros | Cons |
|---|---|
| Reduces randomness in selection (less variance). | Slightly more complex to implement than standard roulette selection. |
| Ensures even sampling proportional to fitness. |
Selected this spin
Tally — how often each was selected vs. expected share
roulette_wheel_selection.py Python
import numpy as np
population = ['A', 'B', 'C', 'D', 'E']
fitness_scores = [10, 20, 30, 25, 15] # higher is better
def roulette_wheel_selection(population, fitness_scores, num_selections):
total_fitness = sum(fitness_scores)
selection_probs = [f / total_fitness for f in fitness_scores]
selected_chromosomes = np.random.choice(population, size=num_selections, replace=True, p=selection_probs)
return selected_chromosomes
selected = roulette_wheel_selection(population, fitness_scores, 3)
print("Selected chromosomes:", selected)replace controls whether the same element can be chosen more than once:
replace=True→ sampling with replacement: the same chromosome can be selected multiple times; after one is chosen, it's still "available". This is common in genetic algorithms, because the most fit individuals can be selected more than once (proportional to their selection probability).replace=False→ sampling without replacement: once an element is chosen, it cannot be selected again, so all selected chromosomes are unique.
Tournament Selection 🏆
Randomly select a small group (a "tournament") of individuals and pick the best one from that group to be a parent. Selection pressure can be controlled by changing k:
- Larger k → stronger selection pressure (more elitist).
- Smaller k → more diversity.
| Pros | Cons |
|---|---|
| Easy to implement. Selection pressure can be controlled by changing k. | May lose diversity if tournament size is too large. |
Winners so far
tournament_selection.py Python
# Implementation of Tournament Selection with indexes
def tournament_selection(population, fitness_scores, tournament_size, num_selections):
selected_chromosomes = []
for _ in range(num_selections):
# choose random indexes of chromosomes from the population for the tournament
tournament = np.random.choice(len(population), tournament_size, replace=False)
# chromosomes in the tournament
selected_population = [population[i] for i in tournament]
print("Tournament participants:", selected_population)
print("Fitness scores:", [fitness_scores[i] for i in tournament])
# select the index of best chromosome from the tournament
winner = tournament[np.argmax([fitness_scores[i] for i in tournament])]
print("Tournament winner:", population[winner])
selected_chromosomes.append(population[winner])
return selected_chromosomes
selected = tournament_selection(population, fitness_scores, tournament_size=3, num_selections=3)
print("Selected:", selected)Rank-Based Selection
Instead of using raw fitness values, individuals are ranked according to fitness. The selection probability depends on rank, not the absolute fitness.
- Sort the population by fitness (best to worst).
- Assign selection probabilities based on rank (e.g., linearly or exponentially decreasing).
- Select individuals using these rank-based probabilities.
| Pros | Cons |
|---|---|
| Prevents domination by one very fit individual. | Can be slower to converge because it reduces differences between individuals. |
| Maintains steady selection pressure. |
Selection probability of each individual — roulette (fitness-proportional) vs. rank-based (ranks 1…5).
rank_based_selection.py Python
def rank_based_selection(population, fitness_scores, num_selections):
# Rank individuals based on fitness
sorted_indices = np.argsort(fitness_scores)
sorted_fitness = [(i, fitness_scores[i], population[i]) for i in sorted_indices]
print("Sorted indices and their scores:", sorted_fitness)
ranks = np.arange(1, len(fitness_scores) + 1)
print("Ranks:", ranks)
probs = ranks / np.sum(ranks)
print("Selection probabilities:", probs)
print("Elements by rank: ", np.array(population)[sorted_indices])
chosen = np.random.choice(np.array(population)[sorted_indices], size=num_selections, p=probs)
return chosen
selected = rank_based_selection(population, fitness_scores, num_selections=3)
print("Selected chromosomes:", selected)numpy.arange([start,] stop[, step,] dtype=None) creates an array with evenly spaced values within a given range — similar to Python's built-in range(), but returns a NumPy array instead of a list. A Python list can store mixed data types; in a NumPy array all elements must have the same data type (NumPy will try to cast them to a common type).
Elitism
The best individuals from the current generation are automatically passed to the next generation, without alteration (elitism).
| Pros | Cons |
|---|---|
| Guarantees that the best solutions are preserved. | Reduces diversity. |
| Improves convergence speed. |
Truncation Selection
Select only the top fraction of the population (e.g., top 30%) based on fitness. All selected individuals have equal probability of being parents.
- Sort population by fitness.
- Keep only the top percentage (say, best 20–50%).
- Randomly select parents from this truncated set.
| Pros | Cons |
|---|---|
| Very simple and deterministic. | Can quickly reduce genetic diversity. |
| Strong selection pressure (fast convergence). | May get stuck in local optima. |
Summary of selection methods
| Method | Key idea | Strength | Weakness |
|---|---|---|---|
| Roulette Wheel | Prob. proportional to fitness | Simple | Premature convergence |
| Tournament | Best of random subset wins | Adjustable pressure | Can lose diversity |
| Rank-Based | Selection by rank | Stable pressure | Slower convergence |
| SUS | Evenly spaced roulette sampling | Low variance | More complex |
| Elitism | Best always survive | Guarantees progress | Less diversity |
| Truncation | Top % survive | Simple & strong pressure | Fast loss of diversity |
Crossover
Crossover is a process of taking more than one parent solution and producing a child solution from them.
There are a lot of types of crossover, such as:
| Binary coded | Real coded | Order coded |
|---|---|---|
| Single Point | Linear | Partially-Mapped |
| Two-Point | Single Arithmetic | Cycle |
| Multi-Point | ||
| Uniform | ||
| Shuffle |
One-point crossover
For order-coded chromosomes (permutations), copy the first part from one parent, then fill the remaining values in their order from the other parent — so no value is repeated. Drag the crossover point:
Uniform crossover
Getting a gene from one of the parents randomly! A random mask decides, gene by gene, which parent child 1 takes from; child 2 takes from the other parent.
Mutation
A mutation makes a small random change to a single chromosome, which keeps diversity in the population. Three common operators for order-coded chromosomes:
GA in action: Travelling Salesman Problem
Everything together. Each chromosome is a tour — a permutation of the cities — and fitness is higher for shorter tours. Every generation: keep the 2 best tours (elitism), pick parents by tournament selection (k = 3), combine them with the one-point order crossover from above, and mutate each child with the chosen operator.
Best tour length per generation
Population of 60 tours over 14 cities. Try a mutation rate of 0 — without mutation the population loses diversity and often gets stuck early (premature convergence).
20 auto-graded tasks, 100 points: GA terminology, selection pressure, roulette wheel and SUS, tournament, rank, elitism and truncation, crossover, mutation and the TSP.