遺伝的アルゴリズム-視覚的な実装

約4年前、大学で遺伝的アルゴリズムなどの最適化手法について聞いたことがあります。 彼についてどこでも正確に2つの事実が報告されました：彼はクールで、彼は働きません。 むしろ、動作しますが、ゆっくりと、信頼性が低く、どこにも使用できません。 しかし、彼は進化のメカニズムを美しく示すことができます。 この記事では、この単純な方法の例に基づいて進化のプロセスを実際に見る美しい方法を紹介します。 あなたはほんの少しの数学、プログラミング、そして想像力に満ちたこのすべてを必要とします。

アルゴリズムについて簡単に

それでは、遺伝的アルゴリズムとは何ですか？ これは、まず第一に、多次元最適化の方法です。 多次元関数の最小値を見つける方法。 おそらく、この方法はグローバルな最適化に使用できますが、これには困難があります。後で説明します。



この方法の本質は、進化のプロセスを調整することです：増殖し、突然変異の影響を受ける何らかの種類（ベクトルのセット）があり、目的関数を最小化することに基づいて自然選択が行われます。 これらのプロセスをより詳細に検討してみましょう。



したがって、まず、人口を増やす必要があります 。 生殖の基本原理は、子孫がその親に似ているということです。 つまり 何らかの継承メカニズムを要求する必要があります。 そして、ランダム性の要素が含まれていると良いでしょう。 しかし、そのようなシステムの開発率は非常に低く、遺伝的多様性は低下し、人口は減少しています。 つまり 関数の値は最小化されなくなります。



この問題を解決するために、 突然変異メカニズムが導入されました。これは、一部の個人のランダムな変更から成ります。 このメカニズムにより、遺伝的多様性に新しいものをもたらすことができます。

次の重要なメカニズムは選択です。 言われたように、選択は、機能を最小化する個人の選択です（生まれた人からのみ可能ですが、すべてから可能です-実践はこれが決定的な役割を果たさないことを示します）。 通常、繁殖前と同じ数の個体が選択されるため、時代から個体までの個体数は一定です。 また、「幸運な人」を選択することも習慣的です。おそらく、機能を最小限に抑えながら、次の世代に多様性をもたらす特定の数の個人です。



多くの場合、これらの3つのメカニズムでは機能を最小限に抑えることはできません。 そのため、母集団は縮退します-遅かれ早かれ、ローカル最小値は母集団全体をその値で詰まらせます。 これが発生すると、ほぼすべての人口が破壊され、新しい（ランダムな）個人が追加されると、彼らは揺れと呼ばれるプロセスを実行します（類推の性質上、グローバルな大変動）。



ここに古典的な遺伝的アルゴリズムの説明がありますが、実装は簡単で、想像力と研究の余地があります。

問題の声明

したがって、この伝説的な（不運ではあるが）アルゴリズムを実装しようとすることを既に決めたとき、何を最小化するかという結論に達しましたか？ 通常、それらはサイン、コサインなどで恐ろしい多次元関数を取ります。 しかし、これはあまり面白くなく、まったく明確ではありません。 単純なアイデアが1つありました-値が明るさの原因となる画像は、多次元ベクトルの表示に優れています。 したがって、単純な関数を導入することができます-ピクセル輝度の違いで測定されたターゲット画像までの距離。 単純さと速度のために、明るさ0または255の画像を撮影しました。



数学の観点から見ると、このような最適化は単なる些細なことです。 このような関数のグラフは、巨大な多次元の「ピット」です（図の3次元の放物面のような）。これは、勾配に沿って進むと必然的にスライドします。 唯一のローカルミニマムはグローバルです。 。



唯一の問題は、下降できるパスの数がすでに大幅に削減されており、合計で測定と同じ数の方向（つまり、ピクセル数）があることです。 明らかに、遺伝的アルゴリズムを使用してこの問題を解決することは価値がありませんが、人口で起こっている興味深いプロセスを見ることができます。

実装

最初の段落で説明したすべてのメカニズムが実装されました。 複製は、「母」と「父」からのランダムなピクセルを単に交差させることによって実行されました。 突然変異は、ランダムな個人のランダムなピクセルの値を反対に変更することによって行われました。 5ステップで最小値が変わらない場合は、揺れた。 その後、「極端な突然変異」が行われます-交換は通常よりも集中的に行われます。



