• ''premature convergence'' in evolutionary algorithm means convergence of algorithm before global optimum solution is reached. Normally, when any evolutionary algorithm is trapped into local minima we term it as premature convergence.
• You may find the publication (link given below) very useful;
• https://www.researchgate.net/publication/280244004_A_comparative_study_of_metaheuristic_optimization_approaches_for_directional_overcurrent_relays_coordination

Article A comparative study of metaheuristic optimization approaches...

Dear Yenugula,

The following explanation is from Wikipedia:

"In genetic algorithms, the term of premature convergence means that a population for an optimization problem converged too early, resulting in being suboptimal.

In this context, the parental solutions, through the aid of genetic operators, are not able to generate offsprings that are superior to their parents.

Premature convergence can happen in case of loss of genetic variation (every individual in the population is identical)."

There are various strategies for preventing premature convergence as listed below:

Strategies to regain genetic variation can be;

• a mating strategy called incest prevention,
• uniform crossover,
• favored replacement of similar individuals (preselection or crowding),
• segmentation of individuals of similar fitness (fitness sharing),
• increasing population size.

Best wishes,

normally the solution which converges at global best will have a very less value of standard deviation. premature convergence means the solution is stuck within the local minima or local maxima. hence the std deviation will be high in the case of premature convergence.

Premature convergence simply means that a population for an optimization problem converged too early, resulting in a suboptimal fitness/objective function.  , premature convergence can be avoided by maintaining diversity in the population. .

premature convergence: is to converge in a very early stage (in few generation) to a local optimum and get  stagnated there.

standard deviation: The answer no it doesn't ! 

How can we detect weither an algo suffer from a premature convergence or not:

if the algo converge in a small number of generation to a local optimal.

When the evolutionary algorithm stuck into local minima or local maxima and cannot come out from that state for certain period, we refer this situation as a premature convergence. This situation arise due to loss of diversity among individuals of the population. One of the technique to avoid premature convergence is to maintain diversity among individuals of the population throughout the execution (run) of evolutionary algorithm. The other techniques for preventing premature convergence are: using archive and designing efficient crossover operators.

Issue of premature convergence related to Genetic Programming is discussed in detail in the following reference. Moreover, it also discusses different approaches to overcome the issue with their relative advantages and drawbacks.

Vipul K. Dabhi, Sanjay Chaudhary, "Empirical modeling using genetic programming: a survey of issues and approaches", Natural Computing (NACO), Springer, Volume 14, No. 2, pp. 1-28, Online ISSN 1572-9796, 2014.

Article Empirical Modeling using Genetic Programming: A Survey of Is...

Evalutionary Algorithms are based on evolving / generating new species (offsprings) that constitute a new set of population or group of individuals. In this process, when the new species are not much different (diversified) to their parents , in other words, their fitness is not improving, then it is said to be stuck in premature convergence  where all the population gets accumulated near a single point. It can be local minim or local maxima depending on the algorithm and evalutionary process.

The only solution is to make sure that the evolutionary process generates diversified offsprings.

Maintaining Diversity in Population of Evolved Models

https://www.researchgate.net/profile/Jan_Drchal/publication/223999339_Maintaining_Diversity_in_Population_of_Evolved_Models/links/09e414fb264184a5f8000000.pdf

Conference Paper Maintaining Diversity in Population of Evolved Models

Premature convergence simply means the algorithm thought it was finished, but it wasn't. As noted above there are a number of causes, but here are two more.

1. The algorithm's exit condition is met, but the point is not optimal. For example, convergence might be very slow and a test for a change in successive points detects very little change. This problem can also be caused by poor scaling.

2. Because you are using a computer, it is possible that the problem is not well-conditioned and, because of that, some value has gone to zero, causing the algorithm to conclude it is done.

Note that ending up at a local minimum (if minimizing) is not premature convergence if the exit condition is met. For example, because Newton's method looks for zeroes of the gradient, it can converge to points that have zero gradient values, but are not minimums. In such a case the algorithm has converged to a point in its solution set and convergence is not premature.

If the problem is premature convergence, it may be possible to adjust the algorithm or numerical values to converge properly. However, if the algorithm properly converges to a point that is in its solution set, but is not the optimal solution, then the only fix is to pick a different starting point.

Hi, 

All the posts above explain very well what is an early convergence.  To prevent the algorithm being stuck in a local optima, it is worth in my opinion to consider these techniques. 

1) It is useful to replace the parents with parents with equivalent fitness. It can help the search pointing somewhere else.

2) The mutation and crossover disturb not appropriately the parents. As a result, it cannot find better optima. 

3) the parameters needs optimised. Use a meta-heuristics to do so. It has been well documented. 

4) More dramatically use an hyper-heuristics to generate new algorithms. The discovery phase should prevent this situation occuring, in my experience.

I hope it helps.

Patricia 

 Hi, 

In my opinion, premature convergence because of lack of diversity, maintaining diversity is the solution for convergence too early.

The question is: How to maintain diversity in the population? 

See the attached file (A comparative review of approaches to prevent premature

convergence in GA).

I hope it will help you.

Best wishes,

Amani

Premature convergence' is typically caused by loss of diversity

Diversity:  measure of the amount variety, i.e. number of different solutions in the population, and how different they are (distance between alternative solutions)

Loss of diversity: after the population converges, it becomes very uniform (all solutions resemble the best one).

Causes:

too strong selective pressure towards best solution

too much exploitation of existing building blocks from current population (e.g. by recombining them, or mutating them only slightly)

Premature convergence = algorithm reports to have found the optimum, even though it has not.

Population size of metaheuristics affect their performances in the following ways:

1. small population size with large iteration cannot explore the whole search space effectively but can exploit some small area of search space by doing local search effectively and thus local minimum is likely (premature convergence problem).

2. large population size with small iteration can explore the whole search space effectively but cannot exploit  various areas of the search space effectively and thus local minimum is again likely (stagnation problem).

Therefore, in both the situation the algorithm cannot perform well. So, a balance between population size and maximum iteration is very important to get satisfactory performance by any metaheuristic algorithm.

Also, testing of various parameters of the algorithm is highly recommended before final run.

Mahamad, from my experience I would disagree with your point 1 and 2. I would be interested though to see the references to these statements. 

When working with various types of EAs  (including Lamarckian and evolving ones), premature convergence was prevented by using two parents and two offsprings. The replacement strategy implement a hill-climber. Having more parents did not improve the results at all. 

If you think in CGP, the mu and lambda of an ES is very small too. No crossover is used. No premature convergence occurs. 

I have experienced this with EAs I have written myself, published ones as well as machined-discovered ones. 

I would recommend Yenugula to research the best parameters in terms of parents, offsprings, crossover and mutation rates. A meta-heuristic or softward by optimisation approach could find out the best parametrisation to Yenugula's needs.

Patricia 

See this paper

Multi-Objective Optimization Algorithm Based on Sperm Fertilization Procedure (MOSFP)

http://www.mdpi.com/2073-8994/9/10/241

Diversity of solutions via

* Position of the Optimal Solution in the search space: If the local minima are in hollows such that you must move from one depth and out to another steep for a minimization problem.

* Choice of Learning Rate: The choice of learning rate could be a cause of premature convergence. A larger learning rate may miss the point of convergence - leading to an over shooting.

The premature convergence of a genetic algorithm arises when the population for an optimization problem converged too early. In order to avoid this situation, the following link may be helpful in this context:

http://bmif.unde.ro/docs/20091/12NICOARA_SIMONA.pdf