I believe premature convergence happens when your population stops improving, i.e., the best individual has the same values during multiple generations. So, if your algorithm was running for 30 generation and it stopped improved by generation 20, it is a case of premature convergence, if you know that there are better solutions for the problem.

In the case you don't know the best solution to the problem, the only solution is to run the algorithm multiple times with different parameters and see the behavior of the population.

It doesn't make sense to invent terns, such as ``premature convergence'', that don't mean anything. The fact that the algorithm converges at all, i.e. that the objective function attains a minimum, is significant-the value of the function at the minimum isn't.

Hi All,

I'm not agree with Stam Nicolis the premature convergence vocabulary does exist and realy a premature convergence in evolutionary algorithm means convergence of algorithm before global optimum solution is reached.

For answering your question i suggest you to see links and attached files on topic.

Predicting Convergence Time for Genetic Algorithms - Semantic Scholar

https://pdfs.semanticscholar.org/.../83a620ac37a725b4248a4cf3f3...

Fluid Genetic Algorithm (FGA) - ScienceDirect

https://www.sciencedirect.com/science/article/.../S22884300163004...

Discovery of Classification Rules Using Distributed Genetic Algorithm

https://www.sciencedirect.com/science/article/pii/.../pdf?...

Improving Genetic Algorithm with Fine-Tuned Crossover and Scaled ...

https://www.hindawi.com/journals/jmath/2016/4015845/

Best regards

I believe premature convergence happens when your population stops improving, i.e., the best individual has the same values during multiple generations. So, if your algorithm was running for 30 generation and it stopped improved by generation 20, it is a case of premature convergence, if you know that there are better solutions for the problem.

In the case you don't know the best solution to the problem, the only solution is to run the algorithm multiple times with different parameters and see the behavior of the population.

Once more: convergence, if the minimum isn't reached simply doesn't make sense!!

If I were you I'd use a deterministic global optimization solver from the family of global optimization methods. Maybe it will take a while, but you would most probably do get a global optimum. In any case, why not give it a try?

Thanks Michael for your response.

Actually the problem is of combinatorial type where pedestrians are supposed to choose certain paths from the sets of paths between different origins and destinations so as to minimize the overall pedestrian delay in the network. Moreover, it is a is mixed integer nonlinear problem, so some of the deterministic techniques are not really suitable for this kind of problem.

I tried branch and bound method and it gave me the solution. But it only works for very small networks. It cannot solve the problem in finite time when the network size becomes large.

Therefore, I tried to use a stochastic global search algorithm so that I can get an approximate solution in finite time.

Do you know the known optimal value for the problem? If yes, try some other configurations of GA or simply try a completely different method to get another "set" of values. Convergence at the non-global optima means that area your algorithm converged is probably located around a large plateau and you probably need a way of dealing with that. May be you should improve the diversification behaviour of your algorithm.

Muhammad: there are graph decomposition methods that might work for you - transfer decomposition comes to mind, although I have only read about it and never worked on it myself. The method guarantees thet you find an optimal solution, but there is no guarantee how long it takes, of course - this is the nature of these problems - it is in general NP-complete. I tought the theory on this stuff in the mid 90-s. :-)

It does rely on you having a truly optimizing tool to solve the sub- and master problems. As these problems are hard in a complexity sense, there is no way that you can hope for a very quick convergence, but you have the advantage of having upper and lower bounds on the optimal value along the way, which means that you can terminate the search when you have a feasible solution that has an objective value not very far away from the value of the subproblem.

Go for it!

Article The equivalence of transfer and generalized benders decompos...

I think here "premature convergence" should actually be stated as finding a local minimum instead of the global. Unfortunately that could happen, as of today there is no optimization approach that guarantees to find the global minimum for any problem, not even at a theoretical level. Specific tools and problems work better or worse (as per the "there is no free lunch" theory), so if you have information about the problem and the expected results then you can use the appropriate approach to improve performance.

