domain specific analysis and modeling of optimal elimination of fitness functions with optimal sampling
This paper extends previous work that presented an algorithm called Optimal Elimination of Fitness Functions (OEFF). OEFF is by itself conditionally optimal over all problem classes, albeit impractical. Here, we complement this algorithm with an optimal sample selection strategy that removes the condition. Consequently, the performance of this combined algorithm over a domain is the black-box complexity of that domain, providing a new technique for deriving black-box complexity. Additionally, we suggest techniques to perform runtime analysis of our extended OEFF algorithm. We discuss how those techniques can be used to build an algorithm that is targeted, practical, yet equivalent to OEFF with optimal sampling over the target domain. This is demonstrated on the Generalized Leading Ones problem domain, where we derive black-box complexity and develop an optimal algorithm.
leading ones elimination of functions black-box optimization