Search

Self-Modifying Cartesian Genetic Programming (SMCGP) is a general purpose, graph-based, developmental form of Cartesian Genetic Programming. In addition to the usual computational functions found in CGP, SMCGP includes functions that can modify the evolved program at run time. This means that programs can be iterated to produce an infinite sequence of phenotypes from a single evolved genotype. Here, we discuss the results of using SMCGP on a variety of different problems, and see that SMCGP is able to solve tasks that require scalability and plasticity. We demonstrate how SMCGP is able to produce results that would be impossible for conventional, static Genetic Programming techniques. [ABSTRACT FROM AUTHOR]

A developmental co-evolutionary genetic programming approach (PAM DGP) and a standard linear genetic programming (LGP) stock trading systemare applied to a number of stocks across market sectors. Both GP techniques were found to be robust to market fluctuations and reactive to opportunities associated with stock price rise and fall, with PAMDGP generating notably greater profit in some stock trend scenarios. Both algorithms were very accurate at buying to achieve profit and selling to protect assets, while exhibiting bothmoderate trading activity and the ability to maximize or minimize investment as appropriate. The content of the trading rules produced by both algorithms are also examined in relation to stock price trend scenarios. [ABSTRACT FROM AUTHOR]

A developmental co-evolutionary genetic programming approach (PAM DGP) is compared to a standard linear genetic programming (LGP) implementation for trading of stocks in the technology sector. Both interday and intraday data for these stocks were analyzed, where both implementations were found to be impressively robust to market fluctuations while reacting efficiently to opportunities for profit. PAM DGP proved slightly more reactive to market changes compared to LGP for intraday data, where the converse held true for interday data. Both implementations had very impressive accuracy in choosing both profitable buy trades and sells that prevented losses for both interday and intraday stock data. These successful trades occurred in the context of moderately active trading for interday prices and lower levels of trading for intraday prices. [ABSTRACT FROM AUTHOR]

IEEE 802.16, also known as WiMAX, is a new wireless access technology for currently increasing demand of wireless high-speed broadband service. Efficient and effective deployment of such a network to service an area of users with certain traffic demands is an important network planning problem. In this article, we resort to a Genetic Algorithm in order to yield good approximation solutions. In our method, individual representation and genetic variation operations are specifically designed to incorporate the feature of this application problem. Moreover, an adaptive population size approach inspired by neutral theory in molecular biology is applied in our algorithm to enhance its search ability. Simulation results show that our algorithm is fairly effective and robust to different scenarios of the network planning problem. By comparing to a conventional fixed population size scheme, our method is further verified to be able to accelerate the search process. [ABSTRACT FROM AUTHOR]

We discuss how to use a Genetic Regulatory Network as an evolutionary representation to solve a typical GP reinforcement problem, the pole balancing. The network is a modified version of an Artificial Regulatory Network proposed a few years ago, and the task could be solved only by finding a proper way of connecting inputs and outputs to the network. We show that the representation is able to generalize well over the problem domain, and discuss the performance of different models of this kind. [ABSTRACT FROM AUTHOR]

Population size is a critical parameter that affects the performance of an Evolutionary Computation model. A variable population size scheme is considered potentially beneficial to improve the quality of solutions and to accelerate fitness progression. In this contribution, we discuss the relationship between population size and the rate of evolution in Genetic Programming. We distinguish between the rate of fitness progression and the rate of genetic substitutions, which capture two different aspects of a GP evolutionary process. We suggest a new indicator for population size adjustment during an evolutionary process by measuring the rate of genetic substitutions. This provides a separate feedback channel for evolutionary process control, derived from concepts of population genetics. We observe that such a strategy can stabilize the rate of genetic substitutions and effectively accelerate fitness progression. A test with the Mackey-Glass time series prediction verifies our observations. [ABSTRACT FROM AUTHOR]

Self Modifying CGP (SMCGP) is a developmental form of Cartesian Genetic Programming(CGP). It is able to modify its own phenotype during execution of the evolved program. This is done by the inclusion of modification operators in the function set. Here we present the use of the technique on several different sequence generation and regression problems. [ABSTRACT FROM AUTHOR]

A developmental co-evolutionary genetic programming approach (PAM DGP) is compared to a standard linear genetic programming (LGP) implementation for trading of stocks across market sectors. Both implementations were found to be impressively robust to market fluctuations while reacting efficiently to opportunities for profit, where PAM DGP proved slightly more reactive to market changes than LGP. PAM DGP outperformed, or was competitive with, LGP for all stocks tested. Both implementations had very impressive accuracy in choosing both profitable buy trades and sells that prevented losses, where this occurred in the context of moderately active trading for all stocks. The algorithms also appropriately maintained maximal investment in order to profit from sustained market upswings. [ABSTRACT FROM AUTHOR]

