Defining locality as a problem difficulty measure in genetic programming

A mapping is local if it preserves neighbourhood. In Evolutionary Computation, locality is generally described as the property that neighbouring genotypes correspond to neighbouring phenotypes. A representation has high locality if most genotypic neighbours are mapped to phenotypic neighbours. Locality is seen as a key element in performing effective evolutionary search. It is believed that a representation that has high locality will perform better in evolutionary search and the contrary is true for a representation that has low locality. When locality was introduced, it was the genotype-phenotype mapping in bitstring-based Genetic Algorithms which was of interest; more recently, it has also been used to study the same mapping in Grammatical Evolution. To our knowledge, there are few explicit studies of locality in Genetic Programming (GP). The goal of this paper is to shed some light on locality in GP and use it as an indicator of problem difficulty. Strictly speaking, in GP the genotype and the phenotype are not distinct. We attempt to extend the standard quantitative definition of genotype-phenotype locality to the genotype-fitness mapping by considering three possible definitions. We consider the effects of these definitions in both continuous- and discrete-valued fitness functions. We compare three different GP representations (two of them induced by using different function sets and the other using a slightly different GP encoding) and six different mutation operators. Results indicate that one definition of locality is better in predicting performance.     

A study of fitness distance correlation as a difficulty measure in genetic programming

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.     

Interweaving genetic programming and genetic algorithm for structural and parametric optimization in adaptive platform product customization

An adaptive product platform offers high customizability for generating feasible product variants for customer requirements. Customization takes place not only to product platform structure but also to its relevant parameters. Structural and parametric optimization processes are interwoven with each other to achieve the total optimality. This paper presents an evolutionary method dealing with interwoven structural and parametric optimization of adaptive platform product customization. The method combines genetic programming and genetic algorithm for handling structural and parametric optimization, respectively. Efficient genetic representation and operation schemes are carefully adapted. While designing these schemes, features specific to structural and parameter customization are considered for the simplification of platform product management. The experimental results show that the performance of the proposed algorithm outperforms that of the tandem evolutionary algorithm in which a genetic algorithm for parametric optimization is totally nested in a genetic programming for structural optimization.     

Emergence in genetic programming

Banzhaf explores the concept of emergence and how and where it happens in genetic programming [1]. Here we consider the question: what shall we do with it? We argue that given our ultimate goal to produce genetic programming systems that solve new and difficult problems, we should take advantage of emergence to get closer to this goal.     

Population variation in genetic programming

A new population variation approach is proposed, whereby the size of the population is systematically varied during the execution of the genetic programming process with the aim of reducing the computational effort compared with standard genetic programming (SGP). Various schemes for altering population size under this proposal are investigated using a comprehensive range of standard problems to determine whether the nature of the “population variation”, i.e. the way the population is varied during the search, has any significant impact on GP performance. The initial population size is varied in relation to the initial population size of the SGP such that the worst case computational effort is never greater than that of the SGP. It is subsequently shown that the proposed population variation schemes do have the capacity to provide solutions at a lower computational cost compared with the SGP.     

Open issues in genetic programming

It is approximately 50 years since the first computational experiments were conducted in what has become known today as the field of Genetic Programming (GP), twenty years since John Koza named and popularised the method, and ten years since the first issue appeared of the Genetic Programming & Evolvable Machines journal. In particular, during the past two decades there has been a significant range and volume of development in the theory and application of GP, and in recent years the field has become increasingly applied. There remain a number of significant open issues despite the successful application of GP to a number of challenging real-world problem domains and progress in the development of a theory explaining the behavior and dynamics of GP. These issues must be addressed for GP to realise its full potential and to become a trusted mainstream member of the computational problem solving toolkit. In this paper we outline some of the challenges and open issues that face researchers and practitioners of GP. We hope this overview will stimulate debate, focus the direction of future research to deepen our understanding of GP, and further the development of more powerful problem solving algorithms.     

Repeated patterns in genetic programming

Evolved genetic programming trees contain many repeated code fragments. Size fair crossover limits bloat in automatic programming, preventing the evolution of recurring motifs. We examine these complex properties in detail using depth vs. size Catalan binary tree shape plots, subgraph and subtree matching, information entropy, sensitivity analysis, syntactic and semantic fitness correlations. Programs evolve in a self-similar fashion, akin to fractal random trees, with diffuse introns. Data mining frequent patterns reveals that as software is progressively improved a large proportion of it is exactly repeated subtrees as well as exactly repeated subgraphs. We relate this emergent phenomenon to building blocks in GP and suggest GP works by jumbling subtrees which already have high fitness on the whole problem to give incremental improvements and create complete solutions with multiple identical components of different importance.     

Hoare logic-based genetic programming

Almost all existing genetic programming systems deal with fitness evaluation solely by testing. In this paper, by contrast, we present an original approach that combines genetic programming with Hoare logic with the aid of model checking and finite state automata, henceby proposing a brand new verification-focused formal genetic programming system that makes it possible to evolve reliable programs with mathematically-verified properties.     

Stochastic bilevel programming in structural optimization

