Is it normal for GA to struggle on simple linear problems?
1 回表示 (過去 30 日間)
古いコメントを表示
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,
0 件のコメント
採用された回答
John D'Errico
2017 年 3 月 21 日
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.
3 件のコメント
John D'Errico
2017 年 3 月 21 日
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. :)
"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?
その他の回答 (0 件)
参考
カテゴリ
Help Center および File Exchange で Genetic Algorithm についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!