There is growing interest in the use of analogies of biological development for problem solving in computer science. Nature is extremely intricate when compared to human designs, and incorporates features such as the ability to scale, adapt and self-repair that could be usefully incorporated into human-designed artifacts. In this chapter, we discuss how the metaphor of biological development can be used in artificial systems and highlight some of the challenges of this emerging field. [ABSTRACT FROM AUTHOR]

Measuring fitness progression using numeric quantification in an Evolutionary Computation (EC) system may not be sufficient to capture the rate of evolution precisely. In this paper, we define the rate of evolution Re in an EC system based on the rate of efficient genetic variations being accepted by the EC population. This definition is motivated by the measurement of ˵amino acid to synonymous substitution ratio″ ka/ks in biology, which has been widely accepted to measure the rate of gene sequence evolution. Experimental applications to investigate the effects of four major configuration parameters on our rate of evolution measurement show that Re well reflects how evolution proceeds underneath fitness development and provides some insights into the effectiveness of EC parameters in evolution acceleration. [ABSTRACT FROM AUTHOR]

The paper describes a new approach, based on cell biology, to the uncapacitated examination timetabling problem. This approach begins with a single cell which is developed into a fully grown organism through the processes of cell division, cell interaction and cell migration. The mature organism represents a solution to the particular timetabling problem. The paper discusses the performance of this method on the Carter set of benchmark problems. This data set is comprised of real-world timetabling problems. The results obtained using the developmental approach are compared to that obtained by other biologically inspired algorithms applied to the same set of benchmarks and the best results cited in the literature for the Carter data set. [ABSTRACT FROM AUTHOR]

Mackey-Glass chaotic time series prediction and nuclear protein classification show the feasibility of evaluating genetic programming populations directly on parallel consumer gaming graphics processing units. Using a Linux KDE computer equipped with an nVidia GeForce 8800 GTX graphics processing unit card the C++ SPMD interpretter evolves programs at Giga GP operations per second (895 million GPops). We use the RapidMind general processing on GPU (GPGPU) framework to evaluate an entire population of a quarter of a million individual programs on a non-trivial problem in 4 seconds. An efficient reverse polish notation (RPN) tree based GP is given. [ABSTRACT FROM AUTHOR]

Two prominent genetic programming approaches are the graph-based Cartesian Genetic Programming (CGP) and Linear Genetic Programming (LGP). Recently, a formal algorithm for constructing a directed acyclic graph (DAG) from a classical LGP instruction sequence has been established. Given graph-based LGP and traditional CGP, this paper investigates the similarities and differences between the two implementations, and establishes that the significant difference between them is each algorithm΄s means of restricting inter-connectivity of nodes. The work then goes on to compare the performance of two representations each (with varied connectivity) of LGP and CGP to a directed cyclic graph (DCG) GP with no connectivity restrictions on a medical classification and regression benchmark. [ABSTRACT FROM AUTHOR]

Research in the field of examination timetabling has developed in two directions. The first looks at applying various methodologies to induce examination timetables. The second takes an indirect approach to the problem and examines the generation of heuristics or combinations of heuristics, i.e. hyper-heuristics, to be used in the construction of examination timetables. The study presented in this paper focuses on the latter area. This paper presents a first attempt at using genetic programming for the evolution of hyper-heuristics for the uncapacitated examination timetabling problem. The system has been tested on 9 benchmark examination timetabling problems. Clash-free timetables were found for all 9 nine problems. Furthermore, the performance of the genetic programming system is comparable to, and in a number of cases has produced better quality timetables, than other search algorithms used to evolve hyper-heuristics for this set of problems. [ABSTRACT FROM AUTHOR]

This chapter applies linear GP to the evolution of cooperative teams to several prediction problems. Different linear methods for combining outputs of the team programs are compared. These include hybrid approaches where [1] a neural network is used to optimize the weights of programs in a team for a common decision and [2] a real-numbered vector (the representation of evolution strategies) of weights is evolved in tandem with each team. The cooperative team approach results in an improved training and generalization performance compared to the standard GP method. [ABSTRACT FROM AUTHOR]

In this chapter we will investigate structural and semantic distance metrics for linear genetic programs. A causal connection between changes of genotypes and of phenotypes form a necessary condition for being able to control differences between genetic programs. The two objectives of this chapter are to show [1] how distance information between individuals can be used to control structural diversity of individuals and [2] how variation distance on effective code can be controlled probabilistically with different linear genetic operators. [ABSTRACT FROM AUTHOR]

This chapter brings together theories about neutral variations and code growth in genetic programming. We argue that neutral variations are important for the growth of code in GP runs. Other existing theories about code growth are verified for linear GP and are partly reevaluated from a different perspective. In evolutionary computation neutral variations are argued to explore flat regions of the fitness landscape while non-neutral variations exploit regions with gradient information. We investigate the influence of different variation effects on growth of code and the prediction quality for different kinds of variation operators. It is well known that a high proportion of neutral code (introns) in genetic programs may increase the probability for variations to be neutral. But which type of variation creates the introns in the first place? For linear GP with minimum mutation, step size results show that neutral variations almost exclusively represent a cause for (rather than a result of) the emergence and growth of intron code. This part of the chapter is a continuation of our earlier studies [25]. We also examine different linear genetic operators regarding an implicit length bias. In contrast to an explicit bias, implicit bias does not result from the dynamics of the operator alone, but requires the existence of a fitness pressure. We will close this chapter with a discussion about how to control code growth in linear GP. Different approaches are reviewed including variation-based methods and selection-based methods. Both may be applied specifically to effective code and/or to noneffective code. [ABSTRACT FROM AUTHOR]

In this chapter a comparison between the linear representation and the traditional tree representation of genetic programming is performed. The comparison examines prediction performance and model size based on two collections of benchmark problems that have been composed of artificial test problems and of real-world applications from bioinformatics, respectively. Both linear GP and tree-based GP use crossover for macro variations. Additionally, we apply the linear GP variant from Section 6.2.3 which works exclusively with (effective) instruction mutations to compare its performance for a larger number of problems. But first of all, we introduce tree-based GP in some further detail. [ABSTRACT FROM AUTHOR]

In the previous two chapters parameters have been analyzed that are closely related to one of the variation operators. In this chapter we analyze influences of more general system parameters that are relevant in linear genetic programming. In particular, the number of registers, the number of constants, the population size, and the maximum program length will be studied. Additionally, we compare different initialization techniques for linear genetic programs. Test problems are again the approximation problem mexican hat and the classification problem spiral introduced in Section 5.8.1. [ABSTRACT FROM AUTHOR]

Crossover has been the traditional operator in tree-based GP for varying the content and size of programs. In this chapter we systematically introduce crossover and mutation operators for the linear program representation and compare their influence on prediction performance and the complexity of evolved solutions. We can distinguish between two different levels of variation done by these operators. Macro variations operate on the instruction level (or macro level). In this perspective, an instruction represents the smallest unit. Micro variations operate on the level of instruction components (micro level) and manipulate registers, operators, and constants. Only macro variations influence program growth. Macro variations may be further divided into segment variations and instruction variations, depending on whether a contiguous subsequence of instructions or only one instruction is subjected to change. Only segment variations will form the subject of this chapter. Other variations will be treated in a subsequent chapter We will see that the performance of a variation operator strongly depends on its maximum (and average) step size on the symbolic program structure, on its influence on code growth, and on the proportion of effective and neutral variations. Among other things, macro mutations with minimum step size will turn out to be most effective provided that a change of the structurally effective code can be guaranteed. We will also investigate how linear genetic programs can be manipulated more efficiently through respecting their functional structure. [ABSTRACT FROM AUTHOR]

The experimental results from Chapter 5 have confirmed two important assumptions. First, when using recombination best results were obtained with a relatively low limit to segment length. Second, segment recombination has not been found to be more powerful than segment mutation. Both aspects motivate the use of mutations that affect one instruction only. The following considerations try to point out why linear programs in particular are likely to be served better by using only minimal mutation operations. [ABSTRACT FROM AUTHOR]

We reported on LGP applied to a number of medical classification tasks. It was demonstrated that, on average, genetic programming performs competitive to RPROP neural networks with respect to the generalization performance. The runtime performance of genetic programming becomes especially important for time-critical applications or when operating with large data sets from real-world domains like medicine. Two techniques were presented that reduced the computational costs significantly. First, the elimination of noneffective code from linear genetic programs resulted in an average decrease in runtime of about a factor of 5 here. Second, by using a demetic population in combination with an elitist migration strategy the number of effective generations was reduced by a factor of about 3, without decreasing the performance of the evolutionary algorithm. [ABSTRACT FROM AUTHOR]