元の写真としてノノグラム（「日本のスキャンワード」）を取りましたが、実際には、黒い四角だけを撮ることができます-まったく違いはありません。 以下は、複数の画像の結果です。 ここでは、「家」を除くすべてについて、突然変異の数は個人ごとに平均で100であり、人口には100人が存在し、伝播すると人口は4倍に増加しました。 ラッキーは各時代で30％でした。 家については、より小さい値が選択されました（人口の30人、1人あたり50人の突然変異）。







繁殖で「ラッキーなもの」を使用すると、個体群の最小化傾向が減少することが実験的にわかりましたが、停滞状態から抜け出すのに役立ちます。 グラフからわかること：左のグラフは、幸運な人との「ファラオ」人口の発達を示しています。







したがって、非常に長い時間ではありますが、このアルゴリズムによって問題を解決できることがわかります。 大きな画像の場合、揺れが多すぎると、母集団内の多数の個人を解決できます。 この投稿の範囲を超えて、さまざまな次元のパラメーターの最適な選択を残します。

グローバル最適化

前述のように、ローカルな最適化は、多次元の場合でもかなり簡単な作業です。 アルゴリズムがグローバル最適化にどのように対処するかを見るのははるかに興味深いです。 ただし、このためには、最初に多くの極小値を持つ関数を作成する必要があります。 私たちの場合、これはそれほど難しくありません。 距離からいくつかの画像（家、恐竜、魚、ボート）までの距離を最小にするだけで十分です。 その後、最初のアルゴリズムがランダムな穴に「スリップ」します。 そして、あなたはそれを数回実行することができます。



しかし、この問題にはさらに興味深い解決策があります：ローカルミニマムに滑り込んで、強い揺れ（または個人を新たに開始する）を行い、既知のミニマムに近づくと罰金を追加することを理解できます。 ご覧のとおり、写真は交互に表示されます。 元の機能に触れる権利はありません。 ただし、ローカルの最小値を記憶し、独自にペナルティを追加することができます。



この写真は、極小値に達したとき（強い停滞）、人口が単純に死んだときの結果を示しています。







ここでは、人口が死亡し、わずかな罰金が（通常の距離から既知の最小値まで）追加されます。 これにより、繰り返しの可能性が大幅に減少します。







人口が死なず、単に新しい条件に順応し始めたときのほうが興味深い（次の図）。 これは、0.000001 * sum ^ 4の形式の罰金で達成されます。この場合、新しい画像は少しうるさくなります。







このノイズは、ペナルティを最大（0.000001 * sum ^ 4、20）に制限することにより除去されます。 しかし、4番目のローカルミニマム（恐竜）に到達できないことがわかります。これは、おそらく他の最小値に近すぎるためです。

生物学的解釈

この言葉を恐れずに、シミュレーションからどのような結論を引き出すことができますか？ まず第一に、私たちは有性生殖-発達と適応性の最も重要なエンジンを見ます。 しかし、それだけでは十分ではありません。 ランダムで小さな変更の役割は非常に重要です。 それらは進化の過程で動物の新しい種の出現を提供し、我々は人口の多様性を提供します。



地球の進化における最も重要な役割は、自然災害と大量絶滅（恐竜、昆虫などの絶滅-約10の大きなものがありました-下の図を参照）によって果たされました。 これは、モデリングによって確認されました。 そして、「幸運な人」の選択は、今日の最も弱い生物が将来の将来の世代の基礎になることができることを示しました。



彼らが言うように、すべては人生のようです。 この日曜大工進化法は、興味深いメカニズムと開発におけるその役割を明確に示しています。 もちろん、（もちろん、ディフラに基づいた）より多くの価値のある進化モデルがあり、それらはより生命に近い要素を考慮に入れています。 もちろん、より効果的な最適化方法があります。

PS

ここではすべてがゴーレムマトリックスであり、写真を操作するためのツールがあるため、プログラムをMatlab（または、Octaveでも）で作成しました。 ソースコードが添付されています。