I was asked to have a look at the Genetic Algorithm from this site: http://www.mathworks.com/matlabcentral/fileexchange/13680. Just to get an idea I benchmark here the TSP model eil51 from TSPLIB against GAMS/Gurobi. I used Octave instead of Matlab. The solution TSP tour is quite different.
| MIP/Gurobi | GA/Octave | |
| Source | eil51.gms | tsp_ga.m |
| Language | GAMS | Matlab |
| Solver | Gurobi | Octave |
| Options | threads 4 cuts 2 heuristics 0.2 | defaults |
| Objective | 426.00 (Proven optimal) | 437.23 |
| Time (seconds) | 214.255 | 1939.2 |
Warning: to a large extent this is not a fair comparison.
TSP Tour from GAMS/Gurobi:
TSP Tour from TSP_GA:
Why do you call this an unfair comparison? I think the GA people do a lot of interesting work, but I have seen a zillion papers on GA for the TSP, most of which seem to believe that 50 node TSPs are difficult to solve to optimality. A reminder that optimality is not hard for this size problems seems completely fair.
ReplyDeleteI would not be surprised that a high-performance, parallel GA code with some tuning (to make things even) does a little better than what I showed here. Of course the nice thing of a MIP is that they provide bounds and in this case prove optimality.
ReplyDeleteYou can put the code for do the first graphic in .gch?? Please
ReplyDelete