Fenna has decided to use roulette wheel selection and cycle crossover (CX) for her genetic algorithm. She has two other important decisions to make:

• What values to assign to the variables when they are first initialized. These variables
  include population size, initial population routes, and mutation rate.
• What stopping criteria to use for the genetic algorithm.

Discuss the impact that these decisions may have on the success of the genetic algorithm.

Award [12 max].

Roulette wheel selection

• Effective with large-sized problems.
• Low fitness parents of the population have a chance for be selected.
• This is important in hill climbing/avoiding local minima.
• When a population contains only individuals with scores of large, nearly equal values, the selection probability of all individuals becomes nearly identical.
• Other types of selection may be more suitable for smaller search spaces.
• Prevents overly quick convergence.
• Populations must be sorted on every cycle.

Cyclic crossover (CX)

• Allows for two parents chromosomes/cities to be combined/preserved.
• And not be duplicated during crossover.
• Ensures diversity of chromosomes/cities from parents.
• Accelerates the search process in genetic algorithms.

Population size

• It is difficult to decide upon a population size.
• Too large a population will increase the likelihood of a near-optimal solutions but will increase the length of time to run through a generation.
• A large enough population may have enough diversity to arrive at a near-optimal solution without any mutation.
• Too small a population may mean that you may never arrive at a near-optimal solutions;
• Because there is not enough variation in the parents.
• This may require you to increase the mutation rate, which will add greater variation.
• But may also not arrive at a near-optimal solution.

Initial routes

• A random generation of cities would not be an optimal initial population.
• Some form of optimization of the initial population could be done.
• A scale map of the cities could be created and people attempt an optimal route by drawing the path between.
• These human attempts at the optimal solution could be used for the initial population.
• Along with some random routes to ensure variation.

Mutation rate

• Typical mutation rate is around 1%.
• A higher value will result in a more random population.
• Too high and the population will not evolve towards a near-optimal solution.
• Too low and there may not be enough diversity in the population to find a near-optimal solution.
• Mutation allows you to escape from local minima optimisation.

Stopping criterion

• A set number of iterations (generations). This could be based on run for 100 iterations or run for a set period of time. This solution would rely on chance for estimating the number of iterations required to ensure convergence.
• A set number of iterations (generations) when the best route does not change. For example, if after 100 generations the value doesn’t change for another 30 generations (i.e., 30%) then the algorithm stops. This would increase the likelihood of convergence.
• Set a target distance for the route and run the algorithm until that distance is reached.

Conclusion

• A final measured conclusion is included in which the candidate links together the various points in evaluating the probability of success.

Please see markband.

The extended response question always links relevant computer science with a question that requires students to discuss a specific aspect of the Case Study. This is communicated in the challenges section. In this case study, the question related to the first challenge which was to understand the role of convergence in genetic algorithms and the factors affecting convergence.

Many candidates produced excellent answers that demonstrated an understanding of how initial routes, population size, selection method, crossover method, and mutation affect convergence. Proficient answers critically analyzed the interplay between these choices and how they affected exploration and exploitation. Unlike previous case studies, there was no opportunity to reference real-world situations.

Some candidates failed to mention all the points outlined in the question. Some had misconceptions and made inaccurate points. A few candidates were not well prepared and wrote virtually nothing of any value.