Genetic Algorithm not returning best found solution

TL;DR: ga is returning a random solution and cost (Fval) for my given problem, even when there are better feasible solutions in multiple generations of the algorithm (as depicted by the progression plot and the latest generation in ga's output).

---

I am working with non-constrained, bounded, mixed-integral genetic algorithm. My implementation of the ga optimization function runs successfully, and on its progress-plot (seen below) I can see ga progression towards a local minimum. For instance, here, on the plot, one can see a "best penalty value" of around .189 (I've removed the datatip for clarity), while the latest generation penalty value is .359. However, the Fval (functional cost value) for the minimal solution returned by ga() is 0.4953, far worse than the other costs.

This is not (as far as I can tell) due to an infeasible solution, though I know that can happen with interger constraints, as ga is finding better values even with an infeasibility penalty (see here and here for documentation). I'm also not just worried about ga not finding a global minimum--I know that a genetic algorithm is not guaranteed to converge to the global minimum.

From the documentation for ga, I gathered that the returned solution "X" is the best genome found by the algorithm (see highlighted source here), not just best genome of the population making up the final generation. However, even if my assumption was wrong, the output scores of the final generation still do not equate to the returned Fval. I sincerely cannot understand where the Fval is coming from, nor how X is not the minimum genome found.

---

I've recreated my code as best as I can replicate it, though there is a lot happening in the background with object creation and simulation that is not represented in this snippet. Because I've replaced my background simulation with random number generators, the ga algorithm is very random in the example, but it still exhibits the behavior that I'm wondering about. The Fval returned is .6152, while I can see multiple genomes that were below 0.2.

lb = [4, ones(1, 10), ones(1, 6), zeros(1, 10), zeros(1, 10)];
ub = [10, 10*ones(1, 10), 4*ones(1, 6), ones(1, 10), ones(1, 10)];
intcon = 1:17;

options = optimoptions( 'ga', 'PopulationSize', 30, ...
        'FunctionTolerance', 0.01, 'PlotFcn', {@gaplotbestf, @gaplotrange},...
        'MaxGenerations',200, 'MaxStallGenerations', 20); 

[Result.X, Result.Fval, Result.GAexitflag, Result.GAoutput, Result.GApopulation, Result.GAscores] = ...
    ga(@(X)obj_fun(X), length(lb), [], [], [], [], lb, ub,[],intcon, options);

Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance
and constraint violation is less than options.ConstraintTolerance.

disp(Result.Fval)

    0.6152

%% Cost functions (I don't think these influence ga, but included them for completeness
function [cost] = obj_fun(X) % original has more inputs
    % These come from a pathfinding simulation, I've replaced them with a
    % random function for now
    sensor_cost = randi(130) + 5;
    path_cost = randi(300) + 40;
    
    max_sensor = 138.8; %From another function, I've hardcoded it here
    best_path = 40;     %ditto
   
    cost = totalCost(sensor_cost, path_cost, max_sensor, best_path);
end

function [cost] = totalCost(sensor_cost, path_cost, max_sensor, best_path)
    %Normalizes the inputs and returns a score from 0-1.5, lower is better
    norm_sensor_cost = sensor_cost / max_sensor;
    if path_cost == Inf
        norm_path_cost = 2;
    else
        norm_path_cost = (1 - best_path / path_cost);
    end
    cost = (norm_sensor_cost + norm_path_cost) / 2;
end

Thank you for your help!

Answer 1

[Star Strider]

I do not entirely understand what your ‘obj_fun’ fitness function optimises, however expecting ga to optimise 37 parameters in 200 generations is likely a bit optimistic. Give it more generations and it will likely converge on a much better parameter set.

[Fifteen12]

That's good info for genetic algorithms. It doesn't quite answer my questions about about ga and the random Fval returns. From my view ga has converged on several better parameters than what it's returning to me, is there something else I should be looking at?

obj_fun returns a cost based on a back end simulation that I didn't include here (instead replacing them with random number generators), but which is based on the genome. We have a fairly limited integer bound for most of the genome which limits our possible permutations. I don't think the objective functions have much to do with the strange behavior I'm experiencing, but I wanted to include them in case wiser eyes than mine saw something I didn't.

[Star Strider]

I have no idea what you’re optimising, so I can’t comment specifically on it. However, ga is characteristically random, so it may not converge on the same parameter set each time. I usually run ga several times, saving the final results, and then choose the best of the saved results. (There is no absolute certainty that ga will find the global minimum in any particular run, however that probability increases significantly over several runs.)

It is always possible to use a hybrid function that will use a gradient descent approach to ‘fine tune’ the ga results after ga converges. I occasionally use that approach. It’s listed among the options.

Also, I thank you for clearing up the random number calls. Used in any optimisation function call, they create a ‘moving target’ that makes convergence impossible.

I stil usggest that allowing at least 1000 generations, and perhaps 5000 will increase the probability that ga will converge on an optimal set of parameters.

If you are doing any sort of parameter estimation fitting a function to data, it may very well be that 37 parameters are too many to adequately fit the data. An underdetermined system (more parameters than data) will never converge.

[Fifteen12]

Thanks Star Strider for the extended response. While I agree with you that ga isn't going to return a global minimum, my problem is not with the algorithm converging, but with ga not returning the best value it found during its search. In my example (which is admittedly a little confusing), ga returns a solution and Fval that are clearly sub-optimal to many other genomes in the final population as well as others from earlier generations. Am I misunderstanding how ga chooses what solution to return?

[Star Strider]

My pleasure!

The ga function should return the best value it found. As I understand, it retains that individual. The ‘fval’ value is the fitness of the best individual. The best individual is the individual with the lowest fitness value that also conforms to the constraints.

[Fifteen12]

That is my understanding too, and the root of my question. As it appears to me, ga is not returning the lowest fitness value, but some arbitrary value not related to any individual apparent to me. From the progression plots shown in my example, to the last generation, I find many individuals with lower optimal scores than the one returned. Am I encountering a bug?

The only constraints imposed are general boundary constraints and integer constraints, all of which conform to ga's specification (linked in the question). As stated in the docs, using just integer constraints will not result in penalty additions unless I have a custom mutation or cross-linking function (I do not, only the objective function as supplied).

[Star Strider]

Apparently, I don’t understand your problem well enough (or for that matter, at all). I’ve never had any problems with ga, although most of my experience with it has been in nonlinear regression or similar problems, where it has shown itself quite capable of finding the global minimum.

Also, I characteristically use:

'PlotFcn',@gaplotbestf, 'PlotInterval',1

to track the fitness values during optimisation, not penalty values, let it run to 5000 generations if it needs to, and:

'HybridFcn',@fmincon

to do a gradient descent optimisation at the end.

Then again, I’ve never had a problem that required 37 parameters. My problems generally require about half that many, including optimising the initial conditions for an ode15s integration of a system of differential equations describing the compartmental or chemical kinetics of a process, the initial conditions generally being about a third of the total parameter space.

.

[Fifteen12]

Thanks for extended help to a complicated question. I'm going to keep this question open and see if someone might be able to answer it, I'd love to learn that I'm just misinterpreting the output. I'll try @fmincon and see if that helps, but as we're not dealing with any quite of surface (no equality/inequality/nonlinear constraints beyond value bounds) I don't think it will yield results--but you never know!

[Star Strider]

The problem you’re solving is as yet undefined from my perspective. I have no idea even what sort of problem it is, other than it optimises 37 parameters and ga is only given 200 generations to converge on a solution.

[Fifteen12]

I may have been unclear. I'm going to go ahead and post a new question and try to clarify. Thanks again for all your help.

[Fifteen12]

In writing up the second question I may have answered this one. I'm guessing that ga calls the obj_fun for the optimal genome before returning it, not just the optimal genome found. So the random cost function in my example is randomizing the Fval on the return. I'll have to look at my actual objective function and figure out which parts of are not deterministic.

[Torsten]

The MATLAB optimizers are suited for deterministic optimization. Your problem as it is formulated seems to be a stochastic optimization problem.

And the fact that you don't use the vector X of optimization parameters in the objective function seems more than strange.

[Fifteen12]

You're right Torsten, again, I was using randi in this example, my obj_fun is a complex simulation (this is an optimization of an optimization problem) that constructs multiple objects before completion. But I think I out thought myself--the random assignment in the object function (again, used as a placeholder here) is causing the strange output.

[Star Strider]

I thought the random number generators weren’t being used in the actual code. I mentioned the problem with using them in an earlier Comment. If you’re actually using them in the code, then it will quite simply never converge.

[Fifteen12]

They're not, they're a placeholder for a more complex simulation. However, within that simulation there is some nondeterministic behavior that I think is causing the problem.

[Fifteen12]

The code is an attempt to configure the properties of a robot involved in a pathfinding mission. Here the genome represents the properties of the robot, while the cost function is how well the robot did at pathfinding. The pathfinding simulation involves some noise, which is nondeterministic. I think ga is calling the objective function (which runs a new pathfinding simulation with the inputted genome) every generation for the "best found so far" genome. The noise in the simulation is then inpacting the returned score.

[Star Strider]

I appreciate the explanation.

At least now I understand the essence of the problem, if not the problem itself.

Answer 2

[Alex Sha]

Taking my experience, GA is not an efficient and ideal global optimization algorithm, in lots of cases, GA like random reserach which giving different results each running.

[Fifteen12]

Thanks Alex Sha, though I appreciate the opinion, my question is not about whether or not to use a genetic algorithm (or if its deterministic), but on the specific functionality of the ga function. I'm not using GA to find a global optimum, but to explore a variety of configurations within a prescribed simulation, somethine genetic algorithms excel at.