Search

Differential Evolution (DE) is one of the most effective approaches in Evolutionary Computation to tackling complex black-box optimization, however, the overall performance of a DE variant is heavily dependent on its mutation strategy and the associated parameter control schemes. According to the “No free Lunch theorem”, every mutation strategy has its own fatal defect, therefore, DE variant with a single mutation strategy can not tackle all optimization problems. Furthermore, DE variant with ensemble of mutation strategies usually needs more parameter control schemes, which inevitably decreases the practicality of it. Here in this paper, a novel Cooperative Strategy based DE (CS-DE) with population diversity enhancement is proposed, and the CS-DE algorithm has the following contributions: First, a cooperative strategy pool containing two similar mutation strategies is advanced in the algorithm, and the two mutation strategies share the same parameter control. Second, a novel grouping strategy is proposed, then the two mutation strategies can be chosen in an adaptive manner by different individuals in generating trial vectors during the evolution. Third, novel adaptation schemes for the three control parameters F , CR and PS as well as a stagnation based re-initialization mechanism are also proposed in our CS-DE algorithm. 58 benchmarks from the CEC2013 and CEC2014 test suites are employed in algorithm validation, and experiment results show the competitiveness of the CS-DE algorithm with several state-of-the-art DE variants.

As revealed by the no free lunch theorem, no single algorithm can outperform any others on all classes of optimization problems. To tackle this issue, methods for recommending an existing algorithm for solving given problems have been proposed. However, existing recommendation methods for continuous optimization suffer from low practicability and transferability, mainly due to the difficulty in extracting features that can effectively describe the problem structure and lack of data for training a recommendation model. This work proposes a generic recommender system to address the above two challenges. First, a novel method is proposed to represent an analytic objective function of a continuous optimization problem as a tree, which is directly used as the features of the problem. For black-box optimization problems whose objective function is unknown, a symbolic regressor is adopted to estimate the tree structure. Second, a large number of benchmark problems are randomly created based on the proposed tree representation, providing an abundant amount of training data with various levels of difficulty. By employing a deep recurrent neural network, a recommendation model is trained to recommend a most suitable metaheuristic algorithm for white- or black-box optimization, making a significant step forward towards fully automated algorithm recommendation for continuous optimization. Experimental results on 100 000 benchmark problems show that the proposed recommendation model achieves considerably better performance than existing ones, and exhibits high transferability to real-world problems.

Owing to no free lunch theorem, meta-heuristic search algorithms, behaviour and performance are different for solving specific class of optimization problems than another. Further, search algorithms are conceptualized of exploration and exploitation aspects. Ameliorated grey wolf optimization algorithm is proposed to solve economic power load dispatch problem that synergizes between exploration and exploitation aspects. Ameliorated grey wolf optimization procedure coordinates the behaviour of grey wolves, random exploratory search, local random search and opposition learning heuristics. Grey wolf optimization algorithm is considered to perform global search and random exploratory search applied to perform a search in the neighbourhood of already visited search locations. To maintain good solutions and diversity among solutions, opposition based learning has been implemented. The practical aspects i.e. value-point loading effect, avoidance of prohibited operating zones and ramp rate limits, generation limits of generators and satisfaction of power demand constraint are undertaken to solve economic power load dispatch problem. Heuristic search is exploited to handle equality constraints. The proposed algorithm is validated on standard benchmark functions and medium to large electric power systems. Results reveal that proposed technique is a potential method to solve economic load dispatch problems as it competes with recent algorithms undertaken for comparison.

The chapter considers the recent but already classic theoretical result called No Free Lunch Theorem in the context of optimization practice. The No Free Lunch Theorem is probably the fundamental theoretical result of the Machine Learning field but its practical meaning and implication for practitioners facing “real life” industrial and design optimization problems are rarely addressed in the technical literature. This discussion is intended for a broad audience of mathematicians, engineers, and computer scientists and presents a probabilistic understanding of the theorem that can shed light to its meaning and impact in the industrial optimization practice.

