並列クラスタにおけるGAの処理時間について
No. 02, 2001年 6月 6日
片浦 哲平

1  はじめに

今回のレポートでは，GAプログラムを並列化することで処理時間がどのように変化するかを考察する． データを収集するGAプログラムは佐野正樹氏が作成したソースを用いる． 今回のプログラムでは，対象となる問題に乱数を用い，処理はcambriaで行った．

2  実験内容

今回の実験では，PRC_NUM(島数)を変化させることで並列の効果を測った． また，島数の変化に伴い，島数で割り切れるだけのPOP_SIZE(個体数)を選んだ． また，今回はプロセッサ数＝島数ということで，1つのサブ母集団に対して1つの プロセッサを割り当てるという方法で計測した． プログラムの初期パラメータはTable:1 の通りである．

Table 1: 初期値

TRIAL=1	OBJ_FUNC=sleep	MIG_RATE=0.3
MIG_ITVL=5	CROSS_RATE=0.8	G_LENGTH=100
MU_RATE=0.01	LOAD=1	MAX_GENERATION=2000

3  実行結果

まず，実行した結果をTable:2 に示す．

　 Table 2: 実行結果

クラスタ数	個体数	etc	Selection	Migration	Crossover	Mutation	合計
1	4096	186.3053006	395.57341	0.009869	244.427667	154.362667	980.6789136
2	4096	64.431883	127.048592	42.331138	104.373018	71.360762	409.545393
4	4096	34.257255	32.87469	10.682657	61.066126	36.215362	175.09609
8	4096	15.015722	9.148281	3.577251	32.589945	18.461339	78.792538
16	4096	0.740367	3.461006	1.47111	14.987497	9.707319	30.367299
32	4096	2.949651	1.251293	0.888675	8.074433	5.012548	18.1766
51	4080	1.96476	0.594965	3.164427	3.333735	2.145619	11.20351
64	4096	1.6607	0.534036	2.15044	3.119018	1.406074	8.870268
80	4080	0.820223	0.326122	2.74632	1.970274	1.147094	7.010033
91	4095	1.06107	0.296004	1.442369	1.913847	1.377027	6.090317
100	4100	0.959806	0.430478	0.822201	2.343808	1.086122	5.642415
128	4096	0.418504	0.250465	1.664117	1.27001	0.783825	4.386921
204	4080	0.231337	0.108174	1.373741	0.763804	0.390968	2.868024
210	4200	0.229749	0.108519	1.520581	0.779119	0.388429	3.026397
220	4180	0.301871	0.198763	0.494986	1.045141	0.615345	2.656106
222	3996	0.240407	0.09824	0.903459	0.879479	0.420262	2.541847
225	4050	0.247912	0.099936	0.50179	1.251918	0.556353	2.657909
226	4068	0.204245	0.097712	1.201146	0.693106	0.353043	2.549252
227	4086	0.205357	0.099788	1.148694	0.739053	0.357662	2.550554
228	4104	0.203371	0.097872	1.059419	0.801189	0.403901	2.565752

次に得た結果をFig:1 〜Fig:6 に示す．

Figure 1: etc

Figure 2: Selection

Figure 3: Migration

Figure 4: Crossover

Figure 5: Mutation

Figure 6: 合計

Fig:1 〜Fig:6 すべてにおいて，クラスタ数を増やすと計算時間が 短縮されるということが分かった．Fig:3 のMigrationにおいてプロセッサ数が 1のときにほぼ0という値が出たが，これはプロセッサ数＝島数，すなわち島数＝1， したがって，移住が全くない条件のもとでの測定であるからである．

以上の結果をまとめて表示したものをFig:7 に示す．

Figure 7: 全結果

4  考察

今回の結果からクラスタ数を増やせば計算速度が向上するということが分かった．しかし， このプログラムは，乱数を発生させただけのものであるので，解が収束するということは ない．この点をふまえて解が存在する対象問題でも同じような計測を行う必要があると思う．

また，一部でクラスタ数が増えたにもかかわらず，計算速度が落ちたものがあるが これは初期値でTRIAL=1としているため，1回しか試行していないためである．GAは 確率的手法であるのでTRIALの回数を増やし平均をとれば，計算速度はクラスタ数に 比例してよくなると思われる．

しかし，クラスタ数を増やすと総計算時間における通信時間の割合は大きくなる． 現在のクラスタの弱点は100BASEでしか転送できない通信速度にあると思うが， この問題は，今回の計測ではまったく表れなかった．この点は今後考えなければならない ことだと思う．

---

File translated from T_EX by T_TH, version 2.92.
On 09 May 2001, 16:59.