Genetic programming loops
I played around with genetic programming for a while and was starting to wonder how to implement loop constructs.
In the case for loops, I can imagine 3 parameters:
- start : start value of the counter
- end : the upper limit of the counter
- expression : expression to execute while counter < end
Now the tricky part is the expression because it generates the same value every iteration if no counter is entered into it . So I could let the counter character be present in expressions, but how can I prevent it from appearing outside of for loops?
Another problem is using the result of an expression. I might have a for loop that sums the results, another that multiplies them together, but it is limiting and doesn't seem right. I would like to get a general solution, not one for each operator.
Does anyone know of a good method for implementing loops in genetic programming?
source to share
Well, it's tricky. Genetic Programming (original Goat-style GP) is best suited for functional-style programming i.e. There is no internal execution state, and each node is a function that returns (and possibly accepts) values, like lisp. This is a problem when node is some kind of loop - it is not clear what node should return.
You could also design the loop node as a binary node. One parameter is a boolean expression that is called before each loop, and if true is returned, the loop will be executed. The second parameter will be the loop expression.
The problem you already mentioned is that there is no way to change the loop expression. You can solve this by introducing the concept of some internal state or variables. But that leaves you with other problems, such as the need to define the number of variables. A variable can be implemented for example. by a set of functions - a setter (one argument, no return value, or it can return an argument) and getter (no arguments, returns the value of a variable).
As far as the way to handle the processing of loop results, you can quickly go from GP to strongly typed GP or STGP. It is very important to use GP with types. Then your loop can effectively be a function that returns a list of values (like numbers), and you can have other functions that take such lists and calculate other values ...
There is another GP algorithm (my favorite) called Grammatical Evolution (or GE), which uses context-free grammar to generate programs. It can be used to encode type information as in STGP. You can also define the grammar so that you can create classic c-like for and while loops. Some extensions to it, such as Dynamicaly Defined Functions, can be used to dynamically inject variables.
If anything is unclear, just comment on the answer and I will try to clarify it.
source to share
The problem with zegkjan's answer is that there are several ways to dump a cat.
Theres actually a simpler and sometimes better solution for creating GP data structures than goat trees, using stacks instead.
This technique is called Stack Based Genetic Programming which is quite old (1993). This genetic programming technique removes trees completely, you have an instruction list and a data stack (where your functional and finite set remain the same). You iterate through the command list, push the values onto the data stack and pop the values to consume them, and pop the new value / values onto the stack, given your instruction. For example, consider the following genetic program.
0: PUSH TERMINAL X
1: PUSH TERMINAL X
2: MULTIPLY (A,B)
Iterating through this program will give you:
step1: DATASTACK X
step2: DATASTACK X, X
step3: DATASTACK X^2
After you have completed all the instructions in the program list, you simply pop the cardinality off the stack you care about (this way you can get multiple values from the GP program). This becomes a fast and extremely flexible method (memory, the number of parameters does not matter, and the number of items returned) you can implement quite quickly.
To loop around this method, you can create a separate stack, an executable stack, in which new special operators are used to push and pop multiple operators at the same time from the execution stack for later execution.
Alternatively, you can simply include a jump instruction to jump back into your program list, make a loop statement, or have separate information about holding the stack. Thanks to this, the genetic program could theoretically develop its own loop.
0: PUSH TERMINAL X
1: START_LOOP 2
2: PUSH TERMINAL X
3: MULTIPLY (A, B)
4: DECREMENT_LOOP_NOT_ZERO
step1: DATASTACK X
LOOPSTACK
step2: DATASTACK X
LOOPSTACK [1,2]
step3: DATASTACK X, X
LOOPSTACK [1,2]
step4: DATASTACK X^2
LOOPSTACK [1,2]
step5: DATASTACK X^2
LOOPSTACK [1,1]
step6: DATASTACK X^2, X
LOOPSTACK [1,1]
step7: DATASTACK X^3
LOOPSTACK [1,1]
step8: DATASTACK X^3
LOOPSTACK [1,0]
Note, however, that with either method it can be difficult for the GP program to actually develop a term that has a loop, and even if it does, its chances of such a mechanism leading to a poor health score at the start, probably removing it from population in any way. To address this type of problem (potentially good innovations that died out early due to poor early suitability), you will need to incorporate demes concepts into your genetic program to isolate genetically disparate populations.
source to share