遺伝的アルゴリズム
例えば最適解が
~101~
という問題があるとする。このとき
~111~
~000~
という二つの個体が交叉して最適解を得る確率を求める。 交叉の方式が二点交叉の場合は交差点が
~1|1|1~ ⇒ ~101~
~0|0|0~ ⇒ ~010~
で最適解が得られる。このとき遺伝子型の長さを l とおくと、最適解が得られる確率 p は
p = 2 l ( l − 1 ) {\displaystyle p={\frac {2}{l(l-1)}}}
と求められる。これは l が長くなるにつれ加速度的に確率が低くなる。つまりl が長いとほとんどの確率で上記の二つの個体は最適解と一致しないビットを新しく生成した個体に受け継がせてしまうことになる。このように最適解と一致するビットの近くにいて最適解の生成を妨げる現象をヒッチハイキングといい、そのビットをヒッチハイカーという。
このヒッチハイキングは一様交叉によって防ぐことができる。一様交叉は各要素が独立で交叉するので、上記の場合は
~111~⇒~101~
~000~⇒~010~
か
~111~⇒~010~
~000~⇒~101~
で最適解を得る。このとき、最適解を生成する確率は
p = 2 2 3 = 1 4 {\displaystyle p={\frac {2}{2^{3}}}={\frac {1}{4}}}
であり、この確率は l の長さが長くなっても変化しない。