A comparison of physical mapping algorithms based on the maximum likelihood model

MOTIVATION: Physical mapping of chromosomes using the maximum likelihood (ML) model is a problem of high computational complexity entailing both discrete optimization to recover the optimal probe order as well as continuous optimization to recover the optimal inter-probe spacings. In this paper, two versions of the genetic algorithm (GA) are proposed, one with heuristic crossover and deterministic replacement and the other with heuristic crossover and stochastic replacement, for the physical mapping problem under the maximum likelihood model. The genetic algorithms are compared with two other discrete optimization approaches, namely simulated annealing (SA) and large-step Markov chains (LSMC), in terms of solution quality and runtime efficiency. RESULTS: The physical mapping algorithms based on the GA, SA and LSMC have been tested using synthetic datasets and real datasets derived from cosmid libraries of the fungus Neurospora crassa. The GA, especially the version with heuristic crossover and stochastic replacement, is shown to consistently outperform the SA-based and LSMC-based physical mapping algorithms in terms of runtime and final solution quality. Experimental results on real datasets and simulated datasets are presented. Further improvements to the GA in the context of physical mapping under the maximum likelihood model are proposed. AVAILABILITY: The software is available upon request from the first author.     

A novel numerical optimization algorithm inspired from weed colonization

This paper introduces a novel numerical stochastic optimization algorithm inspired from colonizing weeds. Weeds are plants whose vigorous, invasive habits of growth pose a serious threat to desirable, cultivated plants making them a threat for agriculture. Weeds have shown to be very robust and adaptive to change in environment. Thus, capturing their properties would lead to a powerful optimization algorithm. It is tried to mimic robustness, adaptation and randomness of colonizing weeds in a simple but effective optimizing algorithm designated as Invasive Weed Optimization (IWO). The feasibility, the efficiency and the effectiveness of IWO are tested in details through a set of benchmark multi-dimensional functions, of which global and local minima are known. The reported results are compared with other recent evolutionary-based algorithms: genetic algorithms, memetic algorithms, particle swarm optimization, and shuffled frog leaping. The results are also compared with different versions of simulated annealing — a generic probabilistic meta-algorithm for the global optimization problem — which are simplex simulated annealing, and direct search simulated annealing. Additionally, IWO is employed for finding a solution for an engineering problem, which is optimization and tuning of a robust controller. The experimental results suggest that results from IWO are better than results from other methods. In conclusion, the performance of IWO has a reasonable performance for all the test functions.     

Modeling and design optimization of asynchronous flexible assembly systems with statistical process control and repair

This article presents the implementation of hybrid procedures involving the use of analytical performance evaluation techniques, discrete event simulation, and Monte Carlo optimization methods for the stochastic design optimization of asynchronous flexible assembly systems (AFASs) with statistical process control (SPC) and repair loops. AFASs are extremely complex and difficult to analyze in that such systems are subject to starvation and blocking effects, random jam occurrences at workstations, and splitting and merging of the assembly flow due to repair loops. Hence, an integrated approach simultaneously analyzing the interactions between product quality and optimal/near optimal system design is pursued. In the analytical analysis stage, a model based on GI/G/1 queueing network theory is used. In the Monte Carlo optimization stage, two alternative stochastic optimization approaches, namely, heuristic versions of stochastic quasigradient and simulated annealing algorithms, are implemented and compared in terms of their capabilities of solving complex AFAS design problems. The hybrid procedures presented appear to perform reasonably well in designing AFASs to reach a target production rate.     

Genetic Algorithm Based Scheduling of Meta-Tasks with Stochastic Execution Times in Heterogeneous Computing Systemst1

In this study, we address the meta-task scheduling problem in heterogeneous computing (HC) systems, which is to find a task assignment that minimizes the schedule length of a meta-task composed of several independent tasks with no data dependencies. The fact that the meta-task scheduling problem in HC systems is NP-hard has motivated the development of many heuristic scheduling algorithms. These heuristic algorithms, however, neglect the stochastic nature of task execution times in an attempt to minimize a deterministic objective function, which is the maximum of the expected values of machine loads. Contrary to existing heuristics, we account for this stochastic nature by modeling task execution times as random variables. We, then, formulate a stochastic scheduling problem where the objective is to minimize the expected value of the maximum of machine loads. We prove that this new objective is underestimated by the deterministic objective function and that an optimal task assignment obtained with respect to the deterministic objective function could be inefficient in a real computing platform. In order to solve the stochastic scheduling problem posed, we develop a genetic algorithm based scheduling heuristic. Our extensive simulation studies show that the proposed genetic algorithm can produce better task assignments as compared to existing heuristics. Specifically, we observe a performance improvement on the relative cost heuristic (M.-Y. Wu and W. Shu, A high-performance mapping algorithm for heterogeneous computing systems, in: Int. Parallel and Distributed Processing Symposium, San Francisco, CA, April 2001) by up to 61%.     

