W. B. Langdon

Genetic Programming + Data Structures = Automatic Programming!

W. B. Langdon


University College, London

Genetic Programming and Data Structures, Kluwer, 1998. W.B.Langdon@cs.ucl.ac.uk http://www.cs.ucl.ac.uk/staff/W.Langdon

Background

• Tutorial based upon Genetic Programming and Data Structures [Langdon1998]

  
  

• Chapters 1 (Introduction), 2 (Survey) and Sections 3.1-3.3 (Advanced GP techniques), will be assumed
  
• Memory (3.4-3.5)

  
  

• Multi-tree programs (3.6)

  3.7, 3.8 Come back to as needed

  
  

• Pareto Optimality (3.9)

  
  

• Evolving a stack (Ch 4)

  
  

• Evolving a queue (Ch 5) (1 of 3 approaches)

  
  

• Evolving a list (Ch 6)

• Using data structures, Dyck language (7.2)

• Calculator (7.3)

  Chapter 8, Price's and Fishers' theorem. GP deception.

• Conclusions

• Effort values (Appendix A),

  Glossary (B),

  Scheduling preventive maintenance (C),

  Implementation, caching and speedups, bench marks,
  ftp addresses (D)

  
  

• References, tutorial page 

  
  

• Order form, 25% discount

Algorithms + Data Structures	=	Programs
Genetic Algorithms + Data Structures	=	Evolution Programs
Genetic Programming + Data Structures	=	Automatic Programming!

``To build [or evolve] a successful program, appropriate data structures should be used together with appropriate algorithms (these correspond to genetic operators used for transforming individual chromosomes [or programs])'',

[Michalewicz1994, page xi].

Aims

• Computers that ``program themselves''

• GP automatically evolving programs
• Performance is similar to or even slightly better than human written programs
• But mainly evolved functions, no side-effects, no memory
• Aim show software engineering
  • can be used in GP
  • can be beneficial

Scalar Memory

One memory cell M0, function SETM0 and terminal M0 (reads M0) [Koza1992]

What to do if M0 is not set?

Indexed Memory

[Teller1993,Teller1994]

Fixed number of cells

Indexed Memory

• What to do if cell has no value?

• What if address is not valid?
  • Make it valid

  • ignore memory, return default value
  • raise exception

  • abort program

• Trees contain a mix of address and data types.

  32 bit integers. Strongly Typed Genetic Programming (STGP)? [Montana1995]

Data Objects

Multi-tree Programs

One Individual - One Program: Five Operations - Five Trees

Multi-tree Crossover

Crossover in One Tree at a time

Pareto Optimality

 

• Traditionally every program given a single fitness measure

• Often program required to do many tasks
• Pareto, keep score on each task separate

• CPU, memory usage or size can also be objectives

• Avoids deciding weighting between objectives

• Discourage population trading one objective against another

How Pareto Works

• Fitness values are compared dimension by dimension.

• If a fitness is no worse than the other in every dimension

  and better in at least one dimension then it dominates

• For example point 2 dominates B but does not dominate A.

  As $2_x > B_x \wedge 2_y \ge B_y$but $2_x > A_x \wedge 2_y \not\ge A_y$,

Pareto Fitness Sharing

• Without dispersive pressure, population tends to converge.

• Multi-objective also tendency for the number of niches to fall however fitness sharing can be used

• fitness sharing estimate individual's Pareto rank by comparing it with a random sample of the whole population (81).

Effect of Comparison Set on Pareto Front

Number of different non dominated fitness values in a list population (Chapter 6) with and without a comparison set (no niche sharing, not elitist, pop=10,000, no demes)

Fitness Sharing Pareto Tournament Selection

• Pareto optimality can be readily combined with tournament selection
• Compare each program in tournament with best
• Instead of one ``best so far'' in the tournament, keep a list of ``best so far'' individuals
• If better than a ``best so far'' individual, that individual is removed from the list.

• If it is worse, then it is discarded.

• If not discarded after whole list, added to the list.

• without sharing at end of tournament, chose at random from ``best so far'' list

