Genetic Algorithm for Knapsack Problem

So, in a way, this entire solution is the product of an error in reproduction. :)

That's one of the problems with Genetic Programming in general - you might get a specific program optimised to a specific problem, but you never learn anything about the problem space from it.

  # Initialize it with the most we can need of any individual numbers, plus the maximum possible zero's we could use
  # (Just picked 5, because it can't take more than 7, and we have at least 2 of everything. I know there are better ways of doing this, but I was just hacking something up quickly).
  x = [2.15,2.75,3.35,3.55,4.2,5.8].map{|n| [n]*(15.05/n).to_i}.flatten + [0]*5
  # Find all of the combinations that add up to 15.05
  x.combination(7).select{|c| c.inject(:+)==15.05}.uniq

  [2.15,2.15,2.15,2.15,2.15,2.15,2.15]
  [2.15,3.55,3.55,5.80]

Evolution didn't build humans by starting with the problem of 'build a human' - it branches into solving various local niche problems simultaneously (primarily motivated by, how to replicate self). See also: Darwin's finches.

I would assume that biological evolution also spends a lot of time stuck in local maxima with short periods of volatile change as a new local maximum is identified (this hypothesis fits perhaps conveniently with the fossil record).

So natural selection is excellent for blindly solving problems with progressive goal(s) - which are rarely of the type identified by pure computer science. But, hard optimization problems with an open-ended solution could be well-suited.

A problem such as this where a near-miss answer doesn't get you any closer to the correct answer makes it difficult or impossible to identify relative genetic fitness - evolution is more likely to get stuck in an ineffective local maximum. Evolution may be slower at solving this problem than pure random guessing.

Interestingly, the article introduces the aspect of preparation time, which is not exactly what I understood from the xkcd comic. I believe this would allow an artificial escape route for the algorithm, since it's less likely to get stuck in a wrong local maximum considering price alone.

tl;dr: Agreed, biological evolution doesn't seem to effectively solve a yes/no problem like this.

The punch line was that they mathematically proved that genetic algorithms produce less optimal solutions than hill-climbing.

So why are "genetic algorithms" so common in nature? Well, it turned out that genetic algorithms were better at producing solutions that were resilient to changing environmental conditions. They produced a less sharp peak at the solution they did find, so when a change occurred in the underlying conditions, the still had a reasonable chance of being at least ok.

In a previous life, we applied GA to finding defects in design and implementation. The genes were atomic actions one could take with the product. Chromosomes were scenarios. In this case two valid scenarios can be crossed to expose a defect. The system was monitored while the scenario was processed, and fitness was measured as whether or not a defect was detected.

One excellent side-affect of this process was that when defective scenarios were used to seed population, we received convergence to a minimum reproduction.