Tips to avoid genetic algorithms premature convergence

24 views (last 30 days)
Hello,
I am using MATLAB's Genetic Algorithms for an optimization problem. The genome is composed by 24 genes, the problem is bounded, and the only ga options I've changed are:
populationSize = 400;
crossoverFraction = 0.65;
EliteCount = 4;
maxGenerations = 100; % corrected typo, was 10 in the original post, sorry :-)
StalLGenLimit = 30
MutationFcn = @mutationadaptfeasible
CreationFcn = @gacreationlinearfeasible
The rest is not set so it should be default.
I get quite good results, but I suspect that the algorithm is prematurely converging. The plot of the best fitness quickly reaches a plateau after few (say, 10 - 15) iterations, and from the score plot I can see that altough I have a quite high mutationFraction (1-crossoverFraction) the population diversity quickly vanishes. I have to say that my problem is not so trivial, and it is possible that random mutation very often leads to individuals with very bad fitness.
What I would like to ask you is: do you have suggestions in order to improve the convergence, preferably using the tools at disposals with MATLAB? Any suggestion will be highly appreciated!
Thank you guys,
Best regards

Answers (1)

Alan Weiss
Alan Weiss on 16 Sep 2014
Edited: Alan Weiss on 16 Sep 2014
There is no option maxGenerations. Perhaps you mean Generations. If you set Generations to 10, then you should never have more than 10 iterations. So you are ensuring too-rapid convergence with this option.
Do you have nonlinear constraints? If so, each iteration is, in fact, many function evaluations, and the intermediate calculations do not appear in iterative display or plot functions. So what might appear to be too-rapid convergence is, in fact, normal with nonlinear constraints, because you don't see the intermediate evaluations.
I have three specific recommendations to avoid premature convergence:
  1. Give a well-distributed initial population. You can give a partial population.
  2. Set a much higher population size. Maybe 10 times higher. This can cause the initial population to take a long time when using the gacreationlinearfeasible creation function. But you need that function only when you have linear constraints. Do you? If you have only bound constraints, and you find that initial population creation is too time-consuming, then I suggest that you do not set this creation function.
  3. The best advice I can give, and one I hope you take seriously, is to forgo GA and instead try patternsearch. For an initial point, assuming you have finite bounds on all components, repeatedly try
x0 = lb + rand(size(lb)).*(ub - lb)
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation
  3 Comments
huilong yu
huilong yu on 6 Jan 2017
Dear, Alan, I'm currently using the 'gamultiobj' to find a Pareto solution for a defined multiobjective problem. I set the initial popolation as 1000 with linear constraints and found that it takes too long time using 'gacreationlinearfeasible' to create the initial populations, would you like to give me some suggestions? Thank you!
Alan Weiss
Alan Weiss on 10 Jan 2017
In the future, I suggest that you start a new topic rather than adding onto an existing topic (I nearly didn't see this question).
I suggest that you make a custom initial population. Give your bounds and linear constraints to linprog, and use a random objective function vector f where n is the number of variables:
f = randn(n,1);
f = f/norm(f);
Solve the linear programming problem with this f for 1000 different f values, and use the resulting population (collected as a matrix, where each row of the matrix is one solution vector) as the initial point for gamultiobj.
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation

Sign in to comment.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!