The JCLEC framework contains a final implementation for several types of evolutionary algorithms, which make easy the execution of an experiment. JCLEC has implementations of classical algorithms and niching algorithms. These kind of algorithms are exposed in detail below.
Classical Evolutionary Algorithms
In this section, we present Classical Evolutionary Algorithms. This module contains the following algorithms:
- Simple Generational Algorithm (SG).
- Simple Generational Algorithm with Elitism (SGE).
- Steady State Algorithm (SS).
- CHC Algorithm (CHC).
Simple Generational Algorithm (SG)
This is a classical Genetic Algorithm which implements a generational schema. The steps are the following:
- Randomly generates an initial population.
- Evaluates the fitness of all individuals.
- Selects the fittest individuals.
- Creates a new population by means of recombination and mutation.
- Go to step 2.
Simple Generational Algorithm with Elitism (SGE)
This algorithm is like the Generational one, but ensures any time that the best individual passes to the next generation.
Steady State Algorithm (SS)
This is a classical Genetic Algorithm which implements a steady state schema. The steps are the following:
- Randomly generates an initial population.
- Evaluates the fitness of all individuals.
- Selects the fittest individuals.
- Generates a number of descendants by means of recombination and mutation.
- Replaces the weakest individuals with the descendants.
- Go to step 2.
CHC Algorithm (CHC)
This is a conservative selection algorithm that works together with a radical recombination operator and with mecanisms used to prevent the premature convergence and to maintain the diversity.
Its philosophy consist on combining an elitist selection, which maintains the best individuals, with a crossover operator that generates sons very different from their parents.
The CHC algorithm uses the following components:
- Elitist Selection: it selects the N best chromosomes in the set composed by parents and sons, i.e. the best N individuals found from the begining are kept in the actual population.
- HUX Uniform Crossover: it exchanges exactly the half of the loci that are different in the parents. This crossover operator ensures that the sons have a maximum Hamming distance to their parents.
- Incest prevention: N/2 couples are formed in the population. The crossover operator is only applied to those couples whose members have at least a concrete number of different bits (crossover threshold). The crossover threshold is initialized to L/4 (where L is chromosome length). If no crossover is performed in a complete cycle, the crossover threshold is decrement in 1.
- Reinitialization: when the crossover threshold is less than 0, the population is restarted using one of these approaches:
1. Using the best individual as a template and creating a copy of it.
2. Keeping the best individual or a set of the best individuals, and the rest of the population is generated in a random mode.
Niching Algorithms
In this section, we present Niching Algorithms. This module contains the following algorithms:
- Clearing Algorithm.
- Sharing Algorithm.
- Sequential Algorithm
Clearing Algorithm
In this algorithm, the capacity k of a niche is specified as the maximum number of elements that this niche can contain. So, the fitness of k better individuals of this niche is kept (dominant individuals) while the fitness of the rest of the individuals is reseted.
Two individuals belongs to the same niche if their distance within the search space is less than the disimilarity threshold.
The Clearing method is applied after the fitness evaluation and before applying the selection operator. The disimilarity value could be the Hamming distance for binary genotypes or the Euclidean distance for real genotype. Also, this distance can be defined to the phenotype level.
Each subpopulation contains a dominant individual: the one with the best fitness. If one individual belongs to a subpopulation, then its disimilarity with the dominant individual is less than the disimilarity threshold, frecuently known as the niche radius.
Sharing Algorithm
Sharing is probably the most common method in the niche techniques. This algorithm leads to promote the search in the non-explored areas of the search space. Also, it has the objective of creating stable subpopulations.
This algorithm has two main limitations, which are the following:
- You may stablish the disimilarity threshold, which requires you have a priori knowledge about how far are the optimun individuals, and this kind of information is often unknown.
- The disimilarity threshold is the same for all the individuals, which implies that the distance within the scope between all the optimum individuals must be approximately the same. This may leads to a fault in order to maintain all the desired optimum individuals if the distance between them is not the same.
Sequential Algorithm
This algorithm is based on a classical Genetic Algorithm. Furthermore, it uses knowledge from one iteration to the next one, so the knowledge from the previous iteration is used to avoid searching in regions that have already been visited. Therefore, the probability of finding a new solution is drastically increased.
The Sequential algorithm can be used with different kinds of AGs or even with other optimization techniques such as Simulated Annealing.