Autor(en): Reichel, Joachim
Skutella, Martin
Titel: On the size of weights in randomized search heuristics
Sprache (ISO): en
Zusammenfassung: Runtime analyses of randomized search heuristics for combinatorial optimization problems often depend on the size of the largest weight. We consider replacing the given set of weights with smaller weights such that the behavior of the randomized search heuristic does not change. Upper bounds on the size of the new, equivalent weights allow us to obtain upper bounds on the expected runtime of such randomized search heuristics independent of the size of the actual weights. Furthermore we give lower bounds on the largest weights for worst-case instances. Finally we present some experimental results, including examples for worst-case instances.
Schlagwörter: analysis of algorithms and problem complexity
evolutionary algorithms
performance
randomized search heuristics
theory of computation
URI: http://hdl.handle.net/2003/26160
http://dx.doi.org/10.17877/DE290R-9027
Erscheinungsdatum: 2008-08
Enthalten in den Sammlungen:Sonderforschungsbereich (SFB) 531

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
25308.pdfDNB393.7 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource ist urheberrechtlich geschützt.



Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org