An issue related to GENETIC ALGORITHM. I am trying to solve a Large Binary Integer Linear optimization Problem using GA. GA is violating all the linear constraints.

I am having problem related to Genetic Algorithm. I am trying to solve a Large Binary Integer Linear optimization Problem using GA.

All the constraints in the model are linear. All the variables are integers and some variables are Binary.

The Problem arising is that GA is violating all the constraints despite that they are all linear constraints not nonlinear.

Also while plotting the Best of f value vs generations it plots Penalty value vs generation.

Suggest me how can I get the feasible solution.

The Problem should have the Following Solution For Z calculated using intlinprog

218250.0000 1 1.00000000000060 1 1 1 1.00000000000000 1 0 5000 0 0 499.999999999998 3500.00000000000 1500.00000000000 0 2000.00000000000 3000.00000000000 500.000000000000 0 3500.00000000000 0 1500.00000000000 0 0 600 0 900.000000000001 0

Here is the simplified code:

% mat_eqn.m

function W = mat_eqn(X)

H = [500 350 1000 1250 800 900 850 750 8 14 13 11 7 10 11 10 10 25 20 15 4 2 1 3 4 11 8 7];

% X is a Row matrix

W = X*H';

end

%Solve.m

clear all;

A= [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 0 0; 0 0 0 0 -4000 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 -3500 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0; 0 0 -5000 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 -6000 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 1 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 1 1 0 0 0 0 0 0 0 0; 0 0 0 0 -4000 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 -3500 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 -5000 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0; 0 0 0 -6000 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0; 0 0 0 0 0 0 0 0 -1 0 -1 0 1 1 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 1 1 0 0 0 0 0 -1 0 -1 0 0 0 0; -6500 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 -6000 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1; 0 0 0 0 0 0 -1500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0; 0 0 0 0 0 0 0 -1600 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 -1 0 -1 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 -1 0 -1];

B = [-3000;-4000;0;0;0;0;0;0;0;0;0;0;0;0;0;0;600;1200;0;0;0;0];

 lb = zeros(1,28);

 ub = [ones(1,8),inf(1,20)];

 IntCon = [1:28];

 options = gaoptimset(@ga);

 options = gaoptimset('TolCon', 0.001,'PopulationSize',300,'PlotFcns',@gaplotbestf);

 [X gval]= ga(@mat_eqn,28,-A,-B,[],[],lb ,ub,[],IntCon,options);

 Z=[gval X];

Answer 1

[jgg]

Your problem is that you probably aren't starting with a population which meets your constraints. I can get a solution to your problem by seeding in values which satisfy the constraints as follows:

1) Step one: solve the constraints for a linear solution.

 f = zeros(size(X));
 x_new = linprog(f,-A,-B,[],[],lb,ub);

2) Step 2: Seed a population with lots of x_new values.

init = repmat(x_new,1,100)';

3) Step 3: Use the new feasible population

 options = gaoptimset('TolCon', 0.001,'PopulationSize',300,'PlotFcns',@gaplotbestf, 'InitialPopulation',init, );

I would suggest running this a few dozen times and saving the optimums to generate a population of likely feasible points to seed the population, since the initial population in this code is very homogeneous. This is likely to help find a good global solution.

[TEEH]

Thanks for the answer but it didn't solved the problem.

Still the same problem persists. Its keeps on violating the constraints.

[jgg]

This runs on my PC with your example data, and successfully converges to a point which does not violate the constraints. Could you post a better example of your code to explain why this is the case? You should be able to run this as-is and create a solution.

By construction, if you seed the init matrix as defined above, your population always meets the constraints, so I think you either have more complicated constraints than you demonstrated, or you're not seeding a feasible population. Try following the steps again to make sure.

[TEEH]

Thanx jgg for your brilliant input. Problem successfully solved.