自然な遺伝的アルゴリズムまたはC ++での生物の進化の証拠

はじめに

ナチュラルコンピューティングモデルは、現代科学で広く使用されています。 その適用範囲は非常に広く、モデリング、人工知能、パターン認識、制御の問題を解決するために使用されます。



自然計算の最も一般的な方法の1つは、遺伝的アルゴリズムです。 これらのアルゴリズムがどのように構成され、どのように機能するかをよりよく理解するために、そのようなアルゴリズムの1つである遺伝子を再現することが決定されました。 特定の問題を解決する方法を適用するには、この方法を習得する必要があります。 したがって、このペーパーで検討する遺伝的アルゴリズムは、特定の問題を解決しません。 主なものは、遺伝的アルゴリズムの作業をモデル化および視覚化するプログラムを作成するプロセスと結果の両方です。 プログラマーの経験は重要です。

このプログラムは、最も原始的な生物の集団の行動をモデル化します。 このプログラムは実用的とは言えませんが、遺伝的アルゴリズムの原理を明確に示しています。

自然選択が環境条件によって決定される遺伝的アルゴリズムの動作のモデリング

モデリングは、モデルの構築と研究を通じて客観的な世界の科学的知識の方法です。



視覚化は、人が情報を提示するための最も便利な方法の1つです。 情報がグラフィカルに表示され、無意味な数字の大きな配列の形ではなく、情報を知覚する方がより便利です。したがって、作業の重要な部分はアルゴリズムのグラフィカル表現です。



何らかの方法を使用する前に、比較的簡単なタスクで、おそらく数回、最初に調査してテストする必要があります。 プログラマーにとって、そのような研究は特定のプログラムを書いています。



C ++プログラミング言語は、強力で実績のあるプログラミング言語であるため、作業用に選択されました。 C ++はプログラマーの間で広まっています。 視覚化には、OpenGLオープングラフィックライブラリが使用されます。

目的と目的

この作業の目的は、作業をモデル化し、環境条件に応じて自然選択が決定される遺伝的アルゴリズムを視覚化するプログラムを作成することです。

タスク

1. 情報源を分析するため。
2. 遺伝的アルゴリズムに関連する基本的な概念を学ぶ
3. 原始的な生物の生物種を作成します。
4. 生物同士の相互作用のシステムを作成します。
5. ライフサイクルを整理します（新しい生物の誕生、平均寿命、生殖および死）。
6. 進化の原動力を作成します。
7. 捕食者と被食者の関係を確立します。
8. 結論として、母集団に関する統計データの収集を実装する必要があります。

ビューを作成

プログラムは、OpenGLオープングラフィックライブラリを使用してC ++プログラミング言語で記述されています。

生物種を表すために、原始生物の座標、速度、寿命、およびその他のパラメーターを含むBioクラスが作成されました。



バイオクラスフィールド

