# Placement of IoT Microservices in Fog Computing Systems: A Comparison of Heuristics
## 3 Heuristics for Microservice Placement
### Genetic Algorithms  
Genetic Algorithms (GAs) are a class of heuristics used to solve a plethora of problems, including allocation problems in Edge and Fog computing [14; 15].  
The main characteristics of a genetic algorithm can be summarized as follows. A _chromosome_ represents a solution modeled as a sequence of _genes_, where each gene represents a single parameter of the solution. The system starts from a _population_ of _individuals_ that are initially generated at random and then evolve through _generations_. Individuals represent possible problem solutions.  
Considering the microservice allocation problem described in Section 2.2, a chromosome is set of \(M=\|\mathcal{M}\|\) genes, where \(M\) is the number of considered microservices. The value of each gene is an integer number \(\in[1,F]\), with \(F=\|\mathcal{F}\|\) being the number of fog nodes. To map the decision variable \(x_{m,f}\) on the genes, we can define the \(m^{th}\) gene as \(g_{m}=\{f:x_{m,f}=1\}\). The proposed definition satisfies Equations (2) and (5), ensuring that a microservice \(m\) is allocated on one fog node and not more.  
Each individual is associated with a _fitness score_ that is calculated through the objective function (Equation (1)) and the evolution of the generations is guided by the individuals' fitness scores. Due to constraints in (3) and (4) regarding the overload of fog nodes and the respect of SLAs, not every chromosome (solution) is acceptable. However, we prefer to let the population evolve while not excluding unacceptable solutions in order to exploit the capability of GAs to investigate a wide range of configurations. To take into account the two constraints, we choose to add corresponding penalty factors to the objective function, resulting in the following:  
\[obj^{*}(X)=\sum_{c\in\mathcal{C}}w_{c}R_{c}+P_{ol}+P_{SLA} \tag{11}\]  
where \(P_{ol}=S_{f}^{*}(1+\lambda_{f}-1*S_{f})\) if overload occurs, with \(S_{f}^{*}\) being an arbitrary high value of the service time for a fog node. In a similar way, we define a penalty for SLA violations as \(P_{SLA}=S_{c}^{*}(S_{c}/T_{SLA})\), with \(S_{c}^{*}\) representing an arbitrary high value of the service time of a microservice chain. The aim of the penalties is to eliminate individuals which violate the constraints. The choice to define both the penalties as proportional to the seriousness of the corresponding constraint violation is useful in cases where the population includes a great fraction of individuals with unacceptable values, as individuals with the worst values are the first to be eliminated.  
The generations evolve by applying different genetic operators, such as _mutation_, _crossover_, and _selection_. We exploit a _random mutation_ operator able to randomly modify a single gene in a chromosome; in this way, we can explore new possibilities in the solution space. Moreover, we apply a _uniform crossover_ operator which combines two parent individuals into two new individuals. As a last step, we apply a _tournament selection_ approach to identify individuals that should be included in the next generation based on their associated fitness score.  
For the implementation of the algorithm, we rely on the DEAP (DEAP: Distributed Evolutionary Algorithms in Python library [[https://deap.readthedocs.io/en/master/](https://deap.readthedocs.io/en/master/)]([https://deap.readthedocs.io/en/master/](https://deap.readthedocs.io/en/master/)), accessed on 24 June 2023). We tune the GA parameters through preliminary tests; specifically, the mutation probability is set to \(P_{mut}=0.8\%\) and the crossover probability to \(P_{cx}=0.8\%\). Moreover, we consider a population of 60 individuals with a number of generations equal to 600. This experimental setup is consistent with previous experiments in similar contexts [19].