魂の遺伝的アルゴリズムで実験する。
私は自分の経験、観察、考えを少しのエッセイで共有したかった。
それで、私が最初に考えた質問：どの人口の規模を選ぶべきか。
この質問を体系的に定式化すると、次のように聞こえます。
人口のサイズを計算するために、どのような基準に基づいて、どのような基準に基づいていますか？
この質問に答えるには、遺伝的アルゴリズムが何であるかを決定する価値があります。
私の意見では、これはとても賢い検索アルゴリズムです。
（遺伝的アルゴリズムのクラスを使用して、要素の可能な組み合わせが膨大な量のシステムで最適なソリューションを見つける効率は、地球上の生命の数十億年の進化によって経験的に確認されているため、スマートです
遺伝的アルゴリズムの単純化されたメカニズムは次のとおりです。
-初期集団の開始-可能な値のサブセット（染色体の集団）をランダムに選択します。
次に、遺伝的アルゴリズム自体：
-人口から各染色体について、適合度関数の値を計算します（最適解が検索されるパラメーターを特徴付けるように設定されます）。
-交差に参加する染色体を選択します（染色体の適合関数の値が大きいほど、交差に参加する可能性が高くなります）
-私たちは、交配の遺伝的オペレーターの助けを借りて、次世代を形成します。 初期染色体のペアワイズ組換えを実行します（突然変異演算子の効果-今のところ、取っておきます）
そのため、最大値の染色体が見つかるまで、周期的に（最適化された特性により人口を順次改善していきます）続けます。
簡単にするために、各遺伝子の対立遺伝子が値{0、1}であるL遺伝子で構成される染色体を例にとります。
理論的には、染色体集団のサイズは[1、2 ^ L]の範囲になります。
ここで、母集団サイズ2 ^ Lは、遺伝的アルゴリズムが網羅的な検索アルゴリズムに縮退する制限的なケースです（適応関数はすべての可能な値に対して計算されるため、遺伝演算子を使用せずに解が見つかる状況）。
母集団サイズ1は、縮退したケースです（任意の値をランダムに選択し、任意の方法としてその最適値を宣言します）。
この退化したケースは、（最適ではない場合でも）答えが完全にない場合よりもはるかに優れている場合に適用できます。
ちなみに、このアプローチの適用範囲はジョークによって特徴付けられます：
Chapaev Petke：デバイス？
ペトカ：20
チャパエフ：20とは何ですか？
Petka：アプライアンスはどうですか？
染色体集団のサイズをNとする
サブセット上で組換えを行いますが、同時に目標はセット全体の最適な値を見つけることですので、染色体のセットには必要なすべての値が含まれている必要があります。
つまり 母集団のサイズは、各遺伝子（この場合は遺伝子座）について、対立遺伝子のすべての可能な値が母集団全体で提示されるようにする必要があります。
例で説明しましょう：L = 5、N = 4、そしてある時点で人口は次のようになります：
10110
10011
11100
10001
だから：
-4つの染色体すべての最初の遺伝子座は、対立遺伝子1のみで表されます。
-2番目の軌跡は3つの値0と1つの値1で表されます。
-3番目の軌跡は、2つの値0と2つの値1で表されます。
-4番目の軌跡は、2つの値0と2つの値1で表されます。
-5番目の軌跡は、2つの値0と2つの値1で表されます。
したがって、染色体01010に対して最適な値が達成された場合、遺伝的アルゴリズムがどの程度機能しても（突然変異演算子を使用せずに）、この値は決して見つかりません。
ランダムな染色体セットに必要なすべての要素が含まれる確率を計算してみましょう。
すべての染色体のいずれかの遺伝子座の1つが1のみを含む確率は（1/2）^ Nに等しい
すべての染色体のいずれかの遺伝子座の1つが0のみを含む確率は、（1/2）^ Nに等しい
明らかに、他のすべてのケースでは、完全なセット{0,1}が存在します
したがって、1つの軌跡の確率は次のとおりです。1-（1/2）^ N-（1/2）^ N = 1-（1/2）^（N-1）
したがって、すべてのL遺伝子座にそれぞれ完全な対立遺伝子セットが含まれる確率：
P1 =（1-（1/2）^（N-1））^ L
ここで、N（母集団内の染色体の数）を、P（母集団が組換えに必要なすべての要素を含む確率）およびL（染色体内の遺伝子座の数）で表現します。
N = 1 + LOG2（1 /（1-P1 ^（1 / L）））
たとえば、L = 100およびP1 = 0.999（つまり99.9％）の場合、必要な母集団サイズN = 18（可能な異なる染色体の総数〜10 ^ 30）を取得します
P1の値をどれだけ大きくしても、組換えによって染色体を取得できない反復で染色体のセットが取得される確率はゼロではないことに注意してください。
これは、突然変異演算子の必要性が発効する場所です。
実際には、交差した染色体の適応機能に目を向けて交差を実行する（つまり、最も適合したセットを再結合する）ことにより、人口の適応度の成長を達成するため、それ自体は非常に有害ですが、突然変異演算子は完全に無秩序です。
（自然界では、突然変異の出現につながる可能性のある染色体の損傷はかなり頻繁に起こる現象ですが、これらの損傷の大部分を修復するための効果的なメカニズムは細胞内で発生します。そのため、突然変異は非常にまれな現象であり、これは偶然ではありません）
しかし、「ホメオパシー用量」では、突然変異演算子は有用であり、正確には、組換えに十分なセットの100％を維持することが不可能であるためです。
遺伝子座のいずれかがすべての染色体に対して1のみまたは0のみを含む確率は、（1/2）^（N-1）
P2突然変異の必要な（失われた多様性を回復するための）確率をある程度表現しようとします
したがって、P2は1つの染色体の突然変異の確率です。
その場合、染色体の特定の遺伝子座の突然変異の確率はP2 / Lに等しくなります。
特定の染色体座位が変異しない確率は1-P2 / L
この遺伝子座がどの染色体でも変異しない確率は（1-P2 / L）^ N
したがって、特定の遺伝子座が少なくとも1つの染色体で変異する確率は1-（1-P2 / L）^ N
信頼性のために、少なくとも1つの染色体の特定の遺伝子座の突然変異の確率は、すべての染色体のこの遺伝子座に値（0または1）が存在しない確率よりも1桁高いことが必要です。
さらに、突然変異の事実は、必要な突然変異を扱っていることを意味するものではありません。
したがって、不等式があります。
1-（1-P2 / L）^ N> 10 *（1/2）^（N-1）
変換すると、次の値が得られます。
P2> L *（1-（1-10 *（1/2）^（N-1））^（1 / N））
不等式の下限に基づいて、染色体の突然変異の確率を計算するための次の式を取得します。
P2 = L *（1-（1-10 *（1/2）^（N-1））^（1 / N））
N = 18（値L = 100およびP1 = 99.9％に基づいて計算された）の場合、P2〜0.05％を取得します
つまり 長いL = 100遺伝子座を持つ染色体の場合、必要な最小母集団サイズN = 18と、1つの染色体P2 = 0.04％の突然変異の必要確率を取得します。
L = 1000の場合、N = 22およびP2 = 0.03％になります
更新：
人口サイズと突然変異頻度の上記の計算は、遺伝的アルゴリズムの安定した性能に必要な条件のみを指定していることに注意する価値があります（つまり、これらの条件が満たされない場合、アルゴリズムは不安定になるか、アルゴリズムは原則として機能しません-それは局所的な最適にさえ到達しません）。
条件の十分性を評価するには、収束係数/局所/グローバル最適化への収束速度を考慮する必要があります（これは次のエッセイのトピックです-1〜2週間で考えます）。
遺伝的アルゴリズムの母集団サイズの選択
All Articles