背景

複数の最適解を GA を用いて発見しようという試みは 1967 年の Rosenberg の研究に 遡るが, 本格的な GA の適用は 1985 年の Schaffer [33] が考案した多 目的最適化問題向けベクトル評価遺伝アルゴリズム VEGA (Vector Evaluated Genetic Algorithm) からである. VEGA は各評価関数ごとにサブ集団を作り, 適応度の計算と 選択はそのサブ集団の中だけで行ない, 交配をサブ集団間で行なうものである. それぞ れのサブ集団は各々の評価関数の最適化を試みるが, 交配によって他の評価関数も良く するような個体が流入するので, 全体としてすべての評価関数を押し上げる圧力がかか りパレート最適解が得られるというメカニズムである. Schaffer は VEGA を DeJong の 関数や多次元の制御工学問題に適用し, いくつかの発見的手法を加えてパレ ート最適解を求めた.

しかし, Richardson, Palmer, Liepins, Hilliard [30] はそれぞれ のサブ集団の個体が一緒になって新しい集団を生み出すということは, 結局, 複数の評 価関数を線形結合した一つの評価関数で普通の GA を実行するのと等価であることを示 した. ただし, 重み係数は現在の集団の適応度の分布に依存する.

GA でパレート最適解を求めるもう一つ試みはパレート最適性に関する順位 ( ranking) を適応度とする方法である. パレート最適解は常に順位 1 を持ち, パレ ート最適解以外は自分の左下に存在する解候補のランクの総和を与える. 順位の重複や欠落が発生することを除けば, 通常のランク選択のGAを行 なうことによってパレート最適解を求めることができる. Fonseca, Fleming [9] はこの方法に, 適応度の Sharing を用いた棲み分けと分化のテクニ ックによって, パレート最適解集合を求める手法を提案し, ガスタービンのステップ応 答の最適化問題に適用した.

並列遺伝的アルゴリズムは, 個体間の競合を局所的に限定することによって, 並列度を 向上させると同時に, 集団の多様性を永続的に維持できる長所を持っている. 多目的最 適化遺伝的アルゴリズムはパレート解集合という多様な個体集合を得ることを目標にし ているので, 並列遺伝的アルゴリズムを適用することにより, 高速化するだけでなく, より高品質の解を得られる可能性がある.