研究報告補足資料(Jiro Kamiura:2001.10.08)

Rastrigin関数について移住率と移住間隔をそれぞれ変化させて各々20回試行を行った結果を使用して，移住率，移住間隔の両パラメータが遺伝的アルゴリズムの解探索に有意に影響することを示す．また，移住率と移住間隔が互いに相互作用を持つことも示す．

実験に使用したパラメータをTable.1に示す．

Table1. パラメータ

パラメータ名	値
設計変数の数	10
染色体長	100 ( 10設計変数×10ビット )
母集団サイズ	400
島数	40 ( 1島あたり10個体 )
選択手法	ランキングルーレット選択
移住トポロジ	ランダムリング
移住方法	ランダム --> ホール
移住機会	選択の後
移住間隔	1 , 5 , 10
移住率	0.1 , 0.3 , 0.5
交叉手法	一点交叉
交叉率	1.0
突然変異手法	通常の突然変異
突然変異率	0.01 ( 1/染色体長 )
エリート個体数	1
エリート保存の順番	保存が先
エリートをどこから選ぶか	個体＋エリート
エリート個体の選び方	上位
エリートの戻し方	ワーストを上書き
エリートを必ず選択するか	必ず選択する
終了条件	800000評価 ( 2000世代)
試行回数	20

Table2.移住率と移住間隔の実験結果

			移住率
			B₁	B₂	B₃
			0.1	0.3	0.5
移住間隔	A₁	1	30800 38000 38400 39200 39600 40000 40000 42000 42000 43200 43200 43600 44800 47600 47600 48400 48800 51200 56400 70400	24800 28800 28800 29200 30400 32000 35200 35600 36000 38800 40400 41200 41600 45600 45600 53600 57600 58400 61200 67200	26800 27200 28000 28400 28400 33200 35200 37200 37600 38400 44400 45200 46800 48000 48400 48800 51200 61200 70000 96400
	A₂	5	50800 57200 59600 59600 60800 64400 64800 65200 66800 67200 68000 68800 69200 70000 72000 72800 74400 74800 74800 77600	42800 44800 45600 46800 48800 49600 50400 50400 52400 52400 52400 53200 54400 54800 55200 55200 57200 58400 60400 60800	39200 42000 42400 42400 43600 44400 44800 45600 46000 46400 46800 47200 47600 49200 50400 50400 50800 50800 52400 55600
	A₃	10	68800 72400 73200 79600 79600 82000 82400 84400 85200 86000 88800 88800 90000 92400 92400 94000 96800 100400 100800 101600	56800 59200 60800 62400 63200 63600 64400 64400 64400 64800 65600 66400 67600 68400 68400 68800 68800 68800 71600 72800	52800 53200 53600 56400 56400 56400 56800 58000 59600 60800 60800 60800 61200 61600 62400 64400 65600 65600 68800 74000

Table3.実験結果の平均値

			移住率
			B₁	B₂	B₃
			0.1	0.3	0.5
移住間隔	A₁	1	44760	41600	44040
	A₂	5	66940	52300	46900
	A₃	10	86980	65560	60460

本節では，[1]の手順に従って分散分析を行う．

データの分解式

平均μの推定値は全データの平均である．

m = 56615.55556

因子 A の各水準 A_i に対する真値 α_i の点推定は以下の通り．

a₁ = -13148.88889
a₂ = -1235.555556
a₃ = 14384.44444

同様に，因子 B の各水準 B_i に対する真値 β_i の点推定は以下の通り．

b₁ = 9611.111111
b₂ = -3462.222222
b₃ = -6148.888889

ここで，因子Aと因子Bが互いに独立に特性値yに影響する場合には式(1)の構造模型を使用する．

y_ij = μ + α_i + β_j + ε_ij ... (1)

しかし，因子Aと因子Bが互いに影響を与えながら特性値yに影響する場合には，式(2)の構造模型を使用する．

y_ij = μ + α_i + β_j + γ_ij + ε_ij ... (2)

λ_ij が因子Aと因子Bの交互作用（A×B）を表す．A×Bの自由度は，因子Aの自由度と因子Bの自由度の積となる．
ここで，因子Aと因子Bの交互作用を含む残差

e_ij = y_ij - ( m + a_i + b_j) ... (3)

を求めると，Table.4のようになる．

Table4.因子Aと因子Bの交互作用を含む残差

			移住率
			B₁	B₂	B₃
			0.1	0.3	0.5
