Differential evolution for dynamic environments with unknown numbers of optima

This paper investigates optimization in dynamic environments where the numbers of optima are unknown or fluctuating. The authors present a novel algorithm, Dynamic Population Differential Evolution (DynPopDE), which is specifically designed for these problems. DynPopDE is a Differential Evolution based multi-population algorithm that dynamically spawns and removes populations as required. The new algorithm is evaluated on an extension of the Moving Peaks Benchmark. Comparisons with other state-of-the-art algorithms indicate that DynPopDE is an effective approach to use when the number of optima in a dynamic problem space is unknown or changing over time.     

A Tabu Search Based Approach for Solving a Class of Bilevel Programming Problems in Chemical Engineering

In this paper an approach based on the tabu search paradigm to tackle the bilevel programming problems is presented. The algorithm has been tested for a number of benchmark problems and the results obtained show superiority of the approach over the conventional methods in solving such problems.     

Problem of reconstructing a disturbance in a linear stochastic equation: The case of incomplete information

The problem of reconstructing an unknown deterministic disturbance characterizing the level of random noise in a linear stochastic second-order equation is investigated based on the approach of dynamic inversion theory. The reconstruction is performed with the use of discrete information on a number of realizations of one coordinate of the stochastic process. The problem under consideration is reduced to an inverse problem for a system of ordinary differential equations describing the covariance matrix of the original process. A finite-step solving algorithm based on the method of auxiliary controlled models is suggested. Its convergence rate with respect to the number of measured realizations is estimated.     

Efficient time integration in multiplicative inelasticity

In Shutov et al. (Comput Methods Appl Mech Eng 265:213–225, 2013), the numerical time integration of a famous large strain model of Maxwell fluid type has been considered. The underlying model is based on the multiplicative decomposition of the deformation gradient and includes a Neo-Hookean hyperelasticity relation as well as an incompressible viscous flow rule. Shutov et al. presented a time stepping algorithm for implicit time integration of the inelastic flow rule, which is based on Euler backward time discretisation, prevents error accumulation and is iteration free. In this contribution, the basic idea of the this approach is applied to more general models of multiplicative viscoelasticity. Here, extended hyperelastic relations including general functions of the first principal invariant of deformation tensors are regarded. An efficient time stepping algorithm is derived, where only one scalar equation for one scalar unknown has to be solved within every time step. The approach is applied to a specific viscoelastic model. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

Reconstruction of external actions under incomplete information in a linear stochastic equation

The problem of reconstructing unknown external actions in a linear stochastic differential equation is investigated on the basis of the approach of the theory of dynamic inversion. We consider the statement when the simultaneous reconstruction of disturbances in the deterministic and stochastic terms of the equation is performed with the use of discrete information on a number of realizations of a part of coordinates of the stochastic process. The problem is reduced to an inverse problem for systems of ordinary differential equations describing the mathematical expectation and covariance matrix of the original process. A finite-step software-oriented solution algorithm based on the method of auxiliary controlled models is proposed. We derive an estimate for its convergence rate with respect to the number of measured realizations.     

A Genetic/Tabu Thresholding Hybrid Algorithm for the Process Allocation Problem

In this paper we describe an hybrid heuristic approach, which combines Genetic Algorithms and Tabu Thresholding, for the static allocation of interacting processes onto a parallel target system, where the number of processes is greater than the number of available processors. This problem is known to be NP-hard and finds many practical applications, given the increasing diffusion of distributed and parallel computing systems.The algorithm faces infeasibilities due to processors overload by incorporating them into the objective function and by adapting the mutation operator. Global search is performed on the set of local optima obtained by a repair search operator based on a Tabu Thresholding procedure.Extensive computational testing on randomly generated instances with up to 100 processes characterized by different target network topologies with 4 to 25 processors, shows that the algorithm favorably compares with other approaches from the literature.The proposed approach has also been extended to the allocation of parallel objects and classes, where an additional co-residence constraint between each parallel object and the associated class arises.     

On oracle factoring of integers

We present an oracle factorisation algorithm, which in polynomial deterministic time, finds a nontrivial factor of almost all positive integers n based on the knowledge of the number of points on certain elliptic curves in residue rings modulo n.     

A smoothing heuristic for a bilevel pricing problem

In this paper, we provide a heuristic procedure, that performs well from a global optimality point of view, for an important and difficult class of bilevel programs. The algorithm relies on an interior point approach that can be interpreted as a combination of smoothing and implicit programming techniques. Although the algorithm cannot guarantee global optimality, very good solutions can be obtained through the use of a suitable set of parameters. The algorithm has been tested on large-scale instances of a network pricing problem, an application that fits our modeling framework. Preliminary results show that on hard instances, our approach constitutes an alternative to solvers based on mixed 0–1 programming formulations.     

QRS complex detection based on multi wavelet packet decomposition