Self-adaptive particle swarm optimization: a review and analysis of convergence

Particle swarm optimization (PSO) is a population-based, stochastic search algorithm inspired by the flocking behaviour of birds. The PSO algorithm has been shown to be rather sensitive to its control parameters, and thus, performance may be greatly improved by employing appropriately tuned parameters. However, parameter tuning is typically a time-intensive empirical process. Furthermore, a priori parameter tuning makes the implicit assumption that the optimal parameters of the PSO algorithm are not time-dependent. To address these issues, self-adaptive particle swarm optimization (SAPSO) algorithms adapt their control parameters throughout execution. While there is a wide variety of such SAPSO algorithms in the literature, their behaviours are not well understood. Specifically, it is unknown whether these SAPSO algorithms will even exhibit convergent behaviour. This paper addresses this lack of understanding by investigating the convergence behaviours of 18 SAPSO algorithms both analytically and empirically. This paper also empirically examines whether the adapted parameters reach a stable point and whether the final parameter values adhere to a well-known convergence criterion. The results depict a grim state for SAPSO algorithms; over half of the SAPSO algorithms exhibit divergent behaviour while many others prematurely converge.     

Minimizing stochastic complexity using local search and GLA with applications to classification of bacteria

In this paper, we compare the performance of two iterative clustering methods when applied to an extensive data set describing strains of the bacterial family Enterobacteriaceae. In both methods, the classification (i.e. the number of classes and the partitioning) is determined by minimizing stochastic complexity. The first method performs the minimization by repeated application of the generalized Lloyd algorithm (GLA). The second method uses an optimization technique known as local search (LS). The method modifies the current solution by making global changes to the class structure and it, then, performs local fine-tuning to find a local optimum. It is observed that if we fix the number of classes, the LS finds a classification with a lower stochastic complexity value than GLA. In addition, the variance of the solutions is much smaller for the LS due to its more systematic method of searching. Overall, the two algorithms produce similar classifications but they merge certain natural classes with microbiological relevance in different ways.     

Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.     

Folding small proteins via annealing stochastic approximation Monte Carlo

Recently, the stochastic approximation Monte Carlo algorithm has been proposed by Liang et al. (2007) as a general-purpose stochastic optimization and simulation algorithm. An annealing version of this algorithm was developed for real small protein folding problems. The numerical results indicate that it outperforms simulated annealing and conventional Monte Carlo algorithms as a stochastic optimization algorithm. We also propose one method for the use of secondary structures in protein folding. The predicted protein structures are rather close to the true structures.     

Optimizing exact genetic linkage computations.

Genetic linkage analysis is a challenging application which requires Bayesian networks consisting of thousands of vertices. Consequently, computing the probability of data, which is needed for learning linkage parameters, using exact computation procedures calls for an extremely efficient implementation that carefully optimizes the order of conditioning and summation operations. In this paper, we present the use of stochastic greedy algorithms for optimizing this order. Our algorithm has been incorporated into the newest version of SUPERLINK, which is a fast genetic linkage program for exact likelihood computations in general pedigrees. We demonstrate an order of magnitude improvement in run times of likelihood computations using our new optimization algorithm and hence enlarge the class of problems that can be handled effectively by exact computations.     

A cooperative particle swarm optimizer with migration of heterogeneous probabilistic models

Particle Swarm Optimization (PSO) is a stochastic optimization approach that originated from simulations of bird flocking, and that has been successfully used in many applications as an optimization tool. Estimation of distribution algorithms (EDAs) are a class of evolutionary algorithms which perform a two-step process: building a probabilistic model from which good solutions may be generated and then using this model to generate new individuals. Two distinct research trends that emerged in the past few years are the hybridization of PSO and EDA algorithms and the parallelization of EDAs to exploit the idea of exchanging the probabilistic model information. In this work, we propose the use of a cooperative PSO/EDA algorithm based on the exchange of heterogeneous probabilistic models. The model is heterogeneous because the cooperating PSO/EDA algorithms use different methods to sample the search space. Three different exchange approaches are tested and compared in this work. In all these approaches, the amount of information exchanged is adapted based on the performance of the two cooperating swarms. The performance of the cooperative model is compared to the existing state-of-the-art PSO cooperative approaches using a suite of well-known benchmark optimization functions.     

Continuous optimization algorithms for tuning real and integer parameters of swarm intelligence algorithms

