# Difference-Based Mutation Operation for Neuroevolution of Augmented Topologies +
## 2 Materials and Methods
### Crossover and Mutation Operators Used in NEAT  
There were originally two main mutation types proposed for the NEAT algorithm, the first one is adding connections between nodes, and the second is adding nodes in between connections. In this, the set of operators was expanded, and the following mutation types were used:  
* Add connection: two nodes are selected randomly, and connected to each user. The weight of the connection is assigned randomly in the following way: first a random value from [0,1] is generated, and if it is smaller then 0.5, then the weight is set as a normal distributed random number with a mean equal to 0 and standard deviation set to 0.1 (\(normand(0,0.1)\)). Otherwise, the weight it set close to 1, i.e., \(normand(1,0.1)\). A new innovation number is assigned to the connection.
* Mutating random node: the type of operation performed in a randomly chosen node is changed to another one, and the new innovation number is assigned to the node. Only hidden nodes are mutating.
* Connection removal: if the structure of the network is not minimal, then a randomly chosen connection is deleted. The connections between inputs and outputs are never chosen.
* Connections merging: if the network structure contains at least two connections following the same path, i.e., having the same source and destination, then these nodes are merged together, and the weight value is assigned as the sum of weights. The new connection receives the innovation number of one of the merged.
* Adding a node to connection: one of the connections is randomly selected and divided into two, and a node is placed in between. The new node receives a new innovation number and operation, one of the weights is set to 1, while the other keeps the previous value. The connections receive new innovation numbers.
* Assigning random weights: every connection is mutated with a probability of \(1/NumberOfConnections\) the connection receives either weight, chosen from \(normand(0,0.1)\) or \(normand(1,0.1)\). Otherwise, the current value of the weight is used as a mean value to generate new as follows: \(w=normand(w,0.01)\), where \(w\) is the current weight value. With probability of \(1/NumberOfConnections\) each weight is either activated or deactivated.  
Each of the six described mutation operators is applied with certain probabilities, shown in Table 1.  
Only one of the mutation operators is used for every individual. If some of the conditions required for mutation are not satisfied, then no mutation is applied to an individual. Some of the mutations may result in an invalid structure of the neural network, i.e., there could be nodes not connected to anything or connections with a non-existing destination. To fix the invalid nodes or connections the purging operation is used, which removes them from the solution.  
The crossover in NEAT generates a new topology by combining two individuals. The resulting offspring is further used in the mutation step, described above. To perform the crossover, the innovation numbers are used to determine which nodes and connections are the same for both solutions, in particular, the two parents' mating genes are aligned, i.e., the parts of the chromosome having the same historical markers. The offspring \(s_{i}\) is composed of the genes, which are randomly chosen from the first or second parent, and the disjoint and excess genes are taken from the parent with higher fitness. The disjoint genes are determined as the genes which exist in one parent, but not the other, while there is still a common part further on in the chromosome. The excess genes are the tail genes of the parent individuals, which are only present in one of them. A more detailed description of the crossover in NEAT could be found in [9].