Maximum-Score Diversity Selection

Lade...
Vorschaubild
Dateien
Diss_Meinl.pdf
Diss_Meinl.pdfGröße: 9.04 MBDownloads: 323
Datum
2010
Autor:innen
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Gesperrt bis
Titel in einer weiteren Sprache
Maximum-Score Diversity Selection
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Dissertation
Publikationsstatus
Published
Erschienen in
Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

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.

Fachgebiet (DDC)
004 Informatik
Schlagwörter
Multiobjective optimization, heuristic, chemoinformatics, combinatorial optimization
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690MEINL, 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>
Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Kontakt
URL der Originalveröffentl.
Prüfdatum der URL
Prüfungsdatum der Dissertation
July 9, 2010
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen