Feature selection via a multi-swarm salp swarm algorithm

1.   Introduction

With the development of 5G, big data, blockchain, and other technologies, data volume in many fields shows a trend of geometric exponential growth. These data are often high-dimensional datasets with hundreds or even thousands of features, some of which are irrelevant, redundant, or noisy ^[1]. These features not only affect the performance of the learning algorithm ^[2], but also greatly increase the calculation cost. Feature selection (FS) aims to remove such irrelevant and redundant features from the original feature set while selecting the most effective ones. It plays an important role in improving algorithm performance and reducing computing costs. Therefore, it has been successfully used in medical analysis ^[3,4], diagnosis of cancer data ^[5,6], drug activity prediction ^[7,8], fault diagnosis ^[9,10,11], and so on.

According to evaluation criteria, FS methods are commonly divided into filter-based and wrapper-based approaches. The filter-based approach usually selects the optimal feature subset based on four metrics (distance, information, consistency, and dependency) during the evaluation process. It ranks features by computing the correlation between features and classes and the redundancy between features. Since the filter-based approach only needs to process datasets without employing a learning algorithm, it has high computational efficiency. The wrapper-based approach combines a search strategy with a learning algorithm for solving FS tasks. Compared with filter-based methods, wrapper-based methods can usually obtain better feature subsets with promising quality in the same tasks. However, wrapper-based approaches have the disadvantages of high time complexity and poor generalization ability. Therefore, many scholars have proposed hybrid approaches with combining filter-based and wrapper-based approaches.

To find the optimal feature subset, FS is treated as an NP-hard discrete optimization problem ^[12]. Therefore, it is impractical for high-dimensional datasets to find the optimal solution from all possible feature subsets by using a similar exhaustive search strategy. Assuming that a dataset contains $N$ features, then $2^N$ feature subsets need to be generated and evaluated to obtaining the optimal feature subset finally. As a result, traditional FS methods are no longer applicable to most data engineering tasks.

The swarm intelligence (SI) algorithm is inspired by simulating the interaction of certain groups of organisms in nature ^{[13,14,15,16]}. By simulating the characteristics of biological foraging, the SI algorithm can obtain better approximate solutions by conducting the strong random search in the search space. In view of this, more and more swarm-based optimization algorithms have been proposed, such as particle swarm optimization (PSO) ^[17,18,19], ant colony optimization (ACO) ^[20,21], whale optimization algorithm (WOA) ^[22], grey wolf optimization algorithm (GWO) ^[23], firefly algorithm (FA) ^[24], artificial bee colony algorithm (ABC) ^[25], and so on. As FS is an NP-hard discrete optimization problem, it is difficult to obtain the optimal solution. Considering the strong random search ability of swarm-based optimization algorithms, they have been employed to solve the FS problem successfully.

Inspired by the group behavior of salps in the ocean, the swarm-based Salp Swarm Algorithm (SSA) is proposed by Mirjalili ^[26]. The salps feed on phytoplankton in the water and move by inhaling and spewing seawater. Due to the advantages of concise implementation and fast convergence in most cases, SSA has been widely applied to solve feature selection problems in recent years. However, the existing algorithms based on SSA have problems such as premature convergence and low search efficiency.

To address the issue mentioned above, we propose a multi-swarm SSA (MSSA) to solve the FS problem. The main contributions of this work are summarized as follows:

1) The salp swarm is divided into three sub-swarms, aiming at maintaining the swarm diversity. When one sub-swarm falls into the local optimum, it will not affect the other two sub-swarms, thus maintaining the diversity of the whole swarm.

2) The updating models of leaders and followers are modified to improve the exploration ability of the MSSA. Based on three sub-swarms, the followers move towards the current optimal leader of the corresponding sub-swarm, so that salps of the swarm have different learning exemplars. In this way, MSSA can avoid premature convergence effectively.

3) An adaptive perturbation strategy (APS) is proposed to enhance the exploitation ability of MSSA. In APS, an adaptive parameter $per$ is designed to adjust the implementing frequency of the lens-OBL strategy and the SBX strategy during swarm evolution, which can help the swarm escape from the local optimum.

The remainder of this paper is structured as follows: Section 2 briefly reviews related work on SI algorithms and SSAs. The proposed MSSA is elaborated in Section 3. Section 4 shows the experimental setup. Section 5 provides experimental results and analysis. The final section concludes the study.

2.   Related work

2.1.   Classical SI algorithm

