解决多目标优化问题的差分进化算法研究进展

差分进化(differential evolution,DE)是一种简单但功能强大的进化优化算法.由于其优秀的性能,其诞生之日起就吸引了各国研究人员的关注.作为一种基于群体的全局性启发式搜索算法,差分进化算法在科学和工程中有许多成功的应用.本文对解决多目标优化问题的差分进化算法研究进行了综述,对差分进化的基本概念进行了详细的描述,给出了几种解决多目标优化问题的差分进化算法变体,并且给出了差分进化算法解决多目标优化问题的理论分析,最后,给出了差分进化算法解决多目标优化问题的工程应用,并指出了未来具有挑战性的研究领域.     

差分进化算法综述

差分进化算法由于算法结构简单易于执行,并且具有优化效率高、参数设置简单、鲁棒性好等优点,因此差分进化算法吸引了越来越多研究者的关注。本文概述了差分进化算法的基本概念以及存在的问题,综述了差分进化算法的控制参数、差分策略、种群结构以及与其他最优化算法混合等4个方面改进策略并讨论它们各自的优缺点,为差分进化算法下一步的改进提出了参考方向。     

引入模拟退火算子的差分进化算法性能研究

为了提高差分进化算法的优化性能,将模拟退火算子引入到差分进化算法中,利用模拟退火算子良好的全局搜索能力进一步提高差分进化算法对复杂问题的优化能力．通过对复杂函数优化的仿真结果表明,算法在求解复杂优化问题上具有更快的收敛速度和更好的全局收敛性．     

一种基于粒子群优化算法和差分进化算法的新型混合全局优化算法

提出一种基于粒子群算法(PSO)和差分进化算法(DE)相结合的新型混合全局优化算法——PSODE．该算法基于一种双种群进化策略，一个种群中的个体由粒子群算法进化而来，另一种群的个体由差分操作进化而来．此外，通过采用一种信息分享机制，在算法执行过程中两个种群中的个体可以实现协同进化．为了进一步提高PSODE算法的性能，摆脱陷入局部最优点，还采用了一种变异机制．通过4个标准测试函数的测试并与PSO和DE算法进行比较，证明本文提出的PSODE算法是一种收敛速度快、求解精度高、鲁棒性较强的全局优化算法．     

混合差分变异策略

为了改善差分进化算法的求解性能,提出一种新的混合差分变异策略．该策略将种群中的每一个个体视作带电粒子,利用粒子所带的电荷量以及粒子之间的吸引排斥机制确定个体移动方向和位移大小．该策略会使个体在其他3个个体施加于它的力的方向上自适应地移动．数值实验表明基于该策略的差分进化算法求解精度高、评估次数少．     

基于搜索空间大小的动态变异算子差分进化算法

差分进化算法（DE）是一种较新的进化计算技术,具有概念简单、易于实现、收敛速度快等优点,得到了广泛的关注和应用.为了解决经典DE计算开销大,参数设置与问题本身过于相关等缺陷,提出了一种改进的差分进化算法（IDE）,它采用了一种动态变异算子,可根据进化代数的增加,基于搜索空间大小,实时地调整变异步长,从而提高算法的求解精度.通过在MATLAB仿真环境下对著名的基准测试函数分别进行求解,将改进后的算法和已有的多种优化算法进行比较,结果表明,改进的IDE算法性能明显优于已知的算法,证明动态变异是一种有效的改进思路.     

差分型复杂过程全局进化方法

复杂过程全局进化算法是一种具有类似分散搜索的通用框架结构,能够高效完成全局搜索的新型进化算法。在该算法的基础上,提出了差分型复杂过程全局进化算法。差分型算法采用拉丁超立方体抽样生成多样性种群,并应用“最小欧几里德距离的最大值法”产生参考集Refset2,以保证参考集的多样性。采用差分变异和交叉策略替代原算法的线性合并,兼顾算法的收敛速度和种群的多样性。应用Nelder-Mead直接搜索法进行局部搜索,防止搜索过程在局部最优点附近反复。仿真结果表明差分型复杂过程全局进化算法,具有较高的搜索效率。     

一种基于混合策略的差分进化算法研究

