(cache) 並列モデルについて 並列モデルについて
氏名　片浦 哲平

1  GAの並列化手法

GAの問題点として高い計算負荷がかかるということが挙げられる．その解決法として 並列化が行われているが，並列化の方法によって以下の3種類の方法に分類される．

1.1  大域的並列化モデル(Global parallelization model)

母集団の分割を行わずに，選択と交叉は大域的に行い，個体の評価のみを複数のプロセッサで 分散処理させるという方法である．したがって，複数のプロセッサが単一のメモリを共有可能な， 共有メモリー型の並列計算機で適用するのが効果的である．この方法では，選択の際にプロ セッサ間で同期をとる必要があるため，個体の評価に時間のかかる問題に向いているといえる．

Figure 1: Global parallelization model

1.2  細粒度並列化モデル(Fine grained parallel model)

大規模並列化GA(massively parallel model)，近傍モデル(neighborhood model)とも呼ばれる 手法で，プロセッサ1つに割り当てられる個体は1つまたは比較的少数であり，近傍のプロセッサ の個体とのみ選択，交叉を行う方法である.
　この方法は低い性能のプロセッサを極めて多数用いる場合には効果的であるが，部分集団の適当な 近傍構造の設定が困難であることや，その近傍構造の決定の際に並列計算機のアーキテクチャが 大きく影響を及ぼすため，アーキテクチャを考慮に入れた設計が必要となる．また，総個体数と 同等数のプロセッサが必要となるのでPCクラスタのような並列計算機システムには不向きである．

Figure 2: Fine grained parallel model(近傍モデルの例)

1.3  粗粒度並列化モデル(Coarse grained parallel model)

粗粒度並列化モデルは母集団を複数のサブ母集団(Subpopulation)に分割する方法である．そのため， 分散GA(Distribute GA)や島モデル(Island model)と呼ばれる．分割母集団は並列計算機上の各 プロセッサに分配され，そこでそれぞれに処理される．そして，早熟収束の回避と多様性の維持を 行うために，一定期間ごとにプロセッサ間で個体の交換を行う．これを移住(Migration)と呼ぶ．
　粗粒度並列化モデルは，移住の頻度，移住先の選択，移住交代の選択法，などの移住スキーム が重要になる．

Figure 3: Coarse grained parallel model(分散GAの例)

2  これまでの研究動向

先ほど述べた並列モデルの中で並列クラスタにおいて最も効果的な手法は知的システムデザイン研究室 OBの畠中一幸さん金子美華さんによって粗粒度並列化モデル(分散GA)であると述べられている．
ここでは，これまでの研究動向として分散GAを発展させた環境分散GAについて述べる．

2.1  環境分散GA(Distributed Environment GA)

GAを実行する際には様々なパラメータを設定する必要があり，それらのパラメータの違いは解の品質に 大きく影響する．したがって，良好な解を得るためにはパラメータを適切な値で設定することが重要で あるが，それらのパラメータの適切な値を知るためには膨大な予備実験を行うなどの必要性が出てくる．
　この問題を解決するために，分散GAにおいてサブ母集団ごとに異なる値でパラメータを設定するための 手法として以下のような環境分散GAが提案されている．

2.1.1  交叉率と突然変異率の分散

GAでは交叉と突然変異の役割はきわめて重要である．交叉は母集団の中の個体間での情報交換を行う のに用いられ，突然変異率は進化が停滞するのを防ぐために用いられる．このため，GAの性能は交叉率 と突然変異率の最適な選択に依存しているといえる．しかし，交叉率，突然変異率の最適な設定が困難 であることから，これらのパラメータを自己適用させる研究が必要不可欠になった． それが，交叉率と突然変異率を分散させた環境分散GAの研究である．

2.1.2  ペナルティパラメータの分散

制約付き最適化問題では，制約条件のもとで最適化を行う．制約条件には等式で表されるものと不等式 で表されるものがある．このような問題では目的関数の最適化だけでなく，解の実行可能性も考慮しな ければならない．制約付き最適化問題を解く際の自然な方法は，その無制限最適解が最適解そのもので あったり，あるいは既知のやり方で最適解に関連付けることができるような合成関数を導入することで ある．

Reference

同志社大学工学部知識工学科修士論文：畠中一幸著
「並列分散遺伝的アルゴリズムの有効性」
同志社大学工学部知識工学科卒業論文：吉田純一著
「並列分散遺伝的アルゴリズムにおける最適な遺伝オペレータ」



File translated from TEX by TTH, version 2.92.
On 09 May 2001, 16:59.