On the equivalences and differences of evolutionary algorithms

Evolutionary algorithms (EAs) are fast and robust computation methods for global optimization, and have been widely used in many real-world applications. We first conceptually discuss the equivalences of various popular EAs including genetic algorithm (GA), biogeography-based optimization (BBO), differential evolution (DE), evolution strategy (ES) and particle swarm optimization (PSO). We find that the basic versions of BBO, DE, ES and PSO are equal to the GA with global uniform recombination (GA/GUR) under certain conditions. Then we discuss their differences based on biological motivations and implementation details, and point out that their distinctions enhance the diversity of EA research and applications. To further study the characteristics of various EAs, we compare the basic versions and advanced versions of GA, BBO, DE, ES and PSO to explore their optimization ability on a set of real-world continuous optimization problems. Empirical results show that among the basic versions of the algorithms, BBO performs best on the benchmarks that we studied. Among the advanced versions of the algorithms, DE and ES perform best on the benchmarks that we studied. However, our main conclusion is that the conceptual equivalence of the algorithms is supported by the fact that algorithmic modifications result in very different performance levels.     

Two-stage update biogeography-based optimization using differential evolution algorithm (DBBO)

The present paper proposes a new stochastic optimization algorithm as a hybridization of a relatively recent stochastic optimization algorithm, called biogeography-based optimization (BBO) with the differential evolution (DE) algorithm. This combination incorporates DE algorithm into the optimization procedure of BBO with an attempt to incorporate diversity to overcome stagnation at local optima. We also propose to implement an additional selection procedure for BBO, which preserves fitter habitats for subsequent generations. The proposed variation of BBO, named DBBO, is tested for several benchmark function optimization problems. The results show that DBBO can significantly outperform the basic BBO algorithm and can mostly emerge as the best solution providing algorithm among competing BBO and DE algorithms.     

Analysis of migration models of biogeography-based optimization using Markov theory

Biogeography-based optimization (BBO) is a new evolutionary algorithm inspired by biogeography, which involves the study of the migration of biological species between habitats. Previous work has shown that various migration models of BBO result in significant changes in performance. Sinusoidal migration models have been shown to provide the best performance so far. Motivated by biogeography theory and previous results, in this paper a generalized sinusoidal migration model curve is proposed. A previously derived BBO Markov model is used to analyze the effect of migration models on optimization performance, and new theoretical results which are confirmed with simulation results are obtained. The results show that the generalized sinusoidal migration model is significantly better than other models for simple but representative problems, including a unimodal one-max problem, a multimodal problem, and a deceptive problem. In addition, performance comparison is further investigated through 23 benchmark functions with a wide range of dimensions and diverse complexities, to verify the superiority of the generalized sinusoidal migration model.     

Localized biogeography-based optimization

Biogeography-based optimization (BBO) is a relatively new heuristic method, where a population of habitats (solutions) are continuously evolved and improved mainly by migrating features from high-quality solutions to low-quality ones. In this paper we equip BBO with local topologies, which limit that the migration can only occur within the neighborhood zone of each habitat. We develop three versions of localized BBO algorithms, which use three different local topologies namely the ring topology, the square topology, and the random topology respectively. Our approach is quite easy to implement, but it can effectively improve the search capability and prevent the algorithm from being trapped in local optima. We demonstrate the effectiveness of our approach on a set of well-known benchmark problems. We also introduce the local topologies to a hybrid DE/BBO method, resulting in three localized DE/BBO algorithms, and show that our approach can improve the performance of the state-of-the-art algorithm as well.     

生物地理学优化算法中迁移算子的比较

生物地理学优化算法(Biogeography-Based Optimization,BBO)是一种模仿物种迁移规律的智能优化算法,其中迁移算子是影响优化效果的关键环节.基于迁移地的选择模式(以迁出率高的栖息地为主导或者以迁入率高的栖息地为主导)和迁移量的规模(单变量和部分变量),提出了BBO算法中可能存在的四种迁移方式.通过对13个经典实例的实验仿真,比较4种迁移算子的优化结果,阐明了产生差异的原因.实验结果表明,迁入主导的部分迁移式算子优化效果最好.     

Biogeography-Based Optimization

