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?

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.

Thank you in advance!

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)

Answer 1

[Alan Weiss]

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]

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?

Thank you for your help,

Steffen

[Alan Weiss]

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