##元のページ
https://github.com/jMetal/jMetalDocumentation/blob/master/algorithm.md#case-study-nsga-ii
The Algorithm
interface
jMetal5のメタヒューリスティックなどのアルゴリズムは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() ;
}
このインターフェースはかなり一般的な設計になっている.
アルゴリズムは必ず実行のためのrun()
メソッドと,結果を返すgetResult()
メソッドを持たなければならない.
また,このインターフェースはjava.lang.Runnable
を継承しているので,どのアルゴリズムもスレッドで実行することができる.
Algorithm
インターフェースはシンプルなので,自由にアルゴリズムを実装できる.
しかし,優れたデザイン,コード再利用,柔軟性を促進するためにjMetal5にはアルゴリズムの実装の補助となるリソースと戦略が含まれている.鍵となるのはbuilderパターンとalgorythm templateの使用である.次の章では,よく知られているNSGA-IIアルゴリズムがどのように,実装され,設定され,拡張されるかを説明します.
Case study: NSGA-II
NSGA-IIは進化的アルゴリズム(Evolutionary algorithms, EA)に仲間である遺伝的アルゴリズム(Genetic Algorithms, GA)の一種である.NSGA-IIの実装は,algorithm template内のthe evolutionary algorithm templateに従っている.このテンプレートはAbstractGeneticAlgorithm
クラスとして定義されている.アルゴリズムのフロー制御は次のような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();
}
}
次にこれらのメソッドがNSGA-II内でどのように実装されているかを述べる.
クラスの宣言は次のようになっている.
public class NSGAII<S extends Solution<?>> extends AbstractGeneticAlgorithm<S, List<S>> {
...
}
これはAbstractGeneticAlgorithm
を継承していることを示す.型パラメータS
はアルゴリズムが操作する解のエンコーディングを指定し,それによって解くことのできる問題の種類や,適用できるoperatorが決定される.このことは次のコンストラクタ内で体現されている.
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;
}
コンストラクタのパラメータは,
- 解く問題
- アルゴリズムの主要なパラメータ(解集団のサイズと最大繰り返し回数)
- 遺伝子操作のoperator: crossover, mutation, selection
- 解を評価するためのevaluatorオブジェクト
すべてのパラメータが,S
に依存していることがわかる.このように,S
が例えばDoubleSolution
にインスタンス化されると,
解ける問題はProblem<DoubleSolution>
を継承した問題,適用可能なoperatorはDoubleSolution
を扱うものでなくてはならなくなる.このアプローチのよいところは,与えられた解に間違ったオペレータが適用されることがないように,コンパイラが保障してくれることである.
デフォルトのcreateInitialPopulation()
はリストに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;
}
解のリストの評価はEvaluator
に任されている.したがってevaluatePopulation()
メソッドはシンプルに次のように実装されている.
@Override protected List<S> evaluatePopulation(List<S> population) {
population = evaluator.evaluate(population, problem);
return population;
}
NSGA-IIの実装は,終了条件が最大繰り返し回数に関連して定義されていることを想定している.
@Override protected boolean isStoppingConditionReached() {
return iterations >= maxIterations;
}
そのため,initProgress()
メソッドは繰り返し回数のカウンターを初期化する.(初期個体はすでに一度評価されていることを前提としているため,初期値は1である.)
@Override protected void initProgress() {
iterations = 1;
}
そしてupdateProgress()
は単にカウンターを1増加させる.
@Override protected void updateProgress() {
iterations++;
}
EAテンプレートによると,selection()
メソッドは集団から交配プールを作成しなければならないので,次のように実装される.
@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;
}
そして,reproduction()
メソッドは交叉や突然変異のオペレータを交配プールに適用し,子の集団に追加される新しい個体を導く.
@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;
}
最後に,replacement()
メソッドは現在の集団と子集団を結合し,そこからランキングと混雑距離による選択を行って次世代の解集団を作成する.
@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
NSGA-IIにEAテンプレートを使用するアドバンテージは,それによってアルゴリズムのバリエーションの実装が簡素化されることにある.例としてSteadyStateNSTGAII
クラスについて説明する.このクラスは,定常状態バージョンのNSGA-IIの実装である.このバージョンの基本はNSGA-IIであるが,サイズ1の補助集団を持つ.SteadyStateNSGAII
クラスはNSGAII
クラスを継承している.
public class SteadyStateNSGAII<S extends Solution<?>> extends NSGAII<S> {
}
コンストラクタも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);
}
違いは,selection()
で交配プールが2つの親個体から作られることとreproduction()
で子個体が1つのみしか生成されないことである.
@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;
}
このように,NSGAII
クラスのほとんどのコードが再利用でき,2つのメソッドのみを再定義するだけでよい.
Using the builderpattern to configure NSGA-II
アルゴリズムを設定するために,jMetal5ではbuilder patternを適用した.
これは,AlgorithmBuilder
インターフェースによって表現されている.
/**
* Interface representing algorithm builders
*
* @author Antonio J. Nebro <antonio@lcc.uma.es>
*/
public interface AlgorithmBuilder<A extends Algorithm<?>> {
public A build() ;
}
TO BE COMPLETED