https://github.com/jMetal/jMetalDocumentation/blob/master/algorithm.md#case-study-nsga-ii
The Algorithm interface
Les algorithmes tels que la méta-heuristique de jMetal5 héritent de l'interface ʻAlgorithm`.
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() ;
}
Cette interface a une conception assez générale.
L'algorithme doit toujours avoir une méthode run () pour l'exécution et une méthode getResult () qui renvoie le résultat.
De plus, puisque cette interface hérite de java.lang.Runnable, tout algorithme peut être exécuté dans un thread.
ʻAlgorithm` L'interface est simple, vous pouvez donc implémenter librement l'algorithme. Cependant, pour promouvoir une bonne conception, la réutilisation du code et la flexibilité, jMetal5 inclut des ressources et des stratégies pour aider à la mise en œuvre de l'algorithme. La clé est le modèle de générateur et modèle d'algorithme Est l'utilisation de. Le chapitre suivant décrit comment le célèbre algorithme NSGA-II est implémenté, configuré et étendu.
Case study: NSGA-II
NSGA-II est un type d'algorithmes génétiques (GA) qui accompagne les algorithmes évolutifs (EA). L'implémentation de NSGA-II suit le modèle d'algorithme évolutif dans modèle d'algorithme. Ce modèle est [ʻAbstractGeneticAlgorithm](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-core/src/main/java/org/uma/jmetal/algorithm/impl/AbstractGeneticAlgorithm.java ) Il est défini comme une classe. Le contrôle de flux de l'algorithme est défini dans la méthode suivante run ()`.
@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();
}
}
Ensuite, ces méthodes sont [NSGA-II](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/ Il décrit comment il est implémenté dans nsgaii / NSGAII.java).
La déclaration de classe est la suivante.
public class NSGAII<S extends Solution<?>> extends AbstractGeneticAlgorithm<S, List<S>> {
...
}
Il s'agit de ʻAbstractGeneticAlgorithm` Indique qu'il hérite. Le paramètre de type «S» spécifie le codage de la solution opérée par l'algorithme, qui détermine le type de problème qui peut être résolu et l'opérateur applicable. Ceci est incorporé dans le constructeur suivant.
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;
}
Les paramètres du constructeur sont
On peut voir que tous les paramètres dépendent de «S». Ainsi, lorsque «S» est instancié dans, par exemple, «DoubleSolution»,
Le problème qui peut être résolu doit être un problème qui hérite de Problème <DoubleSolution>, et l'opérateur applicable doit gérer DoubleSolution. L'avantage de cette approche est que le compilateur garantit que le mauvais opérateur ne sera pas appliqué à une solution donnée.
La valeur par défaut createInitialPopulation () ajoute autant de nouvelles solutions à la liste qu'il y a de 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;
}
L'évaluation de la liste de solutions est laissée à ʻEvaluator. Par conséquent, la méthode ʻevaluatePopulation () est simplement implémentée comme suit.
@Override protected List<S> evaluatePopulation(List<S> population) {
population = evaluator.evaluate(population, problem);
return population;
}
L'implémentation NSGA-II suppose que la condition de terminaison est définie par rapport au nombre maximum d'itérations.
@Override protected boolean isStoppingConditionReached() {
return iterations >= maxIterations;
}
Par conséquent, la méthode ʻinitProgress () `initialise le compteur de répétition. (La valeur initiale est 1 car on suppose que l'individu initial a déjà été évalué une fois.)
@Override protected void initProgress() {
iterations = 1;
}
Et ʻupdateProgress () `incrémente simplement le compteur de 1.
@Override protected void updateProgress() {
iterations++;
}
Selon le modèle d'EA, la méthode selection () doit créer un pool d'accouplement à partir de la population, elle est donc implémentée comme suit.
@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;
}
La méthode «reproduction ()» applique ensuite des opérateurs de croisement et de mutation au pool d'accouplement pour guider les nouveaux individus à ajouter à la population de descendants.
@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;
}
Enfin, la méthode «replacement ()» combine la population actuelle avec ses populations enfants, à partir desquelles elle effectue des sélections en fonction du classement et de la distance de congestion pour créer la population de solutions de nouvelle génération.
@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
L'avantage d'utiliser le modèle EA pour NSGA-II est qu'il simplifie la mise en œuvre des variations d'algorithme. À titre d'exemple, [SteadyStateNSTGAII](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/nsgaii/SteadyStateNSGAII. java) La classe est expliquée. Cette classe est une implémentation de la version en régime permanent de NSGA-II. La base de cette version est NSGA-II, mais elle a une population auxiliaire de taille 1. La classe SteadyState NSGAII hérite de la classe NSGAII.
public class SteadyStateNSGAII<S extends Solution<?>> extends NSGAII<S> {
}
Le constructeur est le même que 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);
}
La différence est que «selection ()» crée un pool d'accouplement à partir de deux individus parents et «reproduction ()» ne produit qu'un seul enfant.
@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;
}
De cette manière, la plupart du code de la classe NSGAII peut être réutilisé et seules deux méthodes doivent être redéfinies.
Using the builderpattern to configure NSGA-II Afin de définir l'algorithme, jMetal5 a appliqué le modèle de générateur. Il s'agit de l'interface ʻAlgorithmBuilder` Il est exprimé par.
/**
* Interface representing algorithm builders
*
* @author Antonio J. Nebro <[email protected]>
*/
public interface AlgorithmBuilder<A extends Algorithm<?>> {
public A build() ;
}
TO BE COMPLETED