Genetic Algorithm never runs past 15 iterations

I am trying to minimize a function with non-linear constraint. Search space is complicating and large so I would expect search to take some time, but no matter what settings/options I use my search always terminates under 15 iterations. Most of the time GA comes back with an answer but it's always subpar. How can I make it search longer?

Here is example of one of my calls...

[x,fval] = ga(@demo_power_mod,4,[],[],[],[],LB,UB,@demo_constraint_mod,gaoptimset('PopulationSize',100,'Display','iter')

Here is an output...

                           Best       max        Stall
Generation  f-count        f(x)     constraint  Generations
    1        5300   0.000452147     0.007359      0
    2       10500   0.000480009     0.007328      0
    3       15700   0.000514905     0.007293      0
    4       20900   0.000565675     0.007245      0
    5       26100   0.000636612     0.007183      0
    6       31300   0.000758782     0.007083      0
    7       36610     0.0115404   2.151e-007      0
    8       41810     0.0112147    0.0001978      0
    9       47010     0.0114633    2.46e-005      0
   10       52210     0.0114687    1.95e-005      0
   11       62310     0.0114617   2.078e-005      0
   12       72410     0.0114657    1.49e-005      0
   13       77610     0.0114722   1.366e-005      0
   14       87710     0.0126579            0      0
   15       92910     0.0115109            0      0
Optimization terminated: average change in the fitness value less than options.TolFun
 and constraint violation is less than options.TolCon.

[Star Strider]

I suggest adding to your gaoptimset call:

..., 'TolFun',1E-8, 'TolCon',1E-8)

or less to see if that improves your results. According to the gaoptimset documentation, the default for these options is 1E-6.

Answer 1

[Sean de Wolski]

[x,fval,exitflag] = ga(fitnessfcn,nvars,...)

What's the exitflag?

doc ga

to have exitflag explained.

[Vlad]

Here is my output...

x =

1.0e+004 *

    0.0014    0.0150    2.2177    0.5725

fval = 0.0121

exitflag = 1

[Sean de Wolski]

1 Without nonlinear constraints — Average cumulative change in value of the fitness function over StallGenLimit generations is less than TolFun, and the constraint violation is less than TolCon.

With nonlinear constraints — Magnitude of the complementarity measure (see Definitions) is less than sqrt(TolCon), the subproblem is solved using a tolerance less than TolFun, and the constraint violation is less than TolCon.

[Vlad]

Here is my understanding of stop condition for exit flag (1)...

Given following default condition: 'Stall generation' = 50, 'Function tolerance' = 1e-6, 'Nonlinear constraint tolerance' = 1e-6.

GA will stop only if: constraint violation is under 1e-6, and fitness function avg change is less than 1e-6 for 50 iterations.

15 iterations certainly does not satisfy that. So I must be setting something incorrectly.

Answer 2

[Alan Weiss]

The nonlinear constraints cause the algorithm to behave differently than you might expect. You see how high the F-counts are. There is a lot of computation happening at each iteration, and with nonlinear constraints, the stopping condition is not "weighted average change in fitness function over 50 iterations." See the nonlinear algorithm description.

And let me make my usual plea that you try using patternsearch instead of ga. You will probably find patternsearch to be faster, more reliable, and easier to tune. The only potential problem with patternsearch is that you need to give starting points. Since you have lower and upper bounds (and I assume that they are finite), you can try the following random start point:

 x0 = LB + rand(size(LB)).*(UB - LB);

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Vlad]

First, thanks for everyones response. You guys are very prompt.

Obviously I had a very simplified view on how non-linear constraints are applied. I thought it's just a secondary operation to weed out population that's deemed fit, but is not.

I am not as familiar with pattern search. GUI interface seems comparable to GA. I gave it a quick try with same function and constraint file and once again it terminated after 5 to 8 iterations. Exit flag says:

"Optimization terminated: mesh size less than options.TolMesh and constraint violation is less than options.TolCon."

In all of the answers fist two parameters vary answer to answer, but the last two always remain at min in my range.

I will read up on pattern search and perhaps figure out my problem