Search

"Better solutions faster" is the reality of the industrial modeling world, now more than ever. Efficiency requirements, market pressures, and ever changing data force us to use symbolic regression via genetic programming (GP) in a highly automated fashion. This is why we want our GP system to produce simple solutions of the highest possible quality with the lowest computational effort, and a high consistency in the results of independent GP runs. In this chapter, we show that genetic programming with a focus on ranking in combination with goal softening is a very powerful way to improve the efficiency and effectiveness of the evolutionary search. Our strategy consists of partial fitness evaluations of individuals on random subsets of the original data set, with a gradual increase in the subset size in consecutive generations. From a series of experiments performed on three test problems, we observed that those evolutions that started from the smallest subset sizes (10%) consistently led to results that are superior in terms of the goodness of fit, consistency between independent runs, and computational effort. Our experience indicates that solutions obtained using this approach are also less complex and more robust against over-fitting. We find that the near-optimal strategy of allocating computational budget over a GP run is to evenly distribute it over all generations. This implies that initially, more individuals can be evaluated using small subset sizes, promoting better exploration. Exploitation becomes more important towards the end of the run, when all individuals are evaluated using the full data set with correspondingly smaller population sizes. [ABSTRACT FROM AUTHOR]

Convergence is a necessary part of any successful GP run, but is also a great weakness due to material lost through the hemorrhage of genetic content through the established evolutionary dynamics. This chapter examines the phenomenon of convergence commonly observed in evolutionary systems before introducing a number of functionally distinct mechanisms are analysed and tested with respect to their ability to modulate the loss of potentially useful genetic content. Each of these methods use little or no explicit measurements to calculate diversity, and we show that they can have a dramatic effect on empirical performance of GP. [ABSTRACT FROM AUTHOR]

In 2003 the Center for Complex Studies (CSCS) of the University of Michigan organized the first Genetic Programming Theory and PracticeWorkshop to bring together practioners and theorists to bridge the gap between what practicioners were doing and what theorists were studying. In the introductory chapter of that volume the authors described Genetic Programming (GP) as "a young art that is just beginning to make its way into applications programming in a serious way" (Riolo and Worzel, 2004). Five years later GP is still a relatively young field, but it is rapidlymaturing and has produced a substantial track record of significant successes on large-scale, real world applications. However, these successes are still generally achieved by researchers with significant expert knowledge of GP; successful application of GP to large scale problems remains out of the reach of novices. The lack of a rigorous, detailed theory that is mature enough to guide the development of GP systems to solve specific problems contributes to this weakness. Thus, there remains an on-going need to both strengthen theory and to keep it closely tied to the practice of GP. The Genetic Programming Theory and Practice Workshops remain focused on this goal. [ABSTRACT FROM AUTHOR]

Numerous models of modern and ancient urban landscapes have been proposed. While is of interest to classify examples of early urban centers, it is even more interesting to model their origins. Since these emergent centers can be viewed not only as adaptations to their social and biological environments, but also as a source of further change. Thus, the meaning or semantics of an emergent center reflects the processes by which it was formed. In the study of one ancient center, Monte Albán, we have used data mining techniques to extract a large number of decision trees describing its settlement over time. Each decision tree specifies the values for selected attributes that can predict settlement activity in the terraces that comprise the site. However, not all terraces with those properties are occupied in the same way. This can result from economic or social reasons. Also, the variables employed do not always have the semantics needed to make sense of the distinction between occupied and unoccupied terraces. In this paper we focus on the latter reason. Here, GP and CA are used to add semantics to rules to make them more understandable to experts in the area. Future work will examine how GP can be used to integrate social and economic constraints in with the basic decision tree rules. [ABSTRACT FROM AUTHOR]

