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.     

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.     

Multi-objective fuzzy flexible job shop scheduling using memetic algorithm

Multi-objective flexible job shop scheduling problem with fuzzy processing time and fuzzy due date is a complicated combinatorial optimization problem. In this paper, a genetic global optimization is combined with a local search method to construct an effective memetic algorithm (MA) for simultaneously optimizing fuzzy makespan, average agreement index and minimal agreement index. First, a hybridization of different machine assignment methods with different operation sequence rules is proposed to generate a high-performance initial population. Second, the algorithm framework similar to the non-dominated sorting genetic algorithm II (NSGA-II) is adopted, in which a well-designed chromosome decoding method and two effective genetic operators are used. Then, a novel fuzzy Pareto dominance relationship based on the possibility degree and a modified crowding distance measure are defined and further employed to modify the fast non-dominated sorting. Next, a novel local search is incorporated into NSGA-II, where some candidate individuals are selected from the offspring population to experience variable neighbourhood local search by using the selection mechanism. In the experiment, the influence of four key parameters is investigated based on the Taguchi method of design of experiment. Finally, some comparisons are carried out with other existing algorithms on benchmark instances, and demonstrate the effectiveness of the proposed MA.     

Macroeconomic Forecasting Using Pooled International Data

The genetic algorithm is examined as a method for solving optimization problems in econometric estimation. It does not restrict either the form or regularity of the objective function, allows a reasonably large parameter space, and does not rely on a point-to-point search. The performance is evaluated through two sets of experiments on standard test problems as well as econometric problems from the literature. First, alternative genetic algorithms that vary over mutation and crossover rates, population sizes, and other features are contrasted. Second, the genetic algorithm is compared to Nelder–Mead simplex, simulated annealing, adaptive random search, and MSCORE.     

Hitch-hiker's guide to genetic algorithms

Genetic algorithms are a set of algorithms with properties which enable them to efficiently search large solution spaces where conventional statistical methodology is inappropriate. They have been used to find effective control and design strategies in industry, for finding rules relating factors and outcomes in medicine and business, and for solving problems ranging from function optimization to identification of patterns in data. They work using ideas from biology, specifically from population genetics, and are appealing because of their robustness in the presence of noise and their ability to cope with highly non-linear, multimodal and multivariate problems. This paper reviews the current literature on genetic algorithms. It looks at ways of defining genetic algorithms for various problems, and examples are introduced to illustrate their application in different contexts. It summarizes the different aspects which have been, and continue to be, the focus of research, and areas requiring further invetigation are identified.     

Complement to a comparative analysis of heuristics for the <Emphasis Type="Italic">p</Emphasis>-median problem

A recent comparison of evolutionary, neural network, and scatter search heuristics for solving the p-median problem is completed by (i) gathering or obtaining exact optimal values in order to evaluate errors precisely, and (ii) including results obtained with several variants of a variable neighborhood search (VNS) heuristic. For a first, well-known, series of instances, the average errors of the evolutionary and neural network heuristics are over 10% and more than 1000 times larger than that of VNS. For a second series, this error is about 3% while the errors of the parallel VNS and of a hybrid heuristic are about 0.01% and that of parallel scatter search even smaller.     

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.     

Improving flexibility and efficiency by adding parallelism to genetic algorithms

In this paper we develop a study on several types of parallel genetic algorithms (PGAs). Our motivation is to bring some uniformity to the proposal, comparison, and knowledge exchange among the traditionally opposite kinds of serial and parallel GAs. We comparatively analyze the properties of steady-state, generational, and cellular genetic algorithms. Afterwards, this study is extended to consider a distributed model consisting in a ring of GA islands. The analyzed features are the time complexity, selection pressure, schema processing rates, efficacy in finding an optimum, efficiency, speedup, and resistance to scalability. Besides that, we briefly discuss how the migration policy affects the search. Also, some of the search properties of cellular GAs are investigated. The selected benchmark is a representative subset of problems containing real world difficulties. We often conclude that parallel GAs are numerically better and faster than equivalent sequential GAs. Our aim is to shed some light on the advantages and drawbacks of various sequential and parallel GAs to help researchers using them in the very diverse application fields of the evolutionary computation.     

Constructing 1-rotational NRDFs through an optimization approach: new (46,9,8), (51,10,9) and (55,9,8)-NRBDs

In this paper we formulate the problem of constructing 1-rotational near resolvable difference families as a combinatorial optimization problem where a global optimum corresponds to a desired difference family. Then, we develop an algorithm based on scatter search in conjunction with a tabu search to construct many of these difference families. In particular, we construct three new near resolvable difference families which lead to an equal number of new 1-rotational near resolvable block designs with parameters: (46,9,8), (51,10,9) and (55,9,8). Our results indicate that this conjunction outperforms both scatter search and tabu search.     

New Algorithms for Evaluating the Log-Likelihood Function Derivatives in the AI-REML Method

In this study, we propose several improvements of the Average Information Restricted Maximum Likelihood algorithms for estimating the variance components for genetic mapping of quantitative traits. The improved methods are applicable when two variance components are to be estimated. The improvements are related to the algebraic part of the methods and utilize the properties of the underlying matrix structures.

In contrast to previously developed algorithms, the explicit computation of a matrix inverse is replaced by the solution of a linear system of equations with multiple right-hand sides, based on a particular matrix decomposition. The computational costs of the proposed algorithms are analyzed and compared.     

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.     

