Genetic algorithms for numerical optimization

Genetic algorithms (GAs) are stochastic adaptive algorithms whose search method is based on simulation of natural genetic inheritance and Darwinian striving for survival. They can be used to find approximate solutions to numerical optimization problems in cases where finding the exact optimum is prohibitively expensive, or where no algorithm is known. However, such applications can encounter problems that sometimes delay, if not prevent, finding the optimal solutions with desired precision. In this paper we describe applications of GAs to numerical optimization, present three novel ways to handle such problems, and give some experimental results.     

Comparison of a genetic algorithm and simulated annealing in an application to statistical image reconstruction

Genetic algorithms (GAs) are adaptive search techniques designed to find near-optimal solutions of large scale optimization problems with multiple local maxima. Standard versions of the GA are defined for objective functions which depend on a vector of binary variables. The problem of finding the maximum a posteriori (MAP) estimate of a binary image in Bayesian image analysis appears to be well suited to a GA as images have a natural binary representation and the posterior image probability is a multi-modal objective function. We use the numerical optimization problem posed in MAP image estimation as a test-bed on which to compare GAs with simulated annealing (SA), another all-purpose global optimization method. Our conclusions are that the GAs we have applied perform poorly, even after adaptation to this problem. This is somewhat unexpected, given the widespread claims of GAs' effectiveness, but it is in keeping with work by Jennison and Sheehan (1995) which suggests that GAs are not adept at handling problems involving a great many variables of roughly equal influence.We reach more positive conclusions concerning the use of the GA's crossover operation in recombining near-optimal solutions obtained by other methods. We propose a hybrid algorithm in which crossover is used to combine subsections of image reconstructions obtained using SA and we show that this algorithm is more effective and efficient than SA or a GA individually.     

A genetic algorithm tutorial

This tutorial covers the canonical genetic algorithm as well as more experimental forms of genetic algorithms, including parallel island models and parallel cellular genetic algorithms. The tutorial also illustrates genetic search by hyperplane sampling. The theoretical foundations of genetic algorithms are reviewed, include the schema theorem as well as recently developed exact models of the canonical genetic algorithm.     

A useful tool for statistical estimation: genetic algorithms

In this article, we introduce genetic algorithms (GAs) as a viable tool in estimating parameters in a wide array of statistical models. We performed simulation studies that compared the bias and variance of GAs with classical tools, namely, the steepest descent, Gauss–Newton, Levenberg–Marquardt and don't use derivative methods. In our simulation studies, we used the least squares criterion as the optimizing function. The performance of the GAs and classical methods were compared under the logistic regression model; non-linear Gaussian model and non-linear non-Gaussian model. We report that the GAs' performance is competitive to the classical methods under these three models.     

Double threshold autoregressive conditionally heteroscedastic model building by genetic algorithms

Asymmetric behaviour in both mean and variance is often observed in real time series. The approach we adopt is based on double threshold autoregressive conditionally heteroscedastic (DTARCH) model with normal innovations. This model allows threshold nonlinearity in mean and volatility to be modelled as a result of the impact of lagged changes in assets and squared shocks, respectively. A methodology for building DTARCH models is proposed based on genetic algorithms (GAs). The most important structural parameters, that is regimes and thresholds, are searched for by GAs, while the remaining structural parameters, that is the delay parameters and models orders, vary in some pre-specified intervals and are determined using exhaustive search and an Asymptotic Information Criterion (AIC) like criterion. For each structural parameters trial set, a DTARCH model is fitted that maximizes the (penalized) likelihood (AIC criterion). For this purpose the iteratively weighted least squares algorithm is used. Then the best model according to the AIC criterion is chosen. Extension to the double threshold generalized ARCH (DTGARCH) model is also considered. The proposed methodology is checked using both simulated and market index data. Our findings show that our GAs-based procedure yields results that comparable to that reported in the literature and concerned with real time series. As far as artificial time series are considered, the proposed procedure seems to be able to fit the data quite well. In particular, a comparison is performed between the present procedure and the method proposed by Tsay [Tsay, R.S., 1989, Testing and modeling threshold autoregressive processes. Journal of the American Statistical Association, Theory and Methods, 84, 231–240.] for estimating the delay parameter. The former almost always yields better results than the latter. However, adopting Tsay's procedure as a preliminary stage for finding the appropriate delay parameter may save computational time specially if the delay parameter may vary in a large interval.     

