Genetic programming for prediction and control

The relatively new field of genetic programming has received a lot of attention during the last few years. This is because of its potential for generating functions which are able to solve specific problems. This paper begins with an extensive overview of the field, highlighting its power and limitations and providing practical tips and techniques for the successful application of genetic programming in general domains. Following this, emphasis is placed on the application of genetic programming to prediction and control. These two domains are of extreme importance in many disciplines. Results are presented for an oral cancer prediction task and a satellite attitude control problem. Finally, the paper discusses how the convergence of genetic programming can be significantly speeded up through bulk synchronous model parallelisation.     

Genetic programming for computational pharmacokinetics in drug discovery and development

The success of a drug treatment is strongly correlated with the ability of a molecule to reach its target in the patient’s organism without inducing toxic effects. Moreover the reduction of cost and time associated with drug discovery and development is becoming a crucial requirement for pharmaceutical industry. Therefore computational methods allowing reliable predictions of newly synthesized compounds properties are of outmost relevance. In this paper we discuss the role of genetic programming in predictive pharmacokinetics, considering the estimation of adsorption, distribution, metabolism, excretion and toxicity processes (ADMET) that a drug undergoes into the patient’s organism. We compare genetic programming with other well known machine learning techniques according to their ability to predict oral bioavailability (%F), median oral lethal dose (LD50) and plasma-protein binding levels (%PPB). Since these parameters respectively characterize the percentage of initial drug dose that effectively reaches the systemic blood circulation, the harmful effects and the distribution into the organism of a drug, they are essential for the selection of potentially good molecules. Our results suggest that genetic programming is a valuable technique for predicting pharmacokinetics parameters, both from the point of view of the accuracy and of the generalization ability.

Genetic based fuzzy goal programming for multiobjective chance constrained programming problems with continuous random variables

Solution procedure consisting of fuzzy goal programming and stochastic simulation-based genetic algorithm is presented, in this article, to solve multiobjective chance constrained programming problems with continuous random variables in the objective functions and in chance constraints. The fuzzy goal programming formulation of the problem is developed first using the stochastic simulation-based genetic algorithm. Without deriving the deterministic equivalent, chance constraints are used within the genetic process and their feasibilities are checked by the stochastic simulation technique. The problem is then reduced to an ordinary chance constrained programming problem. Again using the stochastic simulation-based genetic algorithm, the highest membership value of each of the membership goal is achieved and thereby the most satisfactory solution is obtained. The proposed procedure is illustrated by a numerical example.     

Epigenetic programming: Genetic programming incorporating epigenetic learning through modification of histones

We present the results of our work in simulating the recently discovered findings in molecular biology regarding the significant role which histones play in regulating the gene expression in eukaryotes. Extending the notion of inheritable genotype in evolutionary computation from the commonly considered model of DNA to chromatin (DNA and histones), we present epigenetic programming as an approach, incorporating an explicitly controlled gene expression through modification of histones in strongly-typed genetic programming (STGP). We propose a double cell representation of the simulated individuals, comprising somatic cell and germ cell, both represented by their respective chromatin structures. Following biologically plausible concepts, we regard the plastic phenotype of the somatic cell, achieved via controlled gene expression owing to modifications to histones (epigenetic learning, EL) as relevant for fitness evaluation, while the genotype of the germ cell corresponds to the phylogenesis of the individuals. The beneficial effect of EL on the performance characteristics of STGP is verified on evolution of social behavior of a team of predator agents in the predator-prey pursuit problem. Empirically obtained performance evaluation results indicate that EL contributes to about 2-fold improvement of computational effort of STGP. We trace the cause for that to the cumulative effect of polyphenism and epigenetic stability, both contributed by EL. The former allows for phenotypic diversity of genotypically similar individuals, while the latter robustly preserves the individuals from the destructive effects of crossover by silencing certain genotypic combinations and explicitly activating them only when they are most likely to be expressed in corresponding beneficial phenotypic traits.     

Genetic programming incorporating biased mutation for evolution and adaptation of Snakebot

In this work we propose an approach for incorporating learning probabilistic context-sensitive grammar (LPCSG) in genetic programming (GP), employed for evolution and adaptation of locomotion gaits of a simulated snake-like robot (Snakebot). Our approach is derived from the original context-free grammar which usually expresses the syntax of genetic programs in canonical GP. Empirically obtained results verify that employing LPCSG contributes to the improvement of computational effort of both (i) the evolution of the fastest possible locomotion gaits for various fitness conditions and (ii) adaptation of these locomotion gaits to challenging environment and degraded mechanical abilities of the Snakebot.     

