Mathieu’s log

Apparently researchers from the University of Arizona have discovered an amazonian ant that has developed into an all-female species which reproduces by cloning.

More details can be found here:

• BBC News
• Le Monde (French)
• Rue89 (French)

Sexual reproduction is a great source of diversity which allows species to evolve over time through natural selection. So, from a pure evolutionary standpoint, one may wonder why these ants have favored cloning over sexual reproduction. The “choice” of cloning suggests that these ants are already very well adapted to their environment and can give up evolving. Asexual reproduction is faster, requires less energy and produces fewer errors (deficient individuals). In the case of these ants, it thus allows for mass reproduction of already well-suited individuals. However this comes at the great risk of extinction of the species on the long term because the species will be “trapped” into its current state (mutations are more rare in asexual reproduction) and won’t be able to adapt in case of environmental change (temperature change, new predator). So this strategy can be seen as favoring individuals over the species. Anyway, this is quite a fascinating discovery.

Genetic programming is a Machine Learning technique that allows to “create programs that create programs” by simulating evolution. The purpose is to slowly converge to a program that performs a defined task as well as possible.

I wanted to try out Genetic Programming and I figured writing a solver for the “numbers game” would be a good example. If you don’t know it, it’s part of the popular game shows “Countdown” in the UK and “Des chiffres et des lettres” in France. For example, given the numbers 3, 75, 2, 4, 1 and 1, the goal is to arrive at 888 using the four basic arithmetic operations (+, −, × and ÷) like so:

74 = 75 - 1
12 = 4 * 3
888 = 74 * 12

The above calculations can be represented as a tree like this:

        *
     /      \
    -        *
  /   \    /   \
75    1    4    3

So it becomes clear that solving the numbers game is equivalent to writing little programs. Although I used the tree representation, a possibly simpler representation that I now think of is like a string of stack operations, like in Forth:

75 1 - 4 3 * *

You start with an initial population of random programs and every generation, you create a new population by selecting the best-performing programs from the current generation, mutating programs (changing a constant with another constant, changing an operator with another operator…) and breeding programs (creating programs which are the combination of two programs).

The generated programs must respect some constraints. For example, division must not have a remainder so 7 / 2 is not allowed. Another example is that the constants used must be among the 6 input numbers and can only be used once.

In Genetic Programming, to determine how good the generated programs perform, we need a scoring function. Here it’s very clear: the closer we are from the target number, the better. To decide between two solutions that perform as well as the other, we can select the one with the fewer calculations.

You can find my program here.

Another idea for applying Genetic Programming that I had is for creating hash functions. What would be the scoring function in that case? One could use the avalanche effect (the greater the avalanche effect, the better) or the average number of collisions (the smaller number of collisions, the better). Although I had this idea by myself, it seems that researchers are already investing this!