Concepts of the practical use of genetic algorithms

Foreword

The writing of the article was inspired by two publications:

• Live graphs
• Review of evolution methods ...

I wanted to state my thoughts and my view on this question precisely as a practitioner from programming "with a mathematical background." It will be a “fingers” narration. I am not a specialist in genetic engineering and judging by the superficial descriptions of the mechanisms of functioning of living cells and DNA.
Perhaps it is for the better. The first impression of the “Survey of methods for the evolution of neural networks” was: “it’s quite difficult to write, but I didn’t find practical details or missed them”. I had to dig further. In particular, I found a crossover description - bitwise, which is mentioned in the above-mentioned publication:
"... because the use of standard binary operators, as a rule, leads to the frequent appearance of unviable solutions." In my understanding, it would have sounded like this: “such a method will not give the expected result of crossing, but give rise to a mutant.”
Having read the same descriptions of the implementations of some key points of the GA, I decided to state my vision of the problem.

Crossing over

The first thing I didn’t agree with was the implementation of crossover through a bitwise operation. For me, this method is unacceptable for at least two reasons:

• unstable result;
• unmanaged mutation.

Intuitively, I understood that with very high probability such an approach would give a bad result, at least for automatic control tasks. Imagine if the root or pole of one automatic control system (ACS) is bitwise “crossed” with the corresponding parameter of another ACS. As a result, an unstable ACS will almost certainly be obtained, since for its stability, a sufficiently fine tuning of the coefficients of differential equations is required. And for this area, the stability of the regulator and the precise control of its parameters are very important.
My understanding of the crossover mechanism is this. At a certain stage of cell division, DNA molecules from two homologous chromosomes (with the same sequence of allelic genes) come close to each other, forming a double helix (here I do not mean the spiral structure of the DNA itself). There is a probability that in a certain place of this spiral the “beginnings” of two allelic genes will coincide (the genes responsible for the same property; I may be mistaken) and there is also a possibility that two molecules will stick together at this place, and after “unraveling” 50% probability two molecules "exchange tails." Further, apparently, only one of the chromosomes will participate in the development of a new individual. Here I do not clearly represent all the mechanics.
Thus, crossing over in my understanding transfers a whole group of genes from one chromosome to another. This process even involves DNA mapping research. The basis is the conclusion from the description of the mechanism of crossing-over: genes close to each other in the linear structure of DNA are more likely to pass from parent to offspring together, and genes located far from each other are often separated during DNA replication (it seems this happens at the stage of mitosis cells). Therefore, I believe that the point of contact for crossing-over should be sought, not bit by bit, but between genes. In the DNA for this there are "introns". Otherwise, a “black fly” and a “blue fly” would have a child with hooves.

Genes

