# An On-Orbit Task-Offloading Strategy Based on Satellite Edge Computing
## 4 Algorithm Introduction and Simulation Analysis
### Algorithm Convergence Analysis  
[PERSON] et al. and [PERSON] et al. proved that the typical genetic algorithm and the BPSO algorithm are unable to converge to the global optima, respectively [29; 30].  
[PERSON] et al. proposed the rules for the random search algorithm to converge to the global optima with probability 1 [31], stated as follows:  
* Assumption (\(H1\)) \[f(D(x,\xi))\leq f(x)\text{ {and if} }\xi\in S,f(D(x,\xi))\leq f(\xi),\] (24) where \(D\) is the function that generates the solution to the problem, \(\xi\) is the random vector generated from the probability space \((R^{n},B,\mu_{k})\), \(f\) is the objective function, \(S\) is a subset of \(R^{n}\), denotes the constraint space of the problem, \(\mu_{k}\) is the probability measure on \(B\), and \(B\) is the \(\sigma\)-domain of a subset of \(R^{n}\).
* Assumption (\(H2\)) \[\text{ {For any} }(\text{{Borel}})\text{{subset} }A\text{ {of} }S\text{ {with the measure }}v(A)\ >0,\text{ {we have that}}\prod_{t=0}^{\infty}[1-\mu_{t}(A)]\ =\ 0,\] (25) where \(\mu_{t}(A)\) is the probability of generating \(A\) from the measure \(v(A)\).
* Convergence Theorem (Global Search) Suppose that \(f\) is a measurable function, \(S\) is a measurable subset of \(R^{n}\), and \((H1)\) and \((H2)\) are satisfied. Let \(\left\{x^{t}\right\}_{t=0}^{\infty}\) be a sequence generated by the algorithm. Then, \[\lim_{t\to\infty}P\left[x^{t}\in R_{\varepsilon}\right]=1,\] (26)where \(P\big{[}x^{t}\in R_{\varepsilon}\big{]}\) is the probability at step \(t\), and \(R_{\varepsilon}\) is the global best points set. The theorem shows that for any random search algorithm, it can converge to the global optimal with probability 1 as long as it satisfies Assumptions \(H1\) and \(H2\).  
Next, we will analyze whether the GABPSO algorithm satisfies the above assumptions.  
In the GABPSO algorithm, the solution sequence is \(\{p_{g,t}\}\), where \(t\) is the number of evolutionary generations, and \(p_{g,t}\) is the best particle position at the \(t\)th generation. The function \(D\) is defined as  
\[D\big{(}p_{g,t},x_{i}(t)\big{)}=\left\{\begin{array}{l}p_{g,t},f\big{(}p_{g, t}\big{)}\leq f(x_{i}(t))\\ x_{i}(t),f\big{(}p_{g,t}\big{)}>f(x_{i}(t))\end{array}\right. \tag{27}\]  
Then, it is easy to prove that it satisfies Assumption \(H1\).  
To satisfy Assumption \(H2\), the union of the sample space of a particle population of size \(N\) must contain \(S\), i.e., \(S\subseteq\bigcup_{i=1}^{N}M_{i,t}\), where \(M_{i,t}\) is the support set for the sample space of \(i\)th particle at the \(t\)th generation. It has been shown that the basic PSO algorithm does not satisfy Assumption \(H2\)[32; 33]. In the PSO algorithm, as the number of iterations \(t\) increases, \(v(M_{i,t})\) and \(v\Big{(}\bigcup_{i=1}^{N}M_{i,t}\Big{)}\) decrease. Thus, \(v\Big{(}\bigcup_{i=1}^{N}M_{i,t}\cap S\Big{)}<v(S)\) is established, which means that there exists an integer \(t^{\prime}\) such that when \(t>t^{\prime}\), there exists a set \(A\subset S\) such that \(\sum_{i=1}^{N}u_{i,t}(A)=0\). This is not consistent with Assumption \(H2\).  
However, the GABPSO algorithm adds the crossover and mutation operations of the genetic algorithms. For a normally evolved particle, we set the union of its support set to \(\alpha\); for a particle recreated using crossover and mutation, we set the union of its support set to \(\beta\). Due to the randomness and variability of crossover and mutation operations, there must exist an integer \(t2\) such that \(\beta\supseteq S\) when \(t>t2\). Therefore, for the GABPSO algorithm, there must exist an integer \(t2\) such that \(\alpha\cup\beta\supseteq S\) when \(t>t2\). Define any Borel subset of \(S\) to be \(A=M_{i,t}\). When \(v(A)>0\), \(\mu_{t}(A)=\sum_{i=1}^{N}u_{i,t}(A)=1\), i.e., \(\prod_{t=0}^{\infty}[1-\mu_{t}(A)]=0\). Therefore, the GABPSO algorithm is satisfied by Assumption \(H2\).  
According to the Convergence Theorem, it is known that the GABPSO algorithm can converge to the global optima with probability 1.