スキーマ定理と積み木仮説
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/02 02:19 UTC 版)
「遺伝的アルゴリズム」の記事における「スキーマ定理と積み木仮説」の解説
スキーマ定理とは、ある世代 t でスキーマ H を含む個体の数を m(H, t) と表したとき、次の世代のスキーマ H を含む個体の数 m(H, t+1) は SGA において以下のように表すことができるという定理である。 m ( H , t + 1 ) ≥ m ( H , t ) ⋅ f ( H ) f ¯ ⋅ [ 1 − p c ⋅ δ ( H ) l − 1 − O ( H ) ⋅ p m ] {\displaystyle m(H,t+1)\geq m(H,t)\cdot {\frac {f(H)}{\overline {f}}}\cdot \left[1-p_{c}\cdot {\frac {\delta (H)}{l-1}}-O(H)\cdot p_{m}\right]} ここで、f(H) はスキーマ H を含む個体の適合度の平均、 f ¯ {\displaystyle {\overline {f}}} は全個体の適合度の平均、l は遺伝子型の長さ、pc, pm は交叉率と突然変異率である。 このとき、pc >> pm, δ(H) > O(H) であるので、括弧内の O(H)⋅pm はほとんど無視できる。そのため、この定理は 定義長 δ(H) が小さく f(H) が全体の平均より常に大きい となるようなスキーマ H の数は指数関数的に増大していくことを表している。 ここから、上記の条件を満たすスキーマを保持することが最適解を導くことになるような問題に対しては、GA は最適解を導き出すことが可能であるという考え方ができる。このようなスキーマを積み木（Building Block）といい、この考え方を積み木仮説という。
※この「スキーマ定理と積み木仮説」の解説は、「遺伝的アルゴリズム」の解説の一部です。
「スキーマ定理と積み木仮説」を含む「遺伝的アルゴリズム」の記事については、「遺伝的アルゴリズム」の概要を参照ください。
- スキーマ定理と積み木仮説のページへのリンク
