⏯️ 🧑🏽‍🤝‍🧑🏻 ⛳️ 遺伝的アルゴリズムでWorld of Warcraftのシャーマンパズルを解く 💅🏽 🏸 #⃣

こんにちは、ガーディアン！
少し前に、World of Warcraft Legionがさらに追加されました。まず第一に、私はシャーマンを送り始めました。シャーマンの要塞で、私はパズルマスターLoに行って、あなたがパズルだと思ったものを見ました。

私の前には火と水のトーテム5×5の正方形があり、トーテムをクリックすると、反対に変化します。例えば、水から火へ、火から水へ、そして隣接するトーテムを上下、左右から変更します。すべてのトーテムが水になることを確認する必要があります。最初のクリックの後、私はこのクールなパズルの解決策を急ぐ必要があることに気付きました。
それから来たもの、カットの下で読んでください。

タスクは次のとおりです。

次元N×Mの行列が与えられた場合、行列の各セルには0または1が含まれます。マトリックスセルの値が反対に変化すると、隣接セルの上下左右から自動的に反対の値に変化します。マトリックスがゼロのみで構成されるようにセルの変化のシーケンスを見つけます。

この問題の解決策は非常に標準的で退屈なので、問題を解決するための遺伝的アルゴリズムを書くことにしました。

UPD：誤解があるため、問題を解決することではなく、解決策を見つけるための遺伝的アルゴリズムを作成することがポイントであることを強調します

理論のビット

アルゴリズムを作成するには、遺伝子、遺伝子型、フィットネス関数、突然変異、世代、世代の生存の概念を導入する必要があります。

遺伝子

ゲノムは、マトリックス細胞の価値と呼ばれます。 1または0いずれかです

遺伝子型

遺伝子型とは、長さL = N x M文字列として表される行列を意味します。これには、行列の行が順番に結合され、行の各文字は遺伝子です

例
マトリックス用
 [ [0,0,0,0,0], [1,1,1,1,1], [0,0,0,0,0], [1,1,1,1,1], [0,0,0,0,0] ] 
遺伝子型は0000011111000001111100000の行になります（ L = 25

フィットネス機能

フィットネス関数（フィットネス関数）は、 0から1までの数値を返す関数です。値が1近いほど、個人のフィットネスが向上します。問題は残っています。個人の適応度とは何ですか。簡単にするために、遺伝子型のゼロ遺伝子の数を遺伝子型の長さで割って行うことができます

 function fitness(genotype) { return genotype.replace(/1/g,'').length / genotype.length; }

突然変異

個人の遺伝子型の1つの遺伝子の変化。なぜならゲームのルールによると、マトリックスの5セル（ターゲットと近傍）が変化すると、1つの突然変異で5新しい個人が生成されます。

 const DIRECTIONS = [ {x: 0, y: 0}, {x: 1, y: 0}, {x:-1, y: 0}, {x: 0, y: 1}, {x: 0, y:-1} ]; function mutate(genotype) { return DIRECTIONS.map( direction => { const nextX = x + direction.x; const nextY = y + direction.y; return genotype.flip(nextX, nextY); } ); }

サバイバル

その結果としての適性に応じた個人の選択は、適者の限られた数のままです。この例では、すべての個体をフィットネス関数の降順でソートし、最初のL x 8を残します（値は実験的に取得されました）

 const maxGenerationSize = 400; // 5 * 5 * 8 function surviving(populations) { return populations.sort( (a, b) => { return b.fitness - a.fitness; }).slice(0, maxGenerationSize); }

世代

生存後に残っている多くの個人。さらに、彼の適応度が1に等しい場合、世代の最初の個人が解決策になります。

最適化に関するもう少しの理論

突然変異の後、以前に知られているゲノムまたはより少ない突然変異で得られた遺伝子を、同じまたはより良い適合度で得ることが非常にしばしば可能であることに気付くかもしれません。これを防ぐには、ゲノムのハッシュテーブルを作成します。そのキーはゲノム自体であり、値は突然変異セルの配列です。このゲノムがすでに発見されており、突然変異細胞の数がすでに遭遇した数を超えていない場合、それからうずきを作成します。

また、フィールド全体で3セルまたは5セルのいずれかを変更することも簡単にわかります。フィットネス関数は、値L - 3およびL - 5後にのみ1返します。それらの場合、フィットネス関数0.999値を返して、フィットネスを高めることができます

例
5x5マリーナの場合、フィットネス関数1値は、ゲノムに25すべてのゼロが存在し、 20ゼロまたは22個だけが先行します

ソリューション検索サイクル全体は、次のコードとして表すことができます

 while ( generation++ < maxGenerationsCount && populations[0].fitness !== 1 ) { populations = mutating( populations ); populations = surviving( populations ); }

Webpack、React-Redux、およびMaterial-UIを使用して、数時間で判明したこのような単純なWebアプリケーションを次に示します。

UIの負荷を軽減するために、 breeder.jsファイルのWeb Worker側で計算が行われます。

遺伝的アルゴリズムでWorld of Warcraftのシャーマンパズルを解く