Abstract
dc:description.abstractThe No Free Lunch (NFL) theorems for optimization tell us that when averaged over all possible optimization problems the performance of any two optimization algorithms is statistically identical. This seems to imply that there are no "general-purpose" optimization algorithms. That is, the NFL theorems show that, mathematically, any superior performance of an optimization algorithm on one set of problems is offset by inferior performance of that algorithm on the set of all other problems. In this thesis we consider the seemingly negative implications of the NFL theorems. We first extend a previous NFL theorem to get a new NFL result. We then use ideas from probability theory and cryptography to show that if we believe that extraordinarily small probability events will not happen, then there exists (at least) one algorithm that is indeed a general-purpose algorithm. Thus, the implications of the new NFL result are not as negative as expected.
Degree
thesis:*- Name thesis:degree_name
- MS
- Level thesis:degree_level
- Immediate Access
- Discipline thesis:degree_discipline
- Computational Mathematics
- Year dc:date.available
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Smith, Marisa
- Contributors dc:contributor
-
- Jeffrey Jackson
- John Kern
- Mark Mazur
Subjects
dc:subject × 4Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://dsc.duq.edu/etd/1216
- OAI identifier oai:identifier
- oai:dsc.duq.edu:etd-2232