Simulated parallel annealing within a neighborhood for optimization of biomechanical systems

Optimization problems for biomechanical systems have become extremely complex. Simulated annealing (SA) algorithms have performed well in a variety of test problems and biomechanical applications; however, despite advances in computer speed, convergence to optimal solutions for systems of even moderate complexity has remained prohibitive. The objective of this study was to develop a portable parallel version of a SA algorithm for solving optimization problems in biomechanics. The algorithm for simulated parallel annealing within a neighborhood (SPAN) was designed to minimize interprocessor communication time and closely retain the heuristics of the serial SA algorithm. The computational speed of the SPAN algorithm scaled linearly with the number of processors on different computer platforms for a simple quadratic test problem and for a more complex forward dynamic simulation of human pedaling.     

Evaluation of a particle swarm algorithm for biomechanical optimization

Optimization is frequently employed in biomechanics research to solve system identification problems, predict human movement, or estimate muscle or other internal forces that cannot be measured directly. Unfortunately, biomechanical optimization problems often possess multiple local minima, making it difficult to find the best solution. Furthermore, convergence in gradient-based algorithms can be affected by scaling to account for design variables with different length scales or units. In this study we evaluate a recently-developed version of the particle swarm optimization (PSO) algorithm to address these problems. The algorithm's global search capabilities were investigated using a suite of difficult analytical test problems, while its scale-independent nature was proven mathematically and verified using a biomechanical test problem. For comparison, all test problems were also solved with three off-the-shelf optimization algorithms--a global genetic algorithm (GA) and multistart gradient-based sequential quadratic programming (SQP) and quasi-Newton (BFGS) algorithms. For the analytical test problems, only the PSO algorithm was successful on the majority of the problems. When compared to previously published results for the same problems, PSO was more robust than a global simulated annealing algorithm but less robust than a different, more complex genetic algorithm. For the biomechanical test problem, only the PSO algorithm was insensitive to design variable scaling, with the GA algorithm being mildly sensitive and the SQP and BFGS algorithms being highly sensitive. The proposed PSO algorithm provides a new off-the-shelf global optimization option for difficult biomechanical problems, especially those utilizing design variables with different length scales or units.     

Multiple sequence alignment by parallel simulated annealing

We have developed simulated annealing algorithms to solve theproblem of multiple sequence alignment. The algorithm wns shownto give the optimal solution as confirmed by the rigorous dynamicprogramming algorithm for three-sequence alignment. To overcomelong execution times for simulated annealing, we utilized aparallel computer. A sequential algorithm, a simple parallelalgorithm and the temperature parallel algorithm were testedon a problem. The results were compared with the result obtainedby a conventional tree-based algorithm where alignments weremerged by two-' dynamic programming. Every annealing algorithmproduced a better energy value than the conventional algorithm.The best energy value, which probably represents the optimalsolution, wns reached within a reasonable time by both of theparallel annealing algorithms. We consider the temperature parallelalgorithm of simulated annealing to be the most suitable forfinding the optimal multiple sequence alignment because thealgorithm does not require any scheduling for optimization.The algorithm is also usefiui for refining multiple alignmentsobtained by other hewistic methods.     

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.     

Generating dynamic simulations of movement using computed muscle control

Computation of muscle excitation patterns that produce coordinated movements of muscle-actuated dynamic models is an important and challenging problem. Using dynamic optimization to compute excitation patterns comes at a large computational cost, which has limited the use of muscle-actuated simulations. This paper introduces a new algorithm, which we call computed muscle control, that uses static optimization along with feedforward and feedback controls to drive the kinematic trajectory of a musculoskeletal model toward a set of desired kinematics. We illustrate the algorithm by computing a set of muscle excitations that drive a 30-muscle, 3-degree-of-freedom model of pedaling to track measured pedaling kinematics and forces. Only 10 min of computer time were required to compute muscle excitations that reproduced the measured pedaling dynamics, which is over two orders of magnitude faster than conventional dynamic optimization techniques. Simulated kinematics were within 1 degrees of experimental values, simulated pedal forces were within one standard deviation of measured pedal forces for nearly all of the crank cycle, and computed muscle excitations were similar in timing to measured electromyographic patterns. The speed and accuracy of this new algorithm improves the feasibility of using detailed musculoskeletal models to simulate and analyze movement.     

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.     

