This article explains the concepts of selections in Evolutionary Algorithms (EAs). It covers topics such as value proposition, definitions of phenotypes, genotypes, fitness, population, recombination, mutation, and survivor selection. The article also discusses the parent selection process in EAs and introduces two methods: roulette wheel selection and tournament selection. The next article in the series will focus on mutations.
Evolutionary Algorithm – Selections Explained
Understand the process and code with visualization
Are you struggling to solve complex problems like the Travelling Salesman Problem (TSP)? Evolutionary Algorithm (EA) can help! With over a trillion possible permutations for just 30 cities, brute force is not feasible. But with EA, you can find the optimal solution and understand how each component, like mutations, contributes to the solution.
Value Proposition
It’s important to understand the difference between Genetic Algorithm (GA) and Evolutionary Algorithm (EA). While GA involves representation, parent selection, recombination, mutation, and survival selection, EA goes beyond that. In this guide, we focus on aspects specific to permutation representation, explaining them with intuitive visualizations and code.
Definitions
Before we dive deeper, let’s clarify some terminologies:
Phenotypes: These are the solutions within the problem context.
Genotypes: These are the encodings that represent the phenotype.
Fitness: It’s a measure from a function that serves as the basis for selection.
Population: It’s a collection of individual genotypes.
Recombination: It’s the process of creating two offspring from two parent genotypes.
Mutation: It’s a random change performed on a single genotype.
Survivor Selection: It’s the process of determining which individuals will remain in the population for the next generation.
Outline
EA follows a specific framework:
1. Initialization; Representation
2. Parent selection
3. Recombination
4. Mutation
5. Survivor selection
Initialization and Representation
Before diving into the math and code, we need to frame the problem and formulate the genotype appropriately. Binary representation works for binary problems, but for non-binary problems like TSP, we should use permutation representation. This ensures that the resulting genotype corresponds to a valid phenotype. We can generate a population of genotypes using code.
Parent Selection
In EA, parent selection is important because the offspring are variants of their parents. We need to strike a balance between exploration and exploitation. Two common approaches are roulette wheel and tournament selection. Roulette wheel selection assigns probabilities to each individual based on their fitness, while tournament selection randomly selects a subset of the population and chooses the fittest individual. Code examples are provided for both methods.
To continue learning about EA, stay tuned for the next article on mutations explained.
Discover how AI can redefine your company. Identify automation opportunities, define KPIs, select an AI solution, and implement gradually. For AI solutions, connect with us at hello@itinai.com. Explore our AI Sales Bot at itinai.com/aisalesbot.
List of Useful Links:
- AI Lab in Telegram @aiscrumbot – free consultation
- Evolutionary Algorithm — Selections Explained
- Towards Data Science – Medium
- Twitter – @itinaicom