To solve optimization problems in the practical application fields, e.g., FS, many swarm-based algorithms have been proposed one after another. They include gravitational search algorithm (GSA) ^[27], bat algorithm (BA) ^[28], gray wolf optimization (GWO) algorithm ^[23,29], SSA ^[26], and so on. Especially, some of these algorithms have been used as search strategies for wrapper-based approaches.

However, these optimization algorithms may have problems such as premature convergence, falling into local optimization solutions, and too many parameters needed in the evolution process. Therefore, many scholars have improved these optimization algorithms. For example, Feng Wang et al. introduced a reinforcement learning strategy into PSO, which combines with the level competition mechanism to improve the search efficiency and convergence ability of the algorithm ^[30]. Ke Chen et al. proposed CUS-PSO based on the surrogate model ^[31], which uses the correlation among features to generate candidate particles, and then approximates their fitness values. Ghosh et al. proposed a hybrid algorithm based on ACO ^[32], which combines the wrapper-based approach with the filter-based approach. The hybrid algorithm can reduce the computational complexity by employing a filter for evaluating the candidate feature subsets. Yong Zhang et al. presented the TMABC-FS algorithm ^[33], which uses different search strategies for different roles of bees. In addition, many swarm-based approaches haven't been listed due to the limited space.

2.2.   Canonical SSA

Inspired by the group behavior of salps in the ocean, Mirjalili et al. presented the salp swarm algorithm (SSA) in recent years ^[26]. In SSA, the swarm of salps moves and forages in the form of a chain structure, and the roles of salps consist of leader and follower. The individual at the front of the salp chain acts as the leader, while the rest of the salps act as followers. The leader leads the movement direction of the whole salp chain, while the followers follow the previous leader. In this way, the leader searches for food sources, and followers move towards the leader gradually. This moving pattern enables the salp chain to have strong global exploration and local exploitation abilities. Like other swarm-based algorithms, the position of a salp is defined as a $d$-dimensional vector, where $d$ represents the dimension number of an optimization problem. Then, the swarm of salps can be defined as a $N\times d$ matrix, where $N$ represents the size of the swarm. The matrix is shown in Eq (2.1).

The leader updates its position according to Eq (2.2).

where $x_{j}^{1}$ represents the $j$th dimension of position vector denoting the first salp, which is the leader of salps. $F$ is the position of the food source. $c_{1}$ is an important parameter defined as Eq (2.3). It has the function of balancing exploration ability and exploitation ability of SSA. $c_{2}$ and $c_{3}$, which determine the step size and movement direction of the leader, respectively, are two random numbers in the range of [0, 1]. $ub_{j}$ and $lb_{j}$ represent the upper boundary and the lower boundary of the $jth$ dimension, respectively.

where $l$ is the current number of iterations and $L$ is the maximum number of iterations.

A follower updates its position according to Eq (2.4).

where $x_{j}^{i}$ represents the $j$th dimension of position vector denoting $i$th follower salp.

2.3.   Binary SSA (BSSA)

The SSA was first proposed to solve the continuous optimization problem. Since FS is a discrete optimization problem, SSA cannot effectively deal with it. To address the issue, binary SSA (BSSA) was presented in recent years. In BSSA, the components of position vectors need to be mapped into 0 or 1 after each iteration. The mapping model of position vectors is shown in Eqs (2.5) and (2.6).

where $x_{j}^{i}$ represents the $j$th dimension of position vector denoting the $i$th salp; $rand$ is a random number uniformly distributed in [0, 1]; sigmoid function $S$ represents the probability of selecting a candidate feature; $newx_{j}^{i}$ is the $j$th dimension of position vector denoting $i$th salp.

2.4.   The variants of SSA

Since it was proposed in 2017, SSA has attracted a lot of attention from many scholars. Mechanisms were introduced to improve the performance of SSA. According to different improvement directions, these modifications can generally be divided into three situations: parameter adjustment, learning model adjustment, and hybrid strategy.

1) Parameter Adjustment: From the beginning, SSA stood out from many swarm-based algorithms with fewer parameters and better performance. Therefore, parameters optimization of SSA has also become a core content, aiming at enhancing its performance. Rohit et al. proposed an adaptive SSA (ASSA) with time-varying parameters ^[34]. In ASSA, the parameter $c_{1}$ is adaptively adjusted according to the current number of iterations. This strategy can effectively control the process of the exploration and exploitation. Furthermore, considering that the search process of SSA is nonlinear and complex, Aljarah et al. assigned a variety of nonlinear parameter combinations to SSA, aiming at maintaining the diversity of swarm and bringing different search behaviors of salps ^[35]. In addition, $c_{1}$ and $c_{2}$ are important parameters controlling the movement status of salps. Therefore, many scholars introduced chaotic mapping to adjust the two parameters, aiming at improving its global search ability and robustness. Sayed et al. proposed a novel chaotic salp swarm algorithm (CSSA) ^[36]. In CSSA, the chaotic map is employed to replace parameter $c_{2}$ with chaotic variables. This design introduces the chaotic map into the updating strategy of the swarm, which improves the performance and convergence speed of the algorithm. An improved salp swarm algorithm was proposed by Tawhid et al.. The algorithm introduces tent mapping into the update strategy of the leader, and experiments show that tent mapping can effectively improve the performance of the algorithm ^[37].