public: Code_bio code; //  float x,y,dx,dy; //   bool life; //   float w,h; //  int num; //   int lifetime; //  float range; //  
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Bioクラスは、コンストラクターを提供します（クラスオブジェクトを作成するため）。

 Bio(void) { life=1; // w=20; //   h=20; num=rand()%10000; range=200; //srand(time(0)); //  x=rand()%(winW-(int)w); y=rand()%(winH-(int)h); //srand(time(0)); dx=rand()%8-4; //  dy=rand()%8-4; lifetime=0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンストラクターに加えて、set（int a、int b）関数を作成する必要があります。この関数を使用して、作成したオブジェクトの座標を手動で設定できます。

 void set(int a,int b){ x=a; y=b; life=true; dx=rand()%8-4; dy=rand()%8-4; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ランダムな動きをシミュレートするために、turn（）関数を導入します。この関数は、オブジェクトをいつでも左または右にランダムな角度で回転させます。

 inline void turn(float vect, int deg) { if((dx!=0)||(dy!=0)) { float grad; if((dx>=0)&&(dy<0)) { dy=-dy; grad=atan(dx/dy)*180/pi; grad+=deg; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; dy=-dy; } if((dx>=0)&&(dy>=0)) { grad=atan(dx/dy)*180/pi; grad=90-grad; grad+=deg; grad=90-grad; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; } if((dx<0)&&(dy<=0)) { dy=-dy; dx=-dx; grad=atan(dx/dy)*180/pi; grad=90-grad; grad+=deg; grad=90-grad; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; dy=-dy; dx=-dx; } if((dx<0)&&(dy>=0)) { dx=-dx; grad=atan(dx/dy)*180/pi; grad+=deg; dx=sin(grad*pi/180)*vect; dy=cos(grad*pi/180)*vect; dx=-dx; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

オブジェクトと画面の端との衝突を処理するには、collx（）およびcolly（）関数が必要です。

 inline void collx() { if(xw/2<0) { x=winW-w/2; } if(x+w/2>winW) { x=w/2; } } inline void colly() { if(yh/2<0) { y=h/2; dy=-dy; } if(y+h/2>winH) { y=winH-h/2; dy=-dy; } } };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで必要なのは、オブジェクトの状態を変更して描画するメイン関数Draw（）のみです。

 void Bio::Draw() { if(life) { if(dx==0)dx=rand()%30/10+1; if(dy==0)dy=rand()%30/10+1; // float min=range; bool ok=0; float x2,y2; list<Predator>::iterator i=preds.begin(); for(;i!=preds.end();i++) { if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<min) { min=sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) ); ok=1; x2=i->x; y2=i->y; } } if(ok) { runaway(code.maxspeed,x2,y2); turn(code.maxspeed,(rand()%(2*(int)code.maxturn+1)*10)/10-(int)code.maxturn); } else turn((rand()%(int)(code.maxspeed-code.minspeed+1)*10)/10+code.minspeed, (rand()%(2*(int)code.maxturn+1)*10)/10-(int)code.maxturn); x+=dx; collx(); y+=dy; colly(); // if(1) { glBindTexture(GL_TEXTURE_2D,bio_tex[0]); glBegin(GL_QUADS); glTexCoord2f(0,1); glVertex2f(xw/2,yh/2); glTexCoord2f(1,1); glVertex2f(x+w/2,yh/2); glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2); glTexCoord2f(0,0); glVertex2f(xw/2,y+h/2); glEnd(); } // makechild(); //.  lifetime++; if(lifetime>code.maxltime) life=0; // w=lifetime/40+20; h=lifetime/40+20; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これでビューの作成が終了します。 ここで、これらすべての生物の貯蔵について疑問が生じます（それらは多数存在します）。 それらの数は、ライフサイクルの結果として絶えず変化します。 動的リスト配列は、それらを格納するのに適しています。

 list<Bio> bios;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ライフサイクル

その結果、最初のタスクが完了します。 次に、人口のライフサイクルと生物の相互作用を整理する必要があります。 プログラムは最も原始的な生物の行動をシミュレートする必要があるため、それらの関係は最も単純です。 2人の個人が衝突すると死亡し、子供たちはランダムな座標（1〜3）で表示されます。 従来のコンピューターのコンピューティングリソースを考慮すると、プログラムは通常の速度で最大200の生物を処理できます。 この量は、安定した人口が存在するのに十分ではないため、生物の数が多すぎたり少なすぎたりしないように、条件が導入されます-人口が50未満の場合、より多くの子供が生まれます（1から4）、数が50を超える場合、生殖は遅くなります



遺伝的アルゴリズムが機能するためには、母集団の各個人が独自の遺伝暗号を持っている必要があります。 このため、プログラム内に別のコード構造が作成されています。 人口の各生物には、この構造の独自のインスタンスがあります。 親の遺伝コードを受け入れ、赤ちゃんのコードを返すクロスオーバー関数も必要です。 これらの原始生物の場合、コードには最小速度と最大速度、最大寿命、最大回転角度のみが含まれます。

 struct Code_bio { int maxltime; float minspeed,maxspeed; int maxturn; }; inline Code_bio childcode(Code_bio c1, Code_bio c2) { // Code_bio c; c.maxltime=(c1.maxltime+c2.maxltime)/2; c.minspeed=(c1.minspeed+c2.minspeed)/2; c.maxspeed=(c1.maxspeed+c2.maxspeed)/2; c.maxturn=(c1.maxturn+c2.maxturn)/2; // c.maxltime+=c.maxltime/100*((rand()%(maxltime_mut*2+1))-maxltime_mut); c.maxspeed+=c.maxspeed/100*((rand()%(maxspeed_mut*2+1))-maxspeed_mut); c.minspeed+=c.minspeed/100*((rand()%(minspeed_mut*2+1))-minspeed_mut); c.maxturn+=c.maxturn/100*(rand()%(maxturn_mut*2+1)-maxturn_mut); return c; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Bioクラスでは、再生機能を追加する必要があります。 この機能は、生物の衝突を検出し、それらを殺して子孫を作成します。

 void Bio::makechild() { list<Bio>::iterator i=bios.begin(); for(;i!=bios.end();i++) { if(num!=i->num) { if((lifetime>200)&&(i->lifetime>200)) if(sqrt((xi->x)*(xi->x))+((yi->y)*(yi->y))<w+i->w) { life=0; i->life=0; int c; if(bios.size()<50) c=rand()%4+1; else c=rand()%3+1; for(int j=0;j<c;j++) { Bio b; b.code=childcode(code,i->code); bios.push_back(b); } } } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

レンダリング機能では、変更を加える必要があります：複製を追加します。 すべてのオブジェクトは、20ミリ秒の間隔でタイマー機能で描画されます。 同じ機能で、プログラムはすべての死んだ個人（人生の価値が偽）を削除します。

 list<Bio>::iterator i=bios.begin(); for(;i!=bios.end();i++) i->Draw(); bios.remove_if([](Bio b) {return (b.life==0);}); // 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

捕食者

遺伝的アルゴリズムはまだいくつかの問題を解決する必要があるため、このタスクを設定する必要があります。 この場合、タスクは最も適応した生物を見つけることです。 人口は進化の結果として改善し続けます。 各次世代は​​、環境条件によりよく適応します。 進化の推進要因を作成する必要があります。これにより、最も適応した個人が選択されます。 この要因は捕食者になります。



捕食者は、被害者のように多くの場合があります。 Bioクラスの捕食者クラスは、捕食者が繁殖して死ぬことができないという点でのみ異なります。 それらの数は、プログラム全体で常に固定されます。



プレデタークラスフィールド

 public: float x,y,dx,dy,speed; bool life; float w,h; int num; int lifetime; float range; float hungry;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

手動で作成するためのデフォルトのコンストラクターおよびset（）関数。

 Predator(void) { life=1; w=100; h=100; num=rand()%10000; range=250; speed=10.2; hungry=0;//1*1000/20; //srand(time(0)); x=rand()%(winW-(int)w); y=rand()%(winH-(int)h); //srand(time(0)); dx=rand()%8-4; dy=rand()%8-4; lifetime=0; } void set(int a,int b) { x=a; y=b; life=true; dx=rand()%8-4; dy=rand()%8-4; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

空き時間に、捕食者はランダムな動きをします。 方向を変えるためのturn（）関数は、Bioクラスの同様のメソッドと違いはありません。 捕食者が被害者に追いつくためには、狙い（）関数が必要です。この機能は、被害者の座標と、捕らえなければならない速度を取ります。

 inline void aim(float vect, float x2, float y2) { dx=((x2-x)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); dy=((y2-y)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

メインのDraw（）関数では、捕食者が空腹の場合、その環境を見て、最も近い獲物を見つけて追いかけます。 彼が空腹でない場合、彼は誤って画面を動き回るでしょう。

 inline void Draw() { if(life) { if(dx==0)dx=rand()%30/10+1; if(dy==0)dy=rand()%30/10+1; //  bool ok=0; float x2,y2; if(hungry<=0) { float min=range; list<Bio>::iterator i=bios.begin(); for(;i!=bios.end();i++) { if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<w/2+i->w/2-10) { i->life=0; hungry=0.01*1000/20; } else if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<min) { min=sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) ); ok=1; x2=i->x; y2=i->y; } } } if(ok) aim(speed,x2,y2); else turn(6,(rand()%(2*15+1)*10)/10-15); x+=dx; collx(); y+=dy; colly(); // if(view) { glBindTexture(GL_TEXTURE_2D,pred_tex[0]); glBegin(GL_QUADS); glTexCoord2f(0,1); glVertex2f(xw/2,yh/2); glTexCoord2f(1,1); glVertex2f(x+w/2,yh/2); glTexCoord2f(1,0); glVertex2f(x+w/2,y+h/2); glTexCoord2f(0,0); glVertex2f(xw/2,y+h/2); glEnd(); } //.  // // hungry--; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

捕食者の動的な配列を作成することだけが残っています。

 list<Predator> preds;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

捕食者と被食者の関係

捕食者と獲物との関係が正しく機能するためには、捕食者に捕食者から逃げるように教える必要があります。 そうでなければ、捕食者は単に獲物を食べるだけで、進化は起こりません。 これを行うには、暴走（）メソッドをBioクラスに追加します。 これは、被害者の捕食者による追跡の方法に似ており、反対方向にのみオブジェクトを向けます。

 inline void runaway(float vect, float x2, float y2) { dx=((x-x2)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); dy=((y-y2)*vect)/sqrt( (x-x2)*(x-x2)+(y-y2)*(y-y2) ); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最後に、BioクラスのDraw関数を最終的に変更する必要があります。 単純な混oticとした動きに加えて、捕食者の検出とそこからの逃避を追加する必要があります。

 if(dx==0)dx=rand()%30/10+1; if(dy==0)dy=rand()%30/10+1; // float min=range; bool ok=0; float x2,y2; list<Predator>::iterator i=preds.begin(); for(;i!=preds.end();i++) { if(sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) )<min) { min=sqrt( (xi->x)*(xi->x)+(yi->y)*(yi->y) ); ok=1; x2=i->x; y2=i->y; } } if(ok) runaway(code.maxspeed,x2,y2); else turn((rand()%(int)(code.maxspeed-code.minspeed+1)*10)/10+code.minspeed, (rand()%(2*code.maxturn+1)*10)/10-code.maxturn);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

捕食者が速い獲物を捕まえる可能性は、遅い獲物を捕まえる可能性よりも小さい。 その結果、速い個体は環境条件により良く適応し、平均人口速度の増加が徐々に観察されます。

進化の原理

進化が機能するためには、さらにいくつかの重要なポイントを作成する必要がありました。 捕食者が獲物を追いかけ始めると、獲物は反対方向に逃げます。 犠牲者の速度が捕食者の速度よりはるかに遅い場合、進化は起こりません。なぜなら、その速度にわずかな進化的変化があれば、捕食者はまだ犠牲者を追いつき、食べるからです。 被害者の速度が捕食者の速度よりも速い場合、追い詰められない限り、追い詰めることはできません。 残るオプションは1つだけです。獲物の速度は、捕食者の速度とほぼ等しくなければなりません。 そうすれば、被害者の速度にわずかな進化的変化があったとしても、彼女は他の人よりも大きな優位性を持つことになります。 捕食者はそのような獲物を捕まえる可能性が低くなります。



プログラムが初期集団を作成すると、すべての個体に同じ遺伝子型が設定され、同じ最高速度と最低速度が示されます。 子孫遺伝子型のすべてのパラメーターは、親のパラメーターの算術平均として計算されます。 たとえば、子の最大速度は、親の平均速度の算術平均になります。 遺伝的アルゴリズムをこの方法で実行すると、進化は機能しません。 すべての遺伝子型は単純に平均化され、同じになります。 異なる遺伝子型の初期集団を作成しても、進化はありません。 自然選択と進化の推進要因に加えて、突然変異は退屈です。 必要なのは、算術平均を計算した後、プラス/マイナス10％に変更することだけです。 その後、交配の結果としての一部の個体はより速く生まれ、一部の個体はより遅く生まれ、進化が機能します。



動作中、プログラムはサイズ、平均、最小、最大速度の10秒ごとに4つのファイルに総人口指標を記録します。 これらのデータを使用して、遺伝的アルゴリズムの結果を確認し、母集団の進化について結論を出すことができます。



収集されたデータの断片：



数、最小 スピードマックス 速度、平均 速度：

45.00 1.01842 9.83393 5.42617

54.00 1.01048 10.214 5.61252

53.00 1.00726 10.4374 5.72231

51.00 0.932109 10.1463 5.53921

48.00 0.93236 10.6849 5.80864

45.00 0.908688 11.0295 5.96907

46.00 0.888795 11.1242 6.0065

51.00 0.894669 11.1927 6.04366

48.00 0.933062 11.679 6.30601

52.00 0.92753 11.9278 6.42764

54.00 0.899226 12.3086 6.6039

51.00 0.875113 12.52 6.69756

43.00 0.902515 12.84 6.87124



これらのデータに基づいて、グラフが構築されます。







グラフは、進化の結果として、すべての生物の平均最大速度が10倍に増加したことを示しています。 これは、生物の進化における本当に大きな飛躍です。 このグラフから、すべての生物の平均最低速度は変化していないと結論付けることもできます。 これは、クリーチャーの動きの特性によるものです。 彼らは捕食者から逃げているわけではありませんが、画面の周りをランダムな方向に走っているだけです。 ただし、その速度もランダムに変化します。 遺伝子型に埋め込まれた可能な最小速度と、遺伝子型にも埋め込まれた可能な最大速度の間のランダムな値を取ります。 しかし、これらの生物が敵から逃げるとき、彼らは可能な限り最高の速度で逃げます。 グラフが示すように、最も適した個体の選択を生み出す進化の駆動因子は、可能な限り最大速度のみを変化させる理由です。

結果と結論

1. 遺伝的アルゴリズムの操作のために、人工生物種が作成されました。
2. 生物同士の相互作用のシステムが作成されました。
3. ライフサイクルは組織化されます（新しい生物の誕生、平均寿命、生殖および死）。
4. 進化の原動力として捕食者が作成されました。
5. 捕食者と獲物の相互作用は組織化されています。
6. 統計データの例が収集されます。これは、アルゴリズムの動作を明確に示し、作成された母集団の進化を証明します。

左下には捕食者がいます。

おわりに

作成されたプログラムは、記載されているすべての要件を満たしています。 一見、特定の社会的に有用なタスクを実行しませんが、遺伝的アルゴリズムの原理を明確に示しています。 このプログラムに実装されているアルゴリズムは非常に単純ですが、その仕組みを理解しないと、より複雑な遺伝的アルゴリズムを作成することはできません。

文学

1. Ershov N. M.並列コンピューティングの自然モデル[電子リソース] URL： naturalmodels.blogspot.ru （アクセス05/10/14）。

2. R. Laforet「C ++でのオブジェクト指向プログラミング」、第4版、2011年。

3. B. I. Pakhomov「C / C ++およびMS Visual C ++ 2012」。