1. Introduction
In this tutorial, we’ll study elitism in the context of evolutionary algorithms.
First, we’ll have a brief contextualization of the theme. Then, we’ll review some relevant concepts of evolutionary algorithms related to elitism. Finally, we’ll explore elitism, showing its definitions and examples.
2. Background
Solving optimization problems is one great application of computing in our everyday lives. For example, deciding which route to take for passing into a set of destinations is a classical optimization scenario called the traveling salesman problem.
We can solve the previously cited kind of problem with optimization algorithms. These algorithms, in turn, have multiple categorizations. A critical categorization, however, regards the frequency or possibility of reaching the optimal result for an optimization problem:
- Exact Algorithms: algorithms that always return the optimal solution for a given problem. A traditional example of such algorithms is the brute force ones
- Approximate Algorithms: algorithms that can find the optimal solutions, but there are no guarantees. Multiple heuristics and metaheuristics are examples of approximate algorithms
Although the benefit of always obtaining the optimal solution, exact algorithms usually take a long time and lots of computational resources to execute. So, it is not possible to use them every time.
In this way, approximate algorithms become the straightforward option when exact algorithms are not a feasible alternative.
Evolutionary algorithms are a class of metaheuristics. These algorithms inspire in nature mechanisms to solve optimization problems. Due to that, evolutionary algorithms are considered one of the bases of bio-inspired computing.
One of the most known examples of an evolutionary optimization algorithm is genetic metaheuristics. These metaheuristics employ the concepts of Darwinian Evolution to execute optimization processes.
Other examples of evolutionary algorithms are differential evolution, neuroevolution, and learning classifier systems.
3. Relevant Concepts from Evolutionary Algorithms
A problem solved with evolutionary algorithms must be modeled considering some requirements. So, in this section, we’ll briefly review particular elements directly related to the elitism concept in evolutionary algorithms.
There are three essential elements of evolutionary algorithms for understanding elitism: individual, population, and generation. Let’s see a little bit of each one of them:
- Individual: an individual represents a possible solution to an optimization problem. We can model individuals in different ways according to the considered problem
- Population: a population consists of a set of individuals. So, it means the number of possible solutions to the optimization problem considered at the same time
- Generation: a generation consists of a population created at a given point of evolutionary algorithm execution. Thus, as the algorithm execution goes on, new generations emerge, and the solutions for the optimization problem get refined
The following image shows the relation between the previously presented elements of evolutionary algorithms:
It is relevant to highlight that several other elements compose an evolutionary algorithm. However, these elements relate to technicalities not required for discussing elitism.
Furthermore, we should also talk about crossover and mutation. Evolutionary algorithms typically use these processes, or similar processes, to evolve individuals across the generations:
- Crossover: this process uses two or more existing individuals in a population to create a new one by strategically merging them
- Mutation: this process modifies some characteristic of a given individual to create a new one
With crucial elements and processes already defined, we can finally discuss elitism. Let’s do that in the following section.
4. Elitism in Evolutionary Algorithms
In short, we can see elitism in evolutionary algorithms as a concept that enforces one or two of the conditions next:
- The straightforward inclusion of the best individuals of a generation in the population of the following generation
- The use of the best individuals of a generation a minimum number of times to crossover with other random individuals for creating the following generation
Thus, before applying elitism to create new generations of individuals, we must evaluate the current generation to find the best individuals. For that, evolutionary algorithms calculate and compare an optimization function (or objective function) for each available individual of a population.
The main purpose of using elitism in evolutionary algorithms is to keep the reference for promising areas of the search space across the generations.
In practice, elitism enables the continuous exploiting of these promising areas (where we can find a local or global optima result).
Moreover, elitism also guarantees the presence of the best individuals found considering the entire processing of an evolutionary algorithm in the last generation created, which is the final result.
The image next exemplifies elitism acting over generations of a generic evolutionary algorithm:
4.1. Tuning Elitism in Evolutionary Algorithms
Adopting elitism, however, may also harm evolutionary algorithms. As it propagates already known individuals to follow generations, the possibility of finding new individuals better fitted to solve the problem reduces.
So, elitism inevitably reduces the diversity of a population and decreases the algorithm’s capacity to explore the search space.
Due to that reason, elites are typically small groups of individuals.
There is no concrete and definite size for defining the elite group. Usually, this size is determined as a percentage of the population size.
A widely employed tuning for elitism considers the following configurations:
- The best 10% individuals of a population in a generation form the entire elite group
- The best 50% of individuals in the elite group directly propagate to the next generation
- The worst 50% of individuals in the elite group crossover with non-elite individuals
We should note, however, that the best tuning of elitism in evolutionary algorithms depends on the problem and search space characteristics: there is no global and predefined best configuration.
Finally, it is also important to emphasize that employing elitism is not mandatory for evolutionary algorithms. Again, the option to use it or not highly depends on the specific optimization problem being solved.
5. Conclusion
In this tutorial, we explored elitism in the context of evolutionary algorithms. First, we checked background concepts, thus understanding how evolutionary algorithms fit for optimization problem-solving. So, we studied relevant elements and processes of evolutionary algorithms for our context. At last, we in-depth investigated elitism itself.
We can conclude that elitism can improve evolutionary algorithms. However, we should adequately configure the elitism mechanisms according to the optimization problem to get the best results.