Multi-Objective Community Detection Based on Memetic Algorithm

Community detection has drawn a lot of attention as it can provide invaluable help in understanding the function and visualizing the structure of networks. Since single objective optimization methods have intrinsic drawbacks to identifying multiple significant community structures, some methods formulate the community detection as multi-objective problems and adopt population-based evolutionary algorithms to obtain multiple community structures. Evolutionary algorithms have strong global search ability, but have difficulty in locating local optima efficiently. In this study, in order to identify multiple significant community structures more effectively, a multi-objective memetic algorithm for community detection is proposed by combining multi-objective evolutionary algorithm with a local search procedure. The local search procedure is designed by addressing three issues. Firstly, nondominated solutions generated by evolutionary operations and solutions in dominant population are set as initial individuals for local search procedure. Then, a new direction vector named as pseudonormal vector is proposed to integrate two objective functions together to form a fitness function. Finally, a network specific local search strategy based on label propagation rule is expanded to search the local optimal solutions efficiently. The extensive experiments on both artificial and real-world networks evaluate the proposed method from three aspects. Firstly, experiments on influence of local search procedure demonstrate that the local search procedure can speed up the convergence to better partitions and make the algorithm more stable. Secondly, comparisons with a set of classic community detection methods illustrate the proposed method can find single partitions effectively. Finally, the method is applied to identify hierarchical structures of networks which are beneficial for analyzing networks in multi-resolution levels.     

Searching for Most Parsimonious Trees with Simulated Evolutionary Optimization

This study describes novel algorithms for searching for most parsimonious trees. These algorithms are implemented as a parsimony computer program, PARSIGAL, which performs well even with difficult data sets. For high level search, PARSIGAL uses an evolutionary optimization algorithm, which feeds good tree candidates to a branch-swapping local search procedure. This study also describes an extremely fast method of recomputing state sets for binary characters (additive or nonadditive characters with two states), based on packing 32 characters into a single memory word and recomputing the tree simultaneously for all 32 characters using fast bitwise logical operations. The operational principles of PARSIGAL are quite different from those previously published for other parsimony computer programs. Hence it is conceivable that PARSIGAL may be able to locate islands of trees that are different from those that are easily located with existing parsimony computer programs.     

Evolutionary optimization in multimodal search space

Optimization by a simple evolution strategy based on a mutation and selection scheme without recombination was tested for its efficiency in multimodal search space. A modified Rastrigin function served as an objective function providing fitness landscapes with many local optima. It turned out that the evolutionary algorithm including adaptive stepsize control is wellsuited for optimization. The process is able to efficiently surmount local energy barriers and converge to the global optimum. The relation between the optimization time available and the optimal number of offspring was investigated and a simple rule proposed. Several numbers of offspring are nearly equally suited in a smooth search space, whereas in rough fitness landscapes an optimum is observed. In either case both very large and very small numbers of offspring turned out to be unfavourable for optimization.     

Stochastic search strategy for estimation of maximum likelihood phylogenetic trees

The maximum likelihood (ML) method of phylogenetic tree construction is not as widely used as other tree construction methods (e.g., parsimony, neighbor-joining) because of the prohibitive amount of time required to find the ML tree when the number of sequences under consideration is large. To overcome this difficulty, we propose a stochastic search strategy for estimation of the ML tree that is based on a simulated annealing algorithm. The algorithm works by moving through tree space by way of a "local rearrangement" strategy so that topologies that improve the likelihood are always accepted, whereas those that decrease the likelihood are accepted with a probability that is related to the proportionate decrease in likelihood. Besides greatly reducing the time required to estimate the ML tree, the stochastic search strategy is less likely to become trapped in local optima than are existing algorithms for ML tree estimation. We demonstrate the success of the modified simulated annealing algorithm by comparing it with two existing algorithms (Swofford's PAUP* and Felsenstein's DNAMLK) for several theoretical and real data examples.     

Clonal Selection Based Memetic Algorithm for Job Shop Scheduling Problems

A clonal selection based memetic algorithm is proposed for solving job shop scheduling problems in this paper. In the proposed algorithm, the clonal selection and the local search mechanism are designed to enhance exploration and exploitation. In the clonal selection mechanism, clonal selection, hypermutation and receptor edit theories are presented to construct an evolutionary searching mechanism which is used for exploration. In the local search mechanism, a simulated annealing local search algorithm based on Nowicki and Smutnicki＇s neighborhood is presented to exploit local optima. The proposed algorithm is examined using some well-known benchmark problems. Numerical results validate the effectiveness of the proposed algorithm.     

Optimization by simulating molecular evolution

