Artificial bee colonies for continuous optimization: Experimental analysis and improvements

The artificial bee colony (ABC) algorithm is a recent class of swarm intelligence algorithms that is loosely inspired by the foraging behavior of honeybee swarms. It was introduced in 2005 using continuous optimization problems as an example application. Similar to what has happened with other swarm intelligence techniques, after the initial proposal, several researchers have studied variants of the original algorithm. Unfortunately, often these variants have been tested under different experimental conditions and different fine-tuning efforts for the algorithm parameters. In this article, we review various variants of the original ABC algorithm and experimentally study nine ABC algorithms under two settings: either using the original parameter settings as proposed by the authors, or using an automatic algorithm configuration tool using a same tuning effort for each algorithm. We also study the effect of adding local search to the ABC algorithms. Our experimental results show that local search can improve considerably the performance of several ABC variants and that it reduces strongly the performance differences between the studied ABC variants. We also show that the best ABC variants are competitive with recent state-of-the-art algorithms on the benchmark set we used, which establishes ABC algorithms as serious competitors in continuous optimization.     

Calibration of parameters in Dynamic Energy Budget models using Direct-Search methods

Dynamic Energy Budget (DEB) theory aims to capture the quantitative aspects of metabolism at the individual level, for all species. The parametrization of a DEB model is based on information obtained through the observation of natural populations and experimental research. Currently the DEB toolbox estimates these parameters using the Nelder–Mead Simplex method, a derivative-free direct-search method. However, this procedure presents some limitations regarding convergence and how to address constraints. Framed in the calibration of parameters in DEB theory, this work presents a numerical comparison between the Nelder–Mead Simplex method and the SID-PSM algorithm, a Directional Direct-Search method for which convergence can be established both for unconstrained and constrained problems. A hybrid version of the two methods, named as Simplex Directional Direct-Search, provides a robust and efficient algorithm, able to solve the constrained optimization problems resulting from the parametrization of the biological models.

     

ABC-X: a generalized,automatically configurable artificial bee colony framework

The artificial bee colony (ABC) algorithm is a popular metaheuristic that was originally conceived for tackling continuous function optimization tasks. Over the last decade, a large number of variants of ABC have been proposed, making it by now a well-studied swarm intelligence algorithm. Typically, in a paper on algorithmic variants of ABC algorithms, one or at most two of its algorithmic components are modified. Possible changes include variations on the search equations, the selection of candidate solutions to be explored, or the adoption of features from other algorithmic techniques. In this article, we propose to follow a different direction and to build a generalized ABC algorithm, which we call ABC-X. ABC-X collects algorithmic components available from known ABC algorithms into a common algorithm framework that allows not only to instantiate known ABC variants but, more importantly, also many ABC algorithm variants that have never been explored before in the literature. Automatic algorithm configuration techniques can generate from this template new ABC variants that perform better than known ABC algorithms, even when their numerical parameters are fine-tuned using the same automatic configuration process.     

Set-based particle swarm optimization applied to the multidimensional knapsack problem

Particle swarm optimization algorithms have been successfully applied to discrete/valued optimization problems. However, in many cases the algorithms have been tailored specifically for the problem at hand. This paper proposes a generic set-based particle swarm optimization algorithm for use in discrete-valued optimization problems that can be formulated as set-based problems. A detailed sensitivity analysis of the parameters of the algorithm is conducted. The performance of the proposed algorithm is then compared against three other discrete particle swarm optimization algorithms from literature using the multidimensional knapsack problem and is shown to statistically outperform the existing algorithms.     

Enhanced hybrid search algorithm for protein structure prediction using the 3D-HP lattice model

The problem of protein structure prediction in the hydrophobic-polar (HP) lattice model is the prediction of protein tertiary structure. This problem is usually referred to as the protein folding problem. This paper presents a method for the application of an enhanced hybrid search algorithm to the problem of protein folding prediction, using the three dimensional (3D) HP lattice model. The enhanced hybrid search algorithm is a combination of the particle swarm optimizer (PSO) and tabu search (TS) algorithms. Since the PSO algorithm entraps local minimum in later evolution extremely easily, we combined PSO with the TS algorithm, which has properties of global optimization. Since the technologies of crossover and mutation are applied many times to PSO and TS algorithms, so enhanced hybrid search algorithm is called the MCMPSO-TS (multiple crossover and mutation PSO-TS) algorithm. Experimental results show that the MCMPSO-TS algorithm can find the best solutions so far for the listed benchmarks, which will help comparison with any future paper approach. Moreover, real protein sequences and Fibonacci sequences are verified in the 3D HP lattice model for the first time. Compared with the previous evolutionary algorithms, the new hybrid search algorithm is novel, and can be used effectively to predict 3D protein folding structure. With continuous development and changes in amino acids sequences, the new algorithm will also make a contribution to the study of new protein sequences.     

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.     

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.     

Estimating Genetic Effects and Quantifying Missing Heritability Explained by Identified Rare-Variant Associations

Next-generation sequencing has led to many complex-trait rare-variant (RV) association studies. Although single-variant association analysis can be performed, it is grossly underpowered. Therefore, researchers have developed many RV association tests that aggregate multiple variant sites across a genetic region (e.g., gene), and test for the association between the trait and the aggregated genotype. After these aggregate tests detect an association, it is only possible to estimate the average genetic effect for a group of RVs. As a result of the "winner’s curse," such an estimate can be biased. Although for common variants one can obtain unbiased estimates of genetic parameters by analyzing a replication sample, for RVs it is desirable to obtain unbiased genetic estimates for the study where the association is identified. This is because there can be substantial heterogeneity of RV sites and frequencies even among closely related populations. In order to obtain an unbiased estimate for aggregated RV analysis, we developed bootstrap-sample-split algorithms to reduce the bias of the winner’s curse. The unbiased estimates are greatly important for understanding the population-specific contribution of RVs to the heritability of complex traits. We also demonstrate both theoretically and via simulations that for aggregate RV analysis the genetic variance for a gene or region will always be underestimated, sometimes substantially, because of the presence of noncausal variants or because of the presence of causal variants with effects of different magnitudes or directions. Therefore, even if RVs play a major role in the complex-trait etiologies, a portion of the heritability will remain missing, and the contribution of RVs to the complex-trait etiologies will be underestimated.     

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.     

A competitive clustering particle swarm optimizer for dynamic optimization problems

Optimization in dynamic optimization problems (DOPs) requires the optimization algorithms not only to locate, but also to continuously track the moving optima. Particle swarm optimization (PSO) is a population-based optimization algorithm, originally developed for static problems. Recently, several researchers have proposed variants of PSO for optimization in DOPs. This paper presents a novel multi-swarm PSO algorithm, namely competitive clustering PSO (CCPSO), designed specially for DOPs. Employing a multi-stage clustering procedure, CCPSO splits the particles of the main swarm over a number of sub-swarms based on the particles positions and on their objective function values. The algorithm automatically adjusts the number of sub-swarms and the corresponding region of each sub-swarm. In addition to the sub-swarms, there is also a group of free particles that explore the environment to locate new emerging optima or exploit the current optima which are not followed by any sub-swarm. The adaptive search strategy adopted by the sub-swarms improves both the exploitation and tracking characteristics of CCPSO. A set of experiments is conducted to study the behavior of the proposed algorithm in different DOPs and to provide guidelines for setting the algorithm’s parameters in different problems. The results of CCPSO on a variety of moving peaks benchmark (MPB) functions are compared with those of several state-of-the-art PSO algorithms, indicating the efficiency of the proposed model.     

A Bayesian Interpretation of the Particle Swarm Optimization and Its Kernel Extension

