進化的にきれいな絵を作る Sbartという プログラムの紹介。

これは「遺伝子アルゴリズム(GA)を使ってLISPプログラムを 進化させる」というもので、Koza氏はずっとこの手の話をやっ ています。昨年のICGA(International Conference on Genetic Algorithms)の講演では「お掃除ロボット」を作っ たと言っていましたしKoza_RandomNumberByGAのよう な発表をしていましたが、これも似たような話です。 普通のGAでは解を1次元の文字列に写像してそれらの間で交 配/突然変異処理行ないますが、ここではLispの構文木を`` 染色体''として用い、ふたつの構文木の部分木を交換する操 作を交配処理としています。構文木のノードには\verb+if+ 文や演算子、関数などが入ります。 この論文では3種類の問題に対するプログラムの進化につい て書かれています。 紹介されているプログラムとその適用結果は以下のとおりで す。 \begin{enumerate} \item 平面上の点をたどる問題 32$\times$32の桝目の中に89個の点があり、これを順番にた どっていくプログラムを生成します。構文木の内部ノードと しては\verb+if-sensor+ (前方に点が存在するか調べる関数) と \verb+progn+を使い、葉として\verb+advance+ (前方に 進む関数)\verb+turn-left+ (左を向く関数) \verb+turn-right+ (右を向く関数)の3個を使用します。こ れらを使ってランダムな構文木を作り、そのプログラムを実 行させ、その評価値により構文木を進化させることにより最 終的に正しく点をたどるプログラムが生成されます。 \item 「蟻」のシミュレーション 桝目の中に「巣」と「食物」があり、巣の中に20匹の蟻がい ます。今回は蟻のプログラム要素として「前進」、「回転」 などの他に「フェロモンを出す」「フェロモンをたどる」な どの関数を加えてあり、最初に餌を発見した蟻に続いて他の 蟻が協調して巣まで餌をはこびこむというプログラムを作ら せています。 \item 対戦プログラム 最近の進化論では「共生進化説」が力をのばしていますが、 ここではGAの評価関数として「相手に対する自分の評価」を 使うことにより共生進化をGAでシミュレーションし、対戦ゲー ムのプログラムを作りだすことを試みています。結果として、 ミニマックス法によるものと同等のプログラムが自動的に生 成されたということです。 \end{enumerate} 本当にいろいろなプログラムが自動的に作られるのか、とい うことは非常に疑問ではありますが、ある程度でも自動的に プログラムができてしまうということはなかなか面白いので はないかと思っています。

パソコン上にグラフィックGA評価ツールを作ったというだ け。非常につまらない。

<セル名,位置,インデクス>の列を遺伝子としてGAを配置に 適用する。無意味な解が出ないよう特殊なクロスオーバー 方式を使用する。結果は良好。

複数のSAを動かすことによりGAとSAの融合をはかっている。 評価関数はブロック重なり面積+配線長

文書のdescriptionを複数用意しておいて、問い合わせの 成功/不成功によりGAでオプティマイズする。

GAを用いたVLSI配置法についての解説が含まれている。こ こで紹介されているのはGENIE,GASP,ESP。

グラフをGAでレイアウトする。

有向グラフの配置にGAを適用している。2種類の遺伝子表 現法を比較している。最初の表現法は、2次元空間を配列 であらわしノードの存在するところだけノード番号を書く というもので、クロスオーバーは配列の行や列の入れ替え (これはクロスオーバーではなくインバージョンだと思う が)で行なう。もうひとつの表現法ではノードの座標を並 べたものを遺伝子とする。グラフの矢印が上を向かないよ うに、またアークが交差しないように配置する。結果はあ まりたいしたことがない。空間内にまんべんなく配置され るようになっていない。

コネクションマシン上でグラフレイアウトをGAで動かした。 レイアウトに関して、'perceptual organization'を審美 的要素よりも重視している。perceptual organizationと はグラフの理解を助けるのに役だつ構造で、ノードの集合 を囲う箱があるとかノードが一定間隔で並んでいるとかい うようなものである。グラフを指定するとき、ノードがあ る矩形領域に含まれるとか、きれいに横に並ぶとかといっ た属性を指定することができえる。 レイアウト用にgeneticオペレータは変更を加えてある。 mutationは、ひとつのノード位置を変えるだけでなくノー ドの集合を動かすこともある。またcrossoverは制約の設 定されたノードの集合同士を入れ替えたりする。また mutationによりノードがあまり遠くへ動かないようにして いる。このためノード位置のエンコーディングは(単なる ビットストリングではなく)構造的になっている。 評価関数はペナルティの総和になっている。ペナルティは、 (1)構文的に正しいか(ノードが重なっていないか,etc.)、 (2)指定した属性が満たされているか、(3)審美的に良いか、 の順で大きい。

ノードの位置を単純なビットストリングにマップしないこ とによって収束しやすくしている。これをしないとなかな かうまく結果が得られないと予想される。 (Groves_GAlayoutのようになってしまう)

ヒューリスティックを使って初期値をきめるとバリエーショ ンが小さくなるのでまずい。クロスオーバーやミューテー ションはアプリケーション毎に工夫するのがよい。最終的 に良い結果を得るにはGAで得られた結果にローカル最適化 手法を適用するのがよい。