Exploring Selection

Genetic Algorithms in Elixir — by Sean Moriarity (44 / 101)

👈 Chapter 5 Selecting the Best | TOC | Customizing Selection in Your Framework 👉

Selection is vital to the performance of a genetic algorithm because it contributes to the creation of good solutions for the next generation. The idea is that parents have characteristics that make them strong based on your fitness criteria and will pass these characteristics on to the next generation of solutions.

Consider this: in medieval and early modern Europe, monarchs would carefully select partners to maintain their status as royalty. The idea was based on the assumption that royal blood was stronger and the genes of a commoner would ruin the purity of the bloodline.

Monarchs practiced a loose derivative of selection. They would choose partners based on territory, power, money, and other factors, which essentially amounted to the “fitness” of a potential partner. They hoped that marrying other royals would lead to a strong bloodline and continued success for the royal family.

Unfortunately, the lack of royals to marry outside of preexisting royal families meant that later monarchs often had to “keep it in the family.” A lot of monarchs were forced to marry cousins. While this initially didn’t seem like an issue — both cousins would be royalty and thus strong, after all — as the practice of intermarriage increased, so did the severity of birth defects within the royal family. But, how could the purity and strength of the royal bloodline suffer from often crippling birth defects? The problem was a lack of genetic diversity.

The selection strategy of early monarchs focused too much on perceived fitness of partners and not enough on maintaining genetic diversity. The plight of the monarchs can teach lessons about the importance of selection in your genetic algorithms.

Selection is about balancing genetic diversity and fitness. Genetic diversity is the variety in your population. This doesn’t mean variety in fitness — you can have equally strong individuals that are very different. Consider the two potential solutions to the One-Max problem in the image.

Both individuals have the same fitness, but they’re very different. These two chromosomes would be a perfect match because their diverse characteristics would be combined to form a strong child during crossover. You can see an example of this here:

If you can’t maintain the genetic diversity of your population, then your algorithm will likely converge without finding the best solution. While there are other strategies, such as mutation, for maintaining the genetic diversity of a population, selection is the first step and can make a significant difference in performance.

Selection Is Biased Sampling

If you’re familiar with statistics, you understand that selection is a biased form of sampling. Sampling is the practice of choosing a smaller subset of the population to represent the entire population. Sampling is especially important in surveys and quality assurance because it’s used to estimate the beliefs or characteristics of the population on the whole.

Sampling is done because it’s almost always impossible to survey an entire population. Instead, statisticians aim to get a sample that is representative of the population. The goal is diversity. Selection, on the other hand, is done to improve the population over the next generation. This means that most selection strategies will favor certain individuals over others because they have a better chance of improving the population.

Just as sampling only chooses part of the population, it’s common for selection strategies to only select part of the population as well. The idea is that not every chromosome is fit to be a parent, which would hopefully eliminate the weaker characteristics of a population while keeping the stronger ones.

The number of parents selected for crossover is known as the selection rate. The selection rate is a number between 0 and 1 that dictates the percentage of the population to select for crossover. For example, a selection rate of 0.8 with a population of 100 would mean 80 parents would be selected for crossover.

Varying the selection rate will affect the speed of your algorithms as well as how quickly they converge. Having a selection rate of 1 isn’t a problem. Selection rates are typically high — somewhere in the 0.75–1 range.

Importance of Selection Pressure

You can measure how well a selection strategy balances genetic diversity and fitness by determining its selection pressure. Selection pressure is a mathematical measure of the likelihood of a chromosome getting selected to be a parent. It’s defined as the ratio between the probability of the fittest individual getting picked versus the probability of an individual of average fitness getting picked.

Selection pressure is dictated by the selection rate and the selection strategy. In a truly random selection, the selection pressure is exactly 1 because every individual is equally likely to get picked. Higher selection pressures mean that a selection strategy more heavily favors fitter individuals. It’s a measure of how biased a selection strategy is.

You can use selection pressure to quantify how well your selection strategy fits into the context of your problem. If you have a problem that requires more genetic diversity, you’ll want a selection strategy with a lower selection pressure. If you want your problem to converge quickly, you’ll want a selection strategy with high selection pressure.

Types of Selection

The two main types of selection are fitness-based selection and rewards-based selection.

Fitness-based selection is selection based strictly on fitness criteria. Fitness-based selection strategies are the most common selection strategies. The goal of selection is to increase fitness; therefore, these strategies assume that fitness is the best indication of future potential fitness.

Reward-based selection is selection based on the cumulative reward obtained by an individual. The idea is that parents with high rewards create the best children. The reward can be calculated by a number of different reward functions. Reward-based selection can be useful in multi-objective optimization; however, it’s not all that common.

In this book, you’ll only work with fitness-based selection strategies because they’re the most common and the simplest to implement.

👈 Chapter 5 Selecting the Best | TOC | Customizing Selection in Your Framework 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.