遺伝的プログラミング（GP）の概要

1  はじめに

遺伝的プログラミング（Genetic Programming:GP)は，1992年にStanford大学のJohn Kozaらにより提案された進化論的計算手法である．GPは，遺伝的アルゴリズム（Genetic Algorithms:GA)の遺伝子型を構造的な表現（木構造，グラフ構造）が扱えるように拡張したものである．GPはプログラム生成や学習，推論，概念形成などに応用することを目指している．具体的には，プログラムを進化させて目的とするロボットの制御や構造物の設計を試みている．

2  GP

2.1  アルゴリズム

GPのアルゴリズムをFig:1 に示す．

Figure 1: GPのアルゴリズム

1．初期集団の木構造の生成(Initialization)

　　　ランダムに集団数の数だけ個体（木構造）を生成させる．

２．適合度計算(Evalution)

　　　各個体の適合度を計算する．

３．選択(Selection)

　　　適合度の大きな個体に対して一定数のペアを取り出す．

４．交叉(Crossover)

　　　親1と親2の交叉点をランダムに選び，それぞれ交叉点に応じた部分木同士で交叉させる（Fig:2 ）．

Figure 2：GPの交叉

５．突然変異(Mutation)

　　　ランダムに突然変異点を選び，その点に応じた部分木と突然変異木を入れ替える（Fig:3 ）．

Figure 3：GPの突然変異

６．逆位(Inversion)

　　　兄弟木の入れ替え（Fig:4 ）．

Figure 4：GPの逆位

７．終了判定(Terminal Criterion)

　　　以下のような終了条件がある．

• 実行すべき最大世代にまで達したとき

• 目的とする個体が得られたとき

2.2  GPの基本要素

GPでは次の5つの基本要素を設計することで，様々な応用問題への適用が可能となる．

１．非終端記号 --- 関数ノード

２．終端記号 ----- 実値

３．適合度 ------- 評価値

４．パラメータ ---- 集団数，交叉率，突然変異率など

５．終了条件

3  GPの応用例題

  Santa Fe Trail（人工蟻の探索）問題

プログラムを進化させて目的とするプログラムを生成する簡単な問題として，Santa Fe Trailがある．Santa Fe Trailとは，Fig:5 に示すような32×32のマス目上に89個の餌（Fig:5のピンク色）があり，人工蟻1匹が限られたエネルギーの範囲内で全ての餌をできるだけ効率良く集める問題である．

Figure 5：Santa Fe Trail

人工蟻の定義は以下の通りである．

• 人工蟻は向きを変えつつ前方に一歩ずつ進む．
• 後方，斜めには進めない．
• 壁を越えて進むことはできない．
• 人工蟻はセンサーを持ち，自分の前方に餌があるか否かがわかる．
• 人工蟻は有限のエネルギー（400エネルギー）を持つ．
• 人工蟻が動作（終端記号）を行うたびにエネルギーを1単位消費する．

上記より，人工蟻の行動プログラムをGPで生成するために以下の非終端記号と終端記号を定める．

＜非終端記号＞

• If_Food_Ahead(x,y) --- 前方に餌がある時はxを，ない時はyを実行する．
• Prog2(x,y) ---------- xを実行してyを実行する．
• Prog3(x,y,z) --------- xを実行してyを実行してzを実行する．

＜終端記号＞

• RIGHT --- 右に90度向きを変える．
• LEFT ---- 左に90度向きを変える．
• MOVE --- 前方に一歩進む．

適合度は以下のように評価する．

１．Energy=400,food=0とする．

２．プログラムにしたがって人工蟻を動かす．終端記号を評価したらEnergy=Energy-1とする．

３．もし人工蟻の位置に餌があれば，food=food+1とし餌を消す．

４．Energy=0なら，foodを適合度として返す．

５．2に戻る．

4  GPの問題点

4.1  ブロート

ブロートとは，GPの探索過程でプログラムの長さが増大することである．これによりGPの効率的な探索が阻害される．進化の停滞や実行速度の低下が考えられる．

4.2  スキーマの破壊

プログラムのスキーマ（有益な部分構造）が破壊されること．これにより，プログラムが目的とする解に到達しないことがある．

5  まとめ

本報告では，GPの概要，GPを用いた問題，GPの問題点について説明してきた．GPはGAの遺伝子型を構造型に拡張した進化論的計算法である．GPは自動プログラミングを目的に提案されたものである．実問題として，株価予想システムや作曲支援システムなどでGPが用いられている．しかし，GPは解探索過程でプログラムが膨大となり，効率的な探索がなされなくなる．そこで現在のGPの研究では，GPの膨大な計算時間をいかに抑えるかが焦点になっている．GPの理論の目標はブロートの制御にあるといっても過言ではない．

References

[1]

伊庭斉志. 遺伝的プログラミング入門. 東京大学出版会, 2001.

[2]

伊庭斉志. 遺伝的プログラミング. 東京電機大学出版局, 2001.

Copyright

Copyright (C) 2004 Mitsunori Miki, All rights reserved.
Copyright (C) 2004 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2004 Yoshihisa Fujita, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.

In no event shall the authors be liable for any damages caused in any way
out of the use of this document.