A new multi-population artificial bee algorithm based on global and local optima for numerical optimization

Artificial Bee Colony (ABC) algorithm is a nature-inspired algorithm that showed its efficiency for optimizations. However, the ABC algorithm showed some imbalances between exploration and exploitation. In order to improve the exploitation and enhance the convergence speed, a multi-population ABC algorithm based on global and local optimum (namely MPGABC) is proposed in this paper. First, in MPGABC, the initial population is generated using both chaotic systems and opposition-based learning methods. The colony in MPGABC is divided into several sub-populations to increase diversity. Moreover, the solution search mechanism is modified by introducing global and local optima in the solution search equations of both employed and onlookers. The scout bees in the proposed algorithm are generated similarly to the initial population. Finally, the proposed algorithm is compared with several state-of-art ABC algorithm variants on a set of 13 classical benchmark functions. The experimental results show that MPGABC competes and outperforms other ABC algorithm variants.

     

Two New PRP Conjugate Gradient Algorithms for Minimization Optimization Models

Two new PRP conjugate Algorithms are proposed in this paper based on two modified PRP conjugate gradient methods: the first algorithm is proposed for solving unconstrained optimization problems, and the second algorithm is proposed for solving nonlinear equations. The first method contains two aspects of information: function value and gradient value. The two methods both possess some good properties, as follows: 1)β _k ≥ 0 2) the search direction has the trust region property without the use of any line search method 3) the search direction has sufficient descent property without the use of any line search method. Under some suitable conditions, we establish the global convergence of the two algorithms. We conduct numerical experiments to evaluate our algorithms. The numerical results indicate that the first algorithm is effective and competitive for solving unconstrained optimization problems and that the second algorithm is effective for solving large-scale nonlinear equations.     

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.     

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 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.     

Fast k-NNG Construction with GPU-Based Quick Multi-Select

In this paper, we describe a new brute force algorithm for building the -Nearest Neighbor Graph (k-NNG). The k-NNG algorithm has many applications in areas such as machine learning, bio-informatics, and clustering analysis. While there are very efficient algorithms for data of low dimensions, for high dimensional data the brute force search is the best algorithm. There are two main parts to the algorithm: the first part is finding the distances between the input vectors, which may be formulated as a matrix multiplication problem; the second is the selection of the k-NNs for each of the query vectors. For the second part, we describe a novel graphics processing unit (GPU)-based multi-select algorithm based on quick sort. Our optimization makes clever use of warp voting functions available on the latest GPUs along with user-controlled cache. Benchmarks show significant improvement over state-of-the-art implementations of the k-NN search on GPUs.     

Characterising the searchability of continuous optimisation problems for PSO

The focus of research in swarm intelligence has been largely on the algorithmic side with relatively little attention being paid to the study of problems and the behaviour of algorithms in relation to problems. When a new algorithm or variation on an existing algorithm is proposed in the literature, there is seldom any discussion or analysis of algorithm weaknesses and on what kinds of problems the algorithm is expected to fail. Fitness landscape analysis is an approach that can be used to analyse optimisation problems. By characterising problems in terms of fitness landscape features, the link between problem types and algorithm performance can be studied. This article investigates a number of measures for analysing the ability of a search process to improve fitness on a particular problem (called evolvability in literature but referred to as searchability in this study to broaden the scope to non-evolutionary-based search techniques). A number of existing fitness landscape analysis techniques originally proposed for discrete problems are adapted to work in continuous search spaces. For a range of benchmark problems, the proposed searchability measures are viewed alongside performance measures for a traditional global best particle swarm optimisation (PSO) algorithm. Empirical results show that no single measure can be used as a predictor of PSO performance, but that multiple measures of different fitness landscape features can be used together to predict PSO failure.     

Searching and gradualness

Consider the elements of the power set S as the alternatives in a search space. Each element of the set has a value and the goal of a search is to find an element with near-minimum value. If high-valued elements of cardinality i (recall that elements of S are themselves sets) are subsets of high-valued elements of cardinality i + 1, then the search space has a king of gradualness that should facilitate search.A search algorithm might generate a series, S′(1), … S′(k) of samples in S, where all the elements in S′ (i) have cardinality i. I propose a class of search algorithms, where each algorithm A(j) generates S′(i + 1) by emphasizing the j lowest-valued elements in S′(i). I then define search space gradualness and search algorithm performance and formally relate gradualness and performance.     

Extending MAM5 Meta-Model and JaCalIV E Framework to Integrate Smart Devices from Real Environments