2) Learning Model Adjustment: In fact, it is undoubtedly that SSA can achieve better results commonly when solving continuous optimization problems. However, for some complex optimization problems, SSA may can not solve these problems well because the canonical updating models of salps are not efficient enough. Therefore, the updating models of leader and follower were modified according to the actual situation. For example, Choura et al. proposed Chaotic SSA and Dynamic SSA by introducing multiple chaotic maps and adjusting the update method of the follower, respectively ^[38]. Hegazy et al. introduced inertia weights based SSA to modify the updating model of the leader and follower. Experiments show that the proposed algorithm can obtain higher convergence accuracy ^[39]. Moreover, various adjustments about the topology have been made in SSAs because the neighborhood topology determines the learning mechanism. In this way, SSA can select learning exemplars flexibly and then enhance its performance. In the literature ^[40], an elite pool selection strategy was proposed by Tang et al.. In this strategy, an individual in the elite pool is randomly selected and used as a food source. This strategy enhances the exploration ability of the leader and enriches the swarm diversity. Liu et al. proposed a global search-oriented adaptive leader salp swarm algorithm^[41]. In the leader position update formula, the position of the previous generation of the salp group is introduced as a learning exemplar, which improves the sufficiency of global search and effectively avoids the algorithm from falling into the local extremum.

3) Hybrid Strategy: Since the integration of multiple strategies can combine the advantages of different strategies, it is a common way of improving the performance of algorithms. In particular, various local search strategies were integrated into SSAs, which can achieve a good balance between convergence speed and the diversity of the swarm. Zhang et al. proposed an enhanced SSA (ESSA) ^[42]. In ESSA, various strategies such as orthogonal learning, quadratic interpolation, and generalized oppositional learning are combined with SSA to improve its global exploration and local exploitation performance. Yavuz proposed an SSA with a refreshing-gap strategy (DSSA-R) based on a diversified position update equation ^[43]. Instead of using a single leader strategy, DSSA-R accepts half of the swarm as leaders. In addition, the refreshing-gap strategy and linear population reduction strategy are introduced into DSSA-R to strengthen the performance of the DSSA-R. Furthermore, the hybrid of different algorithms is also a research direction in SSAs for obtaining better solutions. For example, SSA was combined with PSO to make the exploration and exploitation abilities more efficient ^[44]. In this approach, the position of each salp is updated according to one of the PSO and SSA updating models randomly. In the literature ^[45], SSA was integrated with GWO, where the leader and the followers are updated according to SSA and GWO, respectively. This hybrid design can improve the exploration and exploitation abilities to a large extent. Given the advantages of the hybrid strategy, our work has done relevant research on this basis.

3.   MSSA

In standard SSA, the leader is responsible for searching in the neighborhood of the food source. Furthermore, the followers update their positions according to their previous salps. However, the updating model of followers may make them move closer to the leader quickly. Once the leader cannot find a better food source, the diversity of the swarm will decline rapidly, and then the SSA will prematurely converge. Considering this problem, the salp swarm of the proposed MSSA is divided into three sub-swarms. In this way, the followers of each sub-swarm follow the current optimal leader of the corresponding sub-swarm. When one sub-swarm falls into local optimum, it will not affect the other two sub-swarms, thus maintaining the diversity of the whole swarm.

Furthermore, the setting for the number of leaders also affects the exploitation ability of SSAs. In canonical SSA, only one leader searches the neighborhood region of the food source. The rest of salps are regarded as followers who are used for exploring the search space. When solving high-dimensional problems with many local optima solutions, this setting may lead to low performance of SSAs. In this work, the optimal number of leaders is obtained through experimental verification. The MSSA consists of the following subsections.

3.1.   Swarm initialization based on cubic chaotic mapping strategy

