An annealed chaotic maximum neural network for bipartite subgraph problem

In this paper, based on maximum neural network, we propose a new parallel algorithm that can help the maximum neural network escape from local minima by including a transient chaotic neurodynamics for bipartite subgraph problem. The goal of the bipartite subgraph problem, which is an NP- complete problem, is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. Lee et al. presented a parallel algorithm using the maximum neural model (winner-take-all neuron model) for this NP- complete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parameter-tuning. However, the model has a tendency to converge to a local minimum easily because it is based on the steepest descent method. By adding a negative self-feedback to the maximum neural network, we proposed a new parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm. The simulation results show that our algorithm finds the optimum or near-optimum solution for the bipartite subgraph problem superior to that of the best existing parallel algorithms.     

Energy landscapes and properties of biomolecules

Thermodynamic and dynamic properties of biomolecules can be calculated using a coarse-grained approach based upon sampling stationary points of the underlying potential energy surface. The superposition approximation provides an overall partition function as a sum of contributions from the local minima, and hence functions such as internal energy, entropy, free energy and the heat capacity. To obtain rates we must also sample transition states that link the local minima, and the discrete path sampling method provides a systematic means to achieve this goal. A coarse-grained picture is also helpful in locating the global minimum using the basin-hopping approach. Here we can exploit a fictitious dynamics between the basins of attraction of local minima, since the objective is to find the lowest minimum, rather than to reproduce the thermodynamics or dynamics.     

Accelerated Simplified Swarm Optimization with Exploitation Search Scheme for Data Clustering

Data clustering is commonly employed in many disciplines. The aim of clustering is to partition a set of data into clusters, in which objects within the same cluster are similar and dissimilar to other objects that belong to different clusters. Over the past decade, the evolutionary algorithm has been commonly used to solve clustering problems. This study presents a novel algorithm based on simplified swarm optimization, an emerging population-based stochastic optimization approach with the advantages of simplicity, efficiency, and flexibility. This approach combines variable vibrating search (VVS) and rapid centralized strategy (RCS) in dealing with clustering problem. VVS is an exploitation search scheme that can refine the quality of solutions by searching the extreme points nearby the global best position. RCS is developed to accelerate the convergence rate of the algorithm by using the arithmetic average. To empirically evaluate the performance of the proposed algorithm, experiments are examined using 12 benchmark datasets, and corresponding results are compared with recent works. Results of statistical analysis indicate that the proposed algorithm is competitive in terms of the quality of solutions.     

A neural network for the Steiner minimal tree problem

The problem of finding the shortest tree connecting a set of points is called the Steiner minimal tree problem and is nearly three centuries old. It has applications in transportation, computer networks, agriculture, telephony, building layout and very large scale integrated circuit (VLSI) design, among others, and is known to be NP-complete. We propose a neural network which self-organizes to find a minimal tree. Solutions found by the network compare favourably with the best known or optimal results on test problems from the literature. To the best of our knowledge, the proposed network is the first neural-based solution to the problem. We show that the neural network has a built-in mechanism to escape local minima.     

Alopex-B: a new, simpler, but yet faster version of the alopex training algorithm

Experimenting with some changes and simplifications to the Alopex algorithm, we obtained a new faster version (Alopex-B), that also shows lower failure rates on training attempts. Like Alopex, our version is network-architecture independent, does not require error or transfer functions to be differentiable, has a high potential for parallelism, and is stochastic (which helps avoid local minima), but unlike Alopex it follows no annealing scheme, and uses less parameters which makes it simpler to implement and to use.     

Approximating the set of local minima in partial RNA folding landscapes

MOTIVATION: We study a stochastic method for approximating the set of local minima in partial RNA folding landscapes associated with a bounded-distance neighbourhood of folding conformations. The conformations are limited to RNA secondary structures without pseudoknots. The method aims at exploring partial energy landscapes pL induced by folding simulations and their underlying neighbourhood relations. It combines an approximation of the number of local optima devised by Garnier and Kallel (2002) with a run-time estimation for identifying sets of local optima established by Reeves and Eremeev (2004). RESULTS: The method is tested on nine sequences of length between 50 nt and 400 nt, which allows us to compare the results with data generated by RNAsubopt and subsequent barrier tree calculations. On the nine sequences, the method captures on average 92% of local minima with settings designed for a target of 95%. The run-time of the heuristic can be estimated by O(n(2)Dνlnν), where n is the sequence length, ν is the number of local minima in the partial landscape pL under consideration and D is the maximum number of steepest descent steps in attraction basins associated with pL.     

A modified error backpropagation algorithm for complex-value neural networks

