约束进化算法及其应用研究综述

约束优化问题广泛存在于科学研究和工程实践中,其对应的约束优化进化算法也成为了进化领域的重要研究方向.约束优化进化算法的本质问题是如何有效地利用不可行解和可行解的信息,平衡目标函数和约束条件,使得算法更加高效.首先对约束优化问题进行定义;然后详细分析了目前主流的约束进化算法,同时,基于不同的约束处理机制,将这些机制分为约...     

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.     

基于剪枝堆栈泛化的离线数据驱动进化优化

现实世界中存在很多目标函数的计算非常昂贵, 甚至目标函数难以建模的复杂优化问题. 常规优化方法在解决此类问题时要么无从入手, 要么效率低下. 离线数据驱动的进化优化方法不需对真实目标函数进行评估, 跳出了传统优化方法的固铚, 极大推动了昂贵优化问题和不可建模优化问题的求解. 但离线数据驱动进化优化的效果严重依赖于所采用代理模型的质量. 为提升离线数据驱动进化优化的性能, 提出了一个基于剪枝堆栈泛化(Stacked generalization, SG)代理模型构建方法. 具体而言, 一方面基于异构的基学习器建立初级模型池, 再采用学习方式对各初级模型进行组合, 以提升代理模型的通用性和准确率. 另一方面基于等级保护指标对初级模型进行剪枝, 在提高初级模型集成效率的同时进一步提升最终代理模型的准确率, 并更好地指导种群的搜索. 为验证所提方法的有效性, 与7个最新的离线数据驱动的进化优化算法在12个基准测试问题上进行对比, 实验结果表明所提出的方法具有明显的优势.     

Biogeography-based optimisation with chaos

The biogeography-based optimisation (BBO) algorithm is a novel evolutionary algorithm inspired by biogeography. Similarly, to other evolutionary algorithms, entrapment in local optima and slow convergence speed are two probable problems it encounters in solving challenging real problems. Due to the novelty of this algorithm, however, there is little in the literature regarding alleviating these two problems. Chaotic maps are one of the best methods to improve the performance of evolutionary algorithms in terms of both local optima avoidance and convergence speed. In this study, we utilise ten chaotic maps to enhance the performance of the BBO algorithm. The chaotic maps are employed to define selection, emigration, and mutation probabilities. The proposed chaotic BBO algorithms are benchmarked on ten test functions. The results demonstrate that the chaotic maps (especially Gauss/mouse map) are able to significantly boost the performance of BBO. In addition, the results show that the combination of chaotic selection and emigration operators results in the highest performance.     

生物地理学优化算法理论及其应用研究综述

生物地理学优化算法（Biogeography-Based Optimization,BBO）是Simon提出的一种基于生物地理学理论的新型智能优化算法,具有良好的收敛性和稳定性。从BBO算法提出的背景出发,介绍了算法的基本理论、算法特点以及算法流程。总结了BBO算法的研究进展,包括BBO算法的理论分析、算法的改进、算法与其他优化算法的混合算法以及BBO算法在函数优化、电力系统、图像处理、机器人路径规划以及调度优化等领域的典型应用。对BBO算法有待解决的问题和未来研究方向进行了总结。     

一种云环境下基于混合型BBO的任务调度算法

任务调度在云计算中占有重要地位,是影响云计算性能的关键因素,被证明是NP问题。启发式算法是解决该问题的最有效方法之一,针对近年来出现的一种新型启发式算法--BBO算法展开研究,由于BBO算法在求解过程中收敛速度较慢,因此结合粒子群算法提出了一种新型算法的任务调度算法--HMBBO,并结合Cloudsim云仿真平台,进行了以Makespan为目标函数的比对实验。实验结果表明,与几种经典的启发式算法相比,HMBBO算法具有寻优能力强、收敛速度快、求解质量高的特点,为解决云计算环境中任务调度问题提供了一种新思路。     

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.     

Enhancing the performance of biogeography-based optimization using polyphyletic migration operator and orthogonal learning

