ジェネティクスライブラリの紹介

投稿日: 2019-10-19 2022-10-27
タグ: Algorithms

1. 序章

このシリーズの目的は、遺伝的アルゴリズムの概念を説明し、最もよく知られている実装を示すことです。

このチュートリアルでは、さまざまな最適化問題を解くために使用できる非常に強力なJeneticsJavaライブラリについて説明します。

遺伝的アルゴリズムについてさらに学ぶ必要があると思われる場合は、この記事から始めることをお勧めします。

2. それはどのように機能しますか？

その公式文書によると、JeneticsはJavaで書かれた進化的アルゴリズムに基づくライブラリです。進化的アルゴリズムは、生殖、突然変異、組換え、選択などの生物学的進化に触発されたメカニズムを使用するため、生物学にルーツがあります。

JeneticsはJavaStream インターフェースを使用して実装されているため、残りのJava StreamAPIとスムーズに連携します。

主な機能は次のとおりです。

摩擦のない最小化–適応度関数を変更または微調整する必要はありません。 Engine クラスの構成を変更するだけで、最初のアプリケーションを開始する準備が整います。
依存関係なし–Jeneticsを使用するために必要なランタイムサードパーティライブラリはありません
Java8対応– Streamおよびラムダ式の完全サポート
マルチスレッド–進化のステップを並行して実行できます

Jeneticsを使用するには、pom.xmlに次の依存関係を追加する必要があります。

<dependency>
    <groupId>io.jenetics</groupId>
    <artifactId>jenetics</artifactId>
    <version>3.7.0</version>
</dependency>

最新バージョンは、MavenCentralのにあります。

3. ユースケース

Jeneticsのすべての機能をテストするために、単純なバイナリアルゴリズムから始まり、ナップサック問題で終わる、さまざまなよく知られた最適化問題の解決を試みます。

3.1. 単純な遺伝的アルゴリズム

最も単純なバイナリ問題を解決する必要があると仮定しましょう。ここでは、0と1で構成される染色体の1ビットの位置を最適化する必要があります。まず、問題に適したファクトリを定義する必要があります。

Factory<Genotype<BitGene>> gtf = Genotype.of(BitChromosome.of(10, 0.5));

長さが10で、染色体に1が含まれる確率が0.5のBitChromosomeを作成しました。

それでは、実行環境を作成しましょう。

Engine<BitGene, Integer> engine
  = Engine.builder(SimpleGeneticAlgorithm::eval, gtf).build();

eval（）メソッドはビットカウントを返します。

private Integer eval(Genotype<BitGene> gt) {
    return gt.getChromosome().as(BitChromosome.class).bitCount();
}

最後のステップでは、進化を開始し、結果を収集します。

Genotype<BitGene> result = engine.stream()
  .limit(500)
  .collect(EvolutionResult.toBestGenotype());

最終的な結果は次のようになります。

Before the evolution:
[00000010|11111100]
After the evolution:
[00000000|11111111]

遺伝子内の1の位置を最適化することができました。

3.2. サブセット和問題

Jeneticsのもう1つの使用例は、サブセット和問題を解くことです。簡単に言うと、最適化するための課題は、整数のセットが与えられた場合、合計がゼロである空でないサブセットを見つける必要があるということです。

このような問題を解決するために、Jeneticsには事前定義されたインターフェイスがあります。

public class SubsetSum implements Problem<ISeq<Integer>, EnumGene<Integer>, Integer> {
    // implementation
}

ご覧のとおり、問題、これには3つのパラメータがあります。

–問題の適応度関数の引数タイプ、この場合は不変、順序付け、固定サイズ整数順序 ISeq
–進化エンジンが使用している遺伝子タイプ、この場合はカウント可能整数遺伝子 EnumGene
–適応度関数の結果タイプ。ここにあります整数

を使用するには問題インターフェイスでは、2つのメソッドをオーバーライドする必要があります。

@Override
public Function<ISeq<Integer>, Integer> fitness() {
    return subset -> Math.abs(subset.stream()
      .mapToInt(Integer::intValue).sum());
}

@Override
public Codec<ISeq<Integer>, EnumGene<Integer>> codec() {
    return codecs.ofSubSet(basicSet, size);
}

最初の関数では、適応度関数を定義しますが、2番目の関数は、一般的な問題のエンコーディングを作成するためのファクトリメソッドを含むクラスです。たとえば、この場合のように、特定の基本セットから最適な固定サイズのサブセットを見つけます。

これで、主要部分に進むことができます。最初に、問題で使用するサブセットを作成する必要があります。

SubsetSum problem = of(500, 15, new LCG64ShiftRandom(101010));

Jeneticsが提供するLCG64ShiftRandomジェネレーターを使用していることに注意してください。次のステップでは、ソリューションのエンジンを構築しています。

次のステップでは、ソリューションのエンジンを構築しています。

Engine<EnumGene<Integer>, Integer> engine = Engine.builder(problem)
  .minimizing()
  .maximalPhenotypeAge(5)
  .alterers(new PartiallyMatchedCrossover<>(0.4), new Mutator<>(0.3))
  .build();

