www.gp-field-guide.org.uk
Contents Top Previous Next

B.3 Source Code

The original TinyGP system was implemented, in the C programming language, to maximise efficiency and minimise the size of the executable.2 The version presented here is a Java re-implementation of TinyGP. The original version did not allow the use of random numerical constants.

How does TinyGP work? The system is based on the standard flattened (linear) representation for trees, which effectively corresponds to listing the primitives in prefix notation but without any brackets. Each primitive occupies one byte. A program is simply a vector of characters. The parameters of the system are as specified in Section  B.1 . They are fixed at compile time through a series of static class variable assignments. The operators used are subtree crossover and point mutation. The selection of the crossover points is performed at random with uniform probability. The primitive set and fitness function are as indicated above. The code uses recursion for the creation of the initial population (grow), for the identification of the subtree rooted at a particular crossover point (traverse), for program execution (run), and for printing programs (print_indiv). A small number of global variables have been used. For example, the variable program is a program counter used during the recursive interpretation of programs, which is automatically incremented every time a primitive is evaluated. Although using global variables is normally considered bad programming practice, this was done purposely, after extensive experimentation, to reduce the executable's size.

The code reads command line arguments using the standard args array.

Generally the code is quite standard and should be self-explanatory for anyone who can program in Java, whether or not they have implemented a GP system before. Therefore very few comments have been provided in the source code.

The source is provided below.

