MATLAB Answers

0

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

Asked by Kobe Geryl on 19 Dec 2014
Latest activity Edited by Matt J
on 7 Jun 2019
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

  0 Comments

Sign in to comment.

1 Answer

Answer by Matt J
on 19 Dec 2014
Edited by Matt J
on 7 Jun 2019
 Accepted Answer

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

  0 Comments

Sign in to comment.