| Date | May 2022 | Marks available | 6 | Reference code | 22M.3.HL.TZ0.3 |
| Level | HL | Paper | 3 | Time zone | no time zone |
| Command term | Compare and contrast | Question number | 3 | Adapted from | N/A |
Question
Refer to the Paper 3 Case study: Genetic algorithms, available under the "Your tests" tab > supplemental materials.
Two selection methods used in genetic algorithms are:
- roulette wheel
- truncation.
Compare and contrast these two selection methods.
Markscheme
Award [6 max]
Roulette Wheel Selection (RWS)
Award [1 max]
Solutions are mapped to a roulette wheel / occupying space that is proportional to their fitness;
Better solutions have a greater probability of being selected / Worse solutions have a lower probability of being selected;
Truncation
Award [1 max]
The best / top N solutions are selected (for entry into the mating pool)/The worst / other solutions are not selected (for entry into the mating pool);
The number chosen for N (truncation point) affects the speed of convergence;
Comparison
Award [4 max]
Both solutions rank/sort the solutions from best to worst OR truncation must be sorted but RWS can be implemented without sorting (e.g. rejection sampling);
Thus, the chosen sorting algorithm OR approach affects the solution time (because it is done every cycle);
In truncation, weakest solutions will never be chosen/only strongest solutions can be chosen;
Whereas in RWS every solution has a chance of being selected/even the worst solution has a chance of being selected;
In truncation, once selected the top N solutions have a probability equal to that of any of the other top N solution (e.g. best and 4th best have an equal chance of being selected);
whereas in RWS proportionality is used so the top N percent are differentiated (e.g. best has a high chance of being selected than 4th best);
RWS is more likely to preserve diversity than truncation;
Because roulette wheel is more likely to avoid local minima than truncation;
Both truncation and roulette wheel make their selections based on fitness scores;
So need to consider the processing required to calculate fitness;
Both methods work well with large populations;
So if population diversity is necessary they are good choices/should not be chosen if population sizes are small;
Examiners report
Most candidates could define the two selection methods. As stated above, many did not compare the two methods. Instead, many students treated the two selection methods independently. Despite this, nearly all candidates gained at least two marks.