Meta-heuristic algorithms have been developed to solve various mathematical and engineering optimization problems. However, meta-heuristic algorithms show different performances depending on the characteristics of each problem. Therefore, there have been many kinds of research to decrease the performance gap for the different optimization problems by developing new algorithms, improving the search operators, and considering self-adaptive parameters setting on their algorithms. However, the previous studies only focused on improving the performance of each problem category (e.g., mathematical problem, engineering problem) without the quantitative evaluation for the operator performance. Therefore, this study proposes a framework for the quantitative evaluation to solve the no free lunch problem using the operators of the representative meta-heuristic algorithms (such as genetic algorithm and harmony search algorithm). Moreover, based on the quantitative analysis results for each operator, there are several types of hybrid optimization algorithms, which combined the operator of harmony search algorithm (HSA), genetic algorithm (GA), and particle swarm optimization (PSO). The optimization process to find the optimal solution is divided into five sections based on the number of function evaluations to see the performance of the search operator according to the section. Representative mathematical problems were applied to quantify the performance and operators. None of the five evaluated applied to mathematical benchmark problems were the best algorithms. Hybrid HSAs showed advanced performance for problems where traditional HSA did not show good performance. However, it still has not escaped the No Free Lunch theorem.

Performance of real-parameter global optimization algorithms is typically evaluated using sets of test problems. We propose a new methodology of extending these benchmarks to obtain a more balanced experimental design. This can be done by selectively removing some of the transformations originally used in the definitions of the test problems such as rotation, scaling, or translation. In this way, we obtain several variants of each problem parametrized by interpretable, high-level characteristics. These binary parameters are used as predictors in a multiple regression model explaining the algorithmic performance. Linear models allow for the attribution of strength and direction of performance changes to particular characteristics of the optimization problems and thus provide insight into the underlying mechanics of the investigated algorithms. The proposed ideas are illustrated with an application example showing the feasibility of the new benchmark. Parametrized benchmarking is a step towards obtaining multi-faceted insight into algorithmic performance and the optimization problems. The overall goal is to systematize a method of matching problems to algorithms and in this way constructively address the limitations imposed by the no free lunch theorem.

The “No Free Lunch” theorem states that, averaged over all optimization problems, without re-sampling, all optimization algorithms perform equally well. Optimization, search, and supervised learning are the areas that have benefited more from this important theoretical concept. Formulation of the initial No Free Lunch theorem, very soon, gave rise to a number of research works which resulted in a suite of theorems that define an entire research field with significant results in other scientific areas where successfully exploring a search space is an essential and critical task. The objective of this paper is to go through the main research efforts that contributed to this research field, reveal the main issues, and disclose those points that are helpful in understanding the hypotheses, the restrictions, or even the inability of applying No Free Lunch theorems.

An existing estimation distribution algorithm (EDA) with univariate marginal Gaussian model was improved by designing and incorporating an extreme elitism selection method. This selection method highlighted the effect of a few top best solutions in the evolution and advanced EDA to form a primary evolution direction and obtain a fast convergence rate. Simultaneously, this selection can also keep the population diversity to make EDA avoid premature convergence. Then the modified EDA was tested by means of benchmark low-dimensional and high-dimensional optimization problems to illustrate the gains in using this extreme elitism selection. Besides, no-free-lunch theorem was implemented in the analysis of the effect of this new selection on EDAs.

