Clustering-driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problem

Michele Samorani (), Yang Wang (), Yang Wang (), Zhipeng Lv () and Fred Glover ()
Additional contact information
Michele Samorani: Santa Clara University
Yang Wang: Huazhong University of Science and Technology
Yang Wang: Northwestern Polytechnical University
Zhipeng Lv: Huazhong University of Science and Technology
Fred Glover: University of Colorado

Journal of Heuristics, 2019, vol. 25, issue 4, No 6, 629-642

Abstract: Abstract A long-standing challenge in the metaheuristic literature is to devise a way to select parent solutions in evolutionary population-based algorithms to yield better offspring, and thus provide improved solutions to populate successive generations. We identify a way to achieve this goal that simultaneously improves the efficiency of the evolutionary process. Our strategy derives from a proposal associated with the scatter search and path relinking evolutionary algorithms that prescribes clustering the solutions and focusing on the two classes of solution combinations where the parents alternatively belong to the same cluster or to different clusters. We demonstrate the efficacy of our approach for selecting parents within this scheme by applying it to the important domain of quadratic unconstrained binary optimization (QUBO), which provides a model for solving a wide range of binary optimization problems. Within this setting, we focus on the path relinking algorithm, which together with tabu search has provided one of the most effective methods for QUBO problems. Computational tests disclose that our solution combination strategy improves the best results in the literature for hard QUBO instances.

Keywords: Path relinking; Machine learning; Clustering; Quadratic unconstrained binary optimization; Tabu search (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9403-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:4:d:10.1007_s10732-018-9403-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9403-z

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().