Based on the analogy between mathematical optimization and molecular evolution and on Eigen's quasi-species model of molecular evolution, an evolutionary algorithm for combinatorial optimization has been developed. This algorithm consists of a versatile variation scheme and an innovative decision rule, the essence of which lies in a radical revision of the conventional philosophy of optimization: A number of configurations of variables with better values, instead of only a single best configuration, are selected as starting points for the next iteration. As a result the search proceeds in parallel along a number of routes and is unlikely to get trapped in local optima. An important innovation of the algorithm is introduction of a constraint to let the starting points always keep a certain distance from each other so that the search is able to cover a larger region of space effectively. The main advantage of the algorithm is that it has more chances to find the global optimum and as many local optima as possible in a single run. This has been demonstrated in preliminary computational experiments.     

Population processing--a powerful class of parallel algorithms

We present a model of optimization of cost functions by a population of parallel processors and argue that especially diploid recombination of gene strings is a promising recipe for optimization which nature proliferates. Based on a simulated evolutionary search strategy diploidy is introduced as a means for maintaining variability in computational problems with large numbers of local extrema. A differentiation into genotypes and phenotypes is performed. The applied strategy is compared to some traditional algorithms simulating evolution on the basis of two sample cost functions.     

Improving the efficiency of evolutionary de novo peptide design: strategies for probing configuration and parameter settings

Evolutionary molecular design based on genetic algorithms (GAs) has been demonstrated to be a flexible and efficient optimization approach with potential for locating global optima. Its efficacy and efficiency are largely dependent on the operations and control parameters of the GAs. Accordingly, we have explored new operations and probed good parameter setting through simulations. The findings have been evaluated in a helical peptide design according to "Parameter setting by analogy" strategy; highly helical peptides have been successfully obtained with a population of only 16 peptides and 5 iterative cycles. The results indicate that new operations such as multi-step crossover-mutation are able to improve the explorative efficiency and to reduce the sensitivity to crossover and mutation rates (CR-MR). The efficiency of the peptide design has been furthermore improved by setting the GAs at the good CR-MR setting determined through simulation. These results suggest that probing the operations and parameter settings through simulation in combination with "Parameter setting by analogy" strategy provides an effective framework for improving the efficiency of the approach. Consequently, we conclude that this framework will be useful for contributing to practical peptide design, and gaining a better understanding of evolutionary molecular design.     

A hybrid neural learning algorithm using evolutionary learning and derivative free local search method

In this paper we investigate a hybrid model based on the Discrete Gradient method and an evolutionary strategy for determining the weights in a feed forward artificial neural network. Also we discuss different variants for hybrid models using the Discrete Gradient method and an evolutionary strategy for determining the weights in a feed forward artificial neural network. The Discrete Gradient method has the advantage of being able to jump over many local minima and find very deep local minima. However, earlier research has shown that a good starting point for the discrete gradient method can improve the quality of the solution point. Evolutionary algorithms are best suited for global optimisation problems. Nevertheless they are cursed with longer training times and often unsuitable for real world application. For optimisation problems such as weight optimisation for ANNs in real world applications the dimensions are large and time complexity is critical. Hence the idea of a hybrid model can be a suitable option. In this paper we propose different fusion strategies for hybrid models combining the evolutionary strategy with the discrete gradient method to obtain an optimal solution much quicker. Three different fusion strategies are discussed: a linear hybrid model, an iterative hybrid model and a restricted local search hybrid model. Comparative results on a range of standard datasets are provided for different fusion hybrid models.     

Toward a theory of evolutionary computation

We outline a theory of evolutionary computation using a formal model of evolutionary computation--the Evolutionary Turing Machine--which is introduced as the extension of the Turing Machine model. Evolutionary Turing Machines provide a better and a more complete model for evolutionary computing than conventional Turing Machines, algorithms, and Markov chains. The convergence and convergence rate are defined and investigated in terms of this new model. The sufficient conditions needed for the completeness and optimality of evolutionary search are investigated. In particular, the notion of the total optimality as an instance of the multiobjective optimization of the Universal Evolutionary Turing Machine is introduced. This provides an automatic way to deal with the intractability of evolutionary search by optimizing the quality of solutions and search costs simultaneously. Based on a new model a very flexible classification of optimization problem hardness for the evolutionary techniques is proposed. The expressiveness of evolutionary computation is investigated. We show that the problem of the best evolutionary algorithm is undecidable independently of whether the fitness function is time dependent or fixed. It is demonstrated that the evolutionary computation paradigm is more expressive than Turing Machines, and thus the conventional computer science based on them. We show that an Evolutionary Turing Machine is able to solve nonalgorithmically the halting problem of the Universal Turing Machine and, asymptotically, the best evolutionary algorithm problem. In other words, the best evolutionary algorithm does not exist, but it can be potentially indefinitely approximated using evolutionary techniques.     

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.     

