https://github.com/jMetal/jMetalDocumentation/blob/master/algorithm.md#case-study-nsga-ii
The Algorithm interface
algorithms such as jMetal5's metaheuristics inherit the ʻAlgorithm` interface.
package org.uma.jmetal.algorithm;
/**
* Interface representing an algorithm
* @author Antonio J. Nebro
* @version 0.1
* @param <Result> Result
*/
public interface Algorithm<Result> extends Runnable {
void run() ;
Result getResult() ;
}
This interface has a fairly general design.
The algorithm must always have a run () method for execution and a getResult () method that returns the result.
Also, since this interface inherits java.lang.Runnable, any algorithm can be executed in a thread.
ʻAlgorithm` The interface is simple, so you can freely implement the algorithm. However, to promote good design, code reuse, and flexibility, jMetal5 includes resources and strategies that help implement the algorithm. The key is the builder pattern and algorythm template Is the use of. The next chapter describes how the well-known NSGA-II algorithm is implemented, configured, and extended.
Case study: NSGA-II
NSGA-II is a type of genetic algorithms (GA) that are a companion to the evolutionary algorithms (EA). The implementation of NSGA-II follows the evolutionary algorithm template in algorithm template. This template is [ʻAbstractGeneticAlgorithm](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-core/src/main/java/org/uma/jmetal/algorithm/impl/AbstractGeneticAlgorithm.java ) It is defined as a class. The flow control of the algorithm is defined in the following run ()` method.
@Override public void run() {
List<S> offspringPopulation;
List<S> matingPopulation;
population = createInitialPopulation();
population = evaluatePopulation(population);
initProgress();
while (!isStoppingConditionReached()) {
matingPopulation = selection(population);
offspringPopulation = reproduction(matingPopulation);
offspringPopulation = evaluatePopulation(offspringPopulation);
population = replacement(population, offspringPopulation);
updateProgress();
}
}
Then these methods are [NSGA-II](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/ It describes how it is implemented in nsgaii / NSGAII.java).
The class declaration is as follows.
public class NSGAII<S extends Solution<?>> extends AbstractGeneticAlgorithm<S, List<S>> {
...
}
This is [ʻAbstractGeneticAlgorithm](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-core/src/main/java/org/uma/jmetal/algorithm/impl/AbstractGeneticAlgorithm.java) Indicates that it inherits. The type parameter S` specifies the encoding of the solution operated by the algorithm, which determines the type of problem that can be solved and the applicable operator. This is embodied in the following constructor.
public NSGAII(Problem<S> problem, int maxIterations, int populationSize,
CrossoverOperator<S> crossoverOperator, MutationOperator<S> mutationOperator,
SelectionOperator<List<S>, S> selectionOperator, SolutionListEvaluator<S> evaluator) {
super() ;
this.problem = problem;
this.maxIterations = maxIterations;
this.populationSize = populationSize;
this.crossoverOperator = crossoverOperator;
this.mutationOperator = mutationOperator;
this.selectionOperator = selectionOperator;
this.evaluator = evaluator;
}
Constructor parameters
It can be seen that all parameters depend on S. Thus, when S is instantiated into, for example, DoubleSolution,
The problem that can be solved must be a problem that inherits Problem <DoubleSolution>, and the applicable operator must handle DoubleSolution. The nice thing about this approach is that the compiler guarantees that the wrong operator will not be applied to a given solution.
The default createInitialPopulation () adds as many new solutions to the list as there are populationSize.
@Override protected List<S> createInitialPopulation() {
List<S> population = new ArrayList<>(populationSize);
for (int i = 0; i < populationSize; i++) {
S newIndividual = problem.createSolution();
population.add(newIndividual);
}
return population;
}
The evaluation of the list of solutions is left to ʻEvaluator. Therefore, the ʻevaluatePopulation () method is simply implemented as follows.
@Override protected List<S> evaluatePopulation(List<S> population) {
population = evaluator.evaluate(population, problem);
return population;
}
The NSGA-II implementation assumes that the termination condition is defined in relation to the maximum number of iterations.
@Override protected boolean isStoppingConditionReached() {
return iterations >= maxIterations;
}
Therefore, the ʻinitProgress () `method initializes the repeat count counter. (The initial value is 1 because it is assumed that the initial individual has already been evaluated once.)
@Override protected void initProgress() {
iterations = 1;
}
And ʻupdateProgress ()` simply increments the counter by 1.
@Override protected void updateProgress() {
iterations++;
}
According to the EA template, the selection () method must create a mating pool from the population, so it is implemented as follows:
@Override protected List<S> selection(List<S> population) {
List<S> matingPopulation = new ArrayList<>(population.size());
for (int i = 0; i < populationSize; i++) {
S solution = selectionOperator.execute(population);
matingPopulation.add(solution);
}
return matingPopulation;
}
The reproduction () method then applies crossover and mutation operators to the mating pool to guide new individuals to be added to the offspring population.
@Override protected List<S> reproduction(List<S> population) {
List<S> offspringPopulation = new ArrayList<>(populationSize);
for (int i = 0; i < populationSize; i += 2) {
List<S> parents = new ArrayList<>(2);
parents.add(population.get(i));
parents.add(population.get(i + 1));
List<S> offspring = crossoverOperator.execute(parents);
mutationOperator.execute(offspring.get(0));
mutationOperator.execute(offspring.get(1));
offspringPopulation.add(offspring.get(0));
offspringPopulation.add(offspring.get(1));
}
return offspringPopulation;
}
Finally, the replacement () method combines the current population with its child populations, from which it makes selections by ranking and congestion distance to create the next generation solution population.
@Override protected List<S> replacement(List<S> population, List<S> offspringPopulation) {
List<S> jointPopulation = new ArrayList<>();
jointPopulation.addAll(population);
jointPopulation.addAll(offspringPopulation);
Ranking<S> ranking = computeRanking(jointPopulation);
return crowdingDistanceSelection(ranking);
}
Case study: Steady-state: NSGA-II
The advantage of using EA templates for NSGA-II is that it simplifies the implementation of algorithm variations. As an example, [SteadyState NSTGAII](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/nsgaii/SteadyStateNSGAII. java) Class is explained. This class is an implementation of the steady-state version of NSGA-II. The basis of this version is NSGA-II, but it has a size 1 auxiliary population. The SteadyState NSGAII class inherits from the NSGAII class.
public class SteadyStateNSGAII<S extends Solution<?>> extends NSGAII<S> {
}
The constructor is the same as NSGA-II.
public SteadyStateNSGAII(Problem<S> problem, int maxIterations, int populationSize,
CrossoverOperator<S> crossoverOperator, MutationOperator<S> mutationOperator,
SelectionOperator<List<S>, S> selectionOperator, SolutionListEvaluator<S> evaluator) {
super(problem, maxIterations, populationSize, crossoverOperator, mutationOperator,
selectionOperator, evaluator);
}
The difference is that selection () creates a mating pool from two parent individuals and reproduction () produces only one child.
@Override protected List<S> selection(List<S> population) {
List<S> matingPopulation = new ArrayList<>(2);
matingPopulation.add(selectionOperator.execute(population));
matingPopulation.add(selectionOperator.execute(population));
return matingPopulation;
}
@Override protected List<S> reproduction(List<S> population) {
List<S> offspringPopulation = new ArrayList<>(1);
List<S> parents = new ArrayList<>(2);
parents.add(population.get(0));
parents.add(population.get(1));
List<S> offspring = crossoverOperator.execute(parents);
mutationOperator.execute(offspring.get(0));
offspringPopulation.add(offspring.get(0));
return offspringPopulation;
}
As you can see, most of the code in the NSGAII class can be reused and only two methods need to be redefined.
Using the builderpattern to configure NSGA-II In order to set the algorithm, jMetal5 applied the builder pattern. This is the ʻAlgorithmBuilder` interface It is represented by.
/**
* Interface representing algorithm builders
*
* @author Antonio J. Nebro <[email protected]>
*/
public interface AlgorithmBuilder<A extends Algorithm<?>> {
public A build() ;
}
TO BE COMPLETED