Constraints not satisfied with 'ga' solver and integer variables

Question

Martha 2018-2-17

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/383263-constraints-not-satisfied-with-ga-solver-and-integer-variables

评论： Martha 2018-2-22

Hi all,

I've been struggling to understand what is the problem with my code. I wrote this long time ago, and now I'm using it with another dataset (large one) and is not working. I'm using 'ga' optimisation with integer variables, but I'm getting the legend of " Optimization terminated: average change in the penalty fitness value less than options.FunctionTolerance but constraints are not satisfied."

Basically what I want to do with my constraints is to avoid repetitions of the integer values in the vector of variables "x" (which has 42 values), and to make sure that the integer value selected for each "x" exists in the respective column of a matrix (124 rows, 42 columns). My LB and UB are between 1 to 124.

The results that I'm getting for the vector "v" are either very close to LB or UB, so 1 to 4 and 122 to 124. So I'm thinking that maybe is completely ignoring all the integer numbers and that's why it cannot find a solution. Here are the line where I call the ga:

x = [55 96 33 73 4 51 37 39 50 78 20 88 1 47 17 44 40 66 56 113 74 31 105 34 108 65 49 8 75 22 99 42 91 46 93 71 82 121 94 114 48 70];
LB=ones(1,42);
UB=zeros(1,42); UB(:)=124;
IntCon=[1:1:42];
hj=72;
options=optimset('Display', 'iter', 'FunValCheck', 'on');
[ x, fval, exitflag] = ga(@(x) ObjFun(x,TwoVal,distances, indices00,OrderedVal,hj,dimension00),42,[],[],[],[],LB,UB,@(x) constGa(x,OrderedVal),IntCon, options);

And the constraint function:

function [c,ceq] = constGa(x,OrderedVal)
ceq=[];
c1=length(unique(x)) == length(x);
c1=double(c1);
c1=(c1-1).^2;
ee=length(x);
for xe=1:ee
   c2(xe)= ~ismember(x(xe),OrderedVal(:,xe));
end
c2=double(c2);
c2=sum(c2);
c=[c1;c2];

If you have an idea what I might be doing wrong, I appreciate your suggestions. When I run this in a smaller dataset of 5 "x" variables instead of 42, and LB and UB between 1 to 18 instead of 1 to 124, I get a solution with satisfied constraints and minimum objective function.

Thank you, Martha

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

请先登录，再进行评论。

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

Answer 1

Matt J 2018-2-17

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/383263-constraints-not-satisfied-with-ga-solver-and-integer-variables#answer_305702

编辑：Matt J 2018-2-17

在 MATLAB Online 中打开

It looks like a difficult feasible set, depending on what OrderedVal contains. It might help to formulate c,ceq in a form that is a bit less quantized,

function [c,ceq] = constGa(x,OrderedVal)
   c1=length(x)-length(unique(x));
   c2=min(abs(bsxfun(@minus, Ordererval,x(:).')));
ceq=[c1,c2];
c=[];

7 个评论
显示 5更早的评论隐藏 5更早的评论

Martha 2018-2-21

在 MATLAB Online 中打开

Hi Matt, and thank you for your answer.

OrderedVal is very large to post here, but maybe is easy to explain. In the dataset that I'm using now 'OrderedVal' is a 124 x 42 matrix, the number of row and columns values can change, but there is always more rows than columns. For each column there are integer values from 1 to 124 randomly located. However, not all the rows have values, for each column the max, number of integer is 124, but for example some of the columns only have 20 values and from 21:124 there are NaNs. This is a very small example, where OrderedVal is a matrix of 18 x 5:

OrderedVal =
   16     1    16    15     1
  14    15    12    16    18
  15    17     2    12    16
  12    16     1    18    12
  18    18    15    17    15
   2    12     9     2     2
   9     2    18     1     9
  17     9    17     9    11
  11    11    14    14    17
  13    14    10     5    14
   5    13    11    10    13
   6     5     5    11     5
 NaN     6    13    13     6
 NaN   NaN     7     7   NaN
 NaN   NaN     8     8   NaN
 NaN   NaN   NaN   NaN   NaN
 NaN   NaN   NaN   NaN   NaN
 NaN   NaN   NaN   NaN   NaN

In this case, my problem seeks to find the best possible combination of 5 integer values without repetitions, that will result in the smallest value of the objective function. For examples with small dataset like this of 18x5 matrix the ga solver works fine. But when I'm trying to use it for bigger datasets it doesn't.

Let me know if you can think about what I'm doing wrong. Thanks,

Martha

Matt J 2018-2-21

I think we need to see the full problem description, including the objective function.

Martha 2018-2-22

在 MATLAB Online 中打开

Hi Matt, Here is the objective function:

function a = ObjFunA(x,TwoParts,dim, OrgVal,OrderedVal,dimTotal)
klp=size(dim); klp=klp(1);
differences=zeros(1,klp);
for lp=1:klp
  Part1=TwoParts(1,lp); Part2=TwoParts(2,lp);
  Val_1=x(Part1); Val_2=x(Part2);
  n=dim(lp);
  Temp1=find(OrgVal(:,Part1)==lp);
  Temp2=find(OrgVal(:,Part2)==lp);
  id1=find(OrderedVal(:,Part1) == Val_1);
  id2=find(OrderedVal(:,Part2) == Val_2);
  q1=dimTotal(id1,Part1,Temp1);
  q2=dimTotal(id2,Part2,Temp2);
  additions=18;
  Total=((q1+q2)/2)+additions;
  Space(lp)=n-((q1+q2)/2);
  sumDim(lp)=(Space(lp)-additions).^2;
end
a=sum(sumDim);

I hope is not confusing, the value of "x" indicates to select an specific element for many combinations of elements that I have. In this case "klp" is the number of total combinations that I need to analyse. I need to find the best combination of "x" values that give me the minimum value of "a". However, I know that most likely "a" will never be zero. I just need to find the best combination with the minimum value of "x".

Thank you, Martha

请先登录，再进行评论。