A dynamic optimization technique for predicting muscle forces in the swing phase of gait

The muscle force sharing problem was solved for the swing phase of gait using a dynamic optimization algorithm. For comparison purposes the problem was also solved using a typical static optimization algorithm. The objective function for the dynamic optimization algorithm was a combination of the tracking error and the metabolic energy consumption. The latter quantity was taken to be the sum of the total work done by the muscles and the enthalpy change during the contraction. The objective function for the static optimization problem was the sum of the cubes of the muscle stresses. To solve the problem using the static approach, the inverse dynamics problem was first solved in order to determine the resultant joint torques required to generate the given hip, knee and ankle trajectories. To this effect the angular velocities and accelerations were obtained by numerical differentiation using a low-pass digital filter. The dynamic optimization problem was solved using the Fletcher-Reeves conjugate gradient algorithm, and the static optimization problem was solved using the Gradient-restoration algorithm. The results show influence of internal muscle dynamics on muscle control histories vis a vis muscle forces. They also illustrate the strong sensitivity of the results to the differentiation procedure used in the static optimization approach.     

A general-purpose framework to simulate musculoskeletal system of human body: using a motion tracking approach*

Computation of muscle force patterns that produce specified movements of muscle-actuated dynamic models is an important and challenging problem. This problem is an undetermined one, and then a proper optimization is required to calculate muscle forces. The purpose of this paper is to develop a general model for calculating all muscle activation and force patterns in an arbitrary human body movement. For this aim, the equations of a multibody system forward dynamics, which is considered for skeletal system of the human body model, is derived using Lagrange–Euler formulation. Next, muscle contraction dynamics is added to this model and forward dynamics of an arbitrary musculoskeletal system is obtained. For optimization purpose, the obtained model is used in computed muscle control algorithm, and a closed-loop system for tracking desired motions is derived. Finally, a popular sport exercise, biceps curl, is simulated by using this algorithm and the validity of the obtained results is evaluated via EMG signals.     

Two hybrid compaction algorithms for the layout optimization problem

In this paper we present two new algorithms for the layout optimization problem: this concerns the placement of circular, weighted objects inside a circular container, the two objectives being to minimize imbalance of mass and to minimize the radius of the container. This problem carries real practical significance in industrial applications (such as the design of satellites), as well as being of significant theoretical interest. We present two nature-inspired algorithms for this problem, the first based on simulated annealing, and the second on particle swarm optimization. We compare our algorithms with the existing best-known algorithm, and show that our approaches out-perform it in terms of both solution quality and execution time.     

An algorithm combining discrete and continuous methods for optical mapping.

Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested copies of it, using fluorescence microscopy. The real-life problem is complicated by numerous factors: false positive and false negative cut observations, inaccurate location measurements, unknown orientations, and faulty molecules. We present an algorithm for solving the real-life problem. The algorithm combines continuous optimization and combinatorial algorithms applied to a nonuniform discretization of the data. We present encouraging results on real experimental data and on simulated data.     

A theoretical analysis of preferred pedaling rate selection in endurance cycling

One objective of this study was to investigate whether neuromuscular quantities were associated with preferred pedaling rate selection during submaximal steady-state cycling from a theoretical perspective using a musculoskeletal model with an optimal control analysis. Specific neuromuscular quantities of interest were the individual muscle activation, force, stress and endurance. To achieve this objective, a forward dynamic model of cycling and optimization framework were used to simulate pedaling at three different rates of 75, 90 and 105 rpm at 265 W. The pedaling simulations were produced by optimizing the individual muscle excitation timing and magnitude to reproduce experimentally collected data. The results from these pedaling simulations indicated that all neuromuscular quantities were minimized at 90 rpm when summed across muscles. In the context of endurance cycling, these results suggest that minimizing neuromuscular fatigue is an important mechanism in pedaling rate selection. A second objective was to determine whether any of these quantities could be used to predict the preferred pedaling rate. By using the quantities with the strongest quadratic trends as the performance criterion to be minimized in an optimal control analysis, these quantities were analyzed to assess whether they could be further minimized at 90 rpm and produce normal pedaling mechanics. The results showed that both the integrated muscle activation and average endurance summed across all muscles could be further minimized at 90 rpm indicating that these quantities cannot be used individually to predict preferred pedaling rates.     

