Publikation:

Maximum-Score Diversity Selection

Lade...
Vorschaubild

Dateien

Diss_Meinl.pdf
Diss_Meinl.pdfGröße: 9.04 MBDownloads: 351

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
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

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

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