Genetic Algorithm not returning best found solution

67 views (last 30 days)
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!

Accepted Answer

Star Strider
Star Strider on 1 Dec 2022
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.
  16 Comments
Fifteen12
Fifteen12 on 3 Dec 2022
Edited: Fifteen12 on 3 Dec 2022
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
Star Strider on 3 Dec 2022
I appreciate the explanation.
At least now I understand the essence of the problem, if not the problem itself.

Sign in to comment.

More Answers (1)

Alex Sha
Alex Sha on 2 Dec 2022
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.
  1 Comment
Fifteen12
Fifteen12 on 2 Dec 2022
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.

Sign in to comment.

Products


Release

R2022b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!