概要

ABCL/f の応用実証プログラムの対象分野の一つとして, 本節では 並列遺伝的アルゴリズムの多目的最適化問題への適用を取り上げる.

研究の背景

遺伝的アルゴリズムは各々の個体が独立に進化するメカニズムを本質的に内在しており, 並列計算機上で効率的な並列化の可能性を秘めている. しかし, 一方では交配や自然選 択といった大域的な制御や逐次的な計算が存在するため, 同期制御による計算待ちや高 コストのプロセッサ間通信を要求し, 古典的な Holland 流の単純 GA をそのまま並列 化しただけでは高い台数効果を得ることができない. この数年, 遺伝的アルゴリズムの これらの制限を克服し, 高い並列性を実現する試みがなされている [8] . いくつかの並列遺伝的アルゴリズムのモデルが提案され, その効率 性や探索性能が比較研究されており, かなり現実問題に近い応用例も一部では報告され ている.

一方, 評価関数(適応度)が複数存在する多目的最適化問題に, 単純 GA を適用する試み も一部では古くから断続的に行なわれてきた. 多目的最適化問題はパレート解と呼ばれ る最適解集合を求めることが目標となるので, 遺伝的アルゴリズムの持つ同時多点探索 の特長が注目されたのである. 並列遺伝的アルゴリズムは, 個体間の競合を局所的に限定することによって, 並列度を 向上させると同時に, 集団の多様性を永続的に維持できる長所を持っている. 多目的最 適化遺伝的アルゴリズムはパレート解集合という多様な個体集合を得ることを目標にし ているので, 並列遺伝的アルゴリズムを適用することにより, 高速化するだけでなく, より高品質の解を得られる可能性がある.

我々は, Island 型並列遺伝的アルゴリズムの多目的最適化問題への適用した [41]. 並列遺伝的アルゴリズムと多目的最適化遺伝的アルゴリズムはそれ ぞれ独自の発展を遂げてきたが, その両者を融合した研究例は未だ存在しなかったので, これが最初の研究例となる.

研究内容(多目的並列遺伝的アルゴリズム)

多目的最適化並列遺伝的アルゴリズムのメカニズムは以下のようにまとめられる. 多 目的GAの各個体は多目的評価関数 の定義域空間上の n-次元実数ベク トル を表す. 適応度の評価には個体間の優越関係から決まるランクを用いる. ここである個体が別の個体に優越するとは, すべての目的関数の評価が良いことである. ランクにより個体には半順序関係が付けられ, パレート最適個体ならばランクは1であ る.

交配, 突然変異, 自然選択を各世代で繰り返すのは普通のGAと同様であるが, 多目的最 適化に適した特別な交配, 突然変異を用いた. 交配は2個体の定義域空間上での相対位 置から子個体の位置を決め, 定義域の外にある場合には元の個体との中点操作で定義域 に入るまで元の個体に近付ける. これによりパレート解が存在しやすい定義域の境界上 に子個体を生成することができる. 自然選択は3種類を用意した. 最も基本的な選択法 であるランクに基づくルーレット選択, 集団の多様性を向上するために個体の混雑度に 応じてランク値をバイアスするルーレット選択＋シェアリング, ランク1のパレート解 のみ残すエリート保存戦略であるパレート最適個体保存選択の3つである.

さらに, 並列GAではサブ集団と呼ばれる複数の集団群が独自にGAの各世代を実行し, 数 世代おきに個体を別のサブ集団に移住する. この移住操作により, サブ集団が局所収束 に陥ることを防ぐ.

研究成果

4種類の例題によりその有効性を検証した. 640個体がただ一つの集団に含まれる単純 GA, 各10個体を持つ64個のサブ集団が完全に独立に動作する並列GA, さらに2世代おき に1個体を移住する並列GAの3モデルについて, それぞれ3種類の自然選択法を適用し, 合計9ケースの手法を比較した. プラットフォームとして 64 プロセッサを搭載した AP1000 を用いた.

その結果, ルーレット選択＋シェアリングの単純GAから得られるパレート最適個体群が 多くの評価で優れていたが, 実行時間が並列GAの数十倍におよぶため実用的には使いに くい. 並列GAではパレート最適個体保存選択で移住を行なうケースが最も優れていた. 単純GAと比較してもわずかに劣るだけである. 計算時間も最短であり, 移住により発 生するプロセッサ間通信のオーバヘッドは無視できる程小さい. また, プロセッサ数を1, 2, 4, …, 64に増やして並列高速化の具合を見ると, ほぼ線 形に高速化されておりスケーラブルなアルゴリズムであることが証明された. 64プロセッ サでは1プロセッサの35〜50倍の速度が得られた.

ABCL/f の future/touch や並列オブジェクト機能により並列アルゴリズ ムを記述した. サブ集団は並列オブジェクトとして実装したので, 並列化のためには インスタンスを各プロセッサ上で生成すること, クラスメソッドとして実装した世代操 作および移住操作をfuture呼び出しで並列に実行することだけあったので, 並列 化が容易であった. この並列化により1プロセッサ版の40倍以上の高速化を実現できた ので, 言語処理系の並列化性能も実証することができた.