SELs in arrays
SELs in arrays
- Subject: SELs in arrays
- From: Robert Goldsmith <email@hidden>
- Date: Wed, 26 Sep 2001 00:24:40 +0100
hi everyone :)
Thankyou for all the help :)
As a couple of you asked for a little more detail, here it is. Anyone
not interested, please scan down to the couple of questions I have at
the end <g>
The program is a form of Genetic Programming. To be precise, it is
called Cartesian GenetiC Programming, a for of GP developed by my
supervisor, myself and a few other researchers as a way to improve
the performance of GP systems. So what is GP? Basically, we copy
nature. We have a problem and, instead of just trying to find the
answer in normal logical ways, we mimic the processes of evolution:
stocastic, population based 'generate and test'.
The basic formula is easy:
1) generate an initial collection of possible solution
representations (the population)
2)Test each one (evaluation)
3)Select one or more of the better ones (Selection)
4)Generate a new population based on the selected entities from part 3
5)jump back to stage 2 and repeat until a solution is found.
Easy :)
The solution representation in most GP systems is some form of a
tree. the top node of the tree has its output treated as the answer
and at the bottom of the tree, at the leaves, you feed in the input
values and constants you wish to use. Each node of the tree is an
operation. It has inputs and outputs (usually 2 or 3 inputs and 1
output). Operations such as arithmetic, logic and programmatic
commands can be used (with care).
GP systems can be used to solve timetabling and logistics problems,
paint pictures, compose music, design circuits and pcb layouts and
many other things. However, they are usually painfully slow :)
CGP takes things one step further. Unlike normal GP with it's trees,
CGP uses graphs - allowing a much more compact evolved
representation. CGP has a few other advantages I won't go into :)
Although the general idea is very simple (always the best <g>), when
it comes to actually writing the code (and expanding on the very
basic outline above) things get a bit messy. I have done this in C
with vast vast swathes of pointers but i wanted to expand the system
further so figured oo was a better (if slightly slower) approach.
The system needs a collection of entities (the population) in an
array (so they can be identified by index). Each entity holds one
possible representation of a solution. That's the easy part.
Each entity has an array of nodes. Each node has it's inputs
connected to the output of a node with a lower index (so no loops
occur) and it is totally allowed - in fact better - for two nodes to
get their inputs from the same node output. These links are not
static but, in stage 4 above, are 'mutated' to create changes between
entities in the population.Basically, at any time, any node could be
connected to any node with a lower index and it changes often.
Each node also has an operation. In fact, each node has a selection
of operations and, like the links, the operation actually used may
change at any time and will change often.
the entity, totally separately, may have a number of inputs and
outputs. The inputs are represented by input-nodes with a fixed
output, no inputs and no operation. Each output is 'tapped' from a
random (and, yes, often changing) node somewhere in the array of
nodes. As you will realise, this means that not every node plays a
part in generating the outputs.
Because some nodes are redundant at any one moment, it is not a good
idea to evaluate every node so the evaluation process starts at one
of the nodes tapped by an entity output and works back through the
node structure until input-nodes are hit and the evaluation process
can build up from the bottom in a recursive nature. Values are cached
to prevent the need to re-evaluate.
Most of this is basic, boring oo coding but there are a few
interesting design questions raised:
************* people only looking for questions please start reading
here <g> ***********
1) For each node, a message has to be sent to each of it's inputs
asking for a value. The inputs change often and this is a time
critical method (evaluation takes by far the largest percentage of
processing time). I have a c array holding the Id's of the inputs.
Whenever a mutation occurs, i ask the parent entity (each node knows
about it's parent) to randomly select for it a node with an index
higher than itself. As the nodes are in an NSArray i use
indexForNodeIdenticalTo to get the node index then randomly select an
index lower and pass back the ID of the object at that index. This
way, each node only has to make one call to get a result (instead of
having to ask the parent).
Does this all sound reasonable?
I use a C array here because I don't know how slow NSArray and
NSMutableArray objects are. what is the comparison?
2) Every node also has an operation. As this can change at any time I
do the following:
Each node has all possible operations available. The operations being
used in any particular run are stored in a static c array of SELs at
init of the program (read in from a settings file using
NSDictionary). When the operation changes, I randomly select an index
from this array and store the SEL in the instance - again so that
only minimal processing is needed to select the operation to be
performed. Again, the evaluation call is time critical so the idea of
storing SELs as strings instead would not be so good.
In the emails I received from my posting, three options were
mentioned apart from NSString (which would be slow): NSInvocation,
NSNumber / NSValue and IMPs. I have no idea what IMPs are. Which does
everyone think is best for the job? Am I right to keep the c array as
SELs
3) As I mentioned, when an entity 'wins' an evaluation (by getting
the lowest score), a new population has to be generated based on
mutations of this winner. Throwing away the population and
re-generating it is far too slow so I want to read the configuration
of each node - operation and inputs - wrap it all up in something and
post it to all the other entities in the population so they may read
it and adjust themselves as needed. The inputs I can do easily - each
node has an index and so each node simply asks the nodes it is using
as inputs what index they are and wraps that info up in an
NSArray.The operation each node performs, however, was the real
problem I emailed about.
Why use an NSArray of NSArrays? Because in future, nodes may not have
the same number of inputs and I wanted to code a design where the
entity itself did not need to care about what config info each node
had, only the number of nodes.
Well, that's it :)
Sorry for the huge email !
Any ideas on any part of this, answers, suggestions etc very very welcome :)
Robert
--
Please note the new email address:
email@hidden