Maximum Diversity Problem. A Multi-Objective Approach

Abstract

The Maximum Diversity (MD) problem is the process of selecting a subset of elements where the diversity among selected elements is maximized. Several diversity measures were already studied in the literature, optimizing the problem considered in a pure mono-objective approach. This work presents for the first time multi-objective approaches for the MD problem, considering the simultaneous optimization of the following five diversity measures: (i) Max-Sum, (ii) Max-Min, (iii) Max-MinSum, (iv) Min-Diff and (v) Min-P-center. Two different optimization models are proposed: (i) Multi-Objective Maximum Diversity (MMD) model, where the number of elements to be selected is defined a-priori, and (ii) Multi-Objective Maximum Average Diversity (MMAD) model, where the number of elements to be selected is also a decision variable. To solve the formulated problems, a Multi-Objective Evolutionary Algorithm (MOEA) is presented. Experimental results demonstrate that the proposed MOEA found good quality solutions, i.e. between 98.85% and 100% of the optimal Pareto front when considering the hypervolume for comparison purposes.