Optimal vaccination schedules using simulated annealing

SUMMARY: Since few years the problem of finding optimal solutions for drug or vaccine protocols have been tackled using system biology modeling. These approaches are usually computationally expensive. Our previous experiences in optimizing vaccine or drug protocols using genetic algorithms required the use of a high performance computing infrastructure for a couple of days. In the present article we show that by an appropriate use of a different optimization algorithm, the simulated annealing, we have been able to downsize the computational effort by a factor 10(2). The new algorithm requires computational effort that can be achieved by current generation personal computers. AVAILABILITY: Software and additional data can be found at http://www.immunomics.eu/SA/     

Evaluation of performance criteria for simulation of submaximal steady-state cycling using a forward dynamic model.

The objectives of this study were twofold. The first was to develop a forward dynamic model of cycling and an optimization framework to simulate pedaling during submaximal steady-state cycling conditions. The second was to use the model and framework to identify the kinetic, kinematic, and muscle timing quantities that should be included in a performance criterion to reproduce natural pedaling mechanics best during these pedaling conditions. To make this identification, kinetic and kinematic data were collected from 6 subjects who pedaled at 90 rpm and 225 W. Intersegmental joint moments were computed using an inverse dynamics technique and the muscle excitation onset and offset were taken from electromyographic (EMG) data collected previously (Neptune et al., 1997). Average cycles and their standard deviations for the various quantities were used to describe normal pedaling mechanics. The model of the bicycle-rider system was driven by 15 muscle actuators per leg. The optimization framework determined both the timing and magnitude of the muscle excitations to simulate pedaling at 90 rpm and 225 W. Using the model and optimization framework, seven performance criteria were evaluated. The criterion that included all of the kinematic and kinetic quantities combined with the EMG timing was the most successful in replicating the experimental data. The close agreement between the simulation results and the experimentally collected kinetic, kinematic, and EMG data gives confidence in the model to investigate individual muscle coordination during submaximal steady-state pedaling conditions from a theoretical perspective, which to date has only been performed experimentally.     

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.     

Determining residual reduction algorithm kinematic tracking weights for a sidestep cut via numerical optimization

Musculoskeletal modeling allows for the determination of various parameters during dynamic maneuvers by using in vivo kinematic and ground reaction force (GRF) data as inputs. Differences between experimental and model marker data and inconsistencies in the GRFs applied to these musculoskeletal models may not produce accurate simulations. Therefore, residual forces and moments are applied to these models in order to reduce these differences. Numerical optimization techniques can be used to determine optimal tracking weights of each degree of freedom of a musculoskeletal model in order to reduce differences between the experimental and model marker data as well as residual forces and moments. In this study, the particle swarm optimization (PSO) and simplex simulated annealing (SIMPSA) algorithms were used to determine optimal tracking weights for the simulation of a sidestep cut. The PSO and SIMPSA algorithms were able to produce model kinematics that were within 1.4° of experimental kinematics with residual forces and moments of less than 10 N and 18 Nm, respectively. The PSO algorithm was able to replicate the experimental kinematic data more closely and produce more dynamically consistent kinematic data for a sidestep cut compared to the SIMPSA algorithm. Future studies should use external optimization routines to determine dynamically consistent kinematic data and report the differences between experimental and model data for these musculoskeletal simulations.     

Sloped muscle excitation waveforms improve the accuracy of forward dynamic simulations