Well placement optimization is one of the major challenging factors in the field development process of oil and gas industry. The objective function of well placement optimization is considered as high dimensional, discontinuous and multi-model. Over the last decade, both gradient-based and gradient-free optimization methods have been implemented to tackle this problem. Nature-inspired gradient-free optimization algorithms like particle swarm optimization, genetic algorithm, covariance matrix adaptation evolution strategy and differential evolution have been utilized in this area. These optimization techniques are implemented as stand-alone or as hybrid form to maximize the economic factors. In this paper, several nature-inspired metaheuristic optimization techniques and their application to maximize the economic factors are reviewed. Newly developed optimization algorithms are very efficient and favorable when compared to other established optimization algorithms and in all cases, it has been noticed that hybridization of two or more algorithms works better than stand-alone algorithms. Furthermore, none of the single optimization techniques can be established as being universally superior which aligns with no free lunch theorem. For future endeavor, combining optimization methods and exploiting multiple optimization processes for faster convergence and developing efficient proxy model is expected.

International audience; Offline parameter tuning (OPT) of multi-objective evolutionary algorithms (MOEAs) has the goal of finding an appropriate set of parameters for solving a large number of problems. According to the no free lunch theorem (NFL), no algorithm can have the best performance in all classes of optimization problems. However, it is possible to find an appropriate set of parameters of an algorithm for solving a particular class of problems. For that sake, we need to study how to estimate the aggregation quality function for an algorithmic configuration assessed on a set of optimization problems. In this paper, we study robustness measures for dealing with the parameter settings of stochastic algorithms. We focus on decomposition-based MOEAs and we propose to tune scalarizing functions for solving some classes of problems based on the Pareto front shapes using up to 7 objective functions. Based on our experimental results, we were able to derive interesting guidelines to evaluate the quality of algorithmic configurations using a combination of descriptive statistics.

Solving complex optimization problems can be painstakingly difficult endeavor considering multiple and conflicting design goals. A growing trend in utilizing meta-heuristic algorithms to solve these problems has been observed as they have shown considerable success in dealing with tradeoffs between conflicting design goals. Many meta-heuristic algorithms have been developed to date (e.g. Simulated Annealing (SA), Particle Swarm Optimization (PSO), Teaching Learning based Optimization (TLBO), Grey Wolf Optimizer(GWO) to name a few). Much of these algorithms have adopted elegant metaphors (e.g. heating and cooling of metals in the case of SA and swarming of flocking birds in the case of PSO) from nature in order to derive the mathematical models for generating the solution as well as provides control over their exploration (i.e. sufficient roaming of the search space) and exploitation (i.e. using known knowledge of the surroundings). In line with the no free lunch theorem (), this paper argues that rather than focusing on designing new algorithm, new research should focus on adaptive hybridization of meta-heuristics algorithms in order to compensate the limitation of one with the strengths of another. In this paper, we review the meta-heuristic and hyper-heuristic algorithms in order to highlight the current-state-of-the-arts and suggest areas for future research.

It is well known that the performance of an evolutionary algorithm (EA) is highly dependent on the setting of EA parameters. There have been many studies on EA parameter setting, but no single method outperformed all other methods on all classes of problems as declared by the no free lunch theorem. In order to overcome the heavy computational burden usually required for parameter tuning, we propose an EA parameter tuning procedure applicable to any set of test problems. First, we employ an optimal Latin hypercube design (OLHD) in which parameters of an EA algorithm are set as factors. Next, using parameter settings sampled by OLHD, we run EAs to solve the test problems. Then, we statistically recommend parameter settings suitable for the test problems. Statistical evaluation of this application results suggests the best recombination method, and the recommended parameter ranges of population size, selection rate, and mutation rate are reduced by 93%, 80%, and 84%, respectively, compared to those usually used in parameter ranges. Finally, the recommended parameter setting is applied to the optimization problem of a high-speed spindle motor for a hard disk drive, and shows the effectiveness of the proposed procedure for a practical design optimization application.

Created in the 90s of the past century methods of constructing algorithms (metaheuristic), inspired by the no free lunch theorem of Wolpert and Macready, using specific properties of problems, do not meet present expectations of practitioners. Commonly used artificial intelligence algorithms in recent years have also proved to be ineffective in solving a large group of extremely difficult instances of various problems. In the work we present some empirical methods of exploration of solution space in optimization problems whose solutions are represented by permutations. While sampling the set of permissible solutions we designate the histogram of the frequency of occurrence of local minima and on this basis we verify the statistical hypothesis concerning the (normal) distribution of occurrence of these minima. Due to this process we can flexibly change the “radius” of the searched area. Computational experiments performed on examples of the job shop problem are promising and inspire to conduct further research in this direction.

The weighted circle packing problem is a kind of important combination optimization problem and has the NP-hard property. Inspired by the No Free Lunch Theorem, a knowledge-based heuristic particle swarm optimization approach with the adjustment strategy (KHPSOA) is developed for this problem. The knowledge (e.g., the relation between its weight matrix and better solution) is obtained from this problem itself and existing layout scheme diagrams and applied to form more effective ordering and positioning rules of the proposed heuristic method. A better layout scheme of larger circles is obtained through the heuristic method. The optimal solution of this problem is obtained by inserting a few residual smaller circles into the gaps of the better layout scheme and further optimizing it through the proposed particle swarm optimization with the adjustment strategy. The numerical experiments show that KHPSOA is superior to the existing algorithms in the performances.

Considering the “no free lunch theorem” (Wolpert and Macready, IEEE Trans Evolut Comput 67(1), 1997, [297]), it is still important to try to test how the examined metaheuristic works when applied to different well-known problems. That is why several well-known benchmark functions are considered in the following experimental study (Digalakis and Margaritis, Int J Comput Math 79(4):403–416, 2002, [82]). In order to obtain plausible results, the systems compared should be parametrized in the most similar way. So it is the case presented in this section, as EMAS, and its memetic variants (Baldwinian and Lamarckian) are compared with PEA (along with respective memetic modifications). Later, a comparison between EMAS and its immunological variant (iEMAS) is made. Finally two discrete problems are tackled: Low Autocorrelation Binary Sequence (LABS) and Optimal Golomb Ruler (OGR).

In literature, empirically and theoretically, it has been well-demonstrated that the performance of differential evolution (DE) is sensitive to the choice of the mutation and crossover strategies and their associated control parameters. According to the No Free Lunch theorem, a single set of well-tuned combination of strategies and their associated parameter combination is not suitable for optimization problems having different characteristics. In addition, different mutation and crossover strategies with different parameter settings can be appropriate during different stages of the evolution. Based on this observation, DE with an ensemble of mutation and crossover strategies and their associated control parameters referred to as EPSDE was proposed. However, it has been observed that the fixed discrete parameter values as in EPSDE may not yield optimal performance. In this paper, we propose self-adaptive DE algorithm (Sa-EPSDE) with a set of mutation strategies while their associated parameter values F and CR are sampled using mean and standard deviation values. In addition, the probability of selecting a combination to produce an offspring at a particular generation during the evolution process depends on the success of the combination. The performance of the proposed Sa-EPSDE algorithm is evaluated on a set of 14 bound-constrained problems designed for Conference on Evolutionary Computation (CEC) 2005. In order to validate the performance of proposed Sa-EPSDE algorithm on real-world applications, the algorithm is hybridized with a simple priority listing method and applied to solve unit commitment problem by considering 10-, 20-, 40-, 60-, 80- and 100-bus systems for one day scheduling period. The results showed that the proposed method obtained superior performance against other compared algorithms.

We encounter optimization problems in our daily lives and in various research domains. Some of them are so hard that we can, at best, approximate the best solutions with (meta-) heuristic methods. However, the huge number of optimization problems and the small number of generally acknowledged methods mean that more metaheuristics are needed to fill the gap. We propose a new metaheuristic, called chemical reaction optimization (CRO), to solve optimization problems. It mimics the interactions of molecules in a chemical reaction to reach a low energy stable state. We tested the performance of CRO with three nondeterministic polynomial-time hard combinatorial optimization problems. Two of them were traditional benchmark problems and the other was a real-world problem. Simulation results showed that CRO is very competitive with the few existing successful metaheuristics, having outperformed them in some cases, and CRO achieved the best performance in the real-world problem. Moreover, with the No-Free-Lunch theorem, CRO must have equal performance as the others on average, but it can outperform all other metaheuristics when matched to the right problem type. Therefore, it provides a new approach for solving optimization problems. CRO may potentially solve those problems which may not be solvable with the few generally acknowledged approaches.

The foundations for evolutionary algorithms (EAs) were established in the end of the 60’s [1, 2] (EAs) and strengthened in the beginning of the 70’s [3, 4]. EAs appeared as an alternative to the exact or approximate optimization methods whose application to many real problems were not acceptable in terms of performance. When applied to real problems, EAs provide a valuable relation between quality of the solution and efficiency to obtain it; for this reason these techniques attracted immediately the attention of many researchers and became what they nowadays represent: the cutting-edge approach to real-world optimization. Certainly, this has also been the case for other related techniques, such as simulated annealing [5] (SA), tabu search [6] (TS), etc. The term metaheuristics has been coined to denote them. The term hybrid evolutionary algorithm (HEAs) (resp. hybrid metaheuristics) refers to the combination of an evolutionary technique (resp. metaheuristics) with another (perhaps exact or approximate) technique for optimization. The aim is to combine the best of both worlds with the objective of producing better results than each of the involved components working alone. HEAs have been proved to be very successful in the optimization of many practical problems (e.g., [7, 8]) and, as a consequence, currently there exist an increasing interest in the optimization community for this kind of techniques. One crucial point in the the development of HEAs (and hybrid metaheuristics in general) is the need of exploiting problem knowledge as was clearly exposed in the formulation of the No Free Lunch Theorem (NFL) by Wolpert and Macready [9] (a search algorithm performs in strict accordance with the amount and quality of the problem knowledge they incorporate). Quite interestingly, this line of thinking had

A sizable amount of research has been done to improve the mechanisms for knowledge extraction such as machine learning classification or regression. Quite unintuitively, the no free lunch (NFL) theorem states that all optimization problem strategies perform equally well when averaged over all possible problems. This fact seems to clash with the effort put forth toward better algorithms. This letter explores empirically the effect of the NFL theorem on some popular machine learning classification techniques over real-world data sets.

This chapter presents popular meta-heuristics inspired from nature focusing on evolutionary computation (EC). The first section, as an elevator pitch, briefly walks through problem solving, touching upon notions such as optimization problems, meta-heuristics, constraint handling, hybridization, and the No Free Lunch Theorem for optimization, and also giving very short introductions into several most popular meta-heuristics. The next two sections are dedicated to evolutionary algorithms and swarm intelligence (SI), two of the main areas of EC. Three particular optimization methods illustrating these two areas are presented in more detail: genetic algorithms (GAs), differential evolution (DE), and particle swarm optimization (PSO). For a better understanding of these algorithms, references to R packages implementing the algorithms and code samples to solve numerical and combinatorial problems are given. The fourth section is dedicated to the use of EC techniques in data analysis. Optimization of the hyper-parameters of conventional machine learning techniques is illustrated by a case study. The last section reviews applications of meta-heuristics in geosciences.

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. In this paper, a framework is presented for conceptualizing optimization problems that leads to useful insights and a simple explanation of the NFLT.

A framework is developed to explore the connection between effective optimization algorithms and the problems they are solving. A number of "no free lunch" (NFL) theorems are presented which establish that for any algorithm, any elevated performance over one class of problems is offset by performance over another class. These theorems result in a geometric interpretation of what it means for an algorithm to be well suited to an optimization problem. Applications of the NFL theorems to information-theoretic aspects of optimization and benchmark measures of performance are also presented. Other issues addressed include time-varying optimization problems and a priori "head-to-head" minimax distinctions between optimization algorithms, distinctions that result despite the NFL theorems' enforcing of a type of uniformity over all algorithms.

In this study, we have compared six state-of-the-art Multiobjective Evolutionary Algorithms (MOEAs) designed specifically for many-objective optimization problems under a number of carefully crafted benchmark problems. Using the performance metrics ensemble, we aim at providing a comprehensive measure and more importantly revealing insight pertaining to specific problem characteristics that the underlying MOEA could perform the best. The experimental results confirm the finding from the No Free Lunch theorem: any algorithm's elevated performance over one class of problems is exactly paid for in loss over another class. In addition, the experimental results show that the performance of MOEA to solve many-objective optimization problems depends on two distinct aspects: the ability of MOEA to tackle the specific characteristics of the problem and the ability of MOEA to handle high-dimensional objective space.

Biogeography-based optimization (BBO) is a new evolutionary algorithm inspired by biogeography. BBO has demonstrated good performance on various benchmark functions and real-world optimization problems. However, the performance of BBO is sensitive to the migration model which provides the most important control parameters, immigration rate and emigration rate. According to no free lunch theorem, it is impossible for BBO with a single migration model to obtain always good performance. In this paper, BBO with an ensemble of migration models (BBO-EMM) is introduced and is realized using in three parallel populations. The performance is tested on a set of 25 benchmark functions of CEC 2005 and compared with variant versions of BBO with a single migration model with respect to optimization ability and running time. Results show that the proposed BBO-EMM is better than other BBO algorithms for the problems that we studied in this paper.

That there is no best initial parameter setting for a metaheuristic on all optimization problems is a proven fact (no free lunch theorem). This paper studies the applicability of so called robust parameter settings for combinatorial optimization problems. Design of Experiments supported parameter screening had been carried out, analyzing a discrete Particle Swarm Optimization algorithm on three demographically very dissimilar instances of the Traveling Salesmen Problem. First experimental results indicate that parameter settings produce varying performance quality for the three instances. The robust parameter setting is outperformed in two out of three cases. The results are even significantly worse when considering quality/time trade-off. A methodology for problem generalization is referred to as a possible solution.

Several constraint handling techniques have been proposed to be used with the evolutionary algorithms (EAs). According to the no free lunch theorem, it is impossible for a single constraint handling technique to outperform all other techniques on every problem. In other words, depending on several factors such as the ratio between feasible search space and the whole search space, multi-modality of the problem, the chosen EA and global exploration/local exploitation stages of the search process, different constraint handling techniques can be effective on different problems and during different stages of the search process. Motivated by these observations, we proposed an ensemble of constraint handling techniques (ECHT) to solve constrained real-parameter optimization problems. In ECHT, each constraint handling method has its own population and every function call is used effectively. Being a general concept, the ECHT can be realized with any existing EA. In this paper, we present ECHT with Differential Evolution (DE) as the basic search algorithm (ECHT-DE). The ECHT is formed using four different constraint handling techniques present in the literature. ECHT-DE is evaluated on the functions from CEC 2010 problem set.

The complexity of fitness landscapes, e.g., in terms of multimodalities and presence of plateaus, typical of many realworld optimization problems coupled with the limitations imposed by the No Free Lunch Theorem, are strong mitigating factors for domain-specific Memetic Computing approaches. More specifically, since the No Free Lunch Theorem proves that the performance of each algorithm over all the possible problems is the same, there is no longer a reason to discuss which algorithm is universally better or worse. Thus, instead of trying to propose universally applicable algorithms, researchers in recent years have started to propose algorithms which are tailored specific to the problems in hand. In this context, the Memetic Computing paradigm offers the possibility of flexibly designing domain-specific optimization algorithms by integrating and coordinating algorithmic components capable of dealing with difficulties specifically related to the decision space and fitness landscape of a given problem. This thematic issue deals with a set of problem difficulties which are of great interest in an industrial context, i.e., uncertainties in the fitness function, and gathers novel Memetic Computing approaches which attempt to solve this set of problems. It addresses those optimization problems characterized by a complex fitness landscape and uncertain environments. An optimization problem contains uncertainties

This chapter aims to address some of the fundamental issues that are often encountered in optimization problems, making them difficult to solve. These issues include premature convergence, ruggedness, causality, deceptiveness, neutrality, epistasis, robustness, overfitting, oversimplification, multi-objectivity, dynamic fitness, the No Free Lunch Theorem, etc. We explain why these issues make optimization problems hard to solve and present some possible countermeasures for dealing with them. By doing this, we hope to help both practitioners and fellow researchers to create more efficient optimization applications and novel algorithms.

The no free lunch (NFL) theorem tells us that without any structural assumptions on an optimization problem, no algorithm can perform better on average than blind search. Although for most such impossibility theorems, the proofs are lengthy, difficult, and often not at all intuitive, we can get a feel for the NFL theorem by considering the proverbial needle in a haystack problem. Clearly, in this instance, no algorithm has any better chance of finding the optimum than blind search. The title also refers to the human-machine interface (HMI). Traditionally, this term has had the narrow meaning of facilitating communication between humans and computing machines, such as via the graphical user interface or head-up displays. But as technology advances, this communication interface will also evolve. Certainly, in the future we can see voice, fuzzy, and natural language inputs and outputs. Here, however, we are using the term in an even broader sense: to demarcate the dividing line between what humans do and what machines do in problem solving or optimization. The twin purposes of the article are to explore the implications of NFL and to address the proper allocation of natural and computational intelligence in optimization problem solving.

According to the no free lunch (NFL) theorems all black-box algorithms perform equally well when compared over the entire set of optimization problems. An important problem related to NFL is finding a test problem for which a given algorithm is better than another given algorithm. In this paper we propose an evolutionary approach for solving this problem: we will evolve multi-objective test functions for which a given algorithm A is better than another given algorithm B. The evolved functions are represented as binary strings. Several numerical experiments involving PESA and NSGA II are performed. The results show the effectiveness of the proposed approach. Several multi-objective problems for which PESA performs better than NSGA II and several multi-objective test problems for which NSGA II performs better than PESA have been evolved.

This work offers details of our recent research dealing with the development of a hybrid multi-objective optimization. Wolpert and Macready determined in single objective optimization that no single algorithm outperforms another over all possible classes of objective functions. This is the well known “No Free Lunch Theorem” (NFL) as it applies to searches and optimization problems. Koppen has shown how NFL can be extended to multiobjective optimization problems. NFL does not reject the possibility that there are classes of problems where one algorithm outperforms another. The problem faced by design engineers is that they may not know the class of problem, from an NFL point of view, they need to optimize beforehand. The objective function(s) form(s) as the design develops, and a robust optimization tool must be able to handle whatever class of objective functions any design renders. If an optimization tool provides multiple search algorithms which are automatically switched to, as the search demands, it may be possible to robustly optimize a large variety of objective function combinations. In single objective optimization the measure of a search algorithm’s progress can be easily calculated from its ability to improve the value of the objective function. The objective function value is the single quality factor that can be used to accurately compare the final results of different optimization routines. A common method to handle MultiObjective Optimization Problems (MOOP) is to optimize using the concepts of Pareto fronts and non-dominated sets. Zitzler et al., discussed how for MOOPs it is difficult to impossible to use one quality factor to determine which Pareto approximation set is superior among multiple approximations generated by multiple algorithms (when the true non-dominated set is unknown). In this work the question of robustness in light of NFL, as applied to MOOP, is addressed with the development of a multi-objective hybrid evolutionary computer program. An approach utilizing multiple switching criteria is developed and implemented. The switching criteria are a set of quality factors that the switching algorithm uses to switch between search algorithms automatically. The software developed for this work was tested on multiple standard test function suites. The software was also tested against some of its single algorithm components to determine what performance differences a multi-objective hybrid search software may possess with respect to single search algorithm software.

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.

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.