# A Hybrid Strategy Improved SPEA2 Algorithm for Multi-Objective Web Service Composition
## 4 Algorithm
### Breeding  
The MSPEA2+ algorithm shares the breeding process introduced in the SPEA2 [11]. The archive is defined as \(\overline{p}_{g}\). In each iteration, a batch of individuals selected by the sorting of fitness value is copied and stored in the archive.  
If the archive is insufficient, the remaining solutions from the original set are sorted by \(R_{i}\), and the top-ranking solutions are added to the archive until the set's satisfaction. If the obtained solutions exceed the archive's capacity, solutions are gradually removed by deleting the solution with shortest \(\delta_{k}^{g}\) until satisfaction is reached. The fitness calculation is performed according to the following formula:  
\[\left\{\begin{array}{l}R_{i}=\sum\limits_{j\in P_{g},j\sim i}\ S(j)\\ D_{i}=\frac{1}{\sigma_{i}^{k}+2}\\ F_{i}=R(i)+D(i)\end{array}\right. \tag{6}\]  
where \(S(j)\) is the number of individual \(\mathcal{L}_{j}^{g}\) domains, \(\sigma_{i}^{k}\) is the \(k_{th}\) smallest distance between \(\mathcal{L}_{j}^{g}\) and every individual in \(p_{g}\); in this paper we take \(k\) as \(\sqrt{N+\sqrt{N}}\).  
The mating pool is defined as \(M_{g}\), and individuals are selected through tournament selection without replacement to fill the mating pool.  
In SPEA2+ [39], to prevent the loss of information during the tournament selection process, all archives are saved for the next iteration, ensuring the retention of optimal solutions. The process is effective for the WSCP based on WM. However, as discussed in Section 4.1, the information of the combinatorial structure is not preserved in individuals during genetic processes. As a result, many solutions generated by crossover and mutation may not satisfy the input-output dependency constraints after decoding. Consequently, the population quickly converges to a small set of solutions, stuck in local optima.  
Figure 3: Example of encoding and decoding.  
Based on this, our algorithm incorporates father-child generation selection, which has been proven to be highly effective in NSGA2 [40]. By merging the currently generated parent generation with the previous generation and sorting by SPEA2 fitness, we select the first \(n\) (size of population) solutions with smaller fitness, guaranteeing continuously approaching iteration of the optimal solution in our algorithm.  
```
0:\(N\) (Population size); \(\overline{N}\) (Archive size); \(g_{max}\) (Maximum number of generations);
0: A (Non-dominated set);
1: Initialize population \(p_{g}\) of permutations \(\mathcal{L}_{i}^{g}\) and create the empty archive \(\overline{p}_{g}\) (where \(i=1,2\), \(\ldots\), \(m\) and \(g=0\));
2:While\(g\leq g_{max}\)do
3: Calculate fitness values of individual in \(p_{g}\);
4: Copy all nondominated individuals in \(p_{g}\) to \(\overline{p}_{g}\);
5: Adjust the size of \(\overline{p}_{g}\) to \(\overline{N}\) by fitness sort or \(\sigma_{i}^{k}\);
6: Perform binary tournament selection on \(\overline{p}_{g}\) in order to fill the mating pool \(M_{g}\);
7:For each individual \(\mathcal{L}_{i}^{g}\) from \(M_{g}\), do
8: Perform neighbor crossover and mutation to \(\mathcal{L}_{i}^{g}\) and set it to \(p_{g+1}\);
9:End for;
10:For each individual \(\mathcal{L}_{j}^{g}\) from \(p_{g}\), do
11: Perform preference crossover and mutation to \(\mathcal{L}_{j}^{g}\) and set it to \(p_{g+1}\);
12:End for;
13: Merge \(p_{g}\) and \(p_{g+1}\) to \(p_{g+1}\) and caculate fitness of \(p_{g+1}\), adjusting \(p_{g+1}\) size by choosing \(N\) individuals with better fitness;
14:End while;
```  
**Algorithm 1** MSPEA2+ Main Loop