The complex-valued backpropagation algorithm has been widely used in fields of dealing with telecommunications, speech recognition and image processing with Fourier transformation. However, the local minima problem usually occurs in the process of learning. To solve this problem and to speed up the learning process, we propose a modified error function by adding a term to the conventional error function, which is corresponding to the hidden layer error. The simulation results show that the proposed algorithm is capable of preventing the learning from sticking into the local minima and of speeding up the learning.     

New learning automata based algorithms for adaptation of backpropagation algorithm parameters

One popular learning algorithm for feedforward neural networks is the backpropagation (BP) algorithm which includes parameters, learning rate (eta), momentum factor (alpha) and steepness parameter (lambda). The appropriate selections of these parameters have large effects on the convergence of the algorithm. Many techniques that adaptively adjust these parameters have been developed to increase speed of convergence. In this paper, we shall present several classes of learning automata based solutions to the problem of adaptation of BP algorithm parameters. By interconnection of learning automata to the feedforward neural networks, we use learning automata scheme for adjusting the parameters eta, alpha, and lambda based on the observation of random response of the neural networks. One of the important aspects of the proposed schemes is its ability to escape from local minima with high possibility during the training period. The feasibility of proposed methods is shown through simulations on several problems.     

Structural basis of hierarchical multiple substates of a protein. I: Introduction

A computer experiment of protein dynamics is carried out, which consists of two steps: (1) A Monte Carlo simulation of thermal fluctuations in the native state of a globular protein, bovine pancreatic trypsin inhibitor; and (2) a simulation of the quick freezing of fluctuating conformations into energy minima by minimization of the energy of a number of conformations sampled in the Monte Carlo simulation. From the analysis of results of the computer experiment is obtained the following picture of protein dynamics: multiple energy minima exist in the native state, and they are distributed in clusters in the conformational space. The dynamics has a hierarchical structure which has at least two levels. In the first level, dynamics is restricted within one of the clusters of minima. In the second, transitions occur among the clusters. Local parts of a protein molecule, side chains and local main chain segments, can take multiple locally stable conformations in the native state. Many minima result from combinations of these multiple local conformations. The hierarchical structure in the dynamics comes from interactions among the local parts. Protein molecules have two types of flexibility, each associated with elastic and plastic deformations, respectively.     

CLIFF: clustering of high-dimensional microarray data via iterative feature filtering using normalized cuts

We present CLIFF, an algorithm for clustering biological samples using gene expression microarray data. This clustering problem is difficult for several reasons, in particular the sparsity of the data, the high dimensionality of the feature (gene) space, and the fact that many features are irrelevant or redundant. Our algorithm iterates between two computational processes, feature filtering and clustering. Given a reference partition that approximates the correct clustering of the samples, our feature filtering procedure ranks the features according to their intrinsic discriminability, relevance to the reference partition, and irredundancy to other relevant features, and uses this ranking to select the features to be used in the following round of clustering. Our clustering algorithm, which is based on the concept of a normalized cut, clusters the samples into a new reference partition on the basis of the selected features. On a well-studied problem involving 72 leukemia samples and 7130 genes, we demonstrate that CLIFF outperforms standard clustering approaches that do not consider the feature selection issue, and produces a result that is very close to the original expert labeling of the sample set.     

Competitive spiking and indirect entropy minimization of rate code: efficient search for hidden components.

Our motivation, which originates from the psychological and physiological evidences of component-based representations in the brain, is to find neural methods that can efficiently search for structures. Here, an architecture made of coupled parallel working reconstruction subnetworks is presented. Each subnetwork utilizes non-negativity constraint on the generative weights and on the internal representation. 'Spikes' are generated within subnetworks via winner take all mechanism. Memory components are modified in order to directly minimize the reconstruction error and to indirectly minimize the entropy of the spike rate distribution, via a combination of a stochastic gradient search and a novel tuning method. This tuning dynamically changes the learning rate: the higher the entropy of the spike rate, the higher the learning rate of the gradient search in the subnetworks. This method effectively reduces the search space and increases the escape probability from high entropy local minima. We demonstrate that one subnetwork can develop localized and oriented components. Coupled networks can discover and sort components into the subnetworks; a problem subject to combinatorial explosion. Synergy between spike code and rate code is discussed.     

Supercoiled DNA energetics and dynamics by computer simulation.

