Genetic fractals

This genetic algorithm generates a set of rules for a string rewriting fractal that matches a given target image.

General idea

A string rewriting fractal is produced by iteratively applying a set of rules on how to replace a part of the input with a new one. Fractals like the Sierpinski Carpet subdivide each distinct square in a plane into nine smaller squares and fill them with colors according to a rule. In the next iteration, these squares will be subdivided and replaced again, and so on. Effectively, starting with a single square, the result grows ninefold with each iteration.

In their simplest forms, such rulesets have only two rules, but can have arbitrarily many. For n rules/shades, there are n⁹ⁿ possible rulesets (including rotations and symmetrical ones) with many very different resulting fractals. Most represent noisy images but some of them have geometrical properties. It is therefore feasible to find those rulesets that produce a given target picture, e.g. by means of a genetic algorithm.

This algorithm was inspired and heavily influenced by a post on Jack Hodkinson's blog that explains the idea and general approach in far more detail. Thank you!

Example

After breeding for 200 generations to match the letter Pi. Tint color applied to the result.

Requirements

Python 3, NumPy and PIL

How to run

Run from the console like this, pointing to the target image as an argument. The image should be grayscale and 3ⁿ * 3ⁿ pixels large, where n is the number of iterations (stated in targetIteration, see below) the ruleset should be run to be compared to the target. E.g., the default value of 4 implies a target image 81 x 81 pixels large.

$ python3 fractals.py --target pi.png

Options (selection)

At the top of the file you can change several options to finetune the behaviour of the script. Find explanations there. Some of them include:

• numShades: the amount of shades and subsequently of rules the ruleset should have
• targetIteraion: how many iterations of the rulesets should be run before it is compared to the target image. If this number is denoted by n, this implies that the target image should be 3ⁿ * 3ⁿ pixels large
• progressFrequency: the number of generations to pass before saving a progress picture
• autosaveFrequency: the number of generations to pass before autosaving the rulesets
• populationSize: the amount of rulesets to create on start up
• generationSize: the amount of rulesets for all further generations
• targetConvergance: the minimum fitness to reach until the script stops
• maxGenerations: the maximum amount of generations to iterate until the script stops
• breedingSize: the amount of best adopted rulesets to breed with each other to create the next generation

Limitations

The algorithm is currently rather slow. Breeding and fitness measurement takes quite a while, however, at the moment, I am not sure how to optimise without switching to a more performant language. Suggestions and pull requests to that matter are very much welcome!