Fitness-proportionate selection (FPS) gives fitter candidate solutions a greater chance of being chosen without making selection deterministic. In a genetic algorithm, it can choose parents for crossover and mutation or help decide which individuals survive into the next generation. It also guides artificial bee colony (ABC) search toward higher-quality food sources. Unlike elitism, which preserves top performers, FPS still gives less-fit candidates a chance. section 7.3.3 section 10.5 section 7.3.5
Roulette wheel selection turns fitness values into a random draw:
- Add the fitness values of all N candidates to obtain total fitness F. section 7.3.3
- Give candidate k probability pₖ = f(xₖ) / F, then add probabilities in order to form cumulative probabilities qₖ. section 7.3.3
- Draw r uniformly from [0, 1] and choose the first candidate whose cumulative probability reaches r. Repeat for further selections. section 7.3.3
Five ticket prices
Suppose five pricing candidates have fitness values 8,820, 84,420, 90,000, 128,500, and 18,000. Their total is 329,740. The fourth candidate receives the largest selection probability, about 0.39, but is not guaranteed to win. With the candidates in that order, a draw of 0.25 selects the second; a draw of 0.58 selects the fourth. For implementation, calculate cumulative values from the unrounded probabilities rather than adding displayed rounded figures. section 7.3.3
Table 7.5 Cumulative probabilities (view table figure)
| Candidate solutions x |
Values of x in the solution space |
Candidate solutions in the binary coding space |
Objective function f(x) |
Selection probability pk |
Cumulative probability qk |
|---|---|---|---|---|---|
| x1 |
77 |
01001101 |
8,820 |
0.03 |
0.03 |
| x2 |
203 |
11001011 |
84,420 |
0.26 |
0.28 |
| x3 |
110 |
01101110 |
90,000 |
0.27 |
0.56 |
| x4 |
145 |
10010001 |
128,500 |
0.39 |
0.95 |
| x5 |
230 |
11100110 |
18,000 |
0.05 |
1.00 |
Compare each candidate’s fitness-derived probability with its cumulative cutoff to see where a random draw lands. section 7.3.3
Parent selection and survivor selection answer different questions. Parent selection decides which existing candidates generate offspring. Survivor selection forms the next population from existing individuals and new offspring; FPS can use fitness to favor retention or use inverse fitness when deciding whom to delete or replace. Keeping the best individuals while allowing other candidates to remain helps balance strong solutions against population diversity. section 7.3.3 section 7.3.5
For a minimization problem, first make sure the value used as selection fitness rewards better solutions. In the ABC Rosenbrock example, smaller objective values are converted into larger selection fitness values before probabilities are calculated. One candidate with objective value 15.15 receives fitness about 0.062 and selection probability 0.49. Onlooker bees consequently explore better food sources more often, while scout bees can search new regions when a source stops improving. section 10.5
Table 10.3 Solution fitness calculations (view table figure)
| Candidate solution Xm |
Objective function fm(Xm) |
Fitness fitm(Xm) |
Probability of selection pm |
|---|---|---|---|
| X1 = (–1.04,0.11) |
98.56 |
0.010 |
0.08 |
| X2 = (–1.10,–0.10) |
174.02 |
0.006 |
0.04 |
| X3 = (–0.75,0.22) |
15.15 |
0.062 |
0.49 |
| X4 = (–1.10,0.29) |
88.87 |
0.011 |
0.09 |
| X5 = (–0.86,0.10) |
43.76 |
0.022 |
0.18 |
| X6 = (–1.00,0.26) |
59.66 |
0.016 |
0.13 |
Shows why objective value and selection fitness must be distinguished in the minimization example. section 10.5
