研究3:遺伝的アルゴリズムを活用した風景画の複製
・背景と目的
・アプローチ手法
・原理
・可視化方法
・可視化結果
・考察
【原理】
ここでは難解な数式や概念については触れず、最も基本的な部分である【遺伝的アルゴリズムとはなにか？】ということについて触れます。
より深く遺伝的アルゴリズムについて学びたい方は こちら からどうぞ。
【進化的アルゴリズムと遺伝的アルゴリズム】
遺伝的アルゴリズムは進化的アルゴリズムの一種なので、遺伝的アルゴリズムを理解するために、まず進化的アルゴリズムについて触れます。進化的アルゴリズムとは、問題を解くために進化の原理を応用したメタヒューリスティック(さまざまな問題に適用可能なヒューリスティック)な最適化アルゴリズムです。計算科学上の進化の概念は自然界における進化の概念に似ています。
すべての進化的アルゴリズムの背景にある考え方は、個体群と自然淘汰です。ランダムに選択した個体の集合から始めて、最も強い個体を選択します。個体の強さは、事前に定義された適応度関数によって決まります。このようにして、適者生存の方法を用いるのです。
選択された個体を用いて、組み換えや突然変異を行い次の世代を作ります。ここで作成した個体集合を作ると、次の世代では古い世代と生存競争することになります。弱い個体を捨てて子孫に置き換えることによって、個体群全体の適合レベルを向上していきます。書房の全体適合レベルに到達するまでこの処理を繰り返します。
遺伝的アルゴリズムは、個体をビット列で表現し、問題を解くビット列を見つける進化的アルゴリズムです。選択、交差、突然変異 といった確率的操作を使って、ビット列を操作しながら次の世代を作ります。これを繰り返すことにより、より強い世代の個体群を生み出し、問題を解くのです。
適応度関数は、ビット列がどれくらい問題の解にふさわしいのかを表す適応度を評価します。適応度関数は評価関数とも呼ばれます。遺伝的アルゴリズムは、自然界からインスパイアされた操作を行います。それが、生物学の用語に密接に関連した用語が用いられている理由です。
【遺伝的アルゴリズムの基本概念】
遺伝的アルゴリズムを実装するためには、いくつかの重要な概念や用語を理解する必要があります。様々な問題を解決するために遺伝的アルゴリズムを用いる分野全体で、これらの概念が用いられます。
遺伝的アルゴリズムの最も重要な性質はランダム性です。繰り返しにおいては、個体をランダムに選択する必要があります。つまり、非決定的な処理である、ということです。したがって、同じアルゴリズムを複数回実行すると異なる結果になることがあります。
次に個体群について説明します。個体群は、解の候補となる個体の集合のことです。遺伝的アルゴリズムでは、どの段階においても単一の最適解を維持するわけではありません。あくまで潜在的な解の集合を維持するのであって、そのうちの一つが最適となるわけです。ただし、最適解以外の解も、解の探索において重要な働きをします。バリエーションのある解の個体群を扱うため、局所最適に陥りにくくなります。局所最適に陥ることは、他の最適化手法で直面する古典的問題です。
遺伝的アルゴリズムの個体群と確率的な性質がわかったので、次に遺伝子操作について説明します。次の世代の個体を作るには、現在の世代の最強の個体群から生み出す必要があります。ひとつの方法として、現在の世代の複数の個体にランダムな変更を加える方法があります。この変更のことを突然変異と呼びます。ただし、この変更によって既存の個体が良くなるのか悪くなるのかはわかりません。
次の考え方は、組換えです。交叉と呼ぶこともあります。これは生物の進化過程における交配の役割に直接的に対応するものです。つまり、現在の世代の個体を組み合わせて新しい個体を作ります。親の個体のいくつかの特徴を組み合わせて子孫を作るわけです。これによって、個体群の中で現在の世代の弱い個体を、次の世代の強い子孫で置き換えていきます。
交叉と突然変異を実施するためには、選択の基準が必要です。選択の概念は自然淘汰の理論からインスパイアされたものです。遺伝的アルゴリズムでは、次の世代を生み出す処理と選択の処理を繰り返していきます。選択の処理において、強い個体が選ばれ、弱い個体を消していきます。適者生存の考えに従うわけです。選択の処理は、個体の強さを計算する適応度関数を用いて行います。