Implementing crossover in genetic programming [closed]

Question

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!

Gunther

I strongly recommend having a look at Essentials of Metaheuristics. It's available for free (if you fill out a form) and it contains an overview of a broad spectrum of metaheuristic techniques including genetic programming, crossover operators, steady-state model, etc. – Kilter

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...

Fordone

Answer 2

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.

Cochineal

Answer 3

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.

Aleshia

Answer 4

Check out MetaOptimize.com for your stacky needs.

Menstruate

Answer 5

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).

Scrappy

Answer 6

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.

Checkup

Answer 7

I would create an unlimited number of offspring, but only on the basis of success, and let older members of the population die. Lack of fitness can also lead to early death. This just seems to follow a natural order.

Canaster

Answer 8

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?

Yes its your choice; but generally, its not advisable to create many individuals with the same parents, because the difference among the individual's trends created by the same parents would be very limited and that could cost processing speed and memory which could have been spent on other individuals showing different trends and behaviors that requires analysis (but creating more individuals cannot be a problem if the evolution process is close to reaching its endpoint).

Q2. In steady state GP...

It is advisable to replace individuals based on the ranking provided by the fitness function you have adopted.

Mennonite