Quantitative models for stock selection and portfolio management face the challenge of determining the most efficacious factors, and how they interact, from large amounts of financial data. Genetic programming using "simple objective" fitness functions has been shown to be an effective technique for selecting factors and constructing multi-factor models for ranking stocks, but the resulting models can be somewhat unbalanced in satisfying the multiple objectives that portfolio managers seek: large excess returns that are consistent across time and the cross-sectional dimensions of the investment universe. In this study, we implement and evaluate three multi-objective algorithms to simultaneously optimize the information ratio, information coefficient, and intra-fractile hit rate of a portfolio. These algorithms — the constrained fitness function, sequential algorithm, and parallel algorithm — take widely different approaches to combine these different portfolio metrics. The results show that the multi-objective algorithms do produce well-balanced portfolio performance, with the constrained fitness function performing much better than the sequential and parallel multi-objective algorithms. Moreover, this algorithm generalizes to the held-out test data set much better than any of the single fitness algorithms. [ABSTRACT FROM AUTHOR]

Research has shown that evolutionary algorithms are a promising approach for training agents in heterogeneous multi-agent systems. However, research in evolving teams (or ensembles) has proven that common evolutionary approaches have subtle, but significant, weaknesses when it comes to balancing member performance and member cooperation. In addition, there are potentially significant scaling problems in applying evolutionary techniques to very large multi-agent systems. It is impractical to train each member of a large system individually, but purely homogeneous teams are inadequate. Previously we proposed Orthogonal Evolution of Teams (OET) as a novel approach to evolving teams that overcomes the weaknesses with balancing member performance and member cooperation. In this paper we test two basic evolutionary techniques and OET on the problem of evolving multi-agent systems, specifically a landscape exploration problem with heterogeneous agents, and examine the ability of the algorithms to evolve teams that are scalable in the number of team members. Our results confirm that the more traditional evolutionary approaches suffer the same weakness with multi-agent systems as they do with teams and that OET does compensate for these weaknesses. In addition, the three algorithms show distinctly different scaling behavior, with OET scaling significantly better than the two more traditional approaches. [ABSTRACT FROM AUTHOR]

Trust is a major issue with deploying empirical models in the real world since changes in the underlying system or use of the model in new regions of parameter space can produce (potentially dangerous) incorrect predictions. The trepidation involved with model usage can be mitigated by assembling ensembles of diverse models and using their consensus as a trust metric, since these models will be constrained to agree in the data region used for model development and also constrained to disagree outside that region. The problem is to define an appropriate model complexity (since the ensemble should consist of models of similar complexity), as well as to identify diverse models from the candidate model set. In this chapter we discuss strategies for the development and selection of robust models and model ensembles and demonstrate those strategies against industrial data sets. An important benefit of this approach is that all available data may be used in the model development rather than a partition into training, test and validation subsets. The result is constituent models are more accurate without risk of over-fitting, the ensemble predictions are more accurate and the ensemble predictions have a meaningful trust metric. [ABSTRACT FROM AUTHOR]

Genetic programming has been used by Koza and many others to design electrical, mechanical, and mechatronic systems, including systems with both active and passive components. This work has often required large population sizes (on the order of ten thousand) and millions of design evaluations to allow evolution of both the topology and parameters of interesting systems. For several years, the authors have studied the evolution of multi-domain engineering systems represented as bond graphs, a form that provides a unified representation of mechanical, electrical, hydraulic, pneumatic, thermal, and other systems in a uni-fied representation. Using this approach, called the Genetic Programming/Bond Graph (GPBG) approach, they have tried to evolve systems with perhaps tens of components, but looking at only 100,000 or fewer design candidates. The GPBG system uses much smaller population sizes, but seeks to maintain diverse search by using "sustained" evolutionary search processes such as the Hierarchical Fair Competition principle and its derivatives. It uses stochastic setting of parameter values (resistances, capacitances, etc.) as a means of evolving more robust designs. However, in past work, the GPBG system was able to model and simulate only passive components and simple (voltage or current, in the case of electrical systems) sources, which severely restricted the domain of problems it could address. Thus, this paper reports the first steps in enhancing the system to include active components. To date, only three models of a transistor and one model of an operational amplifier (op amp) are analyzed and implemented as two-port bond graph components. The analysis method and design strategy can be easily extended to other models or other active components or even multi-port components. This chapter describes design of an active analog low-pass filter with fifth-order Bessel characteristics. A passive filter with the same characteristics is also evolved with GPBG. Then the best designs emerging from each of these two procedures are compared. [The runs reported here are intended only to document that the analysis tools are working, and to begin study of the effects of stochasticity, but not to determine the power of the design procedure. The initial runs did not use HFC or structure fitness sharing, which will be included as soon as possible. Suitable problems will be tackled, and results with suitable numbers of replicates to allow drawing of statistically valid conclusions will be reported in this paper, to determine whether interesting circuits can be evolved more efficiently in this framework than using other GP approaches.] [ABSTRACT FROM AUTHOR]

