Is there a bug in the genetic algorithm (ga) under certain conditions?

I discovered some abnormal behavior in the ga when I made changes.

The fitness function is evaluated far more times than I would expect when MaxGenerations is set to 10 an PopulationSize is 4. (I would expect roughly 40 or 44 calls).

Further, the output function is called many more times than 10. The generations roll back to 0 several times.

This is potentially an issue because the fitness function for my application (integer problem, binary elements only in solution, linear and nonlinear constraints, custom crossover and mutation) takes a long time to run and is the main bottleneck.

Here is a quick script that demonstrates the issue:

nVars = 3;
initialPopulation = [1,0,0;1,1,1;1,0,1;1,1,0];
A = [-1 0 0];
b = -1;
outputFunction = @OutputFunction;
fitnessFunction = @FitnessFunction;
nonlinfcn = @NonLinearConstraintFunction;
plotInterval = 1;
maxGenerations = 10;
maxTime = 60*60;
penaltyFactor = 100;
populationSize = 4;

opts = optimoptions('ga', ...
    'InitialPopulationMatrix', initialPopulation,...
    'OutputFcn', outputFunction,...
    'MaxGenerations', maxGenerations, ...
    'MaxTime', maxTime, ...
    'PenaltyFactor', penaltyFactor, ...
    'PlotInterval', plotInterval, ...
    'PopulationSize', populationSize, ...
    'PlotFcn',{@gaplotbestf,@gaplotscores,@gaplotscorediversity});


[x,fval,exitflag,output,population,scores] = ga(fitnessFunction, ...
    3, A, b, [], [], [], ...
    [], nonlinfcn, [], opts);

disp(genArray);
disp(funEvalArray);

function score = FitnessFunction(x)
    score = x*x';
end

function [state, options, optchanged] = OutputFunction(options,state,flag)
    optchanged = false;
    gen =  state.Generation;
    fitnessEvals = state.FunEval;
    disp('output called')
    disp(gen);
    disp(fitnessEvals);
end

function [c, ceq] = NonLinearConstraintFunction(x)
    c = 20 - sum(x.*x);
    ceq = [];
end

Answer 1

[Alan Weiss]

You have a nonlinear constraint function. This changes the algorithm quite a bit; see Nonlinear Constraint Solver Algoirithm. See also how many function evaluations occur in Nonlinear Constraints Using ga.

Alan Weiss

MATLAB mathematical toolbox documentation

[Doug Rank]

I have nonlinear constraints, but I am using custom crossover and mutation functions and I enforce the constraints within crossover and mutation. I also supply an initial population that was created and validated with the constraints.

Therefore, I think I do not need the nonlinear constraint solver portion. Is there a way to override it?

[Alan Weiss]

If your population cannot be infeasible with respect to the nonlinear constraints, then by all means do not include nonlinear constraints as part of your problem formulation. Leave nonlinfcn out of your ga call.

Alan Weiss

MATLAB mathematical toolbox documentation

[Doug Rank]

Thank you!

If I can ask your opinion: what do you think would be a good reason(s) to use custom crossover/mutation functions rather than the one(s) built into MATLAB?

[Alan Weiss]

In my opinion, there is very little reason to use ga as a solver except to handle integer constraints for nonlinear problems. For your problem, which you say has nonlinear and integer constraints, it might be worthwhile to use ga, though. Your custom mutation, crossover, and creation functions might be a good argument for ga in your application.

Maybe I didn't answer your question. My opinion is that ga is vastly overused, and most problems can be better handled differently. But for your case, knowing no problem details, I cannot say; maybe ga is the most appropriate solver.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Doug Rank]

Thanks!