スキーマ・ビルディングブロック・リンケージ（遺伝的アルゴリズム）
はじめに
この記事では，遺伝的アルゴリズムの中で重要な概念であるスキーマ・ビルディングブロック・リンケージについてまとめます．これらは，より性能の良い遺伝的アルゴリズムを考える上で非常に大切です．
目次
スキーマ
スキーマは，遺伝子を表現する文字列と文字 からなる個体と同じ長さの文字列で，以下で説明するように複数の個体を表します．
例えば遺伝子がビット列で表現される場合，スキーマは の3つの文字からなる文字列です．
は
の両方の文字を表します．このとき，次のスキーマ
は，以下の個体すべてを表します．
ここで，スキーマの定義長と次数を定義します．
上で示したスキーマ の定義長は3，次数は2となります．
ビルディングブロック
スキーマのうち，次数が小さい・定義長が短い・平均適応度が高いものをビルディングブロックと呼びます．平均適応度は，スキーマが表す個体の適応度の平均です．
遺伝的アルゴリズムでは，ビルディングブロックをうまく処理することでより良い解を求めることができます．
ビルディングブロックの例を１つ示します．
個体を20 bit のビット列 で表し，その適応度を4 bit のトラップ関数を5つ並べた評価関数
\begin{equation} f(s) = \sum_{i = 1}^{4} {\rm{trap}}_5(u_i) \end{equation}
\begin{equation} \mathrm{trap}_5(u) = \begin{cases} 3 - u & ( u = 0, 1, 2, 3) \\ 4 & ( u = 4) \end{cases} \end{equation}
で計算するものとします． は文字列
を4等分した文字列中の1の数です．
このとき，5つのトラップ関数のそれぞれの最適解のみを固定したスキーマ
\begin{align} H_1 &= 1111 ~ **** ~ **** ~ **** ~ **** \\ H_2 &= **** ~ 1111 ~ **** ~ **** ~ **** \\ H_3 &= **** ~ **** ~ 1111 ~ **** ~ **** \\ H_4 &= **** ~ **** ~ **** ~ 1111 ~ **** \\ H_5 &= **** ~ **** ~ **** ~ ****\ ~ 1111 \end{align}
はビルディングブロックと考えられます．これらのビルディングブロックを組み合わせることで，最適解
\begin{equation} s^{*} = 1111~1111~1111~1111~1111 \end{equation}
を得ることができます．
遺伝的アルゴリズムでは，最適解につながるビルディングブロックに適合する個体を増やしていき，それらを交叉によって組み合わせることで良い解を求めることができます．逆に，交叉によってビルディングブロックが破壊されてしまうと解の探索がうまく進みません．
ビルディングブロックが破壊されてしまう簡単な例として，上記のビルディングブロック を含む個体の一点交叉を考えます．
\begin{align} \require{color} 1001 ~ \textcolor{blue}{11} | \textcolor{blue}{11} ~ 0011 ~ 1010 ~ 0101 \\ 1101 ~ 00 | 00 ~ 1100 ~ 1001 ~ 1011 \end{align}
個体中に示した | で交叉させると，
\begin{align} 1011 ~ \textcolor{red}{1100} ~ 1100 ~ 1001 ~ 1011 \\ 1101 ~ 0011 ~ 0011 ~ 1010 ~ 0101 \end{align}
となり，ビルディングブロック が破壊されてしまいます（ちなみに，上記の2個体の場合，ビルディングブロックを作り出すことができる交叉点も存在します）．
リンケージ
リンケージとは，複数の遺伝子座が集まってビルディングブロックを構成する傾向のことです．リンケージが分かれば，どの遺伝子座がビルディングブロックを構成しているかがわかります．ビルディングブロックを構成している遺伝子座がわかれば，ビルディングブロックを壊さないような交叉手法を適用することができます．
例として，ビルディングブロックの例で扱った評価関数の部分関数（トラップ関数）それぞれに寄与する遺伝子座の集合をリンケージと考えることができます．遺伝子座の番号を左から1, ２, ......, 20とすると，{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}, {17, 18, 19, 20} がリンケージとなります．
十分な数の初期個体群をランダムに生成することにより集団内にビルディングブロックを確保し，ビルディングブロックを壊さないように交叉を行うことで効率の良い解の探索ができます．初期集団にビルディングブロックが含まれていない場合でも，突然変異を適用することでビルディングブロックの供給が望めます．
リンケージの長さが ビットなら，
程度の初期集団を確保すれば十分と考えられます．
参考
棟朝雅晴『遺伝的アルゴリズムーその理論と先端的手法ー』[POD版] , 森北出版
