## 4 Methodology
### Adaptive Scatter Search Algorithm for the MCDS Problem
#### 4.2.3 ASS-MCDS Algorithm
Figure 4 shows how the performance of ASS-MCDS in acquiring the best domination is related to the size of the reference set \(Ref_{Size}\). Thus, increasing the \(Ref_{Size}\) increases the ASS-MCDS performance. However, this resulted in more time consumption as summarized in Figure 5, where ASS-MCDS1, ASS-MCDS2, and ASS-MCDS3 are the ASS-MCDS with \(Ref_{Size}\) equal to 10, 15, and 20, respectively. \begin{table}
\begin{tabular}{l l c} \hline \hline
**Parameter** & **Definition** & **Value** \\ \hline \(P_{Size}\) & Population size & \(60+(V_{n}/200)\times 20\) \\ \(n_{step}\) & Number of iterations in local search & 10 \\ \(Ref_{Size}\) & Size of reference set & 15 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Parameter setting. Figure 3: The performance of the ASS-MCDS with different \(n_{step}\) values. Figure 2: The performance of the ASS-MCDS with different \(P_{Size}\) values. The performance of the fitness function weights \(\alpha\), \(\beta\), and \(\gamma\) of Equation (1) was studied using several setting values. The obtained best settings of these parameters are the following values:

* **Setting 1:**\(\alpha=\
icefrac{{1}}{{2}}\), \(\beta=\
icefrac{{1}}{{4}}\), and \(\gamma=\
icefrac{{1}}{{4}}\);
* **Setting 2:**\(\alpha=\
icefrac{{1}}{{4}}\), \(\beta=\
icefrac{{1}}{{2}}\), and \(\gamma=\
icefrac{{1}}{{4}}\);
* **Setting 3:**\(\alpha=\
icefrac{{1}}{{4}}\), \(\beta=\
icefrac{{1}}{{4}}\), and \(\gamma=\
icefrac{{1}}{{2}}\);
* **Setting 4:**\(\alpha=\
icefrac{{1}}{{3}}\), \(\beta=\
icefrac{{1}}{{3}}\), and \(\gamma=\
icefrac{{1}}{{3}}\). The performance of these different settings of the fitness function weights is shown in Figure 6 using four different networks. There is almost no major difference in results obtained by these values but the

Figure 4: The performance of the ASS-MCDS with different \(Ref_{Size}\) values. Figure 5: The average processing time of the ASS-MCDS with different \(Ref_{Size}\) values. best one is the fourth setting. Using this best setting of equal weights, the fitness function defined by Equation (1) takes the following formula after adjusting its weight parameters. \[fit(x)=\frac{1}{3}\left[\frac{V_{D}}{V_{n}}+\frac{C_{n}}{\sum_{i}^{V_{n}}x_{i}}+ \frac{V_{n}-\sum_{i}^{V_{n}}x_{i}}{V_{n}}\right]. \tag{3}\]

For simplicity, the fitness function form can be equivalently rewritten as:

\[fit(x)=\frac{V_{D}}{V_{n}}+\frac{C_{n}}{\sum_{i}^{V_{n}}x_{i}}+\frac{V_{n}- \sum_{i}^{V_{n}}x_{i}}{V_{n}}. \tag{4}\]

### Numerical Results

In this section, the algorithmic performance of the proposed method introduced in Algorithm 2 is investigated by comparing the results of ASS-MCDS against the results of other benchmark methods presented in [1; 11; 12; 21]. To measure the performance of the ASS-MCDS, two different quantities are used to make comparisons:

* Minimum number (Min. ): This measure gives the minimum connected domination number found in all independent runs and represents the minimum number of connected nodes in the best solution;
* Average number (Avg. ): This measure calculates the average number of dominant connected nodes in best solutions found in independent runs. The maximum number of iterations for the ASS-MCDS is 20 for each graph. The comparison experiment is set to test ASS-MCDS results with network instances described in Table 1. Table 3 displays the comparison results obtained by the ASS-MCDS against the three following methods:

* A greedy randomized adaptive search procedure [21];
* Ant colony optimization algorithms [1];
* The memetic algorithm [11; 12]. Figure 6: The performance of the different settings of the fitness function weights. Table 3 displays the minimum number (Min.) and average (Avg.) values of the network instances obtained by applying the ASS-MCDS and the above-mentioned three methods. Generally, it can be concluded that the proposed method (ASS-MCDS) acquired the best results with the network instances including in instances with a large number of wireless nodes.