# GASP: Genetic Algorithms for Service Placement in Fog Computing Systems
## 4 Experimental Results
### Convergence Analysis of GAs  
The second critical analysis concerns the impact of the number of generations on the performance of the genetic algorithm. We carry out this analysis for the two previously presented two scenarios, that is, \(\rho=0.5\), \(\delta\mu=0.01\) and \(\rho=0.5\), \(\delta\mu=1\).  
In this, and the subsequent, evaluation, we consider the previously introduced discrepancy between the GAs and the solver (\(\epsilon\)). The value of \(\epsilon\) is measured at every generation for the GA (compared with the final output of the solver). This allows us to evaluate if the population is converging over the generations to an optimum.  
Figure 6 presents the results of this analysis. Specifically, we consider the evolution of \(\epsilon\) for the considered scenarios through 300 generations of the genetic algorithm. The graph shows also an horizontal line at the value of 1%: we consider that the genetic algorithm has reached convergence when \(\epsilon\leq 1\%\), and we consider the generation when this condition is verified as a metric to measure of how fast the algorithm can find a suitable solution. Note that, given the generally low value of \(\epsilon\), this convergence criteria returns values quite similar to the more common formulation where  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Parameter** & **Value** \\ \hline Strategy & _Simple strategy_ \\ Selection & _Tournament selection_ \\ Mutation & _Uniform Integer mutation_ \\ Crossover & _Uniform crossover_ \\ Population size & 200 \\ Generations & 300 \\ \(P_{mut}\) & 0.8\% \\ \(P_{cx}\) & 0.8\% \\ \hline \hline \end{tabular}
\end{table}
Table 2: Default genetic algorithm (GA) parameters.  
convergence is defined on the basis of being close (i.e., within 1%) to the best result achieved with the genetic algorithm itself.  
Comparing the three curves, we observe two highly different behaviors. On one hand, for the curve characterized by \(\delta\mu=1\) (curve marked with filled triangles in Figure 6), we observe a clear descending trend. At the opposite end of the behavior spectrum, the curve for \(\delta\mu=0.01\) (curve marked with filled squares), is characterized by a value of \(\epsilon\) that is very low right from the first generation and remains stable over the generations. The third curve (\(\delta\mu=0.1\), marked with filled circles) is similar to the case with \(\delta\mu=0.01\), even if a small descending trend can be observed in the first generations. The reason for this behavior can be explained considering the nature of the problem, where the objective function depends on two main contributions: the processing time (that depends mainly on the ability of the algorithm to distribute fairly the sensors among the fog nodes) and the network latency, that depends on the ability of the algorithm to map the sensors on the closest fog node. When \(\delta\mu=0.1\) and \(\delta\mu=0.01\), the impact of the second contribution is reduced by one or two orders of magnitude compared to the case \(\delta\mu=1\). Therefore, any solution that provides a good level of load sharing will be close to the optimum. As the genetic algorithm initializes the chromosomes with a random solution (with a uniform probability distribution), it may have one or more individuals from the first generation that provide very good performance. Further evolution of the population provides limited benefit (due to the reduced weight of the network latency component) in explaining the stable values of \(\epsilon\) over the generations. The case when \(\delta\mu=1\) is remarkably different as the two contributions to the objective function have a comparable impact. Therefore, the genetic algorithm must evolve through the generations to explore a large space of solutions to find good individuals letting the population evolve.