Gene Expression Programming: A New Adaptive Algorithm for Solving Problems, Complex Systems, 2001.

Gene expression programming, a genotype/phenotype genetic algorithm (linear and ramified), is presented here for the first time as a new technique for the creation of computer programs. Gene expression programming uses character linear chromosomes composed of genes structurally organized in a head and a tail. The chromosomes function as a genome and are subjected to modification by means of mutation, transposition, root transposition, gene transposition, gene recombination, and one- and two-point recombination. The chromosomes encode expression trees which are the object of selection. The creation of these separate entities (genome and expression tree) with distinct functions allows the algorithm to perform with high efficiency that greatly surpasses existing adaptive techniques. The suite of problems chosen to illustrate the power and versatility of gene expression programming includes symbolic regression, sequence induction with and without constant creation, block stacking, cellular automata rules for the density-classification problem, and two problems of boolean concept learning: the 11-multiplexer and the GP rule problem.

html | pdf

Gene Expression Programming in Problem Solving, WSC6 tutorial, 2001.

In this work, the recently invented learning algorithm, gene expression programming, will be introduced focusing mainly on problem solving. Besides a simple introductory example, I chose two relatively complex test problems of symbolic regression. One of these problems was chosen in an attempt to shed some light on the question of constant creation in models discovered with learning algorithms and to provide a palpable measure of the accuracy of the evolved models and the efficiency of the algorithms. The chosen problems also show how gene expression programming is capable of modeling complex realities with great accuracy, allowing, at the same time, the extraction of knowledge from the evolved models.

html | pdf paper | pdf presentation

Mutation, Transposition, and Recombination: An Analysis of the Evolutionary Dynamics, FEA 2002.

Gene expression programming (GEP) uses mutation, transposition, and crossover to create variation. Although there exists a large body of work in genetic algorithms concerning the roles of mutation and recombination, these results not only do not apply to GEP due to the genotype/phenotype representation but also seem to contradict the GEP experience. Therefore, and given the diversity of GEP operators, it is convenient to develop some kind of understanding of their power. The aim of this work is to help develop such an understanding and to show the evolutionary dynamics and the transforming power of each genetic operator, with their advantages and limitations.

html | pdf

Discovery of the Boolean Functions to the Best Density-Classification Rules Using Gene Expression Programming, EuroGP 2002.

Cellular automata are idealized versions of massively parallel, decentralized computing systems capable of emergent behaviors. These complex behaviors result from the simultaneous execution of simple rules at multiple local sites. A widely studied behavior consists of correctly determining the density of an initial configuration, and both human and computer-written rules have been found that perform with high efficiency at this task. However, the two best rules for the density-classification task, Coevolution1 and Coevolution2, were discovered using a coevolutionary algorithm in which a genetic algorithm evolved the rules and, therefore, only the output bits of the rules are known. However, to understand why these and other rules perform so well and how the information is transmitted throughout the cellular automata, the Boolean expressions that orchestrate this behavior must be known. The results presented in this work are a contribution in that direction.

html | pdf

Gene Expression Programming in Problem Solving, in Soft Computing and Industry: Recent Applications, 2002.

Gene expression programming is a full fledged genotype/phenotype system that evolves computer programs encoded in linear chromosomes of fixed length. The structural organization of the linear chromosomes allows the unconstrained and fruitful (in the sense that no invalid phenotypes will follow) operation of important genetic operators such as mutation, transposition, and recombination as the expression of each gene always results in valid programs. Although simple, the genotype/phenotype system of gene expression programming is the first artificial genotype/phenotype system with a complex and sounding translation mechanism. Indeed, the interplay between genotype (chromosomes) and phenotype (expression trees) is at the core of the tremendous increase in performance observed in gene expression programming. Furthermore, gene expression programming shares with genetic programming the same kind of tree representation and, therefore, with GEP it is possible, for one thing, to retrace easily the steps undertaken by genetic programming and, for another, to explore easily new frontiers opened up by the crossing of the phenotype threshold. In this tutorial, the fundamental differences between gene expression programming and its predecessors, genetic algorithms and genetic programming, are briefly summarized so that the evolutionary advantages of gene expression programming could be better understood. The work proceeds with a detailed description of the main players in this new algorithm, focusing mainly on the interactions between them and how the simple yet revolutionary structure of the chromosomes allows the efficient, unconstrained exploration of the search space.

