# A Comprehensive Review on Scatter Search: Techniques, Applications, and Challenges

Authors: Minakshi Kalra; Shobhit Tyagi; Vijay Kumar; Manjit Kaur; Wali Khan Mashwani; Habib Shah; Kamal Shah
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

Recent years have witnessed the use of metaheuristic algorithms to solve the optimization problems that usually require extensive computations and time. Among others, scatter search is the widely used evolutionary metaheuristic algorithm. It uses the information of global optima, which is stored in a different and unique set of solutions. In this paper, an updated review of scatter search (SS) is given. SS has been successfully applied in a variety of research problems, namely, data mining, bioinformatics, and engineering design. This paper presents the modified and hybrid versions of SS with their applications. The control strategies are discussed to show their impact on the performance of SS. various issues and future directions related to SS are also discussed. It inspires innovative researchers to use this algorithm for their research domains.


---

## Body

## 1. Introduction

The real-life problems require a large number of variables and constraints, which makes the computation process complex. Some problems also include nonlinear constraints, large solution space, high computational cost, multiple local optimum solutions, and complexity [1]. Recently, it has been observed from the literature that metaheuristic algorithms are being used to solve the real-life problems such as medical imaging, remote sensing, engineering design problems, and traffic control management [2–4]. Unlike traditional algorithms whose main focus includes precision, accuracy, and completeness, metaheuristic algorithms (MHAs) focus on speed and efficiency. For a given problem, there is no guarantee that MHA produces the global optimal solution. However, they are able to produce an approximate solution using their intuitive and plausible arguments.MHAs are broadly classified into four main categories [5]. These are evolutionary algorithms (or EAs), trajectory-based algorithms (or TBAs), swarm-based algorithms (or SBAs), and physics-based metaheuristic algorithms (or PBAs) (see Figure 1). EAs are the algorithms, which are based on the evolution of species. These are based on the theory of Charles Darwin, “Survival of Fittest.” The fitness of a particular candidate is measured by its adaptation capability towards the environment [6]. Basically, EAs focus only on a subset of mechanisms defined over the biological evolutionary process. Some of the popular EAs are genetic algorithm (GA) [7], differential evolution (DE) [8], etc. Both GA and DE use the evolutionary process to find the best candidate solution with highest fitness value. Other EAs include biogeography-based optimizer (BBO) [9], genetic programming (GP) [10], and evolution strategy (ES) [11].Figure 1
Classification of metaheuristic algorithms.TBAs are inspired by biology to evolve a single trajectory of search points rather than the population. These are also known as human-based metaheuristic algorithms. The well-known single trajectory algorithms are tabu search (TS) [12], harmony search (HSA) [13], simulated annealing (SA) [14], and teaching-learning-based optimization (TLBO) [15]. PBAs are derived from the existing physical laws. Some of these algorithms are Central Force Optimization (CFO) [16], Big-Bang Big-Crunch (BBBC) [17], and Gravitational Search Algorithm (GSA) [18]. The search agents used by these algorithms can communicate with each other using the laws of physics such as laws of thermodynamics and gravitational force. SBAs are also known as swarm intelligence algorithms. These algorithms are derived by the “collective intelligence.” SBAs include flocks of birds, schools of fish, and colonies of ants. The well-known algorithms are particle swarm optimization (PSO) and ant colony optimization (ACO). PSO investigates probabilistic algorithms inspired by the flocking, schooling, and herding [19]. ACO are based on the behaviour of several species of ants [20]. Apart from PSO and ACO, other SBAs include artificial bee colony (ABC) algorithm [21], cuckoo search (CS) [22], bat-inspired algorithm (BA) [23], spiral spotted hyena optimizer (SSHO) [24], etc.Scatter search (SS) is a metaheuristic algorithm whose working is based on its sibling tabu search [12]. SS is useful for continuous as well as discrete optimization problems. SS shows the promising results for solving many nonlinear and combinatorial problems. SS can be used in many nonlinear optimization problems on bounded variables such as linear ordering problem, max clique problem, graph coloring problem, job shop scheduling, bipartite drawing problem, and capacitated multicommodity network design. Figure 2 shows the number of research articles published on SS according to Google Scholar (2013–2021).Figure 2
Number of publications on SS.The main attention of this paper is to present a comprehensive review of SS and encourage the young researchers to utilize SS in their research area. This paper discusses the control parameters of SS. The modification and hybridization of SS with other optimization techniques are discussed with pros and cons. The recent applications of SS are discussed with their methodologies and features. The possible future research directions for young researchers are also investigated.This paper summarizes the scatter search as follows:(1)
Workflow of SS that comprises the various components of SS(2)
Improvements in the performance of SS that comprise modification and hybridization with other optimization techniques(3)
Improvements in control parameters of SS that involve path relinking, subset reduction, set covering, and memory(4)
Applicability of SS that comprises scheduling, data mining, civil engineering, bioinformatics, and manufacturing(5)
Possible research direction of SS, which consists of modification and applicability of SS in different research domainsThe rest of this paper is structured as follows: Section2 presents the research methodology used in this review. Section 3 presents the classical scatter search along with its working procedure. In Section 4, the techniques used to improve scatter search are discussed. Section 5 presents the variants of scatter search. The applications of scatter search are mentioned in Section 6. Section 7 discusses future research directions followed by concluding remarks in Section 8.


## 2. Research Methodology

