進化をプレイしましょうか？ スクリーンセーバーの遺伝的アルゴリズム

先月軍隊で。 さまざまな興味深いプロジェクトの時間を徐々に解放しました。 脳を占有するものを正確に決定するだけです。 私はリチャード・ドーキンスの利己的な遺伝子を読み終え、アイデアが定式化されました-進化の原理を使用して視覚化を行いたいです。





図1.細菌集団は、そのニーズに合わせて環境を再構築します。



どうぞ！

• ペトリ皿とプログラムのアイデア
• プログラミング言語、環境、ライブラリ
• 作業バージョンが単純すぎる
• 追加のアイデア
• 最初の興味深い結果
• 最適化、構成
• プログラミング動作
• 便利な機能
• デブリーフィング、計画
• プログラム、ソース、手順へのリンク

ペトリ皿とプログラムのアイデア

平らな表面に粘性のある栄養液がこぼれたペトリ皿を想像してください。 どこかで食物の濃度が高く、どこかで低い。 カップのいくつかの場所で、同じ粘性の毒物を、いくつかの場所で-信号物質（「フェロモン」）を追加し、表面にバクテリアのコロニーを均等に分布させました。 私たちに残されているのは、特定の環境への適応性を高める興味深い突然変異の成長を観察することです。 似たようなことをしたかった。



ペトリ皿自体（競技場）では、すべてが最初から明確でした-食品、毒、フェロモンの2次元配列で、各フレームがゆっくりと混ざり合っています（通常のブラーで）。 競技場は閉じています-トーラスの表面を表します。 しかし、細菌の実装ではそれほど単純ではありません。 それらが特定のセル内のフィールドに個別に配置されている場合、複雑なルールのみで別のセルラーオートマトンを受け取ります。 したがって、それらの基本的な物理モデルを作成する価値があります-衝突はありませんが、フロート座標、速度、および摩擦があります。 そして、細菌が相互作用する食物、毒またはフェロモンは、野外の最も近い細胞から選択されます。



バクテリアは栄養培地からエネルギーを受け取り、毒とフェロモンを分泌することができます。 蓄積された食料は1秒ごとに消費され、アクション（移動、ターン、割り当て）も内部リソースを消費します。 細菌は、一定量の食物を蓄積した後、単純な分裂により無性生殖します。 さらに、身体には、有害な環境や空腹時に減少するライフポイントがあります。 死にかけている細菌は、わずかな食物を残します。 毒はバクテリアの成長を阻害し、シグナル伝達物質はある生物が他の生物に他のことを伝えることを可能にします：「この領域はすでに占領されているので、ここに食べ物を集めることは有益ではありません」

アイデアが定式化されたので、実装を開始します。

プログラミング言語、環境、ライブラリ

私は少しcheし、最近のプロジェクトを出発点として使用しましたが、その中核には、構成、マウス、キーボード、カメラの操作に必要なものすべてが含まれていました。 言語-C ++ 11（ GCC 4.8.1、MinGW ）、開発環境-NetBeans 7.4 （および場合によってはSublime Text 3 ）グラフィックス（OpenGL）を操作するためのライブラリとしてSFML 2.1を選択し、 設定を保存するjsoncppを選択しました。 残念ながら、開発の初期段階ではバージョン管理システムをインストールすることはできませんでしたが、これは人生を大きく損なっていました。 そのような機会が現れるとすぐに-tortoiseHgで水銀 。 ご覧のとおり、すべてがクロスプラットフォームであり、必要に応じて、他のシステムでプレイすることも可能です（現在はXPのみが手元にあります）。

作業バージョンが単純すぎる

私は最初、液体のフィールドを浮動小数点数の配列として作成しました。そのため、プログラムの最も遅い部分は、CPU上のこのフィールドをぼかすことでした。 ただし、後で最適化について。 バクテリアの動きは非常に単純です。実際、このコードはすべての物理を正常に処理します（ Verlet統合を使用しています）。

Math::Vector tmp = this->position; this->position += this->position - this->old_position; this->old_position = this->position - (1.0f - this->settings.friction) * (this->position - tmp);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、変異のバリエーションと動作について説明します。 速度やサイズなどの「物理」パラメータを変更したくありませんでした。動作を変更する方がはるかに興味深いです。 したがって、各細菌には一連のアクションが含まれています。

 MOVE, ROTATE_LEFT, ROTATE_RIGHT, CREATE_FEROMON, CREATE_POISON
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

