Generating abstract images using genetic algorithms

Hi, Habr!

This summer I took part in the Scientific and Educational School of Moscow State University , which is conducted by the Moscow State University and the Laboratory of Scientific Creativity of the SSCC of Moscow State University . In this article I would like to tell you about a project that I developed during school on a special course on programming under the guidance of MAD_GooZe .

For impatient

The idea of ​​the project

So, we had the idea to do something interesting using genetic algorithms. For example - try to generate beautiful abstract images. By the way, before starting work on this project, I was very familiar with genetic algorithms, but after talking with the manager and reading some articles on the Internet, I rushed into battle.

Principle of operation

So, as you probably know, genetic algorithms are based on the principles of evolution. They allow solving problems, the “ideal” solution of which is not defined, or the method of its direct preparation is not known. Typically, implementations of such algorithms consist of the following steps:

1. Generation of a random generation of individuals-solutions
2. Selection of the most high-quality individuals of the generation
3. Crossbreeding to obtain their descendants
4. Mutation of descendants
5. Getting a new generation

We will tell about the implementation of these steps in our project.

About image view

We will present the pictures in the RGB color space, in which the color of each pixel is represented using 3 components - red, green and blue, each of which belongs to the interval [0; 255]. We will set the image as a set of three functions r (x, y), g (x, y), b (x, y) - one function for each color component. How to draw a picture of these features?

1. Let's go around all the pixels of the image and find the values ​​of these functions for them, passing the pixel coordinates along the x and y axes as arguments;
2. Separately, for each function, we normalize the obtained values, that is, we reduce them to the interval from 0 to 255, using the formula and rounded.

')
Formulas we will present in the form of trees. For example:

Generate random image generation

Since we represent functions as trees, we can easily generate the initial generation. Each function is simply assembled from its constituent parts (other functions, constants, and arguments). The following primitive functions are used:

Unary	Binary
| a |	a + b
cos (a)	a - b
sin (a)	a * b
ln (a)	a / b
arccos (a)	a mod b
arcsin (a)

At the same time, there are some features:

• We cannot generate too complex functions, as this will entail a performance problem. Therefore, a parameter such as the maximum depth of the function tree is entered. The experimentally chosen optimal value of this parameter is the number 6, since too deep (and therefore complex) functions, in addition to the mentioned problem, also generate ripples in image generation, which reduces their quality, and too simple functions generate primitive images.
• Secondly, to achieve the diversity of the first generation, the generated functions must not be similar to each other in their structure, that is, in the number and location of the forks, as well as in the length of the branches. Therefore, the following method of image generation was invented. With probability where n is the depth of the current node, and N is the maximum depth of the tree, an element without a descendant is placed in this node (that is, a constant or coordinate, unlike functions that descendants are required to have, since they are their arguments). This formula was chosen experimentally, based on the following requirements:
  
  1. The function increases its value with increasing n;
  2. When n = N i.e. the depth of the function cannot exceed the maximum;
  3. Subjective criterion that images are generated not too simple and not too complex
  
  
  
• No one bothers to generate constant functions (which are independent of their arguments). In this case, the value of the component is set to 0 for all pixels.

An example of a randomly generated generation:


It is quite expected that almost all random images look boring. To correct this sad fact, we actually need genetic algorithms.
By the way, a separate image of each channel also does not look interesting, but the three of them form beautiful color effects.

Evaluation of images in a generation

After the generation of the first generation, it is necessary to evaluate the solutions obtained. It is somewhat difficult to evaluate the “prettiness” of images automatically, so this task falls on the user's shoulders: first, he chooses the most liked of the received images (he is given the maximum rating), then the best of the remaining ones and so on.

Crossbreeding

After grading, it is necessary to cross individuals to get a new generation. To obtain a descendant image, 2 parents are required. The probability of each individual to become a parent is directly proportional to its assessment.
The crossing algorithm used here is a type of multipoint crossing adapted to this task, i.e., the descendant genes are a set of parts of the parents' genes taken in a specific order, moreover:

• As a result of crossing, an incorrect function cannot be obtained.
• An image with a higher score makes a greater contribution to the child.

Crossing examples:

Mutation

After receiving a descendant, it is necessary to mutate it so that the diversity of generations is not lost. The mutation is applied to all descendants and consists in the following - all 3 functions of the image are bypassed and in each of them the constants / coordinates change with a certain probability to other constants / coordinates.
Example mutation:

Formation of a new generation

30% of the best images are transferred to a new generation from the old, in order not to accidentally lose their genes. And the rest of the images in the generation - the result of crossing. This allows you to maintain a balance between the diversity of individuals and the continuity of "high-quality" genes.

Technical implementation

The implementation of this project is written in JavaScript. Images are drawn on canvas, they are calculated in web workers, to speed up work.

• Demo
• Github

results

With this project I participated in the conference of scientific works of schoolchildren Scientists of the Future , and took 4th place there, which is probably not bad for a grade 8 student :).

Related Links

• Creating images using gradients
• Visual Interface Generator
• Generation of images, remotely similar to the people

The article was prepared in the framework of the Scientific and Educational School of Moscow State University, together with my head MAD_GooZe .