Mathematical models of the muscle excitation are useful in forward dynamic simulations of human movement tasks. One objective was to demonstrate that sloped as opposed to rectangular excitation waveforms improve the accuracy of forward dynamic simulations. A second objective was to demonstrate the differences in simulated muscle forces using sloped versus rectangular waveforms. To fulfill these objectives, surface EMG signals from the triceps brachii and elbow joint angle were recorded and the intersegmental moment of the elbow joint was computed from 14 subjects who performed two cyclic elbow extension experiments at 200 and 300 deg/s. Additionally, the surface EMG signals from the leg musculature, joint angles, and pedal forces were recorded and joint intersegmental moments were computed during a more complex pedaling task (90 rpm at 250 W). Using forward dynamic simulations, four optimizations were performed in which the experimental intersegmental moment was tracked for the elbow extension tasks and four optimizations were performed in which the experimental pedal angle, pedal forces, and joint intersegmental moments were tracked for the pedaling task. In these optimizations the three parameters (onset and offset time, and peak excitation) defining the sloped (triangular, quadratic, and Hanning) and rectangular excitation waveforms were varied to minimize the difference between the simulated and experimentally tracked quantities. For the elbow extension task, the intersegmental elbow moment root mean squared error, onset timing error, and offset timing error were less from simulations using a sloped excitation waveform compared to a rectangular excitation waveform (p<0.001). The average and peak muscle forces were from 7% to 16% larger and 20-28% larger, respectively, when using a rectangular excitation waveform. The tracking error for pedaling also decreased when using a sloped excitation waveform, with the quadratic waveform generating the smallest tracking errors for both tasks. These results support the use of sloped over rectangular excitation waveforms to establish greater confidence in the results of forward dynamic simulations.     

Biomimicry of symbiotic multi-species coevolution for discrete and continuous optimization in RFID networks

In recent years, symbiosis as a rich source of potential engineering applications and computational model has attracted more and more attentions in the adaptive complex systems and evolution computing domains. Inspired by different symbiotic coevolution forms in nature, this paper proposed a series of multi-swarm particle swarm optimizers called PS²Os, which extend the single population particle swarm optimization (PSO) algorithm to interacting multi-swarms model by constructing hierarchical interaction topologies and enhanced dynamical update equations. According to different symbiotic interrelationships, four versions of PS²O are initiated to mimic mutualism, commensalism, predation, and competition mechanism, respectively. In the experiments, with five benchmark problems, the proposed algorithms are proved to have considerable potential for solving complex optimization problems. The coevolutionary dynamics of symbiotic species in each PS²O version are also studied respectively to demonstrate the heterogeneity of different symbiotic interrelationships that effect on the algorithm’s performance. Then PS²O is used for solving the radio frequency identification (RFID) network planning (RNP) problem with a mixture of discrete and continuous variables. Simulation results show that the proposed algorithm outperforms the reference algorithms for planning RFID networks, in terms of optimization accuracy and computation robustness.     

Parallel computation of a maximum-likelihood estimator of a physical map

Reconstructing a physical map of a chromosome from a genomic library presents a central computational problem in genetics. Physical map reconstruction in the presence of errors is a problem of high computational complexity that provides the motivation for parallel computing. Parallelization strategies for a maximum-likelihood estimation-based approach to physical map reconstruction are presented. The estimation procedure entails a gradient descent search for determining the optimal spacings between probes for a given probe ordering. The optimal probe ordering is determined using a stochastic optimization algorithm such as simulated annealing or microcanonical annealing. A two-level parallelization strategy is proposed wherein the gradient descent search is parallelized at the lower level and the stochastic optimization algorithm is simultaneously parallelized at the higher level. Implementation and experimental results on a distributed-memory multiprocessor cluster running the parallel virtual machine (PVM) environment are presented using simulated and real hybridization data.     

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.     

Time Varying Optimization for Monitoring Multiple Contaminants under Uncertain Hydrogeology

This study presents a method for identifying cost effective sampling designs for long-term monitoring of remediation of groundwater over multiple monitoring periods under uncertain flow conditions. A contaminant transport model is used to simulate plume migration under many equally likely stochastic hydraulic conductivity fields and provides representative samples of contaminant concentrations. Monitoring costs are minimized under a constraint to meet an acceptable level of error in the estimation of total mass for multiple contaminants simultaneously over many equiprobable realizations of hydraulic conductivity field. A new myopic heuristic algorithm (MS-ER) that combines a new error-reducing search neighborhood is developed to solve the optimization problem. A simulated annealing algorithm using the error-reducing neighborhood (SA-ER) and a genetic algorithm (GA) are also considered for solving the optimization problem. The method is applied to a hypothetical aquifer where enhanced anaerobic bioremediation of four toxic chlorinated ethene species is modeled using a complex contaminant transport model. The MS-ER algorithm consistently performed better in multiple trials of each algorithm when compared to SA-ER and GA. The best design of MS-ER algorithm produced a savings of nearly 25% in project cost over a conservative sampling plan that uses all possible locations and samples.