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.     

An evolutionary algorithm for A-optimal incomplete block designs

Evolutionary algorithms are heuristic stochastic search and optimization techniques with principles taken from natural genetics. They are procedures mimicking the evolution process of an initial population through genetic transformations. This paper is concerned with the problem of finding A-optimal incomplete block designs for multiple treatment comparisons represented by a matrix of contrasts. An evolutionary algorithm for searching optimal, or nearly optimal, incomplete block designs is described in detail. Various examples regarding the application of the algorithm to some well-known problems illustrate the good performance of the algorithm     

A new approach for the genetic algorithm

This paper proposes a new approach based on two explicit rules of Mendel experiments and Mendel's population genetics for the genetic algorithm (GA). These rules are the segregation and independent assortment of alleles, respectively. This new approach has been simulated for the optimization of certain test functions. The doctrinal sense of GA is conceptually improved by this approach using a Mendelian framework. The new approach is different than the conventional one in terms of crossover, recombination, and mutation operators. The results obtained here are in agreement with those of the conventional GA, and even better in some cases. These results suggest that the new approach is overall more sensitive and accurate than the conventional one. Possible ways of improving the approach by including more genetic formulae in the code are also discussed.     

Symbolic computation: a unified approach to studying likelihood

We describe a set of procedures that automate many algebraic calculations common in statistical asymptotic theory. The procedures are very general and serve to unify the study of likelihood and likelihood type functions. The procedures emulate techniques one would normally carry out by hand; this strategy is emphasised throughout the paper. The purpose of the software is to provide a practical alternative to difficult manual algebraic computations. The result is a method that is quick and free of clerical error.     

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.     

A two-stage algorithm for computation of the exact distribution of sums of spacings

Based on the recursions in Huffer (1988 Huffer, F. (1988). Divided differences and the joint distribution of linear combinations of spacings. Journal of Applied Probability 25:346–354. [Google Scholar]) and Huffer and Lin (2001 Huffer, F. W., Lin, C. T. (2001). Computing the joint distribution of general linear combinations of spacings or exponential variates. Statistica Sinica 11:1141–1157. [Google Scholar]), we present a two-stage algorithm and two specialized methods for evaluating the probabilities involving linear combination of spacings of special forms. The two-stage algorithm combines the advantages of marking algorithm in Huffer and Lin (1997 Huffer, F. W., Lin, C. T. (1997). Computing the exact distribution of the extremes of sums of consecutive spacings. Computational Statistics and Data Analysis 26:117–132. [Google Scholar]) and general algorithm in Huffer and Lin (2001 Huffer, F. W., Lin, C. T. (2001). Computing the joint distribution of general linear combinations of spacings or exponential variates. Statistica Sinica 11:1141–1157. [Google Scholar]). The proposed methods can analytically derive the exact expressions for some specific problems, and efficiently handle problems such as the distribution of the circular scan statistic and multiple coverage probabilities.     

Generalized multiple-point Metropolis algorithms for approximate Bayesian computation

It is well known that the approximate Bayesian computation algorithm based on Markov chain Monte Carlo methods suffers from the sensitivity to the choice of starting values, inefficiency and a low acceptance rate. To overcome these problems, this study proposes a generalization of the multiple-point Metropolis algorithm, which proceeds by generating multiple-dependent proposals and then by selecting a candidate among the set of proposals on the basis of weights that can be chosen arbitrarily. The performance of the proposed algorithm is illustrated by using both simulated and real data.     

Hierarchical Bayes estimation in small area estimation using cross-sectional and time-series data

Bayesian methods have been extensively used in small area estimation. A linear model incorporating autocorrelated random effects and sampling errors was previously proposed in small area estimation using both cross-sectional and time-series data in the Bayesian paradigm. There are, however, many situations that we have time-related counts or proportions in small area estimation; for example, monthly dataset on the number of incidence in small areas. This article considers hierarchical Bayes generalized linear models for a unified analysis of both discrete and continuous data with incorporating cross-sectional and time-series data. The performance of the proposed approach is evaluated through several simulation studies and also by a real dataset.     

Modified genetic algorithm-based clustering for probability density functions

This article modifies two internal validity measures and applies them to evaluate the quality of clustering for probability density functions (pdfs). Based on these measures, we propose a new modified genetic algorithm called GA-CDF to establish the suitable clusters for pdfs. The proposed algorithm is tested by four numerical examples including two synthetic data sets and two real data sets. These examples illustrate the superiority of proposed algorithm over some existing algorithms in evaluating the internal or external validity measures. It demonstrates the feasibility and applicability of the GA-CDF for practical problems in data mining.     

Knot selection for least-squares and penalized splines

Two new stochastic search methods are proposed for optimizing the knot locations and/or smoothing parameters for least-squares or penalized splines. One of the methods is a golden-section-augmented blind search, while the other is a continuous genetic algorithm. Monte Carlo experiments indicate that the algorithms are very successful at producing knot locations and/or smoothing parameters that are near optimal in a squared error sense. Both algorithms are amenable to parallelization and have been implemented in OpenMP and MPI. An adjusted GCV criterion is also considered for selecting both the number and location of knots. The method performed well relative to MARS in a small empirical comparison.     

