遺伝的アルゴリズム：自然淘汰による検索と最適化

遺伝的アルゴリズムとは何ですか？

過去数年にわたって、人工知能（AI）の周りに素晴らしい話題がありました。 グーグル、アップル、マイクロソフトなどの大手企業が積極的にこのトピックに取り組んでいます。 実際、AIは多くの目標、アプローチ、ツール、およびアプリケーションをカバーする傘です。 遺伝的アルゴリズム（GA）は、考えられる多くのソリューションをインテリジェントに検索するためのツールの1つにすぎません。

GAは、自然進化に存在する原理に基づくメタヒューリスティックな検索および最適化手法です。 これは、より大きなクラスの進化的アルゴリズムに属しています。

GAは染色体の集団を維持します—問題の潜在的な解決策のセットです。 自然淘汰と同様に、「進化」は何世代にもわたって問題の最適な解決策を見つけるという考え方です。

GAは、選択、遺伝子交差、突然変異という3つの進化過程を模倣しています。

自然淘汰と同様に、GA淘汰の中心的な概念はフィットネスです。 より適合した染色体は、生存の可能性が高くなります。 フィットネスは、染色体によって表されるソリューションの品質を測定する関数です。 本質的に、母集団内の各染色体は入力パラメーターを表します。 たとえば、問題に取引の価格とボリュームなどの2つの入力パラメーターが含まれている場合、各染色体は論理的に2つの要素で構成されます。 要素が染色体内でどのようにエンコードされるかは別のトピックです。

選択中、染色体は繁殖のための親のペアを形成します。 それぞれの子供はその親から特徴を取ります。 基本的に、子はその親からの特性の再結合を表します。特性の一部は1つの親から取得され、一部は別の親から取得されます。 組換えに加えて、いくつかの特性は変化する可能性があります。

より適切な染色体はより多くの子供を生み出すので、その後の各世代はより良い適応度を持つでしょう。 ある時点で、世代には、私たちの問題に対する十分な解決策を表す染色体が含まれるようになります。

GAは強力で、複雑な問題に広く適用できます。 従来の最適化手法では解決するのが非常に難しい最適化問題の大きなクラスがあります。 遺伝的アルゴリズムは効率的なアルゴリズムであり、その解はほぼ最適です。 よく知られているアプリケーションには、スケジューリング、輸送、ルーティング、グループテクノロジー、レイアウト設計、ニューラルネットワークトレーニングなどがあります。

物事を実践する

これから説明する例は、GAの「HelloWorld」と見なすことができます。 この例は、Mathematicaを使ったニューラルネットワークのシミュレーションでJ.Freemanによって最初に与えられました。 私はそれをMitsuoGenとRunweiChengによるGeneticAlgorithmsandEngineeringDesignから取得しました。

単語一致問題は、遺伝的アルゴリズムを使用して表現を進化させようとします。 当初、アルゴリズムは、ランダムに生成された文字のリストから「生きるべきか、死ぬべきか」というフレーズを「推測」することになっています。

リスト内の13の場所[空白を除く]のそれぞれに26の可能な文字があるため、純粋にランダムな方法で正しいフレーズを取得する確率は（1/26）^ 13 = 4.03038×10-19であり、これは約[千億]から2つのチャンス（Gen＆Chong、1997）。

ここでは、問題をもう少し広く定義し、解決をさらに困難にします。 私たちが英語や特定のフレーズに限定されていないと仮定しましょう。 最終的には、任意のアルファベット、または任意の記号のセットを処理することになります。 私たちはその言語の知識がありません。 言語があるかどうかさえわかりません。

対戦相手が空白を含む任意のフレーズについて考えたとしましょう。 フレーズの長さとアルファベットの記号の数がわかります。 それが私たちが持っている唯一の知識です。 それぞれの推測の後、対戦相手は何文字が配置されているかを教えてくれます。

各染色体は、アルファベットの記号のインデックスのシーケンスです。 英語のアルファベットについて話している場合、「a」は0で表され、「b」は1で表され、「c」は2で表されます。 したがって、たとえば、「be」という単語は[4, 1]として表されます。

Javaコードスニペットを使用してすべての手順を示しますが、各手順を理解するためにJavaの知識は必要ありません。

遺伝的アルゴリズムコア