We present in this paper a wavelet packet based QRS complex detection algorithm. Our proposed algorithm consists of a particular combination of two vectors obtained by applying a designed routine of QRS detection process using ‘haar’ and ‘db10’ wavelet functions respectively. The QRS complex detection routine is based on the histogram approach where our key idea was to search for the node with highest number of histogram coefficients, at center, which we assume that they are related to the iso-electric baseline whereas the remaining least number coefficients reflect the R waves peaks. Following a classical approach based of a calculated fixed threshold, the possible QRS complexes will be determined. The QRS detection complex algorithm has been applied to the whole MIT-BIH arrhythmia Database to assess its robustness. The algorithm reported a global sensitivity of 98.68%, positive predictive value of 97.24% and a percentage error of 04.12%. Eventhough, the obtained global results are not as excellent as expected, we have demonstrate that our designed QRS detection algorithm performs good on a partial selected high percentage of the whole database, e.g., the partial results, obtained when applying the algorithm on 85.01% of the whole MIT-BIH arrhythmia Database, are 99.14% of sensitivity, 98.94% of positive predictive value and 01.92% of percentage error.     

Application of the variation principle for the problem of buckling of a nonlinearly elastic ring nonuniform along its thickness

There has been considerable recent attention given to the stressed and buckled states of items with complicated configuration made of different nonlinearly elastic materials joined by complete adhesion. However, effective analytical solutions for such problems have been hindered by mathematical difficulties. Approximate methods have thus been developed for such problems. A variational combined principle has been formulated in this communication. A nonlinear geometrical approach has been used for formulating a mixed-type functional with physical relationships given by Euler equations, nonlinear equilibrium equations, and nonlinear boundary conditions for a piecewise-nonuniform nonlinearly elastic body composed of finite elements (particles). As an example, buckling along the nonuniform thickness of nonlinearly elastic rings was analyzed hypothetically assuming plane cross-sections. Options for two-, three-, four-, five-, and six-layered rings in a periodical structure have been reviewed. The critical buckling forces for an even number of layers have been found to be equal to each other. The ratios of the critical forces, elasticity moduli, and proportionality levels were determined for all five variants by the Runge-Kutta method.Presented at the Ninth International Conference on the Mechanics of Composite Materials (Riga, October, 1995).Translated from Mekhanika Kompozitnykh Materialov, Vol. 31, No. 2, pp. 262–268, March–April, 1995.     

Invariant G2V algorithm for computing SAGBI-Gröbner bases

Faugère and Rahmany have presented the invariant F5 algorithm to compute SAGBI-Grbner bases of ideals of invariant rings. This algorithm has an incremental structure, and it is based on the matrix version of F5 algorithm to use F5 criterion to remove a part of useless reductions. Although this algorithm is more efficient than the Buchberger-like algorithm, however it does not use all the existing criteria (for an incremental structure) to detect superfluous reductions. In this paper, we consider a new algorithm, namely, invariant G2V algorithm, to compute SAGBI-Grbner bases of ideals of invariant rings using more criteria. This algorithm has a new structure and it is based on the G2V algorithm; a variant of the F5 algorithm to compute Grbner bases. We have implemented our new algorithm in Maple , and we give experimental comparison, via some examples, of performance of this algorithm with the invariant F5 algorithm.     

Routing optimization in packet switching communication networks

For routing assignments a special model and an optimization algorithm are proposed. The efficiency of the routing assignments is evaluated by the average value of the total cost of delays for all packets in the network. It is the objective function. The main idea is that traffic, which is transmitted from the source node to the destination node, can be split between two or more logical paths. The minimum of the objective function can be found by varying the traffic on every path and simultaneously from all the source nodes to the destination nodes. If this approach is applied, then the objective function is nonseparable and nonlinear. Because its shape is unknown in advance, an adaptive nonlinear optimization algorithm is proposed. For evaluating its efficiency a special set of test functions has been used.     

Efficient algorithms for wavelength assignment on trees of rings

A fundamental problem in communication networks is wavelength assignment (WA): given a set of routing paths on a network, assign a wavelength to each path such that the paths with the same wavelength are edge-disjoint, using the minimum number of wavelengths. The WA problem is NP-hard for a tree of rings network which is well used in practice. In this paper, we give an efficient algorithm which solves the WA problem on a tree of rings with an arbitrary (node) degree using at most 3L wavelengths and achieves an approximation ratio of 2.75 asymptotically, where L is the maximum number of paths on any link in the network. The 3L upper bound is tight since there are instances of the WA problem that require 3L wavelengths even on a tree of rings with degree four. We also give a 3L and 2-approximation (resp. 2.5-approximation) algorithm for the WA problem on a tree of rings with degree at most six (resp. eight). Previous results include: 4L (resp. 3L) wavelengths for trees of rings with arbitrary degrees (resp. degree at most eight), and 2-approximation (resp. 2.5-approximation) algorithm for trees of rings with degree four (resp. six).     

A genetic algorithm for the generalised assignment problem

