Robocodeを例として使用した遺伝的アルゴリズム

この記事が書かれたとき、 「遺伝的アルゴリズム」というフレーズのhabrapoiskは気高い空虚を裏切っていました。 しかし、不十分なレベル*検閲によって切り取られた*は出版日を遅らせ、今や、恥ずかしくて退屈な物myいの後、この記事は世界に自分自身を示す機会を得ました。 この期間中に、類似のトピックに関する少なくとも3つの（多くの人が私の目に触れた）記事が公開されました。以下の文章を初めて読むことはおそらくないでしょう。 そのような人々には、GAを科学的および科学的に説明するための未経験の若者の次の試みから鼻をかむのではなく、プログラミングゲームRobocodeのGAに基づくボットの作成を説明する第2部の次の展示に行くことを提案します。 最新のインテリジェンスによると、これはまだハブで満たされていません

パート1 遺伝的アルゴリズムの寿命と仕事。

遠くから始めましょう。 対処する必要があるタスクのセットがいくつかあります。 私たちの目標は、 Given （タスクの初期条件）をResponse （ターゲット状態）に変換できるアクションを見つけることです。



状況が単純で、そのような問題の解決策がこれらのマットの助けを借りて条件から明確に計算できる場合、ここで、私たちの知恵なしですべてがうまくいき 、 私たちはめちゃくちゃです、私たちはすべて同意しません 。 たとえば、二次方程式を解くとき、答え（値x1、x2）は、学校で教えた式を適用することにより、初期条件（係数a、b、c）から得られます。 そして、教科書に必要な公式がないとき、より悲しいケースで何をすべきか？ ブレーンストーミングを使用して、問題の1つを解決してみてください。 分析的に。 数値的方法。 関数の必死な列挙の力。 しばらくすると、夢のような学生の声が聞こえます。 ええ、ここからカーテンの後ろから出てきます。 したがって、目標は、入力データを受信して​​有効な数字を返す関数（プログラム）を見つけるプログラムを作成することです。 メタプログラミングの力、戦いへ！







うーん、どうやってそのような目標を達成するのでしょうか？ 火の周りの再帰の神に犠牲を払います。関数（プログラム）を見つけるプログラムを書くプログラムを書きます...いいえ、これは二度と機能しません。 進化のメカニズム、自然選択などの現象に目を向けて、自然から例を挙げましょう。 すべては人生と同じです。私たちのプログラムは、より順応した個人のくびきの下で生き、交尾し、出産し、死んで、子孫に最高の資質を伝えます。 クレイジーに聞こえますが、よく見る価値があります。



私たちのプログラムの世界の神は私たちの仕事です。 プログラムはそれを信じ、それと交尾し、教会のろうそくを敬い、人生の意味を見つけ、この問題を解決するという唯一の目的のために生きなければなりません。 環境に最も適応した（問題の解決に近い）がアルファオスになり、生き残り、強い子孫を与えます。 オンラインゲームに一生を費やした敗者は、問題の解決に成功したことを知りませんでしたが、子孫を与えるチャンスは非常にわずかです。 遺伝子プールからこれらの吹き出物の寄与が取り除かれ、プログラム社会全体が解決された問題の明るい未来に向かうでしょう。 まあ、一般的な用語では既に明らかですが、今はニュアンスに対処する必要があります。まず、ペアリングプログラムをどのように想像しますか？ 次に、第一世代のプログラムはどこで入手できますか？ 第三に、個人の適性をどのような基準で判断し、それが交雑育種にどのように影響するか？ 第4に、この乱交がすべて停止した場合のアルゴリズムの終了条件を決定する価値があります。

ペアリングプログラムの技術

私たちの多くは、プログラムで暴力的な性的行為を使用したいという強い欲求を持っていると思います。 ここでは、そのような種間逸脱がわが国では奨励されていないことを事前に警告することを余儀なくされています。 カトリック教会はすべてを私たちに残しています。結婚後のプログラムを備えたプログラムです...そして、その気の毒な男があなたにバーでカクテルを買ったとしても、彼らはパートナーを変えません。 いいえ、私は嘘をついていますが、ハーレムタイプの一夫多妻制は活況を呈しています。 はい、そしてまだ、以下の「父」や「息子」などの言葉を使用しているにもかかわらず、雌雄同体のプログラムがあります。 まあ、近親相姦も...うーん、私は* facepalm *教会について話していました。 さて、それについては後で。



