A tabu search based memetic algorithm for the maximum diversity problem

https://doi.org/10.1016/j.engappai.2013.09.005Get rights and content

Abstract

This paper presents a highly effective memetic algorithm for the maximum diversity problem based on tabu search. The tabu search component uses a successive filter candidate list strategy and the solution combination component employs a combination operator based on identifying strongly determined and consistent variables. Computational experiments on three sets of 40 popular benchmark instances indicate that our tabu search/memetic algorithm (TS/MA) can easily obtain the best known results for all the tested instances (where no previous algorithm has achieved) as well as improved results for six instances. Analysis of comparisons with state-of-the-art algorithms demonstrates statistically that our TS/MA competes very favorably with the best performing algorithms. Key elements and properties of TS/MA are also analyzed to disclose the benefits of integrating tabu search (using a successive filter candidate list strategy) and solution combination (based on critical variables).

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 N={e1,,en} 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):Maximizef(x)=12i=1nj=1ndij·xi·xjsubjecttoi=1nxi=m,xi{0,1},i=1,,nwhere each xi is a binary (zero-one) variable indicating whether an element eiN 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 Q=(qij), the UBQP problem is to identify a binary vector x of length n for the following function:Maximizeg(x)=xQx=i=1nj=1nqijxixj

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)

  • Andrade, P.M.F., Plastino, A., Ochi, L.S., Martins, S.L., 2003. GRASP for the maximum diversity problem. In:...
  • M.R.Q. Andrade et al.

    Grasp with path-relinking for the maximum diversity problem

  • R. Aringhieri et al.

    Optimal results and tight bounds for the maximum diversity problem

    Foundations of Computing and Decision Sciences

    (2009)
  • R. Aringhieri et al.

    Tabu search versus GRASP for the maximum diversity problem

    4 OR: A Quarterly Journal of Operations Research

    (2008)
  • R. Aringhieri et al.

    Comparing local search metaheuristics for the maximum diversity problem

    Journal of the Operational Research Society

    (2011)
  • Cited by (45)

    • A review on discrete diversity and dispersion maximization from an OR perspective

      2022, European Journal of Operational Research
      Citation 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.

    • An ILP based memetic algorithm for finding minimum positive influence dominating sets in social networks

      2018, Physica A: Statistical Mechanics and its Applications
      Citation 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.

    View all citing articles on Scopus
    View full text