Details for NCL-TR-2009005
PropertyValue
NameNCL-TR-2009005
Description
Free Lunch on the Discrete Lipschitz Class
Jiang, Pei
Abstract: The No-Free-Lunch theorem states that all algorithms have the identical performance on average over all functions and there is no algorithm able to outperform others on all problems. However, such a result does not imply that search heuristics or optimization algorithms are futile if we are more cautious with the applicability of these methods and the search space. In this paper, within the No-Free-Lunch framework, we firstly introduce the discrete Lipschitz class by transferring the Lipschitz functions, i.e., functions with bounded slope, as a measure to fulfill the notion of continuity in discrete functions. We then investigate the properties of the discrete Lipschitz class, generalize an algorithm called subthreshold-seeker for optimization, and show that the generalized subthreshold-seeker outperforms random search on this class. Finally, we propose a tractable sampling-test scheme to empirically demonstrate the superiority of the generalized subthreshold-seeker under practical configurations. This study concludes that there exists algorithms outperforming random search on the discrete Lipschitz class in both theoretical and practical aspects and indicates that the effectiveness of search heuristics may not be universal but still general in some broad sense.
FilenameNCL-TR-2009005.pdf
Filesize766.86 kB
Filetypepdf (Mime Type: application/pdf)
Creatorypchen
Created On: 10/19/2009 17:37
ViewersEverybody
Maintained byEditor
Hits2391 Hits
Last updated on 02/23/2011 18:36
Homepage