遺伝的アルゴリズムによる描画性能最適化

どうも吉村です。

現在、MacOSX10.8.4にてcinder0.8.5でOpenGLを用いて特定のウィンドウの領域に描画を行う際、
そのウィンドウの配置や隠蔽具合によって、描画性能に差が生まれてしまうという現象が確認されています。
しかもその性能と配置の関係性が非常に不透明です。
そこで今回は遺伝的アルゴリズムを用いて、自動で最適な場所を探す方法を提案します。

まずは遺伝子から定義していきます。
今回はウィンドウのサイズは固定とし、ウィンドウの位置にのみフォーカスします。
なのでウィンドウの座標のみを遺伝子とします。
実際のコードでは以下のようになります。

遺伝的アルゴリズムでは次に、
①選択
②交叉
③突然変異
を定義しなければなりません。
一つ一つ見ていきましょう。

<選択>
選択、とは遺伝子を評価することに他なりません。
今回の評価基準は以下の二つが考えられます。
1、フレームレートが高い
2、画面の描画領域が広い
この二つを評価基準として用います。

1つ目は簡単です。
cinder環境なので、getAverageFps()関数を用いて計測します。
2つ目は少々厄介です。
なぜならウィンドウは何枚も上に重なる可能性があるためです。
これは以下の2つのステップに分解できます。
⑴ 対象のウィンドウよりも手前のウィンドウ領域を列挙する
⑵ 対象のウィンドウ領域から、手前のウィンドウをそれぞれ減算する

一つ目は、Cocoa APIであるCGWindowListCopyWindowInfo関数を用いて列挙します。
kCGWindowLayer, kCGWindowBounds, kCGWindowNumber, などによりウィンドウを識別します。
二つ目は、単に面積を減算するだけでは正しく領域を減算できないため、ポリゴン演算を用います。
演算には優れたC++フレームワークであるBoost.Geometryを今回は採用しました。

Boost.Geometryの例としては以下のようになります。

これにより、これら二つの尺度により遺伝子がどの程度優れているのか評価することが可能になりました。
選択なので、遺伝子の選択方法もここで合わせて定義します。
乱数の生成は現状非常に優れた疑似乱数生成器である、メルセンヌ・ツイスタを用います。
こちらもboostに良いインターフェースがあるため、こちらを使用します。
実際の選択コードは例えば以下のようになります。

<交叉>
こちらは遺伝子が少ないため非常にシンプルになります。
以下の様に二つのデータのウェイトを乱数により確定します。

<突然変異>
こちらは単純に遺伝子(ウィンドウ位置)を乱数で初期化します。

以上により、今回適用する遺伝的アルゴリズムのすべてが定義されました。

実際に動作させているデモは以下をご覧ください。
少しずつ計測し、最適な位置を探索します。

GA from wowdev on Vimeo.