A tabu search based memetic algorithm for the maximum diversity problem

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).

Authors

• Yang Wang
• Jin-Kao Hao
• Fred Glover
• Zhipeng Lü Huazhong University of Science and Technology

Keywords

• Combinatorial optimization
• Maximum diversity problem
• Metaheuristics
• Tabu search
• Memetic algorithm