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.     

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.      

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.     

A charging-scheme decision model for electric vehicle battery swapping station using varied population evolutionary algorithms

This paper proposes a new battery swapping station (BSS) model to determine the optimized charging scheme for each incoming Electric Vehicle (EV) battery. The objective is to maximize the BSS’s battery stock level and minimize the average charging damage with the use of different types of chargers. An integrated objective function is defined for the multi-objective optimization problem. The genetic algorithm (GA), differential evolution (DE) algorithm and three versions of particle swarm optimization (PSO) algorithms have been implemented to solve the problem, and the results show that GA and DE perform better than the PSO algorithms, but the computational time of GA and DE are longer than using PSO. Hence, the varied population genetic algorithm (VPGA) and varied population differential evolution (VPDE) algorithm are proposed to determine the optimal solution and reduce the computational time of typical evolutionary algorithms. The simulation results show that the performances of the proposed algorithms are comparable with the typical GA and DE, but the computational times of the VPGA and VPDE are significantly shorter. A 24-h simulation study is carried out to examine the feasibility of the model.     

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.     

进化算法研究进展

进化算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，主要包括遗传算法，（ｇｅｎｅｒｉｃａｌｇｏｒｉｔｈｍｓ，简记为ＧＡｓ）、进化规划（ｅｖｏｌｕｔｉｏｎａｒｙｐｒｏｇｒａｍｍｉｎｇ，简记为ＥＰ）和进化策略（ｅｖｏｌｕｔｉｏｎａｒｙｓｔｒａｔｅｇｉｅｓ，简记为ＥＳｓ），它们可以用解决优化和机器学习等问题，进化算法的两个主要特点中群体搜索策略及群体中个体之间的信息交换，进化算法不依赖于梯度信     

Improved differential evolution approach based on cultural algorithm and diversity measure applied to solve economic load dispatch problems

Evolutionary algorithms (EAs) are general-purpose stochastic search methods that use the metaphor of evolution as the key element in the design and implementation of computer-based problems solving systems. During the past two decades, EAs have attracted much attention and wide applications in a variety of fields, especially for optimization and design. EAs offer a number of advantages: robust and reliable performance, global search capability, little or no information requirement, and others. Among various EAs, differential evolution (DE), which characterized by the different mutation operator and competition strategy from the other EAs, has shown great promise in many numerical benchmark problems and real-world optimization applications. The potentialities of DE are its simple structure, easy use, convergence speed and robustness. To improve the global optimization property of DE, in this paper, a DE approach based on measure of population's diversity and cultural algorithm technique using normative and situational knowledge sources is proposed as alternative method to solving the economic load dispatch problems of thermal generators. The traditional and cultural DE approaches are validated for two test systems consisting of 13 and 40 thermal generators whose nonsmooth fuel cost function takes into account the valve-point loading effects. Simulation results indicate that performance of the cultural DE present best results when compared with previous optimization approaches in solving economic load dispatch problems.     

Differential Evolution Using a Neighborhood-Based Mutation Operator

Differential evolution (DE) is well known as a simple and efficient scheme for global optimization over continuous spaces. It has reportedly outperformed a few evolutionary algorithms (EAs) and other search heuristics like the particle swarm optimization (PSO) when tested over both benchmark and real-world problems. DE, however, is not completely free from the problems of slow and/or premature convergence. This paper describes a family of improved variants of the DE/target-to-best/1/bin scheme, which utilizes the concept of the neighborhood of each population member. The idea of small neighborhoods, defined over the index-graph of parameter vectors, draws inspiration from the community of the PSO algorithms. The proposed schemes balance the exploration and exploitation abilities of DE without imposing serious additional burdens in terms of function evaluations. They are shown to be statistically significantly better than or at least comparable to several existing DE variants as well as a few other significant evolutionary computing techniques over a test suite of 24 benchmark functions. The paper also investigates the applications of the new DE variants to two real-life problems concerning parameter estimation for frequency modulated sound waves and spread spectrum radar poly-phase code design.      

Statistical learning makes the hybridization of particle swarm and differential evolution more efficient—A novel hybrid optimizer

This brief paper reports a hybrid algorithm we developed recently to solve the global optimization problems of multimodal functions, by combining the advantages of two powerful population-based metaheuristics—differential evolution (DE) and particle swarm optimization (PSO). In the hybrid denoted by DEPSO, each individual in one generation chooses its evolution method, DE or PSO, in a statistical learning way. The choice depends on the relative success ratio of the two methods in a previous learning period. The proposed DEPSO is compared with its PSO and DE parents, two advanced DE variants one of which is suggested by the originators of DE, two advanced PSO variants one of which is acknowledged as a recent standard by PSO community, and also a previous DEPSO. Benchmark tests demonstrate that the DEPSO is more competent for the global optimization of multimodal functions due to its high optimization quality. Supported by the National Natural Science Foundation of China (Grant No. 60374069), and the Foundation of the Key Laboratory of Complex Systems and Intelligent Science, Institute of Automation, Chinese Academy of Sciences (Grant No. 20060104)     