遺伝的アルゴリズムの一般的な実装から始めることができます。

 public void find() { // Initialization List<T> 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ステップを実行します。

1. 染色体の適合性に基づいて母集団を選択します。
2. クロスオーバー操作で新しい「世代」を生み出します。
3. いくつかのフレーズでいくつかの文字の再結合を実行します。

アルゴリズムのコアは非常にシンプルで、ドメインに依存しません。 すべての問題で同じになります。 調整する必要があるのは、遺伝子演算子の実装です。 次に、前述の各GA演算子を詳しく見ていきます。

選択

すでにご存知のように、選択とは、現在の染色体の後継者、つまり私たちの問題により適した染色体を見つけるプロセスです。 選択中、適合性の高い染色体が生存する可能性が高くなるようにする必要があります。

 private List<T> selection(List<T> 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 < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

この実装の背後にある考え方は次のとおりです。母集団は、数値軸の結果の範囲として表されます。 全人口は0から1の間です。

染色体がとる範囲のチャンクは、その適合性に比例します。 これにより、フィッター染色体がより大きなチャンクになります。 次に、0から1までの数値をランダムにピークし、その数値を含む範囲を見つけます。 明らかに、範囲が広いほど選択される可能性が高くなるため、より適切な染色体は生存する可能性が高くなります。

適応度関数の詳細がわからないため、適応度値を正規化する必要があります。 適応度関数は、染色体を、染色体の適応度を表す任意のdoubleに変換するfitnessで表されます。

コードでは、母集団内のすべての染色体の適応度を見つけ、全体の適応度も見つけます。 forループ内で、総適合度によってスケールダウンされた確率の累積合計を実行します。 数学的には、これにより最終変数の値は1になります。浮動小数点の不正確さのため、それを保証することはできません。念のため、1に設定します。

最後に、入力された染色体の数に等しい回数、乱数を生成し、その数を含む範囲を見つけて、対応する染色体を選択します。 お気づきかもしれませんが、同じ染色体が複数回選択される場合があります。

クロスオーバー

今、私たちは染色体を「繁殖」させる必要があります。

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

事前定義された確率crossoverProbabilityを使用して、繁殖する親を選択します。 選択した親がシャッフルされ、任意の組み合わせが可能になります。 親のペアを取り、 crossover演算子を適用します。 母集団のサイズを同じに保つ必要があるため、ペアごとに2回演算子を適用します。 子供たちは人口の中で両親に取って代わります。

突然変異

最後に、特性の再結合を実行します。

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

事前定義された確率mutationProbabilityを使用して、染色体に対して「突然変異」を実行します。 ミューテーション自体はミューmutationによって定義されます。

問題固有のアルゴリズム構成

次に、ジェネリック実装に提供する必要のある問題固有のパラメーターのタイプを見てみましょう。

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

パラメータはそれぞれ次のとおりです。

1. クロスオーバー演算子
2. クロスオーバー確率
3. フィットネス機能
4. 突然変異演算子
5. 突然変異確率
6. 人口の大きさ
7. 初期集団の染色体サプライヤー
8. 終了機能

問題の構成は次のとおりです。

 new GeneticAlgorithm<char[]>() .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％がクロスオーバーに選択されると予想されます。 染色体のペアのクロスオーバーのための簡単な手順を実行します。 [0..length]の範囲から乱数nを生成します。ここで、 lengthは染色体の長さです。 次に、1つの染色体から最初のn文字を取得し、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 < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

サプライヤは、アルファベットからランダムな文字を取得してランダムなフレーズを生成します。 各フレーズには、一定の定義済みの長さがあります。

終了機能

private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> 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; }

終了関数は呼び出しの数をカウントし、完全に一致する場合、または生成カウントが3,000に達した場合にtrueを返します。

実行

これで、アルゴリズムをテストする準備が整いました。 何度か実行すると、すべての実行が成功するわけではないことに気付くでしょう。 毎回、反復回数は異なります。 これは、アルゴリズムの確率的な性質によるものです。 アルゴリズムには、改善できる点がいくつかあります。 クロスオーバーと突然変異の確率で遊ぶことができます。

数値を下げると、安定しているが遅い解決策になります。 少数の染色体が遺伝子演算子の影響を受けるため、ソリューションにはより多くの反復が必要になります。

数値を増やすとアルゴリズムは高速化されますが、ソリューションが不安定になります。 適合染色体は保存されるだけでなく、遺伝子演算子の影響も受けます。 したがって、彼らは彼らの「良い」遺伝子を失うでしょう。

バランスをとることが重要です。 反復回数を増やすと、アルゴリズムが解決策を見つける機会が増えますが、その一方で、時間がかかります。 クロスオーバーとミューテーションのさまざまな方法を適用することもできます。 これらの演算子を適切に選択すると、ソリューションの品質が大幅に向上します。

次は何？

ここでは、氷山の一角について説明しました。 入力が1つだけで、入力を染色体として簡単に表示できる例を取り上げました。 遺伝演算子は単純明快です。

現実世界の問題を取り上げて、それに遺伝的アルゴリズムを適用することは非常に興味深いことです。 実際の入力データをエンコードする際のさまざまなアプローチと、さまざまなクロスオーバーおよびミューテーションの実装について説明します。

メトリックを最適化するために推測する必要のある一連のパラメーターを使用して問題を表現できる場合は、問題を解決するために使用できるGAをすばやく設定できます。

最も興味深い問題の1つは、人工ニューラルネットワークを教えることです。 最適化可能なパラメーターをシナプスの強さに設定し、フィットネスメトリックをニューラルネットワークが正しい答えを出した入力のパーセンテージに設定できます。 その後、私たちは腰を落ち着けて、ニューラルネットワークを私たちが望む理想的なソリューションに進化させることができます。 または、進化には時間がかかるため、少なくとも十分なものが得られるまでは。