A heuristic search based on diversity for solving combinatorial problems

Francisco Casas (), Claudio E. Torres () and Ignacio Araya ()
Additional contact information
Francisco Casas: Universidad Técnica Federico Santa María
Claudio E. Torres: Universidad Técnica Federico Santa María
Ignacio Araya: Pontificia Universidad Católica de Valparaíso

Journal of Heuristics, 2022, vol. 28, issue 3, No 3, 287-328

Abstract: Abstract In this paper we propose a novel heuristic search for solving combinatorial optimization problems which we call Diverse Search (DS). Like beam search, this constructive approach expands only a selected subset of the solutions in each level of the search tree. However, instead of selecting the solutions with the best values, we use an efficient method to select a diverse subset, after filtering out uninteresting solutions. DS also distinguishes solutions that do not produce better offspring, and applies a local search process to them. The intuition is that the combination of these strategies allows to reach more—and more diverse—local optima, increasing the chances of finding the global optima. We test DS on several instances of the Köerkel–Ghosh (KG) and K-median benchmarks for the Simple Plant Location Problem. We compare it with a state-of-the-art heuristic for the KG benchmark and the relatively old POPSTAR solver, which also relies on the idea of maintaining a diverse set of solutions and, surprisingly, reached a comparable performance. With the use of a Path Relinking post-optimization step, DS can achieve results of the same quality that the state-of-the-art in similar CPU times. Furthermore, DS proved to be slightly better on average for large scale problems with small solution sizes, proving to be an efficient algorithm that delivers a set of good and diverse solutions.

Keywords: Facility location; Submodular function minimization; Tree search; Maximum diversity; Selection operator (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-022-09494-4 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:28:y:2022:i:3:d:10.1007_s10732-022-09494-4

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

DOI: 10.1007/s10732-022-09494-4

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