# Difference-Based Mutation Operation for Neuroevolution of Augmented Topologies +
## 2 Materials and Methods
### The General Scheme of the NEAT Algorithm  
The NEAT algorithm follows the main steps of every evolutionary algorithm, such as selection, crossover, mutation, but also uses specific operators, such as speciation. The main steps of NEAT are presented in Algorithm 1. ```
1:for\(gen=1\) to \(NG\)do
2: Initialize population \(P\) with minimal solutions, calculate fitness \(fit_{i}\), \(i=1,\ldots,N\)
3: Assign species numbers to every individual
4:for\(i=1\) to \(N\)do
5: Perform tournament-based selection (t = 2) to get index \(tr\)
6: Perform crossover between \(P_{i}\) and \(P_{tr}\), save offspring to \(O_{i}\)
7: Select the mutation operator to be used
8: Perform mutation on \(O_{i}\) and calculate fitness
9:endfor
10: Perform speciation of combined parents \(P\) and offspring \(O\) populations
11: Create new population from the representatives of every species
12:endfor
13: Return best found solution
```  
**Algorithm 1** NEAT  
In Algorithm 1 the following notations are used: \(NG\) is the total number of generations, \(P\) is the current population, \(O\) is the offspring population, \(fit\) is the fitness values array, \(N\) is the population size. The speciation mechanism of NEAT uses historical markings to determine the distance between solutions in the population, allowing to cluster individuals into several groups based on their structural similarity. The distance \(\delta\) between two networks is measured as \begin{table}
\begin{tabular}{c c} \hline \hline
**Mutation Type** & **Probability to Use** \\ \hline Add connection & 0.1 \\ Mutating random node & 0.15 \\ Connection removal & 0.15 \\ Connections merging & 0.2 \\ Adding node to connection & 0.1 \\ Assigning random weights & 0.2 \\ No mutation/Proposed approach & 0.1 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Probabilities of mutation operators in NEAT. the linear combination of the number of excess (E) and disjoint (D) genes, as well as the average of weights difference (\(\overline{W}\)) [9] :  
\[\delta=c_{1}*E/L_{g}+c_{2}*D/L_{g}+c_{3}*\overline{W}, \tag{1}\]  
where coefficients \(c_{1}\), \(c_{2}\) and \(c_{3}\) determine the importance of each factor, and \(L_{g}\) is the number of connections genes. The species in NEAT are numbered in the order of their appearance, and at the beginning, after initialization, the first individual is used as the representative of the first species. Next, all other individuals are tested to be similar to each representative, chosen randomly, using the distance metric. If an individual is close to the representative, i.e., \(\delta_{i}\) is less than the threshold value, then this individual is added to the species. If an individual is far from all existing species, it forms a new one and becomes its representative. The median distance between two individuals in the population was used as the threshold value for speciation. Once the speciation is performed for the joint population of parents and offspring, the fitness sharing mechanism is used to determine how many individuals of each species should be represented in the next generation. The adjusted fitness \(fit_{i}^{\prime}\) is calculated based on distance \(\delta\) to other individuals:  
\[fit_{i}^{\prime}=\frac{fit_{i}}{\sum_{j=1}^{N}sh(\delta(i,j))}, \tag{2}\]  
where \(sh()\) is the sharing function, set to 1 if \(\delta\) is below the threshold, and 0 otherwise. The number of individuals to be taken from each species is calculated as:  
\[N_{k}=\frac{\overline{fit_{k}}}{\overline{fit_{total}}}N, \tag{3}\]  
where \(\overline{fit_{k}}\) is the average fitness of species \(k\), and \(\overline{fit_{total}}\) is the average fitness of the population. First, the species with the best average fitness values are chosen, and the species with small average fitness are removed. The best representative of every species is always copied to the new population. According to [9], the speciation procedure allows protecting innovations, i.e., changes to the individuals which may be destructive currently, but deliver significant improvements later.