The performance of optimization algorithms, including those based on swarm intelligence, depends on the values assigned to their parameters. To obtain high performance, these parameters must be fine-tuned. Since many parameters can take real values or integer values from a large domain, it is often possible to treat the tuning problem as a continuous optimization problem. In this article, we study the performance of a number of prominent continuous optimization algorithms for parameter tuning using various case studies from the swarm intelligence literature. The continuous optimization algorithms that we study are enhanced to handle the stochastic nature of the tuning problem. In particular, we introduce a new post-selection mechanism that uses F-Race in the final phase of the tuning process to select the best among elite parameter configurations. We also examine the parameter space of the swarm intelligence algorithms that we consider in our study, and we show that by fine-tuning their parameters one can obtain substantial improvements over default configurations.     

Multiscale Stochastic Reaction–Diffusion Modeling: Application to Actin Dynamics in Filopodia

Two multiscale (hybrid) stochastic reaction–diffusion models of actin dynamics in a filopodium are investigated. Both hybrid algorithms combine compartment-based and molecular-based stochastic reaction–diffusion models. The first hybrid model is based on the models previously developed in the literature. The second hybrid model is based on the application of a recently developed two-regime method (TRM) to a fully molecular-based model, which is also developed in this paper. The results of hybrid models are compared with the results of the molecular-based model. It is shown that both approaches give comparable results, although the TRM model better agrees quantitatively with the molecular-based model.     

Adaptive optimization of fed-batch culture of yeast by using genetic algorithms

A simulation and experimental study has been carried out on the adaptive optimization of fed-batch culture of yeast. In the simulation study, three genetic algorithms based on different optimization strategies were developed. The performance of those three algorithms were compared with one another and with that of a variational calculus approach. The one that showed the best performance was selected to be used in the subsequent experimental study. To confer an adaptability, an online adaptation (or model update) algorithm was developed and incorporated into the selected optimization algorithm. The resulting adaptive algorithm was experimentally applied to fed-batch cultures of a recombinant yeast producing salmon calcitonin, to maximize the cell mass production. It followed the actual process quite well and gave a much higher value of performance index than the simple genetic algorithm with no adaptability.     

Genetic programming assisted stochastic optimization strategies for optimization of glucose to gluconic acid fermentation

This article presents two hybrid strategies for the modeling and optimization of the glucose to gluconic acid batch bioprocess. In the hybrid approaches, first a novel artificial intelligence formalism, namely, genetic programming (GP), is used to develop a process model solely from the historic process input-output data. In the next step, the input space of the GP-based model, representing process operating conditions, is optimized using two stochastic optimization (SO) formalisms, viz., genetic algorithms (GAs) and simultaneous perturbation stochastic approximation (SPSA). These SO formalisms possess certain unique advantages over the commonly used gradient-based optimization techniques. The principal advantage of the GP-GA and GP-SPSA hybrid techniques is that process modeling and optimization can be performed exclusively from the process input-output data without invoking the detailed knowledge of the process phenomenology. The GP-GA and GP-SPSA techniques have been employed for modeling and optimization of the glucose to gluconic acid bioprocess, and the optimized process operating conditions obtained thereby have been compared with those obtained using two other hybrid modeling-optimization paradigms integrating artificial neural networks (ANNs) and GA/SPSA formalisms. Finally, the overall optimized operating conditions given by the GP-GA method, when verified experimentally resulted in a significant improvement in the gluconic acid yield. The hybrid strategies presented here are generic in nature and can be employed for modeling and optimization of a wide variety of batch and continuous bioprocesses.     

Energy-aware task scheduling in heterogeneous computing environments

Efficient application scheduling is critical for achieving high performance in heterogeneous computing (HC) environments. Because of such importance, there are many researches on this problem and various algorithms have been proposed. Duplication-based algorithms are one kind of well known algorithms to solve scheduling problems, which achieve high performance on minimizing the overall completion time (makespan) of applications. However, they pursuit of the shortest makespan overly by duplicating some tasks redundantly, which leads to a large amount of energy consumption and resource waste. With the growing advocacy for green computing systems, energy conservation has been an important issue and gained a particular interest. An existing technique to reduce energy consumption of an application is dynamic voltage/frequency scaling (DVFS), whose efficiency is affected by the overhead of time and energy caused by voltage scaling. In this paper, we propose a new energy-aware scheduling algorithm with reduced task duplication called Energy-Aware Scheduling by Minimizing Duplication (EAMD), which takes the energy consumption as well as the makespan of an application into consideration. It adopts a subtle energy-aware method to search and delete redundant task copies in the schedules generated by duplication-based algorithms, and it is easier to operate than DVFS, and produces no extra time and energy consumption. This algorithm not only consumes less energy but also maintains good performance in terms of makespan compared with duplication-based algorithms. Two kinds of DAGs, i.e., randomly generated graphs and two real-world application graphs, are tested in our experiments. Experimental results show that EAMD can save up to 15.59 % energy consumption for HLD and HCPFD, two classic duplication-based algorithms. Several factors affecting the performance are also analyzed in the paper.     

