Search

Improving on a previous paper, we explicitly relate reinforcement and selection learning (PBIL) algorithms for combinatorial optimization, which is understood as the task of finding a fixed-length binary string maximizing an arbitrary function. We show the equivalence of searching for an optimal string and searching for a probability distribution over strings maximizing the function expectation. In this paper however, we will only consider the family of Bernoulli distributions. Next, we introduce two gradient dynamical systems acting on probability vectors. The first one maximizes the expectation of the function and leads to reinforcement learning algorithms whereas the second one maximizes the logarithm of the expectation of the function and leads to selection learning algorithms. We finally give a stability analysis of solutions. [ABSTRACT FROM AUTHOR]

This paper presents an integrated on-line learning system to evolve programmable logic array (PLA) controllers for navigating an autonomous robot in a two-dimensional environment. The integrated online learning system consists of two learning modules: one is the module of reinforcement learning based on temporal-difference learning methods, and the other is the module of evolutionary learning based on genetic algorithms. The control rules extracted from the module of reinforcement learning can be used as input to the module of evolutionary learning, and quickly implemented by the PLA through on-line evolution. The on-line evolution has shown promise as a method of learning systems in complex environment. The evolved PLA controllers can successfully navigate the robot to a target in the two-dimensional environment while avoiding collisions with randomly positioned obstacles. [ABSTRACT FROM AUTHOR]

A technique for random number generation for a specific hardware Parallel Genetic Algorithm (PGA) architecture is presented. The thermal noise properties of silicon semiconductor material are used to provide a single true-random white noise source. This is combined with a bit-serial propagation technique to produce multiple true-random parallel number streams for parallel genetic evolution. The results demonstrate that the proposed architecture produces spatially and temporally uncorrelated numbers while minimising the complexity of generation and propagation hardware. [ABSTRACT FROM AUTHOR]

In the present paper, optimization of functions with uncertainty by means of Genetic Algorithms (GA) is discussed. For such problems, there have been proposed methods of sampling fitness function several times and taking average of them for evaluation of each individual. However, important applications having uncertain fitness functions are online adaptation of real systems and complicated computer simulation using random variables. In such applications, possible number of fitness evaluation is quite limited. Hence, methods achieving optimization with less number of fitness evaluation is needed. In the present paper, the authors propose a GA for optimization of continuous fitness functions with observation noise utilizing history of search so as to reduce number of fitness evaluation. In the proposed method, value of fitness function at a novel search point is estimated not only by the sampled fitness value at that point but also by utilizing the fitness values of individuals stored in the history of search. Computer experiments using quadric fitness functions show that the proposed method outperforms the conventional GA of sampling fitness values several times at each search point in noisy environment. [ABSTRACT FROM AUTHOR]

Recently, there has been an increasing interest in applying evolutionary computation to path planning [15]. To date, these evolutionary path planners have been single agent planners. In real-world environments where the knowledge of obstacles is naturally distributed, it is possible for single agent path planners to become overwhelmed by the volume of information needed to be processed in order to develop accurate paths quickly in non-stationary environments. In this paper, a new adaptive replacement strategy (ARS) is presented that allows steady-state evolutionary path planners to search efficiently in non-stationary environments. We compare this new ARS with another ARS using a test suite of 5 non-stationary path planning problems. Both of replacement strategies compared in this paper work by allowing an influx of diversity rather than increasing mutation rates. We refer to this influx of diversity as hyper-diversity. [ABSTRACT FROM AUTHOR]

When solving constraint satisfaction problems (CSPs) with stochastic search algorithms (SSAs) using the standard penalty function, it is not possible to show that there is no solution for a problem instance. In this paper we present a hybrid function that can be generally used in conjunction with SSAs to prove unsolvability without changing the search algorithms drastically. We use eight state-of-the-art algorithms to show the general usability of the new function. We compare the algorithms with and without the new penalty function and we test the scalability of the new function. [ABSTRACT FROM AUTHOR]