Most swarm-based approaches contain random parameters, which are usually generated from Uniform and Gaussian distributions. However, more and more swarm-based approaches were proposed based on chaos theory, which can achieve better accuracy, convergence speed, and stability ^[36]. Considering its advantages of non-linearity, ergodicity, and randomness, a chaotic mapping strategy was employed for initialization of the swarm. In particular, this strategy made the approaches obtain better diversity of the swarm in the previous research works ^[46,47]. Inspired by these researches, the cubic chaotic mapping strategy is used for initializing the swarm of salps, aiming at obtaining a diversity swarm in our work. The expression of the cubic chaotic mapping strategy is shown in Eq (3.1).

where $y_{i, j}\in$(0, 1); $\rho$ is a control parameter and its value is in the range of (1.5, 3). The chaotic sequence is mapped into decision space and then converted into the position vector of a salp. The conversion equation is shown in Eq (3.2).

where $x_{j}^{i}$ is the value of $j$th dimension of position vector denoting $i$th salp; $ub_{j}$ and $lb_{j}$ represent the upper boundary and the lower boundary of the $j$th dimension, respectively.

The process of swarm initialization is shown in Algorithm 1.

3.2.   Multi-swarm updating strategy

In the original SSA, the updating formula of the leader is controlled by three parameters, i.e., $c_{1}$, $c_{2}$, and $c_{3}$. $c_{1}$ decreases nonlinearly with the iteration of SSA. $c_{2}$ and $c_{3}$ are random numbers between [0, 1]. This updating strategy is very random, and it does not take into account the informations carried by other salps in the swarm so that the SSA is easy to fall into a local optimum.

To address this issue, a new updating model of the leader is proposed in MSSA. In MSSA, the parameter $c_{1}$ takes into account the position informations of two random salps for controlling the movement direction of a salp. Like the canonical SSA, however, $c_{2}$ and $c_{3}$ are also random numbers between [0, 1]. $c_{2}$ is employed to control the stepsize of the movement. $c_{3}$ controls whether the best information in personal history is used by salps. The updating model of the leader is shown in Eq (3.3).

where $ub_{j}$ and $lb_{j}$ are the upper boundary and lower boundary of the $j$th dimension in the decision space, respectively; $pbest_{j}^{i}$ is the historical personal optimal position of the $i$th leader; $gbest$ is the current selected food source for the swarm. $x_{j}^{i}$ is the $j$th dimension of position vector denoting the $i$th salp. The updating formula of $c_{1}$ is shown in Eq (3.4).

where $t$ is the current number of iterations, and $T$ is the maximum number of iterations. $x_{j}^{r1}$ and $x_{j}^{r2}$ represent two salps selected randomly from the swarm. It can be seen that $c_{1}$ utilizes the informations of two salps. Compared with changing randomly, this setting mode of $c_{1}$ can improve the convergence efficiency of MSSA.

Furthermore, the swarm of MSSA is divided into three sub-swarms. The followers move towards the current optimal leader of the corresponding sub-swarm, so that salps of the swarm have different learning exemplars. In this way, the swarm has better diversity (shown in Figure 1). The updating model of followers is shown in Eq (3.5).

where $pbest_{j}^{i}$ is the personal historical optimal position of the $i$th follower; $x_{j}^{i}$ is $j$th dimension of the position vector of $i$th salp in the swarm.

The process of updating positions of salps is shown in Algorithm 2. In lines 3–10, the positions of all leaders are updated first according to the Eq (3.3). In lines 11 and 12, the optimal leader of each sub-swarm is selected. At last, followers are updated with reference to the position of the optimal leader in the corresponding sub-swarm.

3.3.   Adaptive perturbation strategy (APS)

The opposite-based learning (OBL) was introduced into many swarm-based optimization algorithms, aiming at improving the performance of these algorithms ^[48,49]. It can search for the inverse solution of the current solution to expand the search range rapidly, and then maintain the diversity of the swarm. These OBL-based algorithms can quickly obtain good candidate solutions in the early iterations, while they may fall into local optima in the late iterations. In this instance, the opposition-based learning with lens imaging principle (lens-OBL) was proposed in ^[50], which achieved better performance in maintaining swarm diversity. The formula for calculating the opposite solution through lens-OBL is shown in Eq (3.6). $a$ and $b$ are the maximum and minimum values of the positions in the current population, as shown in Eq (3.7).

where $a_{j}$ and $b_{j}$ are values of $a$ and $b$ in the $j$th dimension, respectively. When $k = 1$, the standard OBL formula can be obtained from the lens-OBL strategy. At this time, OBL is a special case of lens-OBL strategy. When extending to $d$ dimensional space, assuming that the position vector of a salp is $X\left (x_{1}, x_{2}, \dots, x_{d} \right)$, the reverse solution $X^{*} \left (x_{1}^{*}, x_{2}^{*}, \dots, x_{d}^{*} \right)$ can be obtained according to Eq (3.6).

The simulated binary crossover (SBX) strategy is a real-coded recombination operator ^[51]. Since SBX strategy has strong local search ability, it is widely used in multi-objective evolutionary algorithms. To be specific, it uses two parents to produce two offsprings by blending the genes on their chromosomes one by one. The two offspring inherit the information of the parent and also mutate to a certain extent. As an operator, it can effectively improve the search ability of the algorithm. Assuming there are two parents $x_{1}$ and $x_{2}$, their two offsprings, i.e., $off_{1}$ and $off_{2}$, can be generated by Eq (3.8).

where $\beta$ is determined dynamically by the distribution factor $\eta$, as shown in Eq (3.9).

where $\eta$ is a constant representing the distribution index. When the value of $\eta$ is larger, the offsprings will more similar to their parents. The value of $\eta$ is commonly set to 10 or 20 ^[52,53].

To improve the exploitation ability of the swarm, an adaptive perturbation strategy (APS) based on lens-OBL and SBX strategy is proposed in MSSA, as shown in Algorithm 3. In APS, an adaptive parameter $per$ is designed to adjust the implementing frequency of the lens-OBL strategy and the SBX strategy during swarm evolution. Specifically, the SBX strategy is effectively used to promote communication between different sub-swarms, while the lens-OBL strategy is employed to enhance the local search ability of the swarm. In this way, the proposed APS can enhance the exploitation ability of MSSA effectively, which can also help MSSA escape from the local optimum. The parameter $per$ is calculated as shown in the Eq (3.10).

where $num$ is used for calculating the number of stagnant iterations. After each iteration of swarm, the $num$ is increased by 1 when the $gbest$ does not improve; otherwise, $num$ is reset to 0. The APS is executed multiple times, which may cause the population to search excessively in unpromising areas, Therefore, we limit the value of $per$ to [0, 0.3]. With the increasing of the $num$, the value of $per$ can increase from 0 to 0.3 when adopting the adaptive strategy. The more times of iteration stagnation, the greater the impact of the lens-OBL strategy and SBX strategies on the swarm.

3.4.   The Framework of MSSA

Together with the aforementioned modules, MSSA can be described as in Algorithm 4. The flow chart of MSSA is shown in Figure 2.

3.5.   Time complexity analysis

It can be seen from the framework of MSSA that the main computational complexity of the algorithm is mainly affected by the updating process and the local search process. Actually, the fitness evaluation is related to the real problem, so this process is not considered in the analysis. In this section, only the time complexity of the population update process and the local search process are analyzed.

In the process of updating the population position, the best leader needs to be found. Therefore, the time complexity of sorting $N/2$ leaders in the population is $O((Nlog(N/2))/2)$. Suppose the dimension of the search space is $D$, all $N$ salps update their position vectors in $D$ dimensions. Therefore, the time complexity of updating the positions of particles is $O(ND)$. In summary, the time complexity of the population update phase is $O(((Nlog(N/2))/2))+ND)$. In the local search phase, the time complexity of executing the APS strategy is $O(ND/2)$.

Based on the above analysis, the time complexity of MSSA is $O(((Nlog(N/2))/2))+ND)$ plus $O(ND/2)$, i.e., $O(Nlog(N)+ND)$. We can see that the time complexity of MSSA is slightly increased compared with the canonical SSA. It means that although MSSA introduces a new update model and adaptive perturbation strategy, its time complexity does not increase significantly, and this conclusion proves the effectiveness of MSSA.

4.   Experimental setup

4.1.   Datasets

To evaluate the performance of MSSA, three group experiments were conducted on 10 well-known UCI datasets that cover different domains and different attributes. Table 1 shows these datasets, including the number of classes, features, and data instances.

4.2.   Setup of experimental

In this subsection, the parameters and the environment of experiments are briefly introduced. After a series of experiments in MSSA, the optimal values of the main parameters are obtained. The values of the main parameters of MSSA and comparison algorithms are shown in Table 2. The main parameters of MSSA are explained as follows: $T$ represents the maximum number of iterations and is set to 100. $leaderNum$ represents the number of leaders in the swarm and is set to $N/2$. The $per$ is an adaptive parameter, which controls the probability of executing the lens-OBL and the SBX strategy. $N$ is the size of a salp swarm and is set to 60. Consider that for larger values of $\eta$, the offspring will be more like their parents. In order to strengthen the local search ability of the population, $\eta$ is set to 10 in the SBX strategy. $k$ is the scaling factor in the lens-OBL strategy. It is worth noting that the threshold for decoding is set to 0.5 in this paper. If the value of a feature is greater than the threshold, the feature is added to the feature subset.