html | pdf

Combinatorial Optimization by Gene Expression Programming: Inversion Revisited, ASAI 2002.

Combinatorial optimization problems require combinatorial-specific search operators so that populations of candidate solutions can evolve efficiently. Indeed, several researchers created modifications to the basic genetic operators of mutation and recombination in order to create high performing combinatorial-specific operators. However, it is not known which operators perform better as no systematic comparisons have been done. In this work, a new algorithm that explores a new chromosomal organization based on multigene families is used. This new organization together with several combinatorial-specific search operators, namely, inversion, gene and sequence deletion/insertion, and restricted and generalized permutation, allow the algorithm to perform with high efficiency. The performance of the new algorithm is empirically compared on the 13- and 19-cities tour traveling salesperson problem, showing that the long abandoned inversion operator is by far the most efficient of the combinatorial operators. The efficiency and potentialities of the new algorithm are further demonstrated by solving a simple task assignment problem.

html | pdf

Function Finding and the Creation of Numerical Constants in Gene Expression Programming, WSC7, 2002.

Gene expression programming is a genotype/phenotype system that evolves computer programs of different sizes and shapes (the phenotype) encoded in linear chromosomes of fixed length (the genotype). The chromosomes are composed of multiple genes, each gene encoding a smaller sub-program. Furthermore, the structural and functional organization of the linear chromosomes allows the unconstrained operation of important genetic operators such as mutation, transposition, and recombination. In this work, three function finding problems, including a high dimensional time series prediction task, are analyzed in an attempt to discuss the question of constant creation in evolutionary computation by comparing two different approaches to the problem of constant creation. The first algorithm involves a facility to manipulate random numerical constants, whereas the second finds the numerical constants on its own or invents new ways of representing them. The results presented here show that evolutionary algorithms perform considerably worse if numerical constants are explicitly used.

html | pdf paper | pdf presentation

Analyzing the Founder Effect in Simulated Evolutionary Processes Using Gene Expression Programming, in Soft Computing Systems: Design, Management and Applications, 2002.

Gene expression programming is a genotype/phenotype system that evolves computer programs encoded in linear chromosomes of fixed length. The interplay between genotype (chromosomes) and phenotype (expression trees) is made possible by the structural and functional organization of the linear chromosomes. This organization allows the unconstrained operation of important genetic operators such as mutation, transposition, and recombination. Although simple, the genotype/phenotype system of gene expression programming can provide some insights into natural evolutionary processes. In this work the question of the initial diversity in evolving populations of computer programs is addressed by analyzing populations undergoing either mutation or recombination. The results presented here show that populations undergoing mutation recover practically undisturbed from evolutionary bottlenecks whereas populations undergoing recombination alone depend considerably on the size of the founder population and are unable to evolve efficiently if subjected to really tight bottlenecks.

html | pdf

Genetic Representation and Genetic Neutrality in Gene Expression Programming, Advances in Complex Systems, 2002.

The neutral theory of molecular evolution states that the accumulation of neutral mutations in the genome is fundamental for evolution to occur. The genetic representation of gene expression programming, an artificial genotype/phenotype system, not only allows the existence of non-coding regions in the genome where neutral mutations can accumulate but also allows the controlled manipulation of both the number and the extent of these non-coding regions. Therefore, gene expression programming is an ideal artificial system where the neutral theory of evolution can be tested in order to gain some insights into the workings of artificial evolutionary systems. The results presented in this work show beyond any doubt that the existence of neutral regions in the genome is fundamental for evolution to occur efficiently.

html | pdf

Function Finding and the Creation of Numerical Constants in Gene Expression Programming, in Advances in Soft Computing: Engineering Design and Manufacturing, 2003.