Experimental results reported in many papers suggest that making an appropriate choice of a method and its parameters to solve a nonlinear parameter optimisation problem remains an open question. The most promising approach at this stage of research seems to be experimental, involving a design of a scalable test suite of constrained optimisation problems. Then it would be possible to evaluate merits and drawbacks of the available optimisation methods as well as test new methods efficiently. In this paper we discuss the new test-case generator TCG-2 for constrained parameter optimisation techniques. The TCG-2 is capable of creating various test problems with different characteristics, including the dimensionality of the problem, number of local optima, number of active constraints at the optimum, topology of the feasible search space, etc. This test-case generator is very useful for analysing and comparing different constraint-handling techniques and different nonlinear parameter optimisation techniques. [ABSTRACT FROM AUTHOR]

Adaptivity has become a key issue in Evolutionary Algorithms, since early works in Evolution Strategies. The idea of letting the algorithm adjust its own parameters for free is indeed appealing. This paper proposes to use adaptive mechanisms at the population level for constrained optimization problems in three important steps of the evolutionary algorithm: First, an adaptive penalty function takes care of the penalty coefficients according to the proportion of feasible individuals in the current population; Second, a Seduction/Selection strategy is used to mate feasible individuals with infeasible ones and thus explore the region around the boundary of the feasible domain; Last, selection is tuned to favor a given number of feasible individuals. A detailed discussion of the behavior of the algorithm on two small constrained problems enlights adaptivity at work. Finally, experimental results on eleven test cases from the literature demonstrate the power of this approach. [ABSTRACT FROM AUTHOR]

In this paper, we propose a competitive image segmentation algorithm. It is a dynamic evolving optimization method, which we call the population algorithm. The method is inspired from nature, where the image segments are a population of entities that struggle for the limited image space and settle territory expansion conflicts locally without central authority. Hence, it is a region-based segmentation approach that locally considers region boundary adjustments in a dynamic way. Experiments confirm that this metaphor indeed applies when the image segmentation problem is modeled accordingly. [ABSTRACT FROM AUTHOR]

This paper presents an adaptive tit-for-tat strategy and a study of its behavior in spatial IPD games. The adaptive tit-for-tat strategy is shown elsewhere to demonstrate high performance in IPD tournaments or individual IPD games with other types of strategies, and obtains higher scores than the pure tit-for-tat strategy. In spatial IPD games, the strategy exhibits stability and resistance to perturbations, and those properties are more pronounced in variations of the spatial game model that induce some degree of "noise": probabilistic winning, spatial irregularity and continuous time. The adaptive tit-for-tat strategy is also compared to pure tit-for-tat and found to be more stable and predominant in perturbed environments. [ABSTRACT FROM AUTHOR]

This paper shows that the performance of coevolutionary genetic algorithms can be improved considerably by introducing a balancing mechanism. This is to prevent one population from —out-evolving― the other one. As a result, fitness variance is maintained and can be used to guide coevolution. Two different balancing mechanisms are introduced here. Their performance is compared to an unbalanced coevolutionary genetic algorithm. Finally, causal links are suggested between: a lack of balance, the loss of important niches and coevolutionary cycles. [ABSTRACT FROM AUTHOR]

Previous research on host-parasite algorithms has shown that the co-evolutionary arms race is difficult to sustain when the tasks faced by hosts and parasites are heavily asymmetric. We have therefore proposed an asymmetry-handling algorithm, AHPA, with a capacity for self-adapting the allocation of generations to hosts and parasites, so that the problem asymmetry is counteracted. In this paper we discuss the need for systematic evaluation of this algorithm, so that its behaviour under varying levels of asymmetry can be studied in detail. We propose the use of Kaufmann's NK landscape model for this purpose, and show how the model can be adapted for the testing of host-parasite algorithms. Using the adapted model, we present simulation results which confirm AHPA's ability to sustain a stable arms-race under varying levels of asymmetry. [ABSTRACT FROM AUTHOR]

In the study of the evolution of altruism two possible mechanisms have been distinguished. One is reciprocal altruism, the other is kin selection. This paper focuses on altruism based on kin selection in environments in which there is little migration of individuals ("viscous populations"). Two simulations show that the evolution of evolutionarily stable non-reciprocal altruism is possible in societies with limited dispersal, confirming earlier research [1]. It has been questioned, however, whether these conditions occur in natural situations. This paper demonstrates that if the tendency to migrate is itself represented as a gene controlled by an evolutionary process, a tendency not to migrate evolves among altruists. Thus, the conditions which would allow the evolution of altruism are not merely a matter of coincidence, but are actively selected for, increasing the likelihood that it will be present in natural situations. [ABSTRACT FROM AUTHOR]

