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.

Question

TEEH 2015-12-18

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/260806-an-issue-related-to-genetic-algorithm-i-am-trying-to-solve-a-large-binary-integer-linear-optimizati

评论： TEEH 2015-12-19

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];

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

jgg 2015-12-18

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/260806-an-issue-related-to-genetic-algorithm-i-am-trying-to-solve-a-large-binary-integer-linear-optimizati#answer_203633

在 MATLAB Online 中打开

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.

3 个评论
显示 1更早的评论隐藏 1更早的评论

jgg 2015-12-18

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 2015-12-19