ネットワーク性能に合わせた 分散遺伝的アルゴリズムにおける 最適な移住についての検討 知的システムデザイン研究室 斉藤　宏樹

遺伝的アルゴリズム ・遺伝的アルゴリズム（GA）は有効な最適化手法の 一つ． GAの問題点 ・個体の評価に時間を要する． ・解探索に膨大な反復計算を 行うため計算コストが高い． 並列化により， 計算コストを軽減させ， 実行速度を向上させる

島モデルは分散遺伝的アルゴリズム（DGA）と 並列遺伝的アルゴリズム ・GAを並列化して実行 並列遺伝的アルゴリズム（PGA）の研究が行われて いる． ・PGAの代表的なモデル 実行速度の向上だけでなく、有効な解探索を目的と した，島モデルがある． 島モデルは分散遺伝的アルゴリズム（DGA）と 呼ばれる．

分散遺伝的アルゴリズム ・DGAは母集団を複数の分割母集団（島）に分割し 各島内で遺伝的操作を行うGAの並列モデル． ・移住という操作により各島間で 個体の交換が行われる． 並列で行う場合， 移住には通信を要する．

移住のパラメータ ・移住率 各島内における移住個体の 割合． ・移住間隔 何世代おきに移住するか． 最適な移住のパラメータは，問題に依存し， 何回か試行することで経験的に定めてきた．

DGAを並列計算機上で実行 ・島数を増加させることで，実行時間は短縮するか． （並列化効率は良くなるか．） ・移住のパラメータは，実行時間にどう影響するか． ・CPUやネットワークの性能が異なる並列計算機上で ＤＧＡを実行．

数値実験に用いたマシン ・実験では本研究室にあるGregor，Maiaを使用． CPU Pentium 1GHz×64×2 POWER3-Ⅱ375MHz×16 通信ライブラリ MPI，PVM IBM MPI for AIX 通信プロトコル GM，TCP/IP USプロトコル，TCP/IP 通信媒体 Myrinet 2000， Fast Ethernet SPスイッチ， ・ GregorでMyrinet，Ethernetによる実行時間の比較． ・ MaiaでSPスイッチ，Ethernetによる実行時間の比較．

実験方法 ・移住間隔，島数を変えて計測． 移住間隔を経験的に利用している１と５に設定し， 島数は２から最大４０で実行． ・テスト関数にはRidge関数を使用． 単峰性で依存関係あり． ・１島を１プロセッサとする．

DGAのパラメータ ・DGAのパラメータを以下に示す． ・総個体数を島数で割ったものが，１島の個体数と なる． 総個体数 遺伝子長 設計変数 移住率 終了世代 試行回数 480 200 20 0.5 1000 ・総個体数を島数で割ったものが，１島の個体数と なる．

島数と実行時間 MyrinetはEthernetよりも実行時間が短くなっている． Ethernetは島数が増えると実行時間が長くなっている． Gregor：２０回試行平均 MyrinetはEthernetよりも実行時間が短くなっている． Ethernetは島数が増えると実行時間が長くなっている．

SPスイッチの方がEthernetより実行時間が短い． 島数と実行時間 Maia ：２０回試行平均 SPスイッチの方がEthernetより実行時間が短い．

実行時間における移住時間の割合 Ethernetは島数が増加すると移住に多くの時間を 消費し，移住によるCPUの待ち時間が長い． Gregor ：２０回試行平均 Ethernetは島数が増加すると移住に多くの時間を 消費し，移住によるCPUの待ち時間が長い．

ＳＰスイッチはMyrinet同様移住時間の占める割合が 実行時間における移住時間の割合 Maia ：２０回試行平均 ＳＰスイッチはMyrinet同様移住時間の占める割合が 増加しない．

ネットワーク性能 ・EthernetはＣＳＭＡ/ＣＤ方式． ネットワーク媒体上に，データ転送が行われて いないかどうかを検査し，行われてなければ データ転送を行う． 検査してから転送するまでには遅延時間があり， 同時に送信するデータ数が増加すると， データの衝突を起こす． Myrinet，SPスイッチは通信路が一つでは無く， 衝突が起こらないようにしている．

CPUとネットワーク性能 ・Gregor，MaiaのEthernet CPUの性能とネットワークのバランスが悪いので， 島数が増加すると実行時間が長くなる． ・GregorのMyrinet，MaiaのSPスイッチ CPUの性能とネットワークの性能のバランスが 良いので，実行時間は短くなる． CPUとネットワークの性能に応じて， DGAを実行することが重要である．

CPUとネットワーク性能に応じた移住 ・DGAにおける移住間隔を，通信負荷に応じて， 変更する必要がある． ・移住間隔を以下のパラメータによって，動的に 変更する． 通信負荷率を用いたDGAを実行する．

実験方法 ・移住間隔，島数を変えて実行時間を計測． 移住間隔を始め１に設定し，通信負荷率が 0.2，0.3を超えると，移住間隔を２倍にしていく． 島数は２から最大４０で実行． ・テスト関数にはRidge関数を使用． ・１島を１プロセッサとする． ・Gregorのみで実行． ・DGAのパラメータは前回と同様．

島数と実行時間 ２０回試行平均 通信負荷に応じて動的に移住間隔を変更することで， EthernetにMyrinet同様並列化効率が見られる．

実行中の移住間隔の推移 Ethernet：通信負荷率0.2 島数の増加に伴ない，移住間隔を大きくしている．

実行中の移住間隔の推移 Myrinet：通信負荷率0.2 Myrinetは通信負荷が低く，移住間隔を大きくしない．

解の性能 ・通信負荷に応じて移住間隔を大きくすることで， 実行時間は短くなった． 移住間隔を動的に変更することで， 解探索はどうなるのか． ・Ridge関数の最適解が求まるまでの実行時間， 世代数について，一定間隔の移住（１，５）を行う ものと解の性能を比較する．

DGAのパラメータ 総個体数 遺伝子長 設計変数 移住率 交叉 交叉率 突然変異率 選択 トーナメントサイズ エリート保存 終了世代 試行回数 480 200 20 0.5 一点交叉 1.0 0.005 トーナメント選択 4 1 1000

移住間隔を固定した場合より，最適解を得るまでの 最適解を得るまでの時間 Ethernet ：２０回試行の平均値 移住間隔を固定した場合より，最適解を得るまでの 実行時間が短い．

最適解を得るまでの時間 Myrinet ：２０回試行の平均値

最適解を得るまでの世代数 Ethernet ：２０回試行の中央値 より多くの評価計算が行われている．

最適解を得るまでの世代数 Myrinet ：２０回試行の中央値

まとめ ・異なるCPUとネットワークで，DGAを実行． CPUとネットワーク性能に応じて，DGAを 実行することが重要であることがわかった． 移住間隔を動的に変更することで，マシンの 性能をフルに利用し，並列化効率を向上できた． 解の性能は，従来のDGAより短い実行時間で 求めることができた．

ネットワーク性能の比較 Ethernet Myrinet SPスイッチ 理論バンド幅 12.5MB/sec 160MB/sec トポロジ スイッチングハブ 高速スイッチング

Ethernetで遅延が発生した理由 ・CSMA/CD方式 パケットの増加による衝突． ・TCP/IP処理による遅延 今回の実行時間から考えると，無視できる． これはMaiaによる実行結果からわかる． ・ヘッダ情報の増加 データ数が増加すると，ヘッダ情報が増加するが， 島数が２と４０の場合で0.475KBしか異ならない． これは，移住個体２個分である．

TCP/IPのオーバヘッド解析 単位：マイクロ秒 処理内容 割合 システムコール 1.6 TCP 15.5 IP 6.2 プロトコル処理切り替え 3.2 デバイスドライバ 4.7 ハードウェア割り込み 5.9 NIC＋メディア遅延 7.7 合計 44.8 TCP/IP処理 48.4% 参考資料：Linuxで並列処理をしよう

独自の軽量プロトコルを用いて，低遅延を実現 低遅延ソフトウェアGM 独自の軽量プロトコルを用いて，低遅延を実現

移住の実装 ・移住における通信の方法 MPI_Sendrecv（）により移住個体の遺伝子情報を， 各島間で通信する． MPI_Bcast（）により通信を行う島の情報を， 各島間に送信する． ・通信量 遺伝子の情報量＝移住個体数×200B 通信する島の情報量＝島数×2B

・理論バンド幅の80%の性能がでているとする． 島数が40の場合の通信量 ・理論バンド幅の80%の性能がでているとする． バンド幅＝0.006（移住時間）×12.5MB×0.8＝0.6MB ・通信量 遺伝子の情報量＝6（移住個体数）×200B＝1.2KB 通信する島の情報量＝40（島数）×2B＝0.08KB

移住率 ・移住率を変更しなかった理由 移住率を変化させても，送受信するデータ数は 島数が増加することで増えつづけ，その影響が 大きいと考えたからである．