All experiments were implemented on MATLAB R2016a software. The computer is equipped with an Intel Core (TM) i7 CPU and the Windows 10 operating system. To reduce experimental statistical errors, for each dataset all the algorithms have been conducted 20 times. Furthermore, to better test the performance of the proposed MSSA, this paper also uses the Friedman test and Wilcoxon signed rank test to analyze the experimental results.

4.3.   Fitness function

For FS task in dataset classification problem, we usually need to focus on two goals. One is to have a higher classification accuracy, and the other is to select a smaller size of feature subset. Therefore, Eq (4.1) is used as the fitness function in our experiments.

where $\alpha$ is the weight factor that determines the relative importance of the classification accuracy, and $\alpha$ is set to 0.9 in this work. The $accuracy$ denotes the classification accuracy of a candidate solution. $l$ represents the number of features selected by the candidate solution. $L$ represents the total number of features of the original feature set. In this way, we turn a two-objective problem into a minimal one. In our work, K Nearest Neighbor (KNN) classifier is used for evaluating candidate solutions. When the classification accuracies of two potential solutions are the same, the smaller candidate feature subset will be considered as a better one.

5.   Experimental results and analysis

5.1.   Analysis of parameters

The parameter $k$ is the scaling factor of the lens-OBL strategy. The value of $k$ affects the scope of lens-OBL strategy and then affects the accuracy of MSSA. Similarly, the parameter $leaderNum$ determines the number of leaders in the swarm. When $leaderNum$ takes a more appropriate value, it can effectively balance the exploration and exploitation abilities of MSSA. In this part, we analyze the optimal value of $k$ and $leaderNum$ through experimental results. Eight representative UCI datasets, covering from low to high dimensions, are selected for experiments. The performance of experiments with different parameters is shown in Tables 3 and 4, respectively.

5.1.1.   Analysis about parameter $k$

In this experiment, different values of $k$ are designed to analyze its impact on the performance of MSSA. Through the analysis, if $k$ is too small, it is easy to exceed the upper or lower boundaries when executing the lens-OBL strategy. When $k = 1$, the lens-OBL strategy becomes the standard OBL strategy. In summary, to make the value of $k$ more representative, the value range of $k$ is set to [0.6, 2] in these experiments. Based on this, comparative experiments were performed on eight datasets. As shown in Table 3, the average classification accuracies were obtained, with bold representing the optimal results.

It can be clearly seen from Table 3 that different values of $k$ have the same accuracies on the Tic-tac-toe and Zoo datasets. For some low-dimensional datasets, like WineEW, CongressEW, and Lymphography, the average accuracies obtained by MSSA with a larger $k$ value are higher. For high-dimensional datasets, such advantages are not obvious. From all experimental results, it can be seen that MSSA has the best performance when $k$ is set to 0.8. Therefore, the value of $k$ is set to 0.8 in the subsequent experiments.

5.1.2.   Analysis about the number of leaders

Table 4 shows the average classification accuracies of MSSA with different numbers of leaders (from $3\times N/4$ to $N/5$). It can be seen that, for most datasets, MSSA has higher classification accuracies and yields the best results when the number of leaders is set to $N/2$. The reason for these results is that the structure with $N/2$ leaders effectively extended the exploitative searching pattern of MSSA. Furthermore, the diversity of the swarm was not reduced by the excessive number of leaders. Furthermore, based on the results of the Friedman nonparametric statistical test ($F$-test), MSSA with $N/2$ leaders results in more promising results.

Figure 3 shows the convergence processes of MSSA with different numbers of leaders on six datasets, where the horizontal axis is the number of iterations and the vertical axis is the classification accuracy. It can be seen from Figure 3 that MSSA with more leaders can often find better results in the early stages of iterations, while the diversities of the swarm are reduced greatly in the later stages of iterations. This is because excessive salps are easy to gather when there are too many leaders in the swarm. However, as shown in Figure 3, the exploration and exploitation abilities of MSSA are well balanced when the number of leaders is set to $N/2$. Therefore, this setting about the number of leaders can balance the exploration and exploitation abilities of the swarm successfully, so that MSSA can achieve higher performance.

