Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14404
For citation please use:
Main Title: On the Size of Weights in Randomized Search Heuristics
Author(s): Reichel, Joachim
Skutella, Martin
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15631
http://dx.doi.org/10.14279/depositonce-14404
License: http://rightsstatements.org/vocab/InC/1.0/
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.
Subject(s): evolutionary algorithms
randomized search heuristics
Issue Date: 2008
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2008, 31
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-031-2008.pdf
Format: Adobe PDF | Size: 352.99 kB
DownloadShow Preview
Thumbnail
Report-031-2008.ps.gz
Format: Unknown | Size: 323.55 kB
Download

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.