Constrained global optimization for estimating molecular structure from atomic distances.

Finding optimal three-dimensional molecular configurations based on a limited amount of experimental and/or theoretical data requires efficient nonlinear optimization algorithms. Optimization methods must be able to find atomic configurations that are close to the absolute, or global, minimum error and also satisfy known physical constraints such as minimum separation distances between atoms (based on van der Waals interactions). The most difficult obstacles in these types of problems are that 1) using a limited amount of input data leads to many possible local optima and 2) introducing physical constraints, such as minimum separation distances, helps to limit the search space but often makes convergence to a global minimum more difficult. We introduce a constrained global optimization algorithm that is robust and efficient in yielding near-optimal three-dimensional configurations that are guaranteed to satisfy known separation constraints. The algorithm uses an atom-based approach that reduces the dimensionality and allows for tractable enforcement of constraints while maintaining good global convergence properties. We evaluate the new optimization algorithm using synthetic data from the yeast phenylalanine tRNA and several proteins, all with known crystal structure taken from the Protein Data Bank. We compare the results to commonly applied optimization methods, such as distance geometry, simulated annealing, continuation, and smoothing. We show that compared to other optimization approaches, our algorithm is able combine sparse input data with physical constraints in an efficient manner to yield structures with lower root mean squared deviation.     

Log Transformation Improves Dating of Phylogenies

Phylogenetic trees inferred from sequence data often have branch lengths measured in the expected number of substitutions and therefore, do not have divergence times estimated. These trees give an incomplete view of evolutionary histories since many applications of phylogenies require time trees. Many methods have been developed to convert the inferred branch lengths from substitution unit to time unit using calibration points, but none is universally accepted as they are challenged in both scalability and accuracy under complex models. Here, we introduce a new method that formulates dating as a nonconvex optimization problem where the variance of log-transformed rate multipliers is minimized across the tree. On simulated and real data, we show that our method, wLogDate, is often more accurate than alternatives and is more robust to various model assumptions.     

A Report on "One Day Symposium on Numerical Cladistics"

A recent symposium on numerical cladistics held at the American Museum of Natural History in New York City, addressed novel methods for searching tree space, applications of randomizations in cladistic analysis, and data management. One of the major concerns in systematics is that of finding the global optimum in tree length. The space to search is complex because it includes many local optima. It is a difficult task to escape local optima without a great loss in efficiency. The ideal is to search among suboptimal topologies and still obtain an answer in a reasonable amount of time. Nixon presented a new family of methods called "parsimony ratchet," which are successful at escaping local optima. Moilanen presented a new program which may have similar advantages. Two presentations, one by Goloboff and Farris and another by Farris, Goloboff, Källersjö, and Oxelman, introduced modifications to parsimony jackknifing that improved its accuracy when compared to normal heuristic searches. Wheeler discussed the advantages of new methods of analyzing DNA and protein sequence data, which eliminate multiple alignment; the most recent one packs nucleotides into strings which constitute the new characters. Siddall discussed different applications of randomization in cladistics and their logical consistency, finding some more acceptable than others. Nixon and Carpenter presented a new program for managing data. This symposium will probably be a landmark judging from the originality and practicality of the points presented.     

THE PHYLOGENETIC RELATIONSHIPS AMONG REQUIEM AND HAMMERHEAD SHARKS: INFERRING PHYLOGENY WHEN THOUSANDS OF EQUALLY MOST PARSIMONIOUS TREES RESULT

Abstract— Protein variation among 37 species of carcharhiniform sharks was examined at 17 presumed loci. Evolutionary trees were inferred from these data using both cladistic character and a distance Wagner analysis. Initial cladistic character analysis resulted in more than 30 000 equally parsimonious tree arrangements. Randomization tests designed to evaluate the phylogenetic information content of the data suggest the data are highly significantly different from random in spite of the large number of parsimonious trees produced. Different starting seed trees were found to influence the kind of tree topologies discovered by the heuristic branch swapping algorithm used. The trees generated during the early phases of branch swapping on a single seed tree were found to be topologically similar to those generated throughout the course of branch swapping. Successive weighting increased the frequency and the consistency with which certain clades were found during the course of branch swapping, causing the semi-strict consensus to be more resolved. Successive weighting also appeared resilient to the bias associated with the choice of initial seed tree causing analyses seeded with different trees to converge on identical final character weights and the same semi-strict consensus tree.
The summary cladistic character analysis and the distance Wagner analysis both support the monophyly of two major clades, the genus Rhizoprionodon and the genus Sphyrna. . The distance Wagner analysis also supports the monophyly of the genus Carcharhinus . However, the cladistic analysis suggests that Carcharhinus is a paraphyletic group that includes the blue shark Prionace glauca .     

