A hybrid metaheuristic of integrating estimation of distribution algorithm with Tabu search for the max-mean dispersion problem

DOI10.1155/2019/7104702MaRDI QIDQ2298725zbMATH OpenOpenAlexFDO

Authors Dieudonné Nijimbere, Songzheng Zhao, Haichao Liu, Bo Peng, Aijun Zhang

Publication date 20 February 2020

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2019/7104702

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: This paper presents a hybrid metaheuristic that combines estimation of distribution algorithm with tabu search (EDA-TS) for solving the max-mean dispersion problem. The proposed EDA-TS algorithm essentially alternates between an EDA procedure for search diversification and a tabu search procedure for search intensification. The designed EDA procedure maintains an elite set of high quality solutions, based on which a conditional preference probability model is built for generating new diversified solutions. The tabu search procedure uses a fast 1-flip move operator for solution improvement. Experimental results on benchmark instances with variables ranging from 500 to 5000 disclose that our EDA-TS algorithm competes favorably with state-of-the-art algorithms in the literature. Additional analysis on the parameter sensitivity and the merit of the EDA procedure as well as the search balance between intensification and diversification sheds light on the effectiveness of the algorithm.

Recommendations

• Tabu search guided by reinforcement learning for the max-mean dispersion problem
• Hybrid heuristics for the maximum diversity problem
• A tabu search based memetic algorithm for the Max-Mean dispersion problem
• Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem
• A hybrid three-phase approach for the Max-Mean dispersion problem

Cites work

• A heuristic approach for the max-min diversity problem based on max-clique
• A hybrid heuristic approach based on a quadratic knapsack formulation for the max-mean dispersion problem
• A hybrid three-phase approach for the Max-Mean dispersion problem
• A simple and effective algorithm for the MaxMin diversity problem
• A survey of optimization by building and using probabilistic models
• A tabu search based memetic algorithm for the Max-Mean dispersion problem
• An efficient memetic algorithm for the graph partitioning problem
• An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering
• An exact semidefinite programming approach for the max-mean dispersion problem
• Construction and improvement algorithms for dispersion problems
• Effective metaheuristic algorithms for the minimum differential dispersion problem
• GRASP and path relinking for the equitable dispersion problem
• scientific article; zbMATH DE number 1754721 (Why is no real title available?)
• scientific article; zbMATH DE number 1754723 (Why is no real title available?)
• The equitable dispersion problem
• The quadratic balanced optimization problem

Cited in

(3)

• Effective metaheuristic algorithms for the minimum differential dispersion problem
• Tabu search guided by reinforcement learning for the max-mean dispersion problem
• Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem

This page was built for publication: A hybrid metaheuristic of integrating estimation of distribution algorithm with Tabu search for the max-mean dispersion problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2298725)