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

admin

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

ここ数年、人工知能（AI）が大変な話題になっています。 Google、Apple、Microsoftといった大企業が積極的に取り組んでいます。 実際、AI は、多くの目標、アプローチ、ツール、およびアプリケーションをカバーする傘となっています。 遺伝的アルゴリズム (GA) は、多くの可能なソリューションをインテリジェントに検索するツールの 1 つです。

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

GA は染色体 (問題に対する潜在的な解の集合) の集団を維持します。 自然淘汰と同様に、GAも3つの進化プロセス、すなわち選択、遺伝子交叉、突然変異を模倣しています。 より適合度の高い染色体は生き残る可能性が高くなる。 適合度とは、染色体が表す解の質を測る関数である。 要するに、母集団内の各染色体は入力パラメータを表しているのです。 例えば、取引における価格と出来高のような2つの入力パラメータが問題に含まれる場合、各染色体は論理的に2つの要素で構成されます。

染色体は淘汰される過程で、繁殖のための両親のペアを形成します。 それぞれの子は親から特徴を受け継ぎます。 基本的には、子供は両親からの特性の組換えを表します。 あるものは片方の親から、あるものはもう片方の親から。

適正な染色体はより多くの子供を生むので、後続の世代はより適性が高くなります。 ある時点で、ある世代は我々の問題に対して十分に良い解を表す染色体を含むようになる。

GA は強力で、複雑な問題にも広く適用できる。 従来の最適化技術では解くのがかなり困難な最適化問題の大きなクラスがある。 遺伝的アルゴリズムは、その解が近似的に最適となる効率的なアルゴリズムである。 よく知られた応用例としては、スケジューリング、輸送、ルーティング、グループ技術、レイアウト設計、ニューラルネットワークの学習などがあります。

実践

これから見る例は、GAの「ハローワールド」と考えることができます。 この例は最初J. Freemanが「Simulating Neural Networks with Mathematica」で示したものです。 私は、Genetic Algorithms and Engineering Design by Mitsuo Gen and Runwei Cheng から引用しました。

Word-Matching Problem は、遺伝的アルゴリズムで式を進化させようとするものです。 最初は、アルゴリズムはランダムに生成された文字のリストから「to be or not to be」のフレーズを「推測」することになっている。

リスト中の13ヶ所にそれぞれ26文字の可能性があるので、純粋なランダムで正しいフレーズを得る確率は (1/26)^13=4.0 である。03038×10-19となり、約2回のチャンスになります（Gen & Chong, 1997）。

ここで問題をもう少し広く定義して、解法をさらに難しくしておきます。 英語や特定のフレーズに限定されないと仮定しよう。 私たちは任意のアルファベット、あるいは任意の記号のセットを扱うことになります。 私たちは、その言語に関する知識はない。 言語があるのかどうかも全くわからない。

相手が空白を含む任意のフレーズを考えたとしよう。 我々はそのフレーズの長さとアルファベットの記号の数を知っている。 それだけが我々の知識である。 5710>

各染色体は、アルファベットの記号のインデックスの列です。 英語のアルファベットであれば、「a」は0、「b」は1、「c」は2、・・・と表現されます。 たとえば、「be」という単語は「1316」と表されます。

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

Genetic Algorithm Core

遺伝的アルゴリズムの一般的な実装から始めます：

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. いくつかのフレーズでいくつかの文字の組換えを実行する。 すべての問題で同じになる。 チューニングが必要なのは、遺伝的演算子の実装です。

    Selection

    既にご存知のように、選択とは現在の染色体の後継となる染色体、つまり問題に適合した染色体を見つけることです。 このとき、より適合度の高い染色体が生き残るようにする必要があります。

    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; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses / totalFitness; probabilities = sum; } probabilities = 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());}

    この実装の考え方は以下の通りです。 母集団は数値軸上の結果的な範囲として表現される。

    Visual demonstration of how the selection step in our genetic algorithm works

    染色体が取る範囲の塊は、その適性に比例します。 この結果、適合度の高い染色体はより大きな塊を得ることになります。 次に、0から1の間の数字をランダムに覗き込み、その数字を含む範囲を探します。 明らかに、範囲が大きい方が選択される可能性が高く、したがって、適合した染色体は生き残るチャンスがあります。

    適性関数について詳しく知らないので、適合度の値を正規化する必要があります。 適性関数はfitnessで表され、染色体の適性を表す任意のdoubleに変換します。

    コードでは、集団内の全染色体の適性率を求め、さらに合計適性も求めています。 forループの中で確率の累積和を総適合度によって縮減しています。

    最後に、入力された染色体数と同じ回数だけ、乱数を発生させ、その乱数を含む範囲を求め、対応する染色体を選択します。

    交叉

    次に、染色体を交配させます。

    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; final int index2 = indexes; 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回演算子を適用する。

    Mutation

    最後に、特性の組換えを行います。

    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％の染色体が交叉に選択されると予想されます。 一対の染色体の交叉について、簡単な手順を実行します。 染色体の長さをlengthとすると、の範囲から乱数nを発生させます。

    適合度関数

    private double fitness(char value) { return range(0, value.length) .filter(i -> value == expected) .count();}

    適合度関数は、対象となる語句と与えられた染色体の間の一致数を数えるだけである。 突然変異の確率は0.05ですから、平均して母集団の5％が突然変異を起こすと予想されます。 突然変異はランダムな文字の位置を選び、その値をアルファベットからランダムな文字に置き換えることによって行う。

    Supplier

    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 = ALPHABET; } return result;}

    The supplierはアルファベットからランダムに文字を選び、ランダムなフレーズを生成します。

    Termination Function

    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;}

    終了関数は呼び出し回数をカウントし、完全に一致するか、生成回数が3000回に達したらtrueを返す。 何度か実行してみると、すべての実行が成功するわけではないことに気がつくだろう。 毎回、反復回数は異なるだろう。 これはアルゴリズムの確率的な性質によるものである。 このアルゴリズムには、改良できる点がいくつかあります。 クロスオーバーと突然変異の確率で遊ぶことができます。

    数を下げると、安定した解が得られますが、遅い解になります。 染色体の数が少ないと遺伝的作用素の影響を受けるので、解に要する反復回数が多くなります。

    数を増やすとアルゴリズムは速くなりますが、解は不安定になります。

    数を増やすとアルゴリズムは速くなりますが、解が不安定になります。

    うまくバランスをとることが重要です。 反復回数を増やすと、アルゴリズムが解を見つける機会が増えるが、その反面、時間がかかる。 また、クロスオーバーとミューテーションの異なる方法を適用することができます。 これらの演算子をうまく選択することで、解の質が劇的に向上します。

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

    現実の問題を取り上げて、遺伝的アルゴリズムを適用するのは非常に面白いことです。 実際の入力データのエンコードにおけるさまざまなアプローチや、異なるクロスオーバーやミューテーションの実装を発見できるだろう。

    ある問題を、メトリックを最適化するために推測しなければならないパラメータのセットで表現できる場合、それを解くために使用できるGAをすぐにセットアップすることが可能だ。 最適化可能なパラメータをシナプスの強さに設定し、適合度メトリックをニューラルネットワークが正しい答えを出した入力のパーセンテージに設定することができる。 あとは、ニューラルネットワークを私たちが望む理想的な解に進化させるために、じっくりと腰を据えることができる。 少なくとも、進化には時間がかかるので、十分なものが得られるまで、です

    。

コメントを残す

メールアドレスが公開されることはありません。