The other day, Youtube thought it would seem interesting to me a video called “AI Learns to play Hill Climb Racing”. It's funny, because a couple of minutes before that, I committed another change to the project, where my colleagues and I, in the breaks between work and work, solve exactly this problem. There is no “AI” in that video , however, it was not revealed - the author entertained the public with pampering with Box2D and calmed down on that. Nevertheless, I propose to consider this fact convincing evidence of the relevance of the topic and disassemble the structure of our rattles. 3r33333.  
3r33333.  
Briefly about the task: the vehicle - in our case it is either Alien, or the Zinger sewing machine on wheels, let's call it simply “agent” - must travel along the same directional noise dunes from start to finish. This is what an agent looks like in his sandbox: 3r3333315.  
3r33333.  
3r33333.  
An agent who has touched the back of the track or does not demonstrate proper zeal in moving towards the goal is removed from the track. 3r33333.  
][1] : First, he has established himself well in 3r to 329 important for the national economy. problems
secondly, by the time we started working on the project, we already had our own framework implementing NEAT. So, to be honest, we didn’t choose the solution method - rather, we chose a task where we could drive the ready one. 3r33333.  
3r33333.  
The figure shows an approximate scheme of the work of genetic algorithms: 3r33315.  
3r33333.  
3r33333.  
3r33333.  
It can be seen that any decent GA starts from the initial population (3r33256. Population 3r33259. - a set of potential solutions). Let us create it and at the same time get to know r3r346. first principle of NEAT [/b] . According to this principle, all agents of the starting population should have the simplest, “minimal” topology of the neural network. What does it have to do with topology? The fact is that in NEAT, along with the optimization of link weights, the network architecture is also evolving. This, by the way, eliminates the need to design it for a task. To go from simple architectures to complex ones is not only logical, but also practical (less search space), so you should start with the minimum possible topology - the authors of the method argued this way. 3r33333.  
3r33333.  
For our and all similar cases, this minimal topology is derived from the following considerations. To do something meaningful agent need:
 
3r33333.  
3r3173.  
3r3184. have environmental and state data,
 
3r3184. handle this information,
 
3r3184. interact with your world. 3r3185.  
3r3187. 3r33333.  
The first role is performed by 3r33256. sensors
- neurons of the input layer, which will provide useful information to the agent. Neurons
output. layer will process the data from the sensors. For the interaction with the environment are responsible
actuators
- devices that perform mechanical actions in response to a signal from "their" neuron of the output layer. The general principle of the initial configuration, thus, is the following: we determine the sensors and actuators, we get one neuron one per actuator, all the sensors and one more special neuron - 3r-3256. displacement neuron
(
Bias
, About it below) we connect connections with random weights to all neurons of the output layer. Something like this:
 
3r33333.  
3r3384. 3r33333.  
3r33333.  
[i] b - bias, s - sensors, o - neurons of the output layer, a - actuators, n - number of sensors, k - number of actuators 3r390. 3r33333.  
3r33333.  
And this is what the minimum NA looks like for our task: 3r33315.  
3r33333.  
3r399. 3r33333.  
3r33333.  
We have only one actuator - this is the engine of our wheeled creation. Shoot, jump and play the tune it does not know how. On the engine from a single neuron of the output layer (it is embarrassing to call it a layer), this is the value: 3r3155.  
3r33333.  
3r3108.

3r33333.  
Here w _b - the value of the weight of the connection going from the bias to the output neuron, multiplied by what each bias “produces”, i.e. +? s _i - normalized to the[0,1]range. value on the i-th sensor, w _i Is the value of the coupling weight from the i-th sensor to the output neuron, and f is the activation function. 3r33333.  
3r33333.  
As an activation function, we use this fantasy on the subject of softsign:
 
3r33333.  
3r3128. 3r33333.  
- it showed the best performance in the tests of a neuroevolutionary, well-known in narrow circles, ][2] . And comparing the soft-looking softness of the curves and the symmetry of the graph of this function with the angular-crooked Leaky ReLU makes no sense at all:
 
