The Maximum Diversity Problem (MDP ) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pairwise diversities between the extracted elements. The MDP has recently been the subject of much research and several sophisticated heuristics have been proposed to solve it. The present work ompares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Though this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better.

Comparing Local Search Metaheuristics for the Maximum Diversity Problem

ARINGHIERI, ROBERTO;
2011

Abstract

The Maximum Diversity Problem (MDP ) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pairwise diversities between the extracted elements. The MDP has recently been the subject of much research and several sophisticated heuristics have been proposed to solve it. The present work ompares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Though this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better.
62
266
280
http://www.palgrave-journals.com/jors/journal/vaop/ncurrent/abs/jors2010104a.html
Roberto Aringhieri; Roberto Cordone
File in questo prodotto:
File Dimensione Formato  
2011-JORS-Published-AringhieriCordone.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 536.83 kB
Formato Adobe PDF
536.83 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2011-JORS-PostPrint.pdf

Accesso aperto con embargo fino al 28/01/2012

Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 655.65 kB
Formato Adobe PDF
655.65 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/75442
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 36
  • ???jsp.display-item.citation.isi??? 33
social impact