A new formulation is presented for investigating supercoiled DNA configurations by deterministic techniques. Thus far, the computational difficulties involved in applying deterministic methods to supercoiled DNA studies have generally limited computer simulations to stochastic approaches. While stochastic methods, such as simulated annealing and Metropolis-Monte Carlo sampling, are successful at generating a large number of configurations and estimating thermodynamic properties of topoisomer ensembles, deterministic methods offer an accurate characterization of the minima and a systematic following of their dynamics. To make this feasible, we model circular duplex DNA compactly by a B-spline ribbon-like model in terms of a small number of control vertices. We associate an elastic deformation energy composed of bending and twisting integrals and represent intrachain contact by a 6-12 Lennard Jones potential. The latter is parameterized to yield an energy minimum at the observed DNA-helix diameter inclusive of a hydration shell. A penalty term to ensure fixed contour length is also included. First and second partial derivatives of the energy function have been derived by using various mathematical simplifications. First derivatives are essential for Newton-type minimization as well as molecular dynamics, and partial second-derivative information can significantly accelerate minimization convergence through preconditioning. Here we apply a new large-scale truncated-Newton algorithm for minimization and a Langevin/implicit-Euler scheme for molecular dynamics. Our truncated-Newton method exploits the separability of potential energy functions into terms of differing complexity. It relies on a preconditioned conjugate gradient method that is efficient for large-scale problems to solve approximately for the search direction at every step. Our dynamics algorithm is numerically stable over large time steps. It also introduces a frequency-discriminating mechanism so that vibrational modes with frequencies greater than a chosen cutoff frequency are essentially frozen by the method. With these tools, we rapidly identify corresponding circular and interwound energy minima for small DNA rings for a series of imposed linking-number differences. These structures are consistent with available electron microscopy data. The energetic exchange of stability between the circle and the figure-8, in very good agreement with analytical results, is also detailed. Molecular dynamics trajectories at 100 femtosecond time steps then reveal the rapid folding of the unstable circular state into supercoiled forms. Significant bending and twisting motions of the interwound structures are also observed. Such information may be useful for understanding transition states along the folding pathway and the role of enzymes that regulate supercoiling.(ABSTRACT TRUNCATED AT 400 WORDS)     

Deterministic global optimization algorithm based on outer approximation for the parameter estima- tion of nonlinear dynamic biological systems

ABSTRACT: BACKGROUND: The estimation of parameter values for mathematical models of biological systems is an optimization problem that is particularly challenging due to the nonlinearities involved. One major difficulty is the existence of multiple minima in which standard optimization methods may fall during the search. Deterministic global optimization methods overcome this limitation, ensuring convergence to the global optimum within a desired tolerance. Global optimization techniques are typically classified into stochastic and deterministic. The former typically lead to lower CPU times but offer no guarantee of convergence to the global minimum in a finite number of iterations. In contrast, deterministic methods provide solutions of a given quality (i.e., optimality gap), but tend to lead to large computational burdens. RESULTS: This work presents a deterministic outer approximation-based algorithm for the global optimization of dynamic problems arising in the parameter estimation of models of biological systems. Our approach, which offers a theoretical guarantee of convergence to the global minimum, reformulating the set of ordinary differential equations into an equivalent set of algebraic equations through the use of orthogonal collocation methods, giving rise to a nonconvex nonlinear programming (NLP) problem. This nonconvex NLP is decomposed into two hierarchical levels: a master mixed-integer linear programming problem (MILP) that provides a rigorous lower bound on the optimal solution, and a reduced-space slave NLP that yields an upper bound. The algorithm iterates between these two levels until a termination criterion is satisfied. CONCLUSION: The capabilities of our approach were tested in two benchmark problems, in which the performance of our algorithm was compared with that of the commercial global optimization package BARON. The proposed strategy produced near optimal solutions (i.e., within a desired tolerance) in a fraction of the CPU time required by BARON.     

Applications of simulated annealing to peptides

We report the application of a new conformation searching algorithm called simulated annealing to the location of the global minimum energy conformation of peptides. Simulated annealing is a Metropolis Monte Carlo approach to conformation generation in which both the energy and temperature dependence of the Boltzmann distribution guides the search for the global minimum. Both uphill and downhill moves are possible, which allows the molecule to escape from local minima. Applications to the 20 natural amino acid "dipeptide models" as well as to polyalanines up to Ala80 are very successful in finding the lowest energy conformation. A history file of the simulated annealing process allows reconstruction and examination of the random walk around conformation space. A separate program, Conf-Gen, reads the history file and extracts all low-energy conformations visited during the run.     

Optimal Formation Reconfiguration Control of Multiple UCAVs Using Improved Particle Swarm Optimization

Optimal formation reconfiguration control of multiple Uninhabited Combat Air Vehicles （UCAVs） is a complicated global optimum problem. Particle Swarm Optimization （PSO） is a population based stochastic optimization technique inspired by social behaviour of bird flocking or fish schooling. PSO can achieve better results in a faster, cheaper way compared with other bio-inspired computational methods, and there are few parameters to adjust in PSO. In this paper, we propose an improved PSO model for solving the optimal formation reconfiguration control problem for multiple UCAVs. Firstly, the Control Parameterization and Time Diseretization （CPTD） method is designed in detail. Then, the mutation strategy and a special mutation-escape operator are adopted in the improved PSO model to make particles explore the search space more efficiently. The proposed strategy can produce a large speed value dynamically according to the variation of the speed, which makes the algorithm explore the local and global minima thoroughly at the same time. Series experimental results demonstrate the feasibility and effectiveness of the proposed method in solving the optimal formation reconfiguration control problem for multiple UCAVs.     