A sequential clustering algorithm with applications to gene expression data

Clustering algorithms are used in the analysis of gene expression data to identify groups of genes with similar expression patterns. These algorithms group genes with respect to a predefined dissimilarity measure without using any prior classification of the data. Most of the clustering algorithms require the number of clusters as input, and all the objects in the dataset are usually assigned to one of the clusters. We propose a clustering algorithm that finds clusters sequentially, and allows for sporadic objects, so there are objects that are not assigned to any cluster. The proposed sequential clustering algorithm has two steps. First it finds candidates for centers of clusters. Multiple candidates are used to make the search for clusters more efficient. Secondly, it conducts a local search around the candidate centers to find the set of objects that defines a cluster. The candidate clusters are compared using a predefined score, the best cluster is removed from data, and the procedure is repeated. We investigate the performance of this algorithm using simulated data and we apply this method to analyze gene expression profiles in a study on the plasticity of the dendritic cells.     

Comparative analysis of modern optimization tools for the p-median problem

This paper develops a study on different modern optimization techniques to solve the p-median problem. We analyze the behavior of a class of evolutionary algorithm (EA) known as cellular EA (cEA), and compare it against a tailored neural network model and against a canonical genetic algorithm for optimization of the p-median problem. We also compare against existing approaches including variable neighborhood search and parallel scatter search, and show their relative performances on a large set of problem instances. Our conclusions state the advantages of using a cEA: wide applicability, low implementation effort and high accuracy. In addition, the neural network model shows up as being the more accurate tool at the price of a narrow applicability and larger customization effort.     

Genetic algorithms and scatter search: unsuspected potentials

We provide a tutorial survey of connections between genetic algorithms and scatter search that have useful implications for developing new methods for optimization problems. The links between these approaches are rooted in principles underlying mathematical relaxations, which became inherited and extended by scatter search. Hybrid methods incorporating elements of genetic algorithms and scatter search are beginning to be explored in the literature, and we demonstrate that the opportunity exists to develop more advanced procedures that make fuller use of scatter search strategies and their recent extensions.     

On parallel policies for ranking and selection problems

In this paper we develop and test experimental methodologies for selection of the best alternative among a discrete number of available treatments. We consider a scenario where a researcher sequentially decides which treatments are assigned to experimental units. This problem is particularly challenging if a single measurement of the response to a treatment is time-consuming and there is a limited time for experimentation. This time can be decreased if it is possible to perform measurements in parallel. In this work we propose and discuss asynchronous extensions of two well-known Ranking & Selection policies, namely, Optimal Computing Budget Allocation (OCBA) and Knowledge Gradient (KG) policy. Our extensions (Asynchronous Optimal Computing Budget Allocation (AOCBA) and Asynchronous Knowledge Gradient (AKG), respectively) allow for parallel asynchronous allocation of measurements. Additionally, since the standard KG method is sequential (it can only allocate one experiment at a time) we propose a parallel synchronous extension of KG policy – Synchronous Knowledge Gradient (SKG). Computer simulations of our algorithms indicate that our parallel KG-based policies (AKG, SKG) outperform the standard OCBA method as well as AOCBA, if the number of evaluated alternatives is small or the computing/experimental budget is limited. For experimentations with large budgets and big sets of alternatives, both the OCBA and AOCBA policies are more efficient.     

Bayesian optimal sequential design for nonparametric regression via inhomogeneous evolutionary MCMC

We develop a novel computational methodology for Bayesian optimal sequential design for nonparametric regression. This computational methodology, that we call inhomogeneous evolutionary Markov chain Monte Carlo, combines ideas of simulated annealing, genetic or evolutionary algorithms, and Markov chain Monte Carlo. Our framework allows optimality criteria with general utility functions and general classes of priors for the underlying regression function. We illustrate the usefulness of our novel methodology with applications to experimental design for nonparametric function estimation using Gaussian process priors and free-knot cubic splines priors.     