The fundamental distinction between ordinary evolutionary algorithms (EA) and co-evolutionary algorithms lies in the interaction between coevolving entities. We believe that this property is essentially game-theoretic in nature. Using game theory, we describe extensions that allow familiar mixing-matrix and Markov-chain models of EAs to address coevolutionary algorithm dynamics. We then employ concepts from evolutionary game theory to examine design aspects of conventional coevolutionary algorithms that are poorly understood. [ABSTRACT FROM AUTHOR]

We explore a new general-purpose heuristic for finding high-quality solutions to hard optimization problems. The method, called extremal optimization, is inspired by "self-organized criticality," a concept introduced to describe emergent complexity in many physical systems. In contrast to Genetic Algorithms which operate on an entire "gene-pool" of possible solutions, extremal optimization successively replaces extremely undesirable elements of a sub-optimal solution with new, random ones. Large fluctuations, called "avalanches," ensue that efficiently explore many local optima. Drawing upon models used to simulate far-from-equilibrium dynamics, extremal optimization complements approximation methods inspired by equilibrium statistical physics, such as simulated annealing. With only one adjustable parameter, its performance has proved competitive with more elaborate methods, especially near phase transitions. Those phase transitions are found in the parameter space of most optimization problems, and have recently been conjectured to be the origin of some of the hardest instances in computational complexity. We will demonstrate how extremal optimization can be implemented for a variety of combinatorial optimization problems. We believe that extremal optimization will be a useful tool in the investigation of phase transitions in combinatorial optimization problems, hence valuable in elucidating the origin of computational complexity. [ABSTRACT FROM AUTHOR]

Recombination in the Genetic Algorithm (GA) is supposed to enable the component characteristics from two parents to be extracted and then reassembled in different combinations — hopefully producing an offspring that has the good characteristics of both parents. However, this can only work if it is possible to identify which parts of each parent should be extracted. Crossover in the standard GA takes subsets of genes that are adjacent on the genome. Other variations of the GA propose more sophisticated methods for identifying good subsets of genes within an individual. Our approach is different; rather than devising methods to enable successful extraction of gene-subsets from parents, we utilize variable-size individuals which represent subsets of genes from the outset. Joining together two individuals, creating an ‘offspring' that is twice the size, straight-forwardly produces the sum of the parents' characteristics. This form of component assembly is more closely analogous to combination of symbiotic organisms than it is to sexual recombination. Whereas sexual recombination, modeled by crossover, occurs between similar individuals and exchanges subsets of genes, symbiotic combination, as modeled in our operator, can occur between entirely unrelated species and combines together whole organisms. This paper summarizes our research on this approach to recombination in GAs and describes new methods that illustrate its potential. [ABSTRACT FROM AUTHOR]

This paper considers a new method that enables a genetic algorithm (GA) to identify and maintain multiple optima of a multimodal function, by creating subpopulations within the niches defined by the multiple optima, thus warranting a good "diversity". The algorithm is based on a splitting of the traditional GA into a sequence of two processes. Since the GA behavior is determined by the exploration / exploitation balance, during the first step (Exploration), the multipopulation genetic algorithm coupled with a speciation method detects the potential niches by classifying "similar" individuals in the same population. Once the niches are detected. the algorithm achieves an intensification (Exploitation), by allocating a separate portion of the search space to each population. These two steps are alternately performed at a given frequency. Empirical results obtained with F6 Schaffer's function are then presented to show the reliability of the algorithm. [ABSTRACT FROM AUTHOR]

We propose to show from a study of population genetics that convergence in the simple genetic algorithm is due to the homogeneous nature of its population. By applying an adaptive clustering algorithm we demonstrate that highly fit yet diverse populations result. Heterogenity is established using both genotypic and phenotypic measures, and we show that genetic algorithms using genotypic measures out perform both the simple genetic algorithm and ones using a phenotypic measure. [ABSTRACT FROM AUTHOR]