Evolutionary-inspired probabilistic search for enhancing sampling of local minima in the protein energy surface

Background

Despite computational challenges, elucidating conformations that a protein system assumes under physiologic conditions for the purpose of biological activity is a central problem in computational structural biology. While these conformations are associated with low energies in the energy surface that underlies the protein conformational space, few existing conformational search algorithms focus on explicitly sampling low-energy local minima in the protein energy surface.

Methods

This work proposes a novel probabilistic search framework, PLOW, that explicitly samples low-energy local minima in the protein energy surface. The framework combines algorithmic ingredients from evolutionary computation and computational structural biology to effectively explore the subspace of local minima. A greedy local search maps a conformation sampled in conformational space to a nearby local minimum. A perturbation move jumps out of a local minimum to obtain a new starting conformation for the greedy local search. The process repeats in an iterative fashion, resulting in a trajectory-based exploration of the subspace of local minima.

Results and conclusions

The analysis of PLOW's performance shows that, by navigating only the subspace of local minima, PLOW is able to sample conformations near a protein's native structure, either more effectively or as well as state-of-the-art methods that focus on reproducing the native structure for a protein system. Analysis of the actual subspace of local minima shows that PLOW samples this subspace more effectively that a naive sampling approach. Additional theoretical analysis reveals that the perturbation function employed by PLOW is key to its ability to sample a diverse set of low-energy conformations. This analysis also suggests directions for further research and novel applications for the proposed framework.

     

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.     

Evolutionary dynamics of fearfulness and boldness: a stochastic simulation model

A stochastic simulation model is investigated for the evolution of anti-predator behavior in birds. The main goal is to reveal the effects of population size, predation threats, and energy lost per escape on the evolutionary dynamics of fearfulness and boldness. Two pure strategies, fearfulness and boldness, are assumed to have different responses for the predator attacks and nonlethal disturbance. On the other hand, the co-existence mechanism of fearfulness and boldness is also considered. For the effects of total population size, predation threats, and energy lost per escape, our main results show that: (i) the fearful (bold) individuals will be favored in a small (large) population, i.e. in a small (large) population, the fearfulness (boldness) can be considered to be an ESS; (ii) in a population with moderate size, fearfulness would be favored under moderate predator attacks; and (iii) although the total population size is the most important factor for the evolutionary dynamics of both fearful and bold individuals, the small energy lost per escape enables the fearful individuals to have the ability to win the advantage even in a relatively large population. Finally, we show also that the co-existence of fearful and bold individuals is possible when the competitive interactions between individuals are introduced.     

Parameter estimation with a novel gradient-based optimization method for biological lattice-gas cellular automaton models

Lattice-gas cellular automata (LGCAs) can serve as stochastic mathematical models for collective behavior (e.g. pattern formation) emerging in populations of interacting cells. In this paper, a two-phase optimization algorithm for global parameter estimation in LGCA models is presented. In the first phase, local minima are identified through gradient-based optimization. Algorithmic differentiation is adopted to calculate the necessary gradient information. In the second phase, for global optimization of the parameter set, a multi-level single-linkage method is used. As an example, the parameter estimation algorithm is applied to a LGCA model for early in vitro angiogenic pattern formation.     

Computational protein design with side-chain conformational entropy

Recent advances in modeling protein structures at the atomic level have made it possible to tackle "de novo" computational protein design. Most procedures are based on combinatorial optimization using a scoring function that estimates the folding free energy of a protein sequence on a given main-chain structure. However, the computation of the conformational entropy in the folded state is generally an intractable problem, and its contribution to the free energy is not properly evaluated. In this article, we propose a new automated protein design methodology that incorporates such conformational entropy based on statistical mechanics principles. We define the free energy of a protein sequence by the corresponding partition function over rotamer states. The free energy is written in variational form in a pairwise approximation and minimized using the Belief Propagation algorithm. In this way, a free energy is associated to each amino acid sequence: we use this insight to rescore the results obtained with a standard minimization method, with the energy as the cost function. Then, we set up a design method that directly uses the free energy as a cost function in combination with a stochastic search in the sequence space. We validate the methods on the design of three superficial sites of a small SH3 domain, and then apply them to the complete redesign of 27 proteins. Our results indicate that accounting for entropic contribution in the score function affects the outcome in a highly nontrivial way, and might improve current computational design techniques based on protein stability.