Measure of population diversity in Genetic Algorithms
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, 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.
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):
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!
I got to your blog from http://codebix.com which incidentally is a programming blog aggregator that I made. We’re trying to make it the place for the best progammer-writers. Do have a look.
If you found the website suitable, please do add it to your blogroll so that we may get some programmer-love that we are still missing.
[…] may also be interested to read my earlier post Measure of population diversity in Genetic Algorithms Possibly related posts: (automatically generated)2009 SES Boot CampCall for Papers: Brown […]
I’ve found this your post very interesting. I have several questions and I’ll be very pleased if you could answer on them, Where I can get your contacts?
I see a lot of interesting articles on your website.
You have to spend a lot of time writing, i know how to
save you a lot of work, there is a tool that creates readable, SEO friendly articles
in couple of seconds, just type in google – k2 unlimited content
I read a lot of interesting content here. Probably you spend
a lot of time writing, i know how to save you a lot of work,
there is an online tool that creates unique, SEO friendly articles in seconds, just type
in google – laranitas free content source