MATLAB: GA algorithm does not find the optimal value

gainteger programmingoptimization

I have a simple integer programing model, and the intlinprog() command finds the optimal solution, but ga() does not.
The problem is very simple: max TP*X subject to cost*X <=budget and X is a binary vector of 626 element.
If I run it as a linear programming , it gets me the optimal solution:
[x1,fval1,flag1,output1]=intlinprog(-1*TP,1:626,Cost',budget,[],[],zeros(626),ones(626))
This results in fval1=-1002.5 and flag1=1 optimal solution
at the same time if I run this:
[x4,fval4,flag4,output4]=ga(@(X)(-1*X*TP),626,Cost',budget,[],[],zeros(1,626),ones(1,626),[],1:626)
It result is fval4=-460 flag4=1
Obviously this is wrong and the solution is far cry from the actual solution.

Best Answer

None of the global optimization functions are guaranteed to find the optimal solution. The different global optimization each have different search strategies: some only use the function values to guide the search, whereas others also use random positioning. Any search that only uses the function value to guide the search will not be able to find its way out of a steep enough minima. Any search that uses random positioning to guide the search is not certain to encounter the "best" location in any finite amount of time.
intlinprog works with a very restricted class of problems that can always be divided up into sub-tasks that are each linear. It finds regions, and within each region the minima is either a plain linear combination of the boundary points or else the minima for the region is at one of the vertices. The program can go through all of the regions, and pick out the minima over all of those regions. (There are ways in which some algorithms can prove that it would be a waste of time to search some of the regions, so some algorithms can do better than searching everything.)
ga() and gamultiobj(), though, generally need to work with non-linear functions which cannot be broken up into regions in which the minima is easily found, so they use randomization as part of choosing areas to search -- but they are not at all certain to happen to search in the right area.
Related Question