# I want to solve a optimization problem with binary variables, linear and nonlinear constraints using the genetic algorithm from the optimization toolbox. Is this possible?

13 views (last 30 days)
Steffen Kuehl on 7 Sep 2016
Commented: Alan Weiss on 8 Sep 2016
Hi,
I am trying to solve an optimization problem that has binary variables, linear and nonlinear constraints using the genetic algorithm.
The problem has 340 binary variables. If I run my code with less variables and without linear constraints I get a feasible solution. With 340 variables and without linear contraints I don't get a feasible solution. I read in the documentation that using a feasible Initialpulation would help. Unfortunately CreationFcn',@gacreationlinearfeasible doesn't work with binary variables.
Is there another way to produce a feasible InitialPopluation?
I also tried to get a feasible solution with 'NonlinearConstraintAlgorithm','Penalty' (changing the Penaltyfactor), but that didn't work out either.
If I run the problem with linear and nonlinear constraints the Ouput is: Could not find a feasible initial point.
x =
[]
fval =
[]
exitflag =
-2
Does someone know if it is possible to use ga with binary variables, linear and nonlinear constraints? I would be very nice if someone took the time to read this.
My code looks like the following. I just left out the big arrays.
Steffen
Befaehiger is a 340x2 Array
VF1 and VF2 are 340x8 Arrays
FCM is a 340x340 Array
ObjectiveFunction =
@fitnessfcn
function y = fitnessfcn(x) % fitness function for GA
global Befaehiger
y = x*Befaehiger(:,1)
nvars =
340
intcon = 1:340;
LB = zeros(1,340);
UB = ones(1,340);
A is a 85x340 Array
B is a 85x1 Array
options are on default
ConstraintFunction =
@constraint
function [c, ceq] = constraint(x) % Nonlinear inequality constraints.
global Befaehiger
global FCM
global VF1
global VF2
c=
[ ((Befaehiger(:,2).*VF2(1,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.5;
-((Befaehiger(:,2).*VF2(1,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.0;
((Befaehiger(:,2).*VF2(2,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.2;
-((Befaehiger(:,2).*VF2(2,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.1;
((Befaehiger(:,2).*VF2(3,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.2;
-((Befaehiger(:,2).*VF2(3,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.1;
((Befaehiger(:,2).*VF2(4,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.2;
-((Befaehiger(:,2).*VF2(4,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.1;
((Befaehiger(:,2).*VF2(5,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.2;
-((Befaehiger(:,2).*VF2(5,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.1;
((Befaehiger(:,2).*VF2(6,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.2;
-((Befaehiger(:,2).*VF2(6,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.1;
((Befaehiger(:,2).*VF2(7,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.2;
-((Befaehiger(:,2).*VF2(7,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.1;
((Befaehiger(:,2).*VF2(8,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' - 0.2;
-((Befaehiger(:,2).*VF2(8,:)') .* x')'*(1+ (VF1(1,:)'.*x')' * FCM*0.1)' + 0.1;]
ceq = [];
[x,fval,exitflag] = ga(ObjectiveFunction,nvars,A,B,[],[],LB,UB, ... ConstraintFunction,intcon,opts)

Alan Weiss on 7 Sep 2016
I suggest that you try making a linearly feasible initial population using intlinprog. To get a well-distributed population, use a different random objective function vector f for each population member:
f = randn(n,1); % n is the total number of problem variables
Use this initial population, and the population should remain feasible with respect to bounds and linear constraints as iterations progress.
I suggest that you use a very large population and be prepared to wait. Integer programming in ga is not recommended for more than about 100 variables, so it is not clear whether this approach will work or not.
It seems to me that your nonlinear constraints are quadratic. If that is true, perhaps you could use an integer programming approach along the lines of this example. But I did not examine your constraints in detail, I might have missed something.
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation
Steffen Kuehl on 8 Sep 2016
Thank you for your answer! Creating an Initial Population with intlinprog solves my problem and the ga returns a feasible solution. And I will take a look into the Mixed-Integer Quadratic Programming Portfolio Optimization.
Can you specify what you mean by very large population? More than the 200 chromosomes that are set by default?
Steffen
Alan Weiss on 8 Sep 2016
I would expect that you would need to set the PopulationSize option to several thousand, perhaps 5,000, to have a chance of getting a reliable answer. but ga will run very slowly with this many members; that's why I said "be prepared to wait."
Good luck,
Alan Weiss
MATLAB mathematical toolbox documentation

### Categories

Find more on Genetic Algorithm in Help Center and File Exchange

### Community Treasure Hunt

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

Start Hunting!