遺伝的プログラミング（以下 GP）は、遺伝的アルゴリズム(以下GA)を改良したアルゴリズムである。 GP・GAは共に、生物の進化の過程をモデルとしたものであり、計算機内に仮想生物を大量に生成し、選択・淘汰を繰り返し、世代を重ねるごとに、より解に近づくというものである。選択・淘汰とは、環境に適合した固体は多産であり、適合しない固体は子孫を残せないという意味である。GPの応用としては、関数同定、自動プログラム生成、パターン認識、人工知能などがある。

GPの遺伝子コード

GPでは、遺伝子を木構造で表わす。例えば、は、Fig. 2のように表現される。図の○はノード（端子）と呼び、子ノードを持つ＊や+を非終端子、子ノードを持たない3やx、4を終端子と呼ぶ。

遺伝子の変異には、交叉・逆位・突然変異などがある。各オペレーションの意味はFig. 3のようである。変異が起こる個体や遺伝子の位置は、一般にランダムである。

関数同定問題とは、入出力データから元の関数を求める問題である。例えば、「Table 1のデータから、元の関数を求める」という問題である。この場合の解は、である。なお、この入出力データを教師データと呼ぶ。

Table 1　教師データ

終端子・非終端子の設計

GPの設計で重要なものとして、終端子・非終端子の設計がある。Table 1の場合、

非終端子：＋、−、＊、÷

終端子：、（はランダムな実数）

とするのが妥当であろう。もっと複雑な問題の場合は、非終端子として三角関数・指数関数・対数関数などを追加するとよい。また、１変数入力１出力でなく、多変数入力１出力問題のときは、終端子としてを追加するとよい。

適合度の設計

GPの設計でもう一つの重要なものとして、適合度の設計がある。関数同定問題の場合は、平均誤差や平均二乗誤差が使われる。ただし、この場合は適合度が低いほど優秀な遺伝子とみなす。

例えば、ある遺伝子が、だったとしよう。この式を評価すると

Table 2　

x(入力)	教師データのy		誤差
1.0	7.0	1.0	6.0
2.0	10.0	3.0	7.0
3.0	13.0	5.0	8.0
4.0	16.0	7.0	9.0
		合計	30.0
		平均誤差	7.5

となり、平均誤差は、7.5となり、これが適合度である。この個体が優秀であるかどうかは他の個体の適合度と比較しなければわからない。他の個体に比べて優秀であれば、この個体は多くの子孫を残し、逆に優秀でなければ淘汰される。

あとは、前述したアルゴリズムで世代を重ねれば次第に適合度の低い遺伝子が生き残り、最終的に適合度が０になれば計算は終了する。

その他の設定

その他に、集団の個体数、交叉の確率、突然変異の確率、初期個体の生成方法、選択方法、最大の木の大きさなどがあるが、一般にこれらのパラメータをどう設定すればよいかという理論的な方法は、みつかっていない。

次の応用問題は、「仮想ロボットに、荷物を目的地まで運ばせる」問題である。しかし、従来のようにあらかじめロボットに動作の手順（プログラム）を与えるのではなく自発的にそのプログラムを生成させようという問題である。この学習ロボットは、環境が変わってもセンサーに外乱が入っても対応できるというメリットがある。

環境条件

まず計算機に、仮想ロボット・部屋・障害物・荷物・目的地を用意する。これらの環境条件に依存しないプログラムを生成させるため、部屋の大きさ、障害物の位置、荷物の位置、目的地の位置はランダムとする。また、仮想ロボットには、荷物を持ち上げるアーム、前方にある壁・障害物・荷物・目的地を認識する視覚センサー、壁・障害物・荷物にぶつかったかどうかを判定するバンプセンサーを持つ。センサーの外乱に対応するプログラムを生成させるため、一定の確率でセンサーは対象物の認識を誤るとする。

ロボットのプログラムの実行は、目的地に荷物を運ぶか、一定ステップ以上かかっても目的地に運べなかった場合に終了する。

終端子・非終端子の設計

終端子・非終端子は以下のように設計する。