Genetic algorithm only works with integer constraints..

8 views (last 30 days)
Hello.
I am solving a problem using GA, and while my problem formulation does not require to use integer constraints, I found out that using integer constraints is the only way to solve it - and I do not understand why.. I will explain below.
I have 20 optimization variables.
  • 9 of them represent switching times, formulated in a non-dimensional form, and bounded by [0 1],
  • one is the final time, bounded by [tf1 tf2]
  • other 10 variables represent angles, bounded by [0, 2pi]
If I do not introduce any integer constraints, and only use bounds for the optimization variables, then the GA window looks as below. Nothing changes on the plot, and there is no solution if I stop GA.
However, if I introduce integer constraints for the angles, then GA works very well for my problem:
To do this, I bound angles from 0 to 360 (achieving a 1 degree step), or from 0 to 720 (0.5deg step), and so on..
I learnt that no matter how I formulate this problem (different number of variables, times instead of switching times, etc.), this is always the pattern - a portion of the optimization variables have to be integer constrained. If not for angles, then using integer constraints for the times is also working (such that the time variable can take any value with a step of 1 second).
I would like to understand why this is the case. Ideally, I would like not to use integer constraints. Could it be that I need a better computer?
Thank you.
  17 Comments
Torsten
Torsten on 5 Oct 2022
Edited: Torsten on 5 Oct 2022
Shouldn't the "options" settings follow directly the nonlinear constraints function "nonlcon" if no integer constraints are involved ?
[xSol,fval,exitflag,OUTPUT_GA,POPULATION_FINAL,SCORES] = ga(@(x) fitness4(x), 20,[],[],[],[],lb,ub,@(x) nonlcon4(x),GA_opts);
instead of
[xSol,fval,exitflag,OUTPUT_GA,POPULATION_FINAL,SCORES] = ga(@(x) fitness4(x), 20,[],[],[],[],lb,ub,@(x) nonlcon4(x),[],GA_opts);
in your first two test cases ?
Yakov Bobrov
Yakov Bobrov on 5 Oct 2022
Yes, you are right. However, this did not change anything.
If I may comment on the ga plot that I shared above, it shows 20+ generation, but if I print OUTPUT_GA, I see that only 1 generation has passed...

Sign in to comment.

Answers (1)

Alan Weiss
Alan Weiss on 6 Oct 2022
Yakov, your report indicates that the nonlinearly-constrained problem is being solved in the usual way: having very few iterations, because most of the time is taken up with solving subproblem iterations.
For a similar plot in the documentation, see this link.
When you include integer constraints, the solver uses a different algorithm that shows many more iterations. For a simple demonstration of this effect, see the following simple example:
fun = @(x)log(1 + 100*(x(2) - x(1)^2)^2 + (1 - x(1))^2);
opts = optimoptions('ga',PlotFcn='gaplotbestf');
nvar = 2;
lb = [-2 -2];
ub = -lb;
sol1 = ga(fun,nvar,[],[],[],[],lb,ub,@nlcon,[],opts);
Optimization terminated: average change in the fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance.
sol2 = ga(fun,nvar,[],[],[],[],lb,ub,@nlcon,1,opts);
Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance.
function [c,ceq] = nlcon(x)
c = x(1)^2 + x(2)^2 - 1;
ceq = [];
end
Alan Weiss
MATLAB mathematical toolbox documentation
  2 Comments
Yakov Bobrov
Yakov Bobrov on 7 Oct 2022
@Alan Weiss thank you very much for explaining this. I understand now that I should allow much more time for each generation when not using integer constraints. However, the graph of mine that you have shared, it was for the case when I supplied GA with an initial population. If I allow it to be random, then I observe the following.
At generation 0, the fitness value is displayed as negative, even though when I pause the simulation and compute the fitness value, it is a reasonable positive value. Do you understand why this could be hapenning?
For the next generations, fitness value is positive, but it increases instead of decreasing..
Alan Weiss
Alan Weiss on 13 Oct 2022
This could be due to the nonlinear constraint handling routine. When your population is entirely infeasible with respect to nonlinear constraints, the returned fitness value can be negative. Once you have a feasible individual, who will presumably have a positive fitness function. then for the penalty algorithm all the penalty values will be positive, meaning the fitness function will return just positive values. See Nonlinear Constraint Solver Algorithms.
Alan Weiss
MATLAB mathematical toolbox documentation

Sign in to comment.

Products


Release

R2022a

Community Treasure Hunt

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

Start Hunting!