Randomized heuristic algorithms for orthogonal projection of a point onto a set

Abstract

The problem of orthogonal projection of a point onto a set is an essential problem of computational geometry. This problem has many practical applications in different areas such as robotics, computer graphics and so on. In the present paper three algorithms for solving this problem are proposed. This algorithms are based on the idea of heuristic random search. Numerical experiments illustrating the work of the proposed methods are presented.     

Application of genetic algorithms to the construction of exact D-optimal designs

This paper studies the application of genetic algorithms to the construction of exact D-optimal experimental designs. The concept of genetic algorithms is introduced in the general context of the problem of finding optimal designs. The algorithm is then applied specifically to finding exact D-optimal designs for three different types of model. The performance of genetic algorithms is compared with that of the modified Fedorov algorithm in terms of computing time and relative efficiency. Finally, potential applications of genetic algorithms to other optimality criteria and to other types of model are discussed, along with some open problems for possible future research.     

Bayesian variable selection with related predictors

In data sets with many predictors, algorithms for identifying a good subset of predictors are often used. Most such algorithms do not allow for any relationships between predictors. For example, stepwise regression might select a model containing an interaction AB but neither main effect A or B. This paper develops mathematical representations of this and other relations between predictors, which may then be incorporated in a model selection procedure. A Bayesian approach that goes beyond the standard independence prior for variable selection is adopted, and preference for certain models is interpreted as prior information. Priors relevant to arbitrary interactions and polynomials, dummy variables for categorical factors, competing predictors, and restrictions on the size of the models are developed. Since the relations developed are for priors, they may be incorporated in any Bayesian variable selection algorithm for any type of linear model. The application of the methods here is illustrated via the stochastic search variable selection algorithm of George and McCulloch (1993), which is modified to utilize the new priors. The performance of the approach is illustrated with two constructed examples and a computer performance dataset.     

A clustering-based coordinate exchange algorithm for generating G-optimal experimental designs

In the optimal experimental design literature, the G-optimality is defined as minimizing the maximum prediction variance over the entire experimental design space. Although the G-optimality is a highly desirable property in many applications, there are few computer algorithms developed for constructing G-optimal designs. Some existing methods employ an exhaustive search over all candidate designs, which is time-consuming and inefficient. In this paper, a new algorithm for constructing G-optimal experimental designs is developed for both linear and generalized linear models. The new algorithm is made based on the clustering of candidate or evaluation points over the design space and it is a combination of point exchange algorithm and coordinate exchange algorithm. In addition, a robust design algorithm is proposed for generalized linear models with modification of an existing method. The proposed algorithm are compared with the methods proposed by Rodriguez et al. [Generating and assessing exact G-optimal designs. J. Qual. Technol. 2010;42(1):3–20] and Borkowski [Using a genetic algorithm to generate small exact response surface designs. J. Prob. Stat. Sci. 2003;1(1):65–88] for linear models and with the simulated annealing method and the genetic algorithm for generalized linear models through several examples in terms of the G-efficiency and computation time. The result shows that the proposed algorithm can obtain a design with higher G-efficiency in a much shorter time. Moreover, the computation time of the proposed algorithm only increases polynomially when the size of model increases.     

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 study on algorithms for optimization of Latin hypercubes

A crucial component in the statistical simulation of a computationally expensive model is a good design of experiments. In this paper we compare the efficiency of the columnwise–pairwise (CP) and genetic algorithms for the optimization of Latin hypercubes (LH) for the purpose of sampling in statistical investigations. The performed experiments indicate, among other results, that CP methods are most efficient for small and medium size LH, while an adopted genetic algorithm performs better for large LH.Two optimality criteria suggested in the literature are evaluated with respect to statistical properties and efficiency. The obtained results lead us to favor a criterion based on the physical analogy of minimization of forces between charged particles suggested in Audze and Eglais (1977. Problems Dyn. Strength 35, 104–107) over a ‘maximin distance’ criterion from Johnson et al. (1990. J. Statist. Plann. Inference 26, 131–148).     

大数据下张量充分降维方法及其应用研究

在大数据时代,金融学、基因组学和图像处理等领域产生了大量的张量数据。Zhong等(2015)提出了张量充分降维方法,并给出了处理二阶张量的序列迭代算法。鉴于高阶张量在实际生活中的广泛应用,本文将Zhong等(2015)的算法推广到高阶,以三阶张量为例,提出了两种不同的算法:结构转换算法和结构保持算法。两种算法都能够在不同程度上保持张量原有结构信息,同时有效降低变量维度和计算复杂度,避免协方差矩阵奇异的问题。将两种算法应用于人像彩图的分类识别,以二维和三维点图等形式直观展现了算法分类结果。将本文的结构保持算法与K-means聚类方法、t-SNE非线性降维方法、多维主成分分析、多维判别分析和张量切片逆回归共五种方法进行对比,结果表明本文所提方法在分类精度方面有明显优势,因此在图像识别及相关应用领域具有广阔的发展前景。     

Accelerated Estimation of Switching Algorithms: The Cointegrated VAR Model and Other Applications

Restricted versions of the cointegrated vector autoregression are usually estimated using switching algorithms. These algorithms alternate between two sets of variables but can be slow to converge. Acceleration methods are proposed that combine simplicity and effectiveness. These methods also outperform existing proposals in some applications of the expectation–maximization method and parallel factor analysis.     

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.