Abstract
Inspired by the biological behavior of domestic cats, the Cat Swarm Optimization (CSO) is a metaheuristic which has been successfully applied to solve several optimization problems. For binary problems, the Boolean Binary Cat Swarm Optimization (BBCSO) presents consistent performance and differentiates itself from most of the other algorithms by not considering the agents as continuous vectors using transfer and discretization functions. In this paper, we present a simplified version of the BBCSO. This new version, named Simplified Binary CSO (SBCSO) which features a new position update rule for the tracing mode, demonstrates improved performance, and reduced computational cost when compared to previous CSO versions, including the BBCSO. Furthermore, the results of the experiments indicate that SBCSO can outperform other well-known algorithms such as the Improved Binary Fish School Search (IBFSS), the Binary Artificial Bee Colony (BABC), the Binary Genetic Algorithm (BGA), and the Modified Binary Particle Swarm Optimization (MBPSO) in several instances of the One Max, 0/1 Knapsack, Multiple 0/1 Knapsack, SubsetSum problem besides Feature Selection problems for eight datasets.
Keywords
Introduction
Nature-inspired optimization methods have gained attention in the last decade due to their capacity to reach reasonable solutions in many areas of science [1]. The beginning of this research field is credited to the development of the Genetic Algorithm (GA) in the 1960s, using as inspiration the theory of Evolution of Charles Darwin [2, 3, 4, 5, 6, 7]. In 1995, Kennedy and Eberhart introduced the Particle Swarm Optimization (PSO) [11, 12, 7, 9, 10], starting the swarm-based algorithms field [13, 14]. After that, many other swarm methods have been proposed [3]. A prominent instance of the swarm-based algorithms is the Cat Swarm Optimization (CSO) for continuous problems. Introduced by Chu and Tsai in 2006, the method is inspired by the behavior of domestic cats [15]. The authors state that the cats stay inactive most of the day when resting, while they are alert when they are hunting. Based on these premises, the algorithm divides the cats behavior into two modes, namely seeking and tracing modes [16]. A combination of these modes aims to balance the exploration and exploitation abilities of the algorithm[17].
An increase in the complexity of binary problems in science creates a need for improving binary algorithms. Researchers in the swarm intelligence field have been developing algorithms and methods to deal with binary domains [18, 19]. We highlight some of the studies published last year and discuss many binary problems solved with nature-inspired methods, mainly for feature selection [20, 21, 22, 23, 24, 25, 26, 27].
While the GA was the first one developed from evolutionary computation to deal with binary variables, the pioneer in swarm intelligence is the Binary PSO (BPSO), introduced in 1997 by Kennedy and Eberhart [28]. BPSO is an adaptation of the continuous PSO algorithm developed specifically to address binary variables; BPSO uses transfer and discretization functions to transform continuous vectors into binary ones. Regarding binary versions of the CSO, we highlight the works from Sharafi et al. [29], Mohamadeen et al. [30], Srivastava and Maheswarapu [31], Li et al. [32] and Kumar et al. [33] that apply transfer functions to transform the continuous velocity of the cats into binary strings.
Some proponents of swarm-algorithms apply Boolean gates to perform the displacement of the agents [34, 35, 36, 37, 38]. However, there was no other version of the BCSO before our previous work [39]. In this investigation, we realized good efficiency and search capability when applying Boolean gates on the BCSO.
In the present paper, we have extended the study of the Boolean Binary Cat Swarm Optimization (BBCSO) algorithm by presenting an improved version, the Simplified Binary CSO (SBCSO). In this novel approach, we define a new velocity for the cats, and a new velocity update, which decreases the computational cost by simplifying the tracing mode. All vectors regarding the position of the cats and their displacements are binary values.
In order to assess the effectiveness of the SBCSO, we selected the following problems: One Max, 0/1 Knapsack, Multiple 0/1 Knapsack, Subset Sum and feature selection. We conduct a performance analysis of SBCSO by comparing it with five different bio-inspired algorithms: Binary Cat Swarm Optimization (BCSO), Improved Binary Fish School Search (IBFSS), Binary Artificial Bee Colony (BABC), Binary Genetic Algorithm (BGA), and Modified Binary Particle Swarm Optimization (MBPSO).
The remainder of the paper is organized as follows: Section 2 describes some state-of-art nature-inspired algorithms for optimization; Sections 3–5 discuss CSO and BCSO, BBCSO, and SBCSO, respectively; Section 6 discusses the case study, computational results, and a performance analysis; and Section 7 presents the conclusions.
Nature-inspired algorithms
Natural phenomena inspire the generation of many optimization methods. An essential piece of research elaborated by Siddique and Adeli [40] explores many nature-based algorithms, which are not necessarily based on the interactions among living beings.
The Simulated Annealing was the earliest method that emulates physical phenomena [41]. The thermodynamics principles inspired it, and it simulates the cooling process, which is a gradual lowering of the temperature until the system reaches convergence. Its broad application in engineering problems inspired researchers to elaborate on other physics-based algorithms [42].
The laws of gravitational force described by Isaac Newton inspired the Gravitational Search Algorithm (GSA). This is a population-based method, in which the interactions between the agents (mass) occurs following a simulated artificial gravitational attraction [43].
The jazz improvisation is the primary inspiration in the creation of the Harmony Search Algorithm [44]. During a concert, the musicians play together, and they select the musical notes in order to achieve the best harmony. As time advances, they will remember the notes played before, and the musicians move note by note creating a more beautiful melody [45].
The Spiral Dynamics Algorithm [46] was developed for continuous optimization. The mathematical formulation of spiral phenomena inspired it since such a pattern can be observed in plants, animals, and even galaxies. The central part of the method is plural logarithmic spiral models and their common center.
The Water Drop Algorithm [47] was based on the dynamics of the water in the rivers, and the water drops when moving. The proposers mention that the gravitational force of the Earth is responsible for the water drops when they are moving. They state that such water has a velocity, and each water drop carries some amount of soil in its path. Therefore, some amount of soil is moved. The method was successfully applied in vehicle routing, economic load dispatch, wireless networks, reservoir operation, and others.
The gravitational kinematics inspires central Force Optimisation. This research field creates a model to describe the movement of masses according to the gravitational force. The algorithm addresses a population of probes that are distributed all over the objective function. The method aims to search the biggest mass, which represents the strongest attraction force. As a consequence, it will attract all other agents in the search grid, considered as the best agent.
Also, the Many-Objective Control Optimization [48] proposed by Soto and Adeli is an example of many-objective optimization. The model uses replicator dynamics and an improved version of the robust neural dynamic method from Adeli and Park. The application addressed in such a study is related to vibration control.
The Evolutionary Algorithms (EAs) are among the first nature-inspired methods for optimization. The objective is to simulate an artificial evolution, following a simplified process described in the Darwinian Theory [3]. The primary approach is to “evolve” the agents and apply an artificial selection procedure; the agents with the best fitness values tend to survive in the next iteration.
Currently, the most used EAs for optimization are the Genetic Algorithm (GA) and Differential Evolution (DE). In both strategies, the agents (chromosomes or individuals, and vectors, respectively) go through a process of improvement of the population. The crossover genetic operator is applied to refine the search by means of the exchange of genes (variables) between the agents. Next, a random perturbation is applied in some genes of the population, to allow a global search [49].
In the standard version of the GA, the selection of the individuals to perform the operation occurs before the crossover. In DE, the procedure happens after the mutation, which represents a greedy operation [49].
We also highlight the Memetic Algorithm (MA) as an important representative of the evolutionary class [50, 51, 52]. This approach proposes a step forward concerning the traditional EAs introducing a local search operation. The algorithm then selects a subset of agents with a predefined probability to perform the search during a period of time. The objective is to reduce the likelihood of premature convergence. The current literature [51, 52] also indicates that the MA is not limited to evolutionary approaches, but can be extended to any population method, such as swarm-inspired algorithms if some local search is performed. A primary objective is to reduce the likelihood of premature convergence.
In 1995, Kennedy and Eberhart introduced the Particle Swarm Optimization (PSO) [11, 12], initiating the swarm-based algorithms field [13, 14]. Inspired by the natural social behavior of swarms, like flocks of birds and fish schools, the method creates a population of agents, named particles. Those particles change their positions considering the best position achieved by themselves and the best place observed in their neighborhood.
The PSO is the most used SI algorithm in literature [1, 21]. Consequently, there are a lot of new versions improving its performance. To demonstrate its flexibility and robustness, one can read a comprehensive proposal in the paper from Hossain et al. [53]. In this paper, the authors solved the University Course Scheduling Problem (UCSP) after introducing the PSO with selective search (PSOSS). This algorithm presents the addition of some operators, like selective search and effective swap operation with a repair mechanism.
Among other swarm methods, we highlight the Ant Colony Optimization (ACO). The specific procedure to find food by an ant in a colony inspired the creation of the method [54]. This algorithm is the most used bio-inspired meta-heuristic to solve ordering problems or integer optimization.
The Artificial Bee Colony (ABC) algorithm simulates the way bees communicate after to find good food sources [55, 56]. In this case, the agents tend to explore and refine more in-depth candidate solutions with high fitness. After the PSO, the ABC is probably the most prominent SI algorithm [1, 57].
The Bacteria Foraging Algorithm, as explicit in its name, was inspired on the foraging (chemotactic) process of groups of bacteria type Escherichia coli [58]. The premise is that the agents look for nutrients aiming to maximize energy obtained per unit time. Besides, they communicate with others by sending chemical signals. Recently, the Smart Bacteria Foraging Algorithm [26] was proposed to solve a high-dimensional complex problem. This improved version combines chaos mapping as well as adaptive and quantum computing.
Many other SI algorithms are discussed and analysed in the literature, including but not limited to Bat Algorithm (BA) [59], Firefly Algorithm (FA) [60], Cat Swarm Optimization (CSO) [15], and Fish School Search (FSS) [20, 3].
The main difference between the evolutionary algorithms (EA) and swarm-inspired (SI) methods lies in logic and operators used to realize global and local search [3]. The EAs create new individuals at each iteration to move the candidate solutions in the search space, applying the genetic operators (crossover and mutation) and selection [49]. These steps aim to emulate an artificial evolution. In most SI approaches, the social interactions between simple agents and the environment lead to a self-organization system, giving rise to an intelligent collective behavior. In this situation, the agents change their positions on the surface of the search function [1, 3]. Because of the absence of the selection, the SI methods do not suffer from selection pressure issues. However, as stated by Kononova et al. [61], the population-based methods suffer from the presence of structural bias, which means that they are not capable of searching in all parts of the function with the same efficiency because their operators tend to favor certain areas. So, both methods can be equally efficient.
Cat swarm optimization
The Cat Swarm Optimization (CSO) was proposed in 2006 and since then, many CSO research studies have been published. So, we can state that this is a well-known method in the area of swarm intelligence.
Some recent investigations published in notable journals in the last two years, have addressed CSO applications for problems like multimodal optimization [62], group robotic problems [63], aquifer parameter estimation [64], photovoltaic system under partially shaded condition [65], and document summarizing [66]. This is an indication of CSO’s acceptance among the scientific community.
Regarding the binary optimization, there are several proposals of binary SI algorithms based on PSO [67, 68, 69, 70, 21], ABC [71, 72, 73, 57], and ACO [74, 75, 29]. This justifies the need to develop other alternatives to solve this class of problems.
Following the development of the CSO, many investigations proposed binary CSO versions, named BCSO [16, 17, 18, 19]. However, these methods use transfer functions to transform the agents into binary strings.
In a novel approach introduced in [39], namely the Boolean Binary Cat Swarm Optimization (BBCSO), the cats and their displacements are calculated, and remain in the binary domain. Therefore, the operations and interactions between the agents are performed by Boolean gates, preserving the binary nature of the agents. In this current study, we proposed a simplified version of the algorithm. To the best of our knowledge, we have found a gap that deserves to be filled due to the importance of the CSO.
Binary cat swarm optimization: Previous versions
The first Cat Swarm Optimization (CSO) algorithm for continuous optimization was inspired by the behavior of domestic cats [76]. Each iteration divides the swarm into two groups: the sub-swarm of cats that are seeking, and another sub-swarm that are tracing on the environment [15]. In this section, we describe the previous binary versions of the CSO, which follow the same idea of splitting the population. Such proposals use transfer functions to transform the agent, codified as a real string, into a binary vector.
The seeking mode emulates the resting state of a cat changing its position locally. It operates as a divergence factor by allowing the cats to move regardless of the collective information, and to avoid premature convergence. In tracing mode, the cats move according to their position, velocity, and the best position achieved considering all the agents [76]. In contrast to the seeking mode, the tracing mode acts like a convergence operator, by allowing the cats to be attracted to the discovered regions from other cats [29, 77].
The separation of the agents into those modes presents an exciting balance between exploration and exploitation, with a small increase in computational cost, if compared to the PSO. The BCSO is still simple to implement and understand, but such a metaphor allows an expansion of the search capability of the method.
The algorithm is initialized by defining the number of cats in each mode. So, the user must define the mixture ratio (MR), which indicates the percentage of cats performing the tracing mode. The other cats are allocated in the seeking mode [78]. In Sections 3.2 and 3.3, we provide a detailed description of the operation of such modes.
Also, one can observe that the tracing mode is similar to the PSO. While the position update of CSO is the same as the PSO, the velocity of CSO does not consider the local best [11]. The main difference between the PSO and CSO lies in the presence of the seeking mode, which, in this case, can be considered as a local search. Consequently, the CSO can be related to a MA, as discussed in Section 2 [51, 52]. The strength of MAs is attributed to the synergy between global and local search approaches.
Seeking mode
The cats randomly allocated to the seeking mode perform a local search [15] controlled by the following four variables or factors, which are pre-defined by the user [30]:
Seeking memory pool (SMP): Defines an integer value for the number of clones to be generated from each cat. The idea of this factor is to determine how many points must be explored in the vicinity of the current position. This premise is similar to the clonal principles from the CLONALG algorithm [79]; Probability muting operation (PMO): Is the probability of occurrence of a mutation in a predefined dimension. This percentage lies in the interval 0% Counts of dimensions to change (CDC): This variable defines the number of dimensions (or the number of elements regarding the vector representing the cats) that can be changed (muted). A mutation will occur with probability PMO; Self-position considering (SPC): This variable is a Boolean flag which assumes the states true or not_true. In the first case, the current position of a cat is considered to pass through mutation. Otherwise, just the clones participate in the possible moving.
After the definition of the variables described above, the operation of the seeking mode follows four steps [31] described below. Note that such a sequence of steps is applied to each agent separately:
If the SPC flag is true, the algorithm creates SMP-1 clones of the cat and also considers the original candidate. Otherwise, it creates SMP clones and discards the original candidate; For each clone, mutate CDC dimensions according to the PMO probability; Calculate the fitness of the agents; Considering the current SMP cats, it applies the roulette wheel method described in Eq. (1) and changes the current position by the position of the selected one [33]:
where
The tracing mode emulates the state in which the cats are hunting their preys. We define the displacement by the current velocity, and the position of the cat with the best fitness [33], this representation is similar to the PSO’s social component [11]. In binary tasks, the velocity is, indeed, the probability of flipping a bit in some dimension of the agent [32].
The cat which presents the best fitness is defined as
in which
where
The final velocity (probability of changing the
The velocity is bounded by
The first step to update the position of the cat is to update its velocity. In Eq. (4), one can observe that the velocity produced is a real value. This value is later used to determine the position of the cats in the binary domain. The first proposal to map the value of velocity in the binary domain follows the idea introduced in the BPSO [28], or the usage of the sigmoid function. In this case, the velocity coefficient
Sharafi et al. [29] suggest calculating the binary position for each dimension using Eq. (6):
Although this idea is prevalent in the literature [18], Mohamadeen et al. [30] applied another method to update the positions utilizing Eq. (7):
in which
In addition to the techniques mentioned, there are other approaches in the literature, such as to apply “V-shaped‘’ functions [18]. The first option is to use the modulus of the hyperbolic tangent
Another option is to apply a variation of the arc-tangent function
Then, one can address Eq. (10) to calculate the position of the cat
Observe that,
Boolean BCSO (BBCSO) simplifies the BCSO by reducing the number of equations and coefficients required for the algorithm, and by removing unnecessary exploration caused by the continuous-based methods and operators. We argue that binary operators are more efficient for binary optimization because they are computationally lighter, and they can provide enough diversity and convergence for a swarm-based algorithm. For example, the usage of discretization functions on binary optimization tasks are rarely affected by the change on the decimals of a continuous region [39].
In BBCSO, instead of allocating the cats randomly, a roulette wheel method is applied to select the cats that are going to execute the seeking mode, and the rest of the swarm execute the tracing mode. Moreover, Siqueira et al.[39] observed that the use of SPC flag increases the number of coefficients without a consistent increase in the performance of the algorithm, so it was removed. The algorithm would always consider SPC as true, and the original cat would remain an option for the next generation.
The other modifications proposed are related to the update rule of velocity and position of the cats. The position changes according to the velocity, as described in Eq. (11), while the velocity updates based on the best-positioned cat and its current position, as in Expression Eq. (12).
where
We identified two drawbacks in the tracing mode of BBCSO. The first one is the lack of control over the changes made in the velocity: all the dimensions of the velocity vector are updated. A large number of changes in the dimensions can lead to the loss of diversity (agents with similar positions) and to the premature convergence of the swarm. The second problem is related to the position update operator. The updated position is the result of a bitwise AND operation between the current position and the new velocity, so only the dimensions with values equal to one can be changed. In this case, the tracing mode can be simplified, as we propose in the next section.
To overcome the lack of control in the velocity and the tendency of flipping ones when updating positions, we propose a new version of the BBCSO, named as Simplified Binary Cat Swarm Optimization (SBCSO), with a redesigned tracing mode. The complete implementation of the SBCSO is presented in Algorithm 5.
When dealing with optimization in the continuous domain, the concept of velocity is associated with the step length: towards/away from a position in the search space. However, since there is no intermediary position between binary states, to attract or push away the agents, we defined a new velocity associated with the number of dimensions in the problem. It should be noted that as we increase the number of dimensions changed, the convergence will be faster while increasing the probability of premature convergence and similar individuals in the swarm.
In the tracing mode, the new velocity flips, at most, VD dimensions of a cat
in which
In the tracing mode, we also changed the position update operator. For each dimension randomly selected, the Eq. (14) is applied:
where
SBCSO pseudocodeEstablish the parameters: MR, SMP, CDC, VD and PMO;
Initialize the cat swarm on positions randomly selected, and start the velocities as a full zero vector with
Evaluate each cat and update
stop criterion is not reached Choose randomly
each cat in the seeking mode Make SMP copies of the current cat;
each copy Select CDC dimensions and flip them with probability PMO;
Evaluate the fitness of the SMP copies;
Apply roulette wheel method to select one candidate (the copies or the original cat);
the fitness of the candidate is better than the original cat fitness the candidate replace the original cat;
Update the best cat of the swarm;
each cat in the tracing mode
each dimension selected in a shuffled ordernumber of changed dimensions
Return the
Once the new algorithm is established, we tested whether the roulette wheel and random operators would have the same performance on distributing the cats to perform the tracing and seeking mode. In Table 1, we observe that the random selection (Random) presented similar or superior results to the roulette wheel (Roulette). Thus, the random selection is chosen for SBCSO since it is computationally less expensive.
Results of the fitness value and wilcoxon test with a significance level of 5% comparing the random selection and the roulette wheel approach. Where the symbol “– ” means that there is no statistical difference between the Roulette and the Random, “
” indicates that the Roulette was superior to the other, and the “
” means that the Random version overcame the roulette wheel option
Results of the fitness value and wilcoxon test with a significance level of 5% comparing the random selection and the roulette wheel approach. Where the symbol “
Results of fitness value and Wilcoxon test with a significance level of 5% comparing our proposal with the other algorithms in the One Max problem
This section presents the results of the computational simulations performed with the selected binary problems: One Max, Subset Sum, 0/1 Knapsack, Multiple 0/1 Knapsack and Feature Selection[81, 82, 83, 84]. In addition, we present a comparative performance analysis regarding other important binary bio-inspired algorithms: Binary CSO [30], Improved Binary Fish School Search (IBFSS) [85], Binary Artificial Bee Colony (BABC) [86], Binary Genetic Algorithm (BGA) [87], and Modified Binary Particle Swarm Optimization (MBPSO) [88].
We selected the above mentioned algorithms for specific reasons. The BGA is the most prominent evolutionary approach, being a generational method, and one of the fastest binary algorithm. Besides the Boolean and the Simplified BCSO methods, the BGA is the only one that does not use a discretization strategy. Next, the PSO and ABC are the most used swarm algorithms in relevant literature, and the FSS has yielded good results in several optimization problems. Besides, the operators of the FSS are quite different from the others. Finally, we evaluate the performance of the previous Binary CSO in comparison to the novel version proposed in this paper.
All the algorithms were implemented using the Python programming language (version 3.7) and the simulations were performed in an Intel™ Core I7 4500U processor with 8 GB of RAM. The operational system was Linux Deepin 15.9.1 64 bit.
As the algorithms evaluate the fitness different number of times per iteration, we consider the stop criteria of all the algorithms as 9,000 fitness evaluations. For each one, we performed 30 independent simulations and posteriorly applied a statistical test. The test selected was the Wilcoxon non-parametric statistical test, with a confidence interval of 95%. The test, as mentioned earlier, does not consider the samples as normal distributions, and it is efficient to compare samples from different distributions [57, 20].
For the BCSO, BBCSO and SBCSO, we adopted
Performance of all the algorithms for the subset sum function with 100 dimensions (average of 30 simulations).
This subsection evaluates the computational performance of the algorithms reached on the One Max problem. This problem can be used to analyze the convergence capabilities of the algorithms. In Table 2, we show the average of the fitness value (from 30 simulations), their standard deviation, and the Wilcoxon text compared to our BBCSO proposal considering
Results of fitness value and wilcoxon test with a significance level of 5% comparing the SBCSO with the other algorithms in the subset sum problem
Results of fitness value and wilcoxon test with a significance level of 5% comparing the SBCSO with the other algorithms in the subset sum problem
Performance of all the algorithms for the subset sum function with 1000 dimensions (average of 30 simulations).
Performance of all the algorithms for the 0/1 Knapsack function with 100 dimensions (average of 30 simulations).
Performance of all the algorithms for the 0/1 Knapsack function with 1000 dimensions (average of 30 simulations).
Performance of all the algorithms for the Multiple Knapsack function with 100 dimensions (average of 30 simulations).
Results of fitness value and Wilcoxon test with a significance level of 5% comparing the SBCSO with the other algorithms in the 0/1 Knapsack problem
Results of fitness value and Wilcoxon test with a significance level of 5% comparing the SBCSO with the other algorithms in the 0/1 Knapsack problem
Results of fitness value and Wilcoxon test with significance level of 5% comparing the SBCSO with the other algorithms in the Multiple Knapsack problem
We assessed the algorithms in the Subset Sum problem, which optimizes the sum between numbers. Figures 1 and 2 present the convergences for 100 and 1000 dimensions, respectively. For 100 dimensions, a majority of the algorithms reached similar results. However, for 1000 dimensions, the simplified version of the BBCSO managed to be the best among all the algorithms tested. Furthermore, the results in Table 3, show that for 500 dimensions, SBCSO, BCSO and MBPSO achieved the same results, but for 100 and 1000 dimensions, SBCSO outperformed the other algorithms. These results are confirmed by the Wilcoxon test, which indicates that none of the other algorithms surpassed our simplified proposal. In this problem, the efficiency of SBCSO is established by the control of flipped features, and the diversity and stability of the algorithm.
Datasets chosen to the feature selection experiments
0/1 Knapsack problem aims to choose a set of items (weight and value) that better fits in a total weight bag. As depicted in Figs 3 and 4, SBCSO achieved better convergence in 100 and 1000 dimensions. In Table 4, we observe that the results of SBCSO are also statistically better on almost all the experiments for 100, 500, and 1000 dimensions (using non-parametric Wilcoxon test with 95% of confidence interval), only tying with BCSO for 100 dimensions. Moreover, the stability of SBCSO can be noticed by the smallest standard deviation in comparison to other algorithms. For this problem, we argue that not only the control of flipping features (made by the parameter VD) are relevant for a good convergence, but also the PMO probability for each CDC selected dimensions on the tracing mode permits the swarm not to converge prematurely.
Performance of all the algorithms for the Multiple Knapsack function with 1000 dimensions (average of 30 simulations).
Fitness values, accuracy and Wilcoxon test on the training sets for SBCSO and the other binary algorithms
Multiple Knapsack Problem extends the 0/1 Knapsack problem by aiming to select items to more than one bag, challenging the algorithms similar to the 0/1 Knapsack problem. The results in Figs 5 and 6 show the convergence of all the algorithms. Once again, SBCSO achieved a better solution faster than comparable algorithms. Furthermore, applying the Wilcoxon test with a significance level of 5%, we highlight in Table 5 the efficiency of SBCSO compared to the other algorithms, and SBCSO tied with BCSO for 100 dimensions experiment.
Feature selection problem
In this paper, the Feature Selection problem aims to minimize the number of selected features that maximize the accuracy of datasets’ classification by using the fitness function in Eq. (15).
where accuracy is the cross-validation accuracy on the training set,
Number of selected features, accuracy and Wilcoxon text on the test sets for SBCSO and the other binary algorithms
We defined
The K-nearest neighbors (KNN) with
We chose nine datasets, detailed in Table 6, varying on the complexity and the number of features (13–754), and Table 7 shows the results of all algorithms in terms of fitness and accuracy values. In 5 of 9 datasets, the SBCSO outperformed the other algorithms. The Wilcoxon test indicates that only the IBFSS was able to achieve superior results in the Lung Cancer, Hill-Valley, and Parkinson datasets. However, we highlight that the IBFSS is an algorithm that was designed to deal specifically with feature selection, starting the exploration in advantage. Even in this case, SBCSO managed to find better fitness than the IBFSS in most cases because of the control on feature selection on seeking mode and the capability to continue having new individuals on the tracing mode. Finally, for the Musk 1 dataset, SBCSO and BCSO had the best results compared to the other algorithms.
Regarding the results in terms of the number of features selected and the accuracy in the test sets, Table 8 shows that the IBFSS presented the best performance. IBFSS was explicitly designed to tackle feature selection problems and has mechanisms that help to reduce the number of features selected [85]. For instance, in the initialization process, the IBFSS selects dimensions with a probability of 25%. In the other algorithms assessed, this probability is 50%.
Average computational time in seconds for the proposed algorithm and other binary algorithms analyzed on the Subset Sum problem.
In almost all problems addressed in this work, the SBCSO obtained excellent performance when the number of dimensions increased. One possible explanation for this result might be related to the fact that among all the algorithms assessed in this work, only the CSO-based algorithms have a mechanism that adapts the amount of changes in dimensions to the problem dimensionality (defined by the CDC parameter). In previous works [39], it is noted that these algorithms exhibit excellent performance in problems with a large number of dimensions. As a result, the improvements made in simplified BCSO might have enhanced the performance of the BCSO.
The analysis of the computational cost of the algorithms assessed in this work, Fig. 7, reveals that among CSO algorithms, the SBCSO was the one with the lowest cost followed by the BBCSO. This can be attributed to the low cost of the Boolean operator when compared to the regular arithmetic operations of the BCSO. Compared to the other algorithms, the simplified version of the BBCSO can be considered the second/third fastest, behind the BGA and with similar magnitude as the MBPSO. Previous works also pointed out that the GA-based algorithm presents low execution time when compared with other metaheuristics [91]. The difference in the computational cost between algorithms is to be expected. Even though the SBCSO was not the fastest method, it outperformed the majority of algorithms and was similar to the fastest ones (BGA and MBPSO).
Binary optimization problems still need better solutions. Our work presents a fast and efficient binary swarm-based algorithm, namely the Simplified Binary Cat Swarm Optimization (SBCSO). Although the original CSO was developed to solve continuous optimization problems, versions of CSO can be applied to binary and discrete optimization.
In our proposal, SBCSO is a fast and simplified method that does not apply discretization and transfer functions. Instead, it replaces the continuous operators by a simple logic gate and binary operators, which simplifies the system and decreases the computational cost. The SBCSO simplifies the tracing mode of the BBCSO by creating a new simple procedure to update the position and velocity.
In general, SBCSO outperformed comparable algorithms in accuracy and computational cost, especially in high-dimensional tasks, for One Max, 0/1 Knapsack, Multiple 0/1 Knapsack, Subset Sum, and Feature Selection problems.
For future works, we suggest a comparison between SBCSO and BCSO with different types of transfer functions. Moreover, we could compare SBCSO to P-Systems, which are efficient heuristic search algorithms for 0/1 Knapsack problems [92, 93].
Footnotes
Acknowledgments
The authors thank the FACEPE for the financial support, under grants BCT-0070-3.04/17, BCT-0066-1.03/17 and IBPG-0964-3.04/16. Additionally, the authors are grateful to the University of Pernambuco, CAPES and the Brazilian National Council for Scientific and Technological Development (CNPq), process number 405580/2018-5, for their financial support.
