I am looking to extend my functions with iterations and conditions. The algorithms I am thinking to generates would use both of them.
I can only appreciate how challenging it can be. Has anybody overcame this with genetic Improvement or hyper-heuristics.
Hi Patricia,
There's been surprisingly little work in this area, given how common loops and conditional statements are in programs written by humans.
In early work, there's Koza's DU (do ... until) function, with an action branch and a condition branch. I think this is covered in one of his books. Bill Langdon also did a lot of early work in this area, considering more constrained iterative forms such as forwhile loops with an explicit loop variable. See his thesis:
http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_thesis.html
More recently, there's been a resurgence of interest in the context of evolved image processing programs. For example:
http://goanna.cs.rmit.edu.au/~vc/papers/aust-ai04.pdf
A notable issue with using loops is how to make sure that the loop body completes, since there is no way of doing this analytically in the general case (i.e. the halting problem). The solution usually involves constraining the form of the loop, so that it can not iterate indefinitely, or placing time constraints on its execution, followed by a fitness penalty for exceeding this limit.
An alternative is to change the representation into something that more naturally exhibits dynamical behaviour, such as work on using gene regulatory networks to represent programs. For example, my work (though there are plenty of other examples):
https://www.researchgate.net/publication/256576400_Artificial_Biochemical_Networks_Evolving_Dynamical_Systems_to_Control_Dynamical_Systems
Hope this answers your question. I would be interested to see how you might apply hyper-heuristics to the problem.
Michael
Article Artificial Biochemical Networks: Evolving Dynamical Systems ...
Hi Patricia,
There's been surprisingly little work in this area, given how common loops and conditional statements are in programs written by humans.
In early work, there's Koza's DU (do ... until) function, with an action branch and a condition branch. I think this is covered in one of his books. Bill Langdon also did a lot of early work in this area, considering more constrained iterative forms such as forwhile loops with an explicit loop variable. See his thesis:
http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/langdon_thesis.html
More recently, there's been a resurgence of interest in the context of evolved image processing programs. For example:
http://goanna.cs.rmit.edu.au/~vc/papers/aust-ai04.pdf
A notable issue with using loops is how to make sure that the loop body completes, since there is no way of doing this analytically in the general case (i.e. the halting problem). The solution usually involves constraining the form of the loop, so that it can not iterate indefinitely, or placing time constraints on its execution, followed by a fitness penalty for exceeding this limit.
An alternative is to change the representation into something that more naturally exhibits dynamical behaviour, such as work on using gene regulatory networks to represent programs. For example, my work (though there are plenty of other examples):
https://www.researchgate.net/publication/256576400_Artificial_Biochemical_Networks_Evolving_Dynamical_Systems_to_Control_Dynamical_Systems
Hope this answers your question. I would be interested to see how you might apply hyper-heuristics to the problem.
Michael
Article Artificial Biochemical Networks: Evolving Dynamical Systems ...
On conditions in GP specifically, this product which I use a lot, Eurequa, provides an implementation of if/then/else. http://www.nutonian.com/products/eureqa/
Jim
Koza's function sets often contained iflte -- a four arg arithmetic conditional: if A is less than or equal to B, then C, else D.
An alternative to explicit loops would be to use map and/or reduce, as in functional languages. Making collections (such as lists) a basic data type leads to evolved programs which can operate on collections of data.
Look into the work by Ashlock on If Skip Action Lists. It is an alternative representation for genetic programming. They are described in chapter 12 of Evolutionary Computation for Modeling and Optimization, Springer, 2006. I have used the in a few projects and they will create loop structures.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Artificial Intelligence