📂最適化理論

遺伝的アルゴリズムにおける近交防止アルゴリズムとは何か?

用語 ¹

遺伝的アルゴリズムの交叉混合で解と解の間の距離あるいは類似度を測って、あまりにも似た解同士の交配を防ぎ多様性を高める手法を近親交配防止^{incest prevention}という。

説明

遺伝的アルゴリズムで似た解同士の反復交叉を許すということは、自然における遺伝病の発生確率を上げる程度の問題ではなく、無意味な計算に資源を浪費し続ける罪悪に等しい。

わざわざ「近親交配」という強い表現が使われているのは、実際に遺伝的アルゴリズムを使うと理解しやすいためで、個体群全体を圧倒するエリートが生まれてその独走を止められない場合、ほとんどが最初の先祖に似たまま世代を重ねる現象を容易に観察できるからだ。経験的に見ると、単に突然変異だけでそこまで似た解が独占的地位を占めるのはほとんど不可能で、通常は親族同士で近親交配を繰り返して一点に集中することによって起こる。

防止アルゴリズムの代表例は、クロモソームがビット^bitで表現される解空間 $\left\{ 0, 1 \right\}^{n}$ においてハミング距離を通じて二つの解が一定の距離以上離れている場合にのみ交叉を許す、というものだ。たとえば三つの解 $\mathbf{x}_{1}$、$\mathbf{x}_{2}$、$\mathbf{x}_{3}$ が次のように与えられているとしよう。 $$ \begin{align*} \mathbf{x}_{1} =& (0, 1, 0, 1, 1, 0, 0, 1) \\ \mathbf{x}_{2} =& (0, 1, 1, 1, 0, 0, 0, 1) \\ \mathbf{x}_{3} =& (1, 0, 1, 0, 1, 0, 1, 1) \end{align*} $$ ここで閾値^thresholdが4だとすると、$\mathbf{x}_{1}$ と $\mathbf{x}_{2}$ のハミング距離は3で交叉が禁止されるが、$\mathbf{x}_{1}$ と $\mathbf{x}_{3}$ のハミング距離は5で交叉が許される。