jMetal解説 - Algorithm interface

##元のページ
https://github.com/jMetal/jMetalDocumentation/blob/master/algorithm.md#case-study-nsga-ii


## The `Algorithm` interface
jMetal5のメタヒューリスティックなどのアルゴリズムは`Algorithm`インターフェースを継承している．

```java
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パターン](https://en.wikipedia.org/wiki/Builder_pattern)と[algorythm template](https://github.com/jMetal/jMetalDocumentation/blob/master/algorithmTemplates.md)の使用である．次の章では，よく知られているNSGA-IIアルゴリズムがどのように，実装され，設定され，拡張されるかを説明します．

### Case study: NSGA-II
NSGA-IIは進化的アルゴリズム(Evolutionary algorithms, EA)に仲間である遺伝的アルゴリズム(Genetic Algorithms, GA)の一種である．NSGA-IIの実装は，[algorithm template](https://github.com/jMetal/jMetalDocumentation/blob/master/algorithmTemplates.md)内のthe evolutionary algorithm templateに従っている．このテンプレートは[`AbstractGeneticAlgorithm`](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-core/src/main/java/org/uma/jmetal/algorithm/impl/AbstractGeneticAlgorithm.java)クラスとして定義されている．アルゴリズムのフロー制御は次のような`run()`メソッドに定義される．

```java
@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](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/nsgaii/NSGAII.java)内でどのように実装されているかを述べる．

クラスの宣言は次のようになっている．

```java
public class NSGAII<S extends Solution<?>> extends AbstractGeneticAlgorithm<S, List<S>> {
   ...
}
```

これは[`AbstractGeneticAlgorithm`](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-core/src/main/java/org/uma/jmetal/algorithm/impl/AbstractGeneticAlgorithm.java)を継承していることを示す．型パラメータ`S`はアルゴリズムが操作する解のエンコーディングを指定し，それによって解くことのできる問題の種類や，適用できるoperatorが決定される．このことは次のコンストラクタ内で体現されている．

```java
 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](https://github.com/jMetal/jMetalDocumentation/blob/master/evaluators.md)オブジェクト

すべてのパラメータが，`S`に依存していることがわかる．このように，`S`が例えば`DoubleSolution`にインスタンス化されると，
解ける問題は`Problem<DoubleSolution>`を継承した問題，適用可能なoperatorは`DoubleSolution`を扱うものでなくてはならなくなる．このアプローチのよいところは，与えられた解に間違ったオペレータが適用されることがないように，コンパイラが保障してくれることである．

デフォルトの`createInitialPopulation()`はリストに`populationSize`の数だけ新しい解を追加する．

```java
  @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()`メソッドはシンプルに次のように実装されている．

```java
  @Override protected List<S> evaluatePopulation(List<S> population) {
    population = evaluator.evaluate(population, problem);

    return population;
  }
```

NSGA-IIの実装は，終了条件が最大繰り返し回数に関連して定義されていることを想定している．

```java
 @Override protected boolean isStoppingConditionReached() {
    return iterations >= maxIterations;
  }
```

そのため，`initProgress()`メソッドは繰り返し回数のカウンターを初期化する．（初期個体はすでに一度評価されていることを前提としているため，初期値は１である．）


```java
  @Override protected void initProgress() {
    iterations = 1;
  }
```

そして`updateProgress()`は単にカウンターを1増加させる．


```java
  @Override protected void updateProgress() {
    iterations++;
  }
```

EAテンプレートによると，`selection()`メソッドは集団から交配プールを作成しなければならないので，次のように実装される．

```java
  @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()`メソッドは交叉や突然変異のオペレータを交配プールに適用し，子の集団に追加される新しい個体を導く．

```java
  @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()`メソッドは現在の集団と子集団を結合し，そこからランキングと混雑距離による選択を行って次世代の解集団を作成する．

```java
  @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`](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-algorithm/src/main/java/org/uma/jmetal/algorithm/multiobjective/nsgaii/SteadyStateNSGAII.java)クラスについて説明する．このクラスは，定常状態バージョンのNSGA-IIの実装である．このバージョンの基本はNSGA-IIであるが，サイズ1の補助集団を持つ．`SteadyStateNSGAII`クラスは`NSGAII`クラスを継承している．


```java
public class SteadyStateNSGAII<S extends Solution<?>> extends NSGAII<S> {
}
```

コンストラクタもNSGA-IIと同様である．

```java
  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つのみしか生成されないことである．


```java
  @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`](https://github.com/jMetal/jMetal/blob/jmetal-5.0/jmetal-core/src/main/java/org/uma/jmetal/util/AlgorithmBuilder.java)インターフェースによって表現されている．

```java
/**
 * Interface representing algorithm builders
 *
 * @author Antonio J. Nebro <antonio@lcc.uma.es>
 */
public interface AlgorithmBuilder<A extends Algorithm<?>> {
  public A build() ;
}
```

TO BE COMPLETED