LoginSignup
2

More than 5 years have passed since last update.

jMetal解説 - Algorithm interface

Last updated at Posted at 2018-02-21

元のページ

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2