インターネットをさまようと、彼は遺伝子プログラミングのようなものに興味を持ちました。 簡単に言えば、自然選択の原則に従って、特定の目標を達成するプログラムの自動作成です。 つまり、最初は「生成物」の世代-さまざまな基準（目標達成の近さ）に従ってソートされたプログラムがランダムに作成され、それらの一部は（偶然にも）変異し、一部は消滅し、一部は新しいランダムな生き物に置き換えられます。



したがって、最も価値のある生き物は仕事を続け、子孫を産み、最も弱いものは選択プロセスで排除されます。 いくつかの実験とその結果については、現在準備中です。

最初のサンプル。 迷路を歩く

ペンのテストとして、上の図のように迷路でパスを探すように（この場合は「プログラム」という言葉が大きすぎるため、クリーチャーと呼ぶことにします）クリーチャーに教えることにしました。 この場合、目標は、遺伝子工学を使用して、任意の迷路で経路を見つけるクリーチャーを作成することではなく、特定の迷路で経路を見つけることであり、その結果、クリーチャーには感覚器官がありませんでした。 少し考えて、クリーチャーによって簡単に変更して実行できるコマンドの単純なセットを使用することにしました。 したがって、私たちの「プログラム」または「ゲノム」は、クリーチャーが移動する方向を指定するコマンドのセットにすぎません。 さらに、プログラムのセクションを数回繰り返すことができるループが追加されました。 ゲノムは、たとえば次のようになります。







ここで、FOR（IxT）コマンドは、次のI命令がT回実行されることを意味します。 このようなゲノムを持つ生物は、右に2セル、次に2セル下に移動し、再び右に2セル移動します。



さて、本質的にはゲノムの解釈者である私たちの世話をしましょう。 クリーチャーにはそれぞれ、「名前」、または後で認識するための識別子、クリーチャーが行動するための「ゲノム」、クリーチャーが次の遺伝子を実行するためのステップメソッドがあります（歩くかどうかを確認します）クリーチャーが壁を通過する距離を決定するフィットネス関数、およびゲノムの一部を変更するMutateメソッド。 突然変異については少し後で説明しますが、ここでは、かわいい小さな正方形がテストプログラムをどのように実行するかを見てみましょう。







フィットネス、またはクリーチャーが要件を満たしているかどうかは、フィニッシュとクリーチャーの座標の違いの合計と見なされます。 そのため、ターゲットまでの距離が最小のクリーチャーが最適です。

進化

私たちが持っているクリーチャーは世代ごとに進化し、それぞれ100クリーチャーです。 各世代内で、同じ手順を繰り返します。

• クリーチャーのコンプライアンスの確認（フィットネスの計算）;
• ターゲットまでの距離を増やしてクリーチャーを並べ替えます。
• リスト内の位置に応じて：
  
  -または、クリーチャーは既に十分であり、それを台無しにする必要がないという仮定で、クリーチャーを変更しません。
  
  -ゲノムを変更する：遺伝子の一部を削除、追加、変更します。
  
  -または、新しいランダムな生き物と交換し、古いものは生殖に値しないと「死ぬ」。

ポーキングの方法により、この比率を選択します。上位10個は変化せず、次の60個は変異し、残りの30個は消滅します。 292世代で結果を取得します：







勝者のゲノムは次のとおりです。



Y_INC; X_INC; Y_INC; FOR_2x3; X_INC; Y_INC; FOR_1x4; X_DEC; FOR_2x3; Y_INC; X_INC; Y_DEC; Y_INC; FOR_2x4; Y_INC; X_INC; Y_INC; FOR_2x4; X_DEC; X_INC; X_INC;







ご覧のとおり、クリーチャーはしばしば1か所で踏みつけますが、これは一般的には完全に良くありません。 ゲノムの長さを考慮してみましょう。 しかし、フィニッシュラインまでの距離の後に重要度の高い2番目に配置します。そのため、開始時の2〜3個の遺伝子の短いプログラムは、目標に近づきながら長いプログラムよりも優れていることがわかりません。ゲノム。 このメソッドでは、再び、突っ込んで、式を試してみます：







