EMACI:遺伝的アルゴリズムの探索解の時系列可視化手法の提案
大山 喜冴

(指導教員：伊藤貴之)
多変数データを視覚化するのに有用な統計グラフの1. はじめに一つである．PCP では変数の座標軸を平行に配置し，遺伝的アルゴリズム(GA: Genetic Algorithm)は，解全ての変数で最小値が下端に，最大値が上端になる空間構造が不明で，全探索が不可能なほど広大な解ように変数値をプロットする．そして隣接する座標空間を持つ問題に有効な最適化手法である．GA はダ軸上の変数値をそれぞれ線分で結ぶ．平行座標軸のーウィンの進化論をモチーフに，環境に適合する度間隔を調節することにより，すべての変数の座標軸合い(適合度）を数値で表し[1][2]，その適合度を最適を一画面に表示できることから，同時に全ての辺量化問題の目的関数と考える．適合度の値が進化と共を表示する事が可能である[4][5]．に大きくなることが，最適化問題における最適解に近づくことに相当する．
本論文では GA の反復処理の過程に関する可視化手法を提案する．本手法では GA の解探索過程を可視化し，ユーザが可視化結果を観察しながら，意図的に突然変異確率・交叉確率を調節する機能を備える．この機能により，ユーザはより短時間で準最適

図 2：平行座標プロットによる可視化結果解を発見できると考えている．

3. 提案手法

2. 関連研究

本手法は以下の 3 つの機能を搭載するものである．

遺伝的アルゴリズム

時系列表示部：世代ごとのエリート解のスコア値とGA は解の候補を遺伝子で表現した「個体」を複数パラメータ値を時系列で表示．

用意し，世代が進むに連れ適合度の高い個体を優先

世代全表示部：各世代の全ての遺伝子で表現した個的に選択して，交叉・突然変異などの操作を繰り返体のパラメータ値を表示．

しながら解を探索するアルゴリズムである[1]．GA

GUI：ユーザが可視化結果を観察しながら，意図的の解探索性能は遺伝的演算手法だけでなく，そのパに突然変異確率・交叉確率を調節するためのGUI．

ラメータの個体数・突然変異確率・交叉確率などに本手法は，時系列表示部と世代全表示部を同じウも大きく依存する．そのため，遺伝的演算手法やパィンドウに搭載し，反復処理過程に応じて GUI が起ラメータが解探索性能に及ぼす効果を知るために，動するようになっている．図 3 と図 4 に実行結果を適合値の改善効果を指標とするのが一般的である．

示す．図 3 の実行結果の上方が時系列表示部，下方

Two-Tone Pseudo Coloringが世代全表示部であり，図 4 が GUI である．

2 つの色を帯領域に割り当て，その各々の色の占める幅を制御することで，任意のスカラ値を表現する可視化手法が提案されている[3]．特に時系列データにおいて，数値変化を正確に，また微小な変化が読み取りやすいように可視化できるのが特徴である．
この手法による表示例を図 1 に示す．

図 3：提案手法による可視化例
図 1：Two-Tone Pseudo Coloring による表示例

平行座標プロット
平行座標プロット(PCP: parallel coordinate plot)は1

らだと考えられる．ここで，初期収束とは初期世代で偶然，他の個体より適合度が圧倒的に高い個体が生まれたとき，その個体の子孫ばかりが増えて初期段階で局所解に収束してしまう現象である．
また，初期収束が起こってしまった場合は最初から計算をやり直す方が良い結果が生まれる．そのため，各世代の解候補を表示することは初期収束の早期発見にも繋がるので，より所要時間も短縮される．

図 4：GUI

時系列表示部

表 1：実行結果

本手法では，解の候補を遺伝子で表現した「個体」

局所解回避確率

スコア平均値

再設定無し

0.48

0.9781

交叉確率を再設定

0.52

0.99110.88

0.9729の中で，最も適合度の高い個体をエリート解とみなす．また本手法では，遺伝子の適合度をスコア値とし，遺伝子を構成する値をパラメータ値とする．時突然変異確率を再設定

系列表示部では，世代が進むごとに更新されるエリート解のスコア値とパラメータ値の変化を，4. まとめ

Two-Tone Pseudo Coloring を用いて表示する．

本論文では GA の反復処理の過程で得られる解探世代全表示部
ある一世代について，非エリート解を含めた全遺索過程を可視化させ，可視化結果を観察しながら意伝子の全パラメータを，PCP を用いて表示する．ユ

図的に突然変異確率・交叉確率を調節することがでーザが選んだ世代の解候補の遺伝子を観測できるのきる可視化手法を提案した．

で，個体同士の相対的位置関係も理解する事ができ，本手法により，解候補である固体同士の相対的位解の収束や集散の様子などを把握できるようになる．

置関係も理解する事ができ，解の収束や集散の様子

本手法では座標軸の数は，パラメータの次元数となどを把握できるようになった．そのため，解の収同じであり，座標軸上の変量値は各パラメータの変束や集散に応じて突然変異確率や交叉確率を操作で数としている．

きたため，通常の GA の反復処理より早い世代で準GUI最適解を発見する事が出来た．

謝辞

ユーザが GA の反復過程を観察しながら，状況に応じて意図的に，突然変異確率・交叉確率・遺伝子指導教員の伊藤准教授．副査の河村教授．京都大

数を対話的に再設定できる．ユーザが指定した一定学の小山田教授と山下准教授に感謝の意を示します．の世代数にわたって，エリート解のパラメータ値・参考文献

スコア値に変化が見られなかった場合に，この GUI[1] D. E. Goldberg, Genetic Algorithms in Search,を起動する．

Addison-Wasley Publishing Company, 1989.
[2] D. E. Goldberg, Optimization and Machine Learning,

4. 実行結果

Addison-Wasley Publishing Company, 1989.
[3] T. Saito, H. N. Miyamura, M. Yamamoto, H. Saito, Y.

本論文では以下の問題について，本可視化手法をHoshiya, T. Kaseda, Two-Tone Pseudo Coloring:

用いて準最適解を求めた．
パラメータ数10

パラメータ範囲

0.0～1.0

スコアの極大値

6Compact Visualization for One-Dimensional Data, IEEE
Information Visualization ’05, pp. 173-180, 2005.
[4] H. Y. Lee, H. L. Ong, Visualization Support for Data
Mining, IEEEEXPERT, 1996.

上記の問題を 25 回ずつ，一回につき 150 世代まで

[5] A. Inselberg, B. Dimsdale, Parallel Coordinate: A

繰り返し実験した結果の平均値を，表 1 に示す．以Toolfor

下では，実行結果とその考察を述べる．

Visualizing

Multi-DimensionalIEEEVisualization, 1990.

結果として，GA の反復処理過程中に状況に応じて突然変異確率・交叉確率を意図的に調節する方が良い結果が得られた．理由としては，再設定をしない
場合，GA の問題点でもある初期収束に陥りやすいか2

Geometry,