Genetic programming for medical classification: a program simplification approach

This paper describes a genetic programming (GP) approach to medical data classification problems. In this approach, the evolved genetic programs are simplified online during the evolutionary process using algebraic simplification rules, algebraic equivalence and prime techniques. The new simplification GP approach is examined and compared to the standard GP approach on two medical data classification problems. The results suggest that the new simplification GP approach can not only be more efficient with slightly better classification performance than the basic GP system on these problems, but also significantly reduce the sizes of evolved programs. Comparison with other methods including decision trees, naive Bayes, nearest neighbour, nearest centroid, and neural networks suggests that the new GP approach achieved superior results to almost all of these methods on these problems. The evolved genetic programs are also easier to interpret than the “hidden patterns” discovered by the other methods.

Genetic programming for prevention of cyberterrorism through dynamic and evolving intrusion detection

Because malicious intrusions into critical information infrastructures are essential to the success of cyberterrorists, effective intrusion detection is also essential for defending such infrastructures. Cyberterrorism thrives on the development of new technologies; and, in response, intrusion detection methods must be robust and adaptive, as well as efficient. We hypothesize that genetic programming algorithms can aid in this endeavor. To investigate this proposition, we conducted an experiment using a very large dataset from the 1999 Knowledge Discovery in Database (KDD) Cup data, supplied by the Defense Advanced Research Projects Agency (DARPA) and MIT's Lincoln Laboratories. Using machine-coded linear genomes and a homologous crossover operator in genetic programming, promising results were achieved in detecting malicious intrusions. The resulting programs execute in real time, and high levels of accuracy were realized in identifying both positive and negative instances.     

Genetic algorithm-based fuzzy goal programming for class of chance-constrained programming problems

This paper presents a procedure for solving a multiobjective chance-constrained programming problem. Random variables appearing on both sides of the chance constraint are considered as discrete random variables with a known probability distribution. The literature does not contain any deterministic equivalent for solving this type of problem. Therefore, classical multiobjective programming techniques are not directly applicable. In this paper, we use a stochastic simulation technique to handle randomness in chance constraints. A fuzzy goal programming formulation is developed by using a stochastic simulation-based genetic algorithm. The most satisfactory solution is obtained from the highest membership value of each of the membership goals. Two numerical examples demonstrate the feasibility of the proposed approach.     

Genetic programming of conventional features to detect seizure precursors

This paper presents an application of genetic programming (GP) to optimally select and fuse conventional features (C-features) for the detection of epileptic waveforms within intracranial electroencephalogram (IEEG) recordings that precede seizures, known as seizure precursors. Evidence suggests that seizure precursors may localize regions important to seizure generation on the IEEG and epilepsy treatment. However, current methods to detect epileptic precursors lack a sound approach to automatically select and combine C-features that best distinguish epileptic events from background, relying on visual review predominantly. This work suggests GP as an optimal alternative to create a single feature after evaluating the performance of a binary detector that uses: (1) genetically programmed features; (2) features selected via GP; (3) forward sequentially selected features; and (4) visually selected features. Results demonstrate that a detector with a genetically programmed feature outperforms the other three approaches, achieving over 78.5% positive predictive value, 83.5% sensitivity, and 93% specificity at the 95% level of confidence.     

Multi-objective design of hierarchical consensus functions for clustering ensembles via genetic programming

This paper investigates a genetic programming (GP) approach aimed at the multi-objective design of hierarchical consensus functions for clustering ensembles. By this means, data partitions obtained via different clustering techniques can be continuously refined (via selection and merging) by a population of fusion hierarchies having complementary validation indices as objective functions. To assess the potential of the novel framework in terms of efficiency and effectiveness, a series of systematic experiments, involving eleven variants of the proposed GP-based algorithm and a comparison with basic as well as advanced clustering methods (of which some are clustering ensembles and/or multi-objective in nature), have been conducted on a number of artificial, benchmark and bioinformatics datasets. Overall, the results corroborate the perspective that having fusion hierarchies operating on well-chosen subsets of data partitions is a fine strategy that may yield significant gains in terms of clustering robustness.     

Dependent-chance programming: A class of stochastic optimization

This paper provides a theoretical framework of dependent-chance programming, as well as dependent-chance multiobjective programming and dependent-chance goal programming which are new types of stochastic optimization. A stochastic simulation based genetic algorithm is also designed for solving dependent-chance programming models.     

Lyapunov-based stability analysis automated by genetic programming