Biogeography-based optimization (BBO) is a powerful population-based algorithm inspired by biogeography and has been extensively applied to many science and engineering problems. However, its direct-copying-based migration and random mutation operators make BBO possess local exploitation ability but lack global exploration ability. To remedy the defect and enhance the performance of BBO, an enhanced BBO variant, called POLBBO, is developed in this paper. In POLBBO, a proposed efficient operator named polyphyletic migration operator can formally utilize as many as four individuals’ features to construct a new solution vector. This operator cannot only generate new features from more promising areas in the search space, but also effectively increase the population diversity. On the other hand, an orthogonal learning (OL) strategy based on orthogonal experimental design is employed. The OL strategy can quickly discover more useful information from the search experiences and efficiently utilize the information to construct a more promising solution, and thereby provide a systematic and elaborate reasoning method to guide the search directions of POLBBO. The proposed POLBBO is verified on a set of 24 benchmark functions with diverse complexities, and is compared with the basic BBO, five state-of-the-art BBO variants, five existing OL-based algorithms, and nine other evolutionary algorithms. The experimental results and comparisons demonstrate that the polyphyletic migration operator and the OL strategy can work together well and enhance the performance of BBO significantly in terms of the quality of the final solutions and the convergence rate.     

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.     

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.     

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.     

An analysis of the equilibrium of migration models for biogeography-based optimization

Motivated by the migration mechanisms of ecosystems, various extensions to biogeography-based optimization (BBO) are proposed here. As a global optimization method, BBO is an original algorithm based on the mathematical model of organism distribution in biological systems. BBO is an evolutionary process that achieves information sharing by biogeography-based migration operators. In BBO, habitats represent candidate problem solutions, and species migration represents the sharing of features between candidate solutions according to the fitness of the habitats. This paper generalizes equilibrium species count results in biogeography theory, explores the behavior of six different migration models in BBO, and investigates performance through 23 benchmark functions with a wide range of dimensions and diverse complexities. The performance study shows that sinusoidal migration curves provide the best performance among the six different models that we explored. In addition, comparison with other biology-based optimization algorithms is investigated, and the influence of the population size, problem dimension, mutation rate, and maximum migration rate of BBO are also studied.     

Design of planar concentric circular antenna arrays with reduced side lobe level using symbiotic organisms search

This paper investigates the design of concentric circular antenna arrays (CCAAs) with optimum side lobe level reduction using the Symbiotic Organisms Search (SOS) algorithm. Both thinned and full CCAAs are considered. SOS represents a rather new evolutionary algorithm for antenna array optimization. SOS is inspired by the symbiotic interaction strategies between different organisms in an ecosystem. SOS uses simple expressions to model the three common types of symbiotic relationships: mutualism, commensalism, and parasitism. These expressions are used to find the global minimum of the fitness function. Unlike other methods, SOS is free of tuning parameters, which makes it an attractive optimization method. The results obtained using SOS are compared to those obtained using several optimization methods, like Biogeography-Based Optimization (BBO), Teaching-Learning-Based Optimization (TLBO), and Evolutionary Programming (EP). It is shown that the SOS is a robust straightforward evolutionary algorithm that competes with other known methods.

     

Biogeography-based optimization with improved migration operator and self-adaptive clear duplicate operator

Biogeography-based optimization (BBO) is a new emerging population-based algorithm that has been shown to be competitive with other evolutionary algorithms. However, there are some insufficiencies in solving complex problems, such as poor population diversity and slow convergence speed in the later stage. To overcome these shortcomings, we propose an improved BBO (IBBO) algorithm integrating a new improved migration operator, Gaussian mutation operator, and self-adaptive clear duplicate operator. The improved migration operator simultaneously adopts more information from other habitats, maintains population diversity, and preserves exploitation ability. The self-adaptive clear duplicate operator can clear duplicate or almost identical habitats, while also preserving population diversity through a self-adaptation threshold within the evolution process. Simulation results and comparisons from the experimental tests conducted on 23 benchmark functions show that IBBO achieves excellent performance in solving complex problems compared with other variants of the BBO algorithm and other evolutionary algorithms. The performance of the improved migration operator is also discussed.     

