遺伝的プログラミング(いでんてきプログラミング、英: Genetic Programming, GP)は、メタヒューリスティックなアルゴリズムである遺伝的アルゴリズムを拡張したもので、進化的アルゴリズムの四つの主要な方法論の内の一つでもある。 遺伝的プログラミングは1990年にジョン・コザ 遺伝的プログラミングの探索の流れは遺伝的アルゴリズムと全く同じである(遺伝的アルゴリズム#アルゴリズムの流れ参照)。ただし遺伝子型の表現方法が違うため、交叉や突然変異の方法が若干異なったものになっている。 遺伝的プログラミングでは遺伝子型の表現に木構造を使うため、取り扱う問題が自然と遺伝的アルゴリズムとは異なってくる。遺伝的プログラミングの適用分野としては関数の同定問題やニューラルネットワークや電子回路の設計、あるいはロボットの制御プログラミングの作成などがある。解の表現は、例えば関数同定問題なら解は関数であるために、配列でこれを表現することは難しい。ところが、例えば という木構造なら x × ( 2 − x ) {\displaystyle x\times (2-x)} を表しているというふうに、容易にこれを表現することができる。 解個体を表す木にどういった関数記号を用いるかは事前に決めておくのが一般的で、{+, ?, ×, ÷}など一般的な演算子の他に{sin, cos, tan, exp, logex, x2}といった単項の初等関数などを扱わせることもある。また、2つの枝の持つ値の最大値や最小値をとる関数max, minのほか、無条件で片方の枝の値のみを利用しもう一方は無視する関数を設定することもある。 交叉は主に部分木 この例では関数 3 × ( ( x × 4 ) + x ) {\displaystyle 3\times ((x\times 4)+x)} と関数 ( 3 + x ) − ( 2 / ( x × x ) ) {\displaystyle (3+x)-(2/(x\times x))} になる木を交叉させて、関数 3 × ( x × x ) {\displaystyle 3\times (x\times x)} と関数 ( 3 + x ) − ( 2 / ( ( x × 4 ) + x ) ) {\displaystyle (3+x)-(2/((x\times 4)+x))} となる木が生成されたことを表している。交叉を行う部分木の場所は、一般的にはランダムに決定する。
概要
アルゴリズムの内容
解の表現方法
交叉
参考文献
伊庭斉志、『遺伝的プログラミング入門』、東京大学出版会、2001年、ISBN 4-13-061402-9
関連項目
進化的計算
進化的アルゴリズム
遺伝的アルゴリズム
進化的プログラミング
進化戦略
外部リンク
平澤研究室( ⇒早稲田大学大学院情報生産システム研究科)
.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox{font-size:90%}.mw-parser-output .asbox-note{font-size:90%}.mw-parser-output .asbox .navbar{position:absolute;top:-0.90em;right:1em;display:none}
.mw-parser-output .hlist ul,.mw-parser-output .hlist ol{padding-left:0}.mw-parser-output .hlist li,.mw-parser-output .hlist dd,.mw-parser-output .hlist dt{margin-right:0;display:inline-block;white-space:nowrap}.mw-parser-output .hlist dt:after,.mw-parser-output .hlist dd:after,.mw-parser-output .hlist li:after{white-space:normal}.mw-parser-output .hlist li:after,.mw-parser-output .hlist dd:after{content:" ・\a0 ";font-weight:bold}.mw-parser-output .hlist dt:after{content:": "}.mw-parser-output .hlist-pipe dd:after,.mw-parser-output .hlist-pipe li:after{content:" |\a0 ";font-weight:normal}.mw-parser-output .hlist-hyphen dd:after,.mw-parser-output .hlist-hyphen li:after{content:" -\a0 ";font-weight:normal}.mw-parser-output .hlist-comma dd:after,.mw-parser-output .hlist-comma li:after{content:"、";font-weight:normal}.mw-parser-output .hlist-slash dd:after,.mw-parser-output .hlist-slash li:after{content:" /\a0 ";font-weight:normal}.mw-parser-output .hlist dd:last-child:after,.mw-parser-output .hlist dt:last-child:after,.mw-parser-output .hlist li:last-child:after{content:none}.mw-parser-output .hlist dd dd:first-child:before,.mw-parser-output .hlist dd dt:first-child:before,.mw-parser-output .hlist dd li:first-child:before,.mw-parser-output .hlist dt dd:first-child:before,.mw-parser-output .hlist dt dt:first-child:before,.mw-parser-output .hlist dt li:first-child:before,.mw-parser-output .hlist li dd:first-child:before,.mw-parser-output .hlist li dt:first-child:before,.mw-parser-output .hlist li li:first-child:before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child:after,.mw-parser-output .hlist dd dt:last-child:after,.mw-parser-output .hlist dd li:last-child:after,.mw-parser-output .hlist dt dd:last-child:after,.mw-parser-output .hlist dt dt:last-child:after,.mw-parser-output .hlist dt li:last-child:after,.mw-parser-output .hlist li dd:last-child:after,.mw-parser-output .hlist li dt:last-child:after,.mw-parser-output .hlist li li:last-child:after{content:")\a0 ";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li:before{content:" "counter(listitem)" ";white-space:nowrap}.mw-parser-output .hlist dd ol>li:first-child:before,.mw-parser-output .hlist dt ol>li:first-child:before,.mw-parser-output .hlist li ol>li:first-child:before{content:" ("counter(listitem)" "}.mw-parser-output .navbar{display:inline;font-size:75%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}.mw-parser-output .infobox .navbar{font-size:88%}.mw-parser-output .navbox .navbar{display:block;font-size:88%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}