The meaning and content of genes, depending on the task, may be different. In TAU, a gene can be understood as a certain high-level parameter of regulation quality (for example, the root of the characteristic equation of the transfer function, bandwidth, cut-off frequency, overshoot, etc.) and the rule by which this parameter will affect the final implementation of the ACS. If we consider the task of creating a game in which the world, characters and gameplay are tied to genetic algorithms (about this below), the picture becomes even more beautiful. Here, the genes must have a packet structure in which the type of this gene is encoded - for which it is responsible (for example, it is the gene for avatar skeleton formation or the gene for the formation of a relief of a location, or something else) that this gene creates (behavioral rule, instructions for the structure of something, the rule of the relationship of any characteristics of the object among themselves, etc.), conditional blocks and parameter values. It turns out a kind of hierarchical coding of genes. In accordance with this scheme, we obtain genes of various lengths, which are arrays of numbers, in general, an array of bytes, although this is not necessary. To me, such a scheme seems to be closest to reality (to nature). Instead of an array of bytes, the gene can be represented as a structure containing enumerators (C #, enum), strings and fractional numbers.
I would also like to make a reservation about the peculiarities of DNA work in the case of bisexual (and maybe three, four, etc.) reproduction, as well as about “dominant” and “recessive”.
Judging by the available information, there are chromosomes that are transmitted by the born individual depending on the gender. If the sex of the conceived individual is “female,” then one chromosome is transmitted, and if it is male, the other. How the genes set in the “sex chromosomes” is chosen is unimportant for me. And this idea itself is difficult to apply to the TAU field. Theoretically, I can use this mechanism to adapt the regulators to changing conditions: the driving mode has changed (sports cars have, for example, city mode and sports) - I change the “sex” of the individual ACS. But you will need to store the settings and provide for a special algorithm for switching from one regulator to another.
In games, such a mechanism is very well applicable. It is interesting to implement a "sex change" and look at the metamorphosis that occurs with the character. In principle, it is not very difficult to make a list of genes that will depend on gender. It will be important to ensure a gender balance. Thus, in the game it will be possible to abandon the "racism", playing intersexual differences. But then the game world will be very different from ours (there are no races and there are 3, 4, 5 and / or more genders). Someone like it, but some do not.
About dominant and recessive genes. It is believed that the recessive genes seem to sleep inside the DNA (there are two of them in each chromosome from each of the parents), i.e. if the dominant gene is received from the father, the maternal one sleeps. It turns out this is not always true. In studies of genetic diseases, it was found that mutated recessive genes with pathology still affect the body, but much less than in the case of their dominance. For the game development industry, this will allow the core of the game to lay down conditions under which recessive genes will be involved in modifying the gameplay on the principle of genetic diseases transmitted by the male or female lines (sexually transmitted, is a joke of humor).
')

Practical use

TAU and noise filtering

Your shirt is closer to your heart. I am engaged in research in the field of digital navigation information processing in conditions of high noise intensity in sensors. Therefore, my main questions to the GA are the following: “is their practical application possible in the field of TAU” and “how profitable will their use be”?
There is an approach to solve the problem of “stochastic estimation” of measured parameters through the creation of measuring units with information redundancy [1] (the number of sensors is greater than the number of measured parameters). In such cases, for example, you can use a multidimensional version of the Kalman filter (or an observing Lewinberger identification device) to process signals from sensors. And here it is required to choose (in the case of Lewinjerger's NUA) or to determine (in the case of FC) a mathematical model of a dynamic object (sensor model). In addition to the parameters of the sensor model, information about the measuring noise and disturbances of the dynamic process (internal noise of the sensors) - dispersion and noise covariance is also needed. All these parameters determine the filtration efficiency and the total bandwidth of the measuring system. There are various methods for selecting these parameters. The hardest thing is to choose the dispersion and covariance of the internal noise of the sensors. They can not be measured.
And what if we apply the GA for the selection of optimal values? There are difficulties. First, these algorithms require significant computational power. In fact, this is a search of all possible combinations of values. So, as a student, I selected the parameters of the transfer function, i.e. led decision to answer. I knew about how the frequency response should look like, it remained to pick up in MatLAb the parameters that I would draw this frequency response. But the ACS is an on-board computer, low-power and not very productive computer, or even just a set of frequency filters on operational amplifiers. Secondly, implemented in the form of the ACS computer, the control system constantly calculates the control actions. If its power is small, then there will be no time to "play life". It turns out that here GA are not applicable?
I want to believe that they are applicable. The parameters of a moving object change slowly in time. If a multi-threaded operating system is built into the computer, it is possible to run the GA in the background. It is possible that, in general, these parameters of the ACS will need to be calculated once - when calibrating it in laboratory conditions or in case of semi-natural trials. Additionally, it is possible to complex GA with some algorithm of minimization of functions of many variables (for example, gradient methods [2]), with the help of which one can simulate the process of self-learning or adaptation between standard GA procedures: selection, mutation, crossing-over.
However, one serious problem still remains. Noises - stochastic processes. Therefore, it is difficult to evaluate anything other than the stability of a regulator and a closed system analytically. A statistical approach involves working with large data samples. As a result, the calculation of the fitness function leads again to a large number of calculations.
Once I had to simulate the process of gas condensation on a mirror surface and determine the parameters of parabolic partial differential equations through the optimization of the functional by the method of the fastest descent. In this gradient method, it is required to calculate derivatives in all directions (partial derivatives) at each step of the simulation. Because I did not have an analytical solution of the equation, then I had to determine the derivatives numerically. At the same time, the process is distributed along the vertical axis, and numerical stability required to break this segment into a sufficiently large number of segments. As a result, a very large amount of computation was required. Saved a very low speed of the process. In the field of automatic control there is no such salvation.

Entertainment industry

This can be called my hobby. It is very interesting to observe the self-organization of the simulated artificial world. In publication [5], I came across the mention of a single game on a space theme, in which weapons evolve with the help of GA based on statistics of the use of “ancestral models”. And what if we apply the GA and the principles of cellular automata in the field of the MMORPG as a whole? The idea is ambitious, but extremely interesting. If all or most aspects of the gameplay can be tied to the GA, then we will get one global rule (equation) describing the universe. Let the game, but still ...
How do I see it at the concept level? The player creates an avatar with some basic set of genes. Each gene has a hierarchical packet structure and is used in character generation, and, possibly, locations. The genes contain the rules according to which new and new nodes are created for certain already generated nodes. Here we can understand anything under nodes (see the description of the procedure for generating graphs in [3]). Here is an example:
1. The gene responsible for the type of the skeleton of the character: vertebrate, invertebrate, etc., will be used for some basic (rudimentary?) State. The number (number of “attachment points” of the extremities) and the type of the extremities (in the octopus-like characters will have tentacles, in vertebrates, legs / hands / legs with bones, etc.) depends on this gene.
2. The gene of extremities - is used for skeletons of a certain type (a skeleton that has “place holders” for extremities). This gene, for example, may contain descriptions of basic parameters: relative length / thickness / strength, etc.
3. Muscle gene - the character's muscular system is created by it.
4. And so on ...
Recently I found out about the Google project, which is by the way to mention: Google Body Browser .
According to this conceptual model, you can implement the external, animated part of the game. That appeared on the screen skeleton. Here it is overgrown with meat, nerves, vessels, etc. Beautiful and interesting! Inside, this concept translates into something else.
There is some initial property system. Also in the form of genes, general rules are set, according to which some properties affect others, i.e. non-directional neural network, graph, etc. According to these rules and the current value of the character's DNA, the generation of its specific characteristics in the game begins: points of life, strength, dexterity, speed, intellect, etc. At the same GA, the character's evolution is tied.
" Got a lot of experimentation and earned levelap " (Lord of the Rings, translated from Goblin) ...
and instead of distributing the perks, the player chooses auto-evolution or manually corrects DNA, which is not fully open and partially deciphered (roulette game). Here you can apply the principle on which "NetHack" -like games are based. When creating a character, a new random set of correspondences is created between a specific gene and the corresponding codes of type, subtype, etc. At the beginning of the game, the user does not know anything about the DNA of his avatar. Gradually (with each level), the player learns more and more information about DNA. The death of an avatar must be permanent, but there may be several avatars. In this case, it is possible to try to generate the beloved "Tamagotch" again by the existing DNA record (partial).
In the end, a certain set of genes will determine the characteristics of the character (mentioned above), his reaction to certain events and conditions (another character is next to him or someone else’s; the “smell” of another character is sympathy or aggression, etc.), his features behavior - character and more. If all these characteristics are connected to each other through the genes in the DNA with a sufficiently “balanced” algorithm, then it will be possible to create an interesting gameplay.

Conclusion

This article contains only my thoughts. No clear results or categorical conclusions are presented. I have to use some of this, but something may turn out to be a “dummy”. Perhaps this will result in the creation of a software product. It’s too early yet. But I want to respond to a message like "maybe someone from the readers will continue to research this issue." In this spirit, the author expressed one of these articles. This topic is quite interesting to me and seems very promising. There is a lot of space for creativity.

Thanks for attention! Your questions, comments ...

Literature list

1. Vodicheva L.V. Improving the reliability and accuracy of strapdown inertial measuring unit with an excessive amount of measurements / L.V. Vodicheva // Gyroscopy and navigation. 1997. № 1. S. 55-67.
2. http://www.nsc.ru/rus/textbooks/akhmerov/mo/3.html
3. Live graphs
4. Review of evolution methods ...
5. habrahabr.ru/blogs/games/63967
6. habrahabr.ru/blogs/popular_science/84529