why the ga does not return the minimum value for the objective function?

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

Answer 1

[Walter Roberson]

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.

[Sohrab Abedini]

Thank you Walter for your prompt reply. I agree with all the points you mentioned. I know that sometimes ga is stuck in a local minimum and never converges to the global optima. For my problem, I've proven that it is N-complete, which means there is no solution in polynomial time. I am developing a heuristic to find a near optimal solution for my problem, and the reason I used ga is to have a reference point to compare my heuristic performance with. For my question above, I converted equality constriants to inequality and added IntCon to the ga, and I got way better results compared to what I got with equality constraints. Anyway, I highly appreciate your time addressing my questions, which was a huge help. Best, SA