In the first instance linear genetic programming has been introduced for the benefit of shorter execution time. Genetic programs written as binary machine code do not have to pass through a time-consuming interpre- tation step (see Section 2.2). In this chapter we investigate other, more general features of the linear representation.One basic difference to a tree representation is the emergence of unused code parts in linear genetic pro- grams that are independent of program semantics. Another fundamental difference is that the data flow in a linear genetic program has a directed graph structure that is more general than a tree. [ABSTRACT FROM AUTHOR]

In this chapter linear genetic programming (LGP) will be explored in further detail. The basis of the specific linear GP variant we want to investigate in this book will be described, in particular the programming language used for evolution, the representation of individuals, and the specific evolutionary algorithm employed. This will form the core of our LGP system, while fundamental concepts of linear GP will also be discussed, including various forms of program execution. Linear GP operates with imperative programs. All discussions and experiments in this book are conducted independently from a special type of programming language or processor architecture. Even though genetic programs are interpreted and partly noted in the high-level language C, the applied programming concepts exist principally in or may be translated into most modern imperative programming languages, down to the level of machine languages. [ABSTRACT FROM AUTHOR]

Natural evolution has always been a source of inspiration for science and engineering. “Endless forms, most beautiful”, as Darwin put it. Who would not marvel at the unbelievable variety of life, who would not admire its complexity? A process that could bring about such wonders in nature, couldn't we glean from it some tricks that would be useful for our own activities? Couldn't we learn some methods for the design of other systems, for instance, machines and their behaviors? It is along these lines of thought that algorithms where conceived, able to catch aspects of natural evolution. [ABSTRACT FROM AUTHOR]

We introduce a genetic programming (GP) approach for evolving genetic networks that demonstrate desired dynamics when simulated as a discrete stochastic process. Our representation of genetic networks is based on a biochemical reaction model including key elements such as transcription, translation and post-translational modifications. The stochastic, reaction-based GP system is similar but not identical with algorithmic chemistries. We evolved genetic networks with noisy oscillatory dynamics. The results show the practicality of evolving particular dynamics in gene regulatory networks when modelled with intrinsic noise. [ABSTRACT FROM AUTHOR]

Genetic Programming has been slow at realizing other programming paradigms than conventional, deterministic, sequential von-Neumann type algorithms. In this contribution we discuss a new method of execution of programs introduced recently: Algorithmic Chemistries. Therein, register machine instructions are executed in a non-deterministic order, following a probability distribution. Program behavior is thus highly dependent on frequency of instructions and connectivity between registers. Here we demonstrate the performance of GP on evolving solutions to a parity problem in a system of this type. [ABSTRACT FROM AUTHOR]

Schemata and the schema theorem, although criticised, are often used to explain why genetic algorithms (GAs) work. A considerable research effort has been produced recently to extend the GA schema theory to Genetic Programming (GP). In this paper we review the main results available to date in the theory of schemata for GP and some recent experimental work on schemata. [ABSTRACT FROM AUTHOR]

Our purpose is to enhance performance of Genetic Programming (GP) search. For this, we have been develop a homogeneous system allowing to construct simultaneously a solution and sub-parts of it within a GP framework. This problem is a crucial point in GP research lately since this is intimately linked with building blocks existence problem. Thus, in this paper, we present an "on-going" work concerning DLGP — Dynamic Lattice Genetic Programming— a new GP system to evolve shared specific modules using a hierarchical cooperative coevolution paradigm. This scheme attempts to improve efficiency of GP by taking one's inspiration of organization of natural entities, especially the emergence of complexity. In particular, DLGP does not require heuristic knowledge. Different credit assignment strategies are presented to compute modules fitness. DLGP approach attempts to reduce the global depth of a tree-solution and avoids multiple searches of the same sub-components. Moreover modules induction improves "readability" of GP outputs. In particular, local evolutionary process is applied on the different set of subroutines in order to do converged each population toward a specific ability which remains at disposal of higher level subroutines. Problem decomposition and sub-tasks distribution is emergent through the lattice. [ABSTRACT FROM AUTHOR]

In nature, variation mechanisms have evolved that permit increasingly rapid and complex adaptations to the environment. Similarly, it may be observed that evolutionary learning systems are adopting increasingly sophisticated variation mechanisms. In this paper, we draw parallels between the adaptation mechanisms in nature and those in evolutionary learning systems. Extrapolating this trend, we indicate an interesting new direction for future work on evolutionary learning systems. [ABSTRACT FROM AUTHOR]