• if a candidate has identical fitness to a member of the list, the candidate is discarded.

• With sharing, chose a random sample of whole population

• chose the individual in the list which is dominated the by fewest in the sample

• exerts a divergent selection pressure on the population,

  individuals are preferred if there are few others that dominate them.

Pareto Elitism

• Large steady state population with tournament selection low chance to loose best individual.

• With multi-objectives may have many ``best'' programs. It is possible to kill any of them using tournament selection
• Explicit elitism could be used to protect some

  (user to define which?)

Evolving a Stack, Chapter 4

• Each individual within the population is a trial implementation of the whole of stack
• 5 operations (makenull, top, pop, push and empty).
• Each operation is programmed by its own tree.
• The complete individual is a total of five trees.
• Example stack of ten 32 bit integers.

Choice of Stack Primitives

• Primitives like those a human programmer might use

• arg1, the value to be pushed on to the stack
• arithmetic operators + and -
• constants 0, 1 and the maximum depth of the stack
• 63 integer memory cells (numbered -31...31). read and write (aborted on address errors).
• scalar memory (stack pointer?) aux, inc_aux, dec_aux and write_Aux

Stack Fitness Function

• Same fitness testing for everyone

• Black Box do not look inside memory

• Tests call the 5 procedural interfaces, check values returned. Fitness = number correct answers
• makenull, push return nothing - can only test by later effect on other operations.