移住間隔	A₁	1	-22277.78 -15077.78 -14677.78 -13877.78 -13477.78 -13077.78 -13077.78 -11077.78 -11077.78 -9877.78 -9877.78 -9477.78 -8277.78 -5477.78 -5477.78 -4677.78 -4277.78 -1877.78 3322.22 17322.22	-15204.44 -11204.44 -11204.44 -10804.44 -9604.44 -8004.44 -4804.44 -4404.44 -4004.44 -1204.44 395.56 1195.56 1595.56 5595.56 5595.56 13595.56 17595.56 18395.56 21195.56 27195.56	-10517.78 -10117.78 -9317.78 -8917.78 -8917.78 -4117.78 -2117.78 -117.78 282.22 1082.22 7082.22 7882.22 9482.22 10682.22 11082.22 11482.22 13882.22 23882.22 32682.22 59082.22
	A₂	5	-14191.11 -7791.11 -5391.11 -5391.11 -4191.11 -591.11 -191.11 208.89 1808.89 2208.89 3008.89 3808.89 4208.89 5008.89 7008.89 7808.89 9408.89 9808.89 9808.89 12608.89	-9117.78 -7117.78 -6317.78 -5117.78 -3117.78 -2317.78 -1517.78 -1517.78 482.22 482.22 482.22 1282.22 2482.22 2882.22 3282.22 3282.22 5282.22 6482.22 8482.22 8882.22	-10031.11 -7231.11 -6831.11 -6831.11 -5631.11 -4831.11 -4431.11 -3631.11 -3231.11 -2831.11 -2431.11 -2031.11 -1631.11 -31.11 1168.89 1168.89 1568.89 1568.89 3168.89 6368.89
	A₃	10	-11811.11 -8211.11 -7411.11 -1011.11 -1011.11 1388.89 1788.89 3788.89 4588.89 5388.89 8188.89 8188.89 9388.89 11788.89 11788.89 13388.89 16188.89 19788.89 20188.89 20988.89	-10737.78 -8337.78 -6737.78 -5137.78 -4337.78 -3937.78 -3137.78 -3137.78 -3137.78 -2737.78 -1937.78 -1137.78 62.22 862.22 862.22 1262.22 1262.22 1262.22 4062.22 5262.22	-12051.11 -11651.11 -11251.11 -8451.11 -8451.11 -8451.11 -8051.11 -6851.11 -5251.11 -4051.11 -4051.11 -4051.11 -3651.11 -3251.11 -2451.11 -451.11 748.89 748.89 3948.89 9148.89

これを，繰り返し数ずつの平均(Table.5)と残り(Table.6)との和に分ける．
この繰り返し数ずつの平均が交互作用γ_ijを表し，残りは残差を表す．

Table5.交互作用γ_ij

			移住率
			B₁	B₂	B₃
			0.1	0.3	0.5
移住間隔	A₁	1	-8317.78	1595.56	6722.22
	A₂	5	1948.89	382.22	-2331.11
	A₃	10	6368.89	-1977.78	-4391.11

Table6.残差

			移住率
			B₁	B₂	B₃
			0.1	0.3	0.5
移住間隔	A₁	1	-13960 -6760 -6360 -5560 -5160 -4760 -4760 -2760 -2760 -1560 -1560 -1160 40 2840 2840 3640 4040 6440 11640 25640	-16800 -12800 -12800 -12400 -11200 -9600 -6400 -6000 -5600 -2800 -1200 -400 0 4000 4000 12000 16000 16800 19600 25600	-17240 -16840 -16040 -15640 -15640 -10840 -8840 -6840 -6440 -5640 360 1160 2760 3960 4360 4760 7160 17160 25960 52360
	A₂	5	-16140 -9740 -7340 -7340 -6140 -2540 -2140 -1740 -140 260 1060 1860 2260 3060 5060 5860 7460 7860 7860 10660	-9500 -7500 -6700 -5500 -3500 -2700 -1900 -1900 100 100 100 900 2100 2500 2900 2900 4900 6100 8100 8500	-7700 -4900 -4500 -4500 -3300 -2500 -2100 -1300 -900 -500 -100 300 700 2300 3500 3500 3900 3900 5500 8700
	A₃	10	-18180 -14580 -13780 -7380 -7380 -4980 -4580 -2580 -1780 -980 1820 1820 3020 5420 5420 7020 9820 13420 13820 14620	-8760 -6360 -4760 -3160 -2360 -1960 -1160 -1160 -1160 -760 40 840 2040 2840 2840 3240 3240 3240 6040 7240	-7660 -7260 -6860 -4060 -4060 -4060 -3660 -2460 -860 340 340 340 740 1140 1940 3940 5140 5140 8340 13540