A novel comparative method for identifying shifts in the rate of character evolution on trees

Evolutionary biologists since Darwin have been fascinated by differences in the rate of trait-evolutionary change across lineages. Despite this continued interest, we still lack methods for identifying shifts in evolutionary rates on the growing tree of life while accommodating uncertainty in the evolutionary process. Here we introduce a Bayesian approach for identifying complex patterns in the evolution of continuous traits. The method (auteur) uses reversible-jump Markov chain Monte Carlo sampling to more fully characterize the complexity of trait evolution, considering models that range in complexity from those with a single global rate to potentially ones in which each branch in the tree has its own independent rate. This newly introduced approach performs well in recovering simulated rate shifts and simulated rates for datasets nearing the size typical for comparative phylogenetic study (i.e., ≥64 tips). Analysis of two large empirical datasets of vertebrate body size reveal overwhelming support for multiple-rate models of evolution, and we observe exceptionally high rates of body-size evolution in a group of emydid turtles relative to their evolutionary background. auteur will facilitate identification of exceptional evolutionary dynamics, essential to the study of both adaptive radiation and stasis.     

Global optimization of the Saccharomyces cerevisiae: Fermentation process

In this article, steady‐state optimization of the Saccharomyces cerevisiae fermentation process problem is performed revealing the existence of multiple optimum solutions. The globally optimum solution was determined using the NEOS global optimization solver LINDO. A branch and bound strategy (bnb20.m) and the global search and multistart algorithms in the MATLAB global optimization toolbox were successful in determining locally optimum solutions and these results are validated by plotting the objective function against the decision variables. While in some cases all the strategies were successful in obtaining the globally optimum solutions, an example is presented where the most beneficial product value, which is not a stationary point and lies on the feasible boundary, is obtained by the LINDO global optimization solver (but not the other routines) as the globally optimum solution. The Jones–Kompala model was used to model the steady‐state of the fermentation process. While several articles have been published demonstrating the existence of nonlinearities and bifurcations in this model, the challenges posed by this model to optimization has never been investigated so far and this work attempts to do so. Both dilution rate and the oxygen mass transfer coefficient were used as the decision variables individually and together. © 2013 American Institute of Chemical Engineers Biotechnol. Prog., 29:917–923, 2013     

A Hybrid Search Algorithm for Swarm Robots Searching in an Unknown Environment

This paper proposes a novel method to improve the efficiency of a swarm of robots searching in an unknown environment. The approach focuses on the process of feeding and individual coordination characteristics inspired by the foraging behavior in nature. A predatory strategy was used for searching; hence, this hybrid approach integrated a random search technique with a dynamic particle swarm optimization (DPSO) search algorithm. If a search robot could not find any target information, it used a random search algorithm for a global search. If the robot found any target information in a region, the DPSO search algorithm was used for a local search. This particle swarm optimization search algorithm is dynamic as all the parameters in the algorithm are refreshed synchronously through a communication mechanism until the robots find the target position, after which, the robots fall back to a random searching mode. Thus, in this searching strategy, the robots alternated between two searching algorithms until the whole area was covered. During the searching process, the robots used a local communication mechanism to share map information and DPSO parameters to reduce the communication burden and overcome hardware limitations. If the search area is very large, search efficiency may be greatly reduced if only one robot searches an entire region given the limited resources available and time constraints. In this research we divided the entire search area into several subregions, selected a target utility function to determine which subregion should be initially searched and thereby reduced the residence time of the target to improve search efficiency.     

Taboo-based Monte Carlo Search as a Method to Improve Sampling Efficiency

Abstract

Taboo-based Monte Carlo search which restricts the sampling of the region near an old configuration, is developed. In this procedure, Monte Carlo simulation and random search method are combined to improve the sampling efficiency. The feasibility of this method is tested on global optimization of a continuous model function, melting of the 256 Lennard-Jones particles at T? = 0.680 and ρ? = 0.850 and polypeptides (alanine dipeptide and Metenkephalin). From the comparison of results for the model function between our method and other methods, we find the increase of convergence rate and the high possibility of escaping from the local energy minima. The results of the Lennard-Jones solids and polypeptides show that the convergence property to reach the equilibrium state is better than that of others. It is also found that no significant bias in ensemble distribution is detected, though taboo-based Monte Carlo search does not sample the correct ensemble distribution owing to the restriction of the sampling of the region near an old configuration.