In http://pyeasyga.readthedocs.org/en/latest/examples.html a small example of a knapsack problem is shown. Here it has two constraints instead of the usual one (hence multi-dimensional). Note that we are maximizing the objective. The code to solve this with a genetic algorithm is:
When I run it I actually get a somewhat worse objective:
When solving the same problem as a MIP:
we get as solution:
- Even for some really small examples from the documentation, meta-heuristics find sub-optimal solutions.
- I often see something like: “problem is NP-hard so we must use a meta-heuristic.” I don’t think this is always true.
- MIP solvers have the advantage that they provide optimal solutions for small instances. For large difficult problems they can give a good solution and in addition a measure of how good this solution is (the gap). Meta-heuristics do not have this property.
- Some commercial MIP solvers actually use heuristics extensively inside their algorithms to help find good solutions quickly.
- I have implemented a number of heuristic algorithms for some nasty problems, but I always try to start with a MIP implementation to get a baseline (both wrt performance and solution qualities).