No-free-lunch theorems in the continuum

DOI10.1016/J.TCS.2015.07.029zbMATH Open1329.68233arXiv1409.2175OpenAlexW1582171764MaRDI QIDQ496010FDOQ496010

Authors: Aureli Alabert, Alessandro Berti, R. Caballero, Marco Ferrante 

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: No-Free-Lunch Theorems state, roughly speaking, that the performance of all search algorithms is the same when averaged over all possible objective functions. This fact was precisely formulated for the first time in a now famous paper by Wolpert and Macready, and then subsequently refined and extended by several authors, always in the context of a set of functions with discrete domain and codomain. Recently, Auger and Teytaud have shown that for continuum domains there is typically no No-Free-Lunch theorems. In this paper we provide another approach, which is simpler, requires less assumptions, relates the discrete and continuum cases, and that we believe that clarifies the role of the cardinality and structure of the domain.

Full work available at URL: https://arxiv.org/abs/1409.2175

Recommendations

• Continuous lunches are free plus the design of optimal optimization algorithms
• Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions.
• A ``no free lunch tutorial: sharpened and focused no free lunch
• A no-free-lunch theorem for non-uniform distributions of target functions
• Conditions that obviate the no-free-lunch theorems for optimization

zbMATH Keywords

stochastic processesblack-box optimisationno-free-lunch

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Title not available (Why is that?)
• A no-free-lunch theorem for non-uniform distributions of target functions
• Stochastic global optimization.
• Continuous lunches are free plus the design of optimal optimization algorithms
• Optimizing without derivatives: what does the no free lunch theorem actually say?
• On Positive-Definite Functions

Cited In (5)

• Continuous lunches are free plus the design of optimal optimization algorithms
• A performance analysis of Basin Hopping compared to established metaheuristics for global optimization
• Free lunches on the discrete Lipschitz class
• No free lunch theorem: a review
• A ``no free lunch tutorial: sharpened and focused no free lunch

This page was built for publication: No-free-lunch theorems in the continuum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496010)