## 4 The Proposed Routing Strategy
### Routing Algorithm
```
input :\(G=(N,E,c)\) a satellite network graph, \(M=(o_{i},d_{i},D_{i})_{i\in I}\) a set of commodities output:a set of optimal paths that covers all commodities \(tolerance=5\);
2 Sort the commodities by decreasing flow demand;
3 foreach commodity \(i\)do
4 ifImplementation is requiredthen
5 commodity \(i\)'s candidate paths set \(P\) = \(Solve\_Linear\_Relaxation\_in\_Gurobi(G,M)\);
6 Sort the \(P\) in decreasing order of \(fitness(p)\);
7 select elite chromosomes and add to new population \(P_{new}\);
8 foreach candidate path \(p\) in \(P\)do
9 /* Parent Selection Operation \(*\)/
10 Using the **Roulette Wheel** to select two low fitness parents in \(P\);
11 /* Crossover Operation \(*\)/
12 \(P_{new}\gets P_{new}+\textbf{Crossover}(l,\textit{parents})\) Algorithm 2;
13
14 end if
15 foreach candidate path \(p\) in \(P\)do
16 /* Mutation Operation \(*\)/
17 \(P_{new}\gets P_{new}+\textbf{Mutation}(l,\textit{chromosome})\) Algorithm 3;
18
19 end for
20 sort population \(P_{new}\) in decreasing order;
21 if elite \(p\) same with previous generationthen
22\(tolerance\gets tolerance-1\);
23 iftolerance = 0 then
24 select best fitness path \(p\) as final;
25 break;
26
27 end if
28
29 end for
30
31 initialize tolerance to initial tolerance
32
33 end for
34
35 end for
36
37 end for
```  
**Algorithm 1**The GA heuristic  
The GA heuristic  
The GA treats the problem's solution set as a population and improves the solution quality through selection, crossover, and mutation operations, ultimately obtaining an approximate optimal solution. Therefore, it serves as a significant method in solving the aforementioned problem. \begin{table}
\begin{tabular}{l l} \hline \hline
**GA Term** & **Definition** \\ \hline Generations & The number of iterations \\ Fitness & The objective function to measure the quality of candidate paths \\ Chromosome & The candidate path \\ Gene & The inter-satellite link on the candidate path \\ Population & The number of candidate paths in each loop \\ Elites & The best fitness value path in each iteration \(e\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: GA terminology. ```
input :paternal chromosome parents,  limitation on the number of crossover \(l\) output :\(P_{new}\) offspring chromosomes
1 whilecrossover attempts \(\geq l\)do
2 applyloop crossover to selected parents;
3 ifoffspring solutions are validthen
4 add offspring to \(P_{new}\);
5 break ;
6
7 end if
8 crossover attempts \(\leftarrow\) crossover attempts \(-1\);
9 ifcrossover attempts = \(l\)then
10 add parents to \(P_{new}\);
11
12 end if
13
14 end if
15 return\(P_{new}\);
```  
**Algorithm 2**Crossover  
```
input :offspring chromosome chromosome chromosome, \(l\) limitation on the number of mutations output :mutated offspring chromosomes \(P_{new}\)
1 whilemutation attempts \(\geq l\)do
2 applymutation to chromosome;
3 ifmutated solution is validthen
4 add mutated chromosome to \(P_{new}\);
5 break;
6
7 end if
8 mutation attempts \(\leftarrow\) mutation attempts \(-1\);
9 ifmutation attempts = \(l\)then
10 add chromosome to \(P_{new}\);
11
12 end if
13
14 end if
15 ifno valid mutationthen
16 add original chromosome to \(P_{new}\);
17
18 end if
19 return\(P_{new}\);
```  
**Algorithm 3**Mutation  
Firstly, we use a uniform-length integer-coded method to encode the chromosomes. The number of genes on each chromosome corresponds to the number of ISLs present on the candidate paths. The gene located at each position within the chromosome represents a specific ISL. Secondly, the algorithm maintains high-quality genes by performing selection operations on the chromosomes. The fitness value serves as the basis for the selection process. We define the fitness equation as follows:  
\[fitness= \begin{cases}0\,\ \ \text{if cannot reach the destination.}\\ w_{1}\times(min(rc_{p}))+w_{2}\times(min(d_{p}))\,\ \ \text{otherwise.}\end{cases}  \tag{5}\]  
where \(min(rc_{p})\) represents the minimum remaining capacity among all candidate paths, and \(min(d_{p})\) represents the minimum delay among all candidate paths.