This paper presents the extension of a meta-model (MAM5) and a framework based on the model (JaCalIVE) for developing intelligent virtual environments. The goal of this extension is to develop augmented mirror worlds that represent a real and virtual world coupled, so that the virtual world not only reflects the real one, but also complements it. A new component called a smart resource artifact, that enables modelling and developing devices to access the real physical world, and a human in the loop agent to place a human in the system have been included in the meta-model and framework. The proposed extension of MAM5 has been tested by simulating a light control system where agents can access both virtual and real sensor/actuators through the smart resources developed. The results show that the use of real environment interactive elements (smart resource artifacts) in agent-based simulations allows to minimize the error between simulated and real system.     

Multi-Objective Ant Colony Optimization Based on the Physarum-Inspired Mathematical Model for Bi-Objective Traveling Salesman Problems

Bi-objective Traveling Salesman Problem (bTSP) is an important field in the operations research, its solutions can be widely applied in the real world. Many researches of Multi-objective Ant Colony Optimization (MOACOs) have been proposed to solve bTSPs. However, most of MOACOs suffer premature convergence. This paper proposes an optimization strategy for MOACOs by optimizing the initialization of pheromone matrix with the prior knowledge of Physarum-inspired Mathematical Model (PMM). PMM can find the shortest route between two nodes based on the positive feedback mechanism. The optimized algorithms, named as iPM-MOACOs, can enhance the pheromone in the short paths and promote the search ability of ants. A series of experiments are conducted and experimental results show that the proposed strategy can achieve a better compromise solution than the original MOACOs for solving bTSPs.     

GalaxyDomDock: An Ab Initio Domain–domain Docking Web Server for Multi-domain Protein Structure Prediction

A significant proportion of proteins comprise multiple domains. Domain–domain docking is a tool that predicts multi-domain protein structures when individual domain structures can be accurately predicted but when domain orientations cannot be predicted accurately. GalaxyDomDock predicts an ensemble of domain orientations from given domain structures by docking. Such information would also be beneficial in elucidating the functions of proteins that have multiple states with different domain orientations. GalaxyDomDock is an ab initio domain–domain docking method based on GalaxyTongDock, a previously developed protein–protein docking method. Infeasible domain orientations for the given linker are effectively screened out from the docked conformations by a geometric filter, using the Dijkstra algorithm. In addition, domain linker conformations are predicted by adopting a loop sampling method FALC. The proposed GalaxyDomDock outperformed existing ab initio domain–domain docking methods, such as AIDA and Rosetta, in performance tests on the Rosetta benchmark set of two-domain proteins. GalaxyDomDock also performed better than or comparable to AIDA on the AIDA benchmark set of two-domain proteins and two-domain proteins containing discontinuous domains, including the benchmark set in which each domain of the set was modeled by the recent version of AlphaFold. The GalaxyDomDock web server is freely available as a part of GalaxyWEB at http://galaxy.seoklab.org/domdock.     

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.     

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.     

Adaptive Firefly Algorithm: Parameter Analysis and its Application

As a nature-inspired search algorithm, firefly algorithm (FA) has several control parameters, which may have great effects on its performance. In this study, we investigate the parameter selection and adaptation strategies in a modified firefly algorithm — adaptive firefly algorithm (AdaFa). There are three strategies in AdaFa including (1) a distance-based light absorption coefficient; (2) a gray coefficient enhancing fireflies to share difference information from attractive ones efficiently; and (3) five different dynamic strategies for the randomization parameter. Promising selections of parameters in the strategies are analyzed to guarantee the efficient performance of AdaFa. AdaFa is validated over widely used benchmark functions, and the numerical experiments and statistical tests yield useful conclusions on the strategies and the parameter selections affecting the performance of AdaFa. When applied to the real-world problem — protein tertiary structure prediction, the results demonstrated improved variants can rebuild the tertiary structure with the average root mean square deviation less than 0.4Å and 1.5Å from the native constrains with noise free and 10% Gaussian white noise.     

A particle swarm optimizer with passive congregation

This paper presents a particle swarm optimizer (PSO) with passive congregation to improve the performance of standard PSO (SPSO). Passive congregation is an important biological force preserving swarm integrity. By introducing passive congregation to PSO, information can be transferred among individuals of the swarm. A particle swarm optimizer with passive congregation (PSOPC) is tested with a set of 10 benchmark functions with 30 dimensions and compared to a global version of SPSO (GSPSO), a local version of SPSO (LSPSO), and PSO with a constriction factor (CPSO), respectively. Experimental results indicate that the PSO with passive congregation improves the search performance on the benchmark functions significantly.     

Extreme learning machines for regression based on V-matrix method