Particle swarm optimization is a popular method for solving difficult optimization problems. There have been attempts to formulate the method in formal probabilistic or stochastic terms (e.g. bare bones particle swarm) with the aim to achieve more generality and explain the practical behavior of the method. Here we present a Bayesian interpretation of the particle swarm optimization. This interpretation provides a formal framework for incorporation of prior knowledge about the problem that is being solved. Furthermore, it also allows to extend the particle optimization method through the use of kernel functions that represent the intermediary transformation of the data into a different space where the optimization problem is expected to be easier to be resolved–such transformation can be seen as a form of prior knowledge about the nature of the optimization problem. We derive from the general Bayesian formulation the commonly used particle swarm methods as particular cases.     

Applying a multiobjective metaheuristic inspired by honey bees to phylogenetic inference

The development of increasingly popular multiobjective metaheuristics has allowed bioinformaticians to deal with optimization problems in computational biology where multiple objective functions must be taken into account. One of the most relevant research topics that can benefit from these techniques is phylogenetic inference. Throughout the years, different researchers have proposed their own view about the reconstruction of ancestral evolutionary relationships among species. As a result, biologists often report different phylogenetic trees from a same dataset when considering distinct optimality principles. In this work, we detail a multiobjective swarm intelligence approach based on the novel Artificial Bee Colony algorithm for inferring phylogenies. The aim of this paper is to propose a complementary view of phylogenetics according to the maximum parsimony and maximum likelihood criteria, in order to generate a set of phylogenetic trees that represent a compromise between these principles. Experimental results on a variety of nucleotide data sets and statistical studies highlight the relevance of the proposal with regard to other multiobjective algorithms and state-of-the-art biological methods.     

A new particle swarm optimization algorithm for noisy optimization problems

We propose a new particle swarm optimization algorithm for problems where objective functions are subject to zero-mean, independent, and identically distributed stochastic noise. While particle swarm optimization has been successfully applied to solve many complex deterministic nonlinear optimization problems, straightforward applications of particle swarm optimization to noisy optimization problems are subject to failure because the noise in objective function values can lead the algorithm to incorrectly identify positions as the global/personal best positions. Instead of having the entire swarm follow a global best position based on the sample average of objective function values, the proposed new algorithm works with a set of statistically global best positions that include one or more positions with objective function values that are statistically equivalent, which is achieved using a combination of statistical subset selection and clustering analysis. The new PSO algorithm can be seamlessly integrated with adaptive resampling procedures to enhance the capability of PSO to cope with noisy objective functions. Numerical experiments demonstrate that the new algorithm is able to consistently find better solutions than the canonical particle swarm optimization algorithm in the presence of stochastic noise in objective function values with different resampling procedures.     

Optimal estimation of ion-channel kinetics from macroscopic currents

Markov modeling provides an effective approach for modeling ion channel kinetics. There are several search algorithms for global fitting of macroscopic or single-channel currents across different experimental conditions. Here we present a particle swarm optimization(PSO)-based approach which, when used in combination with golden section search (GSS), can fit macroscopic voltage responses with a high degree of accuracy (errors within 1%) and reasonable amount of calculation time (less than 10 hours for 20 free parameters) on a desktop computer. We also describe a method for initial value estimation of the model parameters, which appears to favor identification of global optimum and can further reduce the computational cost. The PSO-GSS algorithm is applicable for kinetic models of arbitrary topology and size and compatible with common stimulation protocols, which provides a convenient approach for establishing kinetic models at the macroscopic level.     

Application of the Elitist-Mutated PSO and an Improved GSA to Estimate Parameters of Linear and Nonlinear Muskingum Flood Routing Models

Heuristic search algorithms, which are characterized by faster convergence rates and can obtain better solutions than the traditional mathematical methods, are extensively used in engineering optimizations. In this paper, a newly developed elitist-mutated particle swarm optimization (EMPSO) technique and an improved gravitational search algorithm (IGSA) are successively applied to parameter estimation problems of Muskingum flood routing models. First, the global optimization performance of the EMPSO and IGSA are validated by nine standard benchmark functions. Then, to further analyse the applicability of the EMPSO and IGSA for various forms of Muskingum models, three typical structures are considered: the basic two-parameter linear Muskingum model (LMM), a three-parameter nonlinear Muskingum model (NLMM) and a four-parameter nonlinear Muskingum model which incorporates the lateral flow (NLMM-L). The problems are formulated as optimization procedures to minimize the sum of the squared deviations (SSQ) or the sum of the absolute deviations (SAD) between the observed and the estimated outflows. Comparative results of the selected numerical cases (Case 1–3) show that the EMPSO and IGSA not only rapidly converge but also obtain the same best optimal parameter vector in every run. The EMPSO and IGSA exhibit superior robustness and provide two efficient alternative approaches that can be confidently employed to estimate the parameters of both linear and nonlinear Muskingum models in engineering applications.     

