LoginSignup
2
2

More than 3 years have passed since last update.

jMetal解説 - Solution interface

Last updated at Posted at 2018-02-19

元のページ

https://github.com/jMetal/jMetalDocumentation/blob/master/solution.md
これを雑に訳してるだけです.
以下本文.

Solution interface

メタヒューリスティクスを用いる場合,まず最初に解くべき問題の解をどのように表現しエンコードするかを定義しなければならない.解の表現は問題に強く依存し,表現次第で適用可能な演算(e.g., 他の解との再結合,局所探索の手順など)が決まる.したがって,解の表現方法の選択はメタヒューリスティクスの振る舞い,ひいては得られる結果の質に大きく影響する.

下の図は,jMetal 5で解を表現するために使用される基本的なクラスを表す.

jMetal_Solution_Class

この図には,Binary,Double,Integerの3つの解表現が含まれている.
このアプローチにより,同じエンコードに対して多くの実装が提供され,柔軟性が向上する.
また,ジェネリクスの利用により誤った変数の値の代入をコンパイルエラーで発見できる.
例えば,DoubleSolutionの値をint変数に代入しようとするとエラーになる.

Solutionインターフェースのコードは以下のようになっている.

package org.uma.jmetal.solution;

public interface Solution<T> extends Serializable {
  public void setObjective(int index, double value) ;
  public double getObjective(int index) ;

  public T getVariableValue(int index) ;
  public void setVariableValue(int index, T value) ;
  public String getVariableValueString(int index) ;

  public int getNumberOfVariables() ;
  public int getNumberOfObjectives() ;

  public Solution<T> copy() ;

  public void setAttribute(Object id, Object value) ;
  public Object getAttribute(Object id) ;
}

Solutionは変数と目的関数にアクセスするメソッド,copyメソッド,attributeにアクセスするためのメソッドを持つ.

Defining encodings

Solutionインターフェースの実装または拡張によって特定のエンコードが定義される.
DoubleおよびInteger変数のリストを持つ解のインターフェースは,次のように定義される.

package org.uma.jmetal.solution;

public interface DoubleSolution extends Solution<Double> {
  public Double getLowerBound(int index) ;
  public Double getUpperBound(int index) ;
}
package org.uma.jmetal.solution;

public interface IntegerSolution extends Solution<Integer> {
  public Integer getLowerBound(int index) ;
  public Integer getUpperBound(int index) ;
}

これらのインターフェースはDouble,Intefer変数の下限と上限を取得するメソッドを提供する.
これらの値を設定する方法は,実装クラスに委ねられている.

BinarySolutionの場合は以下のようになっている.

import org.uma.jmetal.util.binarySet.BinarySet;

public interface BinarySolution extends Solution<BinarySet> {
  public int getNumberOfBits(int index) ;
  public int getTotalNumberOfBits() ;
}

バイナリ変数のリストを表現していることを仮定している.

混合の変数を持つエンコードを定義することを可能にする.
たとえば,以下のインターフェースでは,double値とinteger値のリストで構成されるSolutionを定義する.

package org.uma.jmetal.solution;

public interface IntegerDoubleSolution extends Solution<Number> {
  public Number getLowerBound(int index) ;
  public Number getUpperBound(int index) ;
  public int getNumberOfIntegerVariables() ;
  public int getNumberOfDoubleVariables() ;
}

Implementing solutions

いろいろな解のインターフェースを定義した.次は,それら全てにデフォルトの実装を提供する.
AbstractGenericSolutionという抽象クラスから始めることにする.

package org.uma.jmetal.solution.impl;

public abstract class AbstractGenericSolution<T, P extends Problem<?>> implements Solution<T> {
  private double[] objectives;
  private List<T> variables;
  protected P problem ;
  protected double overallConstraintViolationDegree ;
  protected int numberOfViolatedConstraints ;
  protected Map<Object, Object> attributes ;
  protected final JMetalRandom randomGenerator ;

AbstractGenericSolutionSolutionの全てのメソッドを含む.
このクラスはjMetal5の全てのSolutionの実装のスーパークラス.
(DefaultBinarySolution, DefaultIntegerSolution, DefaultDoubleSolution, DefaultIntegerDoubleSolution, DefaultIntegerPermutationSolution, DefaultDoubleBinarySolution .)

Where are the populations?

jMetal5には,populationを表現するクラスは存在しない.
代わりにList<Solution>がpopulationとして使用される.

例:

/* A population of double solutions */
List<DoubleSolution> doublePopulation ;

/* The same population using the generic interface */
List<Solution<Double>> doublePopulation ;

/* A population of binary solutions */
List<BinarySolucion> binaryPopulation ;

ユーティリティクラスSolutionListUtilsList<Solution>に対する操作群を提供する.
(例えば,最良/最悪個体を見つけたり,解をランダムに選択したりなど.)

Solution attributes

attributesを組み込むことによって,いくつかのアルゴリズムに必要な特定のフィールドを解に追加することができる.
例えば,SPEA2ではそのままの適応度を解に割り当てるが,NSGA-IIでは解をrank付けして混雑距離の値を割り当てることが必要となる.

属性は直接操作することができるが,以下のインターフェースも定義されている.

package org.uma.jmetal.util.solutionattribute;
/**
 * Attributes allows to extend the {@link Solution} classes to incorporate data required by
 * operators or algorithms manipulating them.
 *
 * @author Antonio J. Nebro <antonio@lcc.uma.es>
 */
public interface SolutionAttribute <S extends Solution<?>, V> {
  public void setAttribute(S solution, V value) ;
  public V getAttribute(S solution) ;
  public Object getAttributeID() ;
}

デフォルトの実装は次のようになっている.

package org.uma.jmetal.util.solutionattribute.impl;

public class GenericSolutionAttribute <S extends Solution<?>, V> implements SolutionAttribute<S, V>{