各アクションは浮動小数点数であり、その値は動きの「強さ」を決定します。 したがって、バクテリアのクローンを作成する場合、何らかのアクションの価値はある程度の確率で変化する可能性があります。



明らかに、このような「難しい」行動でbehaviorを調理することはありませんが、結果は私たちが望むよりもさらに悪いものです。 毒を分泌する細菌はすべて、子孫を残すことなくすぐに死んだ。 誰も（私を除いて）分泌されたフェロモンに注意を払いませんでした（これまでのところ、細菌にはセンサーがありませんでした）。 その結果、誰もがちょうど航海し、その下に食べ物を貪り、そして繁殖に必要な食べ物の蓄積で、彼らはまだ同じ愚かな生き物を作成しました。



唯一の美しい結果は、細菌を低毒耐性に設定したが、死後に大量の食物が放出されたときでした。 この場合、放出された毒で死にかけていましたが、栄養価が高く攻撃的な環境での出産に十分な子孫を残すことができました。





図2.高速クローニングと有毒環境

追加のアイデア

どうやら、有毒な「毒」と「フェロモン」という信号の概念は非常に悪い結果をもたらします。

• メーカーとその子孫を殺す毒を生産することは有益ではありません。
• フェロモンを生産することは有益ではありません（そして、受容体の存在下でも）、バクテリアの存在を与えますが、その「外観」を報告しません。

性質の異なる2つの独立した物質を拒否し、それらの代わりに、各細菌を「理想的な環境のポイント」にしました。 比率が強いほど、混合物のクリーチャーに対する毒性は大きくなります。 この点（抵抗）の値は、親細菌から娘細菌にわずかな歪みをもって伝達されます。





スキーム1.身体にとって理想的な環境

最初の興味深い結果

したがって、さまざまな環境で生き残ることができ、周りの世界を変えるのに有益な生き物の全集団が発生します。 ある集団の理想的な環境は別の集団にとって有害で​​あり、各集団は食物を得る必要があるため、競争が生じるはずでした。 そしてそれが起こった：





図3. 2つの異なる母集団が環境を再構築します。

最適化

結果はおもしろいですが、速度には多くの要望があります。フレームあたり50〜60ミリ秒で16〜20 FPSが得られます。 プロファイリングにはgprofを使用しますが、gprofを使用しなくても、プログラムのボトルネックがCPU上の「液体」の配列を曖昧にしていることは明らかです。 そして、現在の実装（異なる色の3つの流体、洗い流して画面に表示する必要があります）とGPUでの書き換えを要求します。 SFMLでは、シェーダーの操作とテクスチャへのレンダリングは非常に簡単です。 1つの欠点は、浮動小数点テクスチャのサポートがないことです。 したがって、すべての液体をフロート（-1.0から1.0）からunsigned char（0、255）に転送し、sf :: Imageとして保存します。 フィールドを更新するとき、ぼかしシェーダーでテクスチャにレンダリングします。 GLSLフラグメントシェーダーを記述します（最初は、おそらくいくつかの係数を使用して、現在のテクセルとその近傍の通常の算術平均で十分です）。

 uniform sampler2D texture; uniform float blurSize; uniform float horizontalPass; uniform float sigma; uniform float width; uniform float height; vec2 ranged(vec2 v) { if (vx < 0.0) vx += 1.0; else if (vx >= 1.0) vx -= 1.0; if (vy < 0.0) vy += 1.0; else if (vy >= 1.0) vy -= 1.0; return v; } void main() { vec2 texcoordOffset = vec2(1.0, 1.0) / vec2(width, height); float k0 = 1.0; float k1 = 0.5; float k2 = 0.357; vec4 avgValue = texture2D(texture, gl_TexCoord[0].st) * k0 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, -1.0))) * k1 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, -1.0))) * k1 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, 1.0))) * k1 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, 1.0))) * k1 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(-1.0, 0.0))) * k2 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(1.0, 0.0))) * k2 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(0.0, -1.0))) * k2 + texture2D(texture, ranged(gl_TexCoord[0].st - texcoordOffset * vec2(0.0, 1.0))) * k2; gl_FragColor = avgValue / (k0 + 4.0 * k1 + 4.0 * k2); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

作業速度はすぐに2〜2.5倍に増加しました。 最適化の余地があります。 gprofを使用すると、さらにいくつかのボトルネックが見つかります。