差分进化算法DE(Differental Evolution)是一种著名的处理非线性复杂问题的优化技术。为改进其计算开销大、参数设置与问题本身特性过于相关等缺陷,提出一种混合策略的差分进化算法HDE(Hybrid DE)。它混合反向学习OBL(Opposition-based Learning)和自适应机制来进行参数调整,从而能加速算法收敛,同时提高求解成功率。在MATLAB环境中进行的测试实验结果表明,HDE在收敛速度,鲁棒性和计算开销等方面的性能在大部分测试用例上优于已有的多种算法。这表明混合策略是一种行之有效的差分进化算法的研究路径。     

差分进化粒子群混合优化算法的研究与应用

对基本粒子群算法（PSO）和差分进化算法（DE）进行了分析,有机结合两种进化算法提出了一种新型差分进化粒子群混合优化算法,该算法将优化过程分成两阶段,两分群分别采用PSO算法和DE算法同时进行。迭代过程中引入进化速度因子并通过群体间的信息交流阻止算法陷入局部最优。对4个高维复杂函数寻优测试表明算法的鲁棒性、收敛速度和精度,全局搜索能力均优于常规PSO和DE。将提出的改进算法用于乙烯收率软测量建模,应用结果表明模型精度较高、泛化性能较好。     

基于混沌和差分进化的混合粒子群优化算法

研究粒子群算法优化问题,由于标准粒子群优化算法(PSO)在高维复杂函数优化中易早收敛,影响全系统优化。为改进的混合粒子群优化算法,提出了一种基于混沌和差分进化的混合粒子群优化算法(CDEHPSO)。把基于Logistic映射的混沌序列引入到种群初始化操作中。在算法进化过程中,通过一种粒子早熟判断机制,在基本粒子群优化算法中引入了差分变异、交叉和选择操作,对早熟粒子个体进行差分进化操作,从而维持了种群的多样性并有效避免了算法陷入局部最优。仿真结果表明,相比于粒子群优化算法和差分进化算法(DE),CDEHPSO算法具有收敛速度快、搜索能力强的优点。     

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.     

Adaptive strategy selection in differential evolution for numerical optimization: An empirical study

Differential evolution (DE) is a versatile and efficient evolutionary algorithm for global numerical optimization, which has been widely used in different application fields. However, different strategies have been proposed for the generation of new solutions, and the selection of which of them should be applied is critical for the DE performance, besides being problem-dependent. In this paper, we present two DE variants with adaptive strategy selection: two different techniques, namely Probability Matching and Adaptive Pursuit, are employed in DE to autonomously select the most suitable strategy while solving the problem, according to their recent impact on the optimization process. For the measurement of this impact, four credit assignment methods are assessed, which update the known performance of each strategy in different ways, based on the relative fitness improvement achieved by its recent applications. The performance of the analyzed approaches is evaluated on 22 benchmark functions. Experimental results confirm that they are able to adaptively choose the most suitable strategy for a specific problem in an efficient way. Compared with other state-of-the-art DE variants, better results are obtained on most of the functions in terms of quality of the final solutions and convergence speed.     

求解高维多模优化问题的自适应差分进化算法

在基变量选择方差理论分析的基础上,提出一种自适应差分进化算法(ADE).ADE算法通过设计自适应收敛因子构建自调整的权重质心变异策略,同时在交叉策略中引入发射、收缩两种单纯形操作算子,保证算法全局搜索能力的同时,能钉效提高算法后期的局部增强能力.30个优化问题的数值研究结果表明ADE算法具有比DE、DERL以及DERB三种算法更快的收敛速度和可靠性,尤其适合于高维多模优化问题的求解.     

差分进化计算研究综述

差分进化计算(DE)是继遗传算法、微粒子群算法、蚁群算法之后的又一个成功的智能算法。它有三个算子即变异算子、交叉算子、选择算子。差分进化利用种群中个体之间的差异信息实现向最优解区域的搜索。实验证明,该算法具有较好的鲁棒性和求解效率。针对该算法的基本思想以及当前的部分研究成果进行了分析介绍。最后对下一步的研究进行了相应的说明和展望。     

A directional mutation operator for differential evolution algorithms