交配プログラムの問題はそれほど単純ではありません。 関数、文字列、変数のランダムな交換は、コンパイラ/インタープリターからあなたのアドレスへの恐ろしい単語の太い流れにつながり、決して新しいプログラムではありません。 つまり、プログラムを正しくクロスする方法を見つける必要があります。 賢いおじさんたちが道を見つけました。 そして、コンパイラの構造を研究した賢い少年少女も、すでに推測していました。 はい、これは構文ツリーです。



私はすぐに熱意で死にます。私たちのひげはまだそれほど太くないので、最も単純なタイプのプログラムを使用します。 希望する人は無数の豊富なプログラミングの谷に行くことができ、ここではすべてが単純です-プログラムは式で構成され、式はいくつかのアリティ、変数、定数を持つ単純な関数で構成されています。 各式は、プログラムによって返される値の1つをカウントします。



例：二次方程式を解こうとする（あまり成功しない）2つの式の個々のプログラムの正方形：

function square(a, b, c){ x1 = min(sin(b)*(a+1), 0); x2 = 3 + exp(log(b*a)); return {x1, x2}; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

プレゼンテーションを決定しました。今、ストレージを扱う必要があります。 これらのプログラムの周りには、システムのある部分から別の部分（一般的に言えば、私の場合は一般に異なる言語で書かれている）に転送するなど、まだ多くのダンスが残っているため、個人をツリーの形で保存することはあまりありません便利です。 より便利な方法（理想的には有限のアルファベット上の行のセット）でプレゼンテーションを行うには、個々のツリーのプログラムセットがコード化/デコードの方法を学習する必要があります。

木のように見えるが、そうではないようだ

そのため、ツリーを文字列として提示する必要があります。 ここでは、カルバツリーの力が役立ちます。 最初に、ツリーに分類される関数、変数、および定数のセットを決定する必要があります。 変数と定数はツリーの葉に対応し、ターミナル、関数と呼ばれます-ツリーの残りの（内部）ノード、非ターミナルと呼ばれます。 関数が異なる数の引数を持つことができるという事実にも注意を払う価値があります。そのため、このような知識（「アリティ」、専門家の口から静かに流れる言葉）が本当に必要です。 結果は、次のようなエンコードテーブルです。

	非端末				ターミナル
いや	0	1	2	3	4	5	6
アイコン	n	+	*	もし	2	a	b
アリティ	1	2	2	4	0	0	0
価値	-{a1}	{a1} + {a2}	{a1} * {a2}	{a1}> {a2}の場合 {a3}：{a4}	2	a	b

ここで、n、+、*、ifは関数です。 2-定数; aとbは変数です。 実際の問題では、このようなセットと2次方程式を使用した重み付けテーブルは解けません。 また、ゼロによる除算や他の黙示録のシナリオを回避するために、すべての関数は実数のセット全体（まあ、または問題で使用するセット）で定義する必要があるという事実に留意する必要があります。 そして、あなたは油断せずに座って、ゼロから対数をキャッチし、それからどうするかを考えなければなりません。 私たちは誇りに思っている人ではありません。そのような選択肢を除いて、簡単な方法で行きます。



そのため、このようなテーブルを使用して、ツリーから文字列へ、またはその逆に関数を駆動することは問題ではありません。 たとえば、次のような解読用の行を受け取りました。





表に従って、各要素を識別し、アリティも思い出します。





さて、アリティの助けを借りて、関数の引数への参照を整理します。



リストの最後の3つの要素は誰も必要とせず、それらの値は関数の結果に影響を与えないという事実に注意してください。 これは、リストに含まれる要素の数、ツリーノードの数がアリティに応じて常に変動するという事実により発生しました。 そのため、誤ったツリーで苦しむよりも、留守番電話をかける方が適切です。



最初の要素でプルアップすると、式ツリーが手に掛かります：





関数の値は、ツリーの再帰的な走査によって計算できます。これは次のようになります。

お父さんの目はこんな感じ

私たちは最も暑い場所に戻ります-交差点へ。 交配プログラムでは、次の条件を設定します。まず、2つの交配個体が2つの子孫を与えます（つまり、母集団のサイズは一定です）。 第二に、交配の結果として、子孫は両方の親の特性をある程度所有する必要があります（つまり、リンゴはリンゴの木から遠く離れて転がってはいけません）。 これで、プログラムがどのように表示されるかがわかりました。これは、ラインまたはツリーのコレクションです。 したがって、文字列またはツリーとして交差できます。



木を越えることは、ランダムに選択された枝の交換です。 文字列の交差は、いくつかの方法で実装できます。単一点組換え（区分的接着）、点から点への組換え、要素ごとの交換など。分詞を含む長く複雑な文で記述できますが、図を一目で十分に理解できます。







再結合における接着の場所がランダムに選択されることは注目に値します。要素ごとの交差の場合と同様に、交換はある程度の確率で行われます。 遺伝の観点からの交配は有望に見えますが、実装がより困難です。

ねえ、この女の子は私と一緒です！

プロセスの最も親密な部分を見つけました（著者の個人的な生活がどれほど貧弱であるかをこの記事で既に多く感じています）。 今、一対の個人間の関係から、私たちは社会的基盤に移ります。



個人は世代に分けられます。 新世代は、前世代の個人の子供で構成されています。 現在の世代の息子と娘、世代の父親と母親、祖父母、great祖母などがゼロ世代まで存在していることがわかります-誇りに思っているすべての人々の祖先。 生まれた後の新しい世代の各個人は問題を解決しようとしますが、いくつかの神のフィットネス関数はその行動を評価し、若い人の活動の評価に応じて、個人は子孫を再現する機会を獲得します。つまり、属を継続するために選択された世代の最高の代表者をクラスに入れます。 私たちの世界は過酷で残酷であり、ジストピアのすべての規範（またはあなたが望むものは何でもFührerの考えによれば）、不適切な退職した両親は、子孫を産むという使命を果たした後、ガゼンバーゲンで旅行し、子供のカップルのために生活空間を解放します。 子どもたちは親の足跡をたどり、世代から世代へと続きます。



交配のクォータを発行するまさにフィットネス関数（またはフィットネス関数）は、問題を解決する個人の能力を適切に評価し、このフィットネスの数値表現を提供する必要があります（値が高いほど、より良いフィットネス）。 たとえば、その二次方程式の場合、これは、個々のプログラムによって計算された置換値x1、x2について、方程式の左側の値がゼロにどれだけ近いかの尺度である可能性があります。



フィットネス関数は、各個人に特定の数を与え、その有用性とフィットネスを示します。 この値は、選択（選択）手順に影響します。この個人がこの値を持っているほど、交差するペア（さらには複数）を見つける可能性が高くなります。 実際には、世代のすべての個体の適合度を計算した後、これらの値を正規化し（個体の適合度の合計が1に等しくなるように）、キスの場所ごとにロットが描かれ（0から1の乱数）、幸運なものを決定します。 アルファオスは自分自身をいくつかの場所に獲得できますが、敗者は何も獲得できず、 1994年のパメラとのぼろぼろのカレンダーだけで残ります。 この選択方法は「ルーレット選択」と呼ばれ、概略的には次のようになります。





繁殖には他の方法もありますが、それらはすべて一般的なルールを順守しています。つまり、個体のフィットネスが多ければ多いほど、交配に参加しなければなりません。 世代の最高の代表者が追加の人生の形で祖国への奉仕の賞を受け取るとき、プロセスにエリート主義のオプションを含めることもできます：彼は同時に子供を育てることができますが、彼は変更なしで次の世代に移ります。 これにより、非常に成功したソリューションを失うことがなくなり、交差する過程で破壊される可能性があります。



突然変異についても言及します。 この操作は、いくつかの小さな確率でランダムに個人のフラグメントを変更し、遺伝子プールの多様化を可能にします。 便利なことは、突然そのような突然変異が乳糖を分割するのに役立ちます！ もしそうでなければ、もう一つの手は不要です-そして、あなたの日の終わりまでそれで自分自身を苦しめ、子孫を与えることはまだ少しのチャンスです。

創造と黙示録

彼らは世代から世代へと受け継がれる方法を見つけました。今、問題は「何が根本原因になったのですか、それはどのように始まりましたか？ あなたの世界のこれとは対照的に、そのようなことを説明するために「ビッグバン」や「7日間」のようなトリックを思いつく必要はありません。 ここで答えは非常に明確です-それはすべてランダムに作成されたゼロ世代から始まりました。 はい、はい、行/ツリーをランダムに生成します。 唯一の要件は、個人の正確さと、それがどれだけ欠陥があるかです-誰も気にしません、選択はその仕事をします。



私たちの世界は、必要な限り存在します。 満足度の基準を設定し、十分に急な個体が現れたらプロセスを停止するか、世代の個体がどれだけ大きく異なるかを確認します。 世代全体が一卵性双生児で構成されている場合、それ以上のペアリングの興奮は遺伝子プールに新しいものを与えないことは論理的であり、1つの突然変異を期待するのは単純です。 時間制限を設定することもできます。

ねえ！ ハロシャ脳急上昇！ 結果は何ですか？

この魅力的な言葉遣いで立ち止まって振り返ります（つまり、上向き）。 要約すると、遺伝的アルゴリズムは次のようになります。



遺伝的アルゴリズムの個々の形式で問題の解決策を表現することを学ぶ-特定のアルファベット上の固定長のリスト。 その後、フィットネス関数を選択します。これにより、個人を評価し、ゼロ世代をランダムに生成できます。 ここで、自由な愛のサイクルが始まります：これらのデータペアに従って形成された世代の個人のフィットネスが計算され（敗者は捨てられ、アルファオスは1ペアに限定されません）、残りの仲間は、2人の子供を産み（突然変異も付加されます）、自分自身に手を置きます。 これは、選択したものが見つかるか、変更が私たちを喜ばせるのをやめるか、すべてに飽きるまで続きます。 さて、どうすればシェムカなしで行うことができます：

パート2 Robocodeボットの画像における遺伝的アルゴリズムの役割。

最初の部分が引きずり込まれたものは、私たち全員が疲れたので、繰り返しはしません。 一部の実装機能も省略しています。

Robocodeについては、 habrahabr.ru / blogs / programmers_games / 59784で確認できます（写真は失われています）。 つまり、これはもともとJava言語の機能を学習するために作成されたプログラミングゲームであり、参加者は独自のロボットボットを作成し、ロボットボット間の戦いを手配することができます。 各参加者はJavaでコードを記述します。Javaは小さな戦車を制御し、他の戦車と戦います。



私たちは次のタスクに直面しています：遺伝的アルゴリズムを使用した自動化されたボットタンク制御システムの開発。 ロボットは自動的に作成および変更する必要があります。 進化の過程で、1対1の戦闘で特定の事前に選択された敵に「適応」します。

問題の解決策を個人として提示する方法

まず、タンクの能力を決定します。 ロボットが戦闘中に実行できる基本アクションのリストは、銃を回す、体を回転させる、撃つ、移動するという4つのポイントに制限されています。 5番目のアクションであるレーダーの回転は、考慮から除外し、些細なことに気付きました-一定の回転（したがって、タンクには常に敵の位置に関する関連情報があります）。



明らかに、戦闘を成功させるために、これらのアクションはランダムに実行されるべきではなく、戦場の状況（状態）、つまり戦車の位置、速度、エネルギー、その他のパラメーターに依存します。 したがって、戦車の制御プロセスは、戦闘の状態に基づいて上記のアクションを実行することになります。 戦場の状況に基づいて戦車の動作（アクション）を決定する法則は、制御機能と呼ばれ、遺伝的アルゴリズムの機能になります。



制御関数は4つの値（砲弾エネルギー、砲塔回転角、船体回転角、戦車の動き）を返す必要があるため、前の部分で説明したように、4つの式で構成されます。 4つの行/木。



コーディングテーブルを作成するには、一連の基本的な関数、変数、および定数を決定する必要があります。



機能：

+（x、y）= x + y

++（x、y、z）= x + y + z

n（x）= -x

*（x、y）= x * y

**（x、y）= x * y * z

min（x、y）= x> y？ y：x

s（x）= 1 /（1 + exp（-x））

if（x、y、z、w）= x> y？ z：w



変数：

x、y-対戦車の戦車の相対座標。

drは、タンクに「到達する」ために残された距離です。

trは戦車を回すために残された角度です。

wは、戦車からフィールドの端までの距離です。

dhは、敵の戦車の方向と戦車の大砲の間の角度です。

GH-戦車の大砲の回転角。

hは敵の戦車の移動方向です。

dは、戦車と敵の戦車の間の距離です。

eは敵の戦車のエネルギーです。

Eは戦車のエネルギーです。



ウェルと定数：0.5、0、1、2、10

フィットネス機能

フィットネス関数が選択された方法を説明しましょう。 戦闘「Robocode」の結果は、多くのニュアンスに基づいて形成されます。 これは、勝利の数だけでなく、アクティビティ、サバイバル、対戦相手のヒットなど、あらゆる種類のポイントです。 その結果、「Robocode」はパラメーター「合計スコア」でロボットをランク付けします。このパラメーターでは、上記のすべての微妙な点が考慮されます。 個人のフィットネスを計算するときに使用します。合計フィットネスは、両方のタンクの合計ポイントにおけるタンクのポイントの割合に等しく、0〜100の値を取ります。したがって、フィットネス値が50を超える場合、ロボットはしたがって、ライバルは彼よりも強いです。 このようなカウントシステムによれば、最初の場所は、ほとんどのラウンドで勝った人が常に占めているわけではないことに注意してください。 さて、ここではスクーターについてのフレーズで肩をすくめます。クリエーターが基準を定義し、それに従っています。



一般的に、個人のフィットネスの計算には一連の戦いが含まれます！ つまり フィットネスの誤算として、このような一見取るに足りない点は、タンバリンとのそのようなダンスで構成されています。

1）私たちのシステムは、個人のエンコードされた染色体をchromosome.datファイルに保存します。

2）個人ごとに、Robocode環境が起動し、デュエルが開催されます。 彼女の意見には、戦闘の状態を説明する.battle形式のファイルを送信します。戦車のリスト、戦場のサイズ、ラウンド数などです。

3）戦闘の場合、Robocodeは戦車をロードし、ロボットシェルはエンコードされた動作でChromome.datファイルを読み取り、それを一連のアクションに解釈し、それらに従って戦います。

4）試合の終わりに、Robocode環境は戦闘の結果をresults.txtファイルに書き込み、作業を終了します。

5）システムはこのファイルを選択し、戦車と対戦相手の合計スコアを解析して抽出します。 単純な算術により、フィットネスの値を取得します。

彼らのようにね

設計局を要約します。 私たちのシステムは2つの部分（プログラム）で構成されています。 そのうちの最初は、遺伝的アルゴリズムに基づいて、個人を収集し、文字列のセットとして保存し、2番目（ロボットコード）はそれを解釈し（式ツリーに処理）、タンクを制御します（再帰的トラバーサル、つまり現在の状態によって特定の変数の式ツリーの値を計算します）バトル）。 最初のプログラムはSIで記述され、2番目のプログラムはJavaで記述されています。



遺伝的アルゴリズムを実装する際、人口の個体数は51（25ペア+エリート個体1人）に等しく選択されました。 進化の1ステップ（人口の変化）には約12分かかります。したがって、合計で数時間、ケースが引きずられます。



その結果、WallsとCrazyロボットの対戦相手を作成した結果を示します。





最初のケースでは、70歳のフィットネスの個人の1人に到達した後にプロセスを停止しました。2番目のケースでは、世代の個人の平均フィットネスが50を超えるのに十分でした。

熟考後、アルコールで目をすすぐ

誰かが混血を企てることからの痙攣で血の涙を泣くことを恐れていない場合（特に、髪はロボットコードから動き始めます-私たちはJavaとの相互憎悪を持っています）、このプロジェクトのソースを添付します 。 Robocode 1.7.2.2を使用して、Linux（最後のubunt）で開発およびテストされました。 ロボットの名前はハルクです（犠牲者は突然変異であるため）。 彼は（readmeを使用して）残りを教えてくれます。



最後に、科学的な無知と駄洒落をおaびします。子供の頃、ナイトスタンドから落ちました。 私は彼らが私を捕まえて船に乗せ、ヴォルガに沿って行かせることを常に恐れています。 見回す



upd：上記の方法は、最も単純で最も原始的な方法です。 構築されたロボットが実際のロボコードの戦いで真に競争力を持つためには、長いファイル操作が必要です：基本的な要素（関数、変数、定数）、確率、交差の方法、選択、突然変異の慎重な選択...各オプションを評価する適切な時間 したがって、コメントには、ボットを改善するための合理的な提案があり、誰でもそれを行うことができます。