# Reconstruction of Ultra-High Vacuum Mass Spectra Using Genetic Algorithms
## 2 Materials and Methods
### Genetic Algorithms  
A GA is an extremum search algorithm for multivariate functions [32]. It is a global search algorithm; that is, it has the ability to locate the global extrema of these functions, as opposed to gradient descent algorithms (which are currently the most commonly used in this type of problem), which are only capable of finding local extrema [33]. GAs have been proposed as they hold several advantages in comparison with classical optimization methods, namely [34]:  
* They can run in parallel, unlike other optimization algorithms, and can therefore be implemented in modern massively parallel architectures;
* They demonstrate high performance in comparison to other approaches in problems with a large number of variables to be optimized;
* Information on the gradient of the function is not needed to obtain the extremum, and they can work with non-differentiable functions. In a standard GA implementation, five phases are considered:  
* Initial population: this corresponds to the initial values of the parameters with which the algorithm will start iterating. * Fitness function calculation: the function that defines the adjustment of the parameters to the objective pursued (search for an extremum, either maximum or minimum) of a given function. * Selection: the mechanism that establishes which elements of the population under consideration will be taken into account in the next steps of the algorithm. This stage uses the information obtained in the previous stage. * Crossover: a way to obtain new elements in the population from the existing ones by combining the genetic information of two parents to generate a new offspring. * Mutation: the stage of the algorithm where randomness is introduced in the elements of the population, being a key element in the search for the global extrema. Figure 1 illustrates the aforementioned steps graphically, and Algorithm 1 provides a pseudo-code of our implementation. ```
START  Generate the initial population  Compute fitness of individuals using Equation (3)  REPEAT  Selection of best fit using the Rank Selection method  Crossover using the Uniform Crossover method  Mutation using the Uniform Mutation method  Compute fitness of individuals using Equation (3)  UNTIL population has converged OR maximum number of generations reached STOP
```  
**Algorithm 1** Pseudo-code of the GA used  
In the present work, we have defined each individual to be the distribution of partial pressures among each one of the possible gases. This is represented by a vector (chromosome) of 80 components (genes). A gene is represented by a real number, representing the partial pressure of one of the possible gases considered. Consequently, the GA implementation used for this optimization problem is real-valued. As mentioned earlier, partial pressures take values spanning several orders of magnitude, which can become a problem with computational methods due to the sensitivity needed for low exponent values and the range for high exponent values. Because of this, Equation (2) was used to normalize pressures so that the typical values in individuals always fall between 0 and 1 and are uniformly distributed in that interval. The GA starts by initializing the population by generating \(N\) individuals with each one of the genes randomly initialized to a real number between 0 and 1. This is done to maximize the initial exploration space of solutions. The quality of an individual is  
Figure 1: Scheme of the different steps in a GA.  
determined by using a fitness function. In this case, a variation of MAE (mean absolute error) was used:  
\[\text{fitness}=-\sum_{i}\abs{I_{i}-C_{ij}P_{j}} \tag{3}\]  
where \(I_{i}\) represents the normalized intensity values for the measured spectrum for mass \(i\), \(P_{j}\) represents the partial pressure of gas \(j\), and \(C_{ij}\) is the fragmentation pattern matrix as defined in Section 2.1. A minus sign is introduced, as GA literature suggests representing better individuals with higher fitness values [35].