生物地理学优化算法综述

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

基于差分进化生物地理学优化的多层感知器训练方法

针对生物地理学优化训练多层感知器存在的早熟收敛以及初始化灵敏等问题,提出一种基于差分进化生物地理学优化的多层感知器训练方法。将生物地理学优化（Biogeography-based Optimization,BBO）与差分进化(Differential Evolution,DE)算法相结合,形成改进的混合DE_BBO算法;采用改进的DE_BBO来训练多层感知器（Multi-Layer Perceptron,MLP）,并应用于虹膜、乳腺癌、输血、钞票验证等4类数据分类。与BBO、PSO、GA、ACO、ES、PBIL等6种主流启发式算法的实验结果进行比较表明,DE_BBO_MLP算法在分类精度和收敛速度等方面优于已有方法。     

PSO和GA的对比及其混合算法的研究进展

系统地介绍了微粒群优化算法(PSO)和遗传算法(GA)的基本原理、发展和应用的状况,比较了两者的原理特点,列举了各种微粒群优化算法和遗传算法的改进算法。介绍和总结目前出现的两种算法思想结合的局部混合与全局混合两种方式,并用图表给出了说明。分析了两种混合方式的局限性,提出对具体问题找出计算速度和计算精度的平衡点来改进算法。最后做了总结和展望,指出微粒群算法的应用需进一步拓展,和其他算法结合是提高其性能的主要方向。     

基于改进BBO算法的分数阶PID控制器设计

针对分数阶PID(Fractional-Order Proportional-Integral-Derivative,FOPID)控制器参数整定,提出了一种改进生物地理学优化(Biogeography-Based Optimization,BBO)算法。该算法改进点主要包括:迁移操作中保留精英个体;变异操作中引入差分进化(Dtferential Evolution,ED)算法的变异策略;消除重复样本。仿真结果表明:在分数阶PID控制器参数整定中,与原始的BBO算法、遗传算法(Genetic Algorithm,GA)和粒子群算法(Particle Swarm Optimization,PSO)比较,提出的改进BBO算法具有超调量小、误差小,收敛更快的特点。     

Three modified versions of differential evolution algorithm for continuous optimization

Differential evolution (DE) is one simple and effective evolutionary algorithm (EA) for global optimization. In this paper, three modified versions of the DE to improve its performance, to repair its defect in accurate converging to individual optimal point and to compensate the limited amount of search moves of original DE are proposed. In the first modified version called bidirectional differential evolution (BDE), to generate a new trial point, is used from the bidirectional optimization concept, and in the second modified version called shuffled differential evolution (SDE), population such as shuffled frog leaping (SFL) algorithm is divided in to several memeplexes and each memeplex is improved by the DE algorithm. Finally, in the third modified version of DE called shuffled bidirectional differential evolution (SBDE) to improve each memeplex is used from the proposed BDE algorithm. Three proposed modified versions are applied on two types of DE and six obtained algorithms are compared with original DE and SFL algorithms. Experiments on continuous benchmark functions and non-parametric analysis of obtained results demonstrate that applying bidirectional concept only improves one type of the DE. But the SDE and the SBDE have a better success rate and higher solution precision than original DE and SFL, whereas those are more time consuming on some functions. In a later part of the comparative experiments, a comparison of the proposed algorithms with some modern DE and the other EAs reported in the literature confirms a better or at least comparable performance of our proposed algorithms.     

DE/BBO: a hybrid differential evolution with biogeography-based optimization for global numerical optimization

Differential evolution (DE) is a fast and robust evolutionary algorithm for global optimization. It has been widely used in many areas. Biogeography-based optimization (BBO) is a new biogeography inspired algorithm. It mainly uses the biogeography-based migration operator to share the information among solutions. In this paper, we propose a hybrid DE with BBO, namely DE/BBO, for the global numerical optimization problem. DE/BBO combines the exploration of DE with the exploitation of BBO effectively, and hence it can generate the promising candidate solutions. To verify the performance of our proposed DE/BBO, 23 benchmark functions with a wide range of dimensions and diverse complexities are employed. Experimental results indicate that our approach is effective and efficient. Compared with other state-of-the-art DE approaches, DE/BBO performs better, or at least comparably, in terms of the quality of the final solutions and the convergence rate. In addition, the influence of the population size, dimensionality, different mutation schemes, and the self-adaptive control parameters of DE are also studied.     

The spherical search algorithm for bound-constrained global optimization problems