We describe a new selection scheme for steady-state evolution strategies, median selection. In steady-state algorithms, only one individual is generated and evaluated at each step and is immediately integrated into the population. This is especially well suited for parallel fitness evaluation in a multiprocessor environment. Previous steady-state selection schemes resembled (μ + λ) selection, which has a disadvantage in self-adaptation of the mutation step length. Median selection is similar to (μ, λ) selection. Median selection is compared with other steady-state selection schemes and with (μ, λ) selection on a uniprocessor and on a multiprocessor. It achieves equally good or better results as the best other selection scheme for a number of benchmark functions. [ABSTRACT FROM AUTHOR]

When handling tree networks, researchers have sometimes tried using the Pruefer number representation for encoding networks, however GAs often degraded when used on this encoding. This paper investigates the locality of the Pruefer number and its affect on the performance of a Genetic Algorithm (GA). The locality describes how the neighborhood of the genotype is preserved when constructing the phenotype (the tree) from the genotype (the Pruefer number). It is shown that the locality of the Pruefer number is highly irregular on the entire solution space, and that the performance of a GA depends on the structure of the optimal solution. A GA is able to perform well only for networks that have a high locality (stars). For all other types of networks (lists, trees) the locality is low and a GA fails to find the best list or tree. Using a GA with the Pruefer number encoding can be useful, when the best solution tends to be a star. The locality of an encoding could have a strong influence on the performance of a GA. When choosing encodings for optimization problems, researchers should be aware of this and be careful with low locality encodings. If the locality of the encoding is low, a failure of the GA is often unavoidable. [ABSTRACT FROM AUTHOR]

Complex systems are typically composed of a large number of locally interacting components that operate at a critical state between chaos and order, which is known as self-organised criticality. A common feature of this state is the exponential (power law) relationship between the frequency of an event and the size of its impact, such as the event of an earthquake and its strength on the Richter scale. Most state transitions in a component of a complex system only affect its neighbourhood, but once in a while entire avalanches of propagating state transitions can lead to a major reconfiguration of the system. In evolution, this system behaviour has been identified in species extinction on an evolutionary time-scale, where avalanches correspond to mass extinction. In this paper, we applied the concept of self-organised criticality (SOC) to control mutation on the individual level and extinction on the population level in the context of evolutionary algorithms (EA). Our results show that the SOC EAs clearly outperform standard EAs and a previously introduced mass extinction model. Interestingly, the great performance of our SOC EAs is based on a very simple modification of standard EAs and implies almost no additional computational costs. [ABSTRACT FROM AUTHOR]

This paper introduces clustering as a tool to improve the effects of recombination and incorporate niching in evolutionary algorithms. Instead of processing the entire set of parent solutions, the set is first clustered and the solutions in each of the clusters are processed separately. This alleviates the problem of symmetry which is often a major difficulty of many evolutionary algorithms in combinatorial optimization. Furthermore, it incorporates niching into genetic algorithms and, for the first time, the probabilistic model-building genetic algorithms. The dynamics and performance of the proposed method are illustrated on example problems. [ABSTRACT FROM AUTHOR]

In this paper, we perform theoretical analysis and experiments on the Simplex Crossover (SPX), which we have proposed. Real-coded GAs are expected to be a powerful function optimization technique for real-world applications where it is often hard to formulate the objective function. However, we believe there are two problems which will make such applications difficult; 1) performance of real-coded GAs depends on the coordinate system used to express the objective function, and 2) it costs much labor to adjust parameters so that the GAs always find an optimum point efficiently. The result of our theoretical analysis and experiments shows that a performance of SPX is independent of linear coordinate transformation and that SPX always optimizes various test function efficiently when theoretical value for expansion rate, which is a parameter of SPX, is applied. [ABSTRACT FROM AUTHOR]

A conceptual objective behind the self-adaptation of the mutation distribution is to achieve invariance against certain transformations of the search space. In this paper, a priori invariances of a simple evolution strategy and invariances, which can be introduced by self-adaptation, are identified. In principle, correlated mutations can achieve invariance against any linear transformation of the search space. Correlated mutations, as typically implemented, are investigated with respect to both a priori and new invariances. Simulations reveal that neither all a priori invariances are retained, nor the invariance against linear transformation is achieved. [ABSTRACT FROM AUTHOR]