Biogeography is the study of the geographical distribution of biological organisms. Mathematical equations that govern the distribution of organisms were first discovered and developed during the 1960s. The mindset of the engineer is that we can learn from nature. This motivates the application of biogeography to optimization problems. Just as the mathematics of biological genetics inspired the development of genetic algorithms (GAs), and the mathematics of biological neurons inspired the development of artificial neural networks, this paper considers the mathematics of biogeography as the basis for the development of a new field: biogeography-based optimization (BBO). We discuss natural biogeography and its mathematics, and then discuss how it can be used to solve optimization problems. We see that BBO has features in common with other biology-based optimization methods, such as GAs and particle swarm optimization (PSO). This makes BBO applicable to many of the same types of problems that GAs and PSO are used for, namely, high-dimension problems with multiple local optima. However, BBO also has some features that are unique among biology-based optimization methods. We demonstrate the performance of BBO on a set of 14 standard benchmarks and compare it with seven other biology-based optimization algorithms. We also demonstrate BBO on a real-world sensor selection problem for aircraft engine health estimation.      

基于混合迁移策略的生物地理学优化算法

为提高生物地理学优化算法(BBO)的性能,提出一种基于混合迁移策略的生物地理学优化算法(HMBBO)。该算法通过动态选取待迁出种群个体,平衡对解集搜索过程中的选择压力。采用混合迁移策略改进迁移机制,增强算法对解的搜索能力,避免引起过早收敛。并加入分段Logistic混沌机制对个体进行变异,提高算法的收敛精度。基于标准测试函数的仿真实验表明,HMBBO算法可有效避免早熟收敛,在收敛速度和收敛精度上较标准BBO算法有较大提高。     

Ecogeography-based optimization: Enhancing biogeography-based optimization with ecogeographic barriers and differentiations

Biogeography-based optimization (BBO) is a bio-inspired metaheuristic based on the mathematics of island biogeography. The paper proposes a new variation of BBO, named ecogeography-based optimization (EBO), which regards the population of islands (solutions) as an ecological system with a local topology. Two novel migration operators are designed to perform effective exploration and exploitation in the solution space, mimicking the species dispersal under ecogeographic barriers and differentiations. Experimental results show that the EBO outperforms the basic BBO and several other popular evolutionary algorithms (EAs) on a set of well-known benchmark problems. We also present a real-world application of the proposed EBO to an emergency airlift problem in the 2013 Ya׳an–Lushan Earthquake, China.     

差异演化的实验研究

首先基于一些实例研究了差异演化(DE)的参数选择问题；然后在分析DE特点的基础上，将缩放因子F由固定数值设为随机函数，实现了一个简化的DE版本(SDE)，该方法不仅减少了需调整的参数，而且对CR的参数选择更为宽松．与已有文献中遗传算法的带约束型数值优化问题的实验结果对比，表明SDE能在较少的计算次数内获得较好的结果。     

Scheduling of Virtual Cellular Manufacturing Systems: A Biogeography-Based Optimization Algorithm

Virtual cellular manufacturing system (VCMS) is one of the modern strategies in the production facilities layout, which has attracted considerable attention in recent years. In this system, machines are located in different positions on the shop floor and virtual cells are a logical grouping of machines, jobs, and workers from the viewpoint of the production control system. These features not only enhance the system’s agility but also allow a dynamic reassignment of cells as demand changes. This paper addresses the VCMS scheduling problems where the jobs have different orders on machines and the objective is to simultaneously minimize the weighted sum of the makespan and total traveling distance in order to create a balance between criteria. The research methodology firstly consists of a mathematical programming model with regard to the production constraints in order to describe the characteristics of the VCMS. Secondly, a basic genetic algorithm (GA), a biogeography-based optimization (BBO) algorithm, an algorithm based on hybridization of BBO and GA, and the BBO algorithm accompanied by restart phase are developed to solve the VCMS scheduling problems. The developed algorithms have been compared to each other and their performance are evaluated in terms of their best solution and computational time as effectiveness and efficiency criteria, respectively. Consequently, the performance of the best algorithm has been evaluated by the state-of-the-art algorithm, GA, in the literature. The results show that the best algorithm based on BBO could find solutions at least as good as the last famous algorithm, GA, in the literature.     

A hybrid biogeography-based optimization algorithm for job shop scheduling problem

