今日はこの実験を繰り返しますが、規模はまったく異なります。
記事の構造：
注意トラフィック！
遺伝的アルゴリズムとは何ですか？
人工知能の分野では、 遺伝的アルゴリズムは自然selectionに基づく意思決定の発見的手法を指します。 原則として、検索スペースが非常に大きく、正確なソリューションを見つけることができず、ヒューリスティックなソリューションが要件を満たすタスクに使用されます。 タスク自体には、ソリューションの品質に関する何らかの機能があり、それを最大化する必要があります。
最も単純な形式では、遺伝的アルゴリズムの構造は次のとおりです（図を参照）。まず、何らかのソリューションから始めます。この場合、これはランダムな文字列です。 たとえば、文字列内のランダムに選択された文字をランダムに選択された文字に変更し、新しい文字列のセットを取得します（文字列ごとにk個の変異）。 それらから、シェイクスピアのものに近い（一致する文字の数で）ものだけを選択します。たとえば、このような10行は、シェイクスピアのものが含まれていない場合、プロセスを再び開始します。
なぜ機能するのか
多くの点で、遺伝的アルゴリズムは古典的な最適化手法に似ています。母集団は現在の点の集合、突然変異は隣接点の研究、選択は限られた計算リソースの条件で解を見つけるための新しい点の選択です。
現在の検索ポイントを最大値として選択するため、人口は常に最も近い最大値になります（他のすべてのポイント「ダイ」は、最も近い最大値との競合に耐えられません）。 母集団のサイズは重要であるため、最大方向への少なくとも1ステップの確率は無視できないことを意味するため、一定のステップ数の後、母集団は極大に向かって移動します。 そして、最大値に近づいたポイントの子孫は、「生存」が大きくなります。 したがって、十分な数のステップの後、このポイントの子孫が母集団を支配し始め、すべてが最大にシフトします。
極大値になりがちな母集団の視覚化：
（ ランディオルソンによる ）
ランダムな文字列で問題を形式化します
入力 ：文字列S
出力 ：長さlen（ S ）のランダム文字列を文字列Sに変換するのに必要な世代数に等しい自然数N
私たちの場合の突然変異とは何ですか？ 文字列Sを変更することにより、文字列Sからランダムに選択された1つの文字をアルファベットの別の任意の文字に置き換えることを意味します。 このタスクでは、小文字のラテン文字とスペースのみを使用します。
初期集団 （スキームの初期集団）とは何ですか？ これは、入力文字列Sと長さが等しいランダムな文字列です。
子孫とは何ですか？ 定数kごとに1行の突然変異の数を修正すると仮定すると、子孫は現在の世代の各行のk個の突然変異です。
生存者とは何ですか？ 母集団のサイズを定数hで固定すると、生存者は入力ラインSにできるだけ近いhラインになります。
擬似コード（恐らくpythonに似ています）では、次のようになります。
アルゴリズムの例
次の行を考えてみましょう：速い茶色のキツネは怠laな犬を飛び越えて、そのためのプログラムの出力を再現します：
変更のチェーン（左側の世代番号）を考慮してください。
1 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk 2 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk 3 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk 4 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmodyk 5 rbb mffwfhbtxnjjiozz ujhhlxeoyhezarquzmodyk 6 rbb mffcfhbtxnjjiozz ujhhlxeoyhezarquzmodyk 7 rbb mffcf btxnjjiozz ujhhlxeoyhezarquzmodyk 8 rbb mffcf btxnjjiozz ujhhlxeoyheza quzmodyk 9 rbb mffcf brxnjjiozz ujhhlxeoyheza quzmodyk 10 rbb mffcf brxnjjiozz ujphlxeoyheza quzmodyk 20 rbb mffcf bronj fox jujpslxveyheza luzmodyk 30 rbb mficf bronj fox jumps overhehe luzy dyg 40彼はミックブロンフォックスが怠zyな犬を飛び越える 41彼はリックブロンフォックスが怠zyな犬を飛び越える 42彼はリックブロンフォックスが怠zyな犬を飛び越える 43怠qな犬を飛び越える茶色のキツネ 44彼は怠brownな犬の上を素早く茶色のキツネが飛び越える 45アヘクイックブラウンフォックスは怠aな犬を飛び越える 46速い茶色のキツネが怠zyな犬を飛び越える
完全な結論
print_genes（「茶色いキツネが怠laな犬を飛び越える」） 1 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopyk 2 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk 3 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmopyk 4 rbb mffwfhwtxnjjiozz ujhhlxeoyhezarquzmodyk 5 rbb mffwfhbtxnjjiozz ujhhlxeoyhezarquzmodyk 6 rbb mffcfhbtxnjjiozz ujhhlxeoyhezarquzmodyk 7 rbb mffcf btxnjjiozz ujhhlxeoyhezarquzmodyk 8 rbb mffcf btxnjjiozz ujhhlxeoyheza quzmodyk 9 rbb mffcf brxnjjiozz ujhhlxeoyheza quzmodyk 10 rbb mffcf brxnjjiozz ujphlxeoyheza quzmodyk 11 rbb mffcf brxnj iozz ujphlxeoyheza quzmodyk 12 rbb mffcf brxnj ioz ujphlxeoyheza quzmodyk 13 rbb mffcf bronj ioz ujphlxeoyheza quzmodyk 14 rbb mffcf bronj ioz ujphlxeeyheza quzmodyk 15 rbb mffcf bronj ioz ujphlxeeyheza luzmodyk 16 rbb mffcf bronj ioz ujphlxveyheza luzmodyk 17 rbb mffcf bronj foz ujphlxveyheza luzmodyk 18 rbb mffcf bronj foz jujphlxveyheza luzmodyk 19 rbb mffcf bronj foz jujpslxveyheza luzmodyk 20 rbb mffcf bronj fox jujpslxveyheza luzmodyk 21 rbb mffcf bronj fox jujpslxveyheza luzm dyk 22 rbb mffcf bronj fox jujpslxverheza luzm dyk 23 rbb mffcf bronj fox jumpslxverheza luzm dyk 24 rbb mffcf bronj fox jumpslxverheha luzm dyk 25 rbb mffcf bronj fox jumpslxverhehe luzm dyk 26 rbb mffcf bronj fox jumps xverhehe luzm dyk 27 rbb mffcf bronj fox jumps xverhehe luzm dyg 28 rbb mffcf bronj fox jumps xverhehe luzy dyg 29 rbb mffcf bronj fox jumps overhehe luzy dyg 30 rbb mficf bronj fox jumps overhehe luzy dyg 31 rbb mficf bronj fox jumps overhehe lazy dyg 32 rbb mficf bronn fox jumps overhehe lazy dyg 33 rbb mficf bronn fox jumps over ehe lazy dyg 34 rhb mficf bronn fox jumps over ehe lazy dyg 35 hb mficf bronn fox jumps over ehe lazy dyg 36 hb mfick bronn fox jumps over ehe lazy dyg 37 hb m ick bronn fox jumps over ehe lazy dyg 38 hb m ickブロンフォックスジャンプehe怠zyな犬 39彼はミック・ブロン・フォックスが怠heな犬を飛び越える 40彼はミックブロンフォックスが怠zyな犬を飛び越える 41彼はリックブロンフォックスが怠zyな犬を飛び越える 42彼はリックブロンフォックスが怠zyな犬を飛び越える 43怠qな犬を飛び越える茶色のキツネ 44彼は怠brownな犬の上を素早く茶色のキツネが飛び越える 45アヘクイックブラウンフォックスは怠aな犬を飛び越える 46速い茶色のキツネが怠zyな犬を飛び越える
ご覧のとおり、各世代の違いは1つだけです。 rbbzmffwfhwtxnjjiozz ujhhlxeoyhezarquvmopykから、突然変異と選択を経て怠brownな犬の上を素早く茶色のキツネがジャンプするまでに合計46世代かかりました 。
古典的な実験
個々の例、シェークスピアのラインまたはキツネに関する英語のパングラムは興味深いですが、あまり説得力がありません。 したがって、私はより興味深い質問を検討することにしました。古典的な作品をいくつか取り、それらを文に分割し、それぞれの世代数を計算するとどうなりますか？ 世代数が文字列に依存する性質はどうなりますか（たとえば、その長さ）。
ハーパー・リーの「モックバードを殺す」（モッキンバードを殺す、ハーパー・リー）と、JDサリンジャーの「ライでキャッチャー」（ライのキャッチャー、JDサリンジャー）をクラシック作品として選びました。 2つのパラメーターを測定します-文による世代数の分布と、行数に対する世代数の依存性（相関関係はありますか？）。
パラメーターは次のとおりです。行の子孫の数：100。 世代の生存者数：10。
結果
ご覧のように、大部分の文は十分に速く行に到達することができ、100回未満の反復で200回の反復が可能です（すべての文のうち、文で判断して1,135回の反復が必要なのは1つだけであり、ブレークダウンアルゴリズムはミスを犯して複数の文を1つに接着しました） ）：
文字列の長さと世代数の間の相関関係は完全です。 これは、ほぼすべての世代がターゲットラインに一歩近づいたことを意味します。
R ^ 2はそれぞれ0.996と0.997です。
したがって、任意の入力文字列Sの問題の条件下で、世代数が文字列の長さに線形に依存することが実験的に確立されました。これは初期の仮定と一致しています。
コードとデータ
すべてのコード、python-遺伝的アルゴリズム\テキスト処理およびR-視覚化、githubで利用可能：
github.com/SergeyParamonov/genetics-experiments
結論
遺伝的アルゴリズムの基本構造を把握し、文字列突然変異を適用して問題を解決しました。 古典的なテキストを使った実験の結果、我々の条件では、文字列の長さと入力文字列に到達するのに必要な世代数との間に線形関係があることがわかりました。
また、基本的な検索構造を変更して（たとえば、 クロスオーバーを使用して、複数の生成メンバーを使用して子孫を作成する）、正確な解を見つけるのが非常に困難な幅広いクラスの最適化問題を解決できることに注意しました。