## 4 Bi-Objective Optimization Allocation Problem Model and Algorithm
### Improved NSGA2 Based on Transcription Gene and Heuristic Recombination (INSGA2-TGHR)
#### 4.2.3 Crossover Operator: Heuristic Recombination  
Two-point crossover refers to the random setting of two crossover points in the chromosomes of an individual followed by partial gene exchange. The specific procedure of the two-point crossover is: setting two random crossover points in the coding strings of two individuals paired with each other; exchanging the part of chromosomes of two individuals between the set two crossover points.  
The recombination operator is a two-point crossover recombination operator based on the graph partitioning strategy, using the graph partitioning algorithm METIS [30] to group the workflows based on the amount of computation of subtasks in the workflow and the amount of data passed between subtasks. Each group consists of several subtasks, and the gene fragments corresponding to subtasks within the grouping are involved in the crossover as a whole when the recombination variation is performed. When subtasks are assigned to the same resource within a group, the data transfer between several subtasks takes place only in memory and does not involve network communication between computing resources, which effectively reduces the latency and cost of data transfer and thus exhibits a high degree of fitness, and this situation can be called \"advantageous gene fragment\". For example, task A of data preprocessing is input-heavy and output-heavy, while task B of data feature extracting is input-heavy and output-light type, if these two tasks are executed sequentially on the same computing unit. The process of A's output-heavy and B's input-heavy only needs to be executed in the memory of that computing unit, without network transfer. This significantly reduces the transfer latency and bandwidth costs. The process of Heuristic Recombination is to use the graph partitioning algorithm to partition A and B tasks into the same group, forming an \"advantageous gene fragment\" as a whole for crossover recombination.  
Then the \"advantaged gene fragment\" may be recombined to the new chromosome during the crossover process. If the entire new chromosome has a higher fitness, it will be reserved during the selection process. The \"ordinary gene fragments\" that are not assigned to the same resource may be replaced by \"dominant gene fragments\" in the process of crossover recombination, or may mutate in the process of mutation, and finally the algorithm will decide whether to reserve them for the next round of evolution according to the fitness.  
The process is represented in Algorithm 2 and Figure 6, where the METIS [30] algorithm is used for graph partitioning, first, two crossover sites \"x1\" and \"x2\" are obtained, and the indexes of other genes consistent with the grouping within the sites are obtained  
Figure 5: DNA Transcription RNA.  
according to the graph partitioning results. The above results were represented by the 0-1 array \"col\". The recombined newRNA1 uses the gene of RNA1 on the index with \"col\" of 1 and the gene of RNA2 on the index with \"col\" of 0. newRNA2 is exactly the opposite.  
```
input :RNA1,RNA2, \(G_{R}\) output :newRNA1, newRNA2
1 init newRNA1, newRNA2, col;
2 partitionResult \(\gets METISgraphpartition(G_{R})\);
3\(x1\gets random(0,len(\textsf{RNA1}))\),\(x2\gets random(0,len(\textsf{RNA1}))\);
4 if\(x1\geq x2\)then
5\(swap(x1,x2)\);
6 end if
7\(s\gets set(\textsf{partitionResult}[x1:x2])\);
8\(i\gets 0\);
9 while\(i\leq len(\textsf{partitionResult})\)do
10 ifpartitionResult[\(i\)] in sthen
11\(\text{col}[i]\gets 1\);
12 end if
13 else
14\(\text{col}[i]\gets 0\);
15
16 end if
17\(j\gets 0\);
18 while\(j\leq len(\text{col})\)do
19 if\(\text{col}[j]\equiv 1\)then
20 newRNA1[\(j\)]\(\leftarrow\)RNA1[\(j\)];
21 newRNA2[\(j\)]\(\leftarrow\)RNA2[\(j\)];
22
23 end if
24 else
25 newRNA1[\(j\)]\(\leftarrow\)RNA2[\(j\)];
26 newRNA2[\(j\)]\(\leftarrow\)RNA1[\(j\)];
27
28 end if
29
30 end while
```  
**Algorithm 2**HeuristicDoublePointRecombination