これで、ソリューションの検索が少し長くなります。 335世代目では、まったく同じ結果が得られますが、次のゲノムがあります。



FOR_2x4; X_INC; Y_INC; FOR_2x3; Y_INC; X_INC; Y_DEC; Y_INC; FOR_2x4; Y_INC; X_INC;







実際、改善すべき点はまだたくさんありますが、許容できる品質と合理的な人件費で問題は解決されています。 私は、その不完全さに関連してコードを意図的に提供しません。 したがって、明確な良心をもって、タイトルのトピックに進むことができます。

ELTRUTの問題

2012年、カリフォルニア大学ベンジャミンブッシュ校の卒業生は、遺伝的アルゴリズム、特にいわゆるELTRUT問題に従事していました。 タスクの本質はこれです：ビットマップ画像があり、 Logo turtlesのコマンドのシーケンスを見つけて、同様の画像を描画します。 以下は、すべてが非常に簡単に説明されているビデオです。







要するに、ベンジャミンはこのソリューションを提供します。単純な線形ゲノムを捨てて、二次元を優先します。 なんで？ 2次元ゲノムには冗長性があるため、すべての変異がゲノムに根本的な変化を引き起こすわけではありません。 ベンジャミンはまた、ゲノムの興味深い表現形式を提供します：画像の各ピクセルは、カメがこの点にぶつかった場合、線を引く必要がある場合、カメがどの方向に、どの距離で進むべきかを示す遺伝子に関連付けられています。 視覚的に、ゲノムは次のように表示できます。







ここでは、過剰なゲノムが茶色で強調表示されています。 突然変異のほぼ80％で、カメの行動の変化は起こらないことがわかります。 さらに、この問題を解決する際には、「性的生殖」または交配を使用することが提案されています。前世代の2つの生き物が遺伝子を交換して子孫を取得します。 次に、3次元ゲノムとアルゴリズムの最適化について説明しますが、最適化を行いたくありませんでした。3次元は遺伝的アルゴリズムにあまりにも精通しているため、単純化されたアルゴリズムの実装に集中することにしました。



したがって、前のタスクと同様に、各世代には100のクリーチャーがいます。 各世代で：

• 50の最高のクリーチャーを渡り、50の最悪のクリーチャーをその子孫に置き換えます。
• トップ10を除く各クリーチャーに対して1つの遺伝子を変更します。
• クリーチャーがすでにタスクを完了している場合、そのクリーチャーは変化しません。

どのようにクリーチャーが適合するかを判断しますか？ 正しく描画されたピクセルごとに、特定の数のポイントがクリーチャーに加算され、正しく描画されていないピクセルごとに罰金が科されます。 ピクセルが塗りつぶされておらず、塗りつぶしてはならない場合は、カウントを変更しないでください。 合計近似スコアリングアルゴリズム：







別の問題をすぐに解決します（3次元ゲノムによって解決する必要があります）：バグが既にあったピクセルにスナップすると、プログラムはループします。 したがって、訪問したピクセルを踏むと、タートルが停止することを確認します。 同時に、青になるまで貧しい爬虫類を追いかけません。



それで、試してみます。 5x5の画像はそれほど複雑ではありませんが、結果を得ることができますか？









悪くありませんが、プログラムは8x8などの少し大きい画像をどのように処理しますか？







ビデオは大幅に加速されます（前のビデオも加速されますが、わずかに加速されます）。 2000世代は正しい結果を出していない。 続行しようとすることもできますが、スケジュールからわかるように、約1000世代は変わらなかったため、これで問題が解決することはほとんどありません。 まあ、最適化に対する嫌悪感はトリックをしました：私のコンピューターの8x8画像で約2時間かかりました。 したがって、実験は部分的に失敗したと認識されます。



あなたの時間をありがとう、私はこの記事が誰かに興味深いように願っています。