Tips to avoid genetic algorithms premature convergence

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

Answer 1

[Alan Weiss]

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

[Kilin]

Hi Alan, thanks for the reply.

You are right, I meant "Generation", and I've set that to 100, not 10, it was a typo. I don't have constraints except for the upper and lower bounds.

Thanks for your advices, a few comments: 1) I thought the creation function was in charge of this! What do you suggest? 2) For my problem 1 fitness evaluation requires almost 1 minute of computation, so to have reasonable simulation times I have to keep population size or max generations as low as possible. I set things in order to have something like 3 days of simulation on a workstation where I'm able to open a pool of ~10 parallel workers. Given the time limit, maybe it is better to have less generations and a bigger population? What do you suggest?

3) I'll take a look to patternsearch, thanks for the advice

Thank you very much for your advices,

Kilin

[huilong yu]

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]

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