F 4 Non-dominated
5.2 並列 GA モデル
上に多い場合には余分な計算が必要となる．それに対して，多目的におけるGAでは，パ レート最適解集合が探索領域内の広範囲に広がっている場合が多いため，探索の初期段階 においても，最終段階においても，探索領域全体に対する大局的探索が必要となる．また，
それと同時に，各個体はパレート最適解へ近付く必要性があるので，局所探索も必要とな る．これらのことから，個体数は多いほど ，より広い範囲での精度の良いパレ ート最適解 が求められることになる．すなわち，単一目的の場合と多目的の場合とでは，GAに求め られるメカニズムが異なる．
通常の分割母集団モデルを多目的問題に適用した場合，各サブ 母集団内の個体数は，単 一母集団のものと比較してサブ 母集団数分の1と減少するため，各サブ 母集団で求められ る非劣解は劣化する．また，各サブ母集団ないでは非劣解であっても，全体の解集合と比較 した場合には，非劣解ではなくなる場合が考えられるため，探索効率も良いとはいえない．
さらに，探索個体全体を把握することが 難しいため，全体としての多様性維持も困難とな る．そのため，単一母集団モデルであるマスタースレーブモデルと分割母集団モデルとを 比較すると，同一の精度の解を求めるには，前者のモデルの方が有利となる．一方，並列 計算機上での実装を考えた場合，後者の分割母集団モデルの方が通信負荷が低いため，プ ロセッサ数が多い並列計算機やPCクラスタのようなネットワーク性能の低い並列計算機 には適している31）．
これらの点から，並列計算機を用いてGAを行うには，分割母集団モデルで，かつ，単 一母集団モデルと同等の解探索能力を持つ，新しいモデルが 望まれる．そこで本研究では，
そのような多目的最適化GAに適した分割母集団モデルとして異なる特徴を備えた以下の 3つのモデルの提案を行う．
• 全体シェアリングGA(Total Sharing Genetic Algorithm: TSGA)
• 領域分割型GA(Divided Range Multi-Objective Genetic Algorithm: DRMOGA)
• 分散協力型スキーム(Distributed Cooperation Scheme: DC-Scheme)
以下，GAにおける代表的な並列モデルの紹介を行った後，それぞれの手法のアルゴ リ ズムと数値実験を用いた従来手法との比較について述べる．
Population
PE 1
PE 2
PE 3 PE 4 PE 5
Processor Individual PE #
Evaluation
Shared Memory
図5.1 Schematic of master slave model
・近傍モデル
それ以外の並列モデルについても，そのほとんどが上記の3つの並列モデルを変形した モデルとなっている．以下，上記の3つのモデルについて説明する．
5.2.1 マスタースレーブモデル
マスタースレーブモデル(master slave model)では母集団の分割は行わず，選択と交叉 を大域的に行い，個体の評価のみ複数のプ ロセッサを使用する．そのため，最終的に得ら れる結果は単一母集団モデルと差がなく，用いるスレーブ マシンの台数による解への影響 も全くない．しかし ，マスタースレーブ 間の通信負荷が大きく，評価計算の負荷が軽い場 合にはマスターのみに計算負荷が集中してし まうという欠点がある．
そのため，対象問題とし ては評価計算負荷が高い問題に向いており，用いるアーキテク チャ環境としては複数のプ ロセッサが単一のメモリを共有可能な，共有メモリ型の並列計 算機に向いているといえる．図 5.1に概念図を示す．
5.2.2 分割母集団モデル
分割母集団モデル(distributed population model)では 母集団は，使用するプロセッサ 分のサブ 母集団(subpopulation)に分割される．広義では ，母集団をプロセッサ分のサブ
Sub population Individual Migration
図 5.2 Schematic of distributed population model
母集団に分割するモデルの総称を分割母集団モデルと呼ぶが ，分散GA27, 28）と呼ばれる 分割母集団モデルの1つを意味する場合にも用いられる．サブ 母集団は並列計算機上の各 プロセッサに分配され，各サブ 母集団においてGAが行われる．早熟収束の回避と多様性 の維持を行うために，一定間隔ごとにサブ 母集団間で個体の交換を行う． この操作は移住 (Migration)と呼ばれる．移住を行う世代周期を移住間隔(Migration interval)と呼び ，サ ブ 母集団内全体に対する移住個体の割合を移住率(Migration rate)という．移住の概念図 を図 5.2に示す．
分割母集団モデルでは，移住の頻度，移住先の選択法，移住個体の選択法といった移住 に関わるパラメータ，メカニズムが探索に大きく影響する．また，移住の頻度については 各サブ 母集団が一斉に移住を行う同期移住や，各サブ 母集団が個別の判断により移住を行 う非同期移住などがある．この他にも様々な移住のメカニズムが提案されている32）．
このモデルは ，一定間隔ご とに 行われる移住操作以外に通信の負荷がかからないため，
マスタースレーブモデルと比べ通信負荷が低い．そのため，PCクラスタのようなネット ワーク性能の低い並列計算機に適している．
5.2.3 近傍モデル
近傍モデル(neighborhood model)では，プロセッサ1つに割当てられる個体は1つまた は比較的少数であり，プロセッサ間通信のオーバーヘッド を減らすために，近傍のプロセッ サの個体とのみ交叉を行う．このモデルは，個体の配置状態が2次元格子状空間の区分単 位であるセル上に配置されているように見えることから，セルラーGAとも呼ばれる．こ
Processor Individual Neighborhood Exchange
図5.3 Schematic of neighborhood model
のモデルは，低い性能のプ ロセッサを極めて多数用いる並列計算機に多く見られる．
図 5.3にその概念図を示す．このモデルは，プロセッサ間通信のオーバーヘッドが少なく 極めて効率的ではある．しかし ，部分集団の適当な近接構造の設定が困難であること，ま た，その近接構造の決定の際に並列計算機のアーキテクチャに依存することが 問題となる．