1
/*2 * Program:   tiny_gp.java3 *4 * Author:    Riccardo Poli (email: rpoli@essex.ac.uk)5 *6 */
7 8import java. u t i l . * ; 9import java.io . * ; 10import java.text.DecimalFormat; 11 12public class tiny_gp { 13 double [ ] f i t n e s s ; 14 char [ ] [ ] pop; 15 static Random rd = new Random(); 16 static final int 17 ADD = 110 , 18 SUB = 111 , 19 MUL = 112 , 20 DIV = 113 , 21 FSET_START = ADD, 22 FSET_END = DIV; 23 static double [ ] x = new double[FSET_START] ; 24 static double minrandom, maxrandom; 25 static char [ ] program; 26 static int PC; 27 static int varnumber, fitnesscases , randomnumber; 28 static double fbestpop = 0.0 , favgpop = 0 . 0 ; 29 static long seed; 30 static double avg_len; 31 static final int 32 MAX_LEN = 10000 , 33 POPSIZE = 100000 , 34 DEPTH  = 5 , 35 GENERATIONS = 100 , 36 TSIZE = 2; 37 public static final double 38 PMUT_PER_NODE  = 0.05 , 39 CROSSOVER_PROB = 0 . 9 ; 40 static double [ ] [ ] targets ; 41 42 double run() { 
/* Interpreter */
43 char primitive = program[PC++]; 44 if ( primitive < FSET_START ) 45 return(x[primitive ] ) ; 46 switch ( primitive ) { 47 case ADD : return( run() + run() ); 48 case SUB : return( run() - run() ); 49 case MUL : return( run() * run() ); 50 case DIV : { 51 double num = run() , den = run(); 52 if ( Math.abs( den ) <= 0.001 ) 53 return( num ); 54 else 55 return( num / den ); 56 } 57 } 58 return( 0.0 ); 
// should never get here
59 } 60 61 int traverse( char [ ] buffer , int buffercount ) { 62 if ( buffer [buffercount] < FSET_START ) 63 return( ++buffercount ); 64 65 switch(buffer [buffercount ] ) { 66 case ADD: 67 case SUB: 68 case MUL: 69 case DIV: 70 return( traverse( buffer , traverse( buffer , ++buffercount ) ) ); 71 } 72 return( 0 ); 
// should never get here
73 } 74 75 void setup_fitness(String fname) { 76 try { 77 int i ,j; 78 String l i n e ; 79 80 BufferedReader in = 81 new BufferedReader( 82 new 83 FileReader(fname)); 84 l i n e = in.readLine(); 85 StringTokenizer tokens = new StringTokenizer(l i n e); 86 varnumber = Integer.parseInt(tokens.nextToken().trim()); 87 randomnumber = Integer.parseInt(tokens.nextToken().trim()); 88 minrandom = Double.parseDouble(tokens.nextToken().trim()); 89 maxrandom =  Double.parseDouble(tokens.nextToken().trim()); 90 f i t n e s s c a s e s = Integer.parseInt(tokens.nextToken().trim()); 91 targets = new double[ f i t n e s s c a s e s ] [varnumber+1]; 92 if (varnumber + randomnumber >= FSET_START ) 93 System.out. println(
"toomanyvariablesandconstants"
); 94 95 for (i = 0; i < f i t n e s s c a s e s ; i ++ ) { 96 l i n e = in.readLine(); 97 tokens = new StringTokenizer(l i n e); 98 for (j = 0; j <= varnumber; j++) { 99 targets [ i ] [ j] = Double.parseDouble(tokens.nextToken().trim()); 100 } 101 } 102 in. close(); 103 } 104 catch(FileNotFoundException e) { 105 System.out. println(
"ERROR:Pleaseprovideadataf
 i l e"
); 106 System. exit(0); 107 } 108 catch(Exception e ) { 109 System.out. println(
"ERROR:Incorrectdataformat"
); 110 System. exit(0); 111 } 112 } 113 114 double fitness_function( char [ ] Prog ) { 115 int i = 0 , len; 116 double result , f i t = 0 . 0 ; 117 118 len = traverse( Prog, 0 ); 119 for (i = 0; i < f i t n e s s c a s e s ; i ++ ) { 120 for (int j = 0; j < varnumber; j ++ ) 121 x[j] = targets [ i ] [ j ] ; 122 program = Prog; 123 PC = 0; 124 result = run(); 125 f i t += Math.abs( result - targets [ i ] [varnumber] ) ; 126 } 127 return(-f i t ); 128 } 129 130 int grow( char [ ] buffer , int pos, int max, int depth ) { 131 char prim = (char) rd.nextInt(2); 132 133 if ( pos >= max ) 134 return( -1 ); 135 136 if ( pos == 0 ) 137 prim = 1; 138 139 if ( prim == 0 || depth == 0 ) { 140 prim = (char) rd.nextInt(varnumber + randomnumber); 141 buffer [pos] = prim; 142 return(pos+1); 143 } 144 else  { 145 prim = (char) (rd.nextInt(FSET_END - FSET_START + 1) + FSET_START); 146 switch(prim) { 147 case ADD: 148 case SUB: 149 case MUL: 150 case DIV: 151 buffer [pos] = prim; 152 return( grow( buffer , grow( buffer , pos+1, max,depth-1), 153 max,depth-1 ) ); 154 } 155 } 156 return( 0 ); 
// should never get here
157 } 158 159 int print_indiv( char [ ] buffer , int buffercounter ) { 160 int a1=0, a2; 161 if ( buffer [buffercounter] < FSET_START ) { 162 if ( buffer [buffercounter] < varnumber ) 163 System.out.print( 
"X"
+ (buffer [buffercounter] + 1 )+ 
""
); 164 else 165 System.out.print( x[ buffer [buffercounter ] ] ) ; 166 return( ++buffercounter ); 167 } 168 switch(buffer [buffercounter ] ) { 169 case ADD: System.out.print( 
"("
); 170 a1=print_indiv( buffer , ++buffercounter ); 171 System.out.print( 
"+"
); 172 break; 173 case SUB: System.out.print( 
"("
); 174 a1=print_indiv( buffer , ++buffercounter ); 175 System.out.print( 
"-"
); 176 break; 177 case MUL: System.out.print( 
"("
); 178 a1=print_indiv( buffer , ++buffercounter ); 179 System.out.print( 
"*"
); 180 break; 181 case DIV: System.out.print( 
"("
); 182 a1=print_indiv( buffer , ++buffercounter ); 183 System.out.print( 
"/"
); 184 break; 185 } 186 a2=print_indiv( buffer , a1 ); 187 System.out.print( 
")"
); 188 return( a2); 189 } 190 191 192 static char [ ] buffer = new char[MAX_LEN] ; 193 char [ ] create_random_indiv( int depth ) { 194 char [ ] ind; 195 int len; 196 197 len = grow( buffer , 0 , MAX_LEN, depth ); 198 199 while (len < 0 ) 200 len = grow( buffer , 0 , MAX_LEN, depth ); 201 202 ind = new char[len ] ; 203 204 System.arraycopy(buffer , 0 , ind , 0 , len ); 205 return( ind ); 206 } 207 208 char [ ] [ ] create_random_pop(int n, int depth, double [ ] f i t n e s s ) { 209 char [ ] [ ]pop = new char[n] [ ] ; 210 int i ; 211 212 for ( i = 0; i < n; i ++ ) { 213 pop[ i ] = create_random_indiv( depth ); 214 f i t n e s s [ i ] = fitness_function( pop[ i ] ); 215 } 216 return( pop ); 217 } 218 219 220 void stats( double [ ] fitness , char [ ] [ ] pop, int gen ) { 221 int i , best = rd.nextInt(POPSIZE); 222 int node_count = 0; 223 fbestpop = f i t n e s s [best ] ; 224 favgpop = 0 . 0 ; 225 226 for ( i = 0; i < POPSIZE; i ++ ) { 227 node_count +=  traverse( pop[ i ] , 0 ); 228 favgpop += f i t n e s s [ i ] ; 229 if ( f i t n e s s [ i ] > fbestpop ) { 230 best = i ; 231 fbestpop = f i t n e s s [ i ] ; 232 } 233 } 234 avg_len = (double) node_count / POPSIZE; 235 favgpop /= POPSIZE; 236 System.out.print(
"Generation="
+gen+
"AvgFitness="
+(-favgpop)+ 237
                                                                                 "BestFitness="
+(-fbestpop)+
"AvgSize="
+avg_len+ 238
                                                                                 "\nBestIndividual:"
); 239 print_indiv( pop[best] , 0 ); 240 System.out.print( 
"\n"
); 241 System.out. flush(); 242 } 243 244 int tournament( double [ ] fitness , int t s i z e ) { 245 int best = rd.nextInt(POPSIZE) , i , competitor; 246 double  fbest = -1.0e34; 247 248 for ( i = 0; i < t s i z e ; i ++ ) { 249 competitor = rd.nextInt(POPSIZE); 250 if ( f i t n e s s [competitor] > fbest ) { 251 fbest = f i t n e s s [competitor ] ; 252 best = competitor; 253 } 254 } 255 return( best ); 256 } 257 258 int negative_tournament( double [ ] fitness , int t s i z e ) { 259 int worst = rd.nextInt(POPSIZE) , i , competitor; 260 double fworst = 1e34; 261 262 for ( i = 0; i < t s i z e ; i ++ ) { 263 competitor = rd.nextInt(POPSIZE); 264 if ( f i t n e s s [competitor] < fworst ) { 265 fworst = f i t n e s s [competitor ] ; 266 worst = competitor; 267 } 268 } 269 return( worst ); 270 } 271 272 char [ ] crossover( char [ ] parent1 , char [ ] parent2 ) { 273 int xo1start , xo1end, xo2start , xo2end; 274 char [ ] offspring ; 275 int len1 = traverse( parent1 , 0 ); 276 int len2 = traverse( parent2 , 0 ); 277 int l e n o f f ; 278 279 xo1start =  rd.nextInt(len1); 280 xo1end = traverse( parent1 , xo1start ); 281 282 xo2start =  rd.nextInt(len2); 283 xo2end = traverse( parent2 , xo2start ); 284 285 l e n o f f = xo1start + (xo2end - xo2start) + (len1-xo1end); 286 287 offspring = new char[ l e n o f f ] ; 288 289 System.arraycopy( parent1 , 0 , offspring , 0 , xo1start ); 290 System.arraycopy( parent2 , xo2start , offspring , xo1start , 291 (xo2end - xo2start) ); 292 System.arraycopy( parent1 , xo1end, offspring , 293 xo1start + (xo2end - xo2start) , 294 (len1-xo1end) ); 295 296 return( offspring ); 297 } 298 299 char [ ] mutation( char [ ] parent , double pmut ) { 300 int len = traverse( parent , 0 ) , i ; 301 int mutsite; 302 char [ ] parentcopy = new char [len ] ; 303 304 System.arraycopy( parent , 0 , parentcopy , 0 , len ); 305 for (i = 0; i < len; i ++ ) { 306 if ( rd.nextDouble() < pmut ) { 307 mutsite =  i ; 308 if ( parentcopy[mutsite] < FSET_START ) 309 parentcopy[mutsite] = (char) rd.nextInt(varnumber); 310 else 311 switch(parentcopy[mutsite] ) { 312 case ADD: 313 case SUB: 314 case MUL: 315 case DIV: 316 parentcopy[mutsite] = 317 (char) (rd.nextInt(FSET_END - FSET_START + 1) 318 + FSET_START); 319 } 320 } 321 } 322 return( parentcopy ); 323 } 324 325 void print_parms() { 326 System.out.print(
"--TINYGP(Javaversion)--\n"
); 327 System.out.print(
"SEED="
+seed+
"\nMAX_LEN="
+MAX_LEN+ 328
                                                        "\nPOPSIZE="
+POPSIZE+
"\nDEPTH="
+DEPTH+ 329
                                                        "\nCROSSOVER_PROB="
+CROSSOVER_PROB+ 330
                                                        "\nPMUT_PER_NODE="
+PMUT_PER_NODE+ 331
                                                        "\nMIN_RANDOM="
+minrandom+ 332
                                                        "\nMAX_RANDOM="
+maxrandom+ 333
                                                        "\nGENERATIONS="
+GENERATIONS+ 334
                                                        "\nTSIZE="
+TSIZE+ 335
                                                        "\n----------------------------------\n"
); 336 } 337 338 public tiny_gp( String fname, long s ) { 339 f i t n e s s =  new double[POPSIZE] ; 340 seed = s; 341 if ( seed >= 0 ) 342 rd.setSeed(seed); 343 setup_fitness(fname); 344 pop = create_random_pop(POPSIZE, DEPTH, f i t n e s s ); 345 for ( int i = 0; i < FSET_START; i ++ ) 346 x[ i]= (maxrandom-minrandom)*rd.nextDouble()+minrandom; 347 } 348 349 void evolve() { 350 int gen = 0 , indivs , offspring , parent1 , parent2 , parent; 351 double newfit; 352 char [ ]newind; 353 print_parms(); 354 stats( fitness , pop, 0 ); 355 for ( gen = 1; gen < GENERATIONS; gen ++ ) { 356 if (  fbestpop > -1e-5 ) { 357 System.out.print(
"PROBLEMSOLVED\n"
); 358 System. exit( 0 ); 359 } 360 for ( indivs = 0; indivs < POPSIZE; indivs ++ ) { 361 if ( rd.nextDouble() > CROSSOVER_PROB  ) { 362 parent1 = tournament( fitness , TSIZE ); 363 parent2 = tournament( fitness , TSIZE ); 364 newind = crossover( pop[parent1] ,pop[parent2] ); 365 } 366 else { 367 parent = tournament( fitness , TSIZE ); 368 newind = mutation( pop[parent] , PMUT_PER_NODE ); 369 } 370 newfit = fitness_function( newind ); 371 offspring = negative_tournament( fitness , TSIZE ); 372 pop[ offspring ] = newind; 373 f i t n e s s [ offspring ] = newfit; 374 } 375 stats( fitness , pop, gen ); 376 } 377 System.out.print(
"PROBLEM*NOT*SOLVED\n"
); 378 System. exit( 1 ); 379 } 380 381 public static void main(String [ ] args) { 382 String fname = 
"problem.dat"
; 383 long s = -1; 384 385 if ( args.length == 2 ) { 386 s = Integer.valueOf(args [ 0 ] ) .intValue(); 387 fname = args [ 1 ] ; 388 } 389 if ( args.length == 1 ) { 390 fname = args [ 0 ] ; 391 } 392 393 tiny_gp gp = new tiny_gp(fname, s); 394 gp.evolve(); 395 } 396};


www.gp-field-guide.org.uk
Contents Top Previous Next