Implementing crossover in genetic programming

Question

Hi,

I'm writing a genetic programming (GP) system (in C but that's a minor detail). I've read a lot of the literature (Koza, Poli, Langdon, Banzhaf, Brameier, et al) but there are some implementation details I've never seen explained. For example:

I'm using a steady state population rather than a generational approach, primarily to use all of the computer's memory rather than reserve half for the interim population.

Q1. In GP, as opposed to GA, when you perform crossover you select two parents but do you create one child or two, or is that a free choice you have?

Q2. In steady state GP, as opposed to a generational system, what members of the population do the children created by crossover replace? This is what I haven't seen discussed. Is it the two parents, or is it two other, randomly-selected members? I can understand if it's the latter, and that you might use negative tournament selection to choose members to replace, but would that not create premature convergence? (After a crossover event the population contains the two original parents plus two children of those parents, and two other random members get removed. Elitism is inherent.)

Q3. Is there a Web forum or mailing list focused on GP? Oddly I haven't found one. Yahoo's GP group is used almost exclusively for announcements, the Poli/Langdon Field Guide forum is almost silent, and GP discussions on general/game programming sites like gamedev.net are very basic.

Thanks for any help you can provide!

Answer 1

Firstly, relax.

There are no "correct" methods in GP. GP is more art than science. Try lots of schemes and pick the ones that work best.

Q1: 1, 2, or many. You choose.

Q2: Replace, 1, 2, all. Or try some elitism.

Q3: You probably won't find forums discussing these questions b/c there are no right/best answers. Sorry.

PS. In my research, crossover never really performed well...

Answer 2

1. As Ray, says, it's mostly up to you but typically in a steady-state setup you would only create a single offspring.

2. Again you have options. I wouldn't replace the parents. If they've been picked as parents based on their fitness you could be eliminating some of the fittest members of the population. Easiest is just to randomly pick an individual to be replaced. Alternatively, you could replace the least fit individual, but that can lead to premature convergence. Another option is to use the same selection strategy that you use to choose parents but use the inverse fitness so that it favours less fit individuals.

3. You could try comp.ai.genetic on USENET (and Google Groups).

Answer 3

If you can read Python, you may want to take a look at Pyevolve. I am mainly involved in it on the GA side, but it has support for GP as well. May be you can get some hint there.

Answer 4

Thanks all, those are useful and encouraging comments.

(Coincidentally, Python is on my list of things to learn...)

Answer 5

It sounds like some of your questions are not necessarily specific to genetic programming; if that's true, you might have some luck asking the folks over at the NEAT Users Group.

They primarily discuss the Neuroevolution of Augmenting Topologies (or NEAT) algorithm, which is a genetic algorithm used to evolve neural networks. But topics like elitism and crossover strategies are pretty general, and can apply to both GA and GP algorithms.

Otherwise, as Dan and Ray have said, a lot of these decisions are made after experimentation with one's particular software and domain. Try applying your algorithm to different problems and pay attention to how it behaves -- after a while, you'll probably develop an intuition for what works and what doesn't.

Answer 6

Q1 is your choice, but single child would probably be more common. Every time you do the lottery selection of parents, you're applying selection pressure, which is what you want.

Q2: Negative tournament selection is exactly the right approach. Yes, losing low-fitness members of the population causes rapid convergence initially, but once your population gets into the hard-to-search part of the solution space, it won't be as cut-and-dried which ones lose the tournament / lottery. What you do have to beware of is stagnation of the gene pool; I suggest monitoring the entropy of the genome to track its heterogeneity. "elitism is inherent" -- Well, yeah, that's the point! ;-)

Q3: comp.ai.genetic is probably your best bet. Sometimes the topic is picked up in game development fora, like on Gamasutra.

P.S. Genetic programming in C?!? How are you assuring the viability of the offspring? Doing genetic programming in a non-homoiconic language is a real challenge.

Answer 7

Larry, thanks for the reply. Creating one child and having it replace a random member looks pretty clear now. I think I was trying to cram all the main GA as well as GP techniques into one approach and finding it a bit much.

I'm not evolving C code by the way, that's just what I'm writing the GP system in.

Answer 8

Check out MetaOptimize.com for your stacky needs.