## 3 Genetic Algorithm for VNF-Mapping in Cloud/MEC RAN-Based 5G Architectures
### Genetic Algorithm for Service Mapping
The resulting individual undergoes a validation procedure in which the algorithm tries to translate the solution, emulating the creation of the number of VNF instances in every host as its chromosome specifies. If the individual created is not valid, i.e., if the algorithm cannot create the indicated instances of each VNF in every host, due to lack of IT or network resources, it discards the chromosome and creates a new individual  
Figure 2: Example of a chromosome. using the genetic operators (i.e., crossover and mutation). The algorithm repeats the process until achieving a desired population size. The last step is the calculation of two fitness parameters for each individual: The service blocking ratio and the percentage of required active CPU cores. The algorithm then selects the individuals with the best fitness performances to be the parent population of the following generation: GASM selects as preferred those individuals with a lower service blocking ratio and, to resolve the ties, it uses the number of actives CPU cores. The algorithm repeats this operation for as many generations as desired. ```
1:procedureGASM(trafficEstimation, populationSize, nextPopulationSize, numberOfGenerations)
2:\(solution\leftarrow\emptyset\)
3:\(population\leftarrow\emptyset\)
4:\(population\leftarrow generateAdHocIndividuals\)
5:whilesize(population)<populationSizedo
6:\(population\leftarrow population\cup generateRandomIndividual\)
7:\(discardNonFeasibleSolutions(population)\)
8:endwhile
9:\(i\gets 0\)
10:whilei<numberOfGenerationsdo
11:\(nextPopulation\leftarrow\emptyset\)
12:whilesize(nextPopulation)<nextPopulationSizedo
13:\(nextPopulation\leftarrow nextPopulation\cup crossover(population)\)
14:endwhile
15:\(nextPopulation\leftarrow mutation(nextPopulation)\)
16:\(discardNonFeasibleSolutions(nextPopulation)\)
17:\(nextPopulation\leftarrow population\cup nextPopulation\)
18:\(nextPopulationIndividualFitness\leftarrow fitnessEvaluation(nextPopulation)\)
19:\(population,populationIndividualFitness\leftarrow selectFiftestIndividuals(nextPopulation, nextPopulationIndividualFitness, size = populationSize)\)
20:\(i\gets i+1\)
21:endwhile
22:\(solution\leftarrow selectFiftestIndividuals(population, populationIndividualFitness, size = 1)\)
23:ifsolution\(\
eq currentlyEstablishedSolution\)then
24:\(establishVNF(solution)\)
25:endif
26:endprocedure
```  
**Algorithm 1**GASM  
At the end of the procedure, the algorithm returns the individual presenting the best performance in terms of service blocking ratio, or the solution with minor CPU core usage, if any tie appears. Hence, the result will represent the configuration of the NFV-enabled 5G network. ```
1:procedure crossover(population)
2:\(parentA\gets random(population)\)
3:\(parentB\gets random(population)\)
4:if\(parentA\
eq parentB\)then
5:\(randomPoint\gets random(0,size(individualA))\)
6:\(newIndividual[0,randomPoint-1]\leftarrow parentA[0,randomPoint-1]\)
7:\(newIndividual[randomPoint,size(parentB)-1]\leftarrow parentB[randomPoint,size(individual)-1]\)
8:endif
9:returnresult
10:endprocedure
```  
**Algorithm 2**Crossover  
```
1:proceduremutation(population, maxVNFPerLocation, mutationProbability)
2:forindividualinpopulationdo
3:\(i\gets 0\)
4:while!\(i\)<size(individual)do
5:ifrandom(0, 1) < mutationProbabilitythen
6:\(individual[gene]\gets random(0,\)maxVNFPerLocation)
7:endif
8:\(i\gets i+1\)
9:endwhile
10:endfor
11:returnpopulation
12:endprocedure
```  
**Algorithm 3** Mutation