Search

In this paper we relate information theory and Kolmogorov Complexity (KC) to optimization in the black box scenario. We define the set of all possible decisions an algorithm might make during a run, we associate a function with a probability distribution over this set and define accordingly its entropy. We show that the expected KC of the set (rather than the function) is a better measure of problem difficulty. We analyze the effect of the entropy on the expected KC. Finally, we show, for a restricted scenario, that any permutation closure of a single function, the finest level of granularity for which a No Free Lunch Theorem can hold [7], can be associated with a particular value of entropy. This implies bounds on the expected performance of an algorithm on members of that closure.

Nowadays, in the heuristic and metaheuristics community, there is a schism between researchers who say: "we proved experimentally that a given heuristic provides good results on a given problem and we can guess that it is enough general to be applied for other problems", and those who claim: "the No Free Lunch theorem (NFL) proves that there exists no absolute efficient heuristic". The formers suspect the existence of a structure in the solved problem and that structure can occur in other problems. The latters fear that heuristics are especially adapted for the testbed problem this paper addresses structural aspect of combinatorial optimization problems. In a first time, we recall some related works which provide a frame to our work. Particularly, we recall the existence of deceptive problems which are proved to be hard to optimize, the definitions of the five scenarios of knowledge in optimization problem, and some works which already discuss the reach of NFL theorem. In the next part, we give a short overview of how NFL works and discuss its significance with regards to complexity. This leads to the observation that the notion of structure of optimization problems is missing in NFL use. Then, we prove that k-coloring problems respect such a notion of structure, for any k. In the last part we discuss the relevance of our work on four points: the polynomial reduction of NP-complete problems and structure preservation, the connection between our work and the study which squeeze NFL using neighborhood search operators, the position of our study on the five scenarios of knowledge, and finally the difference between metaheuristics and heuristics.

We return to the no free lunch theorem, which is one of the most important theorems from the evolutionary computation foundations. We show that the no free lunch theorem can be interpreted as a trivial property of recursively enumerable languages. We demonstrate that if we consider not all problems and cost functions, i.e., a nontrivial property, the problem of finding the best evolutionary algorithm becomes Turing machine undecidable. We also demonstrate, that in spite of this negative result, the task of search for the best evolutionary computation operator is not so futile. In fact, evolutionary computation itself, being nonalgorithmic, may allow to find the best evolutionary operator in infinity, and to increase indefinitely its quality in the finite time.

Genetic algorithms (GAs) and genetic programming (GP) are often considered as separate but related fields. Typically, GAs use a fixed length linear representation, whereas GP uses a variable size tree representation. This paper argues that the differences are unimportant. Firstly, variable length actually means variable length up to some fixed limit, so can really be considered as fixed length. Secondly, the representations and genetic operators of GA and GP appear different, however ultimately it is a population of bit strings in the computers memory which is being manipulated whether it is GA or GP which is being run on the computer. The important difference lies in the interpretation of the representation; if there is a one to one mapping between the description of an object and the object itself (as is the case with the representation of numbers), or a many to one mapping (as is the case with the representation of programs). This has ramifications for the validity of the No Free Lunch theorem, which is valid in the first case but not in the second. It is argued that due to the highly related nature of GAs and GP, that many of the empirical results discovered in one field will apply to the other field, for example maintaining high diversity in a population to improve performance.

The no free lunch theorem of optimization (NFLT) is an impossibility theorem telling us that a general-purpose universal optimization strategy is impossible, and the only way one strategy can outperform another is if it is specialized to the structure of the specific problem under consideration. Since virtually all decision and control problems can be cast as optimization problems, an appreciation of the NFLT and its consequences is essential for control engineers. We present a framework for conceptualizing optimization problems that leads useful insights and a simple explanation of the NFLT.

This paper has three aims. Firstly, to clarify the poorly understood No Free Lunch Theorem (NFL) which states all search algorithms perform equally. Secondly, search algorithms are often applied to program induction and it is suggested that NFL does not hold due to the universal nature of the mapping between program space and functionality space. Finally, NFL and combinatorial problems are examined. When evaluating a candidate solution, it can be discarded without being fully examined. A stronger version of NFL is established for this class of problems where the goal is to minimize a quantity.

The inherent complexity of the Genetic Algorithms (GAs) has led to various theoretical an experimental approaches whose ultimate goal is to better understand the dynamics of such algorithms. Through such understanding, it is hoped, we will be able to improve their efficiency. Experiments, typically, explore the GA's behavior by testing them versus a set of functions with characteristics deemed adequate. In this paper we present a methodology which aims at achieving a solid relative evaluation of alternative GAs by resorting to statistical arguments. With it we may categorize any iterative optimization algorithm by statistically finding the basic parameters of the probability distribution of the GA's optimum values without resorting to a priori functions. We analyze the behavior of 6 algorithms (5 variations of a GA and a hill climber) which we characterize and compare. We make some remarks regarding the relation between statistical studies such as ours and the well known "No Free Lunch Theorem".

