Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I have a working genetic algorithm which uses a few genetic operators on pairs of individuals.

These two individuals are selected by fitness-proportional (roulette-wheel) selection, that is, an individual's likelihood of being selected is proportional to its fitness.

The way a pair is selected is simply by selecting a single individual from the population twice. Sometimes, the same chromosome can be selected twice, and then all genetic operators are simply operating on two copies of the same individual.

For example, crossover is meaningless in this case.

My question is, should I take measures to ensure the pair that are selected are not equal?

Or should I mitigate the problem by performing operators on single individuals first (such as mutation), so the pair are more likely to be different when it comes to things like crossover?

Or should I ignore the problem completely, "let nature take its course", and allow an individual to breed with itself?

share|improve this question
add comment

2 Answers 2

The usual course is to feign ignorance and let it happen.

However, it is generally bad, so you'd ideally take steps to make it less likely to happen. The brute force solution is of course to simply check for equality and reselect one of the parents if necessary. You can do this, but there's a decent chance that if all you do is throw away the duplicates, the overhead of checking every time may start to limit the returns you get.

Another way to minimize these effects is to use a selection operator that is less biased. Roulette-wheel selection has a very high probability of selecting from only the handful of best individuals in many cases (depends on the particular distribution of fitness values of course). You're probably better off starting off with tournament selection as your default choice. It will give you a wider coverage of the parent pool, which keeps more diversity around for longer. Also, you can tweak the knobs a bit by looking at how you do environment selection (replacing old parents by some combination of old parents and new offspring). The more strongly elitist you are, the faster you'll converge, which you usually want to avoid.

One of the best black-box GAs out there is CHC (Eshelman, 1990) (always be wary of black boxes, but if you're going to treat the method as one, CHC seems to be one of the more effective ones). CHC is worth looking at, partly because it is a pretty good search algorithm, and partly because it provides a window into the types of things you can do to a standard GA to try and exert a bit more control over what it's doing.

CHC takes a very odd approach. It pairs parents completely randomly and without replacement. This means that every parent is selected exactly once (recombination produces two offspring, so each parent is selected as part of one mating pair giving N/2 pairs * 2 offspring/pair = N offspring). Crossover is "HUX" or half-uniform crossover, which produces offspring maximally distant from their parents. Combined, these give a very explorative search. In addition though, it is maximally elitist. Of the N parents and N offspring, the best N of the total are kept. This drives convergence very quickly -- very exploitative. Finally, parents produce no offspring at all if they are closer than a threshold value to one another. The threshold starts at L/4 (L=length of encoding), and is decremented each time zero offspring are produced in a generation. Thus the number of offspring produced in each generation is variable, and this number is used to determine how much the population has converged. At some point, when it has converged sufficiently (when the threshold reaches zero), CHC performs a "cataclysmic mutation" in which all but one individual have 35% of their bits randomly flipped and the process restarts.

Unfortunately the original paper describing CHC is only available in dead-tree form as far as I know. However, you can find a few descriptions online and in other papers that reference it.

share|improve this answer
add comment

Having crossover between the same individual can lead to local optima where only that individual will stay in the population. However, this is not always the case, it is best to test each of your ideas to your own problem :)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.