Is it normal for GA to struggle on simple linear problems?

I will try my best to summarize the problem and paraphrase them for the ease of reading, in short, I would like to use GA on a linear model and develop from there.

A little background:

I have been reluctant to touch GA due to my past failures, all my models have been linearized and solved with linprog or intlinprog. However the amount of non-linear relationships in my problem have been giving me headaches on linearization, hence I thought maybe I should give GA another try, but this time it still ended miserably...

My issue with GA:

In short the problem is linear, and easily solvable by the Matlab linear programming linprog function. Unfortunately when I call GA with the exact same parameters, and lower/upper bound matrices used in linprog, GA struggled to solve the problem and when terminated, gave me anfval that was no way near an optimal solution.

 %lp solves the problem almost instantly
 [xLP fvalLP] = linprog(fLP,A,b,[],[],lb,ub,optionsLP)

 %calling GA with the same parameters, failed to convergence 
 [xGA fvalGA] = ga(fitnessfcn,length(lb),A,b,[],[],lb,ub,[],optionsGA)

P.S. I did not go crazy with the options, they were only for plotting etc., therefore I don't feel option settings were the issue.

Problem description: Not sure if it's important, but I will briefly describe my reduced problem.

24 variables x(1) to x(24) to be optimized, objective/fitness functions are both to minimize sum(x(1:12)). I have reduced the problem that x(13:24) don't even contribute to the objective function, they could be anything as long as being feasible and within bounds.

 A = 
[-1 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 1 0 0 0 0 0 0 0 0 0 0 0
 0 0 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
...
 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 1 0]

 b %a column of values  
lower bound is 0 for all x and upper bound is a constant for all x

This is indeed a very simple LP problem, why would GA struggle to solve? I did played around with population size, maximum tolerance, maximum generation etc. but GA just did not converge. Do I need custom crossover/mutation functions?

Kind Regards,

Answer 1

[John D'Errico]

A genetic algorithm is a stochastic solver. It has no understanding that a problem is easy to solve. That a problem is linear has very little impact on the solver. So what you see as an easy problem is just like any other problem for GA.

In this case, your problem has a 24 dimensional search space. It can take some time to search that space, and do it well.

Stochastic solvers are designed to produce a decent solution to a problem, usually using some physical metaphor. Thus genetic evolution, swarms of bees, the cooling of a set of molecules into a solid from a liquid state, etc. Given sufficient time, these stochastic solvers can converge robustly to a global minimum, because they can "escape" from local minimizers.

[Tu Tu]

Hi John, Thanks for the speedy answer! That makes a lot of sense.

I was also a bit concerned on the dimension of the problem to be 24, however the problem is a time-series analysis on optimal component control and resource saving, meaning that whatever happens now is related to what happened in the previous data point, or x(t) = f(x(t-1)).

Ultimate I would like to expand the analysis to cover a much longer period of time points, which will result in a very high dimension (e.g. t = [1:1000]).

Will that make the problem impractical for GA because constraint matrix A will have an approximate size of 500*1000 just for the single set of constraints x(t+500)-x(t) <= some_value

Perhaps there are better ways of formulating time-series problem for Stochastic solvers? Otherwise abide your explanation, problem with 1000 dimension search space with multiple thousand rows of constraints would be a nightmare for any stochastic solver including GA.

[John D'Errico]

As much as it would be nice if genetic algorithms were good at large problems, they have their limits. You may be heading into a problem domain which exceeds those limits. Yes, I know they are a genetic metaphor, so they should be good at solving problems with millions of variables. :)

In the words of Alan Weiss (from here)

"GA is a random search algorithm, and searching more than a few hundred variables takes a long time."

Can you just use a tool like fmincon?

[Tu Tu]

Tried fmincon and it solved within reasonable time. As much as I love GA, guess I will stick with Fmincon for now. The GA model will be kept as a side project, perhaps one day I could come up with some clever formulation to make it work.

Thanks so much for your help John, much appreciated!

Kind Regards,

Tu