To analyze the stability changes of MSSA with different numbers of leaders, the box diagram toolbox is employed in our work. The box diagram toolbox shows the discrete distribution of data in a relatively stable way, while it can not be affected by outliers. In this subsection, several poor experimental results are considered as outliers. Figure 4 shows the box diagrams of experimental results on six datasets, aiming at analyzing the stabilities of MSSA with different numbers of leaders.

It can be seen from Figure 4 that, MSSA achieves the same experimental results on WineEW and Lymphography datasets. That is to say, the number of leaders has no significant effect on the stability of MSSA on the two datasets, which is consistent with the average classification accuracies shown in Table 4. For dataset CongressEW, the experimental results are more concentrated when the number of leaders is set to $N/2$, even though different numbers of leaders do not lead to outliers. However, MSSAs with different numbers of leaders obtain some outliers on higher dimensional datasets (IonphosphereEW, SonarEW, and Clean1). This means that MSSA may obtain poor results even though it achieves the optimal solutions on these higher-dimensional datasets. In other words, MSSA has a higher classification accuracy and better stability to a large extent.

On the whole, when the number of leaders is set to $N/2$, MSSA does not get outliers on the CongressEW, IonosphereEW, SonarEW, and Clean1 datasets. For dataset Clean1, the experimental results obtained by MSSA with $N/2$ leaders are very similar to the optimal results. That is to say, MSSA with $N/2$ leaders can obtain higher classification accuracies and better stability on these datasets, which is consistent with the experimental results shown in Table 4. Based on the above experimental analysis, the number of leaders of MSSA is set to $N/2$ in our work.

5.2.   Comparison with representative algorithms

To validate the performance of MSSA, it is compared with five swarm-based algorithms in this subsection. The five approaches include Binary Gravitational Search Algorithm (BGSA) ^[27], Binary Grey Wolf Optimizer (BGWO) ^[54], Binary Bat Algorithm (BBA) ^[28], Genetic Algorithm (GA) ^[55], and BPSO ^[17]. The KNN classifier is employed for evaluating the fitness values of candidate solutions. From Table 5, it can be seen that MSSA achieves smaller fitness values among six competitors on 10 well-known UCI datasets. Especially, MSSA has a significant advantage in performance when solving the classification problem with high-dimensional datasets.

Table 6 shows the average classification accuracies obtained by MSSA and these five methods. It can be seen that MSSA achieves the highest classification accuracies among these six approaches on 10 UCI datasets. In particular, MSSA achieves classification accuracies of over 96% on seven out of ten datasets. Furthermore, BGWO and GA obtain suboptimal performance among these six approaches on most of the datasets. In particular, BGWO can obtain better results in low-dimensional datasets, while GA is superior in high-dimensional datasets. Besides, it can be seen from Table 6 that, the higher the dimension of the dataset is, the more significant the performance of MSSA has.

On the other hand, in order to better verify the performance of the proposed algorithm, we also conducted a statistical analysis of the experimental results. According to the results of the Friedman test and Wilcoxon signed rank test in Tables 6 and 7. As shown in Table 6, MSSA outperforms the comparison algorithms on all 10 datasets, so MSSA achieves the highest ranking in the Friedman test, which verifies that MSSA has superior performance. As can be seen from Table 7, the null hypothesis is rejected by all six algorithms. This shows that MSSA is significantly better than the comparison algorithm at the significance level of 0.05.

Furthermore, to further validate the performance of MSSA, we compare it with other six swarm-based algorithms (i.e., HGSA ^[56], S-bBOA ^[57], bGWO1 ^[54], bGWO2 ^[54], WOASA ^[58], and BHOA_S4_Cr2 ^[59]) on these 10 UCI datasets. The average classification accuracies obtained by these methods are shown in Table 8.

From Table 8, it can be seen that MSSA achieves the highest classification accuracies among seven competitors on six out of ten datasets. Furthermore, BHOA_S4_Cr2 obtains the highest classification accuracies on low-dimensional datasets (WineEW and Zoo). WOASA and HGSA achieve the best results on CongressEW and Lymphography datasets, respectively. In particular, MSSA obtains the highest classification accuracies on Tic-tac-toe, IonosphereEW, KrvskpEW, WaveformEW, SonarEW, and Clean1 datasets. Therefore, the superior performance of MSSA is verified again by experimental results. Through analysis, it is found that MSSA can achieve a good balance between exploration and exploitation abilities when solving the classification problem on high-dimensional datasets.

