# Difference-Based Mutation Operation for Neuroevolution of Augmented Topologies +
## 2 Materials and Methods
### Proposed Mutation Operation  
The NEAT algorithm described above has proved itself to be highly competitive compared to other approaches, and found a variety of applications. However, it could be further improved by introducing new search operators, for example, more efficient crossover and mutation schemes. One of the main problems of NEAT is the lack of an efficient parameter-tuning algorithm. Most of the networks, including fully-connected, convolutional, LSTM and many others use backpropagation algorithm for parameter tuning, however, as long as NEAT generates new structures, often with cycles, applying backpropagation would require an automatic differentiation procedure for every new structure, and in many cases, it would be impossible, as the generated structure could be non-differentiable. Another way of solving this problem could be the application of direct search methods, which do not require derivative calculation. For example, evolutionary algorithms such as genetic algorithm [21], differential evolution [22], or biology-inspired, such as particle swarm optimizer [23] could be applied for weights tuning, as well as many others [24].  
However, the existing weights tuning methods have a major disadvantage: they usually tune the weights for one solution, and require quite a lot of computational resources for tuning. In this study, the new difference-based mutation (DBM) scheme is proposed, which does not require additional fitness calculations, and is inspired by the mutation, applied in differential evolution. The proposed difference-based mutation takes into consideration three randomly chosen individuals from the population with indexes \(r1\), \(r2\) and \(r3\), different from each other and the current individual index \(i\), and searches for the corresponding connection genes in them by comparing innovation numbers. The found positions of such numbers are stored in \(e_{i},e_{r1},e_{r2},e_{r3}\), as long as they could be stored in different parts of the chromosome. The genes which have the same innovation numbers and same weight values are not considered. If at least one innovation number is the same for all four individuals, and the weight values are different, then the mutation is performed to generate new weight values:  
\[w_{e_{i}}=w_{e_{r1}}+F\cdot(w_{e_{r2}}-w_{e_{r3}}), \tag{4}\]  
where \(F\) is the scaling factor, and \(w_{e}\) are the weights of corresponding individuals at positions indexed as \(e\). Figure 2 visualizes the identification of the same connections with different weights in DBM.  
Figure 2: Identifying same genes to perform the difference-based mutation.  
The idea behind the difference-based mutation is to use the information stored in the population about every weight coefficient, marked with innovation number, to allow efficient parameter search without additional fitness evaluations. The DBM only changed the weights which are present in several individuals, which means that they are probably important for the network performance.  
The proposed DBM approach was used together with other mutation operators described above, and the probability to use it was set to \(0.1\). Figure 2 shows that, for solutions are required to perform the difference-based mutation. In the example, each of them has the connection node with innovation number 84, and the weight values are different, which makes the DBM possible. Despite the fact there are connections with innovation numbers 0, 1 and 2, they have equal genes in the difference part, which makes DBM for these genes senseless.  
Figure 3 shows the result of DBM application to the solutions shown in Figure 2. In Figure 3 the highlighted connections have innovation number 84, and the first solution is considered as current, and the rest three are the randomly chosen ones. The scaling factor \(F\) is set to 0.5, so according to Equation (4) the resulting weight equals \(-0.3\).  
In the next section, the experimental setup is described, as well as the algorithm's parameters and received results.