MATLAB: Why the ga does not return the minimum value for the objective function

gaGlobal Optimization Toolboxoptimization

I am using matlab ga (genetic algorithm function) to solve a binary assignment problm. my code perfectly works but it does not return the minimum value for the objective function. my problem is really big (10000 decision variables), therefore, I can use simple optimization tools. Here I tested my code on a smaller problem with only (9 decision variables), through enumeration I realized the ga does not return the minimum value. for this small case ga return 146 but the optimum is 94. Any help is highly appreciated. here is my code:
 P = [24 6 7;8 8 21];
 n = size(P,2);
y = cell(n, n);
 for k = 1:n
    for j = 1:n
        y{k,j} = sprintf('y%d%d',j,k); % decision variable if job j is assigned to position k x(j,k) = 1
        % otherwise 0
    end
end
 y = transpose(y(:)); % now x is a n^2-by-1 vector
 y = sym(y, 'integer');
 J = 0;
for j = 1:n
    for k = 1:n
        W(j,k) = P(1,j) * y(1,J + k) ;% processing time of the job in position k
    end
    J = J + n;
end
W1 = sum(W);
C_1_k(1,1) = W1(1,1); % completion time of position 1 on machine 1
for k = 2:n
C_1_k(1,k) = W1(1,k) + (C_1_k(1,k-1)); % completion time of position k > 1 on machine 1
end
SumC1 = sum(C_1_k);
 J = 0;
for j = 1:n
    WW(j,1) = (P(1,j) + P(2,j)) * y(1,J+j); % completion time of the first position on machine 2 %k=1
    J = J + n-1;
end
C_2_k(1,1) = sum(WW); %x(kj)
 for k = 2:n
    K = 0;
    MAX_function = 0.5*(C_1_k(1,k) + C_2_k(1,k-1) + abs(C_1_k(1,k) - C_2_k(1,k-1))); %max function does not work with symbolic variables I wrote simple equivalent
    for j = 1:n
       W_2_k(j,1)  =  (y(1,K+k) * P(2,j));
       K = K + n;
    end
    C_2_k(1,k) = MAX_function + sum(W_2_k,1); %Completion time job in position k on machine 2
 end
 Fun_C_2_k = matlabFunction(C_2_k,'Vars',{y});
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 SumC = sum(C_2_k);
 Fun_SumC = matlabFunction(SumC,'Vars',{y}); %SumC function
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 C_max = C_2_k(1,n);
 Fun_C_max = matlabFunction(C_max,'Vars',{y});
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 ACT = SumC/n;
 for k = 1:n
    SDV(1,k) = (C_2_k(1,k)-ACT)^2;
 end
 CTV = sum(SDV)/n;
  Fun_CTV = matlabFunction(CTV,'Vars',{y});
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\
 % to form opitmization settings
 A = zeros(n,n^2);
 B = zeros(n,n^2);
 K = 0;
 for j = 1:n
    for k = 1:n
        A(j,K+k) = 1;
    end
    K = K+n;
 end
 for j = 1:n
    K = j -1;
    for k = 1:n
       B(j,K+k) = 1;
        K = K+n-1;
    end
 end
 Aeq = [A;B]; %LHS of equality constriants
 %Aeq*transpose(y) The set of equality constriants
 beq = ones(2*n,1); %RHS of equality constriants
 %Aeq*x = beq EQUALITY constraints
 LB = zeros(n,n);%lower bonud for x, since x is a binary variable the lower bound is zero
 LB = LB(:);
 UB = ones(n,n); %Upper bonud for x, since x is a binary variable the upper bound is one
 UB = UB(:);
 nvars = n^2;
 options = gaoptimset('TolCon', 0.0001);
 [y, fval] = ga(Fun_SumC,nvars,[],[],Aeq,beq,LB,UB,[],[],options);i

Best Answer

ga is not an exhaustive search. It never promises to return the global minimum.
ga seldom returns the global minimum over continuous variables even if it manages to find the right "basin of attraction". For continuous variables, ga should typically be followed by a local minimizer such as fmincon to get a better approximation of the precise location.
ga is not magic. ga is a search strategy that should generally be understood as giving a "reasonably good" solution for the time spent searching.
There is no possible algorithm that can reliably return the global minimum of a continuous "black box" function in constrained time . This can be proven by theory.
Your binary assignment problem can be solved in finite time by trying every possible assignment. ga tries random assignments following a strategy, but even given unlimited time, theory says that some combinations will go untested by ga. And you are not giving it unlimited time.
I implemented search for magic squares using ga. I ran it on a relatively modest problem size, 8 or 10, I don't recall which now. I ran it for tens of millions of iterations. It was never able to find the solution. The best it was able to do was the solution except two adjacent items exchanged, and somehow in tens of millions of random tests it never came up with just exchanging that pair. Crossover tended to exchange more than that leading to worse scores; mutation generated configurations that did not meet the sum or uniqueness tests.
Related Question