[Push] Opcode Propagation & Crossover

[Lee Spector]

Hi Rud,

Yes, I think it makes perfect sense that you're seeing a decrease in diversity over time since you have no mutation and since the combined effects of selection and crossover will increase the number of occurrences of instructions from the better programs. I would also note that the program size limit of 20 and the population size of 200 are both rather low, especially if you have a large instruction set (as is common in Push). It's hard to know exactly what these parameters should be but you should think about the likelihood of getting two important instructions anywhere in the same program, etc. For what it's worth I often start by trying a program size limit of 100 and population size 1000, but I usually end up going significantly higher on population sized for any real problem. (For example I'm currently doing a run with population size 100,000. One needs a nice machine and/or efficient code to do this.)

There is indeed some literature on versions of crossover that are more restrictive, or that attempt to force "homologous" recombination. Some of the ideas in the literature may translate well enough to Push, since Push programs are still nested lists... Some related work has also been done on linear genomes... Perhaps a fusion of these ideas would work well in Push? I'm not sure, but I think it'd be worth exploring. You can find some of the related literature by searching for "homologous" at http://liinwww.ira.uka.de/bibliography/Ai/genetic.programming.html

 -Lee


On May 8, 2010, at 10:31 PM, Rud Merriam wrote:

> I did run with over 2000 generations with a maximum points of 20. There was no mutation because I was trying to isolate a problem (which turns out to be due to something wrong in my mutation processing). The population size is 200.
> 
> It appeared that the set of opcodes appearing in the programs was getting smaller. Originally the program were diverse but now there were programs that had repetitions of opcodes.
> 
> When I see things like this I wish I were more conversant with the literature and not just playing with Push because I find it interesting. Perhaps this is a known effect. But I decided to think it through.
> 
> Say you start with the two program (A B) and (C D). When crossover is performed it is 50% whether A or B is chosen and 50% whether C or D is chosen. So there is a 25% chance, to get specific, that B will replace C during crossover. Assume that happens. Now perform crossover on (A B) and (B D) in the next generation. Now there is 25% chance of D being replaced by B. That looks to me like what is happening in my run of many generations. It is beyond my math ability to determine how this works with much larger programs, more diversity, etc. But it seems to suggest that larger populations with short generational runs would be more successful. Which is what Lee has implied recently in emails.
> 
> This makes me question how I have implemented crossover. As illustrated above I am allowing B to replace either C or D. Similarly A can replace C or D. Perhaps A should only be able to replace C, and B replace D? I am thinking about the illustration of biological crossover which occurs at the same point in both genes. Perhaps in GP or Push, at least, the crossover point should be at a similar point? For instance, if one program is 20 points long and the crossover is at 15, a point 3/4 of the way in the other individual should be selected?
> 
> I've looked at some interesting GP websites but they illustrate it using S-expressions which are not directly translatable to Push, leaving me a bit uncertain at times on how to proceed.
> 
>   
>  - 73 - 
> Rud Merriam K5RUD
> http://mysticlakesoftware.com/
> 
> _______________________________________________
> Push mailing list
> Push at lists.hampshire.edu
> https://lists.hampshire.edu/mailman/listinfo/push

--
Lee Spector, Professor of Computer Science
School of Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspector at hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438

Check out Genetic Programming and Evolvable Machines:
http://www.springer.com/10710 - http://gpemjournal.blogspot.com/