# Genetic Algorithm not returning best found solution

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

---

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

##### 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

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!