Geometric Semantic Genetic Programming(GSGP)とはなんなのか

はじめに

本記事ではGenetic Programmingの手法の一つであるGeometic Semantic Genetic Programming(以下GSGP)についての解説をします．
Genetic Programmingを知らない人はGenetic Programmingを知ってからこの記事戻ってきてください．
また，本記事では個人の意図的・偏見的な解釈が含まれていることを了承してください．

GSGPについて

GSGP¹とは2012年に発表されたGPの手法の一つです．
GSGPは，それまでのGPの手法とは違い，「探索対象を構造から数値列へと変更」したことによって注目を浴びました．

それまでのGPでは構造(可変長オブジェクト)を探索するためには以下の二つの手法がとられていました．

• 構造そのものを探索する
  

• 構造を数値列にエンコードしてから探索する
  

しかし，一つ目の構造そのものの探索では，探索空間が可変的になるために効率的な探索が困難でした．
また，二つ目の構造を数値にエンコードする手法も，数値にエンコードすることによって探索空間を歪めてしまうという問題点もありました(つまり真の探索が非効率的になる)．

では，GSGPが何をしたのかというと，構造を探索することをやめたのです．
そもそも，GPの目的は目的の出力を得られる関数(構造)を探索することでした．そこでGSGPは，「構造は何でもいいから，目的の出力だけ得られれるように探索すればよくなーい」というようにGPの手法を大幅に変更したのです．
この目的の出力は，スカラもしくはベクトルなため，探索空間が固定的になり，探索効率が大幅に向上しました．

では，どうやって目的の出力を得る構造を求めるのでしょうか？
それには手法名にも含まれているSemanticとGeometricの意味を理解しなくてはいけません．

Semanticとはなんなのか

Semanticとは日本語訳すると「意味の…」となります．まったく意味がわかりません（笑）
個人的な解釈になりますが，ここでいうSemanticとは構造の意味を指しているのだと思います(個人的解釈)．
構造を意味づけるものとは，すなわち構造からの出力値です．
つまりSemantic Genetic Programmingとは「構造の出力を探索するGP」と意訳することができます．

Geometricとはなんなのか

Geometricとは日本語訳すると「幾何学的な」となります．なにが幾何学的なのでしょう？
ここでいうGeometicとは，距離関係が対称関係にあることを指しています．
つまり，2つの親(A,B)から生まれる子(C)があったときに，親同士の距離d(A,B)と，子と親の距離d(A,C),d(B,C)は次の関係にあるということです．

$$ d(A,B) = d(A,C) + d(B,C)$$

ある意味，内挿交叉に限定するということです．
では，どうやってGeometricでSemanticな遺伝子操作を定義するのでしょう?
以下ではその定義について話します．

Geometric Semantic Crossover

もはやGSGPのCrossoverはCrossoverとは言わずに，「二つの個体の間の個体を生成する方法」と定義したほうがよさそうです．
子個体の生成方法は問題によって異なるのですが，例えばBoolean Expressionの場合は

となります．ここで，$\rm Tree_C$は子個体，$\rm Tree_A$,$\rm Tree_B$は親個体，$\rm Tree_{rand}$はランダムな木構造とします．
見てわかると思いますが，通常のGPとは大きく異なり，親個体間での部分木交換がありません．
GSGPでは，子個体の生成は，親個体+αとすることで生成するのです．

さらに，この交叉方法は常に親個体に+αされていくので，木の大きさは爆発的に大きくなっていきます．
とはいえ，木構造を保存する必要性はなく，個体の出力値だけを保存すれば子個体の生成が行えるので，メモリフローにはなりません．
この個体の出力値だけを保存するというのが，Semanticということです．

Geometric Semantic Mutation

Mutationに関しては，通常のGAと同じような突然変異を行えば大丈夫です．
いま，個体は出力列(数値列)として表現されているため，適当な値を変化させればいいのです．

Review

GSGPは木構造を探索するアルゴリズムではなく，出力値を探索するアルゴリズムです．そのため，解空間が線形になり，探索効率が大幅に上がるというメリットを持ちます．
しかし，過学習しやすいというデメリットも持ちます．当然ですが，継ぎ木のような交叉方法では，任意の出力値を吐き出す関数は複雑になってしまう場合が多いです．そのため，ノイズを含む実問題に対しては過学習するという傾向があります．

一方で，過学習してもよいという問題が存在します．それは論理回路の回帰問題などです．このような問題では入力と出力のすべてのパターンを網羅することが多いため，過学習しても問題ありません．さらに論理回路の回帰問題は，機械学習の手法を使っても解くことはできますが，論理演算子に落とし込むことが面倒です．そのような場面ではGSGPは輝くのかもしれません．

おわりに

この記事を書いているのは2019年6月ですが，最近ではGSGPの熱も過ぎ去ったように思えます．2012年～2016年はGSGPの論文がいっぱい投稿されていますが，2019年現在は少なくなってきています．結局のところ，ノイズがある問題にはGSGPが適用しずらいことが関係しているのかなーとも思っています．

1. Moraglio, Alberto, Krzysztof Krawiec, and Colin G. Johnson. "Geometric semantic genetic programming." International Conference on Parallel Problem Solving from Nature. Springer, Berlin, Heidelberg, 2012. ↩