Gene expression programming is a genotype/phenotype system that evolves computer programs of different sizes and shapes (the phenotype) encoded in linear chromosomes of fixed length (the genotype). The chromosomes are composed of multiple genes, each gene encoding a smaller sub-program. Furthermore, the structural and functional organization of the linear chromosomes allows the unconstrained operation of important genetic operators such as mutation, transposition, and recombination. In this work, three function finding problems, including a high dimensional time series prediction task, are analyzed in an attempt to discuss the question of constant creation in evolutionary computation by comparing two different approaches to the problem of constant creation. The first algorithm involves a facility to manipulate random numerical constants, whereas the second finds the numerical constants on its own or invents new ways of representing them. The results presented here show that evolutionary algorithms perform considerably worse if numerical constants are explicitly used.

html | pdf

Gene Expression Programming and the Evolution of Computer Programs, in Recent Developments in Biologically Inspired Computing, 2004.

In this chapter an artificial problem solver inspired in natural genotype/phenotype systems – gene expression programming – is presented. As an introduction, the fundamental differences between gene expression programming and its predecessors, genetic algorithms and genetic programming, are briefly summarized so that the evolutionary advantages of gene expression programming are better understood. The work proceeds with a detailed description of the architecture of the main players of this new algorithm (chromosomes and expression trees), focusing mainly on the interactions between them and how the simple yet revolutionary structure of the chromosomes allows the efficient, unconstrained exploration of the search space. And finally, the chapter closes with an advanced application in which gene expression programming is used to evolve computer programs for diagnosing breast cancer.

html | pdf

Designing Neural Networks Using Gene Expression Programming, WSC9, 2004.

An artificial neural network with all its elements is a rather complex structure, not easily constructed and/or trained to perform a particular task. Consequently, several researchers used Genetic Algorithms to evolve partial aspects of neural networks, such as the weights, the thresholds, and the network architecture. Indeed, over the last decade many systems have been developed that perform total network induction. In this work it is shown how the chromosomes of Gene Expression Programming can be modified so that a complete neural network, including the architecture, the weights and thresholds, could be totally encoded in a linear chromosome. It is also shown how this chromosomal organization allows the training/adaptation of the network using the evolutionary mechanisms of selection and modification, thus providing an approach to the automatic design of neural networks. The workings and performance of this new algorithm are tested on the 6-multiplexer and on the classical exclusive-or problems.

html | pdf paper | pdf presentation

Automatically Defined Functions in Gene Expression Programming, in Genetic Systems Programming: Theory and Experiences, 2006.

In this chapter it is shown how Automatically Defined Functions are encoded in the genotype/phenotype system of Gene Expression Programming. As an introduction, the fundamental differences between Gene Expression Programming and its predecessors, Genetic Algorithms and Genetic Programming, are briefly summarized so that the evolutionary advantages of Gene Expression Programming are better understood. The introduction proceeds with a detailed description of the architecture of the main players of Gene Expression Programming (chromosomes and expression trees), focusing mainly on the interactions between them and how the simple, yet revolutionary, structure of the chromosomes allows the efficient, unconstrained exploration of the search space. The work proceeds with an introduction to Automatically Defined Functions and how they are implemented in Gene Expression Programming. Furthermore, the importance of Automatically Defined Functions in Evolutionary Computation is thoroughly analyzed by comparing the performance of sophisticated learning systems with Automatically Defined Functions with much simpler ones on the sextic polynomial problem.

html | pdf

Designing Neural Networks Using Gene Expression Programming, in Applied Soft Computing Technologies: The Challenge of Complexity, 2006.

An artificial neural network with all its elements is a rather complex structure, not easily constructed and/or trained to perform a particular task. Consequently, several researchers used genetic algorithms to evolve partial aspects of neural networks, such as the weights, the thresholds, and the network architecture. Indeed, over the last decade many systems have been developed that perform total network induction. In this work it is shown how the chromosomes of Gene Expression Programming can be modified so that a complete neural network, including the architecture, the weights and thresholds, could be totally encoded in a linear chromosome. It is also shown how this chromosomal organization allows the training/adaptation of the network using the evolutionary mechanisms of selection and modification, thus providing an approach to the automatic design of neural networks. The workings and performance of this new algorithm are tested on the 6-multiplexer and on the classical exclusive-or problems.

html | pdf

***