Multi-dimensional Knapsack: Genetic Algorithm vs MIP

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:

Notes:

• 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).