Differential evolution (DE) is widely studied in the past decade. In its mutation operator, the random variations are derived from the difference of two randomly selected different individuals. Difference vector plays an important role in evolution. It is observed that the best fitness found so far by DE cannot be improved in every generation. In this article, a directional mutation operator is proposed. It attempts to recognize good variation directions and increase the number of generations having fitness improvement. The idea is to construct a pool of difference vectors calculated when fitness is improved at a generation. The difference vector pool will guide the mutation search in the next generation once only. The directional mutation operator can be applied into any DE mutation strategy. The purpose is to speed up the convergence of DE and improve its performance. The proposed method is evaluated experimentally on CEC 2005 test set with dimension 30 and on CEC 2008 test set with dimensions 100 and 1000. It is demonstrated that the proposed method can result in a larger number of generations having fitness improvement than classic DE. It is combined with eleven DE algorithms as examples of how to combine with other algorithms. After its incorporation, the performance of most of these DE algorithms is significantly improved. Moreover, simulation results show that the directional mutation operator is helpful for balancing the exploration and exploitation capacity of the tested DE algorithms. Furthermore, the directional mutation operator modifications can save computational time compared to the original algorithms. The proposed approach is compared with the proximity based mutation operator as both are claimed to be applicable to any DE mutation strategy. The directional mutation operator is shown to be better than the proximity based mutation operator on the five variants in the DE family. Finally, the applications of two real world engineering optimization problems verify the usefulness of the proposed method.     

Assembly Line Balancing Using Differential Evolution Models

There is a growing research interest on the application of evolutionary computation-based techniques in manufacturing optimization due to the fact that this field is associated with a plethora of complex combinatorial optimization problems. Differential evolution (DE), one of the latest developed evolutionary algorithms, has rarely been applied on manufacturing optimization problems (MOPs). A possible reason for the absence of DE from this research field is that DE was introduced as global optimizer over continuous spaces, while most of MOPs are of combinatorial nature with discrete decision variables. DE maintains and evolves floating-point vectors and therefore its application to MOPs that have solutions represented by permutations is not straightforward. This paper investigates the use of DE for the solution of the simple assembly line balancing problem (SALBP), a well-known NP-hard MOP. Two basic formulation types for SALBP are examined, namely type-1 and type-2: the former attempts to minimize the number of workstations required to manufacture a product in an assembly line for a given fixed cycle time; while the latter attempts to minimize the cycle time of the line for a given number of stations. Extensive experiments carried out over public benchmarks test instances estimate the performance of DE approach.     

基于分布估计的离散差分演化算法

差分演化(DE)是解决优化问题的非常有效的新兴智能算法,但它主要用于连续优化领域,至今尚不能象解决连续优化问题那样有效的处理组合优化问题.首先提出了离散DE用于组合优化问题,然后在离散DE中引入分布估计算法(EDA)来提高性能,把EDA抽样得到的全局统计信息和离散DE获得的局部演化信息相结合来产生新解,形成基于EDA的离散DE算法.为了保持种群多样性,在提出的算法中引入了位翻转变异操作.实验结果表明,EDA能大大提高离散DE的性能.     

An improved firefly algorithm for solving dynamic multidimensional knapsack problems

There is a wide range of publications reported in the literature, considering optimization problems where the entire problem related data remains stationary throughout optimization. However, most of the real-life problems have indeed a dynamic nature arising from the uncertainty of future events. Optimization in dynamic environments is a relatively new and hot research area and has attracted notable attention of the researchers in the past decade. Firefly Algorithm (FA), Genetic Algorithm (GA) and Differential Evolution (DE) have been widely used for static optimization problems, but the applications of those algorithms in dynamic environments are relatively lacking. In the present study, an effective FA introducing diversity with partial random restarts and with an adaptive move procedure is developed and proposed for solving dynamic multidimensional knapsack problems. To the best of our knowledge this paper constitutes the first study on the performance of FA on a dynamic combinatorial problem. In order to evaluate the performance of the proposed algorithm the same problem is also modeled and solved by GA, DE and original FA. Based on the computational results and convergence capabilities we concluded that improved FA is a very powerful algorithm for solving the multidimensional knapsack problems for both static and dynamic environments.