When Should the Algorithm Be Stopped

<< Click to Display Table of Contents >>

Navigation:  Chapter 6 - Programming Your Genetic Algorithms Using the DLL >

When Should the Algorithm Be Stopped

Previous pageReturn to chapter overviewNext page

There is no direct indication in the genetic algorithm that the process has converged to the best solution.  This is also true for iterative methods.  The idea is to continuously test the quality of the solution.  We can determine the value of the highest fitness with the help of the FindBest function, and calculate the mean fitness of the population by calling the CalcMeanFitness function.  Of course, we could also just “remember” the best fitness in the code, since it is the code that is returning the fitness to GALIB32.DLL.  Note that these functions should be called after calculating the fitnesses, and before the Reproduce function is called to create a new generation for which the previously calculated fitnesses are meaningless.


To determine the best point at which to stop the genetic algorithm, we should compare the best fitness since the start of the evolution with the best one reached in the current generation.  If the best fitness for the current generation does not exceed the previous best fitness for a number of generations (typically 20-200), then the best solution has probably been reached.  The number of required generations is dependent on the complexity of the problem.  It is larger for harder tasks.  Remember to store the values of the chromosomes for the best individual in your program.


It is also very informative to draw graphs of the best fitness in the current population, the best fitness since the start of evolution, and the average current population fitness, all versus the generation number.  The graphs can help you detect that a stationary level has been reached and therefore evolution may be stopped.


Note:  It is important to set the mutation rate to a reasonable level.  If the rate is set too high, the genetic algorithm may never reach a fixed state.


After many generations, the population may consist of very similar individuals with equal fitnesses.  This situation is detected by the Reproduce function, which then returns a special error code (equal-fitnesses - Error Number 12).  Equal fitnesses do not harm the algorithm.  When the fitnesses are equal, you must terminate the algorithm because no further progress is possible.  Remember that a high mutation rate or a larger population may prevent this state from occurring.