The Sharpened No Free Lunch theorem states that all optimization algorithms have the same performance on sets of functions that are closed under permutation, independently of the considered performance measure. However, not all performance measures are informative on how fast or how accurately an algorithm can solve a given problem. In this paper we focus on a particular performance measure, called optimization speed, that quanti fies how fast a search algorithm is able to find an optimal solution, and we try to characterize the set of functions on which all possible search algorithms have the same optimization speed. We call fair these sets, and we prove some results about their structure, the number of such sets and the computational complexity of checking fairness.

Valsecchi, A., Vanneschi, L., Mauri, G. (2010). Optimization speed and fair sets of functions. In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation - GECCO '10 (pp.1475-1476). New York : ACM Press [10.1145/1830483.1830753].

Optimization speed and fair sets of functions

VALSECCHI, ANDREA;VANNESCHI, LEONARDO;MAURI, GIANCARLO
2010

Abstract

The Sharpened No Free Lunch theorem states that all optimization algorithms have the same performance on sets of functions that are closed under permutation, independently of the considered performance measure. However, not all performance measures are informative on how fast or how accurately an algorithm can solve a given problem. In this paper we focus on a particular performance measure, called optimization speed, that quanti fies how fast a search algorithm is able to find an optimal solution, and we try to characterize the set of functions on which all possible search algorithms have the same optimization speed. We call fair these sets, and we prove some results about their structure, the number of such sets and the computational complexity of checking fairness.
abstract + slide
No Free Lunch Theorem; optimization speed
English
Conference of Genetic and Evolutionary Computation - GECCO
2010
Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation - GECCO '10
9781450300728
2010
1475
1476
none
Valsecchi, A., Vanneschi, L., Mauri, G. (2010). Optimization speed and fair sets of functions. In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation - GECCO '10 (pp.1475-1476). New York : ACM Press [10.1145/1830483.1830753].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/50709
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
Social impact