## 4 The Proposed Genetic Algorithm
### The Proposed Improvement
Then, the derivation of the corresponding deployment population based on Algorithm 1. * On the other hand, after selecting excellent individuals out of the deployment population, the corresponding partitioning population should be extracted based on Algorithm 2. Then, crossover and mutation should be performed on these partitioning chromosomes and corresponding deployment individuals should be selected to produce a new deployment population. To summarize, Algorithm 3 shows the complete framework of the improved genetic algorithm in this paper. As mentioned above, if there are \(n\) candidate devices, each partitioning chromosome can directly derive \(n!\) different deployment chromosomes. To control the population size, the algorithm adopts a proportion \(p_{dc}\) (\(0<p_{dc}<=1\)). Then, it only needs to generate \(n!\times p_{dc}\) deployment chromosomes for each partitioning chromosome. ```
Input: a DNN model description model, a performance description of a group of candidate devices \(D\), initial partitioning chromosome population size \(PCN\), the proportion of the initial deployment chromosome population \(p_{dc}\), crossover probability \(p_{c}\), mutation probability \(p_{m}\), maximum number of iterations \(MAXGEN\), the number of consecutive occurrences of the same optimal value \(SVG\) Output: a deployment scheme \(dc\)
1 begin
2\(n\leftarrow\) number of candidate devices in \(D\)
3\(l\leftarrow\) number of layers in model
4\(latency[n][l]\leftarrow\) each DNN layer's execution times on each device in \(D\)\(PP\leftarrow\) randomly generate \(PCN\) partitioning chromosomes
5\(population\leftarrow\) generate \(n!\times p_{dc}\) deployment chromosomes for each partitioning chromosome in \(PP\)\(currentGen=0\)\(maxf=0\)while\(currentGen<MAXGEN\)do\(currentGen++\)\(OP\) = selection(\(population\))\(PP\leftarrow\) extract partitioning chromosomes from \(OP\)\(PP\)update \(PP\) through crossover and mutation\(population\leftarrow\) deployment chromosomes generated based on \(OP\) conforming to \(PP\)\(maxf=maxfitness(population)\)if\(maxf\) has appeared \(SVG\) times continuouslythen
6 break
7 end if
8
9 end while
10
11 end while
12
13 end while
```  
**Algorithm 3**The Framework of the Proposed Genetic Algorithm  
Algorithm 3 first predicts and stores the execution time of each DNN layer according to Equation (1) for calculating individual fitness (from line 2 to line 4). Line 5 and line 6 initialize a deployment population. The while statement from line 9 to line 19 is the main loop in the algorithm. First, line 10 updates the current number of iterations and line 11 selects outstanding individuals from the current population to \(OP\). Then, line 11 and line 12 extract the corresponding partitioning chromosomes from \(OP\) and perform crossover and mutation to generate a new partitioning population \(PP\). Line 14 constructs a new deployment population according to \(OP\) and \(PP\), each of which has a corresponding partitioning chromosome in \(PP\). In the end, the individual with the maximum fitness in the current population is resulted through a specified number of times consecutively as the stop condition. If so, the loop is exited. Otherwise, search is continued until the maximum number of iterations MAXGEN is reached. Finally, the algorithm returnsthe deployment chromosome corresponding to the current maximum fitness as the final optimal deployment scheme. According to the optimization objectives described in Section 3, the fitness function is defined as follows. \[fitness(dc)= \begin{cases}\frac{10^{5}}{\sum_{i=1}^{\alpha}\sum_{j=1}^{\alpha}4c _{ij}\times t_{ij}}&\text{if $dc$ satisfies all constraints}\\ 10^{-6}&\text{if $dc$ does not satisfy all constraints}\end{cases}  \tag{6}\]  
In the above fitness function, \(dc\) is the \(\alpha\) matrix in the formulated problem definition (shown in Equation (4)) for calculating the fitness of a specific deployment chromosome.