The purpose of the Maximum Diversity Problem (MDP) is to extract from a set of elements N a subset M of given cardinality, such that the sum of the pairwise distances between the elements of M is maximum. It models several practical problems in fields such as human resource management, data mining, project financing, and so on. In the literature, it has been attacked both by metaheuristics focusing on refined constructive phases (GRASP) and on refined improvement phases (Tabu Search). In this paper, we describe the combination of the two approaches into an Ant Colony Optimization algorithm, which achieves a graceful interaction between diversification features (provided by the Ant Colony Optimization) and intensification features (mainly provided by Tabu Search). The resulting algorithm outperforms the construction-based algorithms and proves more robust than the improvement-based ones.

An ant colony optimization approach to the Maximum Diversity Problem

ARINGHIERI, ROBERTO;
2007

Abstract

The purpose of the Maximum Diversity Problem (MDP) is to extract from a set of elements N a subset M of given cardinality, such that the sum of the pairwise distances between the elements of M is maximum. It models several practical problems in fields such as human resource management, data mining, project financing, and so on. In the literature, it has been attacked both by metaheuristics focusing on refined constructive phases (GRASP) and on refined improvement phases (Tabu Search). In this paper, we describe the combination of the two approaches into an Ant Colony Optimization algorithm, which achieves a graceful interaction between diversification features (provided by the Ant Colony Optimization) and intensification features (mainly provided by Tabu Search). The resulting algorithm outperforms the construction-based algorithms and proves more robust than the improvement-based ones.
http://www.crema.unimi.it/Biblioteca/SchedaNota.asp?Nota=138
Roberto Aringhieri; Roberto Cordone; Yari Melzani
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/56911
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact