The concept of the practical use of genetic algorithms

Foreword

Two publications inspired the writing of the article:

• Live Counts
• Overview of evolutionary methods ...

I wanted to express my thoughts and my opinion on this issue precisely as a practitioner from programming "with a mathematical background." It will be a story “on the fingers”. I am not a specialist in genetic engineering and judge by surface descriptions of the functioning mechanisms of living cells and DNA.
Maybe it's for the best. The first impression of the “Survey of methods for the evolution of neural networks” was this: “it is rather difficult to write, but I did not find or missed the details of the practical implementation”. I had to dig further. In particular, I found a description of crossing-over - bitwise, which is mentioned in the publication mentioned above:
"... since the use of standard binary operators, as a rule, leads to the frequent appearance of non-viable solutions."In my understanding, it would sound like this: "such a method will not give the expected result of the cross, but will give rise to a mutant."
After reading the same descriptions of the implementations of some key points of the GA, I decided to state my vision of the problem.

Crossingover

The first thing I did not agree with was the implementation of crossing-over through a bitwise operation. For me, this method is unacceptable for at least two reasons:

• unstable result;
• uncontrolled mutation.

Intuitively, I understood that with a very high probability this approach would give a bad result, in any case 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. The result will almost certainly be an unstable self-propelled gun, as 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 a clear control of its parameters are very important.
My understanding of the crossover mechanismthat is. At a certain stage of cell division, DNA molecules from two homologous chromosomes (with the same sequence of allelic genes) come together to form a double helix (here I do not mean the spiral structure of the DNA itself). It is likely that at a certain place in this helix the “beginnings” of two allelic genes coincide (genes responsible for the same property; I may be mistaken) and there is also a chance that at this point two molecules will clump together, and after “unstick” with a 50% probability, the two molecules will 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. Research on the creation of DNA maps is even associated with this process. It is based on the conclusion from the description of the crossing-over mechanism: genes that are 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 common ground for crossing over should not be searched bit by bit, but between genes. There are “introns” in the DNA for this. Otherwise, the “black fly” and “blue fly” would have a baby with hooves.

Genes

