You are here

UCF Digital Collections ยป ETD Collection

A Fitness Function Elimination Theory for Blackbox Optimization and Problem Class Learning

Download pdf | Full Screen View

Date Issued:
2012
Abstract/Description:
The modern view of optimization is that optimization algorithms are not designed in a vacuum, but can make use of information regarding the broad class of objective functions from which a problem instance is drawn. Using this knowledge, we want to design optimization algorithms that execute quickly (efficiency), solve the objective function with minimal samples (performance), and are applicable over a wide range of problems (abstraction). However, we present a new theory for blackbox optimization from which, we conclude that of these three desired characteristics, only two can be maximized by any algorithm.We put forward an alternate view of optimization where we use knowledge about the problem class and samples from the problem instance to identify which problem instances from the class are being solved. From this Elimination of Fitness Functions approach, an idealized optimization algorithm that minimizes sample counts over any problem class, given complete knowledge about the class, is designed. This theory allows us to learn more about the difficulty of various problems, and we are able to use it to develop problem complexity bounds.We present general methods to model this algorithm over a particular problem class and gain efficiency at the cost of specifically targeting that class. This is demonstrated over the Generalized Leading-Ones problem and a generalization called LO**, and efficient algorithms with optimal performance are derived and analyzed. We also tighten existing bounds for LO***. Additionally, we present a probabilistic framework based on our Elimination of Fitness Functions approach that clarifies how one can ideally learn about the problem class we face from the objective functions. This problem learning increases the performance of an optimization algorithm at the cost of abstraction.In the context of this theory, we re-examine the blackbox framework as an algorithm design framework and suggest several improvements to existing methods, including incorporating problem learning, not being restricted to blackbox framework and building parametrized algorithms. We feel that this theory and our recommendations will help a practitioner make substantially better use of all that is available in typical practical optimization algorithm design scenarios.
Title: A Fitness Function Elimination Theory for Blackbox Optimization and Problem Class Learning.
45 views
20 downloads
Name(s): Anil, Gautham, Author
Wu, Annie, Committee Chair
Wiegand, Rudolf, Committee CoChair
Stanley, Kenneth, Committee Member
Clarke, Thomas, Committee Member
Jansen, Thomas, Committee Member
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2012
Publisher: University of Central Florida
Language(s): English
Abstract/Description: The modern view of optimization is that optimization algorithms are not designed in a vacuum, but can make use of information regarding the broad class of objective functions from which a problem instance is drawn. Using this knowledge, we want to design optimization algorithms that execute quickly (efficiency), solve the objective function with minimal samples (performance), and are applicable over a wide range of problems (abstraction). However, we present a new theory for blackbox optimization from which, we conclude that of these three desired characteristics, only two can be maximized by any algorithm.We put forward an alternate view of optimization where we use knowledge about the problem class and samples from the problem instance to identify which problem instances from the class are being solved. From this Elimination of Fitness Functions approach, an idealized optimization algorithm that minimizes sample counts over any problem class, given complete knowledge about the class, is designed. This theory allows us to learn more about the difficulty of various problems, and we are able to use it to develop problem complexity bounds.We present general methods to model this algorithm over a particular problem class and gain efficiency at the cost of specifically targeting that class. This is demonstrated over the Generalized Leading-Ones problem and a generalization called LO**, and efficient algorithms with optimal performance are derived and analyzed. We also tighten existing bounds for LO***. Additionally, we present a probabilistic framework based on our Elimination of Fitness Functions approach that clarifies how one can ideally learn about the problem class we face from the objective functions. This problem learning increases the performance of an optimization algorithm at the cost of abstraction.In the context of this theory, we re-examine the blackbox framework as an algorithm design framework and suggest several improvements to existing methods, including incorporating problem learning, not being restricted to blackbox framework and building parametrized algorithms. We feel that this theory and our recommendations will help a practitioner make substantially better use of all that is available in typical practical optimization algorithm design scenarios.
Identifier: CFE0004511 (IID), ucf:49268 (fedora)
Note(s): 2012-12-01
Ph.D.
Engineering and Computer Science, Computer Science
Doctoral
This record was generated from author submitted information.
Subject(s): Optimization -- Theory -- Discrete Optimization -- Blackbox Complexity -- Optimal Elimination of Fitness Functions -- Generalized Onemax -- Generalized Leading Ones -- Problem Learning
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFE0004511
Restrictions on Access: public 2012-12-15
Host Institution: UCF

In Collections