Genetic Algorithm (GA) with integer, equality and inequality constraint

Hi all,

I try to solve a complex problem as fast as possible using various optimization techniques. With the Genetic Algorithm, some problems arise: I have to combine equality, inequality and integer constraints (only part of the X vector), which is not possible with the ga function. The equality constraints deal with the non-integer variables. This far, I've used some techniques to work around this, but they didn't prove very succesful yet:

1) Let GA look for the integers only, In the evaluation of the fitness of individuals, call a linprog which optimizes the other variables and makes sure the equality constraints are ok. The linprog makes fitness evaluation really slow.

2) Replace the equality constraint by two inequality constr (Ax<=b and Ax>=b), but this renders the problem with a lot of constraints and no feasible solution is found in a 'normal' timeframe.

Are other techniques possible or does anyone have tips which might help to solve this complex problem with much constraints?

Kind regards

Answer 1

[Matt J]

You can eliminate the equality constraints by using them to solve for some of the variables in terms of the others. If you have the patience to read through a really long thread on this, see here

http://www.mathworks.com/matlabcentral/answers/104739#answer_114013

But it's basically very simple. The equalities

     Aeq*x=beq

should have Aeq full row rank, otherwise you have redundant equalities. Since Aeq is full rank, the equalities can be partitioned, possibly after re-ordering the variables, as

     [P,Q]*[xp;xq]=beq

where P is a square nonsingular sub-matrix and x=[xp;xq] is a corresponding partition of the unknowns x. Then the sub-partition xp can be written in terms of xq as

    xp=P\(beq-Q*xq)

Thus, you can eliminate the variables xp by using the above substitution formula to replace them with an expression in xq everywhere in your problem. This leads to a reformulation of the entire problem in terms of xq only and no equality constraints (just inequalities).

EDIT: If Aeq contains non-integer coefficients, then there is no way, through this elimination scheme, to force xp to obey integer constraints. For the elimination method to work in this case, it must be possible to make the partition [P,Q]*[xp;xq] in such a way that all of the integer constrained variables are contained in xq. This FEX submission can be used to search for the sub-matrix P, from among the columns Aeq(:,i) for which x(:,i) are not integer constrained.