In the past years several evolutionary algorithms have been applied to the fixed charge transportation problem (FCTP). Although suffering from a lack of locality, the Prüfer number representation has recently been suggested for the FCTP, and — to our surprise — it has been reported to yield good results. Since this disagrees with the common intuition that locality is an important prerequisite of successful evolutionary search, we analyse the Prüfer number representation in greater detail. The results show that the Prüfer number representation is superior to random search but clearly inferior to the permutation representation with respect to solution quality, which is explained by our locality analysis. [ABSTRACT FROM AUTHOR]

A problem in the use of genetic algorithms is premature convergence, a premature stagnation of the search caused by the lack of population diversity. The mutation operator is the one responsible for the generation of diversity and therefore may be considered to be an important element in solving this problem. A solution adopted involves the control, throughout the run, of the parameter that determines its operation: the mutation probability. In this paper, we study an adaptive approach for the control of the mutation probability based on the application of fuzzy logic controllers. Experimental results show that this technique consistently outperforms other mechanisms presented in the genetic algorithm literature for controlling this genetic algorithm parameter. [ABSTRACT FROM AUTHOR]

A family of recombination operators is studied in this work. These operators are based on keeping and using certain information about the past evolution of the algorithm to guide the recombination process. Within this framework, several recombination operators are specifically designed to preserve diversity within the population, while avoiding implicit mutations. The empirical evaluation of these operators on instances of two test problems (k-EMP and permutation flowshop) shows an improvement of the results with respect to other classical operators. This improvement seems to related to the increasing degree of epistasis of the problem. [ABSTRACT FROM AUTHOR]

In this paper we implement GAs that have one or more parameters that are adjusted during the run. In particular we use an existing self-adaptive mutation rate mechanism, propose a new mechanism for self-adaptive crossover rates, and redesign an existing variable population size model. We compare the simple GA with GAs featuring only one of the parameter adjusting mechanisms and with a GA that applies all three mechanisms - and is therefore almost "parameterless". The experimental results on a carefully designed test suite indicate the superiority of the parameterless GA and give a hint on the power of adapting the population size. [ABSTRACT FROM AUTHOR]

