Binary solutions with GA

Question

Loic Wilfried Biakeu Njia 2017-6-20

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/345425-binary-solutions-with-ga

评论： Brendan Hamm 2017-9-30

Hi

I am currently working with GA on resource allocation and the goal is to find binary solutions with a non linear objective and linear constraints.

At the beginning of the project, I had a problem with more than 700 variables with many constraints and the solutions that I had from GA were very irrelevant. I thought the size of the problem was the issue.

So I broke down the problem into many models in order to have less that hundreds variables (in occurrence 30 variables for the current model I am building) and around hundreds constraints too for each model (in occurrence 95 linear constraints for the same current model). Besides, some of the constraints are normally equality constraints that I transformed into inequality constraints to help GA to find a solution. BUT at the end I still have solutions that don't correspond to the constraints. For the instance, for example if we want to allocate 30 bags in 5 cabinets so that each bag is allocated only in one cabinet, I got some results where one bag is allocated in many cabinets, even though the inequality constraints that I wrote seem totally correct.

I have this report at the end "Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance and constraint violation is less than options.ConstraintTolerance".

I don't really know what to do with this problem and I am quite in a need of a solution for an industrial (confidential) problem after having purchased GA weeks ago (the trials for smaller sizes seemed to work previously). Please could you give any support for that?

Thanks,

Loic

8 个评论
显示 6更早的评论隐藏 6更早的评论

Walter Roberson 2017-6-20

https://www.mathworks.com/help/gads/ga.html#inputarg_nonlcon

nonlcon - nonlinear constraint function

"Function handle that returns two outputs:

[c,ceq] = nonlcon(x)

ga attempts to achieve c ≤ 0 and ceq = 0. c and ceq are row vectors when there are multiple constraints. Set unused outputs to [].

ga does not enforce nonlinear constraints to be satisfied when the PopulationType option is set to 'bitString' or 'custom'.

If IntCon is not empty, the second output of nonlcon (ceq) must be an empty entry ([])."

===

This has nothing to do with your objective function being non-linear: there are restrictions on using constraints with intcon set. nonlinear constraints are the easy way to code the kind of bounds you mentioned, but nonlinear equality constraints are not supported if you have IntCon set. Also,

"Note: When IntCon is nonempty, Aeq and beq must be an empty entry ([]), and nonlcon must return empty for ceq. For more information on integer programming, see Mixed Integer Optimization."

so linear equality constraints are not supported either. That makes it a nuisance to code equalities such as that the number of bags in a cabinet must be exactly 5. However, in some situations you can recode the equality constraint by first coding -1 entries in the A matrix and setting the b entry to the negative of the total: this ensures that at least that many entries are set. Then you code +1 entries in the A and set the corresponding b to the positive of the total: this ensures that no more than that many entries are set. The combination of "at least" and "no more than" can achieve an equality. However, at the moment I am not confident that the same kind of technique can be applied to non=binary integer decision variables.

Loic Wilfried Biakeu Njia 2017-6-21

Hi. Thank you for your answers.

So, please what could finally be the solution of this? If when IntCon is set, Aeq and Ceq must be empty, what to do to have integer solutions at the end? Is it any way possible to still have integer solutions without IntCon but only using Aeq and Ceq? If not, what is the point or the purpose (as you said "nonlinear constraints are the easy way to code the kind of bounds you mentioned") for a MINLP to set Aeq and/or Ceq with no assurance to get integer solutions?

For my case, I already did exactly what you suggested on coding the -1 entries and then the +1 entries. As results, sometimes for the the same system and the same script, the solution seem relevant and sometimes not. I am wondering what could be the cause of that discrepancy?

At the end, please let us consider I use a single integer from 1 to 5 for each bag, I must certainly in that case change the constraints or totally change the objective function because of the new values of the decision variables that are actually now kind of "affectation" variables. Any idea on that please?

Thank you for your answers. Best,

Loic

Loic Wilfried Biakeu Njia 2017-6-28

"Are there maximums? Is the requirement that each cabinet receive exactly 6 bags?"

The objective is to balance the repartition of bags into the cabinet. The maximum a cabinet can receive is ceil(number of bags/number of cabinets), because we can have some cases where the number of bags is not even. For the second question, I didn't write exactly that requirement as an equality constraints. However, to avoid equality constraints, I wrote that each cabinet could receive more than floor(number of bags/number of cabinets) and less than ceil(number of bags/number of cabinets).

For your suggestion about custom creation and mutation function, I don't know more about. I will probably have a look on that.

Thanks,

Walter Roberson 2017-6-28

Ah, good point about the number sometimes having to vary.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Brendan Hamm 2017-9-20

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/345425-binary-solutions-with-ga#answer_282401

This will be a bit length to answer this question again, but I have provided a way you can solve this problem in a previous post:

https://www.mathworks.com/matlabcentral/answers/303045-is-there-a-work-around-to-use-gamultiobj-with-linear-constraints-and-binary-variables

This does use a multiobjective problem, but the idea of writing the population, crossover and mutation functions is the same.

2 个评论
显示无隐藏无

Loic Wilfried Biakeu Njia 2017-9-27

Thanks Brendan for your answer! I like the way you took on the issue.

I have tried your solution but unfortunately it doesn't work for my case. It get stuck in the popFun function and indefinitely computes but I think never finds a Population that conforms all the constraints.

Brendan Hamm 2017-9-30

If you post it on here I will take a look when I have some time and suggest some possible alternatives.

请先登录，再进行评论。

Binary solutions with GA

8 个评论
显示 6更早的评论隐藏 6更早的评论

回答（1 个）

2 个评论
显示无隐藏无

另请参阅

类别

标签

产品

Community Treasure Hunt

Binary solutions with GA

8 个评论 显示 6更早的评论隐藏 6更早的评论

回答（1 个）

2 个评论 显示 无隐藏 无

另请参阅

类别

标签

产品

Community Treasure Hunt

8 个评论
显示 6更早的评论隐藏 6更早的评论

2 个评论
显示无隐藏无