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-01-01
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
