Search

NeuroEvolution (NE) refers to a family of methods for optimizing Artificial Neural Networks (ANNs) using Evolutionary Computation (EC) algorithms. NeuroEvolution of Augmenting Topologies (NEAT) is considered one of the most influential algorithms in the field. Eighteen years after its invention, a plethora of methods have been proposed that extend NEAT in different aspects. In this article, we present a systematic literature review (SLR) to list and categorize the methods succeeding NEAT. Our review protocol identified 232 papers by merging the findings of two major electronic databases. Applying criteria that determine the paper's relevance and assess its quality, resulted in 61 methods that are presented in this article. Our review article proposes a new categorization scheme of NEAT's successors into three clusters. NEAT-based methods are categorized based on 1) whether they consider issues specific to the search space or the fitness landscape, 2) whether they combine principles from NE and another domain, or 3) the particular properties of the evolved ANNs. The clustering supports researchers 1) understanding the current state of the art that will enable them, 2) exploring new research directions or 3) benchmarking their proposed method to the state of the art, if they are interested in comparing, and 4) positioning themselves in the domain or 5) selecting a method that is most appropriate for their problem.

The notion and characterisation of fitness landscapes has helped us understand the performance of heuristic algorithms on complex optimisation problems. Many practical problems, however, are constrained, and when significant areas of the search space are infeasible, researchers have intuitively resorted to a variety of constraint-handling techniques intended to help the algorithm manoeuvre through infeasible areas and toward feasible regions of better fitness. It is clear that providing constraint-related feedback to the algorithm to influence its choice of solutions overlays the violation landscape with the fitness landscape in unpredictable ways whose effects on the algorithm cannot be directly measured. In this work, we apply metrics of violation landscapes to continuous and combinatorial problems to characterise them. We relate this information to the relative performance of six well-known constraint-handling techniques to demonstrate how some properties of constrained landscapes favour particular constraint-handling approaches. For the problems with sampled feasible solutions, a bi-objective approach was the best performing approach overall, but other techniques performed better on problems with the most disjoint feasible areas. For the problems with no measurable feasibility, a feasibility ranking approach was the best performing approach overall, but other techniques performed better when the correlation between fitness values and the level of constraint violation was high.

Complex combinatorial problems are most often optimised with heuristic solvers, which usually deliver acceptable results without any indication of the quality obtained. Recently, predictive diagnostic optimisation was proposed as a means of characterising the fitness landscape while optimising a combinatorial problem. The scalars produced by predictive diagnostic optimisation appear to describe the difficulty of the problem with relative reliability. In this study, we record more scalars that may be helpful in determining problem difficulty during the optimisation process and analyse these in combination with other well-known landscape descriptors by using exploratory factor analysis on four landscapes that arise from different search operators, applied to a varied set of quadratic assignment problem instances. Factors are designed to capture properties by combining the collinear variances of several variables. The extracted factors can be interpreted as the features of landscapes detected by the variables, but disappoint in their weak correlations with the result quality achieved by the optimiser, which we regard as the most reliable indicator of difficulty available. It appears that only the prediction error of predictive diagnostic optimisation has a strong correlation with the quality of the results produced, followed by a medium correlation of the fitness distance correlation of the local optima.

The fitness landscape of the travelling salesman problem is investigated for 11 different types of the problem. The types differ in how the distances between cities are generated. Many different properties of the landscape are studied. The properties chosen are all potentially relevant to choosing an appropriate search algorithm. The analysis includes a scaling study of the time to reach a local optimum, the number of local optima, the expected probability of reaching a local optimum as a function of its fitness, the expected fitness found by local search and the best fitness, the probability of reaching a global optimum, the distance between the local optima and the global optimum, the expected fitness as a function of the distance from an optimum, their basins of attraction and a principal component analysis of the local optima. The principal component analysis shows the correlation of the local optima in the component space. We show how the properties of the principal components of the local optima change from one problem type to another.

