Genetic algorithm only works with integer constraints..

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.

[Alan Weiss]

Yakov, I do not understand why this is happening. Perhaps you should contact technical support so they can investigate your case in detail.

But, if you'd rather talk about it in the community, then please give us some more information.

• Does your problem have linear constraints or nonlinear constraints?
• What MATLAB version do you use?
• Does anything change if you give an initial population?
• Please show your options and entire ga call.
• Is it possible for your fitness function to return complex values?

Alan Weiss

MATLAB mathematical toolbox documentation

[Torsten]

@Yakov Bobrov

Maybe you use sin and cos for the angles when sind and cosd are required ?

Just a wild guess ...

[Yakov Bobrov]

@Alan Weiss

Thank you. Please see my answers below.

• Does your problem have linear constraints or nonlinear constraints? - Only non-linear constraints, and lower-upper bounds. No linear costraints.
• What MATLAB version do you use? - 2022a
• Is it possible for your fitness function to return complex values? - No
• Does anything change if you give an initial population?

To answer this question, I performed three tests:

% Common lines of code
lb = [0,... % zeta1      
      0,... % zeta2
      0,... % zeta3 
      0,... % zeta4
      0,... % zeta5
      0,... % zeta6
      0,... % zeta7
      0,... % zeta8
      0,... % zeta9
      0,... % theta1
      0,... % phi1
      0,... % theta2
      0,... % phi2
      0,... % theta3
      0,... % phi3
      0,... % theta4
      0,... % phi4
      0,... % theta5
      0,...   % phi5
      2*3600]; % tf

ub = [1,...     % zeta1      
      1,...     % zeta2
      1,...     % zeta3 
      1,...     % zeta4
      1,...     % zeta5
      1,...     % zeta6
      1,...     % zeta7
      1,...     % zeta8
      1,...     % zeta9
      360-1,...   % theta1
      360-1,...   % phi1
      360-1,...   % theta2
      360-1,...   % phi2
      360-1,...   % theta3
      360-1,...   % phi3
      360-1,...   % theta4
      360-1,...   % phi4
      360-1,...   % theta5
      360-1,...  % phi5
      4*3600]; % tf

Test 1. No integer constraints. Specifying initial population.

GA_opts = gaoptimset('InitialPopulation',xSolInitial,'PlotFcns',{@gaplotbestf,@gaplotdistance});
[xSol,fval,exitflag,OUTPUT_GA,POPULATION_FINAL,SCORES] = ga(@(x) fitness4(x), 20,[],[],[],[],lb,ub,@(x) nonlcon4(x),[],GA_opts);

After 2.5 minutes, the simulation stops at only 4 generations:

Test 2. No integer constraints. No initial population.

GA_opts = optimoptions('ga','PlotFcn',{@gaplotbestf,@gaplotdistance});
[xSol,fval,exitflag,OUTPUT_GA,POPULATION_FINAL,SCORES] = ga(@(x) fitness4(x), 20,[],[],[],[],lb,ub,@(x) nonlcon4(x),[],GA_opts);

After 5 minutes, simulation is terminated at 6 generations:

The initial fitness value is negative.

Test 3. Integer constraints for the angles. No initial population

intcon = [10,11,12,13,14,15,16,17,18,19];
GA_opts = optimoptions('ga','PlotFcn',{@gaplotbestf,@gaplotdistance});
[xSol,fval,exitflag,OUTPUT_GA,POPULATION_FINAL,SCORES] = ga(@(x) fitness4(x), 20,[],[],[],[],lb,ub,@(x) nonlcon4(x),intcon,GA_opts);

With the default settings, the simulation terminated after ~2.5 minutes, at 329 generations:

I have been using settings from Test 3 for my solution so far, and running up to 5000 generations, producing reasonable results. However, I would like to get rid of the integer constraint (as in Test 2).

Kindly let me know if you understand why this is happening. Nothing else was changed in the code between the tests, except for the initial guess/integer constraint inroduction.

Thanks!

[Torsten]

We neither know fitness4 nor nonlcon4. So no useful comment can be made.

[Yakov Bobrov]

@Torsten Hi. No, I am treating angles correclty. But also nothing else changed in the code, apart from the introduction of an integer constraint.

[Torsten]

As said: How should we be able to tell you the reason without knowing your problem formulation ?

[Yakov Bobrov]

@Torsten Could I share them with you privately?

[Yakov Bobrov]

@Torsten

Is it possible that the issue is not in the fitness/nonlcon functions? As I said, this problem occured to me with very different formulations of my problem. So, I used very different fitness/nonlcon functions, but the GA plots looked fine (as in Test 3) only if I used an integer constraint for half of the variables (previously I fixed the time variables as integers isntead of angles).

[Torsten]

No, sorry.

You might want to wait a while if someone else in the forum is able to guess some reason. But I doubt it without the necessary background information.

And if it's a bug in ga (what you allude to, I guess), we won't be able to find it.

Why don't you contact support ? They will treat your data confidentially as far as I can tell.

[Yakov Bobrov]

@Torsten I am not alluding to anything, because I am new to ga, and I genuinely do not know what could be the reason for this. I will contact support, I just did not know that there is an option to do that...

[Torsten]

Do you use rounding to integers in fitness4 for the variables 10:19 such that they are quasi integers anyway ?

[Yakov Bobrov]

@Torsten

No, because I do not want variables 10:19 to be integers. I would like them to take any value between 0 to 360 (degrees), up to a certain decimal place.

[Torsten]

And how does ga work if you start from the integer solution, but without the intcon setting ?

[Yakov Bobrov]

So, it is basically Test 1 that I showed above. I tried again and GA terminates at 4 generations, and it takes 4 minutes to get there:

[Yakov Bobrov]

Very strange... I ran the code again without any integer constraints and without initial population. As you can see from the screenshot below, fitness function is negative (times 10^9). However, if I pause the simulation and calculate the fitness function, it turns out to be a positive and reasonable number. Also, I am getting good results even after only 20 generations! So, it is only the plot that is wrong. Does it look like a bug?

[Torsten]

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 ?

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)

[Yakov Bobrov]

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

Answer 1

[Alan Weiss]

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

[Yakov Bobrov]

@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]

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