Genetic Algorithm not returning best found solution
42 views (last 30 days)
Show older comments
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.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/1215863/image.png)
---
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);
disp(Result.Fval)
%% 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!
0 Comments
Accepted Answer
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
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.
More Answers (1)
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.
See Also
Categories
Find more on Genetic Algorithm in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!