This paper shows how aggressive reuse of known designs brings orders-ofmagnitude reduction in computational effort, and simultaneously resolves trust issues for synthesized designs, for genetic programming applied to automated structural design. Furthermore, it uses trustworthiness tradeoffs to handle addition of novelty in a trackable fashion. It uses a multi-objective algorithm with an age-layered population structure to avoid premature convergence. While the application here is analog circuit design, the methodology is general enough for many other problem domains. [ABSTRACT FROM AUTHOR]

Simple Genetic Programming (GP) is generally considered to lack the strong separation between genotype and phenotype found in natural evolution. In many cases, the genotype and the phenotype are considered identical in GP since the program representation does not undergo any modification prior to its encounter with "environment" in the form of inputs and a fitness function. However, this view overlooks a key fact: fitness in GP is determined without reference to the makeup of the individual programs but evolutionary changes occur in the structure and content of the individual without reference to its fitness. This creates a disconnect between "genetic recombination" and fitness similar to that in nature that can create unexpected effects during the evolution of a population and suggests an important dynamic that has not been thoroughly considered by the GP community. This paper describes some of the observed effects of this disconnect and studies some approaches for the estimating diversity of a population which could lead to a new way of modeling the dynamics of GP.We also speculate on the similarity of these effects and some recently studied aspects of natural evolution. [ABSTRACT FROM AUTHOR]

With the recent examples of the human-competitiveness of evolutionary design systems, it is not of interest to scale them up to produce more sophisticated designs. Here we argue that for computer-automated design systems to scale to producing more sophisticated results they must be able to produce designs with greater structure and organization. By "structure and organization" we mean the characteristics of modularity, reuse and hierarchy (MR&H), characteristics that are found both in man-made and natural designs. We claim that these characteristics are enabled by implementing the attributes of combination, control-flow and abstraction in the representation, and define metrics for measuring MR&H and define two measures of overall structure and organization by combining the measures of MR&H. To demonstrate the merit of our complexity measures, we use an evolutionary algorithm to evolve solutions to different sizes for a table design problem, and compare the structure and organization scores of the best tables against existing complexity measures. We find that our measures better correlate with the complexity of good designs than do others, which supports our claim that MR&H are important components of complexity. We also compare evolution using five representations with different combinations of MR&H, and find that the best designs are achieved when all three of these attributes are present. The results of this second set of experiments demonstrate that implementing representations with MR&H can greatly improve search performance. [ABSTRACT FROM AUTHOR]

