技術
遺伝的アルゴリズム：自然淘汰による検索と最適化
遺伝的アルゴリズムとは何ですか？
近年、人工知能（AI）に関する騒動が起こっています。グーグル、アップル、マイクロソフトなどの大企業がこの問題に積極的に取り組んでいます。実際、AIは、多くの目標、アプローチ、ツール、およびアプリケーションをカバーする単なる傘です。遺伝的アルゴリズム（GA）は、考えられる多くのソリューションを検討するスマートツールの1つにすぎません。
AGは、メタヒューリスティック検索であり、自然進化に存在する原理に基づく最適化手法です。それは進化的アルゴリズムのより長いクラスに属しています。
AGは 染色体集団 -問題に対する可能な解決策のセット。アイデアは、「進化」が、自然淘汰と同様に、何世代にもわたって問題の最適な解決策を見つけるというものです。
AGは、選択、染色体乗換え、突然変異という3つの進化過程を模倣しています。
良いコードの書き方
自然淘汰と同様に、AG選択の中心的な概念は適応です。適応性の高い染色体は、生存の可能性が高くなります。適応は、染色体によって表される溶液の品質を測定する機能です。本質的に、母集団内の各染色体は、ボリュームや為替レートなどの入力パラメーターを表します。各染色体は、論理的には2つの要素で構成されます。要素が染色体内でどのようにコード化されているかは別の問題です。
選択中に、染色体はペアを形成します 親 のために 再生 。各 子 彼の両親の特徴を取ります。基本的に、子は両親の特性の再結合を表します。特性の一部は一方の親から取得され、一部はもう一方の親から取得されます。組換えに加えて、いくつかの特徴は 変異する 。
最も適切な染色体はより多くの子供を生み出すので、その後の各世代がより適切になります。ある時点で、世代には、私たちの問題に対する十分な解決策を表す染色体が含まれるようになります。
AGは強力で、複雑な問題に広く適用できます。従来の最適化手法を使用して解決するのがやや難しい最適化問題の広範なクラスがあります。遺伝的アルゴリズムは、ほぼ最適なソリューションを持つ効率的なアルゴリズムです。よく知られているアプリケーションには、スケジューリング、輸送、ルート計画、グループテクノロジー、計画設計、ニューラルネットワークトレーニングなどがあります。
物事を実践する
これから説明する例は、AGの「HelloWorld」と見なすことができます。この例は、最初にJ.Freemanによって Mathematicaを使用したニューラルネットワークのシミュレーション 。私はそれを 遺伝的アルゴリズムと工学設計 MitsuoGenとRunweiChengによる。
世界シミュレーション問題は、遺伝的アルゴリズムを使用して式を進化させようとします。最初に、アルゴリズムはランダムに生成された文字のリストから「あるべきかどうか」というフレーズを「推測」する必要があります。
リスト内の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 population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } } これは、すべてのAGが実行する必要のある一連の簡単な手順です。最初のステップでは、フレーズの初期母集団を生成します。母集団のサイズはpopulationSizeによって決定されます。そして、このフレーズがどのように生成されるかは、supplierの実装によって異なります。
反復ステップ内で、ノードテストwhile内で、条件が満たされるまで母集団を進化させます。用語条件には、世代数と母集団内のフレーズの1つの完全一致を含めることができます。 termination正確な実装をカプセル化します。
各反復内で、一般的なAGステップを実行します。
- それは染色体の妥当性の人口の選択を実行します。
- クロスオーバー操作で新しい「世代」を生み出します。
- それはいくつかの文のいくつかの文字の再結合を実行します。
アルゴリズムのコアは非常にシンプルで、ドメインに依存しません。それはすべての問題で同じです。調整する必要があるのは、遺伝子演算子の実装です。次に、前述のAGオペレーターのそれぞれを詳しく見ていきます。
選択
すでに知っているように、選択は現在の染色体の後継者を見つけるために行われるプロセスです—私たちの問題に最も適した染色体です。選択の際、最も一致する染色体が生存する可能性が高くなるようにする必要があります。
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として定義されます。
問題固有のアルゴリズム構成
次に、一般的な実装に提供する必要のある特定の問題パラメーターの種類を見てみましょう。
LLCとはどのような種類の企業ですか
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; パラメータはそれぞれ次のとおりです。1。クロスオーバー演算子2.クロスオーバー確率3.適合性関数4.突然変異演算子5.突然変異確率6.母集団サイズ7.初期母集団の染色体プロバイダー8.関数項
問題の構成は次のとおりです。
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; } 関数という用語は、呼び出しの数をカウントし、完全に一致するものがすでにある場合、または世代数が3,000に達した場合に、trueを返します。
実行
これで、アルゴリズムをテストする準備が整いました。複数回実行すると、すべての実行が成功するとは限らないことに気付くでしょう。毎回、反復回数は異なります。これは、アルゴリズムの確率の性質によるものです。アルゴリズムには、改善できる点がいくつかあります。クロスオーバーと突然変異の確率で遊ぶことができます。
数値を下げて、安定しているが遅い解決策にします。少数の染色体が遺伝子演算子の影響を受けるため、ソリューションにはより多くの反復が必要になります。
数値を増やすとアルゴリズムが高速化されますが、ソリューションが不安定になります。適切な染色体は保存されるだけでなく、遺伝子演算子の影響も受けます。このため、彼らは「良い」遺伝子を失います。
バランスをとることが重要です。反復回数を増やすと、アルゴリズムが解決策を見つける機会が増えますが、その一方で、時間がかかります。また、クロスオーバーと突然変異のさまざまな方法を適用します。これらの演算子を適切に選択すると、ソリューションの品質が劇的に向上します。
次は何ですか？
氷山の一角だけをカバーしました。エントリが1つしかない例を取り上げます。これは、染色体として簡単に提示できます。遺伝演算子は単純です。
実生活から問題を取り上げ、それに遺伝的アルゴリズムを適用することは非常に興味深いことです。実際のデータ入力をエンコードするためのさまざまなアプローチ、およびクロスオーバーとミューテーションのさまざまな実装について説明します。
メトリックを最適化するために推測する必要のある一連のパラメーターを通じて問題を表現できる場合は、問題を解決するために使用できるAGをすばやく確立できます。
最も興味深い問題の1つは、人工ニューラルネットワークを教えることです。最適化されたパラメーターをシナプス力に設定し、適切なメトリックがニューラルネットワークが正しい答えを与えた入力のパーセンテージになるようにすることができます。その後、リラックスしてニューラルネットワークを私たちが望む理想的なソリューションに進化させることができます。または、進化には時間がかかるため、少なくとも十分なものが得られるまでは。
