https://github.com/jMetal/jMetalDocumentation/blob/master/algorithm.md#case-study-nsga-ii
The Algorithm interface
Algorithmen wie die Meta-Heuristik von jMetal5 erben die "Algorithmus" -Schnittstelle.
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() ;
}
Diese Schnittstelle hat ein ziemlich allgemeines Design. Der Algorithmus muss immer eine run () -Methode zur Ausführung und eine getResult () -Methode haben, die das Ergebnis zurückgibt. Da diese Schnittstelle "java.lang.Runnable" erbt, kann jeder Algorithmus in einem Thread ausgeführt werden.
Da die "Algorithmus" -Schnittstelle einfach ist, können Sie den Algorithmus frei implementieren. Um ein gutes Design, die Wiederverwendung von Code und Flexibilität zu fördern, enthält jMetal5 Ressourcen und Strategien zur Unterstützung der Implementierung des Algorithmus. Der Schlüssel ist das Builder-Muster und die Algorythm-Vorlage. Ist die Verwendung von. Im nächsten Kapitel wird beschrieben, wie der bekannte NSGA-II-Algorithmus implementiert, konfiguriert und erweitert wird.
Case study: NSGA-II
NSGA-II ist eine Art genetischer Algorithmen (GA), die eine Ergänzung zu den evolutionären Algorithmen (EA) darstellt. Die Implementierung von NSGA-II folgt der evolutionären Algorithmusvorlage in Algorithmusvorlage. Diese Vorlage ist AbstractGeneticAlgorithm Es ist als Klasse definiert. Die Flusskontrolle des Algorithmus wird in der folgenden Methode "run ()" definiert.
@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();
}
}
Dann sind diese Methoden NSGA-II Es beschreibt, wie es in nsgaii / NSGAII.java implementiert ist.
Die Klassendeklaration lautet wie folgt.
public class NSGAII<S extends Solution<?>> extends AbstractGeneticAlgorithm<S, List<S>> {
...
}
Dies ist AbstractGeneticAlgorithm Zeigt an, dass es erbt. Der Typparameter "S" gibt die Codierung der vom Algorithmus betriebenen Lösung an, die die Art des zu lösenden Problems und den anwendbaren Operator bestimmt. Dies ist im folgenden Konstruktor enthalten.
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;
}
Die Parameter des Konstruktors sind
Es ist ersichtlich, dass alle Parameter von "S" abhängen. Wenn also "S" beispielsweise in "DoubleSolution" instanziiert wird,
Das Problem, das gelöst werden kann, muss ein Problem sein, das "Problem
Die Standardeinstellung "createInitialPopulation ()" fügt der Liste so viele neue Lösungen hinzu, wie es "populationsgröße" gibt.
@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;
}
Die Bewertung der Liste der Lösungen bleibt dem "Bewerter" überlassen. Daher wird die Methode evaluPopulation () einfach wie folgt implementiert.
@Override protected List<S> evaluatePopulation(List<S> population) {
population = evaluator.evaluate(population, problem);
return population;
}
Die NSGA-II-Implementierung geht davon aus, dass die Beendigungsbedingung in Bezug auf die maximale Anzahl von Iterationen definiert ist.
@Override protected boolean isStoppingConditionReached() {
return iterations >= maxIterations;
}
Daher initialisiert die Methode initProgress () den Wiederholungszähler. (Der Anfangswert ist 1, da davon ausgegangen wird, dass die ursprüngliche Person bereits einmal bewertet wurde.)
@Override protected void initProgress() {
iterations = 1;
}
Und updateProgress () erhöht einfach den Zähler um 1.
@Override protected void updateProgress() {
iterations++;
}
Gemäß der EA-Vorlage muss die Methode "selection ()" einen Paarungspool aus der Grundgesamtheit erstellen, sodass sie wie folgt implementiert wird.
@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;
}
Die "reproduction ()" - Methode wendet dann Crossover- und Mutationsoperatoren auf den Paarungspool an, um neue Individuen zu führen, die der Nachkommenpopulation hinzugefügt werden sollen.
@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;
}
Schließlich kombiniert die Methode "replace ()" die aktuelle Population mit ihren untergeordneten Populationen, aus denen sie basierend auf Rangfolge und Überlastungsentfernung eine Auswahl trifft, um die Lösungspopulation der nächsten Generation zu erstellen.
@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
Der Vorteil der Verwendung der EA-Vorlage für NSGA-II besteht darin, dass die Implementierung von Algorithmusvariationen vereinfacht wird. Als Beispiel [SteadyStateNSTGAII](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/nsgaii/SteadyStateNSGA. Java) Klasse wird erklärt. Diese Klasse ist eine Implementierung der stationären Version von NSGA-II. Die Basis dieser Version ist NSGA-II, aber es hat eine Hilfspopulation der Größe 1. Die Klasse "SteadyState NSGAII" erbt von der Klasse "NSGAII".
public class SteadyStateNSGAII<S extends Solution<?>> extends NSGAII<S> {
}
Der Konstruktor ist der gleiche wie bei 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);
}
Der Unterschied besteht darin, dass "selection ()" einen Paarungspool aus zwei übergeordneten Personen erstellt und "reproduction ()" nur ein Kind erzeugt.
@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;
}
Auf diese Weise kann der größte Teil des Codes in der NSGAII-Klasse wiederverwendet werden, und es müssen nur zwei Methoden neu definiert werden.
Using the builderpattern to configure NSGA-II
Um den Algorithmus festzulegen, hat jMetal5 das Builder-Muster angewendet.
Dies ist die Schnittstelle AlgorithmBuilder Es wird vertreten durch.
/**
* Interface representing algorithm builders
*
* @author Antonio J. Nebro <[email protected]>
*/
public interface AlgorithmBuilder<A extends Algorithm<?>> {
public A build() ;
}
TO BE COMPLETED