A modification of the NEAT algorithm is proposed through the use of a mechanism for changing the level of mutations. At the same time, both the weight coefficients and the number of neurons in the hidden layers and the connections between them change. For the task of modelling the XOR operator, a significant acceleration of the training of a neural network was obtained.
Among the algorithms aimed at solving these issues, one of the basic ones is the NEAT (NeuroEvolution of
Augmenting Topologies) genetic algorithm [
The entire configuration of the neural network in the form of a linear representation of neurons and the connections between them is used as the genome in the NEAT algorithm. The initial conditions for the genome are set in the form of a minimal configuration of the neural network and its size increases as it learns. To control the expandability of the network, each element of the genome (neurons and the connections between them) is assigned an innovative number that allows you to take into account the moment this element appears in the genome and, accordingly, the number of iterations of the learning algorithm during which this element is part of the given genome. The presence of an innovative number allows us to differentiate elements of genomes (genes) depending on the history of their appearance in the genome. Genes are called matching if they have the same innovation numbers. If the numbers are different, then the genes are called disjoint if the number of one lies in the range of the number of innovations in the genome of the other gene, or redundant if the number of one is outside this range. When a new genome is formed from matching genes, one of them is randomly taken from any parent, and redundant and disjoint genes are taken from the parent with a large value of the quality function (fitness function). Thus, the NEAT algorithm produces a crossover without using the function of assessing the complexity of the current topology and is aimed at ensuring the predominance of genes with a positive effect over random genes.
Since the introduction of new structural elements in the short term usually worsens the importance of the fitness function, and a positive effect is achieved after appropriate weighting, the NEAT algorithm uses innovative numbers to form niches for genomes with structural innovations and having similar topologies. Moreover, over a given number of iterations, genomes compete with each other only within niches, and not with the entire set of genomes. This allows you to protect new topological elements while adjusting the weight coefficients of these elements. The network structure gradually increases as structural mutations occur, leading to a better value of the quality function.
The aim of this work is the further development of the NEAT algorithm to ensure a higher learning speed and achieve the resulting structure of a neural network with a small number of neurons and the connections between them.
The NEAT algorithm is based on the ideology of the genetic approach [10] and, accordingly, involves the
following steps [
5) Carrying out mutations of descendants due to changes in weighting factors, adding/removing connections between neurons, adding/removing neurons;
The variety of mutations used determines the complex nature of the movement of the learning algorithm on the surface of the quality function. The essence of the proposed modification of the NEAT algorithm is to add a mechanism for changing the intensity of mutations. It can be configured using the following four factors: 1. mutation_intensity - initial (and, subsequently, the current value of the intensity of mutations); 2.
mutation_intensity_max - a maximum allowable value of intensity; mutation_intensity_min - the minimum acceptable value of intensity, which is used when resetting the current mutation, when the network exceeded the previous value of the fitness function; mutation_intensity_step - step of the mutation intensity, by which the current intensity increases if the network during mutations remains at the same value of the fitness function.
The number of mutations that will be carried out on one individual will vary from 1 to the value of mutation_intesity, that is, the current intensity of mutations. If the network is stuck in the learning process, the mutation intensity will slowly increase, thereby increasing the number of mutations per generation in order to accelerate the growth of the network. As soon as the network reaches a structure of higher complexity, and the value of the fitness function begins to increase again, the intensity of mutations is reset to the minimum value, the speed of mutations decreases so that the network does not create random extra connections and neurons.
We will verify the performance of the modified NEAT algorithm by the example of modelling the logical
operation of “exclusive OR” (XOR) [
From a comparison of the configurations of the neural network at different stages of training, it can be seen that weights are first set up, and when the increase in the value of the fitness function slows down significantly, new neurons and connections are added. After that, setting the weights again becomes a priority.
To obtain averaged characteristics, the neural network learning process was run 10 times for the NEAT algorithm and the modified NEAT algorithm. The corresponding numbers of populations on which full network training was achieved in each of the implementations are shown in Figs. 5 and 6.
Fig. 5 - The number of the population on which the network is fully trained in modelling the XOR operator for each of the implementations when learning by the NEAT algorithm.
A comparison of the figures shows that the modified algorithm achieves complete network learning for a smaller number of populations. Since the work of learning algorithms begins with random initial conditions and uses random number generators when performing crossover and mutation operations, the NEAT algorithm in some experiments also required a small number of populations. Figure 7 shows the learning curves averaged over 10 implementations for the NEAT algorithm and the modified NEAT algorithm when the neural network simulates the operation of the XOR operator.
Fig. 7 - Comparison of the learning speed of the neural network when modelling the XOR operator with the
NEAT algorithm and the modified NEAT algorithm
A comparison of the learning curves shown in Figure 7 shows a significant advantage of the modified version of the algorithm.
Usually, in practice, two processes are distinguished - training and the use of a neural network. We can train many times on a special powerful computer. But, as a rule, it will be necessary to use it on another calculator, which is either less powerful or loaded with other tasks. Therefore, in practice, you need to make a certain amount of training and take the minimum configuration to use. Based on this, it is possible to compare the average number of experiments with their generation of populations in each (more precisely, the total number of generations) that must be performed in order to obtain the minimum configuration. Figure 8 shows the average number of generations needed to find a solution depending on the intensity of mutations, and Figure 9 shows the average number of generations needed to find the maximum of the quality function and the minimum configuration depending on the intensity of mutations.
Fig. 8 - The average number of generations required to find a solution depending on the intensity of mutations
Conclusions
Additional use of the mechanism for controlling the intensity of mutations in the NEAT algorithm can significantly increase the learning speed of the neural network in the task of modelling the XOR operator.
This, in turn, leads to a decrease in the total amount of computation required to fully configure the neural network and achieve a minimum configuration. However, due to the very large search space when solving complex problems by the NEAT algorithm, further development of this algorithm is necessary for the direction of increasing the learning speed and parallelizing operations for implementation on multiprocessor computers.