Regarding the genetic algorithm, you can play with the settings, and here are some ideas:

You can trade off convergence (how fast it locates on a minimum) with exploration (how well it covers the parameter space). Getting stuck into local minima is mainly due to not exploring enough of the design space or one individual dominating the population (eg the grouping you described) The most obvious of these is to increase the population size, so you sample more, which not surprisingly increases computation cost. When you have a constrained problem (I assume you have) then you can change the constraint treatment from "death penalty"/hard approach to some penalty function, which also helps exploration near the constraint boundaries.

Regarding the domination problem, you can change the fitness scaling method. If some individuals have very high fitness compared to the rest, then using a rank based scaling, to avoid domination. On the other hand, if there are many high fitness solutions of similar magnitude, then using the raw fitness score is better than rank. Running the problem and inspecting the population a few times should show you which case you are looking at. Also reducing the crossover ratio, and the elite count will encourage mutation, eg exploration, but reduces convergence. Elitism should be kept though, as without that you are likely to lose your best individual and never achieve convergence.

You can also change the mutation. Give it a larger deviation, and a lower shrink rate, and the solutions will be mutated more, eg more exploration, and due to the reduced shrink, it will stay at higher rate even at later generations.

Also you can change the stopping criteria, so it takes more generations to accept a converged solution, obviously at a price of slowing (or preventing) convergence.

As I mentioned because there is no way to guarantee the finding of global extrema, it is a good idea, to run multiple iterations of the process, with different starting populations and/or settings, to increase the certainty that what you find is the global optimum. Inspecting the populations and getting more insight on the problem can give you advice how to further tune your process for the specific application and increase the chance of success.

The question seems very well described and some good answers were already written. You should first select the best set of parameters for your specific optimization problem, in order to avoid premature convergence to local optima, for example by adapting the number of population members and number of generations, and increasing the mutation rate. I do not know the specific program that you are using - I wrote always my own optimization programs - but I am assuming that it is well developed and that you are (or can) using it correctly.

I studied the performance and convergence of a SA algorithm that I developed, in the paper

https://www.researchgate.net/publication/235418729_Optimal_Layout_of_Sewer_Systems_A_Deterministic_versus_a_Stochastic_Model

The convergence/performance (in terms of first results) of a multi-objective (two-objective) optimization model using a simple (i.e. with binary code) GA that I also devised and programed is mentioned in the paper

https://www.researchgate.net/publication/319528457_An_effective_and_comprehensive_model_for_optimal_rehabilitation_of_separate_sanitary_sewer_systems

I agree with David Sziroczak that the problem may be addressed by increasing the diversity in the population, by favoring more exploration over exploitation. To add to some of the methods proposed here, you can implement a random restart (with increasing population size) once there is no improvement after some point [1], or you can partition the population in a way that the diversity of solutions is also encouraged (and not only their fitness) [2]. Below are papers that adopt these strategies:

[1] A. Auger and N. Hansen, “A restart CMA evolution strategy with increasing population size,” in Proc. IEEE CEC, 2005, pp. 1769–1776.

[2] J. A. Vrugt, B. A. Robinson, and J. Hyman, “Self-Adaptive Multimethod Search for Global Optimization in Real-Parameter Spaces,” IEEE Trans. Evol. Comput., vol. 13, no. 2, pp. 243–259, 2009.

David Sziroczak appears to have skipped linear programming (LP) class, as there are methods for that problem that are guaranteed to stop with a guaranteed optimal solution, and moreover there is a polynomially bounded time and space complexity to get there, and confirm it. What did you learn in school?

The No Free Lunch Theorem considers a large class of problems that are much more complex than LP, but that's beside the point here; the point is that you are wrong in saying that there is no method for any problem, 'cause that is just pure baloney.

To iterate, take a look at the continuous knapsack problem, the shortest path problem, the linear assignment problem, and the minimum spanning tree problem - all of them are solvable in a complexity in time and space that is a very low-order polynomial. Please buy a good mathematical optimization, and read it. I can give you hints from the several hundred books I have in my office.