This contribution describes an automatic technique to detect suitable Lyapunov functions for nonlinear systems. The theoretical basis for the work is Lyapunov’s Direct Method, which provides sufficient conditions for stability of equilibrium points. In our proposed approach, genetic programming (GP) is used to search for suitable Lyapunov functions, that is, those that best predict the true domain of attraction. In the work presented here, our GP approach has been extended by defining a target function accounting for the Lyapunov function level sets.     

Evolving choice structures for genetic programming

It is quite difficult but essential for Genetic Programming (GP) to evolve the choice structures. Traditional approaches usually ignore this issue. They define some “if-structures” functions according to their problems by combining “if-else” statement, conditional criterions and elemental functions together. Obviously, these if-structure functions depend on the specific problems and thus have much low reusability. Based on this limitation of GP, in this paper we propose a kind of termination criterion in the GP process named “Combination Termination Criterion” (CTC). By testing CTC, the choice structures composed of some basic functions independent to the problems can be evolved successfully. Theoretical analysis and experiment results show that our method can evolve the programs with choice structures effectively within an acceptable additional time.     

Immune programming

This paper describes ‘Immune Programming’, a paradigm in the field of evolutionary computing taking its inspiration from principles of the vertebrate immune system. These principles are used to derive stack-based computer programs to solve a wide range of problems.An antigen is used to represent the programming problem to be addressed and may be provided in closed form or as an input/output mapping. An antibody set (a repertoire), wherein each member represents a candidate solution, is generated at random from a gene library representing computer instructions. Affinity, the fit of an antibody (a solution candidate) to the antigen (the problem), is analogous to shape-complementarity evident in biological systems. This measure is used to determine both the fate of individual antibodies, and whether or not the algorithm has successfully completed.When a repertoire has not yielded affinity relating algorithm completion, individual antibodies are replaced, cloned, or hypermutated. Replacement occurs according to a replacement probability and yields an entirely new randomly-generated solution candidate when invoked. This randomness (and that of the initial repertoire) provides diversity sufficient to address a wide range of problems. The chance of antibody cloning, wherein a verbatim copy is placed in the new repertoire, occurs proportionally to its affinity and according to a cloning probability. The chances of an effective (high-affinity) antibody being cloned is high, analogous to replication of effective pathogen-fighting antibodies in biological systems. Hypermutation, wherein probability-based replacement of the gene components within an antibody occurs, is also performed on high-affinity entities. However, the extent of mutation is inversely proportional to the antigenic affinity. The effectiveness of this process lies in the supposition that a candidate showing promise is likely similar to the ideal solution.This paper describes the paradigm in detail along with the underlying immune theories and their computational models. A set of sample problems are defined and solved using the algorithm, demonstrating its effectiveness and excellent convergent qualities. Further, the speed of convergence with respect to repertoire size limitations and probability parameters is explored and compared to stack-based genetic programming algorithms.     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.     

Credibility-based chance-constrained integer programming models for capital budgeting with fuzzy parameters

In this paper, we discuss a problem of capital budgeting in a fuzzy environment. Two types of models are proposed using credibility to measure confidence level. Since the proposed optimization problems are difficult to solve by traditional methods, a fuzzy simulation-based genetic algorithm is applied. Two numerical experiments demonstrate the effectiveness of the proposed algorithm.     

Applying genetic programming technique in classification trees

Classification problems are often encountered in many applications. In the past, classification trees were often generated by decision-tree methods and commonly used to solve classification problems. In this paper, we have proposed an algorithm based on genetic programming to search for an appropriate classification tree according to some criteria. The classification tree obtained can be transferred into a rule set, which can then be fed into a knowledge base to support decision making and facilitate daily operations. Two new genetic operators, elimination and merge, are designed in the proposed approach to remove redundancy and subsumption, thus producing more accurate and concise decision rules than that without using them. Experimental results from the credit card data also show the feasibility of the proposed algorithm.     

解非线性规划的多目标遗传算法及其收敛性

给出非线性约束规划问题的一种新解法。它既不需用传统的惩罚函数,又不需区分可行解和不可行解,新方法把带约束的非线性规划问题转化成为两个目标函数优化问题,其中一个是原约束问题的目标函数,另一个是违反约束的度函数,并利用多目标优化中的Pareto优劣关系设计了一种新的选择算子,通过对搜索操作和参数的合理设计给出了一种新型遗传算法,且给出了算法的收敛性证明,最后数据实验表明该算法对带约束的非线性规划问题求解是非常有效的。