研究報告

１．先週からの課題

先週からの課題としてはSGAの並列化があった．

２．研究報告

SGAのプログラムを並列化できるように，SGAプログラムにエリート保存を加えた．しかし，今週はコンパ担当の仕事，テスト勉強，下坂君の月例発表会の手伝いをしていたのでそれ以外に特に進展はない．

報告できるものとして月例発表会のために補足としてデータを取ったので，それを報告する．

プログラムは佐野さんのベンチマーク用のプログラムで，実行はCambriaで行った．初期値は以下の通りである．

表1　初期値

まず，個体数4096のときの実行結果を以下に示す．

図1　個体数4096のときのベンチマークの結果

図2　図1の結果から見たSpeedupの比較

図1，2からGAは並列効果が大きいということがわかる．しかし，月例発表会で吉田純一さんから指摘があったが，図2のidealとtotalは同じGAのモデルではなく，totalは逐次GAを並列化した場合で，idealは並列モデルに適したDGAを用いている．したがって純粋な意味での比較にはならないのである．

次に図1の結果のなかで移住について注目し，個体数が異なった場合にはどのようになるかを測定してみた．

個体数256，512，1024，2048の時の実行結果を以下に示す．

図3　個体数別の移住時間

図3から，図1以上に顕著な結果が出た．個体数が256の場合はプロセス数が32を超えると移住時間が大きくなり，個体数が512以上の場合にはプロセス数が64を超えると移住時間が大きくなるという結果になった．

３．考察および今後の課題

移住は移住率によって決定されるので，プロセス数がいくらであっても全体的な個体の移動数に違いはない．プロセス数が増えると移住時間が減少していた理由は1通信で移動する個体数の違いのためであると思われる．逐次のDGAならば，移住はどのような移住トポロジーをとっても1つの島ごとにしか行われないが，並列GAならば通信の空いている島同士で同時に通信が行えるので効率がよいものだと思われる．

移住時間が大きくなる原因は，通信するデータに対する通信の際に用いるヘッダの容量の比率が大きくなっているためではないかと考えられる．そのため，個体数が少ないと移住する個体数が少ないので，総データ量に対するヘッダの割合が高く，個体数が多い場合に比べて少ないプロセス数で移住時間が増加していると考えられる．

今後は，自分で作成したGAのプログラムで通信時間および，解の精度についても考察していきたいと考えている．