分散分析表

Table.7に移住率と移住間隔の分散分析表を示す．（判定の部分の**は1%で有意，*は5%で有意であることを示す．）

Table7. 移住率と移住間隔の分散分析表

要因	SS	f	V	F	判定	備考
M	5.8E+11	1	5.8E+11	-	-	F₁₅₀² = 4.75 2.41 F₁₅₀⁴ = 2.43 3.44
A(移住間隔)	2.3E+10	2	1.1E+10	141.24	**
B(移住率)	8.5E+09	2	4.27E+09	52.66	**
A×B	3.8E+09	4	9.5E+08	11.73	**
e	1.4E+10	171	8.1E+07	-	-
計	6.3E+11	180	-	-	-

よって移住率と移住間隔は遺伝的アルゴリズムの解探索に対して99%の信頼率で有意に影響があるといえる．
また，移住率と移住間隔は99%の信頼率で有意に相互作用があるといえる．

区間推定

因子Aの各水準における推定値は，

A₁ = m + a₁ = 9611.11
A₂ = m + a₂ = -3462.22
A₃ = m + a₃ = -6148.89

信頼幅は，これらが60 = 20試行*3（Bの水準数）個のデータの平均であることから，

信頼幅 = ±t₁₂₀(0.01) * sqrt(V_e/60) = ±3040.61

となる．
同様に因子Bの信頼幅も

信頼幅 = ±t₁₂₀(0.01) * sqrt(V_e/60) = ±3040.61

となる．

交互作用A×Bについては，単純に推定しないで，主効果との組み合わせで推定を行う．まず，因子Aと因子Bを組み合わせたときの推定値は，γの推定値をcで表すと，

A₁B₁ = m + a₁ + b₁ + c₁₁ = 44760
A₂B₁ = m + a₂ + b₁ + c₂₁ = 66940
A₃B₁ = m + a₃ + b₁ + c₃₁ = 86980
A₁B₂ = m + a₁ + b₂ + c₁₂ = 41600
A₂B₂ = m + a₂ + b₂ + c₂₂ = 52300
A₃B₂ = m + a₃ + b₂ + c₃₁ = 65560
A₁B₃ = m + a₁ + b₃ + c₁₃ = 44040
A₂B₃ = m + a₂ + b₃ + c₂₃ = 46900
A₃B₃ = m + a₃ + b₃ + c₃₃ = 60460

となる．
これは，測定によって得られたデータの平均に等しい．
これらの信頼幅を求めるためには，有効反復数を使う．右辺の要因に含まれる自由度を考えると，平均Mは1，因子Aは2，因子Bは2，交互作用A×Bは4なので，合計の自由度は9である．すると，合計の実験回数は180回なので，

有効反復数 = 180/9 = 20

となる．
こうして信頼幅は，

信頼幅 = ±t₁₂₀(0.01) * sqrt(V_e/20) = ±5266.50

よってそれぞれの区間推定は，Table.8のようになる．

Table8. 区間推定の結果

移住間隔/移住率	1/0.1	5/0.1	10/0.1	1/0.3	5/0.3	10/0.3	1/0.5	5/0.5	10/0.5
上限	50026.50	72206.50	92246.50	46866.50	57566.50	70826.50	49306.50	52166.50	65726.50
平均	44760	66940	86980	41600	52300	65560	44040	46900	60460
下限	39493.50	61673.50	81713.50	36333.50	47033.50	60293.50	38773.50	41633.50	55193.50

平均と1%区間推定した結果を図示すると，Fig.1のようになる．

Fig1. 最適解発見までの評価計算回数（Rastrigin : 平均，1%区間推定）

参考文献

[1] 中村義作， "よくわかる実験計画法"，pp.19 - 37 ( 近代科学社，東京， 1997 )
[2] Statistical table of standard normal distribution， "http://aoki2.si.gunma-u.ac.jp/CGI-BIN/tfxp010.html"
[3] t分布表，"http://espero.edu.toyama-u.ac.jp/~psi/stat2000/DATA/TBU.HTM"

: TOP PAGE :

(1) 2001.10.08
(2) 2001.10.10 : 計算間違いを修正．