The guidelines of PRISMA [25] are used to conduct the systematic review of scatter search. The search has been conducted on four different databases such as Google Scholar, Scopus, PubMed, and arXiv during 20–25 April, 2021. Besides this, manual search has also been conducted to include the research articles. During search process, the query string comprises of “Scatter search” or “SS” or “((review) AND (scatter search))” or “tabu search” or “Applications of scatter search” or “((application) AND (SS))” or “((scatter search) AND (software engineering)” or “modified scatter search” or “improved SS”. The research articles related to advancement and hybridization in scatter search were also considered.After the identification, all the duplicate and irrelevant research articles were excluded. 246 research articles were considered for next phase of screening. After examining the titles and abstract of screened articles, 182 articles were eliminated. 64 articles were selected for eligibility phase. After reading the full articles, 34 articles were removed according to excluding criteria mentioned in Table1. Finally, 30 articles were considered for this review. Figure 3 shows the search process with including and excluding criteria.Table 1
Selection criteria used for shortlisting research articles.
S. No.ParameterInclude criteriaExclude criteria1AnalysisResearch articles involve the various control parameters of SSResearch articles involve the different control parameters of other metaheuristics2ComparisonResearch articles focus on the variants and control operators of SSResearch articles focus on the variants of other metaheuristics3ApplicationResearch articles on software engineering, civil, mechanical, manufacturing, bioinformatics, and networkingResearch articles on social-economics, environment, and society4StudyResearch involves mathematical foundation and experimental resultsResearch involves patent, articles in different language other than EnglishFigure 3
Research methodology used for shortlisting articles.


## 3. Classical Scatter Search

In this section, the inspiration behind the scatter search (SS) is discussed. Thereafter, the working of SS is presented.


### 3.1. Inspiration

The concept of SS is derived from tabu search (TS) [26]. Similar to TS, SS employed local searches for optimization. In local search, TS finds the similar solutions in their neighborhood that have minor differences with the hope of finding an improved solution. The problem with local searches is that they may stick up in the suboptimal or local regions. In TS, different moves are used to enhance their performance. The first move (also known as Worsening Move) is accepted if no improved move is found (i.e., in case of local search). The second move (known as prohibition) is used to back track the search for the earlier visited solutions. TS is implemented using memory structures that consist of user provided and visits solutions. If any potential solution violates a rule or visited again in short span of time, then this solution is marked as “tabu” (forbidden) and the search does not consider this solution again [26].


### 3.2. SS Algorithm

Scatter search (SS) algorithm was proposed by Glover in 1977 [27]. SS uses an iterative method in which the initial population of different and high-quality candidate solutions is partitioned into a set of subsets [28]. A set of subset solutions is known as reference set (RS), and they are used to create new ones. These subsets are linearly recombined using a predefined heuristic in the context of reference set (RS) whether the process is repeated or not. SS joins the subset solutions using Euclidean space to construct generalized paths. Unlike GA, SS uses relatively small population in the reference set (RS).Glover [29] presented a template for implementation of SS. According to this template, SS consists of five procedures to reach the final solution set. These are diversification generation, solution improvement, reference set update, subset generation, and solution combination methods. The relationship between input and output is illustrated in Table 2. The brief description of these methods is given in the succeeding subsections. The framework of SS is depicted in Figure 4.Table 2
Relationship between input and output of different procedures of SS.
ProcedureInputOutputLink to next procedureDiversification GenerationRandom seed solutionsDiverse trail solutionsImprovementImprovementDiverse trail solutionsEnhanced trail solutionsReference set updateReference set updateEnhanced trail solutionsSet of best solutionsSubset generationSubset generationSet of best solutionsSubset of solution for Reference setSolution combinationSolution combinationSubset of solution for Reference setCombined solutionsImprovementFigure 4
Framework of SS.


#### 3.2.1. Diversification Generation Method

Diversification Generation Method (DGM) is used to create distinct and different trial solutions [30]. These trial solutions become the basis for initializing the search process. These solutions are also known as arbitrary (or seed) solutions and are used as an input to the algorithm. SS generates high-grade results when DGM produces solutions that include a good mix of both quality and diversification. Examples of DGM include randomization, semigreedy, and greedy randomized adaptive search procedure (GRASP) [31]. Table 3 illustrates the different types of diversification generators that can be used to produce initial population.Table 3
Different types of diversification generators.
Generator typeDescriptionProsConsRandomRandomly selects a subset of variables to set the value of 1 for every solution producedEase to implement, few parameters are requiredDiversity in population is not mentionedSequentialThe solutions are produced that utilize seed solution, number of problem variables, and an approximation parameterFastGenerator does not ensure the quality of produced solutionsDichotomousThe variable set is partitioned into two subsets and complemented with seed solutionFast, better diversity than sequential generatorA small number of solutions are produced with no control over the qualityRelaxationProduces an initial population based on the objective valueBoth solution quality, diverse solutionsHigher temporal complexity


#### 3.2.2. Improvement Method

The improvement method (IM) is used to generate one or more unique trial solutions. IM converts the seed solution into an “enhanced” solution using some mechanism [31]. If the initial trial solution is the same as the improved solution, then the enhanced solution is to be considered as the input seed solution. The aim of IM is to improve the quality and feasibility of the input solution. The output of IM may be better than the original solution in terms of quality and feasibility. IM is able to handle both feasible and nonfeasible solutions. Some of IM are local search and variable neighborhood descent (VND). IM has deterministic orientation and termination criterion. In general, IM is designed for specific problems to provide specific results [32].


#### 3.2.3. Reference Set Update Method

DGM produces different solution set of large size (say,S). Typically, the size of S produced by DGM is much larger than reference set Refset. The initial Refset is built according to the reference set update method (RSUM). RSUM is used to update and build the population, which comes out from DGM and IM methods. RSUM consists of two steps [33]. Refset is a good mixture of highly different solutions, which are drawn from the initial S population. This step is carried out by different methods in different implementations of SS. From population S, the best set of solutions S/2 is selected using the values obtained from the objective function. This set is added to Refset and deleted from S. The remaining half is selected using a sophisticated measure called distance Dr,p. Here, r is the reference solution and p is the solution in S. The distance is measured by a method of designer’s choice but must follow certain usual metric conditions such as [34](1)Dr,p=0⇔r=p,Dr,q+Dq,p≥Dr,p.Euclidean distance is a commonly used method for continuous variables and is represented as [35](2)Dr,p=∑i=1nri−pi2.Hamming distance (or HD) is equal to the different number of bits in the corresponding string symbols [36]. Similarly, HD is the number of changes needed to convert one string to another bit by bit. The following mathematical formulation is used to compute HD:(3)Dr,p=∑i=1nvi,where(4)vi=0,ifri=pi,1,ifri≠pi.The distance is used to measure the minimum distance between population solutionp and the reference solutions r [32]:(5)Dminp=minr∈RefSetDr,p,p∗=p:maxp∈SDminp.This overall phase is repeated to produce the initialRefset. Dmin is updated as per the requirement. Now, p∗ is the new population solution that is going to be added in Refset. The new minimum distance can be rewritten as follows:(6)Dnew_minp=minDminp,Dp,p∗.In general, RSUM is executed for 500 iterations and the most differentRefset is chosen to initiate SS. At this point of time, the method is applied on trial solutions, that are produced by the subset generation, combination, and IM (see the steps 7–9) in framework of SS. The Euclidean distance computation can also be done by using maximum diversity problem (MDP). The diversity is calculated by the sum of distance between all pairs of elements present in the given set. MDP is nonlinear NP-hard problem, and SS procedure can be used to produce an optimal solution for such problems [32, 36].


#### 3.2.4. Subset Generation Method

The subset generation (SG) method provides input to CM. Initially, all the reference solutions are new. This set of solutions is the initialRefset on which SG method is used. SG method is a list of all pairs of reference solutions. Since the SG method works on the universe of all pairs of reference solutions, therefore, there must be a moderate size of Refset (typically 20). Each time the SG method is executed, the number of reference solutions depends upon the strategy implemented in the RSUM. In general, the number of 2 subsets produced by the SG method is calculated as follows [32, 37]:(7)nm+n2−m22,where n and m are the number of new and old solutions in the reference set, respectively. The generation of subsets can be carried out by many methods of different sizes by creating subset types. Table 4 shows the subset types in the SG method. Martí [38] studied the results of the SG method with different types of subsets. The studies also indicate that the subset Type-1 is an efficient and effective one. Most of SS implementations avoid the use of higher-dimension subsets.Table 4
Subset types in the SG method.
Subset typeDescriptionType-ISG contains two-element subsetsType-IIThree-element subsets constituted from two-element subsetsType-IIIFour-element subsets constituted from three-element subsetsType-IVSubsets constituted fromk-best elements (i.e., k lies in the range of [5, Refset])


#### 3.2.5. Combination Method

The combination method (CM) produces new trial solutions by combining the existing elements of different subsets. This method is directly related to the representation of solutions. In CM, each subset can create one or more new solutions that depend upon the specific form of solution. All solutions produced by CM are subjected to IM. All solutions produced by CM are subjected to IM and RSUM as outlined in Figure 5 dedicated for the procedure of SS.Figure 5
Procedure of SS.


## 3.1. Inspiration

The concept of SS is derived from tabu search (TS) [26]. Similar to TS, SS employed local searches for optimization. In local search, TS finds the similar solutions in their neighborhood that have minor differences with the hope of finding an improved solution. The problem with local searches is that they may stick up in the suboptimal or local regions. In TS, different moves are used to enhance their performance. The first move (also known as Worsening Move) is accepted if no improved move is found (i.e., in case of local search). The second move (known as prohibition) is used to back track the search for the earlier visited solutions. TS is implemented using memory structures that consist of user provided and visits solutions. If any potential solution violates a rule or visited again in short span of time, then this solution is marked as “tabu” (forbidden) and the search does not consider this solution again [26].


## 3.2. SS Algorithm

Scatter search (SS) algorithm was proposed by Glover in 1977 [27]. SS uses an iterative method in which the initial population of different and high-quality candidate solutions is partitioned into a set of subsets [28]. A set of subset solutions is known as reference set (RS), and they are used to create new ones. These subsets are linearly recombined using a predefined heuristic in the context of reference set (RS) whether the process is repeated or not. SS joins the subset solutions using Euclidean space to construct generalized paths. Unlike GA, SS uses relatively small population in the reference set (RS).Glover [29] presented a template for implementation of SS. According to this template, SS consists of five procedures to reach the final solution set. These are diversification generation, solution improvement, reference set update, subset generation, and solution combination methods. The relationship between input and output is illustrated in Table 2. The brief description of these methods is given in the succeeding subsections. The framework of SS is depicted in Figure 4.Table 2
Relationship between input and output of different procedures of SS.
ProcedureInputOutputLink to next procedureDiversification GenerationRandom seed solutionsDiverse trail solutionsImprovementImprovementDiverse trail solutionsEnhanced trail solutionsReference set updateReference set updateEnhanced trail solutionsSet of best solutionsSubset generationSubset generationSet of best solutionsSubset of solution for Reference setSolution combinationSolution combinationSubset of solution for Reference setCombined solutionsImprovementFigure 4
Framework of SS.


### 3.2.1. Diversification Generation Method

Diversification Generation Method (DGM) is used to create distinct and different trial solutions [30]. These trial solutions become the basis for initializing the search process. These solutions are also known as arbitrary (or seed) solutions and are used as an input to the algorithm. SS generates high-grade results when DGM produces solutions that include a good mix of both quality and diversification. Examples of DGM include randomization, semigreedy, and greedy randomized adaptive search procedure (GRASP) [31]. Table 3 illustrates the different types of diversification generators that can be used to produce initial population.Table 3
Different types of diversification generators.
Generator typeDescriptionProsConsRandomRandomly selects a subset of variables to set the value of 1 for every solution producedEase to implement, few parameters are requiredDiversity in population is not mentionedSequentialThe solutions are produced that utilize seed solution, number of problem variables, and an approximation parameterFastGenerator does not ensure the quality of produced solutionsDichotomousThe variable set is partitioned into two subsets and complemented with seed solutionFast, better diversity than sequential generatorA small number of solutions are produced with no control over the qualityRelaxationProduces an initial population based on the objective valueBoth solution quality, diverse solutionsHigher temporal complexity


### 3.2.2. Improvement Method

The improvement method (IM) is used to generate one or more unique trial solutions. IM converts the seed solution into an “enhanced” solution using some mechanism [31]. If the initial trial solution is the same as the improved solution, then the enhanced solution is to be considered as the input seed solution. The aim of IM is to improve the quality and feasibility of the input solution. The output of IM may be better than the original solution in terms of quality and feasibility. IM is able to handle both feasible and nonfeasible solutions. Some of IM are local search and variable neighborhood descent (VND). IM has deterministic orientation and termination criterion. In general, IM is designed for specific problems to provide specific results [32].


### 3.2.3. Reference Set Update Method

DGM produces different solution set of large size (say,S). Typically, the size of S produced by DGM is much larger than reference set Refset. The initial Refset is built according to the reference set update method (RSUM). RSUM is used to update and build the population, which comes out from DGM and IM methods. RSUM consists of two steps [33]. Refset is a good mixture of highly different solutions, which are drawn from the initial S population. This step is carried out by different methods in different implementations of SS. From population S, the best set of solutions S/2 is selected using the values obtained from the objective function. This set is added to Refset and deleted from S. The remaining half is selected using a sophisticated measure called distance Dr,p. Here, r is the reference solution and p is the solution in S. The distance is measured by a method of designer’s choice but must follow certain usual metric conditions such as [34](1)Dr,p=0⇔r=p,Dr,q+Dq,p≥Dr,p.Euclidean distance is a commonly used method for continuous variables and is represented as [35](2)Dr,p=∑i=1nri−pi2.Hamming distance (or HD) is equal to the different number of bits in the corresponding string symbols [36]. Similarly, HD is the number of changes needed to convert one string to another bit by bit. The following mathematical formulation is used to compute HD:(3)Dr,p=∑i=1nvi,where(4)vi=0,ifri=pi,1,ifri≠pi.The distance is used to measure the minimum distance between population solutionp and the reference solutions r [32]:(5)Dminp=minr∈RefSetDr,p,p∗=p:maxp∈SDminp.This overall phase is repeated to produce the initialRefset. Dmin is updated as per the requirement. Now, p∗ is the new population solution that is going to be added in Refset. The new minimum distance can be rewritten as follows:(6)Dnew_minp=minDminp,Dp,p∗.In general, RSUM is executed for 500 iterations and the most differentRefset is chosen to initiate SS. At this point of time, the method is applied on trial solutions, that are produced by the subset generation, combination, and IM (see the steps 7–9) in framework of SS. The Euclidean distance computation can also be done by using maximum diversity problem (MDP). The diversity is calculated by the sum of distance between all pairs of elements present in the given set. MDP is nonlinear NP-hard problem, and SS procedure can be used to produce an optimal solution for such problems [32, 36].


### 3.2.4. Subset Generation Method

The subset generation (SG) method provides input to CM. Initially, all the reference solutions are new. This set of solutions is the initialRefset on which SG method is used. SG method is a list of all pairs of reference solutions. Since the SG method works on the universe of all pairs of reference solutions, therefore, there must be a moderate size of Refset (typically 20). Each time the SG method is executed, the number of reference solutions depends upon the strategy implemented in the RSUM. In general, the number of 2 subsets produced by the SG method is calculated as follows [32, 37]:(7)nm+n2−m22,where n and m are the number of new and old solutions in the reference set, respectively. The generation of subsets can be carried out by many methods of different sizes by creating subset types. Table 4 shows the subset types in the SG method. Martí [38] studied the results of the SG method with different types of subsets. The studies also indicate that the subset Type-1 is an efficient and effective one. Most of SS implementations avoid the use of higher-dimension subsets.Table 4
Subset types in the SG method.
Subset typeDescriptionType-ISG contains two-element subsetsType-IIThree-element subsets constituted from two-element subsetsType-IIIFour-element subsets constituted from three-element subsetsType-IVSubsets constituted fromk-best elements (i.e., k lies in the range of [5, Refset])


### 3.2.5. Combination Method

The combination method (CM) produces new trial solutions by combining the existing elements of different subsets. This method is directly related to the representation of solutions. In CM, each subset can create one or more new solutions that depend upon the specific form of solution. All solutions produced by CM are subjected to IM. All solutions produced by CM are subjected to IM and RSUM as outlined in Figure 5 dedicated for the procedure of SS.Figure 5
Procedure of SS.


## 3.2.1. Diversification Generation Method

Diversification Generation Method (DGM) is used to create distinct and different trial solutions [30]. These trial solutions become the basis for initializing the search process. These solutions are also known as arbitrary (or seed) solutions and are used as an input to the algorithm. SS generates high-grade results when DGM produces solutions that include a good mix of both quality and diversification. Examples of DGM include randomization, semigreedy, and greedy randomized adaptive search procedure (GRASP) [31]. Table 3 illustrates the different types of diversification generators that can be used to produce initial population.Table 3
Different types of diversification generators.
Generator typeDescriptionProsConsRandomRandomly selects a subset of variables to set the value of 1 for every solution producedEase to implement, few parameters are requiredDiversity in population is not mentionedSequentialThe solutions are produced that utilize seed solution, number of problem variables, and an approximation parameterFastGenerator does not ensure the quality of produced solutionsDichotomousThe variable set is partitioned into two subsets and complemented with seed solutionFast, better diversity than sequential generatorA small number of solutions are produced with no control over the qualityRelaxationProduces an initial population based on the objective valueBoth solution quality, diverse solutionsHigher temporal complexity


## 3.2.2. Improvement Method

The improvement method (IM) is used to generate one or more unique trial solutions. IM converts the seed solution into an “enhanced” solution using some mechanism [31]. If the initial trial solution is the same as the improved solution, then the enhanced solution is to be considered as the input seed solution. The aim of IM is to improve the quality and feasibility of the input solution. The output of IM may be better than the original solution in terms of quality and feasibility. IM is able to handle both feasible and nonfeasible solutions. Some of IM are local search and variable neighborhood descent (VND). IM has deterministic orientation and termination criterion. In general, IM is designed for specific problems to provide specific results [32].


## 3.2.3. Reference Set Update Method

DGM produces different solution set of large size (say,S). Typically, the size of S produced by DGM is much larger than reference set Refset. The initial Refset is built according to the reference set update method (RSUM). RSUM is used to update and build the population, which comes out from DGM and IM methods. RSUM consists of two steps [33]. Refset is a good mixture of highly different solutions, which are drawn from the initial S population. This step is carried out by different methods in different implementations of SS. From population S, the best set of solutions S/2 is selected using the values obtained from the objective function. This set is added to Refset and deleted from S. The remaining half is selected using a sophisticated measure called distance Dr,p. Here, r is the reference solution and p is the solution in S. The distance is measured by a method of designer’s choice but must follow certain usual metric conditions such as [34](1)Dr,p=0⇔r=p,Dr,q+Dq,p≥Dr,p.Euclidean distance is a commonly used method for continuous variables and is represented as [35](2)Dr,p=∑i=1nri−pi2.Hamming distance (or HD) is equal to the different number of bits in the corresponding string symbols [36]. Similarly, HD is the number of changes needed to convert one string to another bit by bit. The following mathematical formulation is used to compute HD:(3)Dr,p=∑i=1nvi,where(4)vi=0,ifri=pi,1,ifri≠pi.The distance is used to measure the minimum distance between population solutionp and the reference solutions r [32]:(5)Dminp=minr∈RefSetDr,p,p∗=p:maxp∈SDminp.This overall phase is repeated to produce the initialRefset. Dmin is updated as per the requirement. Now, p∗ is the new population solution that is going to be added in Refset. The new minimum distance can be rewritten as follows:(6)Dnew_minp=minDminp,Dp,p∗.In general, RSUM is executed for 500 iterations and the most differentRefset is chosen to initiate SS. At this point of time, the method is applied on trial solutions, that are produced by the subset generation, combination, and IM (see the steps 7–9) in framework of SS. The Euclidean distance computation can also be done by using maximum diversity problem (MDP). The diversity is calculated by the sum of distance between all pairs of elements present in the given set. MDP is nonlinear NP-hard problem, and SS procedure can be used to produce an optimal solution for such problems [32, 36].


## 3.2.4. Subset Generation Method

The subset generation (SG) method provides input to CM. Initially, all the reference solutions are new. This set of solutions is the initialRefset on which SG method is used. SG method is a list of all pairs of reference solutions. Since the SG method works on the universe of all pairs of reference solutions, therefore, there must be a moderate size of Refset (typically 20). Each time the SG method is executed, the number of reference solutions depends upon the strategy implemented in the RSUM. In general, the number of 2 subsets produced by the SG method is calculated as follows [32, 37]:(7)nm+n2−m22,where n and m are the number of new and old solutions in the reference set, respectively. The generation of subsets can be carried out by many methods of different sizes by creating subset types. Table 4 shows the subset types in the SG method. Martí [38] studied the results of the SG method with different types of subsets. The studies also indicate that the subset Type-1 is an efficient and effective one. Most of SS implementations avoid the use of higher-dimension subsets.Table 4
Subset types in the SG method.
Subset typeDescriptionType-ISG contains two-element subsetsType-IIThree-element subsets constituted from two-element subsetsType-IIIFour-element subsets constituted from three-element subsetsType-IVSubsets constituted fromk-best elements (i.e., k lies in the range of [5, Refset])


## 3.2.5. Combination Method

The combination method (CM) produces new trial solutions by combining the existing elements of different subsets. This method is directly related to the representation of solutions. In CM, each subset can create one or more new solutions that depend upon the specific form of solution. All solutions produced by CM are subjected to IM. All solutions produced by CM are subjected to IM and RSUM as outlined in Figure 5 dedicated for the procedure of SS.Figure 5
Procedure of SS.


## 4. Control Strategies Used in SS

In the recent past, researchers have developed many methods/strategies for modification in components of SS to enhance the performance and efficiency. Modern designs of SS generally increase the complexity along with new additional search parameters. There is no algorithm that can be used systematically to improve the performance of SS implementation [32–34]. Some of advanced designs did not manifest the importance or ranking of these strategies [38]. Figure 6 depicts the strategies used to improve the design of SS.Figure 6
Strategies used to improve the design structure of SS.


### 4.1. Dynamic Update Strategy

Refset is the most important part in SS. During the search process, the SS method is incapable of improving the best solution found by CM for the same reference solutions. The output of CM is based on the diversity of Refset. Therefore, an advance CM gives an advantage even if the Refset is not built efficiently [39]. In the SS method, the static update strategy is used in which Refset is not updated until all pairs are not subjected to CM. The new Refset is built by selecting the best solutions from the solution pool, and the solutions are currently present in Refset.Dynamic updating strategy is a better approach to update the solutions inRefset. In this method, instead of waiting for all the solutions to be combined by the CM, the set is admitted immediately before the next combination is performed. If the new solution is admitted to Refset, then CM has to be applied on the newly inserted solution. Therefore, the solutions are either discarded or become the part of Refset as soon as they are produced. The main advantage of this approach is that the solutions of inferior quality will be discarded quickly and replaced with the newly produced solutions, which can be further used to create improved solutions. The promising solutions may be removed in special circumstances. Also, this method is more complex than the static updating of Refset. The dynamic updating approach can be used to fine-tune the procedure of SS.


### 4.2. Candidate Generation Strategy

Two well-known methods, namely, clustering and anticlustering are used to improve the candidate solution set. Glover [39] proposed a way to improve SS. This approach divides Refset into different clusters for selecting the parent solutions. This method operates with different subpopulations to produce new population [40]. These points may be present on different clusters that lead to diversification. The parents can be chosen alternatively. In “anticlustering,” the parents are selected to be as far as possible from different clusters within the same family of parents. Clustering gives the strategic advantage to SS.


### 4.3. Diversity Control Strategy

SS does not allow duplicates inRefset. The hash function is used to reduce the computation and duplicate solutions in Refset. The following hash function can be used to avoid duplicates and comparing solutions. Here, the solutions are represented with permutation x of size n:(8)Hx=∑i=1ni×xi2.The implementations of SS are designed to check the duplicates inRefset [40]. They generally do not check the diversity of the solution when creating the initial Refset. In Refsetrebuilding, the diversity of set B2 is strictly checked by some distance measure. Initially, the diversity of set B1 is not monitored. Therefore, a minimum diversity test can be used to check whether B1 has diversified solutions or not. The solutions should be chosen as members of the initial Refset.


### 4.4. Rebuilding Strategy

This approach is used when no new trial solutions are admitted toRefset. In this method, more diversified sets are created using the existing reference solutions. Refset is divided into two sets B1 and B2 of different or equal sizes [39]. The solution set B2 is removed from Refset. DGM is reinitialized with the goal of generating solutions that are diverse with respect to B1. Thereafter, DGM is used to construct new P solutions. B2 solutions in Refset are sequentially selected from P to maximize the diversity. To solve this problem, some distance measure is used. Refset is rebuilt to increase the diversity.


### 4.5. Solution Combination Strategy

Constructive linking and vocabulary building methods are used for solution combination [39, 40]. The constructive linking utilized the valuable neighborhoods for making offspring from the collection of parent solutions. The guiding solutions remain the same, but the initial solutions start as null or incomplete solutions.


## 4.1. Dynamic Update Strategy

Refset is the most important part in SS. During the search process, the SS method is incapable of improving the best solution found by CM for the same reference solutions. The output of CM is based on the diversity of Refset. Therefore, an advance CM gives an advantage even if the Refset is not built efficiently [39]. In the SS method, the static update strategy is used in which Refset is not updated until all pairs are not subjected to CM. The new Refset is built by selecting the best solutions from the solution pool, and the solutions are currently present in Refset.Dynamic updating strategy is a better approach to update the solutions inRefset. In this method, instead of waiting for all the solutions to be combined by the CM, the set is admitted immediately before the next combination is performed. If the new solution is admitted to Refset, then CM has to be applied on the newly inserted solution. Therefore, the solutions are either discarded or become the part of Refset as soon as they are produced. The main advantage of this approach is that the solutions of inferior quality will be discarded quickly and replaced with the newly produced solutions, which can be further used to create improved solutions. The promising solutions may be removed in special circumstances. Also, this method is more complex than the static updating of Refset. The dynamic updating approach can be used to fine-tune the procedure of SS.


## 4.2. Candidate Generation Strategy

Two well-known methods, namely, clustering and anticlustering are used to improve the candidate solution set. Glover [39] proposed a way to improve SS. This approach divides Refset into different clusters for selecting the parent solutions. This method operates with different subpopulations to produce new population [40]. These points may be present on different clusters that lead to diversification. The parents can be chosen alternatively. In “anticlustering,” the parents are selected to be as far as possible from different clusters within the same family of parents. Clustering gives the strategic advantage to SS.


## 4.3. Diversity Control Strategy

SS does not allow duplicates inRefset. The hash function is used to reduce the computation and duplicate solutions in Refset. The following hash function can be used to avoid duplicates and comparing solutions. Here, the solutions are represented with permutation x of size n:(8)Hx=∑i=1ni×xi2.The implementations of SS are designed to check the duplicates inRefset [40]. They generally do not check the diversity of the solution when creating the initial Refset. In Refsetrebuilding, the diversity of set B2 is strictly checked by some distance measure. Initially, the diversity of set B1 is not monitored. Therefore, a minimum diversity test can be used to check whether B1 has diversified solutions or not. The solutions should be chosen as members of the initial Refset.


## 4.4. Rebuilding Strategy

This approach is used when no new trial solutions are admitted toRefset. In this method, more diversified sets are created using the existing reference solutions. Refset is divided into two sets B1 and B2 of different or equal sizes [39]. The solution set B2 is removed from Refset. DGM is reinitialized with the goal of generating solutions that are diverse with respect to B1. Thereafter, DGM is used to construct new P solutions. B2 solutions in Refset are sequentially selected from P to maximize the diversity. To solve this problem, some distance measure is used. Refset is rebuilt to increase the diversity.


## 4.5. Solution Combination Strategy

Constructive linking and vocabulary building methods are used for solution combination [39, 40]. The constructive linking utilized the valuable neighborhoods for making offspring from the collection of parent solutions. The guiding solutions remain the same, but the initial solutions start as null or incomplete solutions.


## 5. Variants of SS

In the last few years, researchers have made various modifications in SS to deal with different research problems. The variants of SS are broadly categorized into four classes such as improved, hybrid, chaotic, and multiobjective (see Figure7). Figure 8 shows the percentage distribution of SS variants according to research articles. The summary of SS’s variants is illustrated in Table 5.Figure 7
Variants of SS.Figure 8
Percentage of SS variants according to research articles.Table 5
Summary of scatter search’s variants.
TypeAlgorithmDescriptionApplicationPerformanceRef.ImprovedESSOLModification is done in reference set by using opposition-based learning schemeKinetic models of biochemical systemsFaster convergence rate, avoid local optima[41]SSImprovement in reference setOptimization problemsImprovement in performance[42]CSSBLX-α operator, Solis and Wets algorithm, and Nelder–Mead simplex are employed to improve the performance of SSOptimization problemsBetter exploitation, better efficiency[43]HybridOQNLPLocal NLP solver is employed to enhance the global search ability of SSOptimization problemsImprovement in performance[46]Bee-SSBee algorithm is integrated with SS to enhance the improvement methodTraveling salesman problemMore computational time than SS, better performance[47]GA-SSCrossover and mutation are used to replace combination and improvementKnapsack problemBetter exploration capability[48]CS-SSCS is employed to enhance the improvement methodTraveling salesman problemBetter performance[49]VNS-SSVNS is used to replace both intensification and improvement components of SS to improve the quality solutionsInteger programming problemImprovement in performance[50]MCA-SSMCA is used to update the reference set and improvement method of SSTraveling salesman and job shop scheduling problemsBetter exploration capability[51]TS-SSTS is used to modify the search element for better exploration and exploitationFeedforward neural network problemBetter exploitation and exploration capability[52]DR-SSDR is employed to improve the search capability of SSMixed-integer programmingImproved performance[53]eDE-SSEnhanced DE is used to retain the quality solutions in long-term memoryQuadratic assignment and flow shop scheduling problemsImprove the effectiveness of SS[54]DE-SSPopulation reinitialization method is used to avoid the local optimaOptimization problemsRobust, better performance[55]ACO-SSACO is incorporated in SS to improve the search abilityMulticast routing problemsMinimize the cost[125]ChaoticChSSFour chaos maps are employed to generate CPRNG for SSFlow shop problemBetter exploration capability[56]BinaryBSSModification in diversification generation, improvement, and combination methodsKnapsack problem, maximum diversity problem, max-cut problemImprovement in performance[57]MultiobjectiveAbYSSPareto dominance, density estimation, and external archive are incorporated in SS to store nondominated solutionsOptimization problemsImprove the performance[58]SSMORanking, crowding, and Pareto dominance are incorporated in SSOptimization problemsImprove the performance[59]MOSSTS is used in the diversification generation method to generate Pareto-optimal solutionsOptimization problemsBetter convergence, reasonable computational time[60]SSPMOTS is employed in SS to improve the Pareto-optimal solutionsOptimization problemsBetter performance[61]MPSOSSA new leader selection is used to improve the convergence. PSO is incorporated in SS to improve spreadOptimization problemsBetter convergence rate, improve spread[62]RP-MOSSA new preference-based TS and SS are introducedOptimization problemsBetter Pareto-optimal solutions[63]MOSS-IITS and convex combination methods are used as the diversification generation method. A constraint handling mechanism is employed to handle multiple constrainsOptimization problemsImproved performance[64]MOSSSASA is employed as an improvement method. Fast archiving strategy is used to store the set of nondominated solutionsWater distribution networkImproved quality of network[65]


### 5.1. Improved SS

Remli et al. [41] developed an enhanced SS (ESS) for solving the parameter estimation problem in biochemical systems. Three modifications were done in RefSet formation, RefSet exploitation, and RefSet combination. ESS was further combined with opposition-based learning (ESSOL) to improve the performance. ESSOL was tested on 116 kinetic parameters in Chinese hamster ovary cells. This method provided the best solution with minimum computational time. Laguna and Martí [42] studied various updating mechanisms for reference set of SS. These mechanisms were used to maintain the balance between diversity and intensification during the search process. The performance of SS was evaluated on 40 different test problems. SS was able to generate the optimal solution for 30 out of 40 problems. Herrera et al. [43] introduced a continuous SS (CSS) based on the integration of BLX-α and improvement mechanisms such as Solis and Wets algorithm and Nelder–Mead simplex algorithm. The exploration capability of the Solis and Wets algorithm was used to enhance the best solutions for complex problems, whereas the exploration capability of the Nelder–Mead simplex algorithm to refine the best solutions for simple problems. The performance of CSS was assessed by testing it on 45 test functions and three real-life problems. The comparison results revealed the supremacy of SS over the existing techniques. Another version of continuous SS is presented in [44, 45].


### 5.2. Hybrid SS

Ugray et al. [46] presented an OQNLP to find the global optimal solution for mixed-integer problems. OptQuest known as commercial implementation of SS was used in OQNLP. Local NLP solver was incorporated in OptQuest to improve the search capability for optimization problems. OQNLP evaluated on 100 variables and 100 constraints. OQNLP was able to generate the optimal solutions for all problems. Sagheer et al. [47] implemented a hybrid algorithm based on the bee algorithm and SS to handle traveling salesman problem. The bee algorithm was incorporated in the improvement method to enhance the search capability of SS. This approach (Bee-SS) provided better solutions than the SS. However, the computational time of hybrid approach is larger than the SS. In [48], SS and GA were integrated to solve the knapsack problems. The crossover and mutation operators were used to replace the combination and improvement components of SS. The hybrid approach (GA-SS) attained the best solution for knapsack problem. However, the computational time of hybrid algorithm is little bit higher than the SS.Al-Obaidi [49] combined cuckoo search (CS) and SS (CS-SS) to solve the traveling salesman problem. CS was incorporated in SS to enhance the improvement method. The hybrid algorithm provided 23.2% improvement over SS in terms of fitness value. A new hybrid algorithm based on SS and variable neighborhood search (VNS) was proposed in [50]. VNS was used as an improvement procedure to improve the solutions. VNS-based SS (VNS-SS) performed better than the other algorithms. Alsaidi et al. [51] proposed a hybrid algorithm that combined SS and meerkat clan algorithm (MCA-SS). MCA was used to enhance the performance of the reference set and improvement method. The proposed algorithm was applied on traveling salesman and job shop scheduling problems. The experimental results revealed that the proposed hybrid algorithm was able to provide competitive results over the existing algorithms. El-Fallahi and Martí [52] integrated TS and SS (TS-SS) to solve the training problem of feedforward neural networks. TS incorporated elements for better balance between exploration and exploitation. The hybrid method utilized context information for move selection. The results indicated the effectiveness of TS-SS to solve the training problem of neural network over the existing algorithms. In [53], SS combined with direction rounding (DR-SS) to solve 0–1 mixed-integer programming problems.Davendra et al. [54] implemented a hybrid algorithm based on population algorithms (eDE-SS) to solve quadratic assignment and flow shop scheduling problems. The performance of the proposed hybrid algorithm was validated by using experiment methodology. The performance of the proposed hybrid algorithm clearly indicate the superiority of eDE-SS than some existing evolutionary algorithms in terms of proximity and diversity. Li and Tian [55] combined differential evolution (DE) and SS to solve the global optimization problems. The multiple mutation operators of DE were used to select the most appropriate mutation operator during the evolution process. The results revealed the superiority of the proposed hybrid algorithm over the other algorithms.


### 5.3. Chaotic SS

Davendra et al. [56] modified SS by incorporating the four different chaotic maps such as Burgers, Lozi, Tinkerbell, and Delayed Logistics. The chaos pseudorandom number generators (CPRNGs) were produced from chaotic maps. CPRNGs were utilized in SS to enhance the search capability of SS. The chaotic SS (ChSS) was used to solve the flow shop problem. The results of ChSS were compared with Mersenne Twister. The results revealed that the ChSS outperforms Mersenne Twister.


### 5.4. Binary SS

Gortázar et al. [57] proposed the adaptation of SS to solve the binary optimization problems. The binary-coded SS (BSS) was used to improve the exploitation process. Three diversification generation methods were designed to generate the binary vectors. An improvement method based on two neighborhoods was proposed to produce feasible solutions. Seven different combination methods were proposed to generate high-quality solutions. The effectiveness of BSS was evaluated on 376 problem instances. In terms of validation, BSS performed better than other techniques.


### 5.5. Multiobjective SS

Nebro et al. [58] developed an archive-based hybrid scatter search (AbYSS) to solve the multiobjective problems (MOPs). AbYSS incorporated the concepts of Pareto dominance, density estimation, and external archive. External archive was used to store the nondominated solutions. AbYSS was evaluated on benchmark test functions. The experimental results indicated the effectiveness of AbYSS to solve test functions over the existing algorithms. Nebro et al. [59] introduced SS to solve the MOPs. A nondominated sorting procedure was used to construct the reference set from the initial set. A mutation operator-based on local search was used to enhance the solutions obtained from the reference set. The multiobjective SS (SSMO) was evaluated on benchmark test functions. The experimental results indicated the superiority of SSMO over the existing multiobjective algorithms. Beausoleil [60] introduced a hybrid optimization algorithm based on integration of tabu and scatter search for solving MOPs. Tabu tenures were incorporated in SS to improve the diverse approximation to the Pareto-optimal solutions. The reference set was formed after each iteration of SS. A weighted sum approach was used to compute the solution quality. The results showed the effectiveness of MOSS in solving optimization problems. MOSS provided the better convergence than the other multiobjective algorithms.Molina et al. [61] proposed a multiobjective SS (SSPMO) that utilizes the concept of TS. In SSPMO, the reference set was obtained by choosing the optimal solutions from the initial set for each objective function. The remaining part of reference set was obtained by selecting the remaining optimal solutions in the set that maximized the distance to the solutions present in the reference set. The updating process was done in the initial set for obtaining the better quality solutions. SSPMO was able to provide the good Pareto-optimal solutions. Santana-Quintero et al. [62] presented a multiobjective evolutionary approach (MPSOSS) that utilizes the concept of PSO and SS. A new leader selection mechanism of PSO was used to enhance the convergence rate. SS was used to improve the nondominated solutions. The performance of MPSOSS was evaluated on benchmark test functions. MPSOSS outperforms NSGA-II in terms of convergence and quality solutions. Beausoleil [63] utilized the preference based on the reference points to design multiobjective tabu/scatter architecture (RP-MOSS). A novel mechanism was developed to generate the subsets of solution for designing the reference set. RP-MOSS was able to generate the better Pareto-optimal solutions than the other algorithms.In [64], a new version of multiobjective SS (MOSS-II) was developed to solve constrained problems. A constrained handling mechanism was presented to handle the multiple constraints. MOSS-II utilized TS and convex methods for the diversification generation component of SS. MOSS-II was able to generate the feasible solution for constrained problems. Baños et al. [65] proposed a multiobjective metaheuristic (MOSSSA) that combined SS and SA to solve water distribution network problem.


## 5.1. Improved SS

Remli et al. [41] developed an enhanced SS (ESS) for solving the parameter estimation problem in biochemical systems. Three modifications were done in RefSet formation, RefSet exploitation, and RefSet combination. ESS was further combined with opposition-based learning (ESSOL) to improve the performance. ESSOL was tested on 116 kinetic parameters in Chinese hamster ovary cells. This method provided the best solution with minimum computational time. Laguna and Martí [42] studied various updating mechanisms for reference set of SS. These mechanisms were used to maintain the balance between diversity and intensification during the search process. The performance of SS was evaluated on 40 different test problems. SS was able to generate the optimal solution for 30 out of 40 problems. Herrera et al. [43] introduced a continuous SS (CSS) based on the integration of BLX-α and improvement mechanisms such as Solis and Wets algorithm and Nelder–Mead simplex algorithm. The exploration capability of the Solis and Wets algorithm was used to enhance the best solutions for complex problems, whereas the exploration capability of the Nelder–Mead simplex algorithm to refine the best solutions for simple problems. The performance of CSS was assessed by testing it on 45 test functions and three real-life problems. The comparison results revealed the supremacy of SS over the existing techniques. Another version of continuous SS is presented in [44, 45].


## 5.2. Hybrid SS

Ugray et al. [46] presented an OQNLP to find the global optimal solution for mixed-integer problems. OptQuest known as commercial implementation of SS was used in OQNLP. Local NLP solver was incorporated in OptQuest to improve the search capability for optimization problems. OQNLP evaluated on 100 variables and 100 constraints. OQNLP was able to generate the optimal solutions for all problems. Sagheer et al. [47] implemented a hybrid algorithm based on the bee algorithm and SS to handle traveling salesman problem. The bee algorithm was incorporated in the improvement method to enhance the search capability of SS. This approach (Bee-SS) provided better solutions than the SS. However, the computational time of hybrid approach is larger than the SS. In [48], SS and GA were integrated to solve the knapsack problems. The crossover and mutation operators were used to replace the combination and improvement components of SS. The hybrid approach (GA-SS) attained the best solution for knapsack problem. However, the computational time of hybrid algorithm is little bit higher than the SS.Al-Obaidi [49] combined cuckoo search (CS) and SS (CS-SS) to solve the traveling salesman problem. CS was incorporated in SS to enhance the improvement method. The hybrid algorithm provided 23.2% improvement over SS in terms of fitness value. A new hybrid algorithm based on SS and variable neighborhood search (VNS) was proposed in [50]. VNS was used as an improvement procedure to improve the solutions. VNS-based SS (VNS-SS) performed better than the other algorithms. Alsaidi et al. [51] proposed a hybrid algorithm that combined SS and meerkat clan algorithm (MCA-SS). MCA was used to enhance the performance of the reference set and improvement method. The proposed algorithm was applied on traveling salesman and job shop scheduling problems. The experimental results revealed that the proposed hybrid algorithm was able to provide competitive results over the existing algorithms. El-Fallahi and Martí [52] integrated TS and SS (TS-SS) to solve the training problem of feedforward neural networks. TS incorporated elements for better balance between exploration and exploitation. The hybrid method utilized context information for move selection. The results indicated the effectiveness of TS-SS to solve the training problem of neural network over the existing algorithms. In [53], SS combined with direction rounding (DR-SS) to solve 0–1 mixed-integer programming problems.Davendra et al. [54] implemented a hybrid algorithm based on population algorithms (eDE-SS) to solve quadratic assignment and flow shop scheduling problems. The performance of the proposed hybrid algorithm was validated by using experiment methodology. The performance of the proposed hybrid algorithm clearly indicate the superiority of eDE-SS than some existing evolutionary algorithms in terms of proximity and diversity. Li and Tian [55] combined differential evolution (DE) and SS to solve the global optimization problems. The multiple mutation operators of DE were used to select the most appropriate mutation operator during the evolution process. The results revealed the superiority of the proposed hybrid algorithm over the other algorithms.


## 5.3. Chaotic SS

Davendra et al. [56] modified SS by incorporating the four different chaotic maps such as Burgers, Lozi, Tinkerbell, and Delayed Logistics. The chaos pseudorandom number generators (CPRNGs) were produced from chaotic maps. CPRNGs were utilized in SS to enhance the search capability of SS. The chaotic SS (ChSS) was used to solve the flow shop problem. The results of ChSS were compared with Mersenne Twister. The results revealed that the ChSS outperforms Mersenne Twister.


## 5.4. Binary SS

Gortázar et al. [57] proposed the adaptation of SS to solve the binary optimization problems. The binary-coded SS (BSS) was used to improve the exploitation process. Three diversification generation methods were designed to generate the binary vectors. An improvement method based on two neighborhoods was proposed to produce feasible solutions. Seven different combination methods were proposed to generate high-quality solutions. The effectiveness of BSS was evaluated on 376 problem instances. In terms of validation, BSS performed better than other techniques.


## 5.5. Multiobjective SS

Nebro et al. [58] developed an archive-based hybrid scatter search (AbYSS) to solve the multiobjective problems (MOPs). AbYSS incorporated the concepts of Pareto dominance, density estimation, and external archive. External archive was used to store the nondominated solutions. AbYSS was evaluated on benchmark test functions. The experimental results indicated the effectiveness of AbYSS to solve test functions over the existing algorithms. Nebro et al. [59] introduced SS to solve the MOPs. A nondominated sorting procedure was used to construct the reference set from the initial set. A mutation operator-based on local search was used to enhance the solutions obtained from the reference set. The multiobjective SS (SSMO) was evaluated on benchmark test functions. The experimental results indicated the superiority of SSMO over the existing multiobjective algorithms. Beausoleil [60] introduced a hybrid optimization algorithm based on integration of tabu and scatter search for solving MOPs. Tabu tenures were incorporated in SS to improve the diverse approximation to the Pareto-optimal solutions. The reference set was formed after each iteration of SS. A weighted sum approach was used to compute the solution quality. The results showed the effectiveness of MOSS in solving optimization problems. MOSS provided the better convergence than the other multiobjective algorithms.Molina et al. [61] proposed a multiobjective SS (SSPMO) that utilizes the concept of TS. In SSPMO, the reference set was obtained by choosing the optimal solutions from the initial set for each objective function. The remaining part of reference set was obtained by selecting the remaining optimal solutions in the set that maximized the distance to the solutions present in the reference set. The updating process was done in the initial set for obtaining the better quality solutions. SSPMO was able to provide the good Pareto-optimal solutions. Santana-Quintero et al. [62] presented a multiobjective evolutionary approach (MPSOSS) that utilizes the concept of PSO and SS. A new leader selection mechanism of PSO was used to enhance the convergence rate. SS was used to improve the nondominated solutions. The performance of MPSOSS was evaluated on benchmark test functions. MPSOSS outperforms NSGA-II in terms of convergence and quality solutions. Beausoleil [63] utilized the preference based on the reference points to design multiobjective tabu/scatter architecture (RP-MOSS). A novel mechanism was developed to generate the subsets of solution for designing the reference set. RP-MOSS was able to generate the better Pareto-optimal solutions than the other algorithms.In [64], a new version of multiobjective SS (MOSS-II) was developed to solve constrained problems. A constrained handling mechanism was presented to handle the multiple constraints. MOSS-II utilized TS and convex methods for the diversification generation component of SS. MOSS-II was able to generate the feasible solution for constrained problems. Baños et al. [65] proposed a multiobjective metaheuristic (MOSSSA) that combined SS and SA to solve water distribution network problem.


## 6. Scatter Search Applications

In the last few decades, SS has been used effectively in different research domains. The applications of SS are classified into following categories: data mining, image processing, bioinformatics, civil engineering, mechanical engineering, electrical engineering, industrial engineering, networking, healthcare, and software engineering. Figure9 depicts the applications of SS in different problem domains. The overview of different applications of SS is presented in Table 6.Figure 9
Applications of SS.Table 6
Summary of scatter search’s applications.
ApplicationProblemAlgorithmReferenceSchedulingFlow shop schedulingSS, MOSS, MSS hybrid SS[66–72]Project schedulingHybrid SS[73, 74]Home-care schedulingSS[75]Course timetablingSS[76]Exam timetablingSS, hybrid SS, parallel SS[77–81]Data MiningFeature selectionParallel SS, hybrid SS[82–84]Credit card fraud detectionHybrid SS[85]HealthcareProtein structure predictionSS[86, 87]Nurse rostering problemSS[88, 89]System biologySS[90]Image processingImage registrationSS[91–93]Industrial engineeringVehicle routing problemSS, hybrid SS[94–102]Facility layout problemSS[103–105]Territory design problemSS, MOSS[106, 107]Assembling/dissembling sequence problemSS, MOSS[108–112]Knapsack problemSS, hybrid SS[113–116]Electrical engineeringEconomic load dispatchSS, MOSS[117, 118]Power distributionSS[119]BioinformaticsDNA sequencingHybrid SS[120]Gene expressionSS[121]Chemical process optimizationSS[122]NetworkingRouting problemSS, hybrid SS[123–125]Network planning problemSS[126–129]Software engineeringSoftware testingSS[130–133]Software configurationSS[134, 135]Mechanical engineeringManufacturing systemSS, hybrid SS[136–138]Design problemSS[139–143]Fault detectionMOSS[144]Civil engineeringHigh toll identificationSS[145]Space allocation problemISS, hybrid SS[146, 147]Runway operationHybrid SS[148]Engineering optimizationLinear ordering problemSS[149, 150]Graph coloring problemSS[151]Quadratic assignment problemSS[152]p-median problemParallel SS[153]Permutation problemHybrid SS[154]Regret location problemParallel SS[155]SAT problemSS, hybrid SS[156, 157]Clique problemSS[158]Nonlinear optimization processSS[159–161]MiscellaneousBDDs minimizationSS[162]Craniofacial superimpositionSS[163]Joint replenishmentSS[164]Kinetic models of biochemicalSS[165]Cockpit crew rosteringHybrid SS[166, 167]E-mail spam detectionHybrid SS[168]Subset reductionHybrid SS[169]


### 6.1. Scheduling

Naderi and Ruiz [66] designed a modification in SS for distributed permutation flow shop scheduling problem (DPFSP). They used hybrid RefSet for solutions and job assignment vectors. These solutions and job assignment vectors were combined in the solution-combined procedure. This approach was tested on 720 large instances and obtained 589 new best solutions. Rahimi-Vahed et al. [67] utilized a MOSS to solve FSP that minimizes the completion time and tardiness simultaneously. An adaptive archive updating mechanism was proposed to alleviate nondominated solutions. The performance of MOSS was better than the strength Pareto evolutionary algorithm (SPEA-II). However, the computational time of MOSS is 3.5 times than the SPEA-II. Nowicki and Smutnicki [68] proposed a modified SS (MSS) for FSS with makespan criteria. They used big valley phenomenon. MSS was evaluated on 120 hard instances of twelve different sizes. MSS outperformed the exiting techniques in terms of accuracy. Geng et al. [69] incorporated PSO in SS to minimize the earliness and tardiness constraints of FSP. DE was also used to produce the quality solutions in SS. Ten different jobs were used to assess the performance of this hybrid SS approach. This approach has better search capability and convergence than PSO and GA. Hariharan and Nimal [70] combined GA and SS to minimize the completion time of PFSP. Twenty benchmark problems were used to evaluate the performance of combined approach. The combined approach provides better results than the other techniques. However, this approach did not consider the two important criteria such as due date and setup time. González et al. [71] hybridized tabu search with SS to solve the FSP. The neighborhood structures and distance measures were used to predict the completion time. This approach was able to enhance the 58 solution instances from 178 FSP instances [72].Sari et al. [73] evaluated both GA and SS on project scheduling problem (PSP). As many as 100 benchmark test problems were used to assess the performance of these algorithms. The increased number of iterations is significant in SS, but not in GA. Alvarez-Valdes et al. [74] designed a modification in SS for PSP with renewable resource constraint. The preprocessing techniques were used to reduce the number of variables and constraints. The proposed approach was able to obtain the optimal solutions for 3826 Schirmer test instances. Hiermann et al. [75] evaluated the performance of variable neighborhood search (VNS), memetic search (MS), SS, and SA for solving home healthcare scheduling problem. A random procedure was used to generate the initial solutions. Thereafter, the initial solutions were improved through the VNS, MS, SS, and SA. MS provides better solutions than SS, SA, and VNS.Jaradat and Ayob [76] used an SS to solve the timetabling problem. The reference set and combined solution procedures were used to maintain diverse solutions. A probabilistic selection method was used to produce the elite solutions. The optimal solutions were generated through iterated local search process. SS was tested on Socha’s instances and attained the good results as compared to the existing techniques. Mansour and Sleiman-Haidar [77] proposed a parallel SS algorithm for generating the optimal exam timetables within reasonable time duration. The candidate solutions were distributed over a number of processors. The procedures of SS were computed in parallel fashion. SS produced quality solutions in reasonable time duration. Mohammed et al. [78] utilized SS for producing the optimal exam timetables for Anbar University. SS was able to generate the satisfactory solutions for timetabling problems [79]. Mansour [80] proposed a heuristic technique based on SS for finding the optimal solutions for exam timetabling. This approach was tested on Lebanese American University and produced better examination timetables as compared to manual and other techniques such as SA and GA. Martí et al. [81] used an SS to assign the proctor to final examination of Universitat Pompeu Fabra. The solutions obtained from SS were compared with the CPLEX model. The solutions obtained from SS were inferior from the CPLEX model. However, the reference set of SS provides a large number of quality solutions.


### 6.2. Data Mining

López et al. [82] proposed a parallel SS to select the optimal features for classification. Instance-based learning, Naïve-Bayes, and C4.5 were incorporated in SS. The proposed approach was assessed on twelve UCI repository datasets. The parallel SS attained better accuracy than the sequential SS. The proposed approach achieved 76.2% average reduction in feature subsets. Wang et al. [83] combined both SS and rough set for feature selection. The radial basis function, logistic regression, and J48 were integrated in the hybrid approach. The conditional entropy was used to assess the solution quality. The Australian credit dataset and Japanese consumer credit dataset were used to evaluate the performance of proposed approach. The proposed approach achieved the classification accuracies of 88.9% and 90.5% for Australian credit and Japanese consumer credit datasets, respectively. Adi [84] introduced the parallel SS for classical problem. For the Gisette dataset, parallel SS enhanced the classification performance from 0.97 to 0.99. The execution time was reduced from 120 hours to 40 hours. Duman and Ozcelik [85] hybridized GA and SS to minimize the wrongly classified transactions for credit card fraud detection.


### 6.3. Healthcare

Boumedine and Bouroubi [86] proposed an SS to envisage the best conformation from the given sequence of amino acid. SS provided better results than the other algorithms in terms of low energy. Mansour et al. [87] presented an SS for prediction of 3D structures of proteins. The fitness function was used to minimize the energy function associated with protein structure. Protein Data Bank was used to assess the performance of SS and produce 3D structure with reasonable energy value. Burke et al. [88] presented SS for assigning the shifts to nurse, which ensure that sufficient nurses are available to perform her duties. SS provided quality solutions for seven out of ten test instances within reasonable time duration. Maenhout and Vanhoucke [89] proposed an SS for nurse scheduling. The fitness function was designed by considering the time preference, coverage constraints, and case-specific constraints. The proposed approach was able to generate the optimal schedule for nurses. Egea et al. [90] developed a MEIGO toolbox for solving problems associated with bioinformatics and system biology. They used enhanced SS, VNS, linear programming, and integer programming. The enhanced SS and VNS can be executed in sequential or parallel fashion.


### 6.4. Image Processing

Cordón et al. [91] used SS to solve the 3D image registration problem. This approach was tested on the BrainWeb database. SS provides better results than the improved iterative closet point matching (I-ICP). Cordón et al. [92] developed a mechanism for SS to combine and enhance the solutions for 3D image registration problem. A procedure was developed to maintain the balance between exploration and exploitation in reference set. The preprocessing of images was used to enhance the performance of SS. Both MRI and CT scan images were used to judge the efficiency of proposed SS. The proposed approach outperforms the existing techniques. Santamaría et al. [93] applied SS to solve the pairwise 3D image registration problem. SS was able to provide good results for 3D model reconstruction. However, it suffers from some shortcomings during 3D reconstruction.


### 6.5. Industrial Engineering

Euchi [94] hybridized GA and SS to determine the optimal routes that satisfy the demands of customers and suppliers with minimum transportation cost. SS was used to perform the local search. The hybrid approach was tested on 100–500 customer instances. This approach produced better solutions with in reasonable time. Belfiore and Yoshizaki [95] used SS to solve vehicle routing problem (VRP) with time windows and split deliveries. This approach was applied on 519 stores in eleven Brazilian states. SS offered better solutions than the existing techniques in terms of trucks and distribution cost. Tang et al. [96] applied SS on VRP. They used transportation cost and vehicle load to design the fitness function. The vehicle load considered as a variable factor for customers in each trip. The nearest neighbor method was used to improve the solutions. SS was able to produce good solutions for VRP. SS was successfully used to solve the variants of VRP [97–102].Hakli and Ortacay [103] implemented an improved version of SS (ISS) to solve incapacitated facility location (UFL). The crossover and mutation operators were incorporated in SS to enhance the search capability. ISS was applied on fifteen UFL problems from the OR-Lib dataset. This method shows superiority over the existing techniques. SS has been presented in [104] to solve facility layout problem. The performance of SS was tested on 58 large size instances. The results revealed that SS solved UFL problems and was able to reduce execution time. Xue and Li [105] used SS to solve container-loading problem. SS integrated with multiple neighborhood structures to improve the search ability of SS. SS attained optimal solution. Salazar-Aguilar et al. [106] proposed a MOSS to design the biobjective territory. The greedy random search procedure was used to improve the diversification generation component. The relinked local search was incorporated in an improvement component. The proposed approach was tested on large instances and outperformed the existing techniques in terms of feasible solutions. In [107], SS was used to select strip coils in shipping transportation.In [108], SS applied on disassembly sequence problem. SS was evaluated on 48 different products with up to 100 components. SS has shown 2% average improvement over REVERSE. Rahimi-Vahed et al. [109] implemented an MOSS to optimize utility work, product rate variation, and setup cost for assembly line sequencing problem. MOSS generated diverse nondominated solution that is closer to true Pareto front. However, the computational time of MOSS was 5.5 times than the MOGA. An improvement in SS is introduced in [110] for solving disassembly sequence problem. The solution improvement operator was used to enhance the solution quality. The improved SS (ISS) has less computational time than NSGA-II. ISS produced better optimal solutions than NSGA-II. However, this method did not consider the actual disassembly data. SS has successfully used to solve the mixed-model assembly line sequencing and knapsack problems [109, 111–116].


### 6.6. Electrical Engineering

Mizutani et al. [117] proposed an improvement in SS to forecast the correlation between input and ouput of power load. The weather information was incorporated in the proposed approach. The average correlation obtained from the proposed approach was 0.88. Costa e Silva et al. [118] developed an improved version of SS (ISS) to solve multiobjective environment/economic dispatch problem. The concepts of Pareto dominance and crowding were incorporated in SS. A new combination method strategy was proposed. The proposed approach was evaluated on the IEEE 30-bus six-generator system. ISS provided better solutions then the SS in terms of Pareto solutions. Posada et al. [119] implemented an SS to find the optimal location and price of distributed generation systems. The performance of SS was evaluated on 34 buses. The proposed approach provided 5.8% extra profit than the memetic algorithm.


### 6.7. Bioinformatics

Blazewicz et al. [120] integrated TS with SS to solve DNA sequencing problem. This approach works more efficiently and accurately to detect accurate sequence in comparison with TS, branch-and-bound, and hybrid GA algorithms. Nepomuceno et al. [121] introduced SS to determine biclusters from gene expression data. The correlation between genes was used to design a fitness function. The designed function was able to detect the different patterns from genes. This approach was evaluated on Yeast Cell Cycle, Human B-Cell Lymphoma, and Yeast Stress datasets. The performance of the proposed approach was better than the existing techniques in terms of fitness function. Egea et al. [122] implemented SS to solve the optimization process in chemical processes. Rebuilding was a key operation in reference set generation. The modifications have been done in the five components of SS. The experimental results revealed the supremacy of proposed approach over the other algorithms.


### 6.8. Networking

Greistorfer [123] utilized the SS in tabu search to solve the Chinese postman problem. The improvement procedure was modified. The solution combination method was used to combine the set of elite solutions. The hybrid approach was able to generate better solutions then the other techniques in terms of quality and computational time. Xu and Qu [124] introduced a new approach based on SS and path relinking (SSPR) to handle multicast routing problem. TS and VNS were used as local search for further improvement in SSPR. The benchmark instances taken from OR-library were used to evaluate the performance of SSPR. The results indicated that the SSPR with VNS performed better than the SSPR with TS in terms of cost. SSPR outperforms the existing techniques in terms of tree cost. Chunxin et al. [125] presented a hybrid approach (ACO-SS) for multicast routing problem. ACO was embedded in SS to avoid the premature convergence by using pheromone trails. The pheromone trail updating strategy was used to improve the solution quality. Twenty transmission nodes were used to assess the performance of ACO-SS. ACO-SS offers better solution than ACO in terms of average and minimum cost.Alvarez et al. [126] combined SS and GRASP to determine the feasible solutions for capacitated network design problem. The proposed approach was tested on different network instances. The comparison results showed the superiority of hybrid approach over CPLEX and Dual descent approaches in terms of optimal solution. In [127], GA was embedded in SS to generate better transmission solution for network expansion planning problem. Perez et al. [128] introduced SS to deal with deployment of dense wavelength division multiplexing (DWDM) in the place of fiber network. Diversification generation component of SS was used to allocate the spare capacity of existing network to demand raised by customers. SS was able to handle restoration problems associated with the network. Alvarez et al. [129] utilized SS to solve the multicommodity network design problem. It was shown from simulation results that SS has ability to determine the good solutions for large-scale problem within sufficient time.


### 6.9. Software Engineering

Blanco et al. [130] used SS to design the automatic test generators. The two different strategies were proposed for automatic generation of test cases. In the first strategy, a diversity mechanism was used to explore all the branches of program. The second strategy combined both diversity and local search methods to explore the unreachable branches of program. SS was able to generate the suitable test cases for branch coverage. SS and estimation of distributed algorithm (EDA) have been integrated by Sagarna and Lozano [131] to generate test cases automatically. The best solutions obtained from EDA were applied on SS generator. This approach suffers from diversity problem in some cases. SS has an ability to recover from this problem during rebuilding phase of the diversification method. In [133], SS was used to produce the test cases for covering all the branches of natural language processing (NLP) programs. The convergence rate of SS was better than the existing algorithms. SS was able to explore the all-possible branches of NLP programs.Bouridah and Belhadef [134] introduced SS to configure service function of network function virtualization. SS was able to produce the optimal number and placement of virtual functions. Yamashita et al. [135] used SS to find the optimal resource availability by considering the deadline and relations between project activities. 2400 instances were used to assess the performance of proposed approach. The average gap obtained from SS was 0.12% and 0.18% for 30 and 20 activities of project, respectively. The optimal solutions obtained from SS were 92% and 86% of problems from 30 to 20 activity sets, respectively.


### 6.10. Mechanical Engineering

Chinnusamy et al. [136] proposed an improved SS to design the optimal schedule for flexible manufacturing systems (FMSs). The dispatching rules were combined with Perti Net. The proposed approach performed better than the other techniques in terms of machine utilization. Krishna and Rao [137] implemented SS to find out optimal grinding parameters such as wheel speed, speed of work piece, dressing depth, and dressing lead. The weighted combination of production cost and surface finish was used to design the fitness function. The performance of SS was compared with GA, ACO, and quadratic programming. It is observed from results that SS outperformed the other algorithms. Prabu et al. [138] implemented SS to determine the optimal fixture layout with least deformation. The modification in diversification generation method was made to consider all layouts for the improvement method. SS performed better than GA in terms of computation time and convergence.Francois et al. [139] introduced SS to determine the optimal solutions for boiling water reactor problem. Tan et al. [140] studied the scheduling problem of steel making continuous casting. They integrated both SS and mixed-integer programming (MIP) to solve this problem. SS was used to find out the assignment and sequence variables for charges. Based on the results obtained from SS, MIP designed a constraint network. Thereafter, the constraint network was applied on optimization software. The hybrid approach was able to solve the scheduling problem. The various versions of SS were investigated to solve the permutation problems and MIP problems [141, 142]. Su et al. [143] integrated SS and neural networks to optimize the parameter optimization problem. The relationship between values of control factor and their measures was evaluated using neural networks. This relationship was applied on SS to obtain the optimal parameter setting. A desirability function was designed to convert several responses into single one. The applicability of hybrid approach was tested on blood strip manufacturing company situated in Taiwan. The results showed the superiority of hybrid approach over the other algorithms. Le et al. [144] used SS to determine fault in the design of Network-on-Chip (NOC). The simulation results revealed that the SS algorithm attained low-power consumption, high reliability, and less communication time as compared to GA and PSO.


### 6.11. Civil Engineering

González-Velarde et al. [145] introduced SS to increase the number of tolls and maintain the optimal traffic flow for transportation network. Zhang et al. [146] proposed an improvement in SS (ISS) to solve the corridor allocation problem. The improvement procedures were designed to handle the specific characteristics of allocation problem. The solution obtained from ISS was similar to GUROBI software. The experimental results revealed that ISS performed better performance than SA and SS in terms of solution quality. Beasley [147] combined SS and bionomic algorithms to determine the optimal landing sequence and scheduling of each aircraft. The performance of hybrid approach was assessed on 500 aircraft and 5 runways. The hybrid approach was able to produce the feasible solutions for aircraft landing problem. Soykan [148] presented a hybrid TS and SS approach to determine the optimal solutions for runway operation scheduling problem.


### 6.12. Engineering Optimization

Campos et al. [149, 150] implemented SS to solve the linear ordering problem. The improvement mechanisms were designed to combine solutions and maintain the balance between exploration and exploitation in reference set. SS was tested on both small and large instances of LOLIB. The computational time obtained from SS was reduced by 7% as compared to duplication checking mechanism. SS provided results better than the other techniques in terms of partial deviation. Hamiez and Hao [151] presented SS to solve graph coloring problem. An improvement was made in a set of configurations. The new configurations were replaced with others in terms of quality and diversity. The experimental results proved that SS was able to provide the optimal solutions for graph coloring problem. Cung et al. [152] proposed SS to handle quadratic assignment problem. A new operator was proposed to improve the solution quality. SS was evaluated on test problems of QAPLIB. The results showed that SS was able to provide the optimal solution.Garcia-López et al. [153] developed new strategies for parallelization of SS to enhance exploration and performance. The parallelization of SS was tested on large instance of p-median problem obtained from TSPLIB. The proposed approach provided best solution within reasonable time. Campos et al. [154] integrated both SS and TS to solve the permutation problems. This approach was compared with two commercial software and attained the optimal solution for permutation problems. Ibri et al. [155] proposed a parallel SS to solve the regret location problem. Results proved that the parallel SS performed better results than the exiting algorithms in terms of computational time and solution quality. In [156, 157], SS was implemented to solve SAT and W-MAX-SAT problems. Cavique et al. [158] developed an SS framework to solve the maximum clique problem. The guidance search and local search were incorporated in SS. SS provided the better feasible solutions than the competitive algorithms.Egea and Balsa-Canto [159] developed an enhanced SS (ESS) to handle the noise and discontinuities of nonlinear processes. A local search procedure was incorporated to speed up the convergence of quality solutions. The performance of ESS was assessed on four different test problems and attained the better efficiency and scalability over the existing state-of-art techniques. In the recent years, the variants of SS were applied on cardinality constrained and dynamic models [160, 161].


### 6.13. Miscellaneous

Hung et al. [162] investigated SS to minimize the reduced-ordered binary decision diagrams (BDDs). SS was able to provide the optimal BDD size than the SA and GA. Ibanez et al. [163] studied craniofacial superimposition technique in which images of a missing individual are compared with skull fund to determine whether the same individual or not. SS was used to develop a skull face overlay method. This method was tested on six different cases, which were taken from University of Granada. The method showed fast and accurate performance. Gutierrez et al. [164] investigated the performance of SS and RAND on joint replenishment problem. SS performed better than RAND for most of the cases. In some cases, SS produced the worse solution than RAND. However, the worse solution was not more than 0.119% worst solution of other algorithms. In [166, 167], SS was utilized to solve the cockpit crew rostering problem. Gharehchopogh and Amjad [168] hybridized SS and k-nearest neighbors (KNN) to handle the e-mail spam detection. The simulation results revealed that the hybrid approach performed better than C4.5 and provided 94.54% accuracy with 57 features. Wang et al. [169] proposed SS for attribute reduction in rough set. Thirteen different datasets were used to assess the performance of SS. The simulation results revealed that SS was able to provide quality solution for attribute reduction.


## 6.1. Scheduling

Naderi and Ruiz [66] designed a modification in SS for distributed permutation flow shop scheduling problem (DPFSP). They used hybrid RefSet for solutions and job assignment vectors. These solutions and job assignment vectors were combined in the solution-combined procedure. This approach was tested on 720 large instances and obtained 589 new best solutions. Rahimi-Vahed et al. [67] utilized a MOSS to solve FSP that minimizes the completion time and tardiness simultaneously. An adaptive archive updating mechanism was proposed to alleviate nondominated solutions. The performance of MOSS was better than the strength Pareto evolutionary algorithm (SPEA-II). However, the computational time of MOSS is 3.5 times than the SPEA-II. Nowicki and Smutnicki [68] proposed a modified SS (MSS) for FSS with makespan criteria. They used big valley phenomenon. MSS was evaluated on 120 hard instances of twelve different sizes. MSS outperformed the exiting techniques in terms of accuracy. Geng et al. [69] incorporated PSO in SS to minimize the earliness and tardiness constraints of FSP. DE was also used to produce the quality solutions in SS. Ten different jobs were used to assess the performance of this hybrid SS approach. This approach has better search capability and convergence than PSO and GA. Hariharan and Nimal [70] combined GA and SS to minimize the completion time of PFSP. Twenty benchmark problems were used to evaluate the performance of combined approach. The combined approach provides better results than the other techniques. However, this approach did not consider the two important criteria such as due date and setup time. González et al. [71] hybridized tabu search with SS to solve the FSP. The neighborhood structures and distance measures were used to predict the completion time. This approach was able to enhance the 58 solution instances from 178 FSP instances [72].Sari et al. [73] evaluated both GA and SS on project scheduling problem (PSP). As many as 100 benchmark test problems were used to assess the performance of these algorithms. The increased number of iterations is significant in SS, but not in GA. Alvarez-Valdes et al. [74] designed a modification in SS for PSP with renewable resource constraint. The preprocessing techniques were used to reduce the number of variables and constraints. The proposed approach was able to obtain the optimal solutions for 3826 Schirmer test instances. Hiermann et al. [75] evaluated the performance of variable neighborhood search (VNS), memetic search (MS), SS, and SA for solving home healthcare scheduling problem. A random procedure was used to generate the initial solutions. Thereafter, the initial solutions were improved through the VNS, MS, SS, and SA. MS provides better solutions than SS, SA, and VNS.Jaradat and Ayob [76] used an SS to solve the timetabling problem. The reference set and combined solution procedures were used to maintain diverse solutions. A probabilistic selection method was used to produce the elite solutions. The optimal solutions were generated through iterated local search process. SS was tested on Socha’s instances and attained the good results as compared to the existing techniques. Mansour and Sleiman-Haidar [77] proposed a parallel SS algorithm for generating the optimal exam timetables within reasonable time duration. The candidate solutions were distributed over a number of processors. The procedures of SS were computed in parallel fashion. SS produced quality solutions in reasonable time duration. Mohammed et al. [78] utilized SS for producing the optimal exam timetables for Anbar University. SS was able to generate the satisfactory solutions for timetabling problems [79]. Mansour [80] proposed a heuristic technique based on SS for finding the optimal solutions for exam timetabling. This approach was tested on Lebanese American University and produced better examination timetables as compared to manual and other techniques such as SA and GA. Martí et al. [81] used an SS to assign the proctor to final examination of Universitat Pompeu Fabra. The solutions obtained from SS were compared with the CPLEX model. The solutions obtained from SS were inferior from the CPLEX model. However, the reference set of SS provides a large number of quality solutions.


## 6.2. Data Mining

López et al. [82] proposed a parallel SS to select the optimal features for classification. Instance-based learning, Naïve-Bayes, and C4.5 were incorporated in SS. The proposed approach was assessed on twelve UCI repository datasets. The parallel SS attained better accuracy than the sequential SS. The proposed approach achieved 76.2% average reduction in feature subsets. Wang et al. [83] combined both SS and rough set for feature selection. The radial basis function, logistic regression, and J48 were integrated in the hybrid approach. The conditional entropy was used to assess the solution quality. The Australian credit dataset and Japanese consumer credit dataset were used to evaluate the performance of proposed approach. The proposed approach achieved the classification accuracies of 88.9% and 90.5% for Australian credit and Japanese consumer credit datasets, respectively. Adi [84] introduced the parallel SS for classical problem. For the Gisette dataset, parallel SS enhanced the classification performance from 0.97 to 0.99. The execution time was reduced from 120 hours to 40 hours. Duman and Ozcelik [85] hybridized GA and SS to minimize the wrongly classified transactions for credit card fraud detection.


## 6.3. Healthcare

Boumedine and Bouroubi [86] proposed an SS to envisage the best conformation from the given sequence of amino acid. SS provided better results than the other algorithms in terms of low energy. Mansour et al. [87] presented an SS for prediction of 3D structures of proteins. The fitness function was used to minimize the energy function associated with protein structure. Protein Data Bank was used to assess the performance of SS and produce 3D structure with reasonable energy value. Burke et al. [88] presented SS for assigning the shifts to nurse, which ensure that sufficient nurses are available to perform her duties. SS provided quality solutions for seven out of ten test instances within reasonable time duration. Maenhout and Vanhoucke [89] proposed an SS for nurse scheduling. The fitness function was designed by considering the time preference, coverage constraints, and case-specific constraints. The proposed approach was able to generate the optimal schedule for nurses. Egea et al. [90] developed a MEIGO toolbox for solving problems associated with bioinformatics and system biology. They used enhanced SS, VNS, linear programming, and integer programming. The enhanced SS and VNS can be executed in sequential or parallel fashion.


## 6.4. Image Processing

Cordón et al. [91] used SS to solve the 3D image registration problem. This approach was tested on the BrainWeb database. SS provides better results than the improved iterative closet point matching (I-ICP). Cordón et al. [92] developed a mechanism for SS to combine and enhance the solutions for 3D image registration problem. A procedure was developed to maintain the balance between exploration and exploitation in reference set. The preprocessing of images was used to enhance the performance of SS. Both MRI and CT scan images were used to judge the efficiency of proposed SS. The proposed approach outperforms the existing techniques. Santamaría et al. [93] applied SS to solve the pairwise 3D image registration problem. SS was able to provide good results for 3D model reconstruction. However, it suffers from some shortcomings during 3D reconstruction.


## 6.5. Industrial Engineering

Euchi [94] hybridized GA and SS to determine the optimal routes that satisfy the demands of customers and suppliers with minimum transportation cost. SS was used to perform the local search. The hybrid approach was tested on 100–500 customer instances. This approach produced better solutions with in reasonable time. Belfiore and Yoshizaki [95] used SS to solve vehicle routing problem (VRP) with time windows and split deliveries. This approach was applied on 519 stores in eleven Brazilian states. SS offered better solutions than the existing techniques in terms of trucks and distribution cost. Tang et al. [96] applied SS on VRP. They used transportation cost and vehicle load to design the fitness function. The vehicle load considered as a variable factor for customers in each trip. The nearest neighbor method was used to improve the solutions. SS was able to produce good solutions for VRP. SS was successfully used to solve the variants of VRP [97–102].Hakli and Ortacay [103] implemented an improved version of SS (ISS) to solve incapacitated facility location (UFL). The crossover and mutation operators were incorporated in SS to enhance the search capability. ISS was applied on fifteen UFL problems from the OR-Lib dataset. This method shows superiority over the existing techniques. SS has been presented in [104] to solve facility layout problem. The performance of SS was tested on 58 large size instances. The results revealed that SS solved UFL problems and was able to reduce execution time. Xue and Li [105] used SS to solve container-loading problem. SS integrated with multiple neighborhood structures to improve the search ability of SS. SS attained optimal solution. Salazar-Aguilar et al. [106] proposed a MOSS to design the biobjective territory. The greedy random search procedure was used to improve the diversification generation component. The relinked local search was incorporated in an improvement component. The proposed approach was tested on large instances and outperformed the existing techniques in terms of feasible solutions. In [107], SS was used to select strip coils in shipping transportation.In [108], SS applied on disassembly sequence problem. SS was evaluated on 48 different products with up to 100 components. SS has shown 2% average improvement over REVERSE. Rahimi-Vahed et al. [109] implemented an MOSS to optimize utility work, product rate variation, and setup cost for assembly line sequencing problem. MOSS generated diverse nondominated solution that is closer to true Pareto front. However, the computational time of MOSS was 5.5 times than the MOGA. An improvement in SS is introduced in [110] for solving disassembly sequence problem. The solution improvement operator was used to enhance the solution quality. The improved SS (ISS) has less computational time than NSGA-II. ISS produced better optimal solutions than NSGA-II. However, this method did not consider the actual disassembly data. SS has successfully used to solve the mixed-model assembly line sequencing and knapsack problems [109, 111–116].


## 6.6. Electrical Engineering

Mizutani et al. [117] proposed an improvement in SS to forecast the correlation between input and ouput of power load. The weather information was incorporated in the proposed approach. The average correlation obtained from the proposed approach was 0.88. Costa e Silva et al. [118] developed an improved version of SS (ISS) to solve multiobjective environment/economic dispatch problem. The concepts of Pareto dominance and crowding were incorporated in SS. A new combination method strategy was proposed. The proposed approach was evaluated on the IEEE 30-bus six-generator system. ISS provided better solutions then the SS in terms of Pareto solutions. Posada et al. [119] implemented an SS to find the optimal location and price of distributed generation systems. The performance of SS was evaluated on 34 buses. The proposed approach provided 5.8% extra profit than the memetic algorithm.


## 6.7. Bioinformatics

Blazewicz et al. [120] integrated TS with SS to solve DNA sequencing problem. This approach works more efficiently and accurately to detect accurate sequence in comparison with TS, branch-and-bound, and hybrid GA algorithms. Nepomuceno et al. [121] introduced SS to determine biclusters from gene expression data. The correlation between genes was used to design a fitness function. The designed function was able to detect the different patterns from genes. This approach was evaluated on Yeast Cell Cycle, Human B-Cell Lymphoma, and Yeast Stress datasets. The performance of the proposed approach was better than the existing techniques in terms of fitness function. Egea et al. [122] implemented SS to solve the optimization process in chemical processes. Rebuilding was a key operation in reference set generation. The modifications have been done in the five components of SS. The experimental results revealed the supremacy of proposed approach over the other algorithms.


## 6.8. Networking

Greistorfer [123] utilized the SS in tabu search to solve the Chinese postman problem. The improvement procedure was modified. The solution combination method was used to combine the set of elite solutions. The hybrid approach was able to generate better solutions then the other techniques in terms of quality and computational time. Xu and Qu [124] introduced a new approach based on SS and path relinking (SSPR) to handle multicast routing problem. TS and VNS were used as local search for further improvement in SSPR. The benchmark instances taken from OR-library were used to evaluate the performance of SSPR. The results indicated that the SSPR with VNS performed better than the SSPR with TS in terms of cost. SSPR outperforms the existing techniques in terms of tree cost. Chunxin et al. [125] presented a hybrid approach (ACO-SS) for multicast routing problem. ACO was embedded in SS to avoid the premature convergence by using pheromone trails. The pheromone trail updating strategy was used to improve the solution quality. Twenty transmission nodes were used to assess the performance of ACO-SS. ACO-SS offers better solution than ACO in terms of average and minimum cost.Alvarez et al. [126] combined SS and GRASP to determine the feasible solutions for capacitated network design problem. The proposed approach was tested on different network instances. The comparison results showed the superiority of hybrid approach over CPLEX and Dual descent approaches in terms of optimal solution. In [127], GA was embedded in SS to generate better transmission solution for network expansion planning problem. Perez et al. [128] introduced SS to deal with deployment of dense wavelength division multiplexing (DWDM) in the place of fiber network. Diversification generation component of SS was used to allocate the spare capacity of existing network to demand raised by customers. SS was able to handle restoration problems associated with the network. Alvarez et al. [129] utilized SS to solve the multicommodity network design problem. It was shown from simulation results that SS has ability to determine the good solutions for large-scale problem within sufficient time.


## 6.9. Software Engineering

Blanco et al. [130] used SS to design the automatic test generators. The two different strategies were proposed for automatic generation of test cases. In the first strategy, a diversity mechanism was used to explore all the branches of program. The second strategy combined both diversity and local search methods to explore the unreachable branches of program. SS was able to generate the suitable test cases for branch coverage. SS and estimation of distributed algorithm (EDA) have been integrated by Sagarna and Lozano [131] to generate test cases automatically. The best solutions obtained from EDA were applied on SS generator. This approach suffers from diversity problem in some cases. SS has an ability to recover from this problem during rebuilding phase of the diversification method. In [133], SS was used to produce the test cases for covering all the branches of natural language processing (NLP) programs. The convergence rate of SS was better than the existing algorithms. SS was able to explore the all-possible branches of NLP programs.Bouridah and Belhadef [134] introduced SS to configure service function of network function virtualization. SS was able to produce the optimal number and placement of virtual functions. Yamashita et al. [135] used SS to find the optimal resource availability by considering the deadline and relations between project activities. 2400 instances were used to assess the performance of proposed approach. The average gap obtained from SS was 0.12% and 0.18% for 30 and 20 activities of project, respectively. The optimal solutions obtained from SS were 92% and 86% of problems from 30 to 20 activity sets, respectively.


## 6.10. Mechanical Engineering

Chinnusamy et al. [136] proposed an improved SS to design the optimal schedule for flexible manufacturing systems (FMSs). The dispatching rules were combined with Perti Net. The proposed approach performed better than the other techniques in terms of machine utilization. Krishna and Rao [137] implemented SS to find out optimal grinding parameters such as wheel speed, speed of work piece, dressing depth, and dressing lead. The weighted combination of production cost and surface finish was used to design the fitness function. The performance of SS was compared with GA, ACO, and quadratic programming. It is observed from results that SS outperformed the other algorithms. Prabu et al. [138] implemented SS to determine the optimal fixture layout with least deformation. The modification in diversification generation method was made to consider all layouts for the improvement method. SS performed better than GA in terms of computation time and convergence.Francois et al. [139] introduced SS to determine the optimal solutions for boiling water reactor problem. Tan et al. [140] studied the scheduling problem of steel making continuous casting. They integrated both SS and mixed-integer programming (MIP) to solve this problem. SS was used to find out the assignment and sequence variables for charges. Based on the results obtained from SS, MIP designed a constraint network. Thereafter, the constraint network was applied on optimization software. The hybrid approach was able to solve the scheduling problem. The various versions of SS were investigated to solve the permutation problems and MIP problems [141, 142]. Su et al. [143] integrated SS and neural networks to optimize the parameter optimization problem. The relationship between values of control factor and their measures was evaluated using neural networks. This relationship was applied on SS to obtain the optimal parameter setting. A desirability function was designed to convert several responses into single one. The applicability of hybrid approach was tested on blood strip manufacturing company situated in Taiwan. The results showed the superiority of hybrid approach over the other algorithms. Le et al. [144] used SS to determine fault in the design of Network-on-Chip (NOC). The simulation results revealed that the SS algorithm attained low-power consumption, high reliability, and less communication time as compared to GA and PSO.


## 6.11. Civil Engineering

González-Velarde et al. [145] introduced SS to increase the number of tolls and maintain the optimal traffic flow for transportation network. Zhang et al. [146] proposed an improvement in SS (ISS) to solve the corridor allocation problem. The improvement procedures were designed to handle the specific characteristics of allocation problem. The solution obtained from ISS was similar to GUROBI software. The experimental results revealed that ISS performed better performance than SA and SS in terms of solution quality. Beasley [147] combined SS and bionomic algorithms to determine the optimal landing sequence and scheduling of each aircraft. The performance of hybrid approach was assessed on 500 aircraft and 5 runways. The hybrid approach was able to produce the feasible solutions for aircraft landing problem. Soykan [148] presented a hybrid TS and SS approach to determine the optimal solutions for runway operation scheduling problem.


## 6.12. Engineering Optimization

Campos et al. [149, 150] implemented SS to solve the linear ordering problem. The improvement mechanisms were designed to combine solutions and maintain the balance between exploration and exploitation in reference set. SS was tested on both small and large instances of LOLIB. The computational time obtained from SS was reduced by 7% as compared to duplication checking mechanism. SS provided results better than the other techniques in terms of partial deviation. Hamiez and Hao [151] presented SS to solve graph coloring problem. An improvement was made in a set of configurations. The new configurations were replaced with others in terms of quality and diversity. The experimental results proved that SS was able to provide the optimal solutions for graph coloring problem. Cung et al. [152] proposed SS to handle quadratic assignment problem. A new operator was proposed to improve the solution quality. SS was evaluated on test problems of QAPLIB. The results showed that SS was able to provide the optimal solution.Garcia-López et al. [153] developed new strategies for parallelization of SS to enhance exploration and performance. The parallelization of SS was tested on large instance of p-median problem obtained from TSPLIB. The proposed approach provided best solution within reasonable time. Campos et al. [154] integrated both SS and TS to solve the permutation problems. This approach was compared with two commercial software and attained the optimal solution for permutation problems. Ibri et al. [155] proposed a parallel SS to solve the regret location problem. Results proved that the parallel SS performed better results than the exiting algorithms in terms of computational time and solution quality. In [156, 157], SS was implemented to solve SAT and W-MAX-SAT problems. Cavique et al. [158] developed an SS framework to solve the maximum clique problem. The guidance search and local search were incorporated in SS. SS provided the better feasible solutions than the competitive algorithms.Egea and Balsa-Canto [159] developed an enhanced SS (ESS) to handle the noise and discontinuities of nonlinear processes. A local search procedure was incorporated to speed up the convergence of quality solutions. The performance of ESS was assessed on four different test problems and attained the better efficiency and scalability over the existing state-of-art techniques. In the recent years, the variants of SS were applied on cardinality constrained and dynamic models [160, 161].


## 6.13. Miscellaneous

Hung et al. [162] investigated SS to minimize the reduced-ordered binary decision diagrams (BDDs). SS was able to provide the optimal BDD size than the SA and GA. Ibanez et al. [163] studied craniofacial superimposition technique in which images of a missing individual are compared with skull fund to determine whether the same individual or not. SS was used to develop a skull face overlay method. This method was tested on six different cases, which were taken from University of Granada. The method showed fast and accurate performance. Gutierrez et al. [164] investigated the performance of SS and RAND on joint replenishment problem. SS performed better than RAND for most of the cases. In some cases, SS produced the worse solution than RAND. However, the worse solution was not more than 0.119% worst solution of other algorithms. In [166, 167], SS was utilized to solve the cockpit crew rostering problem. Gharehchopogh and Amjad [168] hybridized SS and k-nearest neighbors (KNN) to handle the e-mail spam detection. The simulation results revealed that the hybrid approach performed better than C4.5 and provided 94.54% accuracy with 57 features. Wang et al. [169] proposed SS for attribute reduction in rough set. Thirteen different datasets were used to assess the performance of SS. The simulation results revealed that SS was able to provide quality solution for attribute reduction.


## 7. Future Research Directions

In last few years, researchers have modified the design structure of SS by using control strategies and integrating the other optimization algorithms. Besides this, there are still few open research areas. The future research directions of SS are given below.


### 7.1. Many-Objective Optimization

SS has not been applied on many-objective optimization problems. SS used Pareto-optimal dominance concept to solve multiobjective problems. The concepts of reference vector adaption strategy, knee points, and hypervolume have to be incorporated in SS to show its efficiency for many-objective problems. There is need to investigate the adaptive archive strategy in SS.


### 7.2. Binary Optimization

In binary SS, the representation of solution vectors is transformed in binary form. There is a need to use the different transfer functions in SS to solve binary problems. S-shaped and V-shaped functions have to be incorporated in SS to check the performance of SS. Recently, Z-shaped functions are developed. These functions have to be added in SS to evaluate the performance of SS in binary space.


### 7.3. Theoretical Evaluation of SS Structure

The theoretical analysis of modified and hybrid SS has not done by researchers. Therefore, theoretical evaluation of SS is required for detailed analysis. Besides this, the theoretical study of control strategies and structure of SS is required.


### 7.4. New Data Modalities

SS has limited applicability in image processing problems. Yet, SS has shown good results on image registration for 3D image scan. SS has to be applied on other problems such as image segmentation, filtering, and edge detection. Besides this, the applicability of SS has to be tested on different data modalities such as CT scan, MRI, and X-ray images for medical imaging.


## 7.1. Many-Objective Optimization

SS has not been applied on many-objective optimization problems. SS used Pareto-optimal dominance concept to solve multiobjective problems. The concepts of reference vector adaption strategy, knee points, and hypervolume have to be incorporated in SS to show its efficiency for many-objective problems. There is need to investigate the adaptive archive strategy in SS.


## 7.2. Binary Optimization

In binary SS, the representation of solution vectors is transformed in binary form. There is a need to use the different transfer functions in SS to solve binary problems. S-shaped and V-shaped functions have to be incorporated in SS to check the performance of SS. Recently, Z-shaped functions are developed. These functions have to be added in SS to evaluate the performance of SS in binary space.


## 7.3. Theoretical Evaluation of SS Structure

The theoretical analysis of modified and hybrid SS has not done by researchers. Therefore, theoretical evaluation of SS is required for detailed analysis. Besides this, the theoretical study of control strategies and structure of SS is required.


## 7.4. New Data Modalities

SS has limited applicability in image processing problems. Yet, SS has shown good results on image registration for 3D image scan. SS has to be applied on other problems such as image segmentation, filtering, and edge detection. Besides this, the applicability of SS has to be tested on different data modalities such as CT scan, MRI, and X-ray images for medical imaging.


## 8. Conclusion

A comprehensive review of the SS algorithm is presented in this paper. The main focus of this paper is to summarize the variants and applications of SS. The variants of SS, namely, improved, hybrid, binary, chaotic, and multiobjective assisted to improve the performance of SS. SS has advantages over the other algorithms in terms of simplicity, flexibility, and hybridization with other algorithms. However, SS is being stuck in local optima for some cases. The appropriate selection of control strategies helped to improve the exploration and exploitation properties of SS. SS has been successfully applied on engineering design problems, data mining, bioinformatics, and networking problems. The future research directions are provided in this paper, which can motive the innovative researchers for further research in their research domains. The researchers can work on SS to find out its efficiency and effectiveness on their research problems.



---

*Source: 5588486-2021-05-31.xml*