Dear Michael Patriksson , first of all I think the tone you are setting is not acceptable in a professional environment.

Second, read the question again please, based on the description it is a nonlinear problem, being solved with a genetic algorithm in Matlab. So the answer is related to how the genetic optimizer works and can be tuned. If you know a method that guarantees to find global solutions for this specific problem, and is available, it would be helpful to recommend it as an answer to the question. Saying that there are problems where there is guaranteed global optimum is not too much help toward solving this specific one.

Third, read again what I was writing, there is no universal optimizer method that guarantees global minima for an arbitrary problem you put in front of it. As you very insightfully noted, there are specific classes of problems and specific solvers, where there is guarantee/proof. However, as of today, there is no practical or theoretical proof that if you select any problem you want in the world (so not one specific class) there exist a suitable method that guarantees the global optimum. If you are aware of such theory, I would be interested in hearing about it.

Genetic algorithms and simulated annealing algorithms if suitably conceived, programmed and applied for a given optimization problem can be regarded as stochastic searching algorithms that can reach the global optimal solution with a given probability, which normally increases with the number of total evaluations in each individual computer run and with the total number of separated program executions. See the PhD Thesis (in Portuguese) fully available in the link below and the two papers that I mentioned before

https://www.researchgate.net/publication/271847229_Optimizacao_Tridimensional_de_Sistemas_Urbanos_de_Drenagem

Thanks Mohamed, I do agree that the term premature convergence does exist and is a real issue in the implementation of stochastic global search algorithms.

Dear David, I did keep Elitism. Regarding crossover and mutation, the MATLAB's genetic algorithm implementation overrides any custom crossover and mutation functions (as far as what I have understood from its documentation). Yes, I did run the multiple iterations hoping that I can find the global optimum or a good approximation to global optimum. The statement about guaranteed optimum of of any problem was a little confusing for me in your first answer. Thank you for clarifying it in your second answer.

Dear Antonio, I am using the MATLAB's genetic algorithm implementation. Regarding your latest answer, it is an interesting piece of information. I conducted separate execution of the program several times so that the probability of reaching the global optimum solution becomes high.

Dear Michael, thanks for recommending the transfer decomposition method. I will look into it.

I tried to change the population size as well as max number of generations. As it is an MINLP, therefore, MATLAB's genetic algorithm minimizes a penalty function. As soon as it finds a feasible solution, it does not really converge until the maximum number of generations is reached. I have attached a screenshot here (in this case only 850 generations are shown, I ran the algorithm for many generations but it didn't really converge and stopped when maximum number of generations exceeded.)

I am thankful for everyone's answers. I hope it will be helpful for other researchers too.

Congratulations for having followed my suggestions and, according to your words, attained the desired success in your optimization problem.

Please refer to the first paper that I mentioned in my first answer. With SA, I made 20 series of 100 computer runs (total of 2000 runs with low to moderate individual computer execution times), and the global optimal solution was reached in one problem in 1385 times, i.e. with an individual probability 69.25% of the runs, and in another more complex search, 779 times, with probability 38.95%. As we all know, the probability of a given event, with an individual probability, p, occur after n independent consecutive trials is given by 1- (1-p)^n. So after 10 isolated computer runs, for example, it is estimated that the global optimal solution will be found (at least one time) with a probability of 99.999% in the first instance of the problem and 99.28% in the second case. You can see the paper for more details.

One simple way to get rid of premature convergence while working with GA is that Keep Stopping Criterion TIGHT. I mean to say the following:

1) Tolerance limit should be very small (all three, function, constraint and variable)

2) Stall generation very high.

Hope it will solve you problem.

One more thing, you can get the same solution at each run if you use the following command at the beginning of each run:

rng('default')

Other parameters should be selected appropriately, they are really very important to give you better result. You have a look at the following article in which I have used five different meta-heuristics including GA.

Article A comparative study of metaheuristic optimization approaches...