遺伝図書館の紹介
1前書き
このシリーズの目的
は、遺伝的アルゴリズムの概念を説明し、最も知られている実装を示すことです。
このチュートリアルでは、さまざまな最適化問題を解決するために使用できる非常に強力なJenetics Javaライブラリについて説明します。
遺伝的アルゴリズムについてもっと学ぶ必要があると思うなら、
この記事
から始めることをお勧めします。
2どのように動作しますか？
そのhttp://jenetics.io[公式文書]によると、JeneticsはJavaで書かれた進化的アルゴリズムに基づいたライブラリです。進化的アルゴリズムは、生殖、突然変異、組み換え、選択など、生物学的進化にヒントを得たメカニズムを使用するため、生物学にそのルーツがあります。
JeneticsはJavaの
Stream
インタフェースを使って実装されているので、他のJavaの
Stream
APIとスムーズに連携します。
主な機能は次のとおりです。
-
摩擦のない最小化
– を変更したり微調整する必要はありません
フィットネス機能
Engine
の設定を変更するだけです
クラスと私たちは私たちの最初のアプリケーションを開始する準備が整いました
依存関係なし** – ランタイムのサードパーティ製ライブラリは必要ありません
Jeneticsを使うために
Java 8対応** –
Stream
とλ式の完全サポート
-
マルチスレッド
– 進化的ステップは並行して実行することができます
Jeneticsを使用するためには、__pom.xmlに以下の依存関係を追加する必要があります。
<dependency>
<groupId>io.jenetics</groupId>
<artifactId>jenetics</artifactId>
<version>3.7.0</version>
</dependency>最新版はhttps://search.maven.org/classic/#search%7Cga%7C1%7Ca%3A%22jenetics%22[Maven Central]にあります。
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のもう一つのユースケースはhttps://en.wikipedia.org/wiki/Subset__sum__problem[サブセット和問題]を解決することです。簡単に言うと、最適化の課題は、整数のセットを考えれば、合計がゼロである空でないサブセットを見つける必要があるということです。
このような問題を解決するために、Jeneticsには事前定義されたインターフェースがあります。
[source,java,gutter:,true]
public class SubsetSum implements Problem<ISeq<Integer>, EnumGene<Integer>, Integer> {
//implementation
}
ご覧のとおり、3つのパラメータを持つ__Problem <T、G、C> __を実装しています。 ** __ ** <T> ** __ - 問題適合度関数の引数の型。 不変で順序付けられた、固定サイズの__Integer__シーケンスの場合 __ISeq <整数> __ ** __ ** <G> ** __ - 進化エンジンが扱っている遺伝子型 ケース、可算__Integer__遺伝子__EnumGene <Integer> __ ** __ ** <C> ** __ - 適合度関数の結果の型。ここでそれは __整数__ __Problem <T、G、C> __インターフェースを使うためには、2つのメソッドをオーバーライドする必要があります。 [source,java,gutter:,true]
@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番目の例では、一般的な問題のエンコーディングを作成するためのファクトリメソッドを含むクラスです。 今度は主要部分に進むことができます。初めに、問題で使用するためのサブセットを作成する必要があります。 [source,java,gutter:,true]
SubsetSum problem = of(500, 15, new LCG64ShiftRandom(101010));
Jeneticsが提供する__LCG64ShiftRandom__ジェネレータを使っています。次のステップでは、ソリューションのエンジンを構築しています。 次のステップでは、ソリューションのエンジンを構築しています。 [source,java,gutter:,true]
Engine<EnumGene<Integer>, Integer> engine = Engine.builder(problem)
.minimizing()
.maximalPhenotypeAge(5)
.alterers(new PartiallyMatchedCrossover<>(0.4), new Mutator<>(0.3))
.build();
我々は、表現型の年齢と子孫を変えるために使われる変更者を設定することによって、結果を最小にすることを試みる（最適には結果は0になる）。次のステップで結果を得ることができます。 [source,java,gutter:,true]
Phenotype<EnumGene<Integer>, Integer> result = engine.stream()
.limit(limit.bySteadyFitness(55))
.collect(EvolutionResult.toBestPhenotype());
述語を返す__bySteadyFitness（）__を使用していることに注意してください。指定された世代数の後でより良い表現型が見つからない場合は進化の流れが切り捨てられ、最良の結果が得られます。私たちがラッキーになり、ランダムに作成されたセットに対する解決策があるならば、私たちはこれに似た何かを見るでしょう: 私たちがラッキーになり、ランダムに作成されたセットに対する解決策があるならば、私たちはこれに似た何かを見るでしょう: [source,text,gutter:,true] ----[85|-76|178|-197|91|-106|-70|-243|-41|-98|94|-213|139|238|219]--> 0
そうでなければ、サブセットの合計は0とは異なります。
3.3. ナップザックファーストフィット問題
Jeneticsライブラリを使うと、https://en.wikipedia.org/wiki/Knapsack__problem[Knapsack problem]のような、より洗練された問題を解決することができます。
簡単に言えば、この問題ではナップザックのスペースが限られているので、どのアイテムを中に入れるかを決める必要があります。
バッグのサイズとアイテムの数を定義することから始めましょう。
int nItems = 15;
double ksSize = nItems ** 100.0/3.0;
次のステップでは、
KnapsackItem
オブジェクト（
size
フィールドと
value
フィールドで定義）を含むランダム配列を生成し、First Fitメソッドを使用して、これらの項目をナップザックの内側にランダムに配置します。
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には非常に重要な機能もあります。シミュレーション期間全体からすべての統計と洞察を簡単に収集できます。** これを行うには、
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ライブラリーの機能について説明しました。
コードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-genetic[GitHub]でMavenプロジェクトとして入手可能です。
Springsteen Record
（はい、存在します）およびTraveling Salesmanの問題。
遺伝的アルゴリズムの他の例を含むシリーズのすべての記事については、以下のリンクをチェックしてください。
Java]**
The Traveling
Javaのセールスマン問題]**
アントコロニー最適化
-
遺伝学図書館入門（こちら）