Some partially sequential nonparametric tests for detecting linear trend

In the present study, we develop two nonparametric partially sequential tests for detecting possible presence of linear trend among the incoming series of observations. We assume that a sample of fixed size is available a priori from some unknown univariate continuous population and there is no sign of trend among these historical observations. Our proposed tests can be viewed as the sequential type tests for monitoring structural changes. We use partial sequential sampling schemes based on usual ranks as well as on sequential ranks. We provide detailed discussion on asymptotic studies related to the proposed tests. We compare the two tests under various situations. We also present some numerical results based on simulation studies. Proposed tests are extremely important in profit making in volatile market through Margin Trading. We illustrate the mechanism with a detailed analysis of a stock price data.     

Parallel multivariate slice sampling

Slice sampling provides an easily implemented method for constructing a Markov chain Monte Carlo (MCMC) algorithm. However, slice sampling has two major drawbacks: (i) it requires repeated evaluation of likelihoods for each update, which can make it impractical when evaluations are expensive or as the number of evaluations grows (geometrically) with the dimension of the slice sampler, and (ii) since it can be challenging to construct multivariate updates, the updates are typically univariate, which often results in slow mixing samplers. We propose an approach to multivariate slice sampling that naturally lends itself to a parallel implementation. Our approach takes advantage of recent advances in computer architectures, for instance, the newest generation of graphics cards can execute roughly 30,000 threads simultaneously. We demonstrate that it is possible to construct a multivariate slice sampler that has good mixing properties and is efficient in terms of computing time. The contributions of this article are therefore twofold. We study approaches for constructing a multivariate slice sampler, and we show how parallel computing can be useful for making MCMC algorithms computationally efficient. We study various implementations of our algorithm in the context of real and simulated data.     

Sequential and two-stage procedures for selecting the better exponential population covering the case of unknown and unequal scale parameters

The problems of selecting the larger location parameter of two exponential distributions are discussed. When the scale parameters are the same but unknown, we consider the procedure of Desu et al. (1977) in detail, and study some of its exact and asymptotic properties. We indicate how this procedure can be modified along the lines of Mukhopadhyay (1979, 1980) to achieve first-order asymptotic efficiency. We then propose a sequential procedure for this set-up and show that it is asymptotically second-order efficient according to Ghosh and Mukhopadhyay (1981). In case the scale parameters are completely unknown and unequal, we propose a two-stage procedure that guarantees the probability of correct selection to exceed the prescribed nominal level in the preference zone. We do not need any new tables to implement this particular procedure other than those in Krishnaiah and Armitage (1964), Gupta and Sobel (1962), Guttman and Milton (1969). We also propose a sequential method in this case and derive some of its asymptotic properties.     

Nonparametric monitoring of financial time series by jump-preserving control charts

Since structural changes in a possibly transformed financial time series may contain important information for investors and analysts, we consider the following problem of sequential econometrics. For a given time series we aim at detecting the first change-point where a jump of size a occurs, i.e., the mean changes from, say, m ₀to m ₀+ a and returns to m ₀after a possibly short period s. To address this problem, we study a Shewhart-type control chart based on a sequential version of the sigma filter, which extends kernel smoothers by employing stochastic weights depending on the process history to detect jumps in the data more accurately than classical approaches. We study both theoretical properties and performance issues. Concerning the statistical properties, it is important to know whether the normed delay time of the considered control chart is bounded, at least asymptotically. Extending known results for linear statistics employing deterministic weighting schemes, we establish an upper bound which holds if the memory of the chart tends to infinity. The performance of the proposed control charts is studied by simulations. We confine ourselves to some special models which try to mimic important features of real time series. Our empirical results provide some evidence that jump-preserving weights are preferable under certain circumstances.     

Inference in molecular population genetics

