Maximum-Score Diversity Selection

Meinl, Thorsten

Maximum-Score Diversity Selection

Files

Diss_Meinl.pdf(9.04 MB)

Date

2010

Title in another language

Maximum-Score Diversity Selection

Publication type

Dissertation

Abstract

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.

Summary in another language

Diese Dissertation behandelt das Maximum-Score Diversity Selection (MSDS) Problem. Reine Diversitätsauswahl, wie sie bereits häufig z.B. in der frühen Wirkstoffforschung in der Pharmaindustrie eingesetzt wird, ist die Auswahl einer Teilmenge von Objekten die möglichst divers ist. MSDS führt ein zweites Kriterium ein, das neben der Optimierung der Diversität, auch die Bewertung ("score'') der Teilmenge optimieren soll (in der Regel die Summe der Bewertungen der einzelnen Objekte). Diese Kombination ist typisch für ein multikriterielles Optimierungsproblem, da sich beide Kriterien -- die Optimierung von sowohl Diversität als auch Bewertung -- in der Regel widersprechen. In dieser Dissertation werden verschiedene Möglichkeiten, dieses spezielle multikriterielle Optimierungsproblem effizient zu lösen, vorgestellt, entwickelt und bewertet. Nach einer ausführlicheren Diskussion der Anwendung von MSDS in der Wirkstoffforschung, wird die Frage nach passenden Definition von Diversität behandelt. Dies ist für die spätere konkrete Anwendung in verschiedenen Gebieten unerlässlich, da die Benutzer häufig nur eine vage Vorstellung von Diversität haben. Es folgt eine Formalisierung von MSDS und der Beweis, dass es sich um ein NP-schweres Optimierungsproblem handelt. Aus diesem Grund können, außer für kleinste Beispiele, keine exakten Lösungen effizient gefunden werden. Nachdem MSDS in den Kontext der multikriteriellen Optimierungsprobleme eingeordnet worden ist, wird die Verwendung von evolutionären Optimierungsverfahren -- im Speziellen genetischen Algorithmen -- untersucht. Das umfasst auch die Vorstellung von neuen genetischen Operatoren für die Erzeugung von Teilmengen oder Kombinationen von Objekten. Auf Grund ihrer universellen Einsetzbarkeit sind genetische Algorithmen oft nicht die beste Methode zur Lösung vieler Probleme, deswegen werden drei weitere problemspezifische Heuristiken diskutiert, von denen zwei leichte Modifikationen existierender Algorithmen zur reinen Diversitätsauswahl sind, und das dritte ein komplett neues Verfahren, genannt Score Erosion, ist. Mittels ausführlicher Tests und Vergleiche aller Methoden wird gezeigt, dass je nach gewählter Diversitätsdefinition alle Verfahren in der Lage sind, vergleichbare Lösungen zu finden, wobei Score Erosion der schnellste Algorithmus ist. Ebenso wird der Einfluss der Struktur des Suchraums genauer untersucht und ob die Anwendung MSDS in der Praxis Vorteile bringt.

Subject (DDC)

004 Computer Science

Keywords

Multiobjective optimization,heuristic,chemoinformatics,combinatorial optimization

Cite This

ISO 690

MEINL, Thorsten, 2010. Maximum-Score Diversity Selection [Dissertation]. Konstanz: University of Konstanz

BibTex

@phdthesis{Meinl2010Maxim-6306,
  year={2010},
  title={Maximum-Score Diversity Selection},
  author={Meinl, Thorsten},
  address={Konstanz},
  school={Universität Konstanz}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6306">
    <dcterms:issued>2010</dcterms:issued>
    <dc:creator>Meinl, Thorsten</dc:creator>
    <dc:contributor>Meinl, Thorsten</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:20Z</dcterms:available>
    <dcterms:abstract xml:lang="eng">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.</dcterms:abstract>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:format>application/pdf</dc:format>
    <dcterms:title>Maximum-Score Diversity Selection</dcterms:title>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6306/1/Diss_Meinl.pdf"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6306"/>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-sa/2.0/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6306/1/Diss_Meinl.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:20Z</dc:date>
    <dc:rights>Attribution-ShareAlike 2.0 Generic</dc:rights>
    <dcterms:alternative>Maximum-Score Diversity Selection</dcterms:alternative>
    <dc:language>eng</dc:language>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
  </rdf:Description>
</rdf:RDF>

Examination date of dissertation

July 9, 2010

Bibliography of Konstanz

Yes