. . .

77 - 48211. 0421200025. 1994-0408
-

# 03, 2013
01: 10.7463/0313.0550970
. .
621.3 + 681.3
, ,
. monakhov@rav.sscc.ru
.
() (, ) , . (, ) [1-3] , - .
() = {}, > 0, , , , , , . () () = {/}, > 0. () () (,). - {X}, 1 < / < N, {}, 1 < / < N, , ,
Y' = A(T,P,FM ,X) . , F , (, , , () ).
, : T - (X1,Y1j, 1 < i < N, P FM T, A*,
F(Yt, A*(T, P,FM, Xt)) < F(Yi, A(T, P, FM, Xi))
1 < i < N, P FM.
(Template-based Multi-variant Evolutionary Synthesis - TMES) () , F. ( ) [4] () [5] (MultiExpression Programming -MEP)[6] , ( , , , ).
, . - . . , . , , , . , , .
, [3]. , , , (1) (+), (2) - ( ) ( ), , , ( ) , (3) ( , ї), (4) , (5) . : (1) -, , , (2) (, ), , [1-3], (3) , () , .
, - , , () [7] ( ) .
1. .
, . Gen (), pk () fn , A( T, Gen) T : Gen = {P, FM} = {p1, p2,..., pk; f1, f2,..., fn}, k, n > 0.
Gen A(T,Gen), T.
( ) "". , . . , . ( ), (), , ( ).
, (fitness function, , ) F A(T,Gen) Yi
N
Xt, 1 < i < N, : F = [ A(T,Gen,X,) - Yi ]2.
i=1
F. , , , .. ( ) .
- Gen , pk ( [4]) () fn ( [5]). Gen pk T : , , , , , , :
{[ 5 ][12][-1][+][&][ > ][ |_ J ]}.
Gen () fn . ,
. . , , . , , - ( ), , , , . , , () . / - 8, , /, - . / = ( + 2)/^ - 5 , 8 = {,,2,5}, = {+,-,/,*,^~}
1, N - , - (), - () , F - .
1.
.
N
1 1 = ^ = 5
2 2 2 = 2 ^2 = 2
3 + 1, 2 3 = + 2 *3 = 7
4 4 = ^ = 6
5 * 4, 1 5 = ^5 = 30
6 5 = 5 = 5
7 - 5, 6 7 = - 5 ^7 = 25
8 \ 7 8 = V - 5 ^ = 5
9 / 3, 8 9 = ( + 2) / V - 5 *9 = 1,4
Gen ( ) fn pk, A(T,Gen).
, fn A(T,Gen,Xi), T Gen, , 1 < i < N.
, pmut [0,1]. Gen , . Gen f n , . () (), pcros [0,1]. ( Gen). () fn, . . () . F. , (), ( ). , .
F .
: . , . best. : . best, , , . , best. , , best [], , best . , best. ( ):
, A(T,Gen).
, A(T,Gen), , 1 < i < N.
2. .
() : , , , () , , , , , , , , , .
[8] 4, , ( ).
, .
[7] . . , , = * , -
. ( ) , , . .. , 0( ), - (). ~ 10 -103. .
= 8 + 4 + 2 - - 2 . [4, 5]. : - 100, - 30000, - 0.15, - 0.7, - 20.
8 - = 0,1,...,7, () = (, 4 + 2 - - 2), I = 1,2, 4 + 2 - - 2 - - (. 2). 8 = {, }, - . , , : = {+,-,/,*}. 2 - I , 1 (),
, ( ),
= 1 / 1
- . , 100 .
2. .
1 ^
1 = 2 43,03 19010 0,023 1,68 1871
2 2 = 4 0,076 38,53 0,0078 0,001 9,75
2 , (9,75 1870 ). , ( ).
: = 2*( + 2*( + 2*( + 2*( + 2*( + 2))))) . 8 - = 0,1,...,7, () = (,^),/ = 1,...,4, 1 - , - (. 3). 8 = {,}, - . , , : = {+,-,/,*}. 3
- , 1 (), , (
), = 1 / 1 - .
, 100 .
3. .
0 ^
1 = 2*( + *1), 0,059 25,9 0,012 0,001 4,92
2 = 2*( + 2* *2) 0,45 231,15 0,034 2,27 13,2
3 3 = 2*( + 2*( + *3)) 18,5 9321,4 1,56 211 11,9
4 4 = 2*( + 2*( + 2* *4)) 48,4 24532,2 1,86 270 26
3 , ( 4,92 26 ). , ( ).
, = * sin() * cos() * 3 .
15 - = 0,1,...,14, () = /(), I = 1, . ,4, - (. 4). 8 = {, }, - . , , : = {+,-,/,*}. 4 - 1 , 1 (), ,
( ), = / -
. , 100 .
4. .
i T t p Gp t m Gm Sm
1 T = T1 * x 995,3 5000 113,7 14,4 8,75
2 T = T2 * cos(x) 696,6 292,6 46,6 5,5 14,95
3 T = T3 * cos(x) * x 150,5 31,9 8,7 0,4 17,3
4 T = T4 * cos(x) * x * x 2,55 11,7 1 0 2,55
4 , ( 2,5 17 ). , ( ).
- (Mackey - Glass), : x(n) = 0.9 * x(n -1) + 0.2 * x(n -17) / (1 + x(n -17)10). 100 - x = 0,1,...,99, TS = {x, Cr} ,
NT = {+,-,/,*,pow(5,x)} . , x(n) = a * x(n -1) + b * f (x(n - d)) , a e [0,2], b e [0,2] - , d e [0,21] - , - Gp =801 tp = 905 .,
Gm=194 tm = 65,3 ., .. Sm=14,25.
.
,
, , (, ) - . . , ( ) .

1. Cole M. Algorithmic Skeletons: Structured Management of Parallel Computation. Cambridge: The MIT Press, 1989. 131 p.
2. Watanobe Y., Mirenkov N., Yoshioka R., Monakhov O. Filmification of methods: A visual language for graph algorithms // Journal of Visual Languages and Computing. 2008. Vol. 19, no. 1. P. 123-150. http://dx.doi.org/10.1016/jjvlc.2006.09.003
3. Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA, 1994. 416 p.
4. Goldberg D.E. Genetic Algorithms, in Search, Optimization and MachineLearning. Addison-Wesley, Reading, MA, 1989.
5. Koza J. Genetic Programming. Cambridge: MIT Press, 1992.
6. Oltean M. Multi Expression Programming. Technical Report. Babes-Bolyai Univ., Romania, 2006.
7. .. // . 2006. . 42, 1. . 116-126.
8. Monakhov O.G., Monakhova E.A. An Algorithm for Discovery of New Families of Optimal Regular Networks // Proc. of 6th Inter. Conf. on Discovery Science (DS 2003). Sapporo, Japan, LNAI, N2843, Springer-Verlag, Berlin Heidelberg, 2003. P. 244-254.
SCIENTIFIC PERIODICAL OF THE BAUMAN MSTU
SCIENCE and EDUCATION
EL FS77 - 48211. 0421200025. ISSN 1994-0408
electronic scientific and technical journal
Method of multi-variant evolutionary synthesis of models based on templates
# 03, March 2013
DOI: 10.7463/0413.0550970
Monahov O.G.
Russia, Novosibirsk, Institute of Computational Mathematics and Mathematical Geophysics SB RAS
monakhov@rav.sscc.ru
The author describes an algorithm of a multi-variant evolutionary synthesis which combines advantages of genetic algorithms and genetic programming, based on a sequential operator structure of chromosome and templates (patterns, skeletons) of algorithms and a given set of pairs of input -output data. Influence of many variants of estimating chromosomes and the degree of the templates specialization on search algorithm efficiency in the evolutionary synthesis was investigated. The author obtained estimates of the algorithm complexity and compared them with ones for the standard method of the evolutionary synthesis; this comparison showed a significant (by several times) decrease in search time by using the multi-variant evolutionary synthesis algorithm.
Publications with keywords: skeleton, design pattern, genetic algorithm, evolutionary synthesis, template
Publications with words: skeleton, design pattern, genetic algorithm, evolutionary synthesis, template
References
1. Cole M. Algorithmic Skeletons: Structured Management of Parallel Computation. Cambridge, MIT Press, 1989. 131 p.
2. Watanobe Y., Mirenkov N., Yoshioka R., Monakhov O. Filmification of methods: A visual language for graph algorithms. Journal of Visual Languages and Computing, 2008, vol. 19, no. 1, pp. 123-150. http://dx.doi.org/10.1016/ijvlc.2006.09.003
3. Gamma E., Helm R., Johnson R., Vlissides J. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA, 1994. 416 p.
4. Goldberg D.E. Genetic Algorithms, in Search, Optimization and MachineLearning. Addison-Wesley, Reading, MA, 1989.
5. Koza J. Genetic Programming. Cambridge, MIT Press, 1992.
6. Oltean M. Multi Expression Programming. Technical Report. Babes-Bolyai Univ., Romania, 2006.
7. Monakhov O.G. Evoliutsionnyi sintez algoritmov na osnove shablonov [Evolutionary synthesis of algorithms based on templates]. Avtometriia, 2006, vol. 42, no. 1, pp. 116-126.
8. Monakhov O.G., Monakhova E.A. An Algorithm for Discovery of New Families of Optimal Regular Networks. Proc. of 6th Inter. Conf. on Discovery Science (DS 2003). Sapporo, Japan, LNAI, N2843, Springer-Verlag, Berlin Heidelberg, 2003, pp. 244-254.