# Utility-Centric Service Provisioning in Multi-Access Edge Computing
## 4 Proposed Nested-Genetic Algorithm
Then if the mutated **x** does not exist in the population, conduct the _Inner-GA (Algorithm 2)_ to find the best request scheduling **y*** for the new **x**. 2.e. ** Replace the current generation with the new one filled by both the elite and offspring. UNTIL the population converges or reaching the maximum number of iterations \(outerMaxIter\). ### Chromosome and Initialization

In our algorithm, the chromosome of a service placement individual \(\mathbf{x}=\{x_{sn}\in\{0,1\}|s\in\mathcal{S},n\in\mathcal{N}\}\) is represented by \(|\mathcal{N}|\) blocks of \(|\mathcal{S}|\) bits each, one block for each MEC node \(n\in\mathcal{N}\), and one bit for each service \(s\in\mathcal{S}\). As such, it can be encoded as a binary vector of size \(|\mathcal{N}|*|\mathcal{S}|\), where the value of gene \(x_{sn}\) located at \((n-1)*|\mathcal{S}|+s\) indicates whether service \(s\) is placed on MEC node \(n\) (1) or not (0). Meanwhile, the chromosome of a request scheduling individual \(\mathbf{y}\) is encoded as an integer vector of size \(|\mathcal{U}|\), in which the value of gene \(y_{u}\) specifies where to schedule the user \(u\in\mathcal{U}\). The chromosome of a service placement and a request scheduling individual are shown in Figure 4a and Figure 4b, respectively. Figure 4: Chromosome representation. (**a**) Service placement individual \(\mathbf{x}=\{x_{sn}\in\{0,1\}|s\in\mathcal{S},n\in\mathcal{N}\}\); (**b**) Request scheduling individual \(\mathbf{y}=\{y_{u}\in\mathcal{H}_{u}|u\in\mathcal{U}\}\), \(\mathcal{H}_{u}=\{0\}\cup\{n\in\mathcal{N}|x_{sn}=1\}\). The initial population (i.e., initialization in Algorithms 1 and 2) is generated randomly but within the constraints of Equation (7). Specifically, the Outer-GA in Algorithm 1 initializes the population of service placement individuals within the storage constraint Equation (7b). We loop over each block (MEC) of the vector and assign value 0 or 1 randomly to each bit (service) of the block until the storage demand of services assigned value 1 exceeds the capacity of the MEC. Then the remaining bits in the block is assigned value 0. The Inner-GA (i.e., Algorithm 2) initializes the population of request scheduling individuals according to a given service placement solution. Let \(\mathcal{H}_{u}=\{0\}\cup\{n\in\mathcal{N}|x_{s_{u}n}=1\}\) denote the set of hosting nodes of the service \(s_{u}\) requested by user \(u\). Here, \(\{0\}\) represents the core cloud, which is assumed to host all services. Then in the chromosome of \(\mathbf{y}\), each gene \(y_{u}\) takes a random element from the corresponding set \(\mathcal{H}_{u}\). A complete solution to the JSPRS problem contains a service placement and a request scheduling individual. To evaluate how fit each solution is, the fitness function is defined according to the objective function in Equation (7), which is to maximize the total utility of all users. Hence, \(Fitness=\sum\limits_{u\in\mathcal{U}}W_{u}\). Once the initial population is created, the GA evolves the generation iteratively by applying the GA operators, i.e., selection, crossover, and mutation for the reproduction process. In each iteration, the selection operator is applied to maintain the parents, and then the crossover and mutation operators are applied to the parents to produce the offspring. These operators will be described in detail next. ### Selection

For the selection operation, we adopt tournament selection, which is the most popular selection method in GA due to its efficiency and ease of implementation [46]. In tournament selection, we pick a few individuals at random from the population, and these individuals compete against each other. The one with the best fitness wins and is selected as a parent for producing offspring. The number of individuals competing in a tournament is referred to as tournament size. We also adopt elitism mechanism, which allows the fittest individuals from the current generation to carry over to the next, unchanged.