A Study on E ffect s of Selection Schem es in Genetic Progr am ming for T im e Series Prediction 2000 2
A Study on E ffect s of Selection Schem es in Genetic Progr am ming for T im e Series Prediction 1999 10 1999 12
1. 1 1.1 1 1.2 3 2. 4 2.1 4 2.2 5 2.3 7 3. 10 3.1 10 3.2 12 4. 16 4.1 16 4.2 18 5. 22 5.1 22
6. 27 28
1. 1.1 (selection ).,. (selective pressure) [Bäck - 96].. (genetic diversity ),... (evolution strategy ) (ranking selection ). (tournament selection ) (evolutionary programming ). (genetic algorithm ) (proportional selection). Goldberg Deb (convergence time) (growth ratio) [Goldberg - Deb - 91]. Back Hoffmeister (takeover time) (genetic diver sity ) [Bäck- Hoffmeister - 91]. Mühlenbein Schlierkamp- Voosen (selection differential) (response to selection) [Mühlenbein- SV - 93].. Blickle T hiele - 1 -
(selection variance) [Blickle- T hiele- 95]. (genetic programming ). - 2 -
1.2..,.. 2, 3. 4, 5. 6. - 3 -
2. 2.1.,,.,,, (, ).... - 4 -
2.2. X ( t). X ( t) = (x ( t), x ( t - 1),,x ( t - )). (1) x ( t + ) f (X ( t))., 1. = 1. = 2 = 1. t + 1 X ( t) = (x ( t),x ( t - 1), x ( t - 2)) (2) x ( t + 1). f k (normalzed mean squared error, NMSE ). - 5 -
E k = N M SE ( k) = 1 N Va r N (x ( t + 1) - f k ( X ( t)) ) 2 t = 1 N (x ( t + 1) - x)2 N t = 1 t = 1 x ( t + 1) - f k (X ( t)) 2 (3) Var = 1 N N t = 1 x ( t + 1) - 1 N N t = 1 x ( t + 1) 2 (4) NMSE (predictor ) f k (X ( t)). - 6 -
2.3. Huebner [Huebner - 89-1, Huebner - 89-2, Huebner - 89-3]. [Zhang - et - al- 97]. 81.5 14NH3 cw (FIR). aq(8,7) NH3 N2O P (13). laser 1. LeCroy.. s/ n 300. a/ d bit. (intensity pulsation )....,..,. - 7 -
1000,.,. [Zhang - et - al- 97]. 1 2. - 8 -
1 2-9 -
3. 3.1. Koza [Koza- 92].,......... 1... - 10 -
1. F T A (0). g 1. 2. D A (g ). 3. A (g ),, A ( g + 1). 4.. g g + 1. 2. 1 3-11 -
3.2. A i A. A = {A 1, A 2,,A M } (5). F = {+, -,, % } T = {x ( t),x ( t - 1),x ( t - 2),R }. % 0 1, R [ 0, 1]. 4.. f ( t) = (x ( t - 2) + 0.48) x ( t - 2) 0.48 % x ( t - 1) % (x ( t - 2) + x ( t)) x ( t) (6) - 12 -
4, A k D = { (X ( t),x ( t + 1)) } N t = 1 (7) f k (X ( t)). f k 3 NMSE E k. A k. - 13 -
F k = 1 1 + E k + (K S k ), k = 1, 2,, M (8) S k K.,......... (incremental data inheritance, IDI) [Zhang - Joung - 99- GP].. - 14 -
M G m ax R P c 200 500 20 0.9 P m 0. 1 K 0.00001 L 20 x ( t), x ( t - 1), x ( t - 2), R +, -,, % 2-15 -
4. 4.1 3,,.,. g i (selection probalilty ). p s ( A g i ) = f ( A g i ) f ( A g j ) j = 1 (9) 0... [Blickle- T hiele- 95]. q, q-.. q-. p s ( A g i ) = 1 q ( ( - i + 1) q - ( - i) q ) (10),. (, ) [Schwefel- 95] - 16 -
1,. p s ( A g i ) = { 1, 1 i 0, < i (11) - 17 -
4.2 NMSE.. 3 20 MIP 0.133 0.063 0.070 0.060 0.204 0.116 0.131 0.097 3 NMSE (MIP [Angeline- 98].) 4 5. f ( t) = ( ( ( v0 % ( ( ( ( ( ( ( v1 + v0% ( ( v2 % v0) ( v1 % ( v2 - v1))))) % ( ( ( ( v1 + ( v 1 + ( v0% ( ( v2 % v0) 0.67)))) + v1) (12) 0.81))% (v1% ( v1 0.79))) + v2) + 0.79) v2) + v0)) % ( v1% 0.51)) v2) - 18 -
5 6-19 -
7-9 NMSE.. (fitness scaling ), (tournament size) (truncation threshold).., 100 5 2 ( 9). 7 NMSE - 20 -
8 NMSE 9 NMSE - 21 -
5. [Goldberg - Deb - 91, Bäck- 96], [Mühlenbein - SV - 93], [Blickle- T hiele- 95] 3..... 5.1. Mühlenbein Schlierkamp- Voosen [Mühlenbein - SV- 93]. R (g ) g + 1 g. R (g ). R (g ) = M (g + 1) - M ( g ) (13) M ( g ) g. M s ( g ). S ( g ) = M s ( g ) - M (g ) (14). - 22 -
, S (g ) R ( g ). R (g ) = b g S (g ) (15) b g (quantitative genetics) realized heritability. b g s R s. R s = s s R ( g ) = b S ( g ) (16) g = 1 g = 1 (heritability ). 10-12 20 S (g ). 6-8 NMSE. R (g ) ( 13-15).,. - 23 -
10 11-24 -
12 13-25 -
14 15-26 -
6...,.... - 27 -
[Angeline- 98] Angeline, P. J., Ev olving predict ors for chaotic tim e series, A pp lications and S cience of Comp utational In tellig ence: P roceeding s of S PI E, Volum e 3390, S. Roget s, D. F ogel, J. Bezdek, and B. Bosacci (Eds.), SPIE, Bellingham, WA, pp. 170-180, 1998. [Bäck - 96] Bäck, T., E volutionary A lg orithm s in T heory and P ractice, Oxford Univ er sity Press, New York, 1996. [Bäck - Hoffm eister - 91] Bäck, T. and Hoffm eist er, F., Ext ended selection m echanism s in genetic algorithm s, In Belew, R.K. and Booker, L.B. (eds.), P roc. 4 th I nt. Conf. on Gen etic A lg orithm s, Morgan Kaufm ann, pp. 92-99, 1991. [Blickle- T hiele- 95] Blickle, T. and T hiele, L., A m athem atical analy sis of tournam ent selection, In P roc. S ix th In t. Conf. on Genetic A lg orithm s, Morgan Kaufm ann, pp. 9-16, 1995. [George- et - al- 94] George E.P. Box, Gwilym M. Jenkin s and Gregory C. Rein sel, T im e s eries analy s is : f orecas ting and control, Prentice Hall 1994. [Goldberg - Deb - 91] Goldberg, D. E. and Deb, D., A comparativ e analy sis of selection schem es u sed in genetic algorithm s, In Rawlin s, G.J.E. (ed.) F oundations of Genetic A lg orithm s, pp. 69-93, 1991. [Huebner - 89-1] U. Huebner, N. B. Abraham, and C. O. W eiss : ``Dim en sion s and entropies of chaotic inten sity pulsation s in a single- m ode far - infrared NH3 laser.' ' P hy s. R ev. A 40, p. 6354 (1989) - 28 -
[Huebner - 89-2] U. Huebner, W. Klische, N. B. Abraham, and C. O. W eiss : On problem s encountered w ith dim en sion calculation s. M eas ures of Comp lex ity and Chaos ; Ed. by N. B. Abraham et. al., Plenum Press, New York 1989, p. 133 [Huebner - 89-3] U. Huebner, W. Klische, N. B. Abraham, and C. O. W eiss : Comparison of Lorenz- like laser behavior with the Lorenz m odel. Coherence and Quantum Op tics VI ; Ed. by J. Eberly et. al., Plenum Press, New York 1989, p. 517 [Kim - Zhang - 98] Kim, J.- J. and Zhang, B.- T., Comparison of selection schem es for m achine lay out design, In P roc. A s ia- Pacif ic Conf. on S im ulated E v olution and L earning (SEAL- 98), Canberra, Au stralia, 1998. [Koza - 92] Koza J. R., Genetic P rog ram m ing : On the P rog ram m ing of Comp uters by M eans of N atural S election, MIT Press, 1992. [Mühlenbein - SV - 93] Mühlenbein, H. and S chlierkamp - Voosen, D., Predictiv e m odels for the breeder genetic algorithm : Continuou s par am eter optimization, E volutionary Comp utation, 1(1):25-49, 1993. [Mulloy - Riolo- Savit - 96] Mulloy, B.S., Riolo, R.L. and Savit, R.S., Dynamics of genetic programming and chaotic tim e series prediction, In Genetic P rog ram m ing 1996, pp. 166-174, 1996. [S chw efel- 95] S chw efel, H.- P., E v olution and Op tim um S eek ing, Wiley, New York, 1995. [W eigend- Gershenfeld- 94] W eigend, A. and Ger shenfeld, N., T im e S eries P rediction: F orecas ting the F uture and Unders tanding the P as t, New York : A ddison - W esley,1994 [W hitley - 89] W hitley, D., T he Genit or algorithm and selection pressure: W hy - 29 -
rank - based allocation of reproductiv e trials is best, In P roc. T hird Int. Conf. on Genetic A lg orithm s, Morgan Kaufm ann, pp. 116-121, 1989. [Zhang - Joung - 99- GP ] Zhang, B.- T. and Joung, J.- G., Genetic programming with increm ental dat a inheritance, Genetic and E volutionary Comp utation Conf erence (GECCO- 99), Orlando, Florida, Morgan Kaufm ann, 1999. [Zhang - et - al- 97] Zhang, B.T., Ohm, P., and Mühlenbein, H., Ev olutionary induction of sparse neural trees, E volutionary Comp utation, 5(2):213-236, 1997. - 30 -
.,...,.,,,,,,,., shlim,,,, ~, 94.,,,.,,.,. Hubert Wang.,,,.,. : RAT M,,,, Matt Groening,,,,,,, l' arc en ciel, rancid, bob marley, doors, X- japan,...