3r33333.  
3r33140. 3r33333.  
3r33333.  
This figure shows the agent's reaction to different values ​​of the activation function. With values ​​close to unity, the engine turns the wheels clockwise, accelerating the agent forward and strongly deflecting the body backwards, so that the mentally minded, but the brave quickly overturned on his back and die. At values ​​close to ? the opposite is true, and at a value of 0.? the agent motor does not work. 3r33333.  
3r33333.  
The same figure shows the role of the displacement neuron - the weight of the connection going from it to the neuron of the output layer is responsible, as follows from (1), for the magnitude and direction of displacement f (x) along the abscissa axis. The dotted line in the figure shows the graph of the activation function with w _b = -1. It turns out that even in the absence of a signal on the sensors, an agent with such a connection would rather quickly go back: f (x) = f (-1 + 0) ≈???r3r3151. b [/sub] have to look), but the benefits in the form of an additional degree of freedom from the possibility of such displacements outweighs. 3r33333.  
3r33333.  
Great, we introduced the neural networks of agents to a future initial population. But NEAT is a genetic algorithm, and it works from 3r33256. genotypes 3r3–3259. - the structures from which networks are formed or, more generally, 3r-3256. phenotypes
in the decoding process. Since we started with the phenotype, let's do everything backwards: we will try to encode the network presented above in the genotype. Here, one cannot do without the second principle of NEAT, the main essence of which is as follows: in the genotype, in addition to the structure of the neural network and the weights of its connections, information is stored about the history of the origin of all its elements. Except for this historical aspect, the phenotype is encoded in the genotype almost “one to one”, therefore, to illustrate the second principle for now, we will be fragments of neural networks. 3r33333.  
3r33333.  
The value of this principle is difficult to overestimate - it provides agents with the possibility of sexual reproduction. The topic is rather delicate, so we will first consider breeding
asexual
. It happens like this: a copy of all the genes of the agent is made, one of several types of changes is made on them - 3r-3256. mutations 3r33259. . In our version of NEAT, the following mutations are possible: 3r33333.  
3r33333.  
3r3173.  
3r3184. change in bond weight, 3r3185.  
3r3184. removing the link, 3r3185.  
3r3184. adding a link, 3r3185.  
3r3184. neuron insertion. 3r3185.  
3r3187. 3r33333.  
The first three types of mutations are simple and understandable without further explanation. The insertion of a neuron is shown in the figure below, it always happens in place of the existing connection, the connection is removed, and two new ones appear in its place: 3r3315.  
3r33333.  
3r3194. 3r33333.  
3r33333.  
Here h is
hidden
(
Hidden
) Neuron. 3r33333.  
3r33333.  
In sexual reproduction or
crossing
two agents are involved - parents, and as a result a third one appears - a child. In the process of the formation of a child's genotype, an exchange of, say, the same 3r33256 occurs. within the meaning of
genes or groups of genes of parents. The second principle is just needed to search for genes with the same meaning. 3r33333.  
3r33333.  
Imagine that we want to cross agents with genotypes that have undergone different series of mutations from the list above: 3r3315.  
3r33333.  
3r33333.  
3r33333.  
It seems logical to look for some common in terms of topology fragments of both parents and take a piece of these fragments for the genotype of the unborn child. This will be difficult, even NP -complicated in the general case, but suppose we managed. In this case, we find that in the parent on the right there are two subgraphs isomorphic to the graph of the left parent. In the picture below, the arcs of these subgraphs are highlighted in different colors:
 
3r33333.  
3r33333.  
3r33333.  
Which one to choose for recombination with left parent genes? 3r33333.  
3r33333.  
Referring to the history of the emergence of these genotypes: 3r33315.  
3r33333.  
3r33333.  
3r33333.  
Both ancestors of the parent agents started, as expected, with a minimum NS (T 3r3-3268. 0 [/sub] ). Their genomes somehow mutated there, and at time T ₁ in the ancestor of the left parent, a hidden neuron was inserted into the link s 3r-3268. 1 [/sub] -> o. At this dramatic moment, the genes encoding the s3r-3268 connections. 1 [/sub] -> h and h -> o, acquire their meaning in the ancestor of the left parent:
communication substitution s ₁ -> o
. 3r33333.  
The s _{genes found exactly the same meaning. 1} -> h ₁ and h ₁ -> o in the genotype of the right parent at time T 3r-3268. 2 [/sub] . The further destinies of our ancestors are not particularly interested in us - we already know what we can mix with: 3r3333315.  
3r33333.  
3r33333.  
3r33333.  
The next time it will be possible to make out how to write a genetic history, all the more so since we have some small finds in this area, they are connected with the adaptation of the original technique to a stable reproduction scheme. 3r33333.  
3r33333.  
It's time to wrap up. The article began with Youtube - they will complete it. In the early version of the simulator, a colleague who wrote the code for generating the track ended it with nothing, a bottomless abyss. The reaction of a neural network that has evolved for a long time in the presence of earthly earth under the wheels can perhaps be called a “rupture of the pattern” for such a design of its small universe: 3r33333.  
3r33333.  

3r33333.  
An extensive collection of other anecdotal stories from the lives of cybernaturalists can be found in ][3] . 3r33333.  
3r33333.  
3r3303. Sources 3r3304. 3r33333.  
3r33333.[1]3r33333. K. O. Stanley and R Miikkulainen, "Evolving Neural Networks through Augmenting Topologies" Evolutionary Computation, vol. 1? no. ? pp. 99-12? 2002. 3r33315.  
3r33333.[2]3r33333. 3r33333. C. Green, “A Review of Activation Functions in SharpNEAT,” 19 June 2017.
3r33333.  
3r33333.[3]3r33333. J. Lehman et al, “The Surprising Creativity of the Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities,” arXiv: Neural and Evolutionary Computing, 2018.