## 4 Methodology
### Adaptive Scatter Search Algorithm for the MCDS Problem
#### 4.2.3 ASS-MCDS Algorithm  
The ASS-MCDS algorithm starts with a population \(P\) that contains \(P_{size}\) diverse trial solutions, which are generated by the diversification generation method using arbitrary trial solutions (or seed solutions) as inputs. During each generation, the quality of each solution in the population is evaluated by the fitness function _fit_ as defined in Equation (1). The ASS-MCDS method applies the LS Algorithm 1 to improve the generated solutions. From these generated solutions, the _RefSet_ with size equal to \(\textit{Ref}_{Size}\) is constructed of \(r_{1}\) high-quality solutions, which represent 80% of the \(\textit{Ref}_{Size}\), and \(r_{2}\) diverse solutions, which represent the remaining 20%. Thus, the size of the reference set is denoted by \(\textit{Ref}_{Size}(=r_{1}+r_{2})\). The construction of the initial reference set starts with the selection of the best \(r_{1}\) solutions from \(P\). These solutions are added to _RefSet_ and then deleted from \(P\). The minimum of the distances for each solution in \(P-\textit{RefSet}\) to the solutions in _RefSet_ is computed. Then, the solution with the maximum of these minimum distances is added to _RefSet_ and deleted from \(P\). A subset generation method operates on the reference set _RefSet_, to generate all pairs of reference solutions. Thus, the method would focus on subsets of size 2 resulting in \((\textit{Ref}_{Size}^{2}-\textit{Ref}_{Size})/2\) new subsets. The pairs in the new subsets are selected one at a time, so that the solution combination method is applied on each subset of solutions which is produced by the generation method to generate two trail solutions. The local search (Algorithm 1) is used to update the current population. During the implementation of the local search method, the connected domination solutions in a pool \(P_{s}\) is maintained. The reference set update method is applied once again. The updated reference set consists of 80% of the best solutions in the reference set solutions and 20% of the connected domination solutions in the \(P_{s}\). Trial solutions that are created as a combination of reference solutions are collected in a pool, denoted by \(T_{pool}\). After the implementation of both the combination method and the improvement method, the \(T_{pool}\) is filled and the reference set is updated. The ASS-MCDS algorithm terminates if none of the improved trial solutions are admitted to _RefSet_ under the rules of the reference set update method. The formal steps of the proposed method are stated in Algorithm 2 as well as Figure 1.  
```
1.Initialization. Set values of \(P_{Size}\) and \(\textit{Ref}_{Size}\). Set \(P_{s}\) to be an empty set. Generate an initial population \(P\) of size \(P_{Size}\). 2.Local Search. Evaluate the fitness of all solutions in \(P\) by using Equation (1). Then, apply Algorithm 1 to improve the solutions in \(P\). 3.Promising Selection Generation. Construct \(P_{s}\) by adding all connected domination solutions in \(P\). 4.Reference Set Update. Construct _RefSet_ by adding the best and the maximally diverse solutions from \(P\). 5.Subset Generation. Generating all pairs of the reference set solutions. 6.Solution Combination. Generate new trial solutions \(T_{pool}\). 7.Local Search. Improve the new solutions in \(T_{pool}\) using Algorithm 1. 8.Promising Selection Update. Update \(P_{s}\). 9.Reference Set Update. Update the _RefSet_. 10.Stopping Condition. Terminate the algorithm if there are no new solutions added to the _RefSet_. Otherwise, go to Step 5. The MCDS problem is usually a NP-hard problem [4; 13]. Therefore, there is no efficient algorithm to solve such a problem in its general form. The scatter search and meta-heuristics in general, are practical solvers and generally polynomial algorithms [25; 26]. The proposed SS-based methods follow the main structures of standard SS with additive procedures which also have a polynomial order performance. ## 5 Experimental Results

The ASS-MCDS method is programmed using MATLAB.