Ranking algorithms

[Shaggy Hiker]

In writing a GA, there has to be some means of determining the parentage for the next generation. The probability of mating has to favor those who performed better for evolution to occur.

I have a GA where the quality of a genome will range from 1 to 10,000 (or more, but leave it at that for now).

One ranking technique would be to add up the quality of each individual, then determine the percent of the total quality that each individual contributed. This becomes their chance of reproducing. However, with the enormous range of qualities, this would mean that bad ones would have NO chance of reproducing. If there were only one or two really good ones, the population would bottleneck within a few generations.

Another alternative, and one that I am using, would be to sort the individuals by quality. If there are 50 individuals in the population, then the best one would get 50 chances, the next best would get 49, the next 48, and so on.

There are two problems with that approach: 1) The top ten all have about the same probability, though the difference between the best and median is fairly big. This means that there is only a small reward for superior performance. 2) The total number of chances = (n(n+1)/2), which means that there are 5,050 for a population of 100. With todays memory, that's not so bad, but it is fairly inefficient.

Can anybody suggest a third alternative ranking system that rewards success more than my current one without running into the problem that a few really good individuals would prevent the rest of the population from having any meaningful contribution?

[wossname]

How about diversity? You could give extra points for an individual's divertisy from a given state.

Good orchid breeders never throw the ugly ones away!

Do you use any special algorithm for selection by weight or are you using a standard one?

[Shaggy Hiker]

It must be special, because I came up with it all on my own. If there is a standard, I don't know what it is.

As for diversity, I do have a function that compares the best genome with the others in the population, and increases the rate of mutation as diversity drops.

[Shaggy Hiker]

Here's what I have settled on for now:

If there are N members in the population, and they are ranked from 0 to N where R is the rank of an individual, then each one gets:

Chances(C) = (N-R)+((N-R)\(R+2))

Thus of sumC total chances, the best gets 1.5N. The next gets 1.3333N, etc. This gives every individual some chance, but weights the likelihood towards the top few. I'll see how it works out. There are many ways to modify this (like using R+3 in place of R+2 to give the lower individuals a greater chance.