direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 31-2008

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Title
On the Size of Weights in Randomized Search Heuristics
Authors
Publication
To appear in Proceedings of the 10th Foundations of Genetic Algorithms, 2009.
Classification
not available
Keywords
evolutionary algorithms, randomized search heuristics
Abstract
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.
Source
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe