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-01-01
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.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
Open Access dal 29/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.