GA vs patternsearch for Integer problem with equality constraints

11 Ansichten (letzte 30 Tage)
Conrado Neto
Conrado Neto am 28 Jul. 2020
Bearbeitet: Conrado Neto am 29 Jul. 2020
I am attempting to solve a simple problem using GA.
My problem has 8 decision variables, all integers, with lb of zeros and ub of TWOS.
I need to ensure that the sum of the variables is always equal to 2.
Therefore I used ga with the following set up:
[x,fval,exitflag,output] = ga(@(x)ObjFun,nvars,A,b,[],[],lb,ub,[],IntCon,opts)
I am writing A and b so that an equality condition is enforced (A(:,2)=-A(:,1) and b(2)=-b(1))
I am solving this simple problem to test the convergence and reliability of ga in a simplified version of my actual problem, before jumping to the real monster.
This problem has 36 possible combinations results. They are:
Comb=[00000002,00000011,00000020,00000101,00000110,00000200,00001001,00001010,00001100,00002000,00010001,00010010,00010100,00011000,00020000,00100001,00100010,00100100,00101000,00110000,00200000,01000001,01000010,01000100,01001000,01010000,01100000,02000000,10000001,10000010,10000100,10001000,10010000,10100000,11000000,20000000]
I solved them all outside of GA and all the possible results (objective function results) are:
R=[97.23,86.40,109.57,93.80,94.21,97.67,89.55,89.75,85.00,95.27,93.71,94.11,94.65,90.41,97.55,88.71,88.81,89.54,85.25,84.12,93.78,93.26,93.61,94.14,89.88,94.07,88.99,97.17,89.43,89.60,90.22,85.84,90.17,85.09,84.29,93.70]
as a student working on research I am trying to get a stable, reliable and fast optimization code to start with those smaller versions of my problem and then build into the big one.
using GA, with all default options, I get no convergence with an exitflag of -2.
however, if I increase the population size (default is 10*8) to 100, 200... I start getting convergence of an exiitflag of 1. HOWEVER, that depends on how I set the RNG.
using 400 population works for all RNG I have tried. but this means that for my actual problem, that will be a lot more complex, I will need such a large population that the problem will take forever to solve. That's my intuition.
so my questions now are:
1) are there other GA options I should try to have a fast and reliable code, given this example and al these conditions?
2) is it possible to use patternsearch enforcing integer constraints for This problem that I am solving?
however, even setting those options, matlab goes to non-integer decision variables in the second interation.)
Thanks for anyone that took the time to read all this,
Conrado
  1 Kommentar
Conrado Neto
Conrado Neto am 28 Jul. 2020
Note that my objective function has no repeated result.
There is only 1 optimal solution.
I am looking for the minimum one.

Melden Sie sich an, um zu kommentieren.

Antworten (1)

John D'Errico
John D'Errico am 28 Jul. 2020
Bearbeitet: John D'Errico am 28 Jul. 2020
An exitflag of -2 means that GA never even found a feasible starting point for your problem. A larger population size lets it randomly SOMETIMES find a feasible start point.
If you are looking for something that is seriously consistent, and will run quickly, then GA is going to be problematic, at least as you want to use it. However, I think you have parameterized the problem completely incorrectly.
Effectively, the problem is you are trying to search over a huge search space, with a constraint that seriously limits the locus of feasible points.
Your statement is the constraint is the sum of these variables MUST be exactly 2, in a 0-1 binary IP.
All that means is you can represent the problem with EXACTLY TWO integer variables. Represent the set of ALL solutions as an integer of the form:
X = 2^n1 + 2^n2
where n1 > n2. Period. That is really all you need to do.
Now your problem has NO equality constraints on the sum of X. NONE. As well, it becomes a simpler problem, because the search space is now only a two variable integer space, with the limits on n1 being 1 to nmax, and n2 is constrained to run between 0 and n1-1.
Now, don't do this the wrong way. DO NOT form X as the sum of those two powers of 2, because if the problem is at all large, then you will see overflows. That would happen if nmax is greater than 52.
But all you need to do is search over the space I have described. n1 and n2 define the locations of the non-zero elements. DONE. And not only that, but TRIVIALLY DONE. The result will be efficient as hell, because you never need to worry about finding a feasible point. EVERY point is now feasible point. And a 2-dimensional search space is an effectively trivial space to search over.
Now, suppose you decide to make the problem more difficult? Suppose you decide that the sum was actually going to be 3, or 5, and there are hundreds of variables in the binary integer IP? Still trivial to solve. Still relatively efficient as hell. Suppose we have 5 variables? Just solve this as a problem where you will optimize over a search space that is again of the form
X = 2^n1 + 2^n2 + 2^n3 + 2^n4 + 2^n5
Again, don't actually form that big number. All n1,n2,n3,n4,n5 are now is the locations of where the corresponding binary bit appears in the binary representation of X. Now you will have the constraints
nmax >= n1 > n2 > n3 > n4 > n5 >= 0
Again, this means you would just have an integer search space. Still simple to solve. Massively efficient compared to the kludge of an approach you were trying to use.
  12 Kommentare
Conrado Neto
Conrado Neto am 28 Jul. 2020
sorry for missing your questions, I hope now you are clear about the problem and can forget that "have me solve the problem you don't really have" statement.
my objective function is getting the x values to call an analysis software and compute the results, there is no closed form solution that can be written in an equation.
Conrado Neto
Conrado Neto am 29 Jul. 2020
Bearbeitet: Conrado Neto am 29 Jul. 2020
Unless I missed something in the proposed formulation, the problem I have with using x(1) and x(2) with lb=[1 1 ] and ub=[8 8] is that this means that I can have x=[1 2] as well as x=[2 1] and they both yield the same result. Is that why you add the constraints: nmax >= n1 > n2 > n3 > n4 > n5 >= 0 ?
Ok yes it is. I wll try it now

Melden Sie sich an, um zu kommentieren.

Community Treasure Hunt

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

Start Hunting!

Translated by