まえがき
こんにちは、Habr！ 遺伝的アルゴリズムに関する簡単な応用レッスンを提供したいと思います。 あなたがそれらに精通していて、働いているならば、それを読むことは時間の無駄です。 このレッスンは、使い始めたいが、方法がわからない人向けです。 あなたはすでに遺伝的アルゴリズムの意味に精通しており、それらがどのように機能するかについて少し知っていると仮定します。
遺伝的アルゴリズムの本質
一部はこの部分をスキップできます。 多くのことは言われています、私はちょうど順序のためにそれを繰り返します。 多変量最適化アルゴリズムと同様に、遺伝的アルゴリズムは目的関数を最小化し、最小値に対応する入力引数のセットを生成するように設計されています。 正確な遺伝的アルゴリズムの優れた機能は、関数のグローバルな最小値を取得する理論的な可能性です。 これがどのように達成されるかについては、少し後で説明します。 本質的に、遺伝的アルゴリズムは進化プロセスの近似シミュレーションにすぎません。 彼らは「遺伝子」と「人口」の概念で動作します。 「遺伝子」は入力引数のセットであり、「母集団」は遺伝子のセットです。 従来の遺伝的アルゴリズムでは、関数の引数から遺伝子を取得するために、バイナリコードで行に単純に記述されます。 このような巨大なバイナリヘビを取得します。 進化の自然なプロセスのように、自然selectionがあります。 機能の価値が最も排除されている遺伝子、変更なしで次世代に最高のパス（エリート）。 他のものは他の遺伝子と交差します（クロスオーバー）。 交差の方法は異なる場合があります。 最も単純なケースでは、任意のペアの各遺伝子が2つの部分に分割され、2番目の遺伝子の終わりが最初の遺伝子の始まりに結び付けられ、最初の遺伝子の終わりが2番目の遺伝子の始まりに結び付けられます。 もちろん、セクションの割合は、このペアのそれぞれで等しくなければなりません。 1つまたは複数のビットをランダムに変更する変異遺伝子のグループは、通常は多数ではありませんが別のグループです。 たとえ私たちがローカルにいるとしても、グローバルミニマムを提供するのはそれらとクロスオーバーです。
問題の声明
VKソーシャルネットワークには、「光を当てる」と呼ばれるかなり興味深いゲームがあります。ユーザーがその中で解決するタスクは遺伝的アルゴリズムに最適であるため、記事を書きたいという欲求を喚起したのは彼女でした。 つまり、ゲームの本質は次のとおりです。発電所と家をケーブルで接続する必要があります。 競技場の各セルには、4種類のケーブルの1つがあります。L型、T型、I型、家を接続するためのI型の半分（Hで表示）です。 プレーヤーは90度単位で自由に回転できます。 一般的に、最初は理解しようとする方が良いです。
試しましたか？ 続けましょう。 競技場の状態の目的関数を構築する必要があります。 入力データは、各ケーブルフラグメントの回転角度です。 2ビットでエンコードできることは簡単に理解できます。 ゲーム開始時の合計フィールドは5x5マスです。 したがって、バイナリコードの遺伝子の長さは5x5x2 = 50ビットです。 目的関数は、入力としてゼロと1の配列を取ります（Matlabではそのような可能性があります）。
競技場の状態の質を評価する方法は？ 隣接するセル間の接続数を使用することをお勧めします。 競技場のスコアは、セルの評価の合計です。 近隣との各セル接続はスコアです。 セル4の隣人：上、下、左、右。
実装機能
一部の人々がHabréでやりたいように、ソースを貼り付けて行ごとに分解したくありません。 gitリポジトリーはまさにそれを行います： github.com/player999/turnonthelight 。 READMEのコメントが役立つはずです。 ここで、ソースを開き、記事と一緒にコピーすることをお勧めします。 私は意図的にそれらを十分に単純化しました。 実装の重要なポイントに触れてください。 プログラムの入力時、テキストファイルの競技場の初期状態は、おおよそ次の形式です。
H1 H0 I1 I1 I3 I1 H2 T1 T1 I3 L3 L2 H1 L0 H1 H0 L1 T3 I0 T3 L0 I0 L0 L0 L0
ここで、文字はセルのタイプであり、数字は時計回りに90度刻みで0〜270度の方向です。 このフィールドは、メインの実行スクリプトから呼び出されるscheme_config関数を使用して読み取られます。 さらに、solve_scheme関数を呼び出すことにより、遺伝的アルゴリズムを適用できます。 実行スクリプトでは、ターゲット関数はfunとして指定されています。これはeval_bits関数のラッパーです。 eval_bitsは、競技場を記述する2つのバイナリ文字列を受け入れます。 最初は細胞型、2番目は細胞の向きです。 当然、遺伝的アルゴリズムの動作中、最初のパラメーターは一定でなければなりません。 プレーヤーはセルタイプを変更できません。 これらの行は、scheme2string関数を使用して、競技場のセルの配列で構成されています。 eval_bitsはeval_schemeのラッパーです。 これは目的関数のコアであり、eval_bitsは引数を競技場を記述する行列に単純に変換します。
目的関数がどのように機能するかを理解してほしい。 今、非常に最小化に。 最初に、遺伝的アルゴリズムのオプションを含む構造を取得する必要があります。 すべての味に多くがあります。 しかし、最も重要なものだけを示しました。
options = gaoptimset('PopulationType','bitstring','PopulationSize',1000,'Generations',100);
PopulationType-引数の提示。 私たちの場合、ビット文字列。 ここには「文字列」という単語が表示されていますが、実際にはゼロと1の二重配列です。
PopulationSize-各反復に含まれる遺伝子の数 。 遺伝子が多いほど、アルゴリズムの動作は良くなりますが、同時に遅くなります。 各降圧遺伝子について、目的関数を計算する必要があります。
世代 -遺伝的アルゴリズムの反復回数。 これは、可能な終了条件の1つです。 もう1つは、たとえば、目的関数の変更が停止したときの出口です。
以下は、最適化関数の呼び出しです。
opt = ga(fun,length(pos),[],[],[],[],[],[],[],options);
制限のある配列は、このタスクに関連していないため、ここにはありません。 長さ（pos）は引数の数を反映します。 Matlabの助けを借りてこれらの関数の詳細を読むことができます。それは素晴らしいです。 また、最適化ツールボックスの設定（optimtoolコマンド）、すべて同じ設定を、使いやすいようにグラフィカルインターフェイスに合わせて再生することもお勧めします。
次に、string2schemeを使用して最適な遺伝子が競技場に戻され、ゲームフィールドがdraw_scheme関数で描画されます。
結論
アルゴリズムにはカスタマイズも必要ですが、パズルの解決策を検索できることを自信を持って証明しました。 この記事があなたを少し助けてくれるか、少なくともあなたを楽しませることを願っています。 たとえば、作業の結果は次のとおりです。