• 4 fixed test sequences, each contains 40 operations

  Generated at random (but don't pop empty stack)

  different proportion of operations in each sequence.

  memory reset before each sequence

Number of each the five stack operations

 

Test Sequence	makenull	top	pop	push	empty	Totals
1	2	2	14	14	8	40
2	14	3	2	13	8	40
3	6	2	7	12	13	40
4	3	18	5	8	6	40
Totals	25	25	28	47	35	160

Number of each the five stack operations - by depth

 

Stack length	makenull	top	pop	push	empty	Totals
undefined	4					4
0	11			27	15	53
1	5	6	14	15	9	49
2	5	7	9	3	5	29
3		6	3	2	2	13
4		6	2		4	12
5-10						0
Totals	25	25	28	47	35	160

Integer Values Pushed onto the Stack

 

Seq	Values pushed														No.
1	658	544	923	-508	709	560	816	810	149	-179	-328	1	490	-451	14
2	-23	-365	814	-464	-885	-702	123	-248	-284	828	177	635	-588		13
3	557	113	942	-918	-233	616	223	-95	238	-634	-262	590			12
4	217	539	496	-377	-848	-239	-233	331							8

47 integer values values of arg1 chosen randomly uniformly from the range -1000...999.

Tableau for Evolving a Stack

             

Objective

To evolve a pushdown stack

Architecture

Five separate trees

Primitives

+, -, 0, 1, max, arg1, aux, inc_aux, dec_aux, read, write, write_Aux

Fitness case

4 test sequences, each of 40 tests (see slides  to )

Fitness score

1.0 for each test passed

Selection

Scalar tournament of 4

Hits

n/a

Wrapper

makenull	result ignored
top	no wrapper
pop	no wrapper
push	result ignored
empty	result $>0 \Rightarrow$ TRUE, else FALSE

Parameters

Population = 1000, Max generations = 101, program size <=250

Success

Fitness >=160.0

Stack Results

• 4 runs of 60 find solutions (population 1000)

• pass all fitness cases (160)
• correct stack operation

• general solutions (given enough memory, stack of any size)

• size of test cases about 890 bits
• size of solution e.g. 57 bits for stack 1
• I.e. GP has a good implicit bias?

Evolved Stack 1

Simplified Stack 1

Evolving a Queue, Chapter 5

Pseudo Code Definition of the Five Queue Operations
[Aho et al.1987]
Operation	Code			Comment
addone (i)	addone	:=	(i + 1) % maxlength;	cyclic increment
makenull	head	:=	0;	initialise queue
	tail	:=	maxlength - 1;
empty	empty	:=	(addone (tail) = head);	is queue empty?
front	front	:=	queue[ head ];	front of queue
enqueue( x)	tail	:=	addone (tail);	add x to queue
	queue[ tail ]	:=	x;
dequeue	dequeue	:=	queue[ head ];	return front
	head	:=	addone (head);	and remove it

Note the use of the function ``addone''

Queue

• As with stack, only require GP to deal with correct cases
• Integer data type
• Simultaneous evolution of 5 operations  $\Rightarrow$ 5 trees

• 3 fundamentally different solutions possible
  • packed array (where the data is moved from the rear to the front of the array)

  • linked list
  • circular buffer

Circular Implementation of queues

Enqueue Increase tail by one (and wrapping round if needbe). Write into the new tail cell.

Dequeue Read from head cell. Then increase head by one.

Queue Primitives

• Concentrate on last experiment (5.10)

• Primitives much like those used with stack but:
  • protected modulus
  • linking functions, Prog2, Qrog2
  • Two scalar memories (Aux1, Aux2) (head and tail?)

  • No increment/decrement terminals

  • Function/Terminal sets specific to each operation, slide 

  • An ADF

    (also operations can call some others, NB no recursion) Pass-by-reference (slide )

Queue Memory

As stack but:

• Two scalars
• Allow testing to continue on address indexing errors

  (provide default value, zero)

• Correct, but memory hungry implementations of queue evolved $\Rightarrow$ excessive memory usage penalty

Queue Syntax

• Unlike Stack, terminals and functions specific to each tree

  The six trees fall into categories:

  • those that initialise things (makenull)
  • change the queue (makenull, dequeue, enqueue),

  Using categories primitives restricted to particular trees:

  •   Set_Auxn can only be used by makenull
  • write only in trees where change is expected
  • arg1 only in trees with arguments, i.e. enqueue and adf1.    
  • adf1 no side effects.  
  • dequeue can call front

Good Engineering Practice

  Measures taken to ensure the ADF is ``sensible''.    

• It does not yield a constant i.e. the same value regardless of its argument
• It transforms its input, i.e. its output is not equal to its input.

• test adf1 independently of the rest of the program. Adf1 rejected if either:
  • all the answers returned by adf1 are the same, or
  • any value returned by adf1 is the same as its input  

Pass by Reference

  

• Allow cursor primitives to evolve
• adf1 uses pass-by-reference (book pages 90-91).
• allows adf1 to update the argument

• Example:

  1.

  aux2=8 and adf1 increments its argument

  2.

  (adf1 aux2)

  3.

  changes aux2 to 9.

Queue Parameters

• Population 10,000
• Deme $= 3 \times 3$
• Each operation (5) scored independently

  Memory usage penalty above 12 cells.

• Pareto (6 dimensions) tournament of 4

Queue Fitness Function

• Like the stack all testing is Black box

• Only use of memory is for early detection of excess use
• 5 test cases. 4 like stack. One long (160). Cf. slide 

• ``tangent'' distribution of data values to give high proportion of near zero values

Number of each the five queue operations

 

Queue length	makenull	front	dequeue	enqueue	empty	Totals
undefined	5					5
0	10			27	16	53
1	4	9	14	18	7	52
2	4	12	11	8	7	42
3		9	6	7	5	27
4		4	6	11		21
5		4	11	9	3	27
6		8	9	11	5	33
7		10	11	9	3	33
8		3	9	4		16
9		5	4		2	11
Totals	23	64	81	104	48	320

Integers enqueued

 

	enqueue arguments
	<	-10	-9	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9	10	>
No.	9	1	3	1		2	2	1	1	4	3	18	5	8	8	5	6	3		2	2		20
Total												104

Tableau for Evolving a Queue

         

Objective

To evolve a first-in first-out queue

Architecture

Five separate trees, plus single ADF

Primitives

makenull	+, -, 0, 1, max, mod, PROG2, QROG2, aux1, aux2, read, write, Set_Aux1, Set_Aux2
front	+, -, 0, 1, max, mod, PROG2, QROG2, aux1, aux2, read
dequeue	+, -, 0, 1, max, mod, PROG2, QROG2, aux1, aux2, read, write, Adf1, Front
enqueue	+, -, 0, 1, max, mod, PROG2, QROG2, aux1, aux2, read, write, Adf1, arg1
empty	+, -, 0, 1, max, mod, PROG2, QROG2, aux1, aux2, read
adf1	+, -, 0, 1, max, mod, PROG2, QROG2, arg1

Fitness Case

4 test sequences, of 40 tests and one of 160 (slide )

No program aborts

Fitness Scaling

Each operation scored independently using Pareto comparison (1 per test passed), Memory usage above minimum (12 cells) penalized

Selection

Pareto tournament of 4

Hits

Test passed

Wrapper

makenull	result ignored
front	no wrapper
dequeue	no wrapper
enqueue	result ignored
empty	result $=0 \Rightarrow$ TRUE, otherwise FALSE
adf1	n/a

Parameters

Population = 10,000, G=100, program size $\le 250$, deme $= 3 \times 3$

Success Predicate

320 hits, i.e. all tests passed

Execution of ``caterpillar'' program

Execution of ``caterpillar'' program. Labels in bold indicate current values, dotted show previous values. Shaded cells hold queue. The heavy arrow indicates the general movement of the caterpillar as data items are added to the queue. As items are removed from the head of the queue it moves to the right, i.e. it acts like the tail of a caterpillar.

Evolved Queue Results

• Caterpillar (5.7)

  Correct but requires infinite memory.

• Shuffler (memory contents is moved to keep compact) Correct but only queue of <10 elements

  Very high ``effort''.

• Circular buffer - given cursor primitives

  ``easy'' 5 success in 11 (18) runs.

• Circular buffer - Evolves and uses own cursor primitives

  6 in 57 runs

  3 non-general overfit test cases.

Execution of Queue program 4.

Circular queue implementation. Adf1 increases it's argument by two and arranges on overflow to use the cells it previously skipped (numbers on the arrows indicate order cells are used in). Cell zero is only used once, but other cells are re-used.  

Evolving a List, Chapter 6

Definitions of the Ten List Operations
Makenull	Make the list an empty list and return position given by End.
Retrieve( p)	Return the element at position p.
Insert( x, p)	Insert x at position p, moving elements at p and following positions to the next higher position.
Delete( p)	Delete the element at position p, moving elements at p+1 and following positions to the previous lower position.
End	Return the position following the last element of the list.
First	Return the position of the first position. If the list is empty, return the position given by End.
Next( p)	Return the position following position p.
Previous( p)	Return the position before position p.
Locate( x)	Return the position of the first element containing value x. If x is not in the list at all then return the position given by End.
Printlist	Print the elements in their order of occurrence.

Iteration

 

• Insert, Delete, Locate and Printlist may process multiple list elements $\Rightarrow$iteration (loops) or recursion

• Require GP to evolve loop (not given as high level primitive)
• Fears that forwhile could cause excessive run time:
  • forbidding nested loops

  • loops only where required (i.e. Adf1)
  • limited number of iterations (32) (cf. Section 2.4.2)

List ADF Hierarchy

• A common ADF available to many trees

• Also each has its own ADF
• Operation specific ADFs called via shared ADF

 

List Syntax Restrictions

 

• Prt_adf must contain at least one print function.

   

• The loop index, i0, only inside the forwhile, loop.

• No nested evaluation loops

•   Adf1 must contain at least one loop and least one i0.  

• Code should use its arguments:

        Retrieve, Next, Previous, Adf1, Ins_adf, Del_adf, Loc_adf and Prt_adf must contain arg1 terminal and Adf1 must contain FUNC  (cf. slide )

List Fitness Function 1

• Each operation given own score

• Additional penalties for excessive CPU and memory usage
• 12 objectives are treated separately by Pareto tournaments

• memory initialised to zero or random before each test sequence
• CPU penalty, but with high threshold

List Fitness Function 2

• 21 Fixed test sequences (total 538 operations)

• 167 subsequences. At end of each
  • cross check values (e.g. are values generated by Printlist correct?)

  • if passes increment score of all operations in subsequence

  • else start next test sequence

    (reduces runtime but encourage premature convergence?)

Locating Errors with Fitness Testing

       

• fitness tests try to indicate which code contains errors

• operations which pass all tests up to designated points probably correct (and so is given its maximum score)

  Assume later errors due to other code

• Applied to Retrieve, End, First, Next, Previous and Printlist

Directed Crossover

  

• Use fitness data to bias tree chosen for crossover towards code in need of improvement

• Used on 90% of crossovers

• It avoids trees which are believed to be correct, cf. slide 
• avoid trees that have not been executed

• avoid changing those that passed all their fitness tests
• biased to choose trees that appear to fail most often

  (details given in [Langdon1995]).

Objective

To evolve a list

Architecture

Ten separate trees, plus five ADFs

Primitives

Makenull	PROG2, write, Set_Aux1, End
Retrieve	arg1, read
Insert	PROG2, aux1, adf1, Next, ARG1, ARG2, write
Delete	PROG2, aux1, adf1, Next, ARG1, Prev
End	aux1
First	aux1
Next	arg1
Previous	arg1
Locate	adf1, First, ARG1
Printlist	adf1, First
Adf1	arg1, aux1, forwhile, i0, FUNC, End
Ins_adf	arg1, swap
Del_adf	arg1, swap, ARG1, Next
Loc_adf	arg1, ARG1, read
Prt_adf	arg1, read, print

All trees may contain +, -, 0, 1 and max

Fitness Case	538 trees run in 21 sequences. 167 consistency tests. Tangent test data distribution (F = 15).
Fitness Scaling	Each tree scored independently using Pareto comparison, memory usage above minimum (12 cells) and CPU usage above 120 per test run are Pareto fitness penalties.
Selection	Elitist Pareto Tournament group 4, Niche population sample size 81.
Hits	Number of consistency checks passed
Wrapper	Insert, Delete and Printlist result ignored, otherwise no wrapper.
Parameters	Population = 10,000, G=100, program size <501, Max initial tree size 50, 90% directed crossover.
Success Predicate	167 hits, i.e. all tests passed

 

Primitive	Purpose
max	constant 10 ($\ge$ max list size).
PROG2( t, u)	evaluate t; return u
arg1	argument of current operation or ADF, but:
ARG1, ARG2	arguments of Insert, Delete, Locate or Printlist.
aux1	an auxiliary variable (i.e. in addition to indexed memory).
Set_Aux1( x)	aux1 = x; return aux1
forwhile( s, e, l)	for i0 = s; i0 $\le$ e; i0++
	if timeout (32) exit loop
	if l returns zero exit loop
	return i0
FUNC	call private ADF of operation which called Adf1.
print( d)	if room in print buffer copy d into it; return number items in it
	else evaluate d; return 0
read( x)	if | x$\vert \le l$ return store[ x]
	else return 0
write( x, d)	if | x$\vert \le l$ store[ x] = d; return original contents of store[ x]
	else evaluate d; return 0
swap( x, y)	if | x$\vert \le l$ and | y$\vert \le l$ exchange contents of store[ x] and store[ y]
	if | x| > l and | y$\vert \le l$ store[ y] = 0
	if | x$\vert \le l$ and | y| > l store[ x] = 0
	return 1

Summary of the Properties of
List Operations and ADFs

	Treat as ADF	Returns value	Argu- ments	Pass-by-reference	Directly testable	Sufficient testing
Makenull	$\times$	$\surd$
Retrieve	$\times$	$\surd$	1		$\surd$	$\surd$
Insert	$\times$	$\times$	2
Delete	$\times$	$\times$	1
End	$\surd$	$\surd$				$\surd$
First	$\surd$	$\surd$				$\surd$
Next	$\surd$	$\surd$	1	$\surd$		$\surd$
Previous	$\surd$	$\surd$	1	$\surd$		$\surd$
Locate	$\times$	$\surd$	1		$\surd$
Printlist	$\times$	$\times$			$\surd$	$\surd$
Adf1	$\surd$	$\surd$	1	$\times$
Ins_adf	$\surd$	$\surd$	1	$\times$
Del_adf	$\surd$	$\surd$	1	$\times$
Loc_adf	$\surd$	$\surd$	1	$\times$
Prt_adf	$\surd$	$\surd$	1	$\times$

List Results

• In a group of 56 runs, two produced solutions

• passed all the tests.

• Like the stack and the queue, solutions correct and general, i.e. given sufficient memory would correctly implement a list of any finite size.

First Evolved Solution to List Problem

Evolution of the frequency of rare primitives

The nine primitives which are lost completely from the population are shown as solid lines

Chapter 8 discusses why primitives may become extinct.

Software Maintenance

  Model for maintaining evolved code:

1.

Start with the original fitness function and the population that contained the solution to the original problem

2.

Write additional fitness tests for the new functionality,

3.

Expand the existing individuals with random code for the new functionality,

4.

Evolve the expanded population with both the original and new fitness tests.

Testing Software Maintenance Model on List

• ``original problem'' + new Locate and Delete

• Solve ``original problem''
• Allow solution to spread (10% of pop passed all tests)

• Trees for Delete and Locate (and their associated ADFs) in every individual in the population are re-created at random.

• 7 more test sequences

• The directed crossover mechanism (slide ) ensures crossovers are   allowed in every tree but are weighted towards the newly introduced random code.

Software Maintenance - Results

• 59 runs, 5 pass 1st stage. 2 of these find solutions.

• Estimated ``effort'' for additional functionality 1/100^th to solve the whole of the new problem from scratch.

Problems Solved Using Data Structures

• Three examples in Chapter 7

• Balanced bracket
• Multiple types of bracket as being correctly nested or not (a Dyck language)

• evolves programs which evaluate Reverse Polish (postfix) expressions.

Dyck Language

GP to evolve a recogniser for a Dyck language.

• Two experiments:

  1.

  GP given stack

  2.

  GP given indexed memory and other primitives from which it can evolve stacks cf. Chapter 4.

• The same fitness function, population size etc.

What is a Dyck Language

• Dyck is a context free languages and requires $\ge$ pushdown automata (i.e. stacks).

• Which sentences are correctly bracketed?

• Four types of bracket pairs:

  (, ), [, ], {, }, `, '.

• E.g. {}[] is correctly bracketed but [} is not.

• Limit of ten symbols per sentence.

Architecture

 

• One result producing tree

• No ADFs in experiment 1 (stack given)

• 3 Adfs in experiment 2, having 0, 1 and 0 arguments.

  Evolve to operate like pop, push and top?

  All can be used by main tree

  adf2 (top?) can be used by adf0.

Dyck Terminals and Functions

• ADD, SUB, PROG2, IFLTE, Ifeq, 0, 1, max

  ARG1 (integer representing current bracket), ifopen, ifmatch

  aux1, Set_Aux1

• The differences between the two experiments are shown in the middle and right hand columns of slide . (stack given v. indexed memory plus inc_aux1, dec_aux1 and ADFs).

• The 5 stack primitives are based on the evolved stack but made rugged. Slide .

                   

Objective	Find a program that classifies sequences of four types of bracket ( ( (represented as 5), ) (71), [ (13), ] (103), { (31), } (137), ` (43) and ' (167) ) as being correctly nested or not.
Primitives	Common	Stack Given	Index Memory
All trees:	ADD, SUB, PROG2, IFLTE, Ifeq, 0, 1, max, aux1	Makenull, Empty, Top, Pop, Push	read, write, inc_aux1, dec_aux1
rpb: as all plus	ifopen, ifmatch, ARG1, Set_Aux1		adf1, adf2, adf3
adf1: as all plus			adf3
adf2: as all plus			arg1, arg2
Max prog size	Initial tree limit 50	50	4 x 50 = 200
Fitness Case	286 fixed test examples, cf. slide
Fitness Scaling	Number of correct answers returned.
Selection	Tournament size 4 (After first solution CPU penalty used giving a two dimensional fitness value, fitness niching used with a sample of up to 81 (9 x 9) nearest neighbours).
Hits	Number test symbols correctly classified.
Wrapper	Zero represents True (i.e. in language) and all other values False.
Parameters	Pop = 10,000, G = 50, Pareto, 3 x 3 demes, CPU penalty only after first solution found, Abort on first error in sentence.
Success predicate	Hits $\ge$ 1756, i.e. all answers correct.

 

Fitness Function

• Fitness is given by presenting each program with each bracket from test sentences and

  counting no. correctly classifies as correctly balanced or not.

• All memory is initialised to zero before each test sentence.    

• Sentences chosen at random (too many to use them all).

• To test programs which classify based on a count of $\mbox{opening}-\mbox{closing}$ brackets, we included examples where there are equal numbers but which are not correctly nested (referred to as ``Balanced'', slide ).

• to limit run time, only lengths 1-6 used unless pass them all, then use lengths 7 and 8.

Dyck Test Sentences

 

Len-	Positive		Negative			After Removing Duplicates
gth			Balanced		Rand	Positive	Balanced	Rand	Score
1			all 8						0
2	all	4	all 60					9	18
3					16			10	30
4	all	32	all	24	16	27	16		172
5					16			16	80
6	rand	32	rand	32	32	32	32	32	576
7					16			16	112
8	rand	32	rand	32	32	32	32	32	768
Totals						91	112	83	1756

Dyck Results

• general solutions were evolved by generation 7 to 23 (3 runs in 3).

• non-demic populations, two runs produced solutions in generations 30 and 39

• 0 of 15 runs using indexed memory primitives passed all the tests.

  Some of the more promising runs were extended beyond 50 generations up to 140 generations without finding a solution.

Evolving a 4 Function Integer Calculator

• Each individual within the population consists of five separate trees (num, plus, minus, times and div) plus either zero or two ADFs.

• Each tree returns a value as the current value of the expression (num's answer is ignored).
• Two experiments
  • stack given, no ADFs

  • indexed memory, two ADFs
• Stack operations Makenull and Empty not used

Objective	Find a program that evaluates integer Reverse Polish (postfix) arithmetic expressions.
Primitives	Common	Stack Given	Index Memory
$+ - \times /$ trees:	ADD, SUB, MUL, DIV, PROG2, 0, 1, aux1, Set_Aux1	Top, Pop, Push	read, write, inc_aux1, dec_aux1, adf1, adf2
num: as ops plus	arg1
adf1: as ops but			no adfs
adf2: as ops but			no adfs and add arg1
adf3: as ops but			no adfs and add arg1, arg2
Max prog size	Initial tree limit 50	5 x 50 = 250	7 x 50 = 350
Fitness Case	127 fixed test expressions, cf. slides , and .
Fitness Scaling	Number of correct answers returned.
Selection	Pareto tournament size 4, CPU penalty (initial threshold 50 per operation), fitness niching used with a sample of up to 81 other members of the population.
Hits	Number of correct answers returned.
Wrapper	Value on num ignored. No wrapper on other trees.
Parameters	Pop = 10,000, G = 100, Pareto, no demes, CPU penalty (increased after 1st solution found), abort on first wrong answer given in expression.
Success predicate	Fitness $\ge$ 194, i.e. a program passes all tests.

Calculator Fitness Function

• separate score for each operation (num, plus, minus, times and div) plus a CPU penalty.

• For each correct answer score of each operation used, is incremented.

  Example: 1+2=3 correct $\Rightarrow$ Increment score of num and plus

• 6 scores each contributes as a separate objective in multi-objective Pareto selection tournaments.
• 127 test expressions which include 194 test points

• CPU penalty of $\lfloor$mean$\rfloor$ primitives executed. Ignore if $\le 50$.

Length of reverse polish expressions

 

length	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	Total
No. of cases			10	3	55	27	44	2	36	1	5		8		3	194

Calculator Test Case

  Number of times each tree occurs in reverse polish expression (RPN) test case and the score it has when the whole test case is passed.

Operation	No.	Max Score
num	550	163
plus	67	58
minus	103	85
times	85	64
divide	156	127
	420
Totals	970	497

Calculator Test Case

 Number of symbols (i.e. operators or numbers) used in the RPN test case for each level of expression nesting. (Depth of nesting calculated after the symbol has been processed).

depth	1	2	3	4	5	6	Total
No. of cases	387	390	149	31	12	1	970

Calculator Results

• 6 of 11 runs with stack passed all the tests.

• 4 general solutions to the problem.

• 2 first solutions failed special cases such as 1-1 and x/y=0

• however in both runs general solutions were evolved less than 12 generations later (before 34 generations).

• 0 found in 59 runs using indexed memory

• Alternative ADFs and function sets tried without success

Actions Performed by Terminals and Functions
Primitive	Purpose
DIV( x, y)	if y $\ne$ 0 return x/ y
	else return 1
SUBR( x, y) DIVR( x, y)	As SUB and DIV except yield y- x and y/ x, i.e. operands reversed.
max	constant 10 ($\ge$ max input size).
PROG2( t, u)	evaluate t; return u
ARG1, arg1, arg2	arguments of current operation or ADF
aux1	an auxiliary variable
Set_Aux1( x)	aux1 = x; return aux1
ifopen( x, t1, t2)	if x = 5, 13, 31 or 43 return t1 //i.e. opening symbol
	else return t2
ifmatch( x, y, t1, t2)	if x = 5, 13, 31 or 43 evaluate y //i.e. opening symbol
	if ( x, y) = (5,71), (13,103), (31,137) or (43,167) return t1
	else return t2 // x and y don't match
	else return t2

Actions Performed by
Terminals and Functions 2 (continued)

 

Makenull	clear stack; return 0
Empty	if stack is empty return 0; else return 1
Top	if stack is empty return 0; else return top of stack
Pop	if stack is empty return 0; else pop stack and return popped value
Push( x)	Evaluate x;
	if < 99 items on stack push x; return x
	else return 0
read( x)	if | x$\vert \le l$ return store[ x]
	else return 0
write( x, d)	if | x$\vert \le l$ store[ x] = d
	return original contents of store[ x]
	else evaluate d
	return 0

Chapter 7 shows GP can

• determine if brackets are correctly nested
• multiple bracket types (Dyck language)
• evaluate Reverse Polish Notation (RPN) expressions.
• Section 7.4 reviews GP literature, many cases where appropriate data structures have been used.

    (PADO [Teller and Veloso1995,Teller1996] does not use problem specific data structures. Better than random performance on classification problems with no obvious structure).  

Recommendations

Advice in [Kinnear, Jr.1994] and [Koza1992] remains sound, however:

1.

GP populations should be closely studied as they evolve:

(a)

Frequency of primitives. Recognise when a primitive becomes extinct

(b)

Population variety.

However a high variety does not indicate all is well. Phenotypic (behaviour) variation may also be useful.

2.

Potential ways to encourage population diversity:

(a)

Removal of the reproduction operator.

(b)

Addition of one or more mutation operators.  

(c)

Smaller tournament sizes???

(d)

Splitting large populations into semi-isolated demes.  

(e)

Using fitness sharing to encourage many fitness niches.  

3.

Fitness caches  

4.

Where GP run time is long, periodically save the current state of the run. Should the system crash; the run can be restarted.

The population can be compressed, e.g. using gzip. Compression to <1 bit per primitive

Convergence of phenotype

Value returned by the ``best'' program in the population. First of 50 GP runs of the sextic polynomial problem [Langdon et al.1999, Figure 8.5].

Conclusions

The key to successful human produced software is using abstraction to control the complexity of each task in hand.

While GP work to date has concentrated on functional abstraction (ADFs etc.), GP must also to take advantage of data abstraction

• We have seen GP can evolve data structures

• it can use them

• appropriate data structures are beneficial to GP

• Computers that program themselves? Some way to go...