Evolutionary algorithms are often applied to tasks where the challenge is to fmd a superior solution. The engineering challengeconcerns how to best design such algorithms in terms of their representation, variation operators, and selection. The distribu-tion of fitness scores that is obtained when applying variation operators to parents can provide useful information for settingthe parameters that are associated with those operators. Experiments presented here indicate that fitness distributions can alsoreveal information about the landscape that surrounds particular parents and suggest that typical methods of self-adaptationmay not be veiy well suited for exploring the state space ofpossible solutions in the presence ofmultiple minima.Keywords: evolutionary computation, fitness distributions, neural networks, no free lunch theorem 1. INTRODUCTION Evolutionary algorithms are often used for optimization in an attempt to find the best solution(s) to a problem that is defmed interms of an evaluation function. In this regard, these algorithms apply a version of stochastic search over a state space ofpotential candidate solutions that is defmed by a representation and a collection ofvariation operators. The search can be cap-tured in the difference equation

Recent developments in the theory of evolutionary computation offer evidence and proof that overturns several conventionally held beliefs. In particular, the no free lunch theorem and other related theorems show that there can be no best evolutionary algorithm, and that no particular variation operator or selection mechanism provides a general advantage over another choice. Furthermore, the fundamental nature of the notion of schema processing is called into question by recent theory that shows that the schema theorem does not hold when schema fitness is stochastic. Moreover, the analysis that underlies schema theory, namely the k- armed bandit analysis, does not generate a sampling plan that yields an optimal allocation of trials, as has been suggested in the literature for almost 25 years. The importance of these new findings is discussed in the context of future progress in the field of evolutionary computation.© (1999) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

Choosing a good representation is a vital component of solving any search problem. However, choosing a good representation for a problem is as difficult as choosing a good search algorithm for a problem. Wolpert and Мacready’s No Free Lunch theorem proves that no search algorithm is better than any other over all possible discrete functions. We elaborate on the No Free Lunch theorem by proving that there tend to be a small set of points that occur as local optima under almost all representations. Along with the analytical results, we provide some empirical evaluation of two representations commonly used in genetic algorithms: Binary Reflected Gray coding and standard Binary encoding.

In many applications, some form of input information, such as test inputs or extra inputs, is available. We incorporate input information into learning by an augmented error function, which is an estimator of the out-of-sample error. The augmented error consists of the training error plus an additional term scaled by the augmentation parameter. For general linear models, we analytically show that the augmented solution has smaller out-of-sample error than the least squares solution. For nonlinear models, we devise an algorithm to minimize the augmented error by gradient descent, determining the augmentation parameter using cross validation. Augmented objective functions also arise when hints are incorporated into learning. We first show that using the invariance hints to estimate the test error, and early stopping on this estimator, results in better solutions than the minimization of the training error. We also extend our algorithm for incorporating input information to the case of learning from hints. Input information or hints are additional information about the target function. When the only available information is the training set, all the models with the same training error are equally likely to be the target. In that case, we show that early stopping of training at any training error level above the minimum can not decrease the out-of-sample error. Our results are nonasymptotic for general linear models and the bin model, and asymptotic for nonlinear models. When additional information is available, early stopping can help.

This paper provides insight into combining stochastic and deterministic search methods using evolutionary algorithms (EAs) such as evolutionary programming, evolutionary strategies, and genetic algorithms integrated with depth-first search with backtracking, branch and bound, and best-first search algorithms such as A*. An important view of such an integration focuses on both theoretical analysis and experimental evaluation. Included in the discussion is the constraining impact of the “No Free Lunch Theorem” on combined search performance. Also, a variety of combinations of EAs and deterministic combined search methods are proposed along with expert system components. Discussion of anticipated results of such architectures speculates about existence of high performance integrated search environments. A particular successful specific NPC problem environment is presented that employs search metrics for short-term performance evaluation and combined search algorithm selection.

This note discusses the recent paper "Some technical remarks on the proof of the no free lunch theorem" by Koppen (2000). In that paper, some technical issues related to the formal proof of the no free lunch (NFL) theorem for search were given by Wolpert and Macready (1995, 1997). The present authors explore the issues raised in that paper including the presentation of a simpler version of the NFL proof in accord with a suggestion made explicitly by Koppen (2000) and implicitly by Wolpert and Macready (1997). They also includes the correction of an incorrect claim made by Koppen (2000) of a limitation of the NFL theorem. Finally, some thoughts on future research directions for research into algorithm performance are given.