  @SuppressWarnings("unchecked")
  @Override
  public V getAttribute(S solution) {
    return (V)solution.getAttribute(getAttributeID());
  }

  @Override
  public void setAttribute(S solution, V value) {
     solution.setAttribute(getAttributeID(), value);
  }

  @Override
  public Object getAttributeID() {
    return this.getClass() ;
  }
}

この実装ではgetAttributedID()はクラスの識別子を返すことに注意したい.
これは,解に同じクラスの別のattributeを持たせることができないことを意味する.

Example of attrivute: constraints

最適化問題には制約がある場合がある.
これは,解を評価するには,目的関数だけでなく,ある種の制約処理のメカニズムを適用するための制約の評価をする必要がある
SoluttionAttributeは制約情報をSolutionに組み込むために使用される.

jMetalのデフォルトの制約処理メカニズムは,NSGA-IIで定義されている,
OverallConstraintViolationであるため,次のクラスが用意されている.

package org.uma.jmetal.util.solutionattribute.impl;
public class OverallConstraintViolation<S extends Solution<?>> extends GenericSolutionAttribute<S, Double> {
}

これは連続値を指定するGenericSolutionAttributeを拡張した空のクラスです.
通常,次のようにSolultionクラス内で制約を評価する.

package org.uma.jmetal.problem.multiobjective;

/** Class representing problem Binh2 */
public class Binh2 extends AbstractDoubleProblem implements ConstrainedProblem<DoubleSolution> {
  public OverallConstraintViolation<DoubleSolution> overallConstraintViolationDegree ;
  public NumberOfViolatedConstraints<DoubleSolution> numberOfViolatedConstraints ;
  /**
   * Constructor
   * Creates a default instance of the Binh2 problem
   */
  public Binh2() {
    ...
    overallConstraintViolationDegree = new OverallConstraintViolation<DoubleSolution>() ;
    numberOfViolatedConstraints = new NumberOfViolatedConstraints<DoubleSolution>() ;
  }

  /** Evaluate() method */
  @Override
  public void evaluate(DoubleSolution solution) {
     ...
  }

  /** EvaluateConstraints() method */
  @Override
  public void evaluateConstraints(DoubleSolution solution)  {
    double[] constraint = new double[this.getNumberOfConstraints()];

    double x0 = solution.getVariableValue(0) ;
    double x1 = solution.getVariableValue(1) ;

    constraint[0] = -1.0 * (x0 - 5) * (x0 - 5) - x1 * x1 + 25.0;
    constraint[1] = (x0 - 8) * (x0 - 8) + (x1 + 3) * (x1 + 3) - 7.7;

    double overallConstraintViolation = 0.0;
    int violatedConstraints = 0;
    for (int i = 0; i < this.getNumberOfConstraints(); i++) {
      if (constraint[i] < 0.0) {
        overallConstraintViolation += constraint[i];
        violatedConstraints++;
      }
    }

    overallConstraintViolationDegree.setAttribute(solution, overallConstraintViolation);
    numberOfViolatedConstraints.setAttribute(solution, violatedConstraints);
  }

このコードには,指定された解が違反している制約の数を設定するためのNumberOfViolatedConstraintsという別のattributeも含まれている.

(このコードを見る限り,constraintの値は正のとき制約を満たし,負のときは制約違反であるように実装するっぽいですね.)

Example of attribute: ranking

SolutionAttributeを使用することでカプセル化できる.
例として,次のような解にランク(NSGA-II's ranking)を割り当てるインターフェースが定義されている.

package org.uma.jmetal.util.solutionattribute;

import java.util.List;

/**
 * Ranks a list of solutions according to the dominance relationship
 *
 * @author Antonio J. Nebro <antonio@lcc.uma.es>
 */
public interface Ranking<S extends Solution<?>> extends SolutionAttribute<S, Integer>{
  public Ranking<S> computeRanking(List<S> solutionList) ;
  public List<S> getSubfront(int rank) ;
  public int getNumberOfSubfronts() ;
}

したがって,クライアントクラス(例えばNSGA-IIクラス)は,単に以下のように使用することができる.

Ranking ranking = computeRanking(jointPopulation);

このように,解の属性はRankingを実装するクラスに内部的に管理され,アルゴリズムからは隠されている.

2
2
0

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
2