Optimum DNA curvature using a hybrid approach involving an artificial neural network and genetic algorithm

In the present paper, a hybrid technique involving artificial neural network (ANN) and genetic algorithm (GA) has been proposed for performing modeling and optimization of complex biological systems. In this approach, first an ANN approximates (models) the nonlinear relationship(s) existing between its input and output example data sets. Next, the GA, which is a stochastic optimization technique, searches the input space of the ANN with a view to optimize the ANN output. The efficacy of this formalism has been tested by conducting a case study involving optimization of DNA curvature characterized in terms of the RL value. Using the ANN-GA methodology, a number of sequences possessing high RL values have been obtained and analyzed to verify the existence of features known to be responsible for the occurrence of curvature. A couple of sequences have also been tested experimentally. The experimental results validate qualitatively and also near-quantitatively, the solutions obtained using the hybrid formalism. The ANN-GA technique is a useful tool to obtain, ahead of experimentation, sequences that yield high RL values. The methodology is a general one and can be suitably employed for optimizing any other biological feature.     

Optimization of β-Cyclodextrin-Assisted Extraction of Apigenin and Luteolin from Chrysanthemum indicum L. Using Response Surface Methodology Combined with Different Optimization Algorithms and Evaluation of Its Antioxidant Capacity

Cyclodextrins and their derivatives have shown successful applications in extracting active compounds from medicinal plants. However, the use of β-cyclodextrin derivatives for extracting apigenin and luteolin from Chrysanthemum indicum L. remains unexplored. Additionally, the application of nature-inspired optimization algorithms in optimizing extraction conditions has been limited. Therefore, this study was performed with the aims of optimizing the extraction of apigenin and luteolin from C. indicum with the assistance of 2-hydroxypropyl-β-cyclodextrin (HP-β-CD) using response surface methodology combined with various optimization algorithms, including desirability function approach, genetic algorithm, particle swarm optimization, and firefly algorithm. The results showed that the optimal conditions obtained by the four algorithms were consistent, with an extraction time of 60 min, HP-β-CD concentration of 30 mg/mL, and a solvent-to-solid ratio of 24 mg/mL. At these conditions, the apigenin and luteolin contents were 1.362±0.008 and 8.724±0.117 mg/g, respectively. The results also showed that HP-β-CD-assisted extraction exhibited significantly higher apigenin and luteolin contents compared to conventional solvent. Comparable results were also yielded from the antioxidant assay. Our study suggested that the nature-inspired optimization algorithms might be potential options in enhancing the effectiveness of the traditional response surface methodology for the optimization of extraction of natural products.     

An LMI approach to design H(infinity) controllers for discrete-time nonlinear systems based on unified models

A unified neural network model termed standard neural network model (SNNM) is advanced. Based on the robust L(2) gain (i.e. robust H(infinity) performance) analysis of the SNNM with external disturbances, a state-feedback control law is designed for the SNNM to stabilize the closed-loop system and eliminate the effect of external disturbances. The control design constraints are shown to be a set of linear matrix inequalities (LMIs) which can be easily solved by various convex optimization algorithms (e.g. interior-point algorithms) to determine the control law. Most discrete-time recurrent neural network (RNNs) and discrete-time nonlinear systems modelled by neural networks or Takagi and Sugeno (T-S) fuzzy models can be transformed into the SNNMs to be robust H(infinity) performance analyzed or robust H(infinity) controller synthesized in a unified SNNM's framework. Finally, some examples are presented to illustrate the wide application of the SNNMs to the nonlinear systems, and the proposed approach is compared with related methods reported in the literature.     

Stochastic and deterministic simulations of heterogeneous cell population dynamics

A Monte Carlo algorithm, which can accurately simulate the dynamics of entire heterogeneous cell populations, was developed. The algorithm takes into account the random nature of cell division as well as unequal partitioning of cellular material at cell division. Moreover, it is general in the sense that it can accommodate a variety of single-cell, deterministic reaction kinetics as well as various stochastic division and partitioning mechanisms. The validity of the algorithm was assessed through comparison of its results with those of the corresponding deterministic cell population balance model in cases where stochastic behavior is expected to be quantitatively negligible. Both algorithms were applied to study: (a) linear intracellular kinetics and (b) the expression dynamics of a genetic network with positive feedback architecture, such as the lac operon. The effects of stochastic division as well as those of different division and partitioning mechanisms were assessed in these systems, while the comparison of the stochastic model with a continuum model elucidated the significance of cell population heterogeneity even in cases where only the prediction of average properties is of primary interest.