How does the ga in matlab give exitflag 1 before reaching the stall generation limit ?

How does the ga in matlab throw an exitflag 1 before reaching the stall generation limit of 50 ? It throws exitflag 1 even if I set total generations less than 50.

I would sincerely appreciate your response this question.

Thanks,

[Geoff Hayes]

Mandar - what is your line of code and options that you are providing to the ga function?

[Mandar]

Hi Geoff, I specific both the max number of iterations and function tolerance in my options for ga.

I use the the following code:

options = gaoptimset('PlotFcns',@gaplotbestf,'InitialPopulation',upper_ini,'PopInitRange',[upper_lb;upper_ub],'ParetoFraction',0.35,'CrossoverFraction',0.8,'DistanceMeasureFcn',{@distancecrowding,'genotype'},'TolFun',1e-3, 'Gen', 5);

Thank you for your response.

[Geoff Hayes]

Hi Mandar - so how many generations have occurred when MATLAB exits from the ga function with the exit flag of 1? Is it 5, because that is what you have set in the options as 'Gen',5? If it is, then this makes sense because I would think that this limit of 5 would be enforced over the stall limit of 50.

[Mandar]

Hi Geoff,

In the documentation, exitflag 1 is described as "— Average cumulative change in value of the fitness function over StallGenLimit generations is less than TolFun, and the constraint violation is less than TolCon."

In my problem, I set the StallGenLimit = 50 and Total Generation = 5; the solver still shows exitflag 1.

I am not sure how it shows exitflag 1 even if I set total generations less than stall generation limit.

[Geoff Hayes]

That's true for without non-linear constraints, but "with nonlinear constraints" states that an exit flag of one will be returned if the 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.

Have you supplied non-linear constraints? Are you using MATLAB 2014a or some other version?

[Mandar]

I am using MATLAB R2012a.

I do not have any non-linear constraints in my problem. So, it should not be using the constraint tolerance (TolCon) for convergence or for exiting the algorithm.

[Geoff Hayes]

Do you have the documentation for 2012a with respect to the exit flag of the ga function? Perhaps it has changed in the newer releases…

For example, at Global Optimization Toolbox Release Notes, the Genetic Algorithm changes for R2014a includes the comment

ga now stops when the average relative change in best fitness value over StallGenLimit generations is less than the TolFun tolerance. Previously, the stopping criterion was a weighted average relative change, where the weighting factor was (1/2)n for the nth prior iteration. This change usually causes ga to take more iterations. The new StallTest option, with default value 'totalChange', controls the stopping criterion. Set StallTest to 'geometricWeighted' to recover the previous behavior.

Though when I look at the ga exitflag documentation for R2012a Global Optimization Toolbox and the equivalent for 2014a, the descriptions are the same.

You may want to contact The MathWorks support concerning this question.

Answer 1

[Alan Weiss]

I don't understand how you are seeing what you report. My reading of the GA code shows that it should give an exit flag of 0 when it hits a generation limit that is smaller than the stall generation limit.

Perhaps you can post your exact options call, your exact call to GA, and the exact exit message.

Alan Weiss

MATLAB mathematical toolbox documentation

[Mandar]

Hi Alan, Geoff,

I think I understand to some extent my mistake with using the ga options.

Even though I have no constraints in my problem, I was using an empty constraint function in my options. For example,

[x,fval, exitflag,output] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,@sim_const,options)

and I was defining the my constraint function as an empty set, function [c, ceq] = sim_const(x)

c = []; ceq = [];

So, exitflag 1 from documentation:

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.

My question now is, since I specify empty set in the constraints function, which criterion does the solver use for showing exitflag 1.

Also, I am not sure if I understand what the documentation means by "the subproblem is solved using a tolerance less than TolFun".

I would appreciate your response on this issue.

Thanks,

[Alan Weiss]

If you want help, please post your exact options call, your exact call to GA, and the exact exit message. And then ask a question about the exact output that you find confusing.

Alan Weiss

MATLAB mathematical toolbox documentation

[Mandar]

Below is my exact code,

options = gaoptimset('PlotFcns',{@gaplotbestf,@gaplotmaxconstr},'Display','iter','Generations', 5,'StallGenLimit',[],'TolFun',1e-3);

ObjectiveFunction = @simple_fitness;

nvars = 2; % Number of variables LB = [0 0]; % Lower bound UB = [1 13]; % Upper bound

ConstraintFunction = @sim_const;

[x,fval, exitflag,output] = ga(ObjectiveFunction,nvars,[],[],[],[],LB,UB,ConstraintFunction,options)

%% Constraint Function

function [c, ceq] = sim_const(x) c = []; ceq = [];

%% Fitness Function

function y = simple_fitness(x)

y = 100 * (x(1)^2 - x(2)) ^2 + (1 - x(1))^2;

%% Results

                           Best       max        Stall
Generation  f-count        f(x)     constraint  Generations
    1         140      0.635724            0      0
    2         260      0.635724            0      1
Optimization terminated: average change in the fitness value less than options.TolFun and constraint violation is less than options.TolCon.

exitflag =

     1

output =

      problemtype: 'nonlinearconstr'
         rngstate: [1x1 struct]
      generations: 2
        funccount: 260
          message: [1x140 char]
    maxconstraint: 0

%%

My question here is about interpreting exitflag 1 for ga problem type 'nonlinearconstr' when the constraint function is an empty set.

When I read the documentation for exitflag 1 for 'nonlinearconstr' problems, it says,

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.

Since my constraint function is an empty set (options.TolCon = []), which criteria is the solver using to stop the optimization process ?

If the solver is using "average change in the fitness value less than options.TolFun" as the stopping criterion,

how is the "average change" calculated (and over how many generations) ?

Answer 2

[Alan Weiss]

Thank you for posting the options, GA call, and returned info.

As you realize, having a nonlinear constraint function, even one that returns all empty, changes the GA algorithm and exit conditions. And having an all-empty return for the nonlinear constraint makes it behave in hard-to-understand ways. For example, when GA internally compares the magnitude of the constraint function, it is comparing [] to some value such as TolCon. What is the result of that comparison? Say you try

 3 <= 5

 ans =

     1

 [] <= 5

 ans =

     []

So, in the end, I have to say that it is not clear to me what happens internally when GA makes these comparisons.

It seems to me that the question you are asking is "What happens if I give GA an unexpected function?" And my answer is "I guess it does unexpected things."

Sorry, I really don't know any more than that. Sorry for the long answer to a short question.

Alan Weiss

MATLAB mathematical toolbox documentation

[Mandar]

Hi Alan, Thanks for your response.

Do you know what the documentation means by:

 "the subproblem is solved using a tolerance less than TolFun".

This is from the explanation of exitflag 1 for 'nonlinearconstr' problems.

"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."

[Alan Weiss]

The subproblem is described here. In addition to the formulas, the relevant portion of the documentation is:

The genetic algorithm minimizes a sequence of subproblems, each of which is an approximation of the original problem. Each subproblem has a fixed value of λ, s, and ρ. When the subproblem is minimized to a required accuracy and satisfies feasibility conditions, the Lagrangian estimates are updated. Otherwise, the penalty parameter is increased by a penalty factor (PenaltyFactor). This results in a new subproblem formulation and minimization problem. These steps are repeated until the stopping criteria are met.

I hope that this is clear. Remember, TolFun operates as a stopping criterion for GA as follows:

Function tolerance (TolFun) — The algorithm stops if the average relative change in the best fitness function value over Stall generations is less than or equal to Function tolerance.

Alan Weiss

MATLAB mathematical toolbox documentation