Full likelihood-based inference for modern population genetics data presents methodological and computational challenges. The problem is of considerable practical importance and has attracted recent attention, with the development of algorithms based on importance sampling (IS) and Markov chain Monte Carlo (MCMC) sampling. Here we introduce a new IS algorithm. The optimal proposal distribution for these problems can be characterized, and we exploit a detailed analysis of genealogical processes to develop a practicable approximation to it. We compare the new method with existing algorithms on a variety of genetic examples. Our approach substantially outperforms existing IS algorithms, with efficiency typically improved by several orders of magnitude. The new method also compares favourably with existing MCMC methods in some problems, and less favourably in others, suggesting that both IS and MCMC methods have a continuing role to play in this area. We offer insights into the relative advantages of each approach, and we discuss diagnostics in the IS framework.     

Efficient initial designs for binary response data

In this paper we introduce a binary search algorithm that efficiently finds initial maximum likelihood estimates for sequential experiments where a binary response is modeled by a continuous factor. The problem is motivated by switching measurements on superconducting Josephson junctions. In this quantum mechanical experiment, the current is the factor controlled by the experimenter and a binary response indicating the presence or the absence of a voltage response is measured. The prior knowledge on the model parameters is typically poor, which may cause the common approaches of initial estimation to fail. The binary search algorithm is designed to work reliably even when the prior information is very poor. The properties of the algorithm are studied in simulations and an advantage over the initial estimation with equally spaced factor levels is demonstrated. We also study the cost-efficiency of the binary search algorithm and find the approximately optimal number of measurements per stage when there is a cost related to the number of stages in the experiment.     

Controlling Type-I Error Rate in Monitoring Structural Changes Using Partially Sequential Procedures

In the present article, we develop some asymptotically power on partially sequential nonparametric tests for monitoring structural changes. Our test procedures are based on Wilcoxon score. We use the idea of curved stopping boundaries. We derive some exact results and perform simulation studies to provide various properties of the tests. We see that one of the proposed procedures significantly controls the Type I error rate. This procedure may be very effective for fluctuation monitoring. We illustrate the procedures by using real life data from the stock market.     

D-optimal minimax design criterion for two-level fractional factorial designs

A D-optimal minimax design criterion is proposed to construct two-level fractional factorial designs, which can be used to estimate a linear model with main effects and some specified interactions. D-optimal minimax designs are robust against model misspecification and have small biases if the linear model contains more interaction terms. When the D-optimal minimax criterion is compared with the D-optimal design criterion, we find that the D-optimal design criterion is quite robust against model misspecification. Lower and upper bounds derived for the loss functions of optimal designs can be used to estimate the efficiencies of any design and evaluate the effectiveness of a search algorithm. Four algorithms to search for optimal designs for any run size are discussed and compared through several examples. An annealing algorithm and a sequential algorithm are particularly effective to search for optimal designs.     

Analysis of familial aggregation in the presence of varying family sizes

Summary.  Family studies are frequently undertaken as the first step in the search for genetic and/or environmental determinants of disease. Significant familial aggregation of disease is suggestive of a genetic aetiology for the disease and may lead to more focused genetic analysis. Of course, it may also be due to shared environmental factors. Many methods have been proposed in the literature for the analysis of family studies. One model that is appealing for the simplicity of its computation and the conditional interpretation of its parameters is the quadratic exponential model. However, a limiting factor in its application is that it is not reproducible , meaning that all families must be of the same size. To increase the applicability of this model, we propose a hybrid approach in which analysis is based on the assumption of the quadratic exponential model for a selected family size and combines a missing data approach for smaller families with a marginalization approach for larger families. We apply our approach to a family study of colorectal cancer that was sponsored by the Cancer Genetics Network of the National Institutes of Health. We investigate the properties of our approach in simulation studies. Our approach applies more generally to clustered binary data.     

Efficient estimation and model selection in large graphical models

We develop a computationally efficient method to determine the interaction structure in a multidimensional binary sample. We use an interaction model based on orthogonal functions, and give a result on independence properties in this model. Using this result we develop an efficient approximation algorithm for estimating the parameters in a given undirected model. To find the best model, we use a heuristic search algorithm in which the structure is determined incrementally. We also give an algorithm for reconstructing the causal directions, if such exist. We demonstrate that together these algorithms are capable of discovering almost all of the true structure for a problem with 121 variables, including many of the directions.