We consider the mathematical modelling and solution of robust and cost-optimizing structural (topology) design problems. The setting is the optimal design of a linear-elastic structure, for example a truss topology, under unilateral frictionless contact, and under uncertainty in the data describing the load conditions, the material properties, and the rigid foundation. The resulting stochastic bilevel optimization model finds a structural design that responds the best to the given probability distribution in the data. This model is of special interest when a structural failure will lead to a reconstruction cost, rather than loss of life. For the mathematical model, we provide results on the existence of optimal solutions which allow for zero lower design bounds. We establish that the optimal solution is continuous in the lower design bounds, a result which validates the use of small but positive values of them, and for such bounds we also establish the locally Lipschitz continuity and directional differentiability of the implicit upper-level objective function. We also provide a heuristic algorithm for the solution of the problem, which makes use of its differentiability properties and parallelization strategies across the scenarios. A small set of numerical experiments illustrates the behaviour of the stochastic solution compared to an average-case deterministic one, establishing an increased robustness. Received December 22, 1999     

Dynamic population variation in genetic programming

Three innovations are proposed for dynamically varying the population size during the run of the genetic programming (GP) system. These are related to what is called Dynamic Population Variation (DPV), where the size of the population is dynamically varied using a heuristic feedback mechanism during the execution of the GP with the aim of reducing the computational effort compared with Standard Genetic Programming (SGP). Firstly, previously developed population variation pivot functions are controlled by four newly proposed characteristic measures. Secondly, a new gradient based pivot function is added to this dynamic population variation method in conjunction with the four proposed measures. Thirdly, a formula for population variations that is independent of special constants is introduced and evaluated. The efficacy of these innovations is examined using a comprehensive range of standard representative problems. It is shown that the new ideas do have the capacity to provide solutions at a lower computational cost compared with standard genetic programming and previously reported algorithms such as the plague operator and the static population variation schemes previously introduced by the authors.     

Redundancy and computational efficiency in Cartesian genetic programming

The graph-based Cartesian genetic programming system has an unusual genotype representation with a number of advantageous properties. It has a form of redundancy whose role has received little attention in the published literature. The representation has genes that can be activated or deactivated by mutation operators during evolution. It has been demonstrated that this "junk" has a useful role and is very beneficial in evolutionary search. The results presented demonstrate the role of mutation and genotype length in the evolvability of the representation. It is found that the most evolvable representations occur when the genotype is extremely large and in which over 95% of the genes are inactive.     

On condensed geometric programming in structural optimisation

The solution of optimisation problems by a sequence of condensed geometric programmes has given rise to a rapidly convergent algorithm for minimum weight structural design. The basis of this algorithm is largely intuitive, and the present paper attempts to place the method on a firmer foundation. This is sought by examining the properties exhibited by the dual geometric programming problem which forms the kernal of many computer routines. It is shown that the solution method is equivalent to a logarithmic form of the popular and numerically verified “optimality-criterion” technique. In addition, it is found to have important properties relating to concavity, scalar invariance and linearity.     

Applications of linear programming in structural layout and optimization

Various computer methods have been developed for the optimal design of indeterminate structures, but it is not possible to guarantee that the result of any method will be a global optimum, rather than merely a local optimum. By temporarily neglecting the conditions of elastic compatibility and formulating a mathematical optimization problem based on the equilibrium conditions and the stress constraints, it is possible to obtain an approximate design which avoids merely local optima. In the cases examined, this design is close to the exact global optimum obtained by enforcing the compatibility conditions and is therefore a good starting point for an optimizing procedure. Examples include a graphical solution of a simple grillage known to have multiple local optima, and a sequence of planar trusses under alternate loading conditions. Linear programming is used to find the minimum weight truss designs satisfying equilibrium; this method eliminates extraneous members and leads to better indeterminate truss configurations than does a stress-ratio type algorithm.     

Optimality criteria and mathematical programming in structural weight optimization

It is shown that the optimality criteria approach to the structural weight minimization results from a proper linearization of the displacement constraints but not of the stress constraints in terms of the reciprocal design variables. On the basis of this interpretation, two new ideas are suggested. First, a “mixed method” is proposed, that can be regarded either as a pure mathematical programming or as an optimality criterion approach. It allows for a convergence control of the optimization process. Secondly, a proper linearization of the stress constraints is introduced by considering the stress components as linear combinations of the generalized displacements. The numerical applications presented in the paper show that both modifications of the optimization scheme lead to a significant improvement in the convergence properties.     

Neutral offspring controlling operators in genetic programming

Code bloat, one of the main issues of genetic programming (GP), slows down the search process, destroys program structures, and exhausts computer resources. To deal with these issues, two kinds of neutral offspring controlling operators are proposed—non-neutral offspring (NNO) operators and non-larger neutral offspring (NLNO) operators. Two GP benchmark problems—symbolic regression and 11-multiplexer—are used to test the new operators. Experimental results indicate that NLNO is able to confine code bloat significantly and improve performance simultaneously, which NNO cannot do.     

Functional search in economics using genetic programming

This paper discusses economic applications of a recently developed artificial intelligence technique-Koza's genetic programming (GP). GP is an evolutionary search method related to genetic algorithms. In GP, populations of potential solutions consist of executable computer algorithms, rather than coded strings. The paper provides an overview of how GP works, and illustrates with two applications: solving for the policy function in a simple optimal growth model, and estimating an unusual regression function. Results suggest that the GP search method can be an interesting and effective tool for economists.