This paper studies the joint effect of V-matrix, a recently proposed framework for statistical inferences, and extreme learning machine (ELM) on regression problems. First of all, a novel algorithm is proposed to efficiently evaluate the V-matrix. Secondly, a novel weighted ELM algorithm called V-ELM is proposed based on the explicit kernel mapping of ELM and the V-matrix method. Though V-matrix method could capture the geometrical structure of training data, it tends to assign a higher weight to instance with smaller input value. In order to avoid this bias, a novel method called VI-ELM is proposed by minimizing both the regression error and the V-matrix weighted error simultaneously. Finally, experiment results on 12 real world benchmark datasets show the effectiveness of our proposed methods.     

Generalized pattern search algorithm for Peptide structure prediction

Finding the near-native structure of a protein is one of the most important open problems in structural biology and biological physics. The problem becomes dramatically more difficult when a given protein has no regular secondary structure or it does not show a fold similar to structures already known. This situation occurs frequently when we need to predict the tertiary structure of small molecules, called peptides. In this research work, we propose a new ab initio algorithm, the generalized pattern search algorithm, based on the well-known class of Search-and-Poll algorithms. We performed an extensive set of simulations over a well-known set of 44 peptides to investigate the robustness and reliability of the proposed algorithm, and we compared the peptide conformation with a state-of-the-art algorithm for peptide structure prediction known as PEPstr. In particular, we tested the algorithm on the instances proposed by the originators of PEPstr, to validate the proposed algorithm; the experimental results confirm that the generalized pattern search algorithm outperforms PEPstr by 21.17% in terms of average root mean-square deviation, RMSD C_α.     

Lagrange Interpolation Learning Particle Swarm Optimization

In recent years, comprehensive learning particle swarm optimization (CLPSO) has attracted the attention of many scholars for using in solving multimodal problems, as it is excellent in preserving the particles’ diversity and thus preventing premature convergence. However, CLPSO exhibits low solution accuracy. Aiming to address this issue, we proposed a novel algorithm called LILPSO. First, this algorithm introduced a Lagrange interpolation method to perform a local search for the global best point (gbest). Second, to gain a better exemplar, one gbest, another two particle’s historical best points (pbest) are chosen to perform Lagrange interpolation, then to gain a new exemplar, which replaces the CLPSO’s comparison method. The numerical experiments conducted on various functions demonstrate the superiority of this algorithm, and the two methods are proven to be efficient for accelerating the convergence without leading the particle to premature convergence.     

A novel comprehensive learning artificial bee colony optimizer for dynamic optimization biological problems

There are many dynamic optimization problems in the real world, whose convergence and searching ability is cautiously desired, obviously different from static optimization cases. This requires an optimization algorithm adaptively seek the changing optima over dynamic environments, instead of only finding the global optimal solution in the static environment. This paper proposes a novel comprehensive learning artificial bee colony optimizer (CLABC) for optimization in dynamic environments problems, which employs a pool of optimal foraging strategies to balance the exploration and exploitation tradeoff. The main motive of CLABC is to enrich artificial bee foraging behaviors in the ABC model by combining Powell’s pattern search method, life-cycle, and crossover-based social learning strategy. The proposed CLABC is a more bee-colony-realistic model that the bee can reproduce and die dynamically throughout the foraging process and population size varies as the algorithm runs. The experiments for evaluating CLABC are conducted on the dynamic moving peak benchmarks. Furthermore, the proposed algorithm is applied to a real-world application of dynamic RFID network optimization. Statistical analysis of all these cases highlights the significant performance improvement due to the beneficial combination and demonstrates the performance superiority of the proposed algorithm.     

Feature Selection via Chaotic Antlion Optimization

Background

Selecting a subset of relevant properties from a large set of features that describe a dataset is a challenging machine learning task. In biology, for instance, the advances in the available technologies enable the generation of a very large number of biomarkers that describe the data. Choosing the more informative markers along with performing a high-accuracy classification over the data can be a daunting task, particularly if the data are high dimensional. An often adopted approach is to formulate the feature selection problem as a biobjective optimization problem, with the aim of maximizing the performance of the data analysis model (the quality of the data training fitting) while minimizing the number of features used.

Results

We propose an optimization approach for the feature selection problem that considers a “chaotic” version of the antlion optimizer method, a nature-inspired algorithm that mimics the hunting mechanism of antlions in nature. The balance between exploration of the search space and exploitation of the best solutions is a challenge in multi-objective optimization. The exploration/exploitation rate is controlled by the parameter I that limits the random walk range of the ants/prey. This variable is increased iteratively in a quasi-linear manner to decrease the exploration rate as the optimization progresses. The quasi-linear decrease in the variable I may lead to immature convergence in some cases and trapping in local minima in other cases. The chaotic system proposed here attempts to improve the tradeoff between exploration and exploitation. The methodology is evaluated using different chaotic maps on a number of feature selection datasets. To ensure generality, we used ten biological datasets, but we also used other types of data from various sources. The results are compared with the particle swarm optimizer and with genetic algorithm variants for feature selection using a set of quality metrics.