それでもやはり、最も不快なボトルネックはコード内のマジックナンバーです。そのため、設定を変更するたびにプロジェクトを再構築する必要があります。 すべての設定をjson configに転送するのは非常に簡単ですが、結果には価値があります。





図5.同様の集団による環境の再編成





図6.コロニーの増殖が遅い

プログラミング動作

現時点では、細菌はその行動を変えることができません。 そのアクションを定義するアクション配列は、細菌の子孫でのみわずかに変化し、その生涯を通じて一定のままです。 一般に、進化のプロセスにより、集団の行動は徐々に変化しています-有害な突然変異は遮断され、有用な突然変異が蓄積されます。 しかし、ここでの利点は非常に相対的な概念です。



たとえば、バクテリアは{FEROMON = -0.5、POISON = 0.2}という環境にあり、その理想的な環境は{FEROMON = 0.6、POISON = 0.6}です。 したがって、環境を理想に近づけるために、両方の物質を少量生産することは彼女にとって有益です。 しかし、彼女は止めることができず、しばらくして、毒とフェロモンを合成し続け、彼女は理想から離れて自分自身を破壊します。 環境を監視して決定を下すために「バクテリアを教える」としたら？



これを行う方法を決定することは残っています。 アセンブラーに似た言語のアイデアがあり、その指示が細菌の遺伝子コードを構成します。 しかし、この場合、ある有用な行動プログラムから別の行動プログラムに移行するには多くの突然変異が必要であり、突然変異の大部分は致命的です。



おそらくニューラルネットワーク？ 私は各細菌が2層の小さなパーセプトロンといくつかのフィードバックから脳を作ることを試みました。 最初の細菌を作成するときの結合の重みはランダムであり、その子孫で変異します。 それはまったく脳なしよりもさらに悪いことが判明しました。 この小さな実験が良い結果をもたらすとは思っていませんでした。 進化の選択は、最も適応したニューラルネットワークを単純に残すことができなかったと思われます。 細菌の周囲の環境は長寿命のために攻撃的すぎるため、最初はニューラルネットワークが完全に訓練されておらず、細菌に無意味な、または有害なコマンドさえも与えていました。



すぐに新しいアイデアが思いついた-条件。 私の場合の状態は次のようになります。

1受容体-結果に影響を与える入力データ：FOOD、FEROMON、POISON、SPEED、FAT、LIFE、FEROMON_RESIST、POISON_RESIST。

2条件付き間隔-条件が真であると見なされる受容体値の間隔

3アクション-条件が正確に影響するもの：MOVE、ROTATE_LEFT、ROTATE_RIGHT、CREATE_FEROMON、CREATE_POISON

4操作-条件が満たされた場合のアクションの変更方法：APPEND（「アクションの値」がアクション値に追加される）、DEDUCT（「アクションの値」がアクション値から減算される）、CLEAR（アクション値がゼロになる）

5強度-アクションが変化する数。



したがって、条件：

 RECEPTOR[min, max], ACTION,OPERATION,VALUE.
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

培地中の細菌{-0.5、0.2}と理想的な培地{0.6、0.6}の状況を考えてみましょう。 このような一連の条件は、理想的な環境の作成と維持を彼女に提供します。

 FEROMON[-1.0,-0.4] CREATE_FEROMON APPEND 0.1 FEROMON[0.6,1.0] CREATE_FEROMON DEDUCT 0.1 POISON[-1.0,-0.5] CREATE_ POISON APPEND 0.1 POISON [0.7,1.0] CREATE_ POISON DEDUCT 0.1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、そのような条件はあなたが非常に効率的に食べ物を得ることができるようにします

 FOOD [0.0, 2.0] MOVE APPEND 1.0 // ,     FOOD [2.0, 10.0] MOVE CLEAR 0.0 // ,    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