In this paper, a hybrid biogeography-based optimization (HBBO) algorithm has been proposed for the job-shop scheduling problem (JSP). Biogeography-based optimization (BBO) is a new bio-inpired computation method that is based on the science of biogeography. The BBO algorithm searches for the global optimum mainly through two main steps: migration and mutation. As JSP is one of the most difficult combinational optimization problems, the original BBO algorithm cannot handle it very well, especially for instances with larger size. The proposed HBBO algorithm combines the chaos theory and “searching around the optimum” strategy with the basic BBO, which makes it converge to global optimum solution faster and more stably. Series of comparative experiments with particle swarm optimization (PSO), basic BBO, the CPLEX and 14 other competitive algorithms are conducted, and the results show that our proposed HBBO algorithm outperforms the other state-of-the-art algorithms, such as genetic algorithm (GA), simulated annealing (SA), the PSO and the basic BBO.     

Effect of hybridizing Biogeography-Based Optimization (BBO) technique with Artificial Immune Algorithm (AIA) and Ant Colony Optimization (ACO)

Hybridization in optimization methods plays a very vital role to make it effective and efficient. Different optimization methods have different search tendency and it is always required to experiment the effect of hybridizing different search tendency of the optimization algorithm with each other. This paper presents the effect of hybridizing Biogeography-Based Optimization (BBO) technique with Artificial Immune Algorithm (AIA) and Ant Colony Optimization (ACO) in two different ways. So, four different variants of hybrid BBO, viz. two variants of hybrid BBO with AIA and two with ACO, are developed and experimented in this paper. All the considered optimization techniques have altogether a different search tendency. The proposed hybrid method is tested on many benchmark problems and real life problems. Friedman test and Holm–Sidak test are performed to have the statistical validity of the results. Results show that proposed hybridization of BBO with ACO and AIA is effective over a wide range of problems. Moreover, the proposed hybridization is also effective over other proposed hybridization of BBO and different variants of BBO available in the literature.     

Blended biogeography-based optimization for constrained optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method that is based on the science of biogeography. We propose two extensions to BBO. First, we propose a blended migration operator. Benchmark results show that blended BBO outperforms standard BBO. Second, we employ blended BBO to solve constrained optimization problems. Constraints are handled by modifying the BBO immigration and emigration procedures. The approach that we use does not require any additional tuning parameters beyond those that are required for unconstrained problems. The constrained blended BBO algorithm is compared with solutions based on a stud genetic algorithm (SGA) and standard particle swarm optimization 2007 (SPSO 07). The numerical results demonstrate that constrained blended BBO outperforms SGA and performs similarly to SPSO 07 for constrained single-objective optimization problems.     

生物地理信息优化算法中迁移算子的改进

原生物地理信息优化算法主要通过迁移算子与变异算子实现群体的进化, 常被应用于求解单目标优化问题。 如果将原有的进化算子直接用于求解连续多目标优化问题,会严重影响群体的多样性。文中将原迁移算子进行改进, 引入扰动因子, 增强群体的多样性。并以此为基础,提出基于生物地理信息的多目标进化算法(BBMOEA)。 通过与原有迁移算子下的算法比较及各类型测试函数的实验, 结果验证改进迁移算子对于求解多目标优化问题是有效可行的。同时将BBMOEA与经典算法SPEA2和NSGA-Ⅱ进行比较, 结果表明BBMOEA所得Pareto解集在收敛的同时,具有较均匀的分布性。     

Biogeography-based optimization with covariance matrix based migration

Biogeography-based optimization (BBO) is a new evolutionary algorithm. The major problem of basic BBO is that its migration operator is rotationally variant, which leaves BBO performing poorly in non-separable problems. To overcome this drawback of BBO, in this paper, we propose the covariance matrix based migration (CMM) to relieve BBO’s dependence upon the coordinate system so that BBO’s rotational invariance is enhanced. By embedding the CMM into BBO, we put forward a new BBO approach, namely biogeography-based optimization with covariance matrix based migration, called CMM-BBO. Specifically, CMM-BBO algorithms are developed by the CMM operator being randomly combined with the original migration in various existing BBO variants. Numeric simulations on 37 benchmark functions show that our CMM-BBO approach effectively improves the performance of the existing BBO algorithms.     

Model selection for least squares support vector regressions based on small-world strategy

Model selection plays a key role in the application of support vector machine (SVM). In this paper, a method of model selection based on the small-world strategy is proposed for least squares support vector regression (LS-SVR). In this method, the model selection is treated as a single-objective global optimization problem in which generalization performance measure performs as fitness function. To get better optimization performance, the main idea of depending more heavily on dense local connections in small-world phenomenon is considered, and a new small-world optimization algorithm based on tabu search, called the tabu-based small-world optimization (TSWO), is proposed by employing tabu search to construct local search operator. Therefore, the hyper-parameters with best generalization performance can be chosen as the global optimum based on the powerful search ability of TSWO. Experiments on six complex multimodal functions are conducted, demonstrating that TSWO performs better in avoiding premature of the population in comparison with the genetic algorithm (GA) and particle swarm optimization (PSO). Moreover, the effectiveness of leave-one-out bound of LS-SVM on regression problems is tested on noisy sinc function and benchmark data sets, and the numerical results show that the model selection using TSWO can almost obtain smaller generalization errors than using GA and PSO with three generalization performance measures adopted.     

改进迁移算子的BBO算法及其在PID参数中的优化

针对生物地理学优化（BBO）算法寻优过程中易陷入搜索动力不足、收敛精度不高等问题,提出一种基于改进迁移算子的生物地理学优化算法（IMO-BBO）。在BBO算法基础上,结合“优胜劣汰”的进化思想,将迁移距离作为影响因素对迁移算子进行改进,并用差分策略将不适宜迁移的个体进行替换,以增加算法的局部探索能力。同时为丰富物种的多样性,引入多种群概念。利用IMO-BBO算法分别对13个基准测试函数进行测试,与基于协方差迁移算子和混合差分策略的BBO （CMM-DE/BBO）算法和BBO算法相比,改进算法提高了对全局最优解的搜索能力,在收敛速度和精确度上也都有显著提高;将IMO-BBO算法应用到PID参数整定中,仿真结果表明,所提算法优化后的控制器具有更快的响应速度和更稳定的精度。     

生物地理学优化算法综述

生物地理学(Biogeography)是一门研究自然界种群迁移机制的科学,Dan Simon用生物地理学的方法和机制来解决工程优化问题,提出了生物地理学优化算法(BBO,Biogeography-Based Optimization).生物地理学优化算法以其独特的搜索机制和较好的性能在智能优化算法领域得到了广泛的关注.对生物地理学优化算法的设计原理、迁徙模型、算法流程及相应迁移和突变操作进行了综述.通过BBO算法在14个基准函数下与传统算法,如遗传算法、蚁群算法和粒子群等优化算法的性能比较,表明生物地理学优化算法是有效的.论述了算法与传统优化算法之间的差异以及BBO算法有待解决的问题.     

Markov blanket-embedded genetic algorithm for gene selection

Microarray technologies enable quantitative simultaneous monitoring of expression levels for thousands of genes under various experimental conditions. This new technology has provided a new way of biological classification on a genome-wide scale. However, predictive accuracy is affected by the presence of thousands of genes many of which are unnecessary from the classification point of view. So, a key issue of microarray data classification is to identify the smallest possible set of genes that can achieve good predictive accuracy. In this study, we propose a novel Markov blanket-embedded genetic algorithm (MBEGA) for gene selection problem. In particular, the embedded Markov blanket-based memetic operators add or delete features (or genes) from a genetic algorithm (GA) solution so as to quickly improve the solution and fine-tune the search. Empirical results on synthetic and microarray benchmark datasets suggest that MBEGA is effective and efficient in eliminating irrelevant and redundant features based on both Markov blanket and predictive power in classifier model. A detailed comparative study with other methods from each of filter, wrapper, and standard GA shows that MBEGA gives a best compromise among all four evaluation criteria, i.e., classification accuracy, number of selected genes, computational cost, and robustness.     

An improved biogeography based optimization approach for segmentation of human head CT-scan images employing fuzzy entropy

The present paper proposes the development of a three-level thresholding based image segmentation technique for real images obtained from CT scanning of a human head. The proposed method utilizes maximization of fuzzy entropy to determine the optimal thresholds. The optimization problem is solved by employing a very recently proposed population-based optimization technique, called biogeography based optimization (BBO) technique. In this work we have proposed some improvements over the basic BBO technique to implement nonlinear variation of immigration rate and emigration rate with number of species in a habitat. The proposed improved BBO based algorithm and the basic BBO algorithm are implemented for segmentation of fifteen real CT image slices. The results show that the proposed improved BBO variants could perform better than the basic BBO technique as well as genetic algorithm (GA) and particle swarm optimization (PSO) based segmentation of the same images using the principle of maximization of fuzzy entropy.