Advanced evolutionary approaches
Although the Genetic Algorithm seems straight-forward, different strategies can be employeed for the different steps of the algorithm.
As a reminder, the general life cycle of a genetic algorithm is:
- Creating a population — Creating a random population of potential solutions.
- Measuring fitness of individuals in the population — Determining how good a specific solution is. This task is accomplished by using a fitness function that scores solutions to determine how good they are.
- Selecting parents based on their fitness — Selecting pairs of parents that will reproduce offspring.
- Reproducing individuals from parents — Creating offspring from their parents by mixing genetic information and applying slight mutations to the offspring.
- Populating the next generation — Selecting individuals and offspring from the population that will survive to the next generation.
Let’s explore how different encoding strategies can be used to represent solutions.
Encoding solutions
When we have a problem at hand, we need to determine how to encode the solutions to the problem so that they can be used by the genetic algorithm. Some common problems include encoding real-numbers like sensor values of a device; order-encoding for problems that require a sequence of actions; and tree-encoding for problems that require a tree of actions, like planning decision paths, and code generation.
Play with the toys below to see how changing values for different problems changes the chromosome representation.
Real-value encoding
Continuous knobs for tuning the drone’s behavior.
Order encoding
Sequence the loot stops to minimize travel time.
Tree encoding
Conditional policy that reacts to mission events.
Selection strategies
Selection strategies help mitigate the problems of roulette-wheel selection; each has advantages and disadvantages that affect the diversity of the population, which ultimately affects whether an optimal solution is found.
One problem with roulette-wheel selection is the vast differences in the magnitude of fitness between chromosomes. This heavily biases the selection toward choosing individuals with high fitness scores or giving poor-performing individuals a larger chance of selection than desired because their fitness is represented disproportionately. This problem affects the diversity of the population. More diversity means more exploration of the search space, but it can also make finding optimal solutions take too many generations.
Roulette wheel selection
A popular technique in choosing parents based on their fitness is roulette-wheel selection. This strategy gives different individuals portions of a wheel based on their fitness. The wheel is “spun,” and an individual is selected. Higher fitness gives an individual a larger slice of the wheel. This process is repeated until the desired number of parents is reached. By calculating the probabilities of 16 individuals of varying fitness, the wheel allocates a slice to each. Because many individuals perform similarly, there are many slices of similar size.
Rank selection
Rank selection aims to solve this problem by ranking individuals based on their fitness and then using each individual’s rank as the value for calculating the size of its slice on the wheel. In the Knapsack Problem, this value is a number between 1 and 16, because we’re choosing among 16 individuals. Although strong individuals are more likely to be selected and weaker ones are less likely to be selected even though they are average, each individual has a fairer chance of being selected based on rank rather than exact fitness.
Think of a marathon. The winner might cross the finish line 1 hour ahead of second place, or just 1 second ahead. In Roulette Wheel selection, that time gap matters—the much faster runner gets a massively bigger slice. In Rank Selection, we ignore the time gap. First place gets $100, Second gets $50. It doesn’t matter how much better the winner was, only that they were better. This prevents one “super-individual” from dominating the population too early.
Elitism
Elitism acts like a “VIP Pass” for your best solutions. It allows the top performers to skip the risky process of crossover and mutation and move straight to the next round. This ensures the best solution found so far is never lost. However, relying on it too much is dangerous: if everyone is an elite, no one is exploring new territory, and the algorithm stops learning. The disadvantage of elitism is that the population can fall into a local best solution space and never be diverse enough to find global bests.
Elitism is often used in conjunction with roulette-wheel selection, rank selection, and tournament selection. The idea is that several elite individuals are selected to reproduce, and the rest of the population is filled with individuals by means of one of the other selection strategies.
Population fitness
Fitness equals total value if the candidate stays under the 3,000,000 weight limit.
Roulette wheel selection
Each candidate is picked with probability proportional to its fitness.
Rank selection
Only the ordering matters. Candidates are weighted by rank, not raw fitness.
Elitism selection
Top 2 candidates are guaranteed once per generation, then roulette fills the rest.
Grokking AI Algorithms
An illustrated guide
Learn the algorithms that power search, optimization, machine learning, deep learning, and generative AI.
