技術
遺伝的アルゴリズム：自然淘汰による検索と最適化
遺伝的アルゴリズムとは何ですか？
過去数年にわたって、人工知能（AI）の周りに素晴らしい話題がありました。グーグル、アップル、マイクロソフトなどの大手企業が積極的にこのトピックに取り組んでいます。実際、AIは多くの目標、アプローチ、ツール、およびアプリケーションをカバーする傘です。遺伝的アルゴリズム（GA）は、考えられる多くのソリューションをインテリジェントに検索するためのツールの1つにすぎません。
GAは、自然進化に存在する原理に基づくメタヒューリスティックな検索および最適化手法です。それは進化的アルゴリズムのより大きなクラスに属しています。
GAは 染色体の集団 —問題の潜在的な解決策のセット。自然淘汰と同様に、「進化」は何世代にもわたって問題の最適な解決策を見つけるという考え方です。
GAは、選択、遺伝子クロスオーバー、突然変異という3つの進化過程を模倣しています。
自然淘汰と同様に、GA淘汰の中心的な概念はフィットネスです。より適合した染色体は、生存の可能性が高くなります。フィットネスは、染色体によって表されるソリューションの品質を測定する関数です。本質的に、母集団内の各染色体は入力パラメーターを表します。たとえば、問題に取引の価格と量などの2つの入力パラメーターが含まれている場合、各染色体は論理的に2つの要素で構成されます。要素が染色体内でどのようにエンコードされるかは別のトピックです。
選択中に、染色体はペアを形成します 親 ために 育種 。各 子 その親から特性を取ります。基本的に、子はその親からの特性の再結合を表します。特性の一部は1つの親から取得され、一部は別の親から取得されます。再結合に加えて、いくつかの特徴は 変異する 。
より適切な染色体はより多くの子供を生み出すので、その後の各世代はより良い適応度を持つでしょう。ある時点で、世代には、問題の十分な解決策となる染色体が含まれます。
GAは強力で、複雑な問題に広く適用できます。従来の最適化手法では解決するのが非常に難しい最適化問題の大きなクラスがあります。遺伝的アルゴリズムは、その解がほぼ最適である効率的なアルゴリズムです。よく知られているアプリケーションには、スケジューリング、輸送、ルーティング、グループテクノロジー、レイアウト設計、ニューラルネットワークトレーニングなどがあります。
物事を実践する
これから説明する例は、GAの「HelloWorld」と見なすことができます。この例は、最初にJ.Freemanによって Mathematicaを使用したニューラルネットワークのシミュレーション 。私はそれを 遺伝的アルゴリズムと工学設計 MitsuoGenとRunweiChengによる。
単語マッチング問題は、遺伝的アルゴリズムを使用して表現を進化させようとします。当初、アルゴリズムは、ランダムに生成された文字のリストから「あるべきかどうか」というフレーズを「推測」することになっています。
リスト内の13の場所[空白を除く]のそれぞれに26の可能な文字があるため、純粋にランダムな方法で正しいフレーズを取得する確率は（1/26）^ 13 = 4.03038×10-19です。 [千億]から2つのチャンス（Gen＆Chong、1997）。
ここでは問題をもう少し広く定義し、解決をさらに困難にします。英語や特定のフレーズに限定されないと仮定しましょう。最終的には、任意のアルファベット、または任意の記号のセットを処理することになります。私たちはその言語の知識がありません。言語があるかどうかさえわかりません。
gulp-minify-css
対戦相手が空白を含む任意のフレーズについて考えたとしましょう。フレーズの長さとアルファベットの記号の数がわかっています。それが私たちが持っている唯一の知識です。それぞれの推測の後、対戦相手は何文字が配置されているかを教えてくれます。
各染色体は、アルファベットの記号のインデックスのシーケンスです。英語のアルファベットについて話している場合、「a」は0で表され、「b」は1で表され、「c」は2で表されます。したがって、たとえば、「be」という単語は[4, 1]として表されます。
Javaコードスニペットを使用してすべての手順を示しますが、 Java 各ステップを理解する必要はありません。
遺伝的アルゴリズムコア
遺伝的アルゴリズムの一般的な実装から始めることができます。
public void find() { // Initialization List population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } } これは、すべてのGAが多かれ少なかれ構成される単純な一連の手順です。初期化ステップで、フレーズの初期母集団を生成します。母集団のサイズはpopulationSizeによって決定されます。フレーズがどのように生成されるかは、supplierの実装によって異なります。
反復ステップ内で、while内で終了条件が満たされるまで母集団を進化させます。ループのテスト。終了条件には、世代数と母集団内のフレーズの1つの完全一致の両方が含まれる場合があります。 termination正確な実装をカプセル化します。
各反復内で、一般的なGAステップを実行します。
- 染色体の適合性に基づいて母集団を選択します。
- クロスオーバー操作で新しい「世代」を生み出します。
- いくつかのフレーズでいくつかの文字の再結合を実行します。
アルゴリズムのコアは非常にシンプルで、ドメインに依存しません。それはすべての問題で同じです。調整する必要があるのは、遺伝子演算子の実装です。次に、前述の各GA演算子を詳しく見ていきます。
選択
すでに知っているように、選択とは、現在の染色体、つまり私たちの問題により適した染色体の後継者を見つけるプロセスです。選択中、適合性の高い染色体が生存する可能性が高くなるようにする必要があります。
private List selection(List population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i { int index = binarySearch(probabilities, random()); if (index <0) { index = -(index + 1); } return population.get(index); }).collect(toList()); } この実装の背後にある考え方は次のとおりです。母集団は、数値軸の結果の範囲として表されます。全人口は0から1の間です。
染色体がとる範囲のチャンクは、その適応度に比例します。これにより、より適切な染色体がより大きなチャンクになります。次に、0から1までの数値をランダムにピークし、その数値を含む範囲を見つけます。明らかに、範囲が広いほど選択される可能性が高くなるため、より適切な染色体は生存する可能性が高くなります。
適応度関数の詳細がわからないため、適応度値を正規化する必要があります。適応度関数はfitnessで表され、染色体を染色体の適応度を表す任意のdoubleに変換します。
コードでは、母集団内のすべての染色体の適合率を見つけ、全体の適合度も見つけます。 for内ループでは、総適合度によってスケールダウンされた確率に対して累積合計を実行します。数学的には、これにより最終変数の値は1になります。浮動小数点の不正確さのため、それを保証することはできません。念のため、1に設定します。
最後に、入力された染色体の数に等しい回数、乱数を生成し、その数を含む範囲を見つけて、対応する染色体を選択します。お気づきかもしれませんが、同じ染色体が複数回選択される場合があります。
クロスオーバー
次に、染色体を「繁殖」させる必要があります。
private void crossover(List population) { final int[] indexes = range(0, population.size()) .filter(i-> random() 事前定義された確率crossoverProbabilityを使用して、繁殖用の親を選択します。選択した親がシャッフルされ、任意の組み合わせが可能になります。親のペアを取り、crossoverを適用しますオペレーター。母集団のサイズを同じに保つ必要があるため、各ペアに演算子を2回適用します。子供たちは人口の中で両親に取って代わります。
突然変異
最後に、特性の再結合を実行します。
private void mutation(List population) { for (int i = 0; i 事前定義された確率mutationProbabilityを使用して、染色体に対して「突然変異」を実行します。突然変異自体はmutationによって定義されます。
問題固有のアルゴリズム構成
次に、一般的な実装に提供する必要のある問題固有のパラメーターのタイプを見てみましょう。
private BiFunction crossover; private double crossoverProbability; private ToDoubleFunction fitness; private Function mutation; private double mutationProbability; private int populationSize = 100; private Supplier supplier; private Predicate termination; パラメータはそれぞれ次のとおりです。
- クロスオーバー演算子
- クロスオーバー確率
- 適応度関数
- 突然変異演算子
- 突然変異確率
- 人口の大きさ
- 初期集団の染色体サプライヤー
- 終了機能
問題の構成は次のとおりです。
new GeneticAlgorithm() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find() クロスオーバー演算子と確率
private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; } クロスオーバーの確率は0.25であるため、平均して染色体の25％がクロスオーバーに選択されると予想されます。染色体のペアのクロスオーバーのための簡単な手順を実行します。乱数を生成しますn範囲[0..length]から、ここでlength染色体の長さです。次に、最初のnを取得して、選択したペアを結合します。 1つの染色体からの文字と2番目の染色体からの残りの文字。
適応度関数
private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); } 適応度関数は、ターゲットフレーズと特定の染色体の間の一致数をカウントするだけです。
突然変異演算子と確率
private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i <2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; } 突然変異操作は、各染色体で独立して実行されます。突然変異の確率は0.05であるため、平均して人口の5％が突然変異すると予想されます。ランダムな文字の位置を選択し、その値をアルファベットのランダムな文字に置き換えることで変化します。変異した染色体ごとに2回行います。
サプライヤー
private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i サプライヤは、アルファベットからランダムな文字を取得してランダムなフレーズを生成します。各フレーズには、一定の定義済みの長さがあります。
終了機能
private boolean termination(Collection chars) { count++; final Optional result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println('Count: ' + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; } 終了関数は呼び出しの数をカウントし、trueを返します完全に一致する場合、または世代数が3,000に達した場合。
実行
これで、アルゴリズムをテストする準備が整いました。数回実行すると、すべての実行が成功するとは限らないことに気付くでしょう。毎回、反復回数は異なります。これは、アルゴリズムの確率的性質によるものです。アルゴリズムには、改善できる点がいくつかあります。クロスオーバーと突然変異の確率で遊ぶことができます。
数値を下げると、安定しているが遅い解決策になります。少数の染色体が遺伝子演算子の影響を受けるため、ソリューションにはより多くの反復が必要になります。
数値を増やすとアルゴリズムが高速化されますが、ソリューションが不安定になります。適合染色体は保存されるだけでなく、遺伝子演算子の影響も受けます。したがって、彼らは彼らの「良い」遺伝子を失うでしょう。
バランスをとることが重要です。反復回数を増やすと、アルゴリズムが解決策を見つける機会が増えますが、その一方で、時間がかかります。クロスオーバーとミューテーションのさまざまな方法を適用することもできます。これらの演算子を適切に選択すると、ソリューションの品質が大幅に向上します。
JavaとノードJSのパフォーマンス
次は何？
ここでは、氷山の一角について説明しました。入力が1つだけで、入力を染色体として簡単に提示できる例を取り上げました。遺伝的演算子は単純明快です。
現実世界の問題を取り上げて、それに遺伝的アルゴリズムを適用することは非常に興味深いことです。実際の入力データをエンコードする際のさまざまなアプローチと、さまざまなクロスオーバーおよびミューテーションの実装について説明します。
メトリックを最適化するために推測する必要のある一連のパラメーターを通じて問題を表現できる場合は、それを解決するために使用できるGAをすばやく設定できます。
最も興味深い問題の1つは、人工ニューラルネットワークを教えることです。最適化可能なパラメーターをシナプスの強さに設定し、フィットネスメトリックをニューラルネットワークが正しい答えを出した入力のパーセンテージに設定できます。その後、私たちは腰を落ち着けて、ニューラルネットワークを私たちが望む理想的なソリューションに進化させることができます。または、進化には時間がかかるため、少なくとも十分に良いものが得られるまでは。
