Matthew Frederick
matthew@mich.distance.net
Indexed Memory
The initial goal of this problem was to evolve a sorting algorithm.
The idea was to put unsorted numbers into an array, run the genetic programming
engine, and see that the elements in the array are now sorted. As
an initial experiment to see how well the genetic programming engine can
handle this type of memory access, an easier problem was designed.
This problem was to evolve an adder function. The arra would be filled
with random number. A number would be passed to the expression each
expression telling it how many cells in memory, starting with the first,
it should sum. So if memory was
| 1.0 | 2.0 | 4.0 | 8.0 | 16.0 | 32.0 | 64.0 | 128.0 | 256.0 | 512.0 |
and the adder was asked to sum the first 4, it should return 15.0.
Since this applet is mainly an experiment, its interface is rather confusing. The number in the upper right give the evolution statistics. The section below it allows you to describe how goo you want the adder to be. These two edit boxes specify the range for the parameter, so if the top box was 0 and the bottom was 2, then the adder would only be asked to add 0 memory cells, 1 memory cell, or 2 memory cells. This was done because the bigger the range, the longer it takes for anything to evolve. The lower half of the right side is for testing. You can specify how many cells you want the current best adder to attempt to add. The group of ten boxes is the actual memory. The large box on the left is the current best expression. This expression can be changed and tested, but you should "Pause" the simulation first before entering your own.
Memory
Unlike any other problem, expressions in this problem have access to internal memory. readMemory and writeMemory are functions for reading and writing memory. readMemory takes one parameter, an index to the memory cell, and returns the value that is in that cell. writeMemory takes two parameters: the first gives the index, and the second tells what number to put there. writeMemory returns what was in the cell before it was overwritten. These functions are describe in Teller. There are 10 memory cells available to expressions. Memory is circular. If an expression tries to access the 11th memory cell, it will be reading the 1st. If it tries to read memory cell -1, it will get the tenth one. Since all numbers are floating point numbers, they are rounded down to an integer when used as an index.
Expressions
Each expression can be composed basic math operations,
constants, conditionals, and some environmental variables. Add, subtract,
multiply, divide, cosine, sine, inverse cosine, and inverse sine are available
to expressions, as well as a branching conditional "if less than zero branch
one way else branch the other way". Constants range in value between
-100.0 and 100.0. The following environmental variables
are available to expressions:
| memorySize | the number of contiguous memory cells the adder is expected to sum |
Criterion for evaluating the controller
Each expression is tested 10 times. The negative difference squared between the real sum and the sum returned by the controller is used for the fitness. Bonus points are given for having the exact answer.
Results
Unlike the other problems, this one wasn't very successful. Even after 100,000 generations, it couldn't evolve a algorithm to add more than the first 7 elements. What a human could write as:
(add (add (add (iflz (sub 5.0 memorySize) (readMemory 5.0) 0.0) (iflz (sub 4.0 memorySize) (readMemory 4.0) 0.0)) (add (iflz (sub 3.0 memorySize) (readMemory 3.0) 0.0) (iflz (sub 2.0 memorySize) (readMemory 2.0) 0.0))) (add (iflz (sub 1.0 memorySize) (readMemory 1.0) 0.0) (iflz (sub 0.0 memorySize) (readMemory 0.0) 0.0))))
was written by the computer as:
(add (sub (readMemory (sub -60.374517400584196 (writeMemory (add -76.2791328651407 (memorySize)) (readMemory (add (iflz -37.641889946442134 -2.5155250841057466 (iflz (add (add 25.177616215846157 (iflz -62.15722517355755 (sub -60.374517400584196 (sub 58.39285076086421 (add (writeMemory (add -55.50486866268854 (memorySize)) (sub (add 91.80731112921876 (memorySize)) (div (writeMemory (memorySize) (add (memorySize) (writeMemory -20.533903759704813 (readMemory -89.60338282266889)))) 4.793246383095621))) (div (readMemory -37.641889946442134) (readMemory (sub -2.5155250841057466 (memorySize))))))) (add (add (iflz (add 25.177616215846157 (readMemory (add (add 25.177616215846157 (add (add (writeMemory 58.39285076086421 (sub 58.39285076086421 58.39285076086421)) (add -37.641889946442134 (writeMemory -63.35340470531234 (sub (add (add (add (readMemory -5.431634256314439) (iflz -89.60338282266889 (writeMemory (add (memorySize) 53.89569269196474) (memorySize)) (writeMemory (div (div (memorySize) 25.177616215846157) (div (memorySize) (add -63.35340470531234 58.39285076086421))) (memorySize)))) (readMemory (div (writeMemory (sub (memorySize) 25.177616215846157) (add -60.374517400584196 (readMemory -76.2791328651407))) (sub (memorySize) 25.177616215846157)))) (readMemory (sub -2.5155250841057466 (memorySize)))) (sub 58.39285076086421 58.39285076086421))))) -21.26645430031671)) (readMemory (div (writeMemory (sub (memorySize) 25.177616215846157) (add -60.374517400584196 (readMemory 43.28762857138065))) (sub (memorySize) (readMemory (sub -2.5155250841057466 (memorySize))))))))) (memorySize) (writeMemory (sub (memorySize) 25.177616215846157) (add (writeMemory (add -55.50486866268854 (memorySize)) (sub (div (writeMemory -12.338174073064494 (add (readMemory (add (readMemory 58.39285076086421) 58.39285076086421)) (writeMemory -20.533903759704813 (readMemory (memorySize))))) 7.472573356232843) (div (writeMemory -2.5155250841057466 (add (readMemory 91.80731112921876) -60.374517400584196)) 7.472573356232843))) (readMemory -37.641889946442134)))) 91.80731112921876) 58.39285076086421))) 25.177616215846157) (readMemory -60.374517400584196) (add 25.177616215846157 (writeMemory (add -76.2791328651407 (memorySize)) -21.26645430031671)))) -76.2791328651407))))) (sub -60.374517400584196 (writeMemory (div (add (add 91.80731112921876 (memorySize)) -63.35340470531234) -2.5155250841057466) -60.374517400584196))) (writeMemory 58.39285076086421 53.89569269196474))
References
Teller, Astro. (1994). The 1994 7th Annual Florida AI Research Symposium. "Genetic Programming, Indexed Memory, The Halting Problem and Other Curiosities". Piscataway, NJ: IEEE Press.