Efficiently finding the optimum number of clusters in a dataset with a new hybrid differential evolution algorithm: DELA

Clustering algorithms, a fundamental base for data mining procedures and learning techniques, suffer from the lack of efficient methods for determining the optimal number of clusters to be found in an arbitrary dataset. The few methods existing in the literature always use some sort of evolutionary algorithm having a cluster validation index as its objective function. In this article, a new evolutionary algorithm, based on a hybrid model of global and local heuristic search, is proposed for the same task, and some experimentation is done with different datasets and indexes. Due to its design, independent of any clustering procedure, it is applicable to virtually any clustering method like the widely used \(k\)-means algorithm. Moreover, the use of non-parametric statistical tests over the experimental results, clearly show the proposed algorithm to be more efficient than other evolutionary algorithms currently used for the same task.     

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.     

基于不确定度采样准则的费时问题优化算法

在实际工程和控制领域中,许多优化问题的性能评价是费时的,由于进化算法在获得最优解之前需要大量的目标函数评价,无法直接应用其求解这类费时问题.引入代理模型以辅助进化算法是求解计算费时优化问题的有效方法,如何采样新个体对其进行真实的目标函数评价是影响代理模型辅助的进化算法寻优性能的重要因素.鉴于此,利用径向基函数神经网络作...     

A hybrid cuckoo search-genetic algorithm for hole-making sequence optimization

Biologically-inspired algorithms are stochastic search methods that emulate the behavior of natural biological evolution to produce better solutions and have been widely used to solve engineering optimization problems. In this paper, a new hybrid algorithm is proposed based on the breeding behavior of cuckoos and evolutionary strategies of genetic algorithm by combining the advantages of genetic algorithm into the cuckoo search algorithm. The proposed hybrid cuckoo search-genetic algorithm (CSGA) is used for the optimization of hole-making operations in which a hole may require various tools to machine its final size. The main objective considered here is to minimize the total non-cutting time of the machining process, including the tool positioning time and the tool switching time. The performance of CSGA is verified through solving a set of benchmark problems taken from the literature. The amount of improvement obtained for different problem sizes are reported and compared with those by ant colony optimization, particle swarm optimization, immune based algorithm and cuckoo search algorithm. The results of the tests show that CSGA is superior to the compared algorithms.     

基于目标空间划分的自适应多目标进化算法

目前,多目标进化算法在众多领域具有极高的应用价值,是优化领域的研究热点之一.分析已有多目标进化算法在保持种群多样性方面的不足并提出一种基于解空间划分的自适应多目标进化算法（space division basedadaptive multiobjective evolutionary algorithm,简称SDA-MOEA）来解决多目标优化问题.该方法首先将多目标优化问题的解空间划分为大量子空间,在算法进化过程中,每个子空间都保留一个非支配解集,以保证种群的多样性.另外,该方法根据每个子空间推进种群前进的距离,自适应地为每个子空间分配进化机会,以提高种群的进化速度.最后,利用3组共14个多目标优化问题检验SDA-MOEA的性能,并将SDA-MOEA与其他5个已有多目标进化算法进行对比分析.实验结果表明：在10个问题上,算法SDA-MOEA显著优于其他对比算法.     

正交演化算法在继电器体积优化设计中的应用

继电器产品的优化设计是在给定的负载条件或环境条件下,在对继电器产品的性态、几何尺寸关系或其他因素限制约束范围内,确定设计参数、目标函数、约束条件以形成优化设计模型,并选择恰当的优化方法以获得最佳设计方案的一系列工作。继电器的体积数学模型涉及到机、电、磁、热等方面,其目标函数和约束函数均是高度非线性的。传统演化算法求解问题时容易陷入局部极小值。在简单演化算法的基础上,结合正交实验法的基本思想,将其应用于演化算法的种群初始化、交叉算子,并引入自适应正交局部搜索来防止局部收敛,得到了一种新型的正交演化算法。通过一系列数值实验验证了该算法的高效性。