A variety of Genetic Algorithms (GA's) for the static Job Shop Scheduling Problem have been developed using various methods: direct vs. indirect representations, pure vs. hybrid GA's and serial vs. parallel GA's. We implement a hybrid GA, called OBGT, for solving JSSP. A chromosome representation containing the schedule itself is used and order-based operators are combined with techniques that produce active and non-delay schedules. Additionally, local search is applied to improve each individual created. OBGT results are compared in terms of the quality of solutions against the state-of-the-art Nowicki and Smutnicki Tabu Search algorithm as well as other GAs, including THX, HGA and GA3. The test problems include different problem classes from the OR-library benchmark problems and more structured job-correlated and machine-correlated problems. We find that each technique, including OBGT, is well suited for particular classes of benchmark problems, but no algorithm is best across all problem classes. [ABSTRACT FROM AUTHOR]

We propose a hybrid approach for solving hybrid-flow-shop problems based on the combination of genetic algorithms and a modified Giffler & Thompson (G&T) algorithm. Several extensions of the hybrid-flow-shop are considered and discussed in the context of a real-world example. The genome in the GA encodes a choice of rules to be used to generate production schedules via the G&T algorithm. All constraints to the scheduling task are observed by the G&T algorithm. Therefore, it provides a well suited representation for the GA and leads to a decoupling of domain specific details and genetic optimization. The proposed method is applied to the optimization of a batch annealing plant. [ABSTRACT FROM AUTHOR]

The traditional focus of scheduling research is finding schedules with a low implementation cost. However, in many real world scheduling applications finding a robust schedule (a quality schedule expected to still be acceptable if something unforeseen happens) or a flexible schedule (a quality schedule expected to be easy to change) is just as important. In this paper the robustness and flexibility of schedules produced by minimizing neighbourhood based robustness measures are investigated. The basic idea is to minimize not only the implementation cost of a single schedule, but the implementation costs of a set of schedules located around a centre schedule. The problems used in the experiments are worst tardiness, summed tardiness and total flow time job shop problems. It is found that the robustness measures increase robustness and to some degree flexibility for worst tardiness and loose summed tardiness problems, while they do not perform well for tight summed tardiness problems and total flow time problems. It is conjectured that neighbourhood based robustness can be expected to work well on problems with few critical points and not well on problems with many critical points. [ABSTRACT FROM AUTHOR]

Genetic Algorithms(GAs) are effective approximation algorithms which focus on "hopeful area" in searching process. However, in harder problems, it is often very difficult to maintain a favorable trade-off between exploitation and exploration. All individuals leave the big-valley including the global optimum, and concentrate on another big-valley including a local optimum often. In this paper, we define such a situation on conventional GAs as the "UV-phenomenon", and suggest UV-structures as hard landscape structures that will cause the UV-phenomenon. We propose Innately Split Model(ISM) as a new GA model which can avoid the UV-phenomenon. We apply ISM to Job-shop Scheduling Problem (JSP), which is considered as one of globally multi-modal and UV-structural problems. It is shown that ISM surpasses all famous approximation algorithms applied to JSP. [ABSTRACT FROM AUTHOR]

Over the past three decades extensive search have been done on pure m-machine flow shop problems. Many researchers faced the Flow Shop Scheduling Problem (FSSP) by means of well-known heuristics which, are successfully used for certain instances of the problem providing a single acceptable solution. Current trends involve distinct evolutionary computation approaches. This work shows an implementation of diverse evolutionary approaches on a set of flow shop scheduling instances, including latest approaches using a multirecombination feature, Multiple Crossovers per Couple (MCPC), and partial replacement of the population when possible stagnation is detected. A discussion on implementation details, analysis and a comparison of evolutionary and conventional approaches to the problem are shown. [ABSTRACT FROM AUTHOR]

This contribution addresses the role of anticipation in evolutionary algorithms for dynamic optimization problems. Recent approaches have mainly focused on maintaining the population diversity as a warrant for the ability of tracking the optimum. In our paper, we show that it is also useful to anticipate changes of the environment by explicitly searching for solutions which maintain flexibility. Although this is a valid approach to all dynamic optimization problems, it seems particularly important for optimization problems where a part of the solution is fixed at each step. For the example of job shop scheduling, we suggest a measure of flexibility and show that much better solutions can be obtained when this measure is incorporated into the fitness-function. [ABSTRACT FROM AUTHOR]

In the paper, we investigate theoretical and practical aspects of distributed computing for simulated annealing algorithms applied to the problem of scheduling l jobs on m machines. Given n = l · m, the total number of tasks, O(n3) processors and an upper bound Λ = Λ(l, m) of the objective function, the expected run-times of parallelized versions of our heuristics [14] are O(n · log n · log Λ) for the exponential cooling schedule and O(n2 · log3/2n · m1/2 · log Λ) for the hyperbolic one. For Markov chains of constant length, the results imply a polylogarithmic run-time O(log n · log(l + m)) for the exponential schedule, where we employ Λ ≤ O(l + m), see Leighton et al. [10]. We implemented a distributed version of our sequential heuristics and first computational experiments on benchmark instances are presented. [ABSTRACT FROM AUTHOR]

Committee machines are known to improve the performance of individual learners. Evolutionary algorithms generate multiple individuals that can be combined to build committee machines. However, it is not easy to decide how big the committee should be and what members constitute the best committee. In this paper, we present a probabilistic search method for determining the size and members of the committees of individuals that are evolved by a standard GP engine. Applied to a suite of benchmark learning tasks, the GP committees achieved significant improvement in prediction accuracy. [ABSTRACT FROM AUTHOR]

In this paper we discuss the polymorphic abilities of a new distributed representation for genetic programming, called Genetically Programmed Networks. These are inspired in a common structure in natural complex adaptive systems, where system functionality frequently emerges from the combined functionality of simple computational entities, densely interconnected for information exchange. A Genetically Programmed Network can be evolved into a distributed program, a rule based system or a neural network with simple adjustments to the evolutionary algorithm. The space of possible network topologies can also be easily controlled. This allows the fast exploration of various search spaces thus increasing the possibility of finding a (or a better) solution. Experimental results are presented to support our claims. [ABSTRACT FROM AUTHOR]

Application of Genetic Programming to the discovery of empirical laws is often impaired by the huge size of the domains involved. In physical applications, dimensional analysis is a powerful way to trim out the size of these spaces This paper presents a way of enforcing dimensional constraints through formal grammars in the GP framework. As one major limitation for grammar-guided GP comes from the initialization procedure (how to find admissible and sufficiently diverse trees with a limited depth), an initialization procedure based on dynamic grammar pruning is proposed. The approach is validated on the problem of identification of a materials response to a mechanical test. [ABSTRACT FROM AUTHOR]

To investigate the fundamental causes of bloat, six artificial random binary tree search spaces are presented. Fitness is given by program syntax (the genetic programming genotype). GP populations are evolved on both random problems and problems with "building blocks". These are compared to problems with explicit ineffective code (introns, junk code, inviable code). Our results suggest the entropy random walk explanation of bloat remains viable. The hard building block problem might be used in further studies, e.g. of standard subtree crossover. [ABSTRACT FROM AUTHOR]

The "ocean color" problem consists in evaluating ocean components concentrations (phytoplankton, sediment, yellow substance) from sunlight reflectance or luminance values at selected wavelengths in the visible band. The interest of this application increases with the availability of new satellite sensors. Moreover monitoring phytoplankton concentrations is a key point for a wide set of problems ranging from greenhouse effect to industrial fishing and signaling toxic algae blooms. To our knowledge, it is the first attempt at this regression problem with Genetic Programming (GP). We show that GP outperforms traditional polynomial fits and rivals artificial neural nets in the case of open ocean waters. We improve on previous works by also solving a range of coastal waters types, providing detailed results on estimation errors. Some experiments were conducted with a dynamic fitness GP algorithm in order to speed up computing time through a process of progressive learning. [ABSTRACT FROM AUTHOR]

When genetic programming (GP) is used to find programs with Boolean inputs and outputs, ordered binary decision diagrams (OB-DDs) are often used successfully. In all known OBDD-based GP-systems the variable ordering, a crucial factor for the size of OBDDs, is preset to an optimal ordering of the known test function. Certainly this cannot be done in practical applications, where the function to learn and hence its optimal variable ordering are unknown. Here, the first GP-system is presented that evolves the variable ordering of the OBDDs and the OBDDs itself by using a distributed hybrid approach. For the experiments presented the unavoidable size increase compared to the optimal variable ordering is quite small. Hence, this approach is a big step towards learning well-generalizing Boolean functions. [ABSTRACT FROM AUTHOR]

Permutations can represent search problems when all points in the search space have unique evaluations. Given a particular set of N evaluations we have N! search algorithms and N! possible functions. A general No Free Lunch result holds for this finite set of N! functions. Furthermore, it is proven that the average description length over the set of N! functions must be O(N lg N). Thus if the size of the search space is exponentially large with respect to a parameter set which specifies a point in the search space, then the description length of the set of N! functions must also be exponential on average. Summary statistics are identical for all instances of the set of N! functions, including mean, variance, skew and other r-moment statistics. These summary statistics can be used to show that any set of N! functions must obey a set of identical constraints which holds over the set of Walsh coefficients. This also imposes mild constraints on schema information for the set of N! functions. When N = 2L subsets of the N! functions are related via Gray codes which partition N! into equivalence classes of size 2L. [ABSTRACT FROM AUTHOR]

This work introduces a general mathematical framework for non-stationary fitness functions which enables the exact definition of certain problem properties. The properties' influence on the severity of the dynamics is analyzed and discussed. Various different classes of dynamic problems are identified based on the properties. Eventually, for an exemplary model search space and a (1, λ)-strategy, the interrelation of the offspring population size and the success rate is analyzed. Several algorithmic techniques for dynamic problems are compared for the different problem classes. [ABSTRACT FROM AUTHOR]

Persistence is a characteristic that distinguishes between different types of objects in our world: alive or dead, stable or unstable. The fact that some objects are able to persist, both in static and dynamic ways, and others are not, appears to be a cornerstone of why interesting things happen in our universe. Hence, the class of dynamical systems in which persistence plays an important role should be a very interesting class of systems. Persistence also appears to be an important aspect of the dynamics displayed by evolutionary search algorithms. In this paper I shall introduce a new measure of static persistence that is more sophisticated than the measure used in previous work. It is shown how this new measure may be useful in distinguishing between dynamics that are performing search and those that are not. [ABSTRACT FROM AUTHOR]

Kauffman's NK-landscapes have become a popular tool for investigating properties of heuristic search algorithms. In this paper we carry out some experiments with a more general, but still tuneable, class of landscapes which we call ℓ, θ landscapes. These landscapes are characterized by a parameter θ which allows interactions at all orders, rather than merely at orders up to a fixed level as is the case with NK-landscapes. This is accomplished by fixing the magnitude and sign of the effects in an experimental design (ED) decomposition of a function. In some cases the cpistasis variance is a simple function of θ, and can be specified in advance. Further, by choosing some measure of the Hamming landscape associated with these functions, such as the number of local optima or the size of the global optimum's basin, it is possible to tune the landscape by mapping the effects onto a search problem. Some experiments are reported with a GA on these landscapes, with results that are rather surprising, in that the quality of the solution obtained appears to be poorly predicted by the properties of the associated Hamming landscape. [ABSTRACT FROM AUTHOR]

This paper investigates the occurrence of error thresholds in genetic algorithms (GAs) running on a wide range of fitness landscape structures. The error threshold, a notion from molecular evolution, is a critical mutation rate beyond which the evolutionary dynamics of a population changes drastically. The paper also introduces Consensus sequence plots, an empirical tool for locating error thresholds on complex landscapes. This plots were borrowed and adapted from theoretical biology. Results suggest that error thresholds occur in GAs but only on landscapes of certain degree of ruggedness or complexity. Moreover, consensus sequence plots can be useful for predicting some features of a landscape such as ruggedness and "step-ness". We argue that error thresholds and consensus sequence plots, may become useful tools for analyzing evolutionary algorithms and visualising the structure of fitness landscapes. [ABSTRACT FROM AUTHOR]

Evolution Strategies (ES) are an approach to numerical optimization that show good optimization performance. The evolutionary behavior of ES has been well-studied on simple problems but not on large complex problems, such as those with highly rugged search spaces, or larger scale problems like those frequently used as benchmark problems for numerical optimization. In this paper, the evolutionary characteristics of ES on complex problems are examined using three different statistical approaches. These are (1) basic statistical measures at the function-value level, (2) Hotelling's T2 for measuring the balance of exploitation and exploration at the individual-code level and (3) principal components analysis at the individual-code level for visualizing the distribution of the population. Among many formulations of ES, the fast-ES and the robust-ES are adopted for the analyses. [ABSTRACT FROM AUTHOR]

When considering continuous spaces EA, a convenient tool to model these algorithms is perturbation theory. In this paper we present preliminary results, derived from Freidlin-Wentzell theory, related to the convergence of a simple EA model. The main result of this paper yields a bound on sojourn times of the Markov process in subsets centered around the maxima of the fitness function. Exploitation of this result opens the way to convergence speed bounds with respect to some statistical measures on the fitness function (likely related to irregularity). [ABSTRACT FROM AUTHOR]

The natural gene expression process evaluates the fitness of a DNA-string through a sequence of representation transformations. The genetic code defines one such transformation in this process. This paper shows that genetic code-like transformations introduce an interesting property in the representation of a genetic fitness function. It points out that such adaptive transformations can convert some functions with an exponentially large description in Fourier basis to one that is highly suitable for polynomial-size approximation. Such transformations can construct a Fourier representation with only a polynomial number of terms that axe exponentially more significant than the rest when fitter chromosomes are given more copies through a redundant, equivalent representation. This is a very desirable property [2, 3] for efficient function-induction from data which is a fundamental problem in learning, data mining, and optimization. [ABSTRACT FROM AUTHOR]

When evolutionary algorithms are used for function optimization, they perform a heuristic search that is influenced by many parameters. Here, the choice of the mutation probability is investigated. It is shown for a non-trivial example function that the most recommended choice for the mutation probability 1/n is by far not optimal, i. e., it leads to a superpolynomial running time while another choice of the mutation probability leads to a search algorithm with expected polynomial running time. Furthermore, a simple evolutionary algorithm with an extremely simple dynamic mutation probability scheme is suggested to overcome the difficulty of finding a proper setting for the mutation probability. [ABSTRACT FROM AUTHOR]