Hi,
I am doing a GA problem. I have done most of it, but am unsure how to code the roulette wheel selector. I have already figured out the fitness of each chromosome and the fitness ratios.
I am unsure how to code my program so it randomly selects the parent chromosomes based on the fitness ratios. Any help is appreciated.
If you need to see source code I will post it.
Could you explain in more detail what the algorithm you require needs to do. Not all of us are GA experts
but many of us can provide solutions/algotihms if we know the context.
What does the roulette wheel selector need to do? What is the form and format of the data on which it
operates? stuff like that.
matfud
Usually GA works something like this:
* Order the parents by their fitness, either linearly (just a list) or by the scale of the fitness (occupies as much probabilty space as it's fitness).
* For as many children you need to create do:
- Choose any 2 parents - the higher fitness the higher probability they are chosen.
- Take a random part (or half) of the chromosones from 1 parent, the rest from the other parent.
- Further change the chromosones by eventual mutation (usually not too big possibility)
For choosing a random parent as described above, these 2 solutions works, whereof the first is a simpler/quicker version:
- Order the parents by their fitness, 0..n-1. Choose the parent by some logarithmic scale or some other algorithm that gives higher probabolity to the parent with the highest probability.
- Order the parents by their fitness, 0..n-1. In order from the parent with least fitness do: Give each parent the weight of their fitness + the weight of the previous parent (w=fitness+w[i-1]). Put them in a binary tree. SUM the fittness of all parents (SUM). When choosing parent; just find the parent with the weight >= Random(SUM) (equal or closest above a random number). Hence each parent has the probability to be chosen by it's fitness.
Gil
if this is for a class... fair enough...
however, if you are seriously doing this for GOOD answers, then i personally suggest you forgo using the roulette selection at all.
with roulette selection, the most fit solutions become more and more common... often at the expense of diversity in the final population. after all, if you keep choosing only the "most fit" you may end up with a solution stuck in "local optima"
better ways to use a "fitness" estimate are found in either the SPEA-II or NSGA-II algoirthms. they both also include measures of dispersion... to ensure that your solutions are spread in objective space.
hope this helps.