Measure of population diversity in Genetic Algorithms

by Amit


Population diversity is a desirable characteristic in a Genetic Algorithm(GA). What it basically implies is that the search space should be well represented. This gives the GA a chance to search for all the possible solutions uniformly. Premature convergence often results in poor or sub-optimal GA performance.

GA literature most often talks about population diversity in a qualitative manner. However, a quantitative measure is sometimes needed, if not for anything else, but for own satisfaction that a population is indeed able to maintain its diversity or sometimes to explain premature convergence, in which the population loses its diversity before it has found all the solutions. In my current research work, I needed such a metric which would give an idea of diversity of the population and give me an idea when there is a premature convergence versus a proper one. I shall now summarize a couple of the efforts that I have found very intuitive: (There may  be more; I found couple more but I haven’t yet found them intuitive and/or explored them fully )

  • Leung et.al, in their work Degree of population diversity-a perspective on premature convergence in genetic algorithms and its markov chain analysis defines a metric, \lambda(x) to define a diversity metric, considering the GA population as a matrix. Unfortunately, by its very definition, the metric is only applicable to a Binary coded GA.
  • Morrison and De Jong in their work Measurement of Population Diversity proposes a novel measure of diversity. Their idea is derived from the concepts of centroid and moment of inertia of a rotating object. They define the moment of inertia of a GA population about its centroid. The larger the value of the moment of inertia, the diverse the population. This comes from the definition itself. This is of course applicable to a real coded GA and hence more useful and widely applicable.

Illustrative plot:

To illustrate the point, the following is a plot showing the variations of the moment of inertia for a population, in the case of a good convergence(RED) and in case of a bad convergence (GREEN):

Illustrative plot showing the population diversity loss

Such a quantitative measure of population diversity, is also useful in setting the GA parameters such as crossover probability or mutation probability. For example, if we see that there is an unexpected convergence, increasing the mutation probability may be a good idea.

Hope you find this post useful!

    Advertisement