Maximum-Score Diversity Selection

Cite This

Files in this item

Checksum: MD5:64947a3929f4ec4053e22c3cd6bc3856

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

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

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dspace:isPartOfCollection rdf:resource=""/> <dcterms:title>Maximum-Score Diversity Selection</dcterms:title> <dc:language>eng</dc:language> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dspace:hasBitstream rdf:resource=""/> <dc:format>application/pdf</dc:format> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:issued>2010</dcterms:issued> <bibo:uri rdf:resource=""/> <dcterms:hasPart rdf:resource=""/> <dcterms:available rdf:datatype="">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> <dcterms:isPartOf rdf:resource=""/> <dc:date rdf:datatype="">2011-03-24T16:11:20Z</dc:date> <dc:creator>Meinl, Thorsten</dc:creator> <dc:contributor>Meinl, Thorsten</dc:contributor> <dc:rights>terms-of-use</dc:rights> <dcterms:alternative>Maximum-Score Diversity Selection</dcterms:alternative> <dcterms:rights rdf:resource=""/> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

Diss_Meinl.pdf 251

This item appears in the following Collection(s)

terms-of-use Except where otherwise noted, this item's license is described as terms-of-use

Search KOPS


My Account