Maximum-Score Diversity Selection
Thorsten Meinl · KOPS (University of Konstanz) · 2010
This thesis discusses the problem of Maximum-Score Diversity Selection (MSDS). Pure diversity selection, as it is often performed e.g. in early drug discovery, is the selection of a subset of available objects that is as diverse as possible. MSDS adds a second objective, which additionally tries to maximize the "score'' of the subset, which usually is the sum of scores of all elements in the subset. Thus, this problem is a classical multi-objective optimization problem since both objectives -- maximizing score and maximizing diversity -- tend to conflict with each other. In this thesis several methods are presented, developed, and evaluated to efficiently solve this special multi-objective optimization problem. After a more detailed discussion about the application of MSDS in drug discovery, the question of suitable definitions of diversity is considered. This is essential for later application domains, where users have only a vague feeling of diversity. Then the Maximum-Score Diversity Selection problem is formalized and shown to be an NP-hard optimization problem. Therefore no exact solution can be computed efficiently for all but the smallest cases. After putting MSDS into the context of multi-objective optimization, the usage of evolutionary algorithms -- specifically genetic algorithms -- for solving the problem is evaluated. This also includes the presentation of novel genetic operators for evolving subsets or combinations of objects. However, being a universal tool, genetic algorithms may not be the best technique for the actual problem. Hence, several problem-specific heuristics are discussed, two of them motivated by the transformation of MSDS into a graph-theoretic problem used in the NP-hardness proof, and a novel heuristics methods, known as Score Erosion. The comparison of all approaches on various synthetic and real-world datasets reveals that all heuristics find solutions of similar quality, given the right measures of diversity, with Score Erosion being the fastest of all presented algorithm as a result of its linear time complexity. Also the questions are investigated as to how the structure of the search space influences the results and whether the application of MSDS pays off in practice.