表現型の年齢と子孫を変更するために使用される変更者を設定することにより、結果を最小化しようとします（最適には結果は0になります）。次のステップで、結果を取得できます。

Phenotype<EnumGene<Integer>, Integer> result = engine.stream()
  .limit(limit.bySteadyFitness(55))
  .collect(EvolutionResult.toBestPhenotype());

述語を返すbySteadyFitness（）を使用していることに注意してください。これにより、指定された世代数の後に適切な表現型が見つからない場合、進化ストリームが切り捨てられ、最良の結果が収集されます。運が良ければ、ランダムに作成されたセットの解決策があると、次のようなものが表示されます。

運が良ければ、ランダムに作成されたセットの解決策があると、次のようなものが表示されます。

[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219] --> 0

それ以外の場合、サブセットの合計は0とは異なります。

3.3. ナップザックファーストフィット問題

Jeneticsライブラリを使用すると、ナップサック問題などのさらに高度な問題を解決できます。簡単に言えば、この問題では、ナップザックのスペースが限られているため、中に入れるアイテムを決定する必要があります。

バッグのサイズとアイテムの数を定義することから始めましょう。

int nItems = 15;
double ksSize = nItems * 100.0 / 3.0;

次のステップでは、 KnapsackItem オブジェクト（sizeおよびvalueフィールドで定義）を含むランダム配列を生成し、それらのアイテムをランダムに内部に配置しますファーストフィット法を使用したナップザック：

KnapsackFF ff = new KnapsackFF(Stream.generate(KnapsackItem::random)
  .limit(nItems)
  .toArray(KnapsackItem[]::new), ksSize);

次に、Engineを作成する必要があります。

Engine<BitGene, Double> engine
  = Engine.builder(ff, BitChromosome.of(nItems, 0.5))
  .populationSize(500)
  .survivorsSelector(new TournamentSelector<>(5))
  .offspringSelector(new RouletteWheelSelector<>())
  .alterers(new Mutator<>(0.115), new SinglePointCrossover<>(0.16))
  .build();

ここで注意すべき点がいくつかあります。

人口サイズは500です
子孫はトーナメントとルーレット盤の選択によって選ばれます
前のサブセクションで行ったように、新しく作成された子孫の変更者も定義する必要があります

Jeneticsの非常に重要な機能も1つあります。シミュレーション期間全体からすべての統計と洞察を簡単に収集できます。これを行うには、 EvolutionStatistics クラス：

EvolutionStatistics<Double, ?> statistics = EvolutionStatistics.ofNumber();

最後に、シミュレーションを実行してみましょう。

Phenotype<BitGene, Double> best = engine.stream()
  .limit(bySteadyFitness(7))
  .limit(100)
  .peek(statistics)
  .collect(toBestPhenotype());

評価統計は、世代ごとに更新されており、7世代に限定され、合計で最大100世代になります。より詳細には、2つの可能なシナリオがあります。

7つの安定した世代を達成すると、シミュレーションが停止します
100世代未満で7つの安定した世代を取得できないため、2番目の limit（）のためにシミュレーションが停止します。

最大世代数の制限を設けることが重要です。そうしないと、シミュレーションが妥当な時間内に停止しない場合があります。

最終結果には多くの情報が含まれています。

+---------------------------------------------------------------------------+
|  Time statistics                                                          |
+---------------------------------------------------------------------------+
|             Selection: sum=0,039207931000 s; mean=0,003267327583 s        |
|              Altering: sum=0,065145069000 s; mean=0,005428755750 s        |
|   Fitness calculation: sum=0,029678433000 s; mean=0,002473202750 s        |
|     Overall execution: sum=0,111383965000 s; mean=0,009281997083 s        |
+---------------------------------------------------------------------------+
|  Evolution statistics                                                     |
+---------------------------------------------------------------------------+
|           Generations: 12                                                 |
|               Altered: sum=7 664; mean=638,666666667                      |
|                Killed: sum=0; mean=0,000000000                            |
|              Invalids: sum=0; mean=0,000000000                            |
+---------------------------------------------------------------------------+
|  Population statistics                                                    |
+---------------------------------------------------------------------------+
|                   Age: max=10; mean=1,792167; var=4,657748                |
|               Fitness:                                                    |
|                      min  = 0,000000000000                                |
|                      max  = 716,684883338605                              |
|                      mean = 587,012666759785                              |
|                      var  = 17309,892287851708                            |
|                      std  = 131,567063841418                              |
+---------------------------------------------------------------------------+

今回は、合計値が716,68のアイテムを最適なシナリオで配置することができました。また、進化と時間の詳細な統計を見ることができます。

テストする方法は？

これは非常に単純なプロセスです。問題に関連するメインファイルを開き、最初にアルゴリズムを実行するだけです。一般的な考え方がわかったら、パラメーターを試してみることができます。

4. 結論

この記事では、実際の最適化問題に基づいたJeneticsライブラリの機能について説明しました。

このコードは、GitHubでMavenプロジェクトとして入手できます。 Springsteen Record （はい、存在します！）や巡回セールスマン問題などの最適化の課題のコード例を提供したことに注意してください。

遺伝的アルゴリズムの他の例を含むシリーズのすべての記事については、次のリンクを確認してください。

getdocs

13036