DNAS上のランダムサーチとDNAS上のDGAの性能比較

上川純一，廣安知之，三木光範

ISDL Report No. 20020408003

2002年9月21日

Abstract

DNAS上に実装したランダムサーチアプリケーションとDNAS上に実装したDGAアプリケーションにおいて，性能比較を行った．結果としてDGAの方が圧倒的に少ない評価計算回数で解に到達することがわかった．

1 はじめに

Distributed Network Application System (以下DNAS)[1]は，ネットワークベースでアプリケーションを実行するためのシステムである．分散したノード間の通信を階層的に制限して行う．このシステムでは，通信を行うためのAPIを提供していて，その上にアプリケーションを実装することができる．現在までに，最適化問題の解決方法である，ランダムサーチと DNAS用の分散遺伝的アルゴリズムが実装されている．二つの手法の性能を比較して， DNAS上に実装した分散遺伝的アルゴリズムの有効性を検証する．

2 ランダムサーチ/DNAS

ランダムサーチをDNAS上に実装した． DNASシステムの各ノードで，独立して処理を行う．各ノードは，乱数を発生し，その乱数で生成された設計変数を評価し，今までしられている値より評価値の高い値を取得したら，それがその時点までに得られた最高値だとし， DNAS serventに情報を伝達する．また，DNAS serventに対して，他のノードの情報を照会し，現在の他のノードの検索状況を取得する．それにより現在探索できている最高の値の情報を取得する．また，DNASシステム上で，自分の下流に居るノードにも伝達するために，取得した情報を自ホストのDNAS serventに伝達する．

この手法は，各ノードが独立に検索するために，並列化効率が良いことはわかっている[1]．

3 分散遺伝的アルゴリズム

遺伝的アルゴリズムとは進化の過程を参考にしている最適化計算の手法である．最適化計算の対象問題の設計変数を個体の遺伝子として表現する．複数の個体をもち，一世代の個体から次の世代の個体を個体の交叉(二つの個体を選び，それぞれの遺伝子配列の部分を継承した新しい個体を作成する)，突然変異(遺伝子が突然すこし変化する)，選択(個体の中でより環境に適合したもの，つまりより最適化問題において最適値に近い値をもつものを残す) の処理を繰り返し，世代を経てより解を得ようという手法である．

DNAS上での分散遺伝的アルゴリズム(以下 DGA)は，各ノードが単純GA(simple GA, 以下 SGA)を行い，その中間結果情報としてランダムな個体の情報を DNAS serventに送信し，また，他のノードの探索個体の情報を自分のシステムにある個体の情報に追加することにより実現している．これは実質的には，個体の情報が他のノードに伝達されていることになり，「各個体が島の中で進化しているところで，他の島に移住している」という状況を模倣しているものだと考えられる．

4 実験

今回は，DNAS上の遺伝的アルゴリズムと， DNAS上のランダムサーチについて，性能を比較した．今回利用したパラメータをTable. 1 に示す．

Table 1: 実験パラメータ

	分散遺伝的アルゴリズム	ランダムサーチ
個体数	100(島あたり)	Not applicable
島数	10
エリートの数	1
設計変数	5
選択	トーナメント選択	Not applicable
交叉	1点交叉
交叉率	100%
突然変異率	0.002
移住率	0.01＊
移住間隔	1世代
トポロジ	ランダムなツリー構造
対象問題	Rastrigin問題
対象問題の大きさ	32-bit 固定小数点 x 5 の計 160 bit

実験結果はFigure. 1に示す．遺伝的アルゴリズムでは選択の過程で，一世代に一個体あたり一回の関数の評価が必要である．ランダムサーチでは，一回乱数を生成するたびにその設計変数によって得られる結果を評価するために関数を評価することが必要になる．

Figure 1: DNAS上での遺伝的アルゴリズムとDNAS上でのランダムサーチの解探索の比較

この結果をみると，遺伝的アルゴリズムがランダムサーチより少ない評価計算回数で最適解に到達するということがわかる．

5 結論

DNASシステム上で遺伝的アルゴリズムとランダムサーチの性能の比較を行った．テストケースとして，Rastrigin 関数を解いた．結果として，ランダムサーチより遺伝的アルゴリズムのほうが格段によい成果をだしているということがわかった．

Reference

[1]: 上川純一，廣安知之，三木光範，谷村勇輔，「動的な階層型システムにおける最適化計算法の検討」，情報処理学会研究報告 2002-HPC-91, Vol. 2002, No. 80, pp. 179-184 (2002)

Copyright

Copyright (C) 2002 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2002 Mitsunori Miki, All rights reserved.
Copyright (C) 2002 Junichi Uekawa, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document．