## 3 Methodology
### A GA-Based MSTs  
The GA-based MSTs is extracted from the CRPLOGARL [13] for WSNs and is presented in the sequel.  
Consider an integer weight \(w(e)>0\) that is associated with an edge \(e\in E\). Let \(w(T)\) be the sum of the edge weights in an MST of the network graph. The computational complexity of finding all MSTs of the network graph is exponential (that is, the problem is NP-hard). The approach GA is used to alleviate the NP-hardness of the All-MST algorithm. The distance-based MST is considered and is defined as the spanning tree having the minimum possible total cartesian distances between the connected vertices.  
The GA population is obtained from MSTs calculated with a baseline MST algorithm [46]. The baseline algorithms for finding the MST of a connected undirected graph are [PERSON]'s algorithm [47], [PERSON]'s algorithm [48], and [PERSON]'s algorithm [46]. [PERSON]'s algorithm and [PERSON]'s algorithm normally yield a network graph with only one MST. The reason is that [PERSON]'s and [PERSON]'s algorithms add the least edge to an existing tree while looking at the whole network graph until the MST is obtained. Subsequently, [PERSON]'s algorithm finds an MST by inputting any node as the root. This enables [PERSON]'s algorithm to generate more than one MST for a network graph that does not have distinct edge weights when using different nodes as the root [49]. Therefore the maximum MSTs that can be generated by [PERSON]'s algorithm for a network graph when varying the root node is the number of the graph nodes \(n\).  
The GA-based MSTs extracts different MSTs of the network graph as the initial population with the baseline [PERSON]'s algorithm by varying the root node. [PERSON]'s algorithm for generating the initial population runs in \(O(Nm\log n)\) time, where \(n\), \(m\), and \(N\) is the number of nodes, edges, and MSTs of the network graph \(G\), respectively. \(n\) is the upper bound of \(N\). The algorithm for finding the GA initial population is given in Algorithm 1.  
```
\(G(V,E)\) \(MSTs\) \(=\{\}\) \(j=0\) while\(j<n\)do  Select vertex \(j\) as the root node \(T=Prim(G,j)\) if\(T\
otin MSTs\)then \(MSTs\leftarrow T\) endif endwhile  Return MSTs
```  
**Algorithm 1** Algorithm to generate initial population for GA-based MSTs.  
The GA for generating MSTs for the number of generations, \(NG\) specified, is given in Algorithm 2.  
A chromosome in the initial population is an MST, with its genes as the graph edges [50]. The mutation operator and the crossover operator are used to evolve the initial population. This results in the generation of new MSTs as a result of the inheritance of some parents' edges.  
The fitness of the newly formed individual, \(T^{k}\) is measured with the objective function, which is the cost of the MST, \(T^{*}\) of the network graph as given in Equation (20).  
\[fitness(k)=\text{Poss}\bigg{[}\sum_{u,v\in T^{k}}d_{u,v}=\sum_{u,v\in T^{*}}d _{u,v}\bigg{]} \tag{20}\]  
The crossover process is achieved by selecting two individuals T1 and T2 randomly from the population as parents to create offspring for the subsequent generation. T1 and T2 are joined to create a sub-graph G1 of G by passing the union operation [51]. The individual form is an MST of G1 and the network graph G as shown in Figure 3. The number of times the crossover operator is carried out is determined by the crossover rate \(cr\).