Hacker News new | ask | show | jobs
by D_hemming 4754 days ago
I'm mildly annoyed that they don't actually post the solution their algorithm found.
2 comments

In this case, since the possibilities are fairly small, you can solve this pretty quickly anyways. I wrote a very naive algorithm in ruby and it solved it it in 7 seconds.

  # 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
There are two answers to this.

  [2.15,2.15,2.15,2.15,2.15,2.15,2.15]
  [2.15,3.55,3.55,5.80]
from what I understand from Koza about genetic programs, it will be indistinguishable from garbage anyway.

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.

I think he means the best combinations of dishes found.
Genetic Programming is a slightly different thing than a Genetic Algorithm, a subclass, really. I didn't read the code too closely on account that C++ template code makes me want to dig my eyes out, but he said he was doing a GA. A GP is a GA where the genes represent Abstract Syntax Trees and the alleles represent instructions.
Nitpick: there's actually no template code except for passing a few type parameters to the GA library, no different from using ArrayList<MyClass> in Java. However, there's a massive overuse of namespaces and fully-qualified class names - a few using directives would make the code much more legible.
Oh, so this blogger is misusing the term (I scanned a little way down the article and thought I'd concluded he was doing GP). In that case this is much less interesting!
I don't get the need for the GA library here. It doesn't seem to have simplified the problem at all. This code looks several orders of magnitude more complex (or at least just ugly) compared to a hand-written GA that just used std::vectors as the genes.