MATLAB Answers

1

Using genetic algorithm (ga) function for integer and linear inequality constrained optimization. Candidate solutions are violating the inequality constraints

Asked by Bob Hickish on 17 Jan 2017
Latest activity Commented on by Alan Weiss
on 6 Jul 2017
I am using the ga() function in the Global Optimisation Toolbox. The problem is constrained by a linear inequality and all the optimisation variables must be integers:
problem.Aineq=[1 1 1 1 1 1];
problem.bineq = 12;
problem.intcon=[1 2 3 4 5 6];
However by looking at the population at various points through the evolution I can see that there are some candidate solutions being generated that violate the inequality constraint.
E.g. A candidate_solution might be: [3 2 2 2 2 2]
I am concerned that the ga() function is "wasting" computing time by evaluating the fitness of solutions that are outside the constrained solution space. Can anyone confirm if this is the case?
From reading the MATLAB documentation for ga() and constrained optimisation it states: "All the linear constraints and bounds are satisfied throughout the optimization." https://uk.mathworks.com/help/gads/examples/constrained-minimization-using-the-genetic-algorithm.html.
Am I misusing ga() if it is violating the constraints?
Thanks

  3 Comments

By what means are you observing the population "at various points through the evolution"?
My best guess, for now, is that you are observing the population at a point prior to some weed-out step where ga discards the candidates not satisfying the linear constraints. I don't think the fitness function is ever actually evaluated at the discarded candidates.
Thanks for your reply Matt J, however I don't think you are right. I say this because even my final population as provided by:
[x,fval,exitflag,output,population,scores] = ga(problem)
contains candidate solutions that break the inequality constraint. It seems unlikely to me that the ga() function would output the final population before the weed-out step?
In answer to your question about how I am observing the population: I am using:
problem.options.OutputFcn=@Output_fcn;
where Output_fcn() just displays the population using state.Population.
I believe the problem is to do with the Mutation Function. I have set it to be the "Adaptive feasible" but I get the following warning: "Warning: Problem has integer constraints. The following options will be ignored by GA: MutationFcn ". There is no mention of this in the documentation. Infact, it states that "Adaptive Feasible" is the one to use when there ARE constraints.
The existence on unfeasible candidates in the population is not necessarily a problem for me, IF they are not passed to the fitness function for evaluation. Can anyone tell me if this is the case, or a possible fix. Thanks

Sign in to comment.

2 Answers

Answer by Alan Weiss
on 17 Jan 2017
 Accepted Answer

Sorry about that, this is a documentation problem. Thank you for reporting the problem. I will fix the documentation soon.
According to a developer, when there are integer constraints, ga strictly enforces bound constraints, but no longer strictly enforces linear constraints. The linear constraints become part of the penalty function that attempts to keep things feasible, but, indeed, the population can be infeasible.
As for what you can do about it, I suppose that you could give a large fitness value for infeasible members as has already been suggested. Or, since your linear constraint is particularly simple, you could write your own mutation, crossover, and creation functions that ensure both an integer-feasible and linear-feasible population, and dispense with the built-in ga version. You see, it is not so easy to satisfy general linear and integer constraints, but your constraint is not at all hard to satisfy.
Again, sorry for the erroneous information in the doc.
Alan Weiss
MATLAB mathematical toolbox documentation

  3 Comments

Thank you Alan Weiss.
I have tried to implement my own mutation, crossover and creation functions. However, MATLAB ga() automatically disables them when you specify integer constraints. eg:
problem.options.MutationFcn=@MyMutationFcn;
leads to: "Warning: Problem has integer constraints. The following options will be ignored by GA: MutationFcn"
I am telling you this for accuracy of your documentation.
Regards, Bob
I just found this post and wanted to iterate that the documentation appears to still be inaccurate with regards to this issue. It has caused some confusion and uncertainty the past couple months.
It is unfortunate that the documentation deadline for the March software release was before the end of January, so my documentation update did not appear in R2017a. It will in R2017b, I assume.
Alan Weiss
MATLAB mathematical toolbox documentation

Sign in to comment.


Answer by Matt J
on 17 Jan 2017
Edited by Matt J
on 17 Jan 2017

From the ga documentation on Mutation Options,
You can specify the mutation function in the Mutation function (MutationFcn) field in the Mutation options pane. Do not use with integer problems. You can choose from the following functions:
I guess the various options available for mutation don't apply when integer constraints are in play.
The existence on unfeasible candidates in the population is not necessarily a problem for me, IF they are not passed to the fitness function for evaluation. Can anyone tell me if this is the case, or a possible fix.
If you are worried about efficiency, I would simply insert a constraint check into the fitness function. In other words, test whether the input satisfies the linear constraints at the very beginning of the fitness function routine and abort all subsequent computations (returning a fitness value of Inf) if it does not. If this slows down execution significantly, it's a pretty good sign that ga is already doing this for you.

  0 Comments

Sign in to comment.