Show HN: Evolve expressions that evaluate to a target number

github.com

8 points·yati··4 comments

This seems closer to genetic programming than genetic algorithms, although the readme doesn't include any information about the experiment's genotype to really know what's going on.

Hi, author here. It could be called genetic programming, if one considers an expression to be a program.

Each individual in the population is encoded as a binary string representing an infix expression, with 0...9 becoming their binary representations (0001 through 1001) and the operators `+`, `-`, * , `/` and `* * ` (exponentiation) represented as 1010 through 1110.

Ah, never mind, that is a genetic algorithm. I was on my phone, so couldn't read through your code easily. Expressions are more often evolved using a technique called genetic programming, where the "DNA" is a tree structure, and operations like crossover are done via swapping subtrees among different members of the population. Check it out, it's cool stuff. It gets used often when you're evolving programs, rather than something with a more fixed genome.

Since I'm on a phone (again): how do you deal with malformed expressions, and changing the length of the genome?

Oh thanks for that :)

In my current scheme, malformed expressions just get a fitness of 0 (where fitness is between 0 and 1; 1 when the expression evaluates to the given target).

Varying lengths are achieved by randomly picking a length for each individual at the beginning. Thereafter, every generation gets varied length genomes automatically because of crossover. Not sure if this is the best approach, though.

Reply on news.ycombinator.com