A new algorithm for the generalised assignment problem is described in this paper. The algorithm is adapted from a genetic algorithm which has been successfully used on set covering problems, but instead of genetically improving a set of feasible solutions it tries to genetically restore feasibility to a set of near-optimal ones. Thus it may be regarded as operating in a dual sense to the more familiar genetic approach. The algorithm has been tested on generalised assignment problems of substantial size and compared to an exact integer programming approach and a well-established heuristic approach.     

Model recovery for Hammerstein systems using the auxiliary model based orthogonal matching pursuit method

This article investigates parameter and order identification of a block-oriented Hammerstein system by using the orthogonal matching pursuit method in the compressive sensing theory which deals with how to recover a sparse signal in a known basis with a linear measurement model and a small set of linear measurements. The idea is to parameterize the Hammerstein system into the linear measurement model containing a measurement matrix with some unknown variables and a sparse parameter vector by using the key variable separation principle, then an auxiliary model based orthogonal matching pursuit algorithm is presented to recover the sparse vector.The standard orthogonal matching pursuit algorithm with a known measurement matrix is a popular recovery strategy by picking the supporting basis and the corresponding non-zero element of a sparse signal in a greedy fashion. In contrast to this, the auxiliary model based orthogonal matching pursuit algorithm has unknown variables in the measurement matrix. For a K-sparse signal, the standard orthogonal matching pursuit algorithm takes a fixed number of K stages to pick K columns (atoms) in the measurement matrix, while the auxiliary model based orthogonal matching pursuit algorithm takes steps larger than K to pick K atoms in the measurement matrix with the process of picking and deleting atoms, due to the gradually accurate estimates of the unknown variables step by step.The auxiliary model based orthogonal matching pursuit algorithm can simultaneously identify parameters and orders of the Hammerstein system, and has a high efficient identification performance.     

An Optimization Based Approach to the Train Operator Scheduling Problem at Singapore MRT

Singapore Mass Rapid Transit (SMRT) operates two train lines with 83 kilometers of track and 48 stations. A total of 77 trains are in operation during peak hours and 41 during off-peak hours. In this article we report on an optimization based approach to develop a computerized train-operator scheduling system that has been implemented at SMRT. The approach involves a bipartite matching algorithm for the generation of night duties and a tabu search algorithm for the generation of day duties. The system automates the train-operator scheduling process at SMRT and produces favorable schedules in comparison with the manual process. It is also able to handle the multiple objectives inherent in the crew scheduling system. While trying to minimize the system wide crew-related costs, the system is also able to address concern with respect to the number of split duties.     

A data assimilation process for linear ill‐posed problems

In this paper, an iteration process is considered to solve linear ill‐posed problems. Based on the randomness of the involved variables, this kind of problems is regarded as simulation problems of the posterior distribution of the unknown variable given the noise data. We construct a new ensemble Kalman filter‐based method to seek the posterior target distribution. Despite the ensemble Kalman filter method having widespread applications, there has been little analysis of its theoretical properties, especially in the field of inverse problems. This paper analyzes the propagation of the error with the iteration step for the proposed algorithm. The theoretical analysis shows that the proposed algorithm is convergence. We compare the numerical effect with the Bayesian inversion approach by two numerical examples: backward heat conduction problem and the first kind of integral equation. The numerical tests show that the proposed algorithm is effective and competitive with the Bayesian method. Copyright © 2017 John Wiley & Sons, Ltd.     

A population global optimization algorithm to solve the image alignment problem in electron crystallography

Knowledge of the structure of biological specimens is critical to understanding their function. Electron crystallography is an electron microscopy (EM) approach that derives the 3D structure of specimens at high-resolution, even at atomic detail. Prior to the tomographic reconstruction, the images taken from the microscope have to be properly aligned. Traditional alignment methods in electron crystallography are based on a phase residual function to be minimized by inefficient exhaustive search procedures. This work addresses this minimization problem from an evolutionary perspective. Universal Evolutionary Global Optimizer (UEGO), an evolutionary multimodal optimization algorithm, has been applied and evaluated for the task of image alignment in this field. UEGO has turned out to be a promising technique alternative to the standard methodology. The alignments found out by UEGO show high levels of accuracy, while reducing the number of function evaluations by a significant factor with respect to the standard method.     

An efficient ECM algorithm for maximum likelihood estimation in mixtures of t-factor analyzers

Mixture of t factor analyzers (MtFA) have been shown to be a sound model-based tool for robust clustering of high-dimensional data. This approach, which is deemed to be one of natural parametric extensions with respect to normal-theory models, allows for accommodation of potential noise components, atypical observations or data with longer-than-normal tails. In this paper, we propose an efficient expectation conditional maximization (ECM) algorithm for fast maximum likelihood estimation of MtFA. The proposed algorithm inherits all appealing properties of the ordinary EM algorithm such as its stability and monotonicity, but has a faster convergence rate since its CM steps are governed by a much smaller fraction of missing information. Numerical experiments based on simulated and real data show that the new procedure outperforms the commonly used EM and AECM algorithms substantially in most of the situations, regardless of how the convergence speed is assessed by the computing time or number of iterations.