This chapter represents a first attempt to characterize the fitness landscapes of real-life Genetic Programming applications by means of a predictive algebraic difficulty indicator. The indicator used is the Negative Slope Coefficient, whose efficacy has been recently empirically demonstrated on a large set of hand-tailored theoretical test functions and well known GP benchmarks. The real-life problems studied belong to the field of Biomedical applications and consist of automatically assessing amathematical relationship between a set of molecular descriptors from a given dataset of drugs and some important pharmacokinetic parameters. The parameters considered here are Human Oral Bioavailability, Median Oral Lethal Dose, and Plasma Protein Binding levels. The availability of good prediction tools for pharmacokinetics parameters like these is critical for optimizing the efficiency of therapies, maximizing medical success rate and minimizing toxic effects. The experimental results presented in this chapter show that the Negative Slope Coefficient seems to be a reasonable tool to characterize the difficulty of these problems, and can be used to choose the most effective Genetic Programming configuration (fitness function, representation, parameters' values) from a set of given ones. [ABSTRACT FROM AUTHOR]

An information—theoretic framework is presented for the development and analysis of the ensemble learning approach of genetic programming. As evolution proceeds, this approach suggests that the mutual information between the target and models should: (i) not decrease in the population; (ii) concentrate in fewer individuals; and (iii) be "distilled" from the inputs, eliminating excess entropy. Normalized information theoretic indices are developed to measure fitness and diversity of ensembles, without a priori knowledge of how the multiple constituent models might be composed into a single model. With the use of these indices for reproductive and survival selection, building blocks are less likely to be lost and more likely to be recombined. Price's Theorem is generalized to pair selection and rewritten to show key factors related to heritability and evolvability. Heritability of information should be stronger than that of error, improving evolvability. We support these arguments with simulations using a logic function benchmark and a time series application. For a chaotic time series prediction problem, for instance, the proposed approach avoids familiar difficulties (premature convergence, deception, poor scaling, and early loss of needed building blocks) with standard GP symbolic regression systems; informationbased fitness functions showed strong intergenerational correlations as required by Price's Theorem. [ABSTRACT FROM AUTHOR]

Genetic programming (GP) shows great promise for solving complex problems in human genetics. Unfortunately, many of these methods are not accessible to biologists. This is partly due to the complexity of the algorithms that limit their ready adoption and integration into an analysis or modeling paradigm that might otherwise only use univariate statistical methods. This is also partly due to the lack of user-friendly, open-source, platform-independent, and freely-available software packages that are designed to be used by biologists for routine analysis. It is our objective to develop, distribute and support a comprehensive software package that puts powerful GP methods for genetic analysis in the hands of geneticists. It is our working hypothesis that the most effective use of such a software package would result from interactive analysis by both a biologist and a computer scientist (i.e. human—human—computer interaction). We present here the design and implementation of an open-source software package called Symbolic Modeler (SyMod) that seeks to facilitate geneticist—bioinformaticist—computer interactions for problem solving in human genetics. We present and discuss the results of an application of SyMod to real data and discuss the challenges associated with delivering a user-friendly GP-based software package to the genetics community. [ABSTRACT FROM AUTHOR]

This chapter demonstrates a novel method combining particle swarm, differential evolution, and genetic programming to build a symbolic regression tool for large-scale, time-constrained regression-classification problems. In a previous paper we experimented with large scale symbolic regression. Here we describe in detail the enhancements and techniques employed to support largescale, time—constrained regression and classification. In order to achieve the level of performance reported here, of necessity, we borrowed a number of ideas from disparate schools of genetic programming and recombined them in ways not normally seen in the published literature. We discuss in some detail the construction of the fitness function, the use of abstract grammars to combine genetic programming with differential evolution and particle swarm agents, and the use of context-aware crossover. [ABSTRACT FROM AUTHOR]

One of the major challenges in an information-rich financial market is how effectively to derive an optimum investment solution among vast amounts of available information. The most efficacious combination of factors or information signals can be found by evaluating millions of possibilities, which is a task well beyond the scope of manual efforts. Given the limitations of the manual approach, factor combinations are typically linear. However, the linear combination of factors might be too simple to reflect market complexities and thus fully capture the predictive power of the factors. A genetic programming process can easily explore both linear and non-linear formulae. In addition, the ease of evaluation facilitates the consideration of broader factor candidates for a stock selection model. Based upon State Street Global Advisors (SSgA)'s previous research on using genetic programming techniques to develop quantitative investment strategies, we extend our application to develop stock selection mode ls in a large investable stock universe, the S&P 500 index. Two different fitness functions are designed to derive GP models that accommodate different investment objectives. First, we demonstrate that the GP process can generate a stock selection model for a low active risk investment style. Compared to a traditional model, the GP model has significantly enhanced future stock return ranking capability. Second, to suit an active investment style, we also use the GP process to generate a model that identifies the stocks with future returns lying in the fat tails of the return distribution. A portfolio constructed based on this model aims to aggressively generate the highest returns possible compared to an index following portfolio. Our tests show that the stock selection power of the GP models is statistically significant. Historical simulation results indicate that portfolios based on GP models outperform the benchmark and the portfolio based on the traditional model. Further, we demonstrate that GP models are more robust in accommodating various market regimes and have more consistent performance than the traditional model. [ABSTRACT FROM AUTHOR]

This chapter gives a narrative of the problems we encountered using genetic programming to build a symbolic regression tool for large-scale, time-constrained regression problems. It describes in detail the problems encountered, the commonly held beliefs challenged, and the techniques required to achieve reasonable performance with large-scale, time-constrained regression. We discuss in some detail the selection of the compilation tools, the construction of the fitness function, the chosen system grammar (including internal functions and operators), and the chosen system architecture (including multiple island populations). Furthermore in order to achieve the level of performance reported here, of necessity, we borrowed a number of ideas from disparate schools of genetic programming and recombined them in ways not normally seen in the published literature. [ABSTRACT FROM AUTHOR]

This chapter describes context-aware crossover. This is an improved crossover technique for GP which always swaps subtrees into their best possible context in a parent. We show that this style of crossover is considerably more constructive than the standard method, and present several experiments to demonstrate how it operates, and how well it performs, before applying the technique to a real world application, the Blood Flow Modeling Problem. [ABSTRACT FROM AUTHOR]

We focus on the halting probability and the number of instructions executed by programs that halt for Turing-complete register based machines. The former represents the fraction of programs which provide useful results in a machine code genetic programming system. The latter determines run time and whether or not the distribution of program functionality has reached a fixed-point. We describe a Markov chain model of program execution and halting which accurately fits empirical data allowing us to efficiently estimate the halting probability and the numbers of instructions executed for programs including millions of instructions. We also discuss how this model can be applied to improve GP practice. [ABSTRACT FROM AUTHOR]

Phase transitions occur in computational, as well as thermodynamic systems. Of particular interest is the possibility that phase transitions occur as a consequence of GP search. If this were so, it would allow for a statistical mechanics approach and quantitative comparisons of GP with a broad variety of rigorously described systems. This chapter summarizes our research group's work in this area and describes a case study that illustrates what is involved in establishing the existence of phase transitions in GP search. [ABSTRACT FROM AUTHOR]

We discuss the difficulties of circuit sizing and describe manual and automatic approaches to it. These approaches make use of blackbox optimization techniques such as evolutionary algorithms or convex optimization techniques such as geometric programming. Geometric programming requires posynomial expressions for a circuit's performance measurements. We show how a genetic algorithm can be exploited to evolve a posynomial expression (i.e. model) of transistor (i.e. mosfet) behavior more accurately than statistical techniques in the literature. [ABSTRACT FROM AUTHOR]

A possible goal in robust design of dynamic systems is to find a system topology under which the sensitivity of performance to the values of component parameters is minimized. This can provide robust performance in the face of environmental change (e.g., resistance variation with temperature) and/or manufacturing-induced variability in parameter values. In some cases, a topology that is relatively insensitive to parameter variation may allow use of less expensive (looser tolerance) components. Cost of components, in some instances, also depends on whether "standard-sized" components may be used or custom values are required. This is true whether the components are electrical components, mechanical fasteners, or hydraulic fittings. However, using only standard-sized or preferred-value components introduces an additional design constraint. This chapter uses genetic programming to develop bond graphs specifying component topology and parameter values for an example task, designing a passive analog low-pass filter with fifth-order Bessel characteristics. It explores three alternative design approaches. The first uses "standard" GP and evolves designs in which components can take on arbitrary values (i.e., custom design). The second approach adds random noise to each parameter; then, at the end of evolution, for the best design found, it "snaps" its parameter values to a small (component-specific) set of "standard" values. The third approach uses only the small set of allowable standard values throughout the evolutionary process, evaluating each design after addition of noise to each standard parameter value. Then the best designs emerging from each of these three procedures are compared for robustness to parameter variation, evaluating each of them with random perturbations of their parameters. Results indicated that, the third method produced the most robust designs, and the second method was better than the first. [ABSTRACT FROM AUTHOR]

History matching is the process of updating a petroleum reservoir model using production data. It is a required step before a reservoir model is accepted for forecasting production. The process is normally carried out by flow simulation, which is very time-consuming. As a result, only a small number of simulation runs are conducted and the history matching results are normally unsatisfactory. In this work, we introduce a methodology using genetic programming (GP) to construct a proxy for reservoir simulator. Acting as a surrogate for the computer simulator, the "cheap" GP proxy can evaluate a large number (millions) of reservoir models within a very short time frame. Collectively, the identified good-matching reservoir models provide us with comprehensive information about the reservoir. Moreover, we can use these models to forecast future production, which is closer to the reality than the forecasts derived from a small number of computer simulation runs. We have applied the proposed technique to a West African oil field that has complex geology. The results show that GP is able to deliver high quality proxies. Meanwhile, important information about the reservoirs was revealed from the study. Overall, the project has successfully achieved the goal of improving the quality of history matuching results without increasing the number of reservoir simulation runs. This result suggests this novel history matching approach might be effective for other reservoirs with complex geology or a significant amount of production data. [ABSTRACT FROM AUTHOR]

The ParetoGP algorithm which adopts a multi-objective optimization approach to balancing expression complexity and accuracy has proven to have significant impact on symbolic regression of industrial data due to its improvement in speed and quality of model development as well as user model selection, (Smits and Kotanchek, 2004), (Smits et al., 2005), (Castillo et al., 2006). In this chapter, we explore a range of topics related to exploiting the Pareto paradigm. First we describe and explore the strengths and weaknesses of the ClassicGPand Pareto-Front GP variants for symbolic regression as well as touch on related algorithms. Next, we show a derivation for the selection intensity of tournament selection with multiple winners (albeit, in a single-objective case). We then extend classical tournament and elite selection strategies into a multi-objective framework which allows classical GP schemes to be readily Pareto-aware. Finally, we introduce the latest extension of the Pareto paradigm which is the melding with ordinal optimization. It appears that ordinal optimization will provide a theoretical foundation to guide algorithm design. Application of these insights has already produced at least a four-fold improvement in the ParetoGP performance for a suite of test problems. [ABSTRACT FROM AUTHOR]

Symbolic regression based on Pareto-Front GP is a very effective approach for generating high-performance parsimonious empirical models acceptable for industrial applications. The chapter addresses the issue of finding the optimal parameter settings of Pareto-Front GP which direct the simulated evolution toward simple models with acceptable prediction error. A generic methodology based on statistical design of experiments is proposed. It includes determination of the number of replicates by half width confidence intervals, determination of the significant factors by fractional factorial design of experiments, approaching the optimum by steepest ascent/descent, and local exploration around the optimum by Box Behnken design of experiments. The results from implementing the proposed methodology to different types of industrial data sets show that the statistically significant factors are the number of cascades, the number of generations, and the population size. The optimal values for the three parameters have been defined based on second order regression models with R2 hig herthan 0.97 for small, medium, and large-sized data sets. The robustness of the optimal parameters toward the types of data sets was explored and a robust setting for the three significant parameters was obtained. It reduces the calculation time by 30% to 50% without statistically significant reduction in the mean response. [ABSTRACT FROM AUTHOR]

This paper reviews the recent use of genetic programming to automatically synthesize human-competitive designs of complex structures in six engineering domains, namely analog electrical circuits, optical lens systems, controllers, antennas, mechanical systems, and quantum computing circuits. First, the paper identifies common features observed in the human-competitive results produced by genetic programming in the six domains and suggests possible explanations for the observed similarities. Second, the paper identifies the characteristics that make a particular domain amenable to the application of genetic programming for the automatic synthesis of designs. Third, the paper discusses certain domain-specific adjustments in technique that may increase the efficiency of the automated process in a particular domain. Fourth, the paper discusses several technique issues that have arisen in more than one domain. [ABSTRACT FROM AUTHOR]

Fitness models are used to reduce evaluation frequency and cost. There are three fundamental challenges faced when using fitness models: (1) the model learning investment, (2) the model level of approximation, and (3) the lack of convergence to optima. We propose a coevolutionary algorithm to resolve these problems automatically during evolution. We discuss applications of this approach and measure its impact in symbolic regression. Results show coevolution yields significant improvement in performance over other algorithms and different fitness modeling approaches. Finally we apply coevolution to interactive evolution of pen stroke drawings where no true fitness function is known. These results demonstrate coevolution's ability to infer a fitness landscape of a user's preference while minimizing user interaction. [ABSTRACT FROM AUTHOR]

We present new results on the evolution of tag-mediated cooperation, demonstrating that the use of multidimensional tags can enhance the emergence of high levels of cooperation. We discuss these results in the context of prior cases in which work on the evolution of cooperation has led to practical techniques for improving the problem-solving performance of genetic programming systems. [ABSTRACT FROM AUTHOR]

Several general evolutionary approaches have proven quite successful at evolving teams (or ensembles) consisting of cooperating team members. However, in this paper we demonstrate that the existing approaches have subtle, but significant, weaknesses. We then present a novel class of evolutionary algorithms (orthogonal evolution of teams (OET)) for evolving teams that overcomes these weaknesses. Specifically it is shown that a typical algorithm from the OET class of algorithms successfully generates team members that have fitnesses comparable to those evolved independently and that have inversely correlated errors, which maximizes the teams' overall performance. Finally it is shown that the OET approach performs significantly better than the standard evolutionary approaches. [ABSTRACT FROM AUTHOR]

Biological sequence analysis presents interesting challenges for machine learning. With an important problem — the recognition of functional target sites for microRNA molecules — as an example, we show how multiple genetic programming classifiers improve accuracy and stability. Moving from single classifiers to bagging and boosting with crossvalidation and parameter optimization requires more computing power. A special-purpose search processor for fitness evaluation renders boosted genetic programming practical for our purposes. [ABSTRACT FROM AUTHOR]

In this chapter, we show the real-world applications of genetic programming (GP) to bioinformatics and robotics. In the bioinformatics application, we propose majority voting technique for the prediction of the class of a test sample. In the application to robotics, we use GP to generate the motion sequences of humanoid robots. We introduce an integrated approach, i.e., the combination of GP and reinforcement learning, to design the desirable motions. The effectiveness of our proposed approaches is demonstrated by performing experiments with real data, i.e., classifying real micro-array gene expression profiles and controlling real humanoid robots. [ABSTRACT FROM AUTHOR]

In certain problem domains, "The Curse of Dimensionality" (Hastie et al., 2001) is well known. Also known as the problem of "High P and Low N" where the number of parameters far exceeds the number of samples to learn from, we describe our methods for making the most of limited samples in producing reasonably general classification rules from data with a larger number of parameters. We discuss the application of this approach in classifying mesothelioma samples from baseline data according to their time to recurrence. In this case there are 12,625 inputs for each sample but only 19 samples to learn from. We reflect on the theoretical implications of the behavior of GP in these extreme cases and speculate on the nature of generality. [ABSTRACT FROM AUTHOR]

Human genetics is undergoing an information explosion. The availability of chip-based technology facilitates the measurement of thousands of DNA sequence variation from across the human genome. The challenge is to sift through these high-dimensional datasets to identify combinations of interacting DNA sequence variations that are predictive of common diseases. The goal of this study is to develop and evaluate a genetic programming (GP) approach to attribute selection and classification in this domain. We simulated genetic datasets of varying size in which the disease model consists of two interacting DNA sequence variations that exhibit no independent effects on class (i.e. epistasis). We show that GP is no better than a simple random search when classification accuracy is used as the fitness function. We then show that including pre-processed estimates of attribute quality using Tuned ReliefF (TuRF) in a multi-objective fitness function that also includes accuracy significantly improves the performance of GP over that of random search. This study demonstrates that GP may be a useful computational discovery tool in this domain. This study raises important questions about the general utility of GP for these types of problems, the importance of data preprocessing, the ideal functional form of the fitness function, and the importance of expert knowledge. We anticipate this study will provide an important baseline for future studies investigating the usefulness of GP as a general computational discovery tool for large-scale genetic studies. [ABSTRACT FROM AUTHOR]

The talks and discussion during the fourth annual Genetic Programming Theory and Practice workshop (GPTPIV), held in Ann Arbor, Michigan, from May 11 to May 13 2006, suggest that the development of GP has crossed a watershed, from an emphasis on exploratory research to focusing on tackling large, real-world applications. Organized by the Center for the Study of Complex Systems (CSCS) of the University of Michigan and supported by Third Millenium, State Street Global Advisors (SSgA), Christopher T. May of Red Queen Capital Management, Michael Korn, and the Biocomputing and Developmental Systems Group of the University of Limerick, the goal of the workshop is to bridge the gap between theory and practice. Paraphrasing the introduction to the first workshop, the goal is "to allow theory to inform practice and practice to test theory." To that end, the GPTP workshop again assembled a group of leading theoreticians and practitioners to present and discuss their recent work. [ABSTRACT FROM AUTHOR]