Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GPDL/Examples/RoyalTree.txt @ 10217

Last change on this file since 10217 was 10080, checked in by gkronber, 11 years ago

#2026 implemented a code generator for random search solvers for GPDL problems
File size: 14.1 KB
Line 
1/* The Royal Tree benchmark problem for GP */
2/* See paper: William F. Punch, How Effective are Multiple Populations in Genetic Programming */
3/* for max. depth 7 (level: g) this is hard to solve. Full enumeration needs a lot of memory. */
4
5PROBLEM RoyalTree
6CODE <<
7  const int MaxDepth = 7;
8  const double FullBonus = 2;
9  const double PartialBonus = 1;
10  const double Penalty = 1.0 / 3.0;
11  const double CompleteBonus = 2.0;
12>>
13
14NONTERMINALS
15  S<<int depth, out double score, out char symb, out bool perfect>>.
16  A<<int depth, out double score, out char symb, out bool perfect>>.
17  B<<int depth, out double score, out char symb, out bool perfect>>.
18  C<<int depth, out double score, out char symb, out bool perfect>>.
19  D<<int depth, out double score, out char symb, out bool perfect>>.
20  E<<int depth, out double score, out char symb, out bool perfect>>.
21  F<<int depth, out double score, out char symb, out bool perfect>>.
22  G<<int depth, out double score, out char symb, out bool perfect>>.
23 
24TERMINALS
25  X. Y. Z.
26
27RULES
28  S<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << perfect = false; if (depth <= 0) { score = 0.0; symb = ' '; return; } >>
29      A<<depth-1, out score, out symb, out perfect>> 
30    | B<<depth-1, out score, out symb, out perfect>>
31    | C<<depth-1, out score, out symb, out perfect>>
32    | D<<depth-1, out score, out symb, out perfect>>
33    | E<<depth-1, out score, out symb, out perfect>>
34    | F<<depth-1, out score, out symb, out perfect>>
35    | G<<depth-1, out score, out symb, out perfect>>                       /* "... it is extremely difficult to climb to a level-f tree and we have never succeeded in climbing to level-g." */
36    | X                                                                    SEM << symb = 'X'; score = 1; >>
37    | Y                                                                    SEM << symb = 'Y'; score = 0; >>
38    | Z                                                                    SEM << symb = 'Z'; score = 0; >>
39  .
40 
41  A<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0;
42                                                                             double s;
43                                                                             bool p;
44                                                                             double w;
45                                                                             char c;
46                                                                             symb = 'A'; perfect = false;
47                                                                           >>
48    S<<depth, out s, out c, out p>>                                        SEM << w = Penalty; if(c == 'X') { w = FullBonus; } >>
49                                                                           SEM << score = w * s; >>
50                                                                           SEM << if (c=='X') { perfect = true; score = CompleteBonus * score; } >>
51  .
52 
53  B<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0;
54                                                                             double s0, s1;
55                                                                             bool p0, p1;
56                                                                             double w0, w1;
57                                                                             char c0 = ' '; char c1 = ' ';
58                                                                             symb = 'B'; perfect = false;
59                                                                           >>
60    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'A') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
61    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'A') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
62                                                                           SEM << score = w0 * s0 + w1 * s1; >>
63                                                                           SEM << if (c0=='A' && c1=='A' && p0 && p1) { perfect = true; score = CompleteBonus * score; } >>
64  .
65 
66  C<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0;
67                                                                            double s0, s1, s2;
68                                                                            bool p0, p1, p2;
69                                                                            double w0, w1, w2;
70                                                                            char c0 = ' '; char c1 = ' '; char c2 = ' ';
71                                                                            symb = 'C'; perfect = false;
72                                                                           >>
73    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'B') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
74    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'B') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
75    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'B') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
76                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2; >>
77                                                                           SEM << if (c0=='B' && c1=='B' && c2=='B' && p0 && p1 && p2) { perfect = true;  score = CompleteBonus * score; } >>
78  .
79 
80  D<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0;
81                                                                             double s0, s1, s2, s3;
82                                                                             bool p0, p1, p2, p3;
83                                                                             double w0, w1, w2, w3;
84                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' ' ;
85                                                                             symb = 'D'; perfect = false;
86                                                                           >>
87    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'C') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
88    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'C') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
89    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'C') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
90    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'C') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
91                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3; >>
92                                                                           SEM << if (c0=='C' && c1=='C' && c2=='C' && c3=='C' && p0 && p1 && p2 && p3) { perfect = true;  score = CompleteBonus * score; } >>
93  .
94
95  E<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0;
96                                                                             double s0, s1, s2, s3, s4;
97                                                                             bool p0, p1, p2, p3, p4;
98                                                                             double w0, w1, w2, w3, w4;
99                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' '; char c4 = ' ';
100                                                                             symb = 'E'; perfect = false;
101                                                                           >>
102    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'D') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
103    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'D') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
104    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'D') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
105    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'D') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
106    S<<depth, out s4, out c4, out p4>>                                     SEM << w4 = Penalty; if(c4 == 'D') { w4 = PartialBonus; if(p4) { w4 = FullBonus; }} >>
107                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3 + w4 * s4; >>
108                                                                           SEM << if (c0=='D' && c1=='D' && c2=='D' && c3=='D' && c4=='D' && p0 && p1 && p2 && p3 && p4) { perfect = true;  score = CompleteBonus * score; } >>
109  .
110 
111  F<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0;
112                                                                             double s0, s1, s2, s3, s4, s5;
113                                                                             bool p0, p1, p2, p3, p4, p5;
114                                                                             double w0, w1, w2, w3, w4, w5;
115                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' '; char c4 = ' '; char c5 = ' ';
116                                                                             symb = 'F'; perfect = false;
117                                                                           >>
118    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'E') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
119    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'E') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
120    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'E') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
121    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'E') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
122    S<<depth, out s4, out c4, out p4>>                                     SEM << w4 = Penalty; if(c4 == 'E') { w4 = PartialBonus; if(p4) { w4 = FullBonus; }} >>
123    S<<depth, out s5, out c5, out p5>>                                     SEM << w5 = Penalty; if(c5 == 'E') { w5 = PartialBonus; if(p5) { w5 = FullBonus; }} >>
124                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3 + w4 * s4 + w5 * s5; >>
125                                                                           SEM << if (c0=='E' && c1=='E' && c2=='E' && c3=='E' && c4=='E' && c5=='E' &&
126                                                                                      p0 && p1 && p2 && p3 && p4 && p5) { perfect = true;  score = CompleteBonus * score; } >>
127  .
128 
129  G<<int depth, out double score, out char symb, out bool perfect>> =      LOCAL << score = 0.0;
130                                                                             double s0, s1, s2, s3, s4, s5, s6;
131                                                                             bool p0, p1, p2, p3, p4, p5, p6;
132                                                                             double w0, w1, w2, w3, w4, w5, w6;
133                                                                             char c0 = ' '; char c1 = ' '; char c2 = ' '; char c3 = ' '; char c4 = ' '; char c5 = ' '; char c6 = ' ';
134                                                                             symb = 'F'; perfect = false;
135                                                                           >>
136    S<<depth, out s0, out c0, out p0>>                                     SEM << w0 = Penalty; if(c0 == 'F') { w0 = PartialBonus; if(p0) { w0 = FullBonus; }} >>
137    S<<depth, out s1, out c1, out p1>>                                     SEM << w1 = Penalty; if(c1 == 'F') { w1 = PartialBonus; if(p1) { w1 = FullBonus; }} >>
138    S<<depth, out s2, out c2, out p2>>                                     SEM << w2 = Penalty; if(c2 == 'F') { w2 = PartialBonus; if(p2) { w2 = FullBonus; }} >>
139    S<<depth, out s3, out c3, out p3>>                                     SEM << w3 = Penalty; if(c3 == 'F') { w3 = PartialBonus; if(p3) { w3 = FullBonus; }} >>
140    S<<depth, out s4, out c4, out p4>>                                     SEM << w4 = Penalty; if(c4 == 'F') { w4 = PartialBonus; if(p4) { w4 = FullBonus; }} >>
141    S<<depth, out s5, out c5, out p5>>                                     SEM << w5 = Penalty; if(c5 == 'F') { w5 = PartialBonus; if(p5) { w5 = FullBonus; }} >>
142    S<<depth, out s6, out c6, out p6>>                                     SEM << w6 = Penalty; if(c6 == 'F') { w6 = PartialBonus; if(p6) { w6 = FullBonus; }} >>
143                                                                           SEM << score = w0 * s0 + w1 * s1 + w2 * s2 + w3 * s3 + w4 * s4 + w5 * s5 + w6 * s6; >>
144                                                                           SEM << if (c0=='F' && c1=='F' && c2=='F' && c3=='F' && c4=='F' && c5=='F' && c6 == 'F' &&
145                                                                                      p0 && p1 && p2 && p3 && p4 && p5 && p6) { perfect = true;  score = CompleteBonus * score; } >>
146  .
147 
148MAXIMIZE
149  <<
150    double score;
151    char symb;
152    bool perfect;
153    S(MaxDepth, out score, out symb, out perfect);
154    return score;
155  >>
156END RoyalTree.
Note: See TracBrowser for help on using the repository browser.