遺伝的プログラミング(GP)

遺伝的プログラミング(GP)とは

遺伝的プログラミング(GP、Genetic Programming)とは、遺伝子の継承における染色体の関係性をモデルにし、変異と結合を繰り返しながら局所的な解を得る問題解決アプローチです。

与えられた問題に対して、どのように解を求めるのか算出方法をアルゴリズムと言います。

木構造や組み合わせ最適化の問題解決アプローチでは、最も良い答えにいかにして最小の計算量で到達できるかを考えます。汎用的なアルゴリズムとして木構造のアプローチがあります。与えられた問題の変数の状態からなる各ノードとリンクによって、グラフを構成し、評価に対して最大化する解すなわちノードを探索します。

GPでは、変数をクロスオーバー(交叉)・突然変異した後に評価し、より評価がよくなればその変数値を採用し、次なるクロスオーバーを試みます。

遺伝的アルゴリズムは、常に同じ動きをされては困るときに使われるケースが多くなります。パックマンのプレイプログラム、ロボットサッカーチーム、ネットワークによる侵入検知システムなどに利用されています。いつも同じような動きをするゲームコンピュータとなんかやりたくないですよね。