# Utility-Centric Service Provisioning in Multi-Access Edge Computing
## 4 Proposed Nested-Genetic Algorithm  
The JSPRS problem is an Integer Nonlinear Programming (INLP) problem, which has been shown as NP-hard [45]. In this section, we introduce a metaheuristic solution based on genetic algorithm (GA) due to the popularity of GA in solving service provisioning problems [22; 28]. The major benefit of GAs is that they enable browsing a large search space to derive a global high-quality solution in polynomial time. Figure 3: Illustrative example. As the name implies, GA is inspired by natural evolution, which is the differential survival and reproduction of individuals over generations. Specifically, GA is an iterative process, in which each iteration is called a generation. Each generation consists of a population of individuals (or candidate solutions). Each individual is represented by its own chromosome, which is characterized by a set of variable components known as genes. The quality of an individual in the population is determined by a fitness function whose value specifies how fit the individual is compared to others in the population. Fitter individuals are given a higher chance to mate and produce offspring for the next generation while individuals with least fitness values are discarded to provide space for new offspring. By applying three genetic operators (selection, crossover, and mutation), an old generation can evolve into a new one with a population of both the elite (i.e., the individuals with the best fitness values) and offspring. This process is repeated until the population converges or reaching the maximum number of generations. The JSPRS problem includes two sub-problems: service placement and request scheduling, which are coupled since the MEC node, to which a request is scheduled, must have a replica of the requested service. To solve the JSPRS problem, we propose a Nested-Genetic Algorithm (Nested-GA) that consists of two genetic algorithms: Outer-GA and Inner-GA. The Outer-GA addresses service placement sub-problem while the Inner-GA addresses request scheduling sub-problem. Specifically, given a service placement **x**, we can obtain the optimal request scheduling solution **y*** that maximizes the total utility of users by using the Inner-GA as shown in Algorithm 2. Based on this optimal **y***, the optimal service placement solution **x*** can be obtained by the outer-GA of the Nested-GA as shown in Algorithm 1. The optimal result (**x***, y***) represents service placement and request scheduling policy. In the following, we will describe the concrete implementation of our proposed Nested-GA to solve the JSPRS problem. ``` Input: Input parameters of Equation (7); the parameters of the outer-GA \(popSizeX\), \(outerMaxIter\), \(eliteSizeX\), \(tourSizeX\), \(p_{xm}\); and the parameters of the Inner-GA. Output: Optimal service placement and request scheduling solution (**x***, y***). 1. Generate initial population of individuals for the JSPRS problem. 1.a. Initialize a population of \(popSizeX\) number of service placement individuals under the constraint Equation (7b), denoted as X_POP. 1.b. For each **x** in \(X\_POP\), conduct the _Inner-GA (Algorithm 2)_ to find the optimal request scheduling **y***, thus producing a complete solution (**x**, **y***) for the problem Equation (7). 2. REPEAT /Search for optimal service placement **x***/** 2.a. ** Find the \(eliteSizeX\) best individuals to be preserved (elitism mechanism). Add them to the parent set. 2.b. Select some other parents according to the principles of tournament selection with tournament size of \(tourSizeX\). 2.c. Choose two service placement **x1** and **x2** of the parent set randomly. Then apply the crossover operation to create two new offspring. Repeat this step until the number of offspring is equal to (\(popSizeX-eliteSizeX\)). 2.d. For each offspring **x** (service placement), do the mutation operation with the mutation probability \(p_{xm}\).