next up previous
Next: RESULTS Up: Quadratic Bloat in Genetic Previous: SUB-QUADRATIC BLOAT

   
EXPERIMENTS

As we intend to run artificial evolution for hundreds of generations on rapidly bloating populations here we restrict ourselves to two problems, one Boolean (6-multiplexer [Koza1992, page 187]) and one continuous (symbolic regression of the quartic polynomial [Koza1992]). Note for speed the quartic problem is simplified and only uses ten test cases. As the distribution of the number programs' for each size and shape is known for binary trees we use only binary functions. Accordingly we introduce a new variation on the Boolean 6-multiplexer problem by replacing Koza's function set with his usual four binary Boolean operators. Using a 64 bit C++ compiler we can evaluate all the 6-multiplexer fitness cases in parallel [Poli and Langdon1999].

Apart from the binary function set, quartic problem population size, the absence of size or depth restrictions and the use of tournament selection our GP runs are essentially the same as [Koza1992]. Parameters are summarised in Tables 1 and 2.


  
Table: 1 GP Parameters for the Quartic Symbolic Regression Problem
Objective: Find a program that produces the given value of the quartic polynomial x2(x+1)(x-1) = x4-x2as its output when given the value of the one independent variable, x, as input
Terminal set: x and 250 floating point constants chosen at random from 2001 numbers between -1.000 and +1.000
Functions set: + - $\times$ $\%$ (protected division)
Fitness cases: 10 random values of x from the range -1 ...1
Fitness: The mean, over the 10 fitness cases, of the absolute value of the difference between the value returned by the program and x4-x2
Hits: The number of fitness cases (between 0 and 10) for which the error is less than 0.01
Selection: Tournament group size of 7, non-elitist, generational
Wrapper: none
Pop Size: 50
Max program: 106 program nodes
Initial pop: Created using ``ramped half-and-half'' with depths between 8 and 5 (No uniqueness requirement)
Parameters: 90% one child crossover, no mutation. 90% of crossover points selected at functions, remaining 10% selected uniformly between all nodes.
Termination: Maximum number of generations 600 or maximum size limit exceeded


  
Table: 2 GP Parameters for Multiplexor Problem (as Table 1 unless stated)
Objective: Find a Boolean function whose output is the same as the Boolean 6 multiplexor function
Terminal set: D0 D1 D2 D3 A0 A1
Functions set: AND OR NAND NOR
Fitness cases: All the 26 combinations of the 6 Boolean arguments
Fitness: number of correct answers
Pop size: 500
Max program: 106 program nodes
Initial pop: Ramped half-and-half max depth between 2 and 6


next up previous
Next: RESULTS Up: Quadratic Bloat in Genetic Previous: SUB-QUADRATIC BLOAT
Bill Langdon
2000-03-16