The Effect of Genomic Inversions on Estimation of Population Genetic Parameters from SNP Data

In recent years it has emerged that structural variants have a substantial impact on genomic variation. Inversion polymorphisms represent a significant class of structural variant, and despite the challenges in their detection, data on inversions in the human genome are increasing rapidly. Statistical methods for inferring parameters such as the recombination rate and the selection coefficient have generally been developed without accounting for the presence of inversions. Here we exploit new software for simulating inversions in population genetic data, invertFREGENE, to assess the potential impact of inversions on such methods. Using data simulated by invertFREGENE, as well as real data from several sources, we test whether large inversions have a disruptive effect on widely applied population genetics methods for inferring recombination rates, for detecting selection, and for controlling for population structure in genome-wide association studies (GWAS). We find that recombination rates estimated by LDhat are biased downward at inversion loci relative to the true contemporary recombination rates at the loci but that recombination hotspots are not falsely inferred at inversion breakpoints as may have been expected. We find that the integrated haplotype score (iHS) method for detecting selection appears robust to the presence of inversions. Finally, we observe a strong bias in the genome-wide results of principal components analysis (PCA), used to control for population structure in GWAS, in the presence of even a single large inversion, confirming the necessity to thin SNPs by linkage disequilibrium at large physical distances to obtain unbiased results.     

Success-biased social learning: Cultural and evolutionary dynamics

Success bias is a social learning strategy whereby learners tend to acquire the cultural variants of successful individuals. I develop a general model of success-biased social learning for discrete cultural traits with stochastic payoffs, and investigate its dynamics when only two variants are present. I find that success bias inherently favors rare variants, and consequently performs worse than unbiased imitation (i.e. random copying) when success payoffs are at least mildly stochastic and the optimal variant is common. Because of this weakness, success bias fails to replace unbiased imitation in an evolutionary model when selection is fairly weak or when the environment is relatively stable, and sometimes fails to invade at all. I briefly discuss the optimal strength of success bias, the complicated nature of defining success in social learning contexts, and the value of variant frequency as an important source of information to social learners. I conclude with predictions regarding the prevalence of success bias in different behavioral domains.     

Training feedforward neural networks with dynamic particle swarm optimisation

Particle swarm optimisation has been successfully applied to train feedforward neural networks in static environments. Many real-world problems to which neural networks are applied are dynamic in the sense that the underlying data distribution changes over time. In the context of classification problems, this leads to concept drift where decision boundaries may change over time. This article investigates the applicability of dynamic particle swarm optimisation algorithms as neural network training algorithms under the presence of concept drift.     

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.     

Particle Swarm Optimization with Scale-Free Interactions

The particle swarm optimization (PSO) algorithm, in which individuals collaborate with their interacted neighbors like bird flocking to search for the optima, has been successfully applied in a wide range of fields pertaining to searching and convergence. Here we employ the scale-free network to represent the inter-individual interactions in the population, named SF-PSO. In contrast to the traditional PSO with fully-connected topology or regular topology, the scale-free topology used in SF-PSO incorporates the diversity of individuals in searching and information dissemination ability, leading to a quite different optimization process. Systematic results with respect to several standard test functions demonstrate that SF-PSO gives rise to a better balance between the convergence speed and the optimum quality, accounting for its much better performance than that of the traditional PSO algorithms. We further explore the dynamical searching process microscopically, finding that the cooperation of hub nodes and non-hub nodes play a crucial role in optimizing the convergence process. Our work may have implications in computational intelligence and complex networks.