On the evolution of recombination in haploids and diploids: I. Deterministic models

In population genetic theory, most analytical and numerical studies of the evolution of recombination have focused on diploid genetics. In studies of the foundations and applications of genetic algorithms (GA's), however, the bit-strings are usually treated as haploid genotypes. In this paper and its companion paper (Bergman et al., 1995), we compare results for the evolutionary dynamics of modifiers of recombination in haploids with results derived for diploids. In this paper, we study the evolution of an allele that controls the rate of recombination between two loci subject to directional selection. It is shown analytically that the fate of a recombination modifier in both haploids and diploids is determined in a complicated way by the sign of the epistasis (interaction in fitness) between the loci, the sign of the initial linkage disequilibrium, and the amount of recombination between the modifier and the genes under selection. This theory is deterministic in that the population is regarded as infinite and no sampling occurs to produce offspring from parents. In the companion paper (Bergman et al., Complexity, 1(2) 1995), we expand upon this work by addressing epistatic interactions among several loci in finite populations.     

Algorithms,genetics, and populations: The schemata theorem revisited

Models for the genetic evolution of natural populations have supplied the inspiration for the adaptive computer algorithms known as “genetic algorithms.” In its original form, a genetic algorithm simulates the evolution of a haploid population: Genetic variation is produced by mutation at a number of genetic loci in a chromosome, represented as a string of bits, and the variants in the various chromosomes are reshuffled by genetic recombination. In nature, the ability of a haploid individual to survive and reproduce is expressed as its fitness; in computer science the value of a string is measured by its ability to program a given task. The performance of genetic algorithms is evaluated in the “schemata theorem,” which we present and discuss in the context of the population genetics of multiple loci and propose a generalization of the theorem. © 1998 John Wiley & Sons, Inc.     

Derivation of Several SDE Systems in One- and Two-Locus Population Genetics

A direct approach is described for deriving stochastic differential equations (SDEs) for the dynamics of evolving populations. Itô SDEs are presented and compared for populations of haploid and diploid individuals with one or more alleles at one locus undergoing pure genetic drift. The results agree with previous investigations in mathematical genetics using diffusion approximations. Furthermore, a stochastic differential equation model is derived for diploid populations with two alleles at two loci. The derived SDE systems provide unifying, consistent models.     

Fully discrete finite element approximations of the forced Fisher equation

We consider fully discrete finite element approximations of the forced Fisher equation that models the dynamics of gene selection/migration for a diploid population with two available alleles in a multidimensional habitat and in the presence of an artificially introduced genotype. Finite element methods are used to effect spatial discretization and a nonstandard backward Euler method is used for the time discretization. Error estimates for the fully discrete approximations are derived by applying the Brezzi-Rappaz-Raviart theory for the approximation of a class of nonlinear problems. The approximation schemes and error estimates are applicable under weaker regularity hypotheses than those that are typically assumed in the literature. The algorithms and analyses, although presented in the concrete setting of the forced Fisher equation, also apply to a wide class of semilinear parabolic partial differential equations.     

On the Orderings and Groupings of Conditional Maximizations within ECM-Type Algorithms

Abstract

The ECM and ECME algorithms are generalizations of the EM algorithm in which the maximization (M) step is replaced by several conditional maximization (CM) steps. The order that the CM-steps are performed is trivial to change and generally affects how fast the algorithm converges. Moreover, the same order of CM-steps need not be used at each iteration and in some applications it is feasible to group two or more CM-steps into one larger CM-step. These issues also arise when implementing the Gibbs sampler, and in this article we study them in the context of fitting log-linear and random-effects models with ECM-type algorithms. We find that some standard theoretical measures of the rate of convergence can be of little use in comparing the computational time required, and that common strategies such as using a random ordering may not provide the desired effects. We also develop two algorithms for fitting random-effects models to illustrate that with careful selection of CM-steps, ECM-type algorithms can be substantially faster than the standard EM algorithm.     

Improving solution of discrete competitive facility location problems

We consider discrete competitive facility location problems in this paper. Such problems could be viewed as a search of nodes in a network, composed of candidate and customer demand nodes, which connections correspond to attractiveness between customers and facilities located at the candidate nodes. The number of customers is usually very large. For some models of customer behavior exact solution approaches could be used. However, for other models and/or when the size of problem is too high to solve exactly, heuristic algorithms may be used. The solution of discrete competitive facility location problems using genetic algorithms is considered in this paper. The new strategies for dynamic adjustment of some parameters of genetic algorithm, such as probabilities for the crossover and mutation operations are proposed and applied to improve the canonical genetic algorithm. The algorithm is also specially adopted to solve discrete competitive facility location problems by proposing a strategy for selection of the most promising values of the variables in the mutation procedure. The developed genetic algorithm is demonstrated by solving instances of competitive facility location problems for an entering firm.     

On multiresolution schemes using a stencil selection procedure: applications to ENO schemes

This paper is devoted to multiresolution schemes that use a stencil selection procedure in order to obtain adaptation to the presence of edges in the images. Since non adapted schemes, based on a centered stencil, are less affected by the presence of texture, we propose the introduction of some weight that leads to a more frequent use of the centered stencil in regions without edges. In these regions the different stencils have similar weights and therefore the selection becomes an ill-posed problem with high risk of instabilities. In particular, numerical artifacts appear in the decompressed images. Our attention is centered in ENO schemes, but similar ideas can be developed for other multiresolution schemes. A nonlinear multiresolution scheme corresponding to a nonlinear interpolatory technique is analyzed. It is based on a modification of classical ENO schemes. As the original ENO stencil selection, our algorithm chooses the stencil within a region of smoothness of the interpolated function if the jump discontinuity is sufficiently big. The scheme is tested, allowing to compare its performances with other linear and nonlinear schemes. The algorithm gives results that are at least competitive in all the analyzed cases. The problems of the original ENO interpolation with the texture of real images seem solved in our numerical experiments. Our modified ENO multiresolution will lead to a reconstructed image free of numerical artifacts or blurred regions, obtaining similar results than WENO schemes. Similar ideas can be used in multiresolution schemes based in other stencil selection algorithms.      

On the criterion vectors of lines of portfolio selection with multiple quadratic and multiple linear objectives

As the research for portfolio selection evolves, traditional models and models with one quadratic objective and multiple linear objectives are being solved. In this paper, I propose models with multiple quadratic and multiple linear objectives. Due to the difficulty involved, I study the new models by lines in decision space, analyze the criterion vectors of the lines by projection, and approximate the nondominated sets by the criterion vectors. As an illustration, I extend Merton’s portfolio selection model, propose algorithms to approximate the nondominated sets by the criterion vectors of portfolios with cardinality 3 and then K, and demonstrate the number of the criterion vectors.     

Analysis of crossovers and selections in a coarse-grained parallel genetic algorithm

The parallel genetic algorithms (PGA) have been developed for combinatorial optimization problems, and its parallel efficiencies have been investigated on a specific problem. These investigations were concerned with how to design a topology and the determination of the optimum setting for parameters (for example, size of subpopulations, migration interval, and so on) rather than the effectiveness of genetic operators. This paper investigates a relation between the parallel efficiency of the coarse-grained PGA and genetic (crossover and selection) operators for the traveling salesman problem on an MIMD parallel computer. The following genetic operators are considered: improved edge recombination (IERX), distance preserving (DPX), and complete subtour exchange (CSEX) crossovers, and two selection operators, which have relatively high selection pressures. Computational results indicate that the parallel efficiency is significantly affected by the difference of crossovers rather than the selections, and the PGA with CSEX gives better properties.     

A New Approach to Cycling in a 2-locus 2-allele Genetic Model

In the reproductive process new genetic types arise due to crossing over and recombination at the meiotic stage. A simplified biological model will be developed which incorporates this effect and the effect of selection. Although a chromosome may contain thousands of genes we will consider a simplified model consisting of two genetic loci, each containing two alleles of some gene.

The model will be then turned into a difference equation or mapping model x* = G(x,r) where x represents the frequency distribution of genotypes in a certain infinite population, x* is this distribution one generation later and r is the recombination parameter. For a certain choice of fitness and recombination parameters the mapping exhibits several fixed points. As r is varied one of the fixed points of the mapping loses its stability due to a conjugate pair of eigenvalues of the linearized mapping leaving the unit disk. It is shown that the required non-resonance conditions and “nonlinear damping” condition are satisfied and thus the fixed point undergoes a Neimark–Sacker bifurcation to a cycling or oscillatory state.

Once a cycling orbit is established one can conclude that genetic variation (over time) of the population can be maintained. This work reformulates and proves earlier observations of Alan Hastings in a way that makes the treatment of chromosomes with more genetic loci more straightforward.     

Variable selection for market basket analysis

Results on cross category effects obtained by explanatory market basket analyses may be biased as studies typically investigate only a small fraction of the retail assortment (Chib et al. in Advances in econometrics, vol 16. Econometric models in marketing. JAI, Amsterdam, pp 57–92, 2002). We use Bayesian variable selection techniques to determine significant cross category effects in a multivariate logit model. Hence, we achieve a reduction of coefficients to be estimated which decreases computation time heavily and thus allows to consider more product categories than most previous studies. Next to the extension of numbers of categories, the second purpose of this paper is to learn about the capabilities of different variable selection algorithms in the context of market basket analysis. We present three different approaches to variable selection and find that an adaptation of a technique by Geweke (Contemporary Bayesian econometrics and statistics. Wiley, Hoboken, 2005) meets the requirements of market basket analysis best, namely high numbers of observations and cross category effects. For a real data set, we show (1) that only a moderate fraction of possible cross category effects are significantly different from zero (one third for our data), (2) that most of these effects indicate complementarity and (3) that the number of considered product categories influences significances of cross category effects.     

Multidimensional Optimization with a Fuzzy Genetic Algorithm

We present a new heuristic method to approximate the set of Pareto-optimal solutions in multicriteria optimization problems. We use genetic algorithms with an adaptive selection mechanism. The direction of the selection pressure is adapted to the actual state of the population and forces it to explore a broad range of so far undominated solutions. The adaptation is done by a fuzzy rule-based control of the selection procedure and the fitness function. As an application we present a timetable optimization problem where we used this method to derive cost-benefit curves for the investment into railway nets. These results show that our fuzzy adaptive approach avoids most of the empirical shortcomings of other multiobjective genetic algorithms.     

New algebraic approaches to classical boundary layer problems

Classical non-steady boundary layer equations are fundamental nonlinear partial differential equations in the boundary layer theory of fluid dynamics. In this paper, we introduce various schemes with multiple parameter functions to solve these equations and obtain many families of new explicit exact solutions with multiple parameter functions. Moreover, symmetry transformations are used to simplify our arguments. The technique of moving frame is applied in the three-dimensional case in order to capture the rotational properties of the fluid. In particular, we obtain a family of solutions singular on any moving surface, which may be used to study turbulence. Many other solutions are analytic related to trigonometric and hyperbolic functions, which reflect various wave characteristics of the fluid. Our solutions may also help engineers to develop more effective algorithms to find physical numeric solutions to practical models.     

Iterative methods for solving proximal split minimization problems

In this paper, we propose two iterative algorithms for finding the minimum-norm solution of a split minimization problem. We prove strong convergence of the sequences generated by the proposed algorithms. The iterative schemes are proposed in such a way that the selection of the step-sizes does not need any prior information about the operator norm. We further give some examples to numerically verify the efficiency and implementation of our new methods and compare the two algorithms presented. Our results act as supplements to several recent important results in this area.     

Path-relinking intensification methods for stochastic local search algorithms

Path-relinking is major enhancement to heuristic search methods for solving combinatorial optimization problems, leading to significant improvements in both solution quality and running times. We review its fundamentals and implementation strategies, as well as advanced hybridizations with more elaborate metaheuristic schemes such as tabu search, GRASP, genetic algorithms and scatter search. Numerical examples are discussed and algorithms compared based on their run time distributions.     

Recent progress in unconstrained nonlinear optimization without derivatives

We present an introduction to a new class of derivative free methods for unconstrained optimization. We start by discussing the motivation for such methods and why they are in high demand by practitioners. We then review the past developments in this field, before introducing the features that characterize the newer algorithms. In the context of a trust region framework, we focus on techniques that ensure a suitable “geometric quality” of the considered models. We then outline the class of algorithms based on these techniques, as well as their respective merits. We finally conclude the paper with a discussion of open questions and perspectives. Current reports available by anonymous ftp from the directory “pub/reports” on thales.math.fundp.ac.be. WWW: http://www.fundp.ac.be/ phtoint/pht/publications.html.     

Continuous-time portfolio optimization under terminal wealth constraints

Typically portfolio analysis is based on the expected utility or the mean-variance approach. Although the expected utility approach is the more general one, practitioners still appreciate the mean-variance approach. We give a common framework including both types of selection criteria as special cases by considering portfolio problems with terminal wealth constraints. Moreover, we propose a solution method for such constrained problems.     

A random evolution related to a Fisher–Wright–Moran model with mutation,recombination and drift

The paper deals with a model of the genetic process of recombination, one of the basis mechanisms of generating genetic variability. Mathematically, the model can be represented by the so‐called random evolution of Griego and Hersch, in which a random switching process selects from among several possible modes of operation of a dynamical system. The model, introduced by Polanska and Kimmel, involves mutations in the form of a time‐continuous Markov chain and genetic drift. We demonstrate asymptotic properties of the model under different demographic scenarios for the population in which the process evolves. Copyright © 2003 John Wiley & Sons, Ltd.     

Weighted cubic and biharmonic splines

In this paper we discuss the design of algorithms for interpolating discrete data by using weighted cubic and biharmonic splines in such a way that the monotonicity and convexity of the data are preserved. We formulate the problem as a differential multipoint boundary value problem and consider its finite-difference approximation. Two algorithms for automatic selection of shape control parameters (weights) are presented. For weighted biharmonic splines the resulting system of linear equations can be efficiently solved by combining Gaussian elimination with successive over-relaxation method or finite-difference schemes in fractional steps. We consider basic computational aspects and illustrate main features of this original approach.     

Bayesian Variable Selection via Particle Stochastic Search

We focus on Bayesian variable selection in regression models. One challenge is to search the huge model space adequately, while identifying high posterior probability regions. In the past decades, the main focus has been on the use of Markov chain Monte Carlo (MCMC) algorithms for these purposes. In this article, we propose a new computational approach based on sequential Monte Carlo (SMC), which we refer to as particle stochastic search (PSS). We illustrate PSS through applications to linear regression and probit models.