This article presents an exploratory landscape analysis of three NP-hard combinatorial optimisation problems: the number partitioning problem, the binary knapsack problem, and the quadratic binary knapsack problem. In the article, we examine empirically a number of fitness landscape properties of randomly generated instances of these problems. We believe that the studied properties give insight into the structure of the problem landscape and can be representative of the problem difficulty, in particular with respect to local search algorithms. Our work focuses on studying how these properties vary with different values of problem parameters. We also compare these properties across various landscapes that were induced by different penalty functions and different neighbourhood operators. Unlike existing studies of these problems, we study instances generated at random from various distributions. We found a general trend where some of the landscape features in all of the three problems were found to vary between the different distributions. We captured this variation by a single, easy to calculate parameter and we showed that it has a potentially useful application in guiding the choice of the neighbourhood operator of some local search heuristics.

Recent works raised the hypothesis that the assignment of a geometry to the decision variable space of a combinatorial problem could be useful both for providing meaningful descriptions of the fitness landscape and for supporting the systematic construction of evolutionary operators (the geometric operators) that make a consistent usage of the space geometric properties in the search for problem optima. This paper introduces some new geometric operators that constitute the realization of searches along the combinatorial space versions of the geometric entities descent directions and subspaces. The new geometric operators are stated in the specific context of the wireless sensor network dynamic coverage and connectivity problem (WSN-DCCP). A genetic algorithm (GA) is developed for the WSN-DCCP using the proposed operators, being compared with a formulation based on integer linear programming (ILP) which is solved with exact methods. That ILP formulation adopts a proxy objective function based on the minimization of energy consumption in the network, in order to approximate the objective of network lifetime maximization, and a greedy approach for dealing with the system's dynamics. To the authors’ knowledge, the proposed GA is the first algorithm to outperform the lifetime of networks as synthesized by the ILP formulation, also running in much smaller computational times for large instances.

We consider optimization problems where the set of solutions available for evaluation at any given time t during optimization is some subset of the feasible space. This model is appropriate to describe many closed-loop optimization settings (i.e., where physical processes or experiments are used to evaluate solutions) where, due to resource limitations, it may be impossible to evaluate particular solutions at particular times (despite the solutions being part of the feasible space). We call the constraints determining which solutions are non-evaluable ephemeral resource constraints (ERCs). In this paper, we investigate two specific types of ERC: one encodes periodic resource availabilities, the other models commitment constraints that make the evaluable part of the space a function of earlier evaluations conducted. In an experimental study, both types of constraint are seen to impact the performance of an evolutionary algorithm significantly. To deal with the effects of the ERCs, we propose and test five different constraint-handling policies (adapted from those used to handle standard constraints), using a number of different test functions including a fitness landscape from a real closed-loop problem. We show that knowing information about the type of resource constraint in advance may be sufficient to select an effective policy for dealing with it, even when advance knowledge of the fitness landscape is limited.

Some authors consider that evolutionary search may be positively influenced by the use of redundant representations, whereas others note that the addition of random redundancy to a representation could be useless in optimization. Given this lack of consensus, two new families of redundant binary representations are developed in this paper. The first family is based on linear transformations and is considered non-neutral. The second family of representations is designed to implement neutrality, and is based on the mathematical formulation of error control codes. A study aimed at assessing the influence of redundancy and neutrality on the performance of a simple evolutionary hillclimber is presented. The (1+1)-ES is modeled using Markov chains and is applied to NK fitness landscapes. The results indicate that the phenotypic neighborhood induced by a redundant representation dominates the behavior of the algorithm, affecting the search more strongly than neutrality, and the representations with better performance on NK fitness landscapes do not exhibit extreme values of any of the indicators of representation quality commonly adopted in the literature.

To deal with complex optimization problems plagued with computationally expensive fitness functions, the use of surrogates to replace the original functions within the evolutionary framework is becoming a common practice. However, the appropriate datacentric approximation methodology to use for the construction of surrogate model would depend largely on the nature of the problem of interest, which varies from fitness landscape and state of the evolutionary search, to the characteristics of search algorithm used. This has given rise to the plethora of surrogate-assisted evolutionary frameworks proposed in the literature with ad hoc approximation/surrogate modeling methodologies considered. Since prior knowledge on the suitability of the data centric approximation methodology to use in surrogate-assisted evolutionary optimization is typically unavailable beforehand, this paper presents a novel evolutionary framework with the evolvability learning of surrogates (EvoLS) operating on multiple diverse approximation methodologies in the search. Further, in contrast to the common use of fitness prediction error as a criterion for the selection of surrogates, the concept of evolvability to indicate the productivity or suitability of an approximation methodology that brings about fitness improvement in the evolutionary search is introduced as the basis for adaptation. The backbone of the proposed EvoLS is a statistical learning scheme to determine the evolvability of each approximation methodology while the search progresses online. For each individual solution, the most productive approximation methodology is inferred, that is, the method with highest evolvability measure. Fitness improving surrogates are subsequently constructed for use within a trust-region enabled local search strategy, leading to the self-configuration of a surrogate-assisted memetic algorithm for solving computationally expensive problems. A numerical study of EvoLS on commonly used benchmark problems and a real-world computationally expensive aerodynamic car rear design problem highlights the efficacy of the proposed EvoLS in attaining reliable, high quality, and efficient performance under a limited computational budget.

One of the major challenges in the field of evolutionary algorithms (EAs) is to characterise which kinds of problems are easy and which are not. Researchers have been attracted to predict the behaviour of EAs in different domains. We introduce fitness landscape networks (FLNs) that are formed using operators satisfying specific conditions and define a new predictive measure that we call motif difficulty (MD) for comparison-based EAs. Because it is impractical to exhaustively search the whole network, we propose a sampling technique for calculating an approximate MD measure. Extensive experiments on binary search spaces are conducted to show both the advantages and limitations of MD. Multidimensional knapsack problems (MKPs) are also used to validate the performance of approximate MD on FLNs with different topologies. The effect of two representations, namely binary and permutation, on the difficulty of MKPs is analysed.

In this paper we extend a previously proposed randomized landscape generator in combination with a comparative experimental methodology to study the behavior of continuous metaheuristic optimization algorithms. In particular, we generate two-dimensional landscapes with parameterized, linear ridge structure, and perform pairwise comparisons of algorithms to gain insight into what kind of problems are easy and difficult for one algorithm instance relative to another. We apply this methodology to investigate the specific issue of explicit dependency modeling in simple continuous estimation of distribution algorithms. Experimental results reveal specific examples of landscapes (with certain identifiable features) where dependency modeling is useful, harmful, or has little impact on mean algorithm performance. Heat maps are used to compare algorithm performance over a large number of landscape instances and algorithm trials. Finally, we perform a meta-search in the landscape parameter space to find landscapes which maximize the performance between algorithms. The results are related to some previous intuition about the behavior of these algorithms, but at the same time lead to new insights into the relationship between dependency modeling in EDAs and the structure of the problem landscape. The landscape generator and overall methodology are quite general and extendable and can be used to examine specific features of other algorithms.

30 pages, 23 figures. The dynamic optimization problem concerns finding an optimum in a changing environment. In the field of evolutionary algorithms, this implies dealing with a time-changing fitness landscape. In this paper we compare different techniques for integrating motion information into an evolutionary algorithm, in the case it has to follow a time-changing optimum, under the assumption that the changes follow a nonrandom law. Such a law can be estimated in order to improve the optimum tracking capabilities of the algorithm. In particular, we will focus on first order dynamical laws to track moving objects. A vision-based tracking robotic application is used as testbed for experimental comparison. The work of the first and second authors has been carried out under a "Ramón y Cajal" research fellowship from the Ministerio de Ciencia y Tecnología of Spain, and partially funded by projects DPI2005-04302 and DPI2006-03444. Publicado

Geometric crossover is a representation-independent generalization of the traditional crossover defined using the distance of the solution space. By choosing a distance firmly rooted in the syntax of the solution representation as a basis for geometric crossover, one can design new crossovers for any representation. Using a distance tailored to the problem at hand, the formal definition of geometric crossover allows us to design new problem-specific crossovers that embed problem-knowledge in the search. The standard encoding for multiway graph partitioning is highly redundant: each solution has a number of representations, one for each way of labeling the represented partition. Traditional crossover does not perform well on redundant encodings. We propose a new geometric crossover for graph partitioning based on a labeling-independent distance that filters out the redundancy of the encoding. A correlation analysis of the fitness landscape based on this distance shows that it is well suited to graph partitioning. A second difficulty with designing a crossover for multiway graph partitioning is that of feasibility: in general recombining feasible partitions does not lead to feasible offspring partitions. We design a new geometric crossover for permutations with repetitions that naturally suits partition problems and we test it on the graph partitioning problem. We then combine it with the labeling-independent crossover and obtain a much superior geometric crossover inheriting both advantages.

Geometric crossover is a formal class of crossovers that includes many well-known recombination operators across representations. In previous work, it was shown that all evolutionary algorithms with geometric crossover (but no mutation) do the same form of convex search regardless of the underlying representation, the specific selection mechanism, offspring distribution, search space, and problem at hand. Furthermore, it was suggested that the generalised convex search could perform well on generalised forms of concave and approximately concave fitness landscapes regardless of the underlying space and representation. In this article, we deepen this line of enquiry and study the runtime of generalised convex search on concave fitness landscapes. This is a first step toward linking a geometric theory of representations and runtime analysis in the attempt to (1) set the basis for a more general, unified approach for the runtime analysis of evolutionary algorithms across representations, and (2) identify the essential matching features of evolutionary search behaviour and landscape topography that cause polynomial performance. We present a general runtime result that can be systematically instantiated to specific search spaces and representations and present its specifications to three search spaces. As a corollary, we obtain that the convex search algorithm optimises LeadingOnes in [Formula: see text] fitness evaluations, which is faster than all unbiased unary black box algorithms.

International audience; We present an approach to genetic programming difficulty based on a statistical study of program fitness landscapes. The fitness distance correlation is used as an indicator of problem hardness and we empirically show that such a statistic is adequate in nearly all cases studied here. However, fitness distance correlation has some known problems and these are investigated by constructing an artificial landscape for which the correlation gives contradictory indications. Although our results confirm the usefulness of fitness distance correlation, we point out its shortcomings and give some hints for improvement in assessing problem hardness in genetic programming.

In this paper we present a technique for visualising hierarchical and symmetric, multi-modal fitness functions that have been investigated in the evolutionary computation literature. The focus of this technique is on landscapes in moderate-dimensional, binary spaces (i.e., fitness functions defined over {0,1}n, for n ≤ 16). The visualisation approach involves an unfolding of the hyperspace into a two-dimensional graph, whose layout represents the topology of the space using a recursive relationship, and whose shading defines the shape of the cost surface defined on the space. Using this technique we present case-study explorations of three fitness functions: royal road, hierarchical-if-and-only-if (H-IFF), and hierarchically decomposable functions (HDF). The visualisation approach provides an insight into the properties of these functions, particularly with respect to the size and shape of the basins of attraction around each of the local optima.

Various techniques for statistical analysis of the structure of fitness landscapes have been proposed. An important feature of these techniques is that they study the ruggedness of landscapes by measuring their correlation characteristics. This paper proposes a new information analysis of fitness landscapes. The underlying idea is to consider a fitness landscape as an ensemble of objects that are related to the fitness of neighboring points. Three information characteristics of the ensemble are defined and studied. They are termed: information content, partial information content, and information stability. The information characteristics of a range of landscapes with known correlation features are analyzed in an attempt to reveal the advantages of the information analysis. We show that the proposed analysis is an appropriate tool for investigating the structure of fitness landscapes.

The fitness landscape of the graph bipartitioning problem is investigated by performing a search space analysis for several types of graphs. The analysis shows that the structure of the search space is significantly different for the types of instances studied. Moreover, with increasing epistasis, the amount of gene interactions in the representation of a solution in an evolutionary algorithm, the number of local minima for one type of instance decreases and, thus, the search becomes easier. We suggest that other characteristics besides high epistasis might have greater influence on the hardness of a problem. To understand these characteristics, the notion of a dependency graph describing gene interactions is introduced. In particular, the local structure and the regularity of the dependency graph seems to be important for the performance of an algorithm, and in fact, algorithms that exploit these properties perform significantly better than others which do not. It will be shown that a simple hybrid multi-start local search exploiting locality in the structure of the graphs is able to find optimum or near optimum solutions very quickly. However, if the problem size increases or the graphs become unstructured, a memetic algorithm (a genetic algorithm incorporating local search) is shown to be much more effective.

Most evolutionary optimization models incorporate a fitness evaluation that is based on a predefined static set of test cases or problems. In the natural evolutionary process, selection is of course not based on a static fitness evaluation. Organisms do not have to combat every existing disease during their lifespan; organisms of one species may live in different or changing environments; different species coevolve. This leads to the question of how information is integrated over many generations. This study focuses on the effects of different fitness evaluation schemes on the types of genotypes and phenotypes that evolve. The evolutionary target is a simple numerical function. The genetic representation is in the form of a program (i.e., a functional representation, as in genetic programming). Many different programs can code for the same numerical function. In other words, there is a many-to-one mapping between “genotypes” (the programs) and “phenotypes”. We compare fitness evaluation based on a large static set of problems and fitness evaluation based on small coevolving sets of problems. In the latter model very little information is presented to the evolving programs regarding the evolutionary target per evolutionary time step. In other words, the fitness evaluation is very sparse. Nevertheless the model produces correct solutions to the complete evolutionary target in about half of the simulations. The complete evaluation model, on the other hand, does not find correct solutions to the target in any of the simulations. More important, we find that sparse evaluated programs are better generalizable compared to the complete evaluated programs when they are evaluated on a much denser set of problems. In addition, the two evaluation schemes lead to programs that differ with respect to mutational stability; sparse evaluated programs are less stable than complete evaluated programs.

Several previous studies have focused on modelling and analysing the collective dynamic behaviour of population-based algorithms. However, an empirical approach for identifying and characterising such a behaviour is surprisingly lacking. In this paper, we present a new model to capture this collective behaviour, and to extract and quantify features associated with it. The proposed model studies the topological distribution of an algorithm's activity from both a genotypic and a phenotypic perspective, and represents population dynamics using multiple levels of abstraction. The model can have different instantiations. Here it has been implemented using a modified version of self-organising maps. These are used to represent and track the population motion in the fitness landscape as the algorithm operates on solving a problem. Based on this model, we developed a set of features that characterise the population's collective dynamic behaviour. By analysing them and revealing their dependency on fitness distributions, we were then able to define an indicator of the exploitation behaviour of an algorithm. This is an entropy-based measure that assesses the dependency on fitness distributions of different features of population dynamics. To test the proposed measures, evolutionary algorithms with different crossover operators, selection pressure levels and population handling techniques have been examined, which lead populations to exhibit a wide range of exploitation-exploration behaviours.

This paper introduces a statistical fitness landscape analysis, based on Weinberger's random walk method and on a time series analysis known as the Box-Jenkins approach, to measure and express the correlation structure of fitness landscapes. The analysis has some additions to and advantages over previous methods for measuring this structure. The analysis is demonstrated on fitness landscapes constructed with Kauffman's NK-model, using two operators (point mutation and a form of crossover) and a combination of the two. Furthermore, the predictive value of the method is shown.

The application of evolutionary algorithms (EAs) in multiobjective optimization is currently receiving growing interest from researchers with various backgrounds. Most research in this area has understandably concentrated on the selection stage of EAs, due to the need to integrate vectorial performance measures with the inherently scalar way in which EAs reward individual performance, that is, number of offspring. In this review, current multiobjective evolutionary approaches are discussed, ranging from the conventional analytical aggregation of the different objectives into a single function to a number of population-based approaches and the more recent ranking schemes based on the definition of Pareto optimality. The sensitivity of different methods to objective scaling and/or possible concavities in the trade-off surface is considered, and related to the (static) fitness landscapes such methods induce on the search space. From the discussion, directions for future research in multiobjective fitness assignment and search strategies are identified, including the incorporation of decision making in the selection procedure, fitness sharing, and adaptive representations.

A grammar tree is used to encode a cellular developmental process that can generate whole families of Boolean neural networks for computing parity and symmetry. The development process resembles biological cell division. A genetic algorithm is used to find a grammar tree that yields both architecture and weights specifying a particular neural network for solving specific Boolean functions. The current study particularly focuses on the addition of learning to the development process and the evolution of grammar trees. Three ways of adding learning to the development process are explored. Two of these exploit the Baldwin effect by changing the fitness landscape without using Lamarckian evolution. The third strategy is Lamarckian in nature. Results for these three modes of combining learning with genetic search are compared against genetic search without learning. Our results suggest that merely using learning to change the fitness landscape can be as effective as Lamarckian strategies at improving search.

As practitioners we are interested in the likelihood of the population containing a copy of the optimum. The dynamic systems approach, however, does not help us to calculate that quantity. Markov chain analysis can be used in principle to calculate the quantity. However, since the associated transition matrices are enormous even for modest problems, it follows that in practice these calculations are usually computationally infeasible. Therefore, some improvements on this situation are desirable. In this paper, we present a method for modeling the behavior of finite population evolutionary algorithms (EAs), and show that if the population size is greater than 1 and much less than the cardinality of the search space, the resulting exact model requires considerably less memory space for theoretically running the stochastic search process of the original EA than the Nix and Vose-style Markov chain model. We also present some approximate models that use still less memory space than the exact model. Furthermore, based on our models, we examine the selection pressure by fitness-proportionate selection, and observe that on average over all population trajectories, there is no such strong bias toward selecting the higher fitness individuals as the fitness landscape suggests.

Various methods have been defined to measure the hardness of a fitness function for evolutionary algorithms and other black-box heuristics. Examples include fitness landscape analysis, epistasis, fitness-distance correlations etc., all of which are relatively easy to describe. However, they do not always correctly specify the hardness of the function. Some measures are easy to implement, others are more intuitive and hard to formalize. This paper rigorously defines difficulty measures in black-box optimization and proposes a classification. Different types of realizations of such measures are studied, namely exact and approximate ones. For both types of realizations, it is proven that predictive versions that run in polynomial time in general do not exist unless certain complexity-theoretical assumptions are wrong.

Memetic algorithms (MAs) have demonstrated very effective in combinatorial optimization. This paper offers explanations as to why this is so by investigating the performance of MAs in terms of efficiency and effectiveness. A special class of MAs is used to discuss efficiency and effectiveness for local search and evolutionary meta-search. It is shown that the efficiency of MAs can be increased drastically with the use of domain knowledge. However, effectiveness highly depends on the structure of the problem. As is well-known, identifying this structure is made easier with the notion of fitness landscapes: the local properties of the fitness landscape strongly influence the effectiveness of the local search while the global properties strongly influence the effectiveness of the evolutionary meta-search. This paper also introduces new techniques for analyzing the fitness landscapes of combinatorial problems; these techniques focus on the investigation of random walks in the fitness landscape starting at locally optimal solutions as well as on the escape from the basins of attractions of current local optima. It is shown for NK-landscapes and landscapes of the unconstrained binary quadratic programming problem (BQP) that a random walk to another local optimum can be used to explain the efficiency of recombination in comparison to mutation. Moreover, the paper shows that other aspects like the size of the basins of attractions of local optima are important for the efficiency of MAs and a local search escape analysis is proposed. These simple analysis techniques have several advantages over previously proposed statistical measures and provide valuable insight into the behaviour of MAs on different kinds of landscapes.

In this paper, we investigate the use of a self-adaptive Pareto evolutionary multi-objective optimization (EMO) approach for evolving the controllers of virtual embodied organisms. The objective of this paper is to demonstrate the trade-off between quality of solutions and computational cost. We show empirically that evolving controllers using the proposed algorithm incurs significantly less computational cost when compared to a self-adaptive weighted sum EMO algorithm, a self-adaptive single-objective evolutionary algorithm (EA) and a hand-tuned Pareto EMO algorithm. The main contribution of the self-adaptive Pareto EMO approach is its ability to produce sufficiently good controllers with different locomotion capabilities in a single run, thereby reducing the evolutionary computational cost and allowing the designer to explore the space of good solutions simultaneously. Our results also show that self-adaptation was found to be highly beneficial in reducing redundancy when compared against the other algorithms. Moreover, it was also shown that genetic diversity was being maintained naturally by virtue of the system's inherent multi-objectivity.

In this paper, we develop techniques based on evolvability statistics of the fitness land-scape surrounding sampled solutions. Averaging the measures over a sample of equal fitness solutions allows us to build up fitness evolvability portraits of the fitness land-scape, which we show can be used to compare both the ruggedness and neutrality in a set of tunably rugged and tunably neutral landscapes. We further show that the tech-niques can be used with solution samples collected through both random sampling of the landscapes and online sampling during optimization. Finally, we apply the techniques to two real evolutionary electronics search spaces and highlight differences between the two search spaces, comparing with the time taken to find good solutions through search.

A new mathematical representation is proposed for the configuration space structure induced by recombination, which we call “P-structure.” It consists of a mapping of pairs of objects to the power set of all objects in the search space. The mapping assigns to each pair of parental “genotypes” the set of all recombinant genotypes obtainable from the parental ones. It is shown that this construction allows a Fourier decomposition of fitness landscapes into a superposition of “elementary landscapes.” This decomposition is analogous to the Fourier decomposition of fitness landscapes on mutation spaces. The elementary landscapes are obtained as eigenfunctions of a Laplacian operator defined for P-structures. For binary string recombination, the elementary landscapes are exactly the p-spin functions (Walsh functions), that is, the same as the elementary landscapes of the string point mutation spaces (i.e., the hypercube). This supports the notion of a strong homomorphism between string mutation and recombination spaces. However, the effective nearest neighbor correlations on these elementary landscapes differ between mutation and recombination and among different recombination operators. On average, the nearest neighbor correlation is higher for one-point recombination than for uniform recombination. For one-point recombination, the correlations are higher for elementary landscapes with fewer interacting sites as well as for sites that have closer linkage, confirming the qualitative predictions of the Schema Theorem. We conclude that the algebraic approach to fitness landscape analysis can be extended to recombination spaces and provides an effective way to analyze the relative hardness of a landscape for a given recombination operator.

Genetic algorithms (GAs) are very efficient at exploring the entire search space; however, they are relatively poor at finding the precise local optimal solution in the region in which the algorithm converges. Hybrid GAs are the combination of improvement procedures, which are good at finding local optima, and GAs. There are two basic strategies for using hybrid GAs. In the first, Lamarckian learning, the genetic representation is updated to match the solution found by the improvement procedure. In the second, Baldwinian learning, improvement procedures are used to change the fitness landscape, but the solution that is found is not encoded back into the genetic string. This paper examines the issue of using partial Lamarckianism (i.e., the updating of the genetic representation for only a percentage of the individuals), as compared to pure Lamarckian and pure Baldwinian learning in hybrid GAs. Multiple instances of five bounded nonlinear problems, the location-allocation problem, and the cell formation problem were used as test problems in an empirical investigation. Neither a pure Lamarckian nor a pure Baldwinian search strategy was found to consistently lead to quicker convergence of the GA to the best known solution for the series of test problems. Based on a minimax criterion (i.e., minimizing the worst case performance across all test problem instances), the 20% and 40% partial Lamarckianism search strategies yielded the best mixture of solution quality and computational efficiency.

The effectiveness of crossover in accelerating evolution in genetic algorithms (GAs) is studied with a haploid finite population of bit sequences. A Babel-like fitness landscape is assumed. There is a single bit sequence (schema) that is significantly more advantageous than all the others. We study the time until domination of the advantageous schema (Td). Evolution proceeds with appearance, spread, and domination of the advantageous schema. The most important process determining Td is the appearance (creation) of the advantageous schema. Crossover helps this creation process and enhances the rate of evolution. To study this effect, we first establish an analytical method to estimate Td with or without crossover. Then, we conduct a numerical analysis using the frequency vector representation of the population with the recurrence relations formulated after GA operations. Finally, we carry out direct computer simulations with simple GAs operating on a population of binary strings directly prepared in the computer memory to examine the performance of the two analytical methods. It is shown that Td is reduced greatly by crossover with a mildly high rate when the mutation rate is adjusted to a moderate value and that an advantageous schema has a fairly large order (the number of bits). From these observations, we can determine implementation criteria for GAs, which are useful when we applying GAs to engineering problems having a conspicuously discontinuous fitness landscape.