Table 9 shows the Wilcoxon signed rank test of the accuracy comparison results between MSSA and six swarm-based algorithms. It can be seen from Table 9 that the null hypothesis is accepted by WOASA, while none of the other five algorithms accepts it. This indicates that MSSA is not significantly different from WOASA, but MSSA is significantly better than the other five comparison algorithms. Although MSSA does not have significant advantages over WOASA, it has achieved higher classification accuracy on most datasets. It indicates that MSSA is superior to the comparison algorithm on these 10 datasets in the comparison experiment.

5.3.   Compare with other versions of SSA

In order to further verify the effectiveness of MSSA, it is compared with three variants of SSA (BSSA, TCSSA3, and BSSA_S3_CP) in this subsection. BSSA is the variant of SSA according to Eqs (2.5) and (2.6). In TCSSA3, the swarm of salps is also divided into multiple sub-swarms, which improves the updating model of leader ^[35]. BSSA_S3_CP adopts the combination of crossover operator and a new transfer function ^[13]. Table 10 shows the fitness values obtained by MSSA and three versions of SSA. Figures 5 and 6 show the average classification accuracy, the ratio of selected features to total features, and the ranking of $F$-test obtained by these SSAs on all 10 UCI datasets. Through three indicators denoted by different colors in heatmaps, we can effectively analyze the advantages and disadvantages of four SSAs.

As shown in Table 10, MSSA achieves better fitness values on 70% of all the datasets. In particular, MSSA outperforms TCSSA3 and BSSA on 90% of all the datasets. Furthermore, BSSA_S3_CP obtains better fitness values on the remaining three datasets (WineEW, Zoo, and Lymphography). Furthermore, for the low-dimensional datasets, the performance of MSSA and BSSA_S3_CP is very similar. For the high-dimensional datasets, however, the advantages of MSSA appear gradually. Besides, MSSA achieves the highest ranking in the $F$-test among these four approaches.

In Figure 5, the darker the color of the heatmap is, the higher the classification accuracy of an algorithm is. It can be seen from the Figure 5 that the colors of BSSA and TCSSA3 are lighter on most of the 10 datasets, which means that the average classification accuracies obtained by them are not significantly different on these 10 UCI datasets. BSSA_S3_CP and MSSA have similar colors in the first few low-dimensional datasets. For high-dimensional datasets (i.e., IonphosphereEW, KrvskpEW, WaveformEW, SonarEW, and Clean1), the colors denoting MSSA are significantly darker than BSSA_S3_ CP. Combined with the ranking values of $F$-test, it can be concluded that MSSA has a better performance than the three competitors.

In Figure 6, the lighter the color of the heatmap, the smaller the size of the selected feature subset. It can be seen that MSSA obtains smaller feature subsets on nine out of ten datasets. Especially, for the highest dimensional dataset Clean1, MSSA obtains a very small subset of features compared with three competitors. From Table 10 and Figure 5, it can be found that MSSA obtains the highest classification accuracy by using the least features on the dataset Clean1, while the fitness value obtained by it is far lower than these three methods. According to the ranking values of $F$-test, MSSA can also obtain smaller sizes of feature subsets on almost all of these datasets.

6.   Conclusions

FS is a challenging data pre-processing step in data mining and machine learning. Inspired by SSA, this paper proposes a novel MSSA to solve the FS task in the dataset classification problem. In MSSA, the diversity of the swarm is maintained dynamically through the chaos mapping strategy and multi-swarm strategy. Furthermore, the updating models of leaders and followers are improved so as to utilize more useful informations carried by salps of three sub-swarms. Moreover, the lens-OBL and SBX strategies are employed to enhance the exploitation ability of MSSA. Through analysis, it is found that MSSA can achieve a better balance between exploration and exploitation abilities when solving the FS task. The experimental results show that MSSA is superior to the other 14 competitors on 10 well-known UCI datasets. Especially, MSSA has significant advantages when facing high-dimensional datasets.

Future research can combine the filter strategy with MSSA to improve its performance. We can also try to apply MSSA to other different fields, such as image classification, image processing, and large-scale optimization.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This study is funded by the Basic Public Welfare Research Project of Zhejiang Province (LGF22F020020), the National Natural Science Foundation of China (72101235, 62011530130, 62272415, 62106092), Scientific Research Starting Foundation of Zhejiang Sci-Tech University (20032309-Y), the Key Research and Development Program of Zhejiang Province (2020C03060), Joint Fund of Zhejiang Provincial Natural Science Foundation (LSZ19F010001), the Natural Science Foundation of Fujian Province (2022J01916), and the Research Fund Project of Zhejiang Sci-Tech University Longgang Research Institute (LGYJY2023003).

Conflict of interest

The authors declare there is no conflict of interest.