In this paper, a new optimization algorithm called Spherical Search (SS) is proposed to solve the bound-constrained non-linear global optimization problems. The main operations of SS are the calculation of spherical boundary and generation of new trial solution on the surface of the spherical boundary. These operations are mathematically modeled with some more basic level operators: Initialization of solution, greedy selection and parameter adaptation, and are employed on the 30 black-box bound constrained global optimization problems. This study also analyzes the applicability of the proposed algorithm on a set of real-life optimization problems. Meanwhile, to show the robustness and proficiency of SS, the obtained results of the proposed algorithm are compared with the results of other well-known optimization algorithms and their advanced variants: Particle Swarm Optimization (PSO), Differential Evolution (DE), and Covariance Matrix Adapted Evolution Strategy (CMA-ES). The comparative analysis reveals that the performance of SS is quite competitive with respect to the other peer algorithms.     

Multi-operator based evolutionary algorithms for solving constrained optimization problems

Over the last two decades, many sophisticated evolutionary algorithms have been introduced for solving constrained optimization problems. Due to the variability of characteristics in different COPs, no single algorithm performs consistently over a range of problems. In this paper, for a better coverage of the problem characteristics, we introduce an algorithm framework that uses multiple search operators in each generation. The appropriate mix of the search operators, for any given problem, is determined adaptively. The framework is tested by implementing two different algorithms. The performance of the algorithms is judged by solving 60 test instances taken from two constrained optimization benchmark sets from specialized literature. The first algorithm, which is a multi-operator based genetic algorithm (GA), shows a significant improvement over different versions of GA (each with a single one of these operators). The second algorithm, using differential evolution (DE), also confirms the benefit of the multi-operator algorithm by providing better and consistent solutions. The overall results demonstrated that both GA and DE based algorithms show competitive, if not better, performance as compared to the state of the art algorithms.     

Incorporating mutation scheme into krill herd algorithm for global numerical optimization

Recently, Gandomi and Alavi proposed a robust meta-heuristic optimization algorithm, called Krill Herd (KH), for global optimization. To improve the performance of the KH algorithm, harmony search (HS) is applied to mutate between krill during the process of krill updating instead of physical diffusion used in KH. A novel hybrid meta-heuristic optimization approach HS/KH is proposed to solve global numerical optimization problem. HS/KH combines the exploration of harmony search (HS) with the exploitation of KH effectively, and hence, it can generate the promising candidate solutions. The detailed implementation procedure for this improved meta-heuristic method is also described. Fourteen standard benchmark functions are applied to verify the effects of these improvements, and it is demonstrated that, in most cases, the performance of this hybrid meta-heuristic method (HS/KH) is superior to, or at least highly competitive with, the standard KH and other population-based optimization methods, such as ACO, BBO, DE, ES, GA, HS, KH, PSO, and SGA. The effect of the HS/FA parameters is also analyzed.     

Polygene-based evolutionary algorithms with frequent pattern mining

In this paper, we introduce polygene-based evolution, a novel framework for evolutionary algorithms (EAs) that features distinctive operations in the evolutionary process. In traditional EAs, the primitive evolution unit is a gene, wherein genes are independent components during evolution. In polygene-based evolutionary algorithms (PGEAs), the evolution unit is a polygene, i.e., a set of co-regulated genes. Discovering and maintaining quality polygenes can play an effective role in evolving quality individuals. Polygenes generalize genes, and PGEAs generalize EAs. Implementing the PGEA framework involves three phases: (I) polygene discovery, (II) polygene planting, and (III) polygene-compatible evolution. For Phase I, we adopt an associative classification-based approach to discover quality polygenes. For Phase II, we perform probabilistic planting to maintain the diversity of individuals. For Phase III, we incorporate polygene-compatible crossover and mutation in producing the next generation of individuals. Extensive experiments on function optimization benchmarks in comparison with the conventional and state-of-the-art EAs demonstrate the potential of the approach in terms of accuracy and efficiency improvement.     

Analytical and numerical comparisons of biogeography-based optimization and genetic algorithms

We show that biogeography-based optimization (BBO) is a generalization of a genetic algorithm with global uniform recombination (GA/GUR). Based on the common features of BBO and GA/GUR, we use a previously-derived BBO Markov model to obtain a GA/GUR Markov model. One BBO characteristic which makes it distinctive from GA/GUR is its migration mechanism, which affects selection pressure (i.e., the probability of retaining certain features in the population from one generation to the next). We compare the BBO and GA/GUR algorithms using results from analytical Markov models and continuous optimization benchmark problems. We show that the unique selection pressure provided by BBO generally results in better optimization results for a set of standard benchmark problems. We also present comparisons between BBO and GA/GUR for combinatorial optimization problems, include the traveling salesman, the graph coloring, and the bin packing problems.