A tabu search based memetic algorithm for the maximum diversity problem
Introduction
The maximum diversity problem (MDP) is to identify a subset M of a given cardinality m from a set of elements N, such that the sum of the pairwise distance between the elements in M is maximized. More precisely, let be a set of elements and dij be the distance between elements ei and ej. The objective of the MDP can be formulated as follows (Kuo et al., 1993):where each xi is a binary (zero-one) variable indicating whether an element is selected to be a member of the subset M.
The MDP is closely related to the unconstrained binary quadratic programming (UBQP) problem (Kochenberger et al., 2004, Lü et al., 2010, Wang et al., 2012). Given a symmetric n×n matrix , the UBQP problem is to identify a binary vector x of length n for the following function:
Contrasting the objective functions of the MDP and the UBQP, we observe that the MDP is a special UBQP with a cardinality constraint.
The MDP is an NP-hard problem and provides practical applications mainly including location, ecological systems, medical treatment, genetics, ethnicity, product design, immigration and admission policies, committee formation, curriculum design, and so on (Katayama and Narihisa, 2005, Martí et al., 2013).
Due to its theoretical significance and many potential applications, various solution procedures have been devised for the MDP problem. Exact algorithms are able to solve instances with less than 150 variables in reasonable computing time (Aringhieri et al., 2009, Martí et al., 2010). However, because of the high computational complexity, heuristic and metaheuristic algorithms are commonly used to produce approximate solutions for larger problem instances. Examples of these methods include various GRASP variants (Andrade et al., 2003, Andrade et al., 2005, Duarte and Marti, 2007, Silva et al., 2004, Silva et al., 2007), tabu search based algorithms (Aringhieri et al., 2008, Aringhieri and Cordone, 2011, Palubeckis, 2007, Wang et al., 2012), variable neighborhood search (Aringhieri and Cordone, 2011, Brimberg et al., 2009), scatter search (Aringhieri and Cordone, 2011), iterated greedy algorithm (Lozano et al., 2011) and hybrid evolutionary algorithm (Gallego et al., 2009, Katayama and Narihisa, 2005). A comprehensive review concerning the MDP and an interesting comparison among the best MDP algorithms can be found in Martí et al. (2013).
Our proposed TS/MA falls within the memetic algorithm classification as laid out in Neri et al. (2011) (and in particular adopts the scatter search template described in Glover (1997)). First, we use tabu search to improve each solution generated initially or created by combining members of a current population. The TS moves are simple swaps that flip (or add and drop) solution elements, drawing on the successive filter candidate list strategy to accelerate the move evaluations. Second, we design a solution combination operator to take advantage of solution properties by reference to the analysis of strongly determined and consistent variables. Finally, we introduce a population rebuilding strategy that effectively maintains population diversity.
In order to evaluate the performance of TS/MA, we conduct experimental tests on three sets of challenging benchmarks with a total of 40 instances. The test results indicate that TS/MA yields highly competitive outcomes on these instances by finding improved best known solutions for six instances and matching the best known results for the other instances. Furthermore, we analyze the influence of some critical components and demonstrate their key roles to the performance of the proposed TS/MA.
The rest of the paper is organized as follows. Section 2 describes the proposed TS/MA. Section 3 presents experimental results and comparisons with state-of-the-art algorithms in the literature. Section 3.3 analyzes several essential components of TS/MA. Concluding remarks are given in Section 4.
Section snippets
Tabu search/memetic algorithm
Algorithms that combine improvement methods with population-based solution combination algorithms, and hence that can be classified as memetic algorithms (Neri et al., 2011), often prove to be effective for discrete optimization (Hao, 2012). By linking the global character of recombinant search with the more intensive focus typically provided by local search, the memetic framework offers interesting possibilities to create a balance between intensification and diversification within a search
Benchmark instances
Three sets of benchmarks with a total of 40 large instances (with at least 2000 variables) are utilized to evaluate the performance of the proposed approach. Small and medium scale benchmarks are excluded in our experimentation because these problem instances can be easily solved by many heuristics in a very short time and can present no challenge for our TS/MA.
- (1)
Random type 1 instances (Type1_22): 20 instances with n=2000, m=200, where dij are integers generated from a [0,10] uniform
Conclusion
In this paper, we have proposed an effective memetic algorithm for the maximum diversity problem based on tabu search. The tabu search component utilizes a successive filter candidate list strategy and is joined with a solution combination strategy based on identifying strongly determined and consistent variables.
Computational experiments on three sets of 40 popular benchmark instances have demonstrated that the proposed TS/MA is capable of easily attaining all the previous best known results
Acknowledgments
We are grateful to the reviewers whose comments have helped to improve the quality of the paper. The work is partially supported by the Pays de la Loire Region (France) within the RaDaPop (2009-2013) and LigeRO (2010-2013) projects.
References (30)
- et al.
Variable neighborhood search for the heaviest-subgraph
Computers & Operations Research
(2009) - et al.
Tabu search and GRASP for the maximum diversity problem
European Journal of Operational Research
(2007) Tabu search for nonlinear and parametric optimization (with links to genetic algorithms)
Discrete Applied Mathematics
(1994)Computational aspects of the maximum diversity problem
Operation research letters
(1996)- et al.
Iterated greedy for the maximum diversity problem
European Journal of Operational Research
(2011) - et al.
A hybrid metaheuristic approach to solving the UBQP problem
European Journal of Operational Research
(2010) - et al.
A branch and bound algorithm for the maximum diversity problem
European Journal of Operational Research
(2010) Iterated tabu search for the maximum diversity problem
Applied Mathematics and Computation
(2007)- et al.
Path relinking for unconstrained binary quadratic programming
European Journal of Operational Research
(2012) - et al.
A hybrid metaheuristic method for the maximum diversity problem
European Journal of Operational Research
(2013)
Grasp with path-relinking for the maximum diversity problem
Optimal results and tight bounds for the maximum diversity problem
Foundations of Computing and Decision Sciences
Tabu search versus GRASP for the maximum diversity problem
4 OR: A Quarterly Journal of Operations Research
Comparing local search metaheuristics for the maximum diversity problem
Journal of the Operational Research Society
Cited by (45)
Solution-based tabu search for the capacitated dispersion problem
2023, Expert Systems with ApplicationsA review on discrete diversity and dispersion maximization from an OR perspective
2022, European Journal of Operational ResearchCitation Excerpt :This comparison reveals that, the first heuristics proposed in the early period, C2 and D2, perform very well considering their simplicity, and in the set of complex metaheuristics proposed in the expansion period, B-VNS (Brimberg et al., 2009) and ITS (Palubeckis, 2007) exhibit the best results (see Table 2). Since then, several new efficient methods have been published (see Section 4), being the Memetic Evolution Strategy MSES (De Freitas et al., 2014), the Memetic Tabu Search TS-MA (Wang et al., 2014) and the opposition-based memetic algorithm OBMA (Zhou & Hao, 2017) the most recent ones. We consider these seven methods and the solutions obtained with CPLEX in our comparison.
Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem
2022, Discrete OptimizationA two-phase tabu search based evolutionary algorithm for the maximum diversity problem
2022, Discrete OptimizationAn ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks
2018, Physica A: Statistical Mechanics and its ApplicationsCitation Excerpt :It is a population based evolutionary algorithm in which local search is used during the evolution. MA has successfully applied to solve a lot of optimization problems, such as global structural balance [24,25], robustness of scale-free networks [26], job shop scheduling problem [27,28], vehicle routing problem [29], graph partitioning problem [30], minimum sum coloring problem [31], maximum diversity problem [32], manufacturing problem [33]. These successful applications motivate us to developing a memetic algorithm for solving the minimum positive influence dominating set problem.