6533b86ffe1ef96bd12cdc71

RESEARCH PRODUCT

Heuristics for the Bi-Objective Diversity Problem

Rafael MartíJosé Manuel ColmenarAbraham Duarte

subject

Mathematical optimization021103 operations researchOptimization problemComputer science0211 other engineering and technologiesGeneral Engineering02 engineering and technologyResolution (logic)Tabu searchComputer Science ApplicationsSet (abstract data type)Artificial IntelligenceGenetic algorithm0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingHeuristicsMetaheuristicVariable neighborhood searchGreedy randomized adaptive search procedure

description

Abstract The Max-Sum diversity and the Max-Min diversity are two well-known optimization models to capture the notion of selecting a subset of diverse points from a given set. The resolution of their associated optimization problems provides solutions of different structures, in both cases with desirable characteristics. They have been extensively studied and we can find many metaheuristic methodologies, such as Greedy Randomized Adaptive Search Procedure, Tabu Search, Iterated Greedy, Variable Neighborhood Search, and Genetic algorithms applied to them to obtain high quality solutions. In this paper we solve the bi-objective problem in which both models are simultaneously optimized. No previous effort has been devoted to study the “combined problem” from a multi-objective perspective. In particular, we adapt the mono-objective methodologies applied to this problem to the resolution of the bi-objective problem, obtaining approximations to its efficient front. An empirical comparison discloses the best alternative to tackle this NP -hard problem.

yearjournalcountryeditionlanguage
2018-10-01Expert Systems with Applications
https://doi.org/10.1016/j.eswa.2018.05.013