HN Reader

I was recently working on simple demos for Genetic Algorithms that only use basic, programming techniques.

My first one just tries to make a 64-bit bitting that is all 1's. I made random selection, roulette wheel, and tournament. Random is there as empirical proof that GA's are smarter than chance. Tournament is doing a great job.

Next idea is student loans. For maybe 15 loans with different rates, what payment plan knocks them all out the fastest? I'm fixing the payment size with a payment plan being a list of numbers representing which loan to apply the payment to (or 0 for no payment). Each step is (a) apply payment, (b) advance all loans with interest, and (c) see if the total is zero. Fitness will be interesting given I need to optimize for minimal principle and payments.

I found some other easy examples people did online that beginners might want to recreate. They include trying to get from point A to B with bananas at random places (avoid falling), best combo of items in your backpack for travel, and ants finding the best path to get the most food in a 2D map. I'll try to dig up the links later if someone wants them. Otherwise, those descriptions alone might be a starting point.

Note the website (ai-contest.com) that the post links to seems to have been hijacked by a gambling site.

For the use-cases where Genetic Programming was popular, I would recommend looking at Bayesian Optimization (bayesopt) as an alternative today (I know I keep recommending the area - but I hope I do when it is relevant :-)). This is mostly because IMHO it has a principled foundation that has been productively developed further in the past few years. Here's a good book on the topic [1], and I've a tutorial as well [2]. Interestingly one of the books I had encountered when reading up on Genetic Algo. years ago was by Melanie Mitchell [3]!

Bayesopt or Genetic Programming, or any search algorithm that can operate over non-differentiable objective functions are very useful in practice. For ex, when performing model selection in the space of hyperparameters, when your model is not differentiable such as a traditional Decision Tree [4]. Or exotic use-cases like molecule discovery [5].

You can try out bayesopt using the botorch or hyperopt libraries. The latter only implements a specific bayesopt algo. which was/is popular but it seems to have been bettered of late [4].

[1] https://bayesoptbook.com/

[2] Part 1 https://blog.quipu-strands.com/bayesopt_1_key_ideas_GPs

[3] Found a free copy online https://www.boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf

[4] "... Analysis of the Black-Box Optimization Challenge 2020" https://proceedings.mlr.press/v133/turner21a.html

[5] ChemBO is an example but there are others https://proceedings.mlr.press/v108/korovina20a.html

Nice writeup, short so is more approachable than John Koza’s classic book on GP. That said, if GP looks useful to you, eventually read Koza’s book, or at least experiment with his Common Lisp code.

Also don’t confuse Genetic Algorithms (GA) with GP.

Genetic programming: https://en.wikipedia.org/wiki/Genetic_programming

Evolutionary computation > History: https://en.wikipedia.org/wiki/Evolutionary_computation #History

- "The sad state of property-based testing libraries" re coverage-guided fuzzing and other Hilbert spaces: https://news.ycombinator.com/item?id=40884466

- re: MOSES and Combo (a Lisp) and now Python too in re: "Show HN: Codemodder – A new codemod library for Java and Python" and libCST and AST and FST; https://news.ycombinator.com/item?id=39139198

- opencog/asmoses implements MOSES on AtomSpace, a hypergraph for algorithmic graph rewriting: https://github.com/opencog/asmoses

The ai-contest.com links go to a strange, irrelevant, and suspicious website.

Naive question: what are the most suitable problems that Genetic Programming is to solve, despite that machine learning especially deep learning is all the rage now? Or do we have models that integrate genetic programming into deep learning?

This is from 2011, FYI.

Hah, this is about the ~2010 Google ai contest “planet wars”. I participated in the 2011 iteration, ‘ants’, which was a fun but humbling experience. Anyone else try that? I recall the final winner’s solution was far less elegant than I expected after the code was released, but man was it effective.

Last I checked, genetic programming wasn’t promising, and I’m a little surprised to see people paying attention to it here.

OTOH that was similar to what people were saying about hidden layers, so YMMV

I just hope the baby is fine!

Nice work! Thanks for posting.