すべての遺伝情報を保存する別のDNAクラスを作成しました。 細菌が増殖すると、特定の確率で各遺伝子を削除または複製できます。 新しい、幸せな遺伝子条件遺伝子を追加する可能性があります。 一連の条件に加えて、細菌の最大速度と理想的な環境の価値がDNAに保存されます。 バクテリアに別のアクションを掛けようとしましたが、活性化には条件も使用する必要がありましたが、結果は鈍いものでした。 しかし、そのような「条件付き」遺伝子の使用の1つの特徴は、私には興味がありそうでした。 たとえば、バクテリアは常に低速で回転することが有益です。 しかし、移動すると、すべての受容体の値が変化します。バクテリアは、常に回転する必要があることをどのように示しますか？ 進化は、条件が明らかに真である個人を選択することがありました。たとえば、毒0.4に対する耐性を持つPOSION_RESIST [0.3、0.6]です。 一方では、このアプローチにより、細菌は環境や受容体パラメーターに関係なく特定のアクションを実行でき、他方では、理想的な環境の変異のばらつきを制限します（耐性が特定の限界を超える細菌はすべての無条件のアクションを失うため）。



ちなみに、ある条件の課題は食料の供給にも費やされるため、大量のゴミ遺伝子の条件を作成することは、進化的に採算が取れません。 依存性に気づくことができます（個々のバクテリアのDNAを見る）-より多くの食物、より多くのごみ遺伝子がDNAに保存されます。



視覚的側面からのマイナスは、細菌が条件に応じて異なる色（フェロモンと毒の比率）を生成する能力であり、色集団への美しい分裂は忘却に沈みました。





図7.条件付き行動をとる人口による食物摂取。

便利な機能

プログラムにインタラクティブ機能を追加しないことは不可能でした。 たとえば、毒、食物またはフェロモンを引き出す能力。 すべての管理機能について説明します。

1. カメラ制御：
   
   
   1. スクロール -カメラのズームイン/ズームアウト
   2. スクロールキーでドラッグ -カメラを移動
2. 描画：
   1. マウスの左ボタン -現在のブラシで描画
   2. アップ -ブラシのサイズ変更
   3. ダウン -インクの変更
   4. すべての液体の明確な画面-q
3. 可視化：
   
   
   1. 細菌の表示/表示- スペース
   2. すべてのフレームを* .pngで保存-F8
   3. 死にかけているバクテリアは赤くなり、飢えているバクテリアはシアンの色合いになります。
4. 速度：
   
   
   1. 操作モードの切り替え（低速/高速/一時停止）- マウスの右ボタン
5. 情報：
   
   
   1. マウスに最も近い細菌のDNAに関する情報を取得するには（時間の停止時に、遺伝子の前に1/0を使用することをお勧めします-最後のフレームで条件が満たされたかどうか） -i
6. プログラム設定：
   
   
   1. ウィンドウ設定-data / settings.json
   2. フォルダー設定の保存-data / screensaver.json
   3. フィールド設定、バクテリアなど -ai.json （ファイルが破損または削除された場合、自動的に復元されます）

デブリーフィング、計画

このプログラムは元々、マイクロプロトタイプとして作成され、15分間再生されました。 しかし、引きずられた。 したがって、コードにはプロトタイプのすべての欠点がありますが、それを排除する予定です。 結果は、中間バージョン（DNAなしおよびマルチカラーの個体群）ほど美しくありません。例えば、起源に応じて細菌を染色するなど、他の視覚化オプションを検討する価値があります。 もう1つの重要な問題は、食物の量のバランスが取れていないことです。プログラムが一晩中機能し、集団が死なないように設定を選択することは困難です。



これが私が近い将来に変えたいものです。

1. フィールドセルの浮動小数点値の回復（ただし、ビデオカード上にある）。フロートからucharへの一定の変換（損失あり）を削除します。
2. 最適化。 バクテリアのクローニングなど、多くのボトルネック。
3. 並列化。 プログラムは単一のスレッドで実行されますが、プログラムは完全に並列化される必要があります。
4. 物質の自動バランス。 必要に応じてフィールドに食べ物を追加します
5. エデンの園。 その後の培養で最も成功した細菌の選択。

プログラム、ソース、手順へのリンク

プログラムの最新のコンパイル済みバージョン

プログラムのソースコード （実行フォルダー内のコンパイル済みバージョン）には、 SFML 2.1およびjsoncppが必要です 。 最後の瞬間まで、box2d（前のプロジェクトの遺産）のb2vec2をベクターとして使用し、最後のコミットでのみ、自己記述ベクターに置き換えたことに注意する必要があります。 したがって、古いバージョンを収集する場合は、新しいMath :: Vectorをそこからcore / math / vector.hに転送します



ai.jsonの設定で遊んで、ai.exeを実行し、進化を追跡します（または積極的に介入します）。



素敵な進化を！