The meaning and content of genes, depending on the task, can be different. In TAU, a gene can be understood as a certain high-level parameter of control quality (for example, the root of the characteristic equation of the transfer function, bandwidth, cutoff 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 gameplaytied to genetic algorithms (see below), the picture becomes even more beautiful. Here the genes must have a package structure in which the type of this gene is encoded - for which it is responsible (for example, a gene for forming the skeleton of an avatar or a gene for forming a relief of a location, or something else), what this gene creates (a behavioral rule, an instruction for generating the structure of something, the rule of the relationship of any characteristics of the object with each other, etc.), conditional blocks and parameter values. It turns out a kind of hierarchical coding of genes. In accordance with this scheme, we get genes of various lengths that are arrays of numbers, in the general case an array of bytes, although this is not necessary. It seems to me that such a scheme is closest to reality (to nature). Instead of a byte array, a gene can be represented as a structure containing enumerators (C #,
I also want to make a reservation about the peculiarities of DNA work in the case of bisexual (and maybe about three-, four-, etc.) reproduction, as well as about “dominant” and “recessive” ones.
Judging by the available information, there are chromosomes that are transmitted to the individual being born, depending on gender. If the sex of the conceived individual is "female", then one chromosome is transmitted, and if it is male, then another. How to select a set of genes contained in the "sex" chromosomes does not matter to me. And this idea itself is difficult to apply to the field of TAU. Theoretically, I can use this mechanism to adapt regulators to changing conditions: the driving mode has changed (for sports cars, for example, there is a city mode and a sports one) - I change the "gender" of the self-propelled guns. But you will need to store the settings and provide for a special algorithm for switching from one controller to another.
In games, such a mechanism is very well applicable. It is interesting to realize the “sex change” and look at the metamorphoses that occur with the character. In principle, it’s not very difficult to make a list of genes that will depend on gender. It will be important to ensure inter-gender balance. Thus, in the game it will be possible to abandon "racism" by playing with inter-gender 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 will like it, but someone will not.
About dominant and recessivegenes. It is generally accepted that recessive genes seem to sleep inside DNA (there are two of them in each of the chromosomes from each of the parents), i.e. if the dominant gene is received from the father, then the mother is asleep. It turns out this is not always true. In studies of genetic diseases, it was found that mutated recessive genes with pathology still have an effect on the body, but much less than in the case of their dominance. For the field of game development, this will make it possible to lay down the conditions in the core of the game under which recessive genes will participate in modifying gameplay on the basis of genetic diseases transmitted through the male or female line (sexually transmitted diseases - 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 processing of navigation information in conditions of high noise intensity in sensors. Therefore, the main questions for GA are the following: “is their practical application in the field of TAU possible” and “how beneficial will their use be”?
There is an approach to solving the problem of “stochastic estimation” of measured parameters through the creation of measuring blocks with information redundancy [1] (the number of sensors is greater than the number of measured parameters). In such cases, for example, a multidimensional Kalman filter (or an observing Lewinberger identification device) can be used to process signals from sensors. And here it is required to select (in the case of the Lewinerger NIE) or determine (in the case of the FC) the mathematical model of the dynamic object (sensor model). In addition to the parameters of the sensor model, we also need information about the measuring noise and the noise of the dynamic process (internal noise of the sensors) - the variance and covariance of the noise. All these parameters determine the filtration efficiency and the total passband of the measuring system. There are various methods for selecting these options. The most difficult thing is to choose the variance and covariance of the internal noise of the sensors. They cannot be measured.
But what if GA is used to select the optimal values? There are difficulties. Firstly, these algorithms require serious computing power. In fact, it is an exhaustive search of all possible combinations of values. So, as a student, I selected the parameters of the transfer function, i.e. cited the decision. I knew approximately what the frequency response should look like, it remained to select in MatLAb the parameters that they would draw this frequency response for me. But self-propelled guns are an on-board computer, a low-power and not very productive computer, or even just a combination of frequency filters on operational amplifiers. Secondly, implemented in the form of a computer-based ACS, it constantly calculates the control actions. If its power is small, then there will be no time to "play into 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 over time. If the operating system with multithreading is built into the computer, then you can start the GA in the background. Perhaps in general, these parameters of the self-propelled guns will need to be calculated once - when it is calibrated in laboratory conditions or during semi-natural tests. Additionally, the GA can be combined with some algorithm to minimize the functions of many variables (for example, gradient methods [2]), with which you can simulate the process of self-learning or adaptation between standard GA procedures: selection, mutation, crossingover.
However, one serious problem remains. Noises are stochastic processes. Therefore, it is difficult to evaluate analytically anything other than the stability of the regulator and the closed system. A statistical approach involves working with large data samples. As a result, the calculation of a fitness function again leads 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 optimization of the functional by the method of steepest descent. In this gradient method, it is required to calculate at each step of the simulation derivatives in all directions (partial derivatives). Because I did not have an analytical solution to the equation, then I had to determine the derivatives numerically. Moreover, 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 number of calculations were 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 the publication [5], I came across a mention of a game on a cosmic topic in which weapons evolve using GA based on statistics on the use of “ancestor models”. But what if we apply GA and the principles of cellular automata in the field of MMORPG as a whole? The idea is large-scale, but extremely interesting. If we manage to tie all or most aspects of the gameplay to the GA, then we get one global rule (equation) that describes the universe. Let the game, but still ...
How do I see this at the concept level? The player creates an avatar with some basic set of genes. Each gene has a hierarchical package structure and is used to generate a character, and possibly locations. The genes contain rules according to which more and more new nodes are created for certain already generated nodes. Here, nodes can be understood as anything (see the description of the graph generation procedure in [3]). Here is an example:
1. The gene responsible for the type of skeleton of the character: vertebral, invertebrate, etc., will be applied for some basic (rudimentary?) State. The quantity (the number of “attachment points” of the limbs) and the type of limbs depend on this gene (octopus-like characters will have tentacles, vertebrates will have paws / arms / legs with bones, etc.).
2. Gene of limbs- It is used for skeletons of a certain type (a skeleton that has "placeholders" for the limbs). This gene, for example, may contain descriptions of basic parameters: relative length / thickness / strength, etc.
3. The muscle gene - it creates the muscular system of the character.
4. And so on ...
Recently I learned about the Google project, which is worth mentioning here: Google Body Browser .
According to this conceptual model, you can implement the external, animated part of the game. A skeleton appeared on the screen. Here it is overgrown with meat, nerves, vessels, etc. Beautiful and interesting! Inside, this concept spills out into something else.
There is some initial system of properties. Also, in the form of genes, general rules are set according to which some properties affect others, i.e. undirected neural network, graph, etc. According to these rules and the current value of the character’s DNA, the generation of his specific characteristics in the game begins: life points, strength, dexterity, speed, intelligence, etc. The character’s evolution is tied to the same GAs.
" Got a lot of experimentation and earned level-up " (Lord of the Rings, translated from Goblin) ...
and instead of distributing perks, the player chooses auto-evolution or manually corrects DNA, which is not yet fully open and partially decrypted (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 particular gene and its 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 can be several avatars. At the same time, according to the available DNA record (partial), one can try again to generate the beloved Tamagoch.
Ultimately, a certain set of genes will determine the character's characteristics (mentioned above), his reaction to certain events and conditions (another character is nearby - his or her own; the “smell” of another character is sympathy or aggression, etc.), his features behavior - character and more. If all these characteristics are linked to each other through genes in the DNA with a sufficiently “balanced” algorithm, then it will be possible to create interesting gameplay.

Conclusion

This article outlines only my thoughts. Explicit results and categorical conclusions are not presented. Some of this I have to use, but some may be a "dummy." Perhaps this will result in the creation of a software product. It's too early to speak. But I want to respond to a message like "maybe one of the readers will continue to research this issue." The author of one of the mentioned articles expressed himself in this spirit. 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 ...

List of literature

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