Numerical computation of bridge probabilities

This paper contains an analysis of the problem of computing the joint probability density of the honor card point count in each of four hands in the game of bridge. Efficient representation of the data is considered. Computational algorithms are given for dealing with a compressed form of the density. From the joint density, the densities of the point count in the best and worst hands are obtained. Also obtained is the conditional distribution that a partnership has m points given that one of the partners has n1 points.     

Simulating posterior Gibbs distributions: a comparison of the Swendsen-Wang and Gibbs sampler methods

We show in detail how the Swendsen-Wang algorithm, for simulating Potts models, may be used to simulate certain types of posterior Gibbs distribution, as a special case of Edwards and Sokal (1988), and we empirically compare the behaviour of the algorithm with that of the Gibbs sampler. Some marginal posterior mode and simulated annealing image restorations are also examined. Our results demonstrate the importance of the starting configuration. If this is inappropriate, the Swendsen-Wang method can suffer from critical slowing in moderately noise-free situations where the Gibbs sampler convergence is very fast, whereas the reverse is true when noise level is high.     

Efficient computation of location depth contours by methods of computational geometry

The concept of location depth was introduced as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust estimation, hypothesis testing, and graphical display. The depth contours form a collection of nested polygons, and the center of the deepest contour is called the Tukey median. The only available implemented algorithms for the depth contours and the Tukey median are slow, which limits their usefulness. In this paper we describe an optimal algorithm which computes all bivariate depth contours in O(n ²) time and space, using topological sweep of the dual arrangement of lines. Once these contours are known, the location depth of any point can be computed in O(log² n) time with no additional preprocessing or in O(log n) time after O(n ²) preprocessing. We provide fast implementations of these algorithms to allow their use in everyday statistical practice.     

Bayesian computation for Log-Gaussian Cox processes: a comparative analysis of methods

The Log-Gaussian Cox process is a commonly used model for the analysis of spatial point pattern data. Fitting this model is difficult because of its doubly stochastic property, that is, it is a hierarchical combination of a Poisson process at the first level and a Gaussian process at the second level. Various methods have been proposed to estimate such a process, including traditional likelihood-based approaches as well as Bayesian methods. We focus here on Bayesian methods and several approaches that have been considered for model fitting within this framework, including Hamiltonian Monte Carlo, the Integrated nested Laplace approximation, and Variational Bayes. We consider these approaches and make comparisons with respect to statistical and computational efficiency. These comparisons are made through several simulation studies as well as through two applications, the first examining ecological data and the second involving neuroimaging data.     

A Bayesian hierarchical approach to dual response surface modelling

In modern quality engineering, dual response surface methodology is a powerful tool to model an industrial process by using both the mean and the standard deviation of the measurements as the responses. The least squares method in regression is often used to estimate the coefficients in the mean and standard deviation models, and various decision criteria are proposed by researchers to find the optimal conditions. Based on the inherent hierarchical structure of the dual response problems, we propose a Bayesian hierarchical approach to model dual response surfaces. Such an approach is compared with two frequentist least squares methods by using two real data sets and simulated data.     

Adaptive evolutionary Monte Carlo algorithm for optimization with applications to sensor placement problems

In this paper, we present an adaptive evolutionary Monte Carlo algorithm (AEMC), which combines a tree-based predictive model with an evolutionary Monte Carlo sampling procedure for the purpose of global optimization. Our development is motivated by sensor placement applications in engineering, which requires optimizing certain complicated “black-box” objective function. The proposed method is able to enhance the optimization efficiency and effectiveness as compared to a few alternative strategies. AEMC falls into the category of adaptive Markov chain Monte Carlo (MCMC) algorithms and is the first adaptive MCMC algorithm that simulates multiple Markov chains in parallel. A theorem about the ergodicity property of the AEMC algorithm is stated and proven. We demonstrate the advantages of the proposed method by applying it to a sensor placement problem in a manufacturing process, as well as to a standard Griewank test function.     

Bayesian Inference and Forecasting in Dynamic Neural Networks with Fully Markov Switching ARCH Noises

We deal with one-layer feed-forward neural network for the Bayesian analysis of nonlinear time series. Noises are modeled nonlinearly and nonnormally, by means of ARCH models whose parameters are all dependent on a hidden Markov chain. Parameter estimation is performed by sampling from the posterior distribution via Evolutionary Monte Carlo algorithm, in which two new crossover operators have been introduced. Unknown parameters of the model also include the missing values which can occur within the observed series, so, considering future values as missing, it is also possible to compute point and interval multi-step-ahead predictions.     

基于遗传算法的投影寻踪聚类

传统的投影寻踪聚类算法PROCLUS是一种有效的处理高维数据聚类的算法,但此算法是利用爬山法（Hill climbing）对各类中心点进行循环迭代、选取最优的过程,由于爬山法是一种局部搜索（local search）方法,得到的最优解可能仅仅是局部最优。针对上述缺陷,提出一种改进的投影寻踪聚类算法,即利用遗传算法（Genetic Algorithm）对各类中心点进行循环迭代,寻找到全局最优解。仿真实验结果证明了新算法的可行性和有效性。