约束优化进化算法综述

约束优化进化算法主要研究如何利用进化计算方法求解约束优化问题,是进化计算领城的一个重要研究课题.约束优化问题求解存在约束区域离散、等式约束、非线性约束等挑战,其问题的本质是如何处理可行解与不可行解的关系才能使得算法更高效.本文首先介绍了约束优化问题的定义,然后系统地分析了目前存在的约束优化方法,同时基于约束处理机制将这些方法分为罚函数法、可行性法则、随机排序法、约束处理法、多目标优化法、混合法六类,并从约束处理方法的方面对约束优化进化算法的最新研究进展进行综述.最后,指出约束优化进化算法需进一步研究的方向与关键问题.     

约束优化进化算法

约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.近年来,约束优化问题求解已成为进化计算研究的一个重要方向.从约束优化进化算法=约束处理技术+进化算法的研究框架出发,从约束处理技术和进化算法两个基本方面对约束优化进化算法的研究及进展进行了综述.此外,对约束优化进化算法中的一些重要问题进行了探讨.最后进行了各种算法的比较性总结,深入分析了目前约束优化进化算法中亟待解决的问题,并指出了值得进一步研究的方向.     

解约束优化问题的一种新的罚函数模型

罚函数法是进化算法中解决约束优化问题最常用的方法之一,它通过对不可行解进行惩罚使得搜索逐步进入可行域.罚函数常定义为目标函数与惩罚项之和,其缺陷一方面在于此模型的罚因子难以控制,另一方面当目标函数值与惩罚项的函数值的差值很大时,此模型不能有效地区分可行解与不可行解,从而不能有效处理约束.为了克服这些缺点,首先引入了目标满意度函数与约束满意度函数,前者是根据目标函数对解的满意度给出的一个度量,而后者是根据约束违反度对解的满意度给出的一个度量.然后将两者有机结合,定义了一种新的罚函数,给出了一种新的罚函数模型.并且设置了自适应动态罚因子,其随着当前种群质量和进化代数的改变而改变.因此它很易于控制.进一步设计了新的杂交和变异算子,在此基础上提出了解决约束优化问题的一种新的进化算法.通过对6个常用标准测试函数所作的数据仿真实验表明,提出的算法是十分有效的.     

求解约束优化问题的ε-DE 算法

差分进化(differential evolution,简称DE)算法解决约束优化问题(constrained optimization problems,简称COPs)时通常采用可行解优先的比较规则,但是该方法不能利用种群中不可行解的信息.设计了可以利用不可行解信息的ε-DE算法.该算法通过构造一种比较准则,使得进化过程可以充分利用种群中优秀不可行解的信息.该准则通过引入种群约束允许放松程度的概念,在进化初始阶段使可行域边界上且拥有较优目标函数的不可行解进入种群;随着进化代数增加,种群约束允许放松程度不断减小,使得种群中不可行解数量减少,直到种群约束允许放松程度为0,种群完全由可行解组成.此外,还选择了一种改进的DE算法作为搜索算法,使得进化过程具有较快的收敛性.13个标准Benchmark函数实验仿真的结果表明:ε-DE算法是目前利用DE算法解决COPs问题中效果最好的.     

基于内部罚函数的进化算法求解约束优化问题

为解决现有约束处理方法可行解的适应度函数不包含约束条件的问题,提出了一种内部罚函数候选解筛选规则.该候选解筛选规则分别对可行解和不可行解采用内部罚函数和约束违反度进行筛选,从而达到平衡最小化目标函数和满足约束条件的目的.以进化策略算法为基础,给出了基于内部罚函数候选解筛选规则的进化算法的一个实现.进一步地,从理论和实验角度分别验证了内部罚函数候选解筛选规则的有效性:以(1+1)进化算法为例,从进化成功率方面验证了内部罚函数候选解筛选规则的理论有效性;通过13个测试问题的数值实验,从进化成功率、候选解后代是可行解的比例、进化步长和收敛速度方面验证了内部罚函数候选解筛选规则的实验有效性.     

约束多目标进化算法研究进展

约束多目标进化算法（CMOEAs）能够同时处理多个相互冲突的目标函数和约束条件,引导种群逼向可行域的最优解,受到了研究者的广泛重视。首先介绍了约束多目标优化问题（CMOPs）的相关定义和多目标进化算法（MOEAs）的三种分类;其次,系统地分析了当前CMOEAs中约束处理机制,凝练出当前主要的四种约束处理方法;然后,从基于支配、基于指标、基于分解三个方面对CMOEAs的研究进展进行了详细综述;最后,指明了CMOEAs存在的挑战和未来研究方向。     

面向复杂约束优化问题的进化算法综述

约束优化是多数实际工程应用优化问题的呈现方式.进化算法由于其高效的表现,近年来被广泛应用于约束优化问题求解.但约束条件使得问题解空间离散、缩小、改变,给进化算法求解约束优化问题带来极大挑战.在此背景下,融合约束处理技术的进化算法成为研究热点.此外,随着研究的深入,近年来约束处理技术在复杂工程应用问题优化中得到了广泛发展,例如多目标、高维、等式优化等.根据复杂性的缘由,将面向复杂约束优化问题的进化优化分为面向复杂目标的进化约束优化算法和面向复杂约束场景的进化算法两种类别进行综述,其中,重点探讨了实际工程应用的复杂性对约束处理技术的挑战和目前研究的最新进展,并最后总结了未来的研究趋势与挑战.     

一种新的自适应惩罚函数算法求解约束优化问题

提出一种新的自适应惩罚函数法,用来处理约束优化问题．这种方法根据当前群体中可行解的比例对目标函数和违反约束条件的程度作出合适的权衡,具有结构简单、参数少等优点．把它和一个简单的进化策略结合起来,得到了一种新的求解约束优化问题的进化算法．选取几个常见的测试函数对这种新方法进行了数值实验．结果表明,所提方法能够非常有效地处理各种约束优化问题,而且具有很强的稳健性;其性能优于或相似于一些尖端的算法．     

用于约束多目标优化问题的双群体差分进化算法

首先给出一种改进的差分进化算法,然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法.该算法同时使用两个群体,其中一个用于保存搜索过程中找到的可行解,另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解,避免了构造罚函数和直接删除不可行解.此外,文中算法、NSGA-Ⅱ和SPEA的时间复杂度的比较表明,NSGA-Ⅱ最优,文中算法与SPEA相当.对经典测试函数的仿真结果表明,与NSGA-Ⅱ相比较,文中算法在均匀性及逼近性方面均具有一定的优势.     

动态罚函数法求解约束优化问题

针对罚函数法在求解约束优化问题时罚系数不易选取的问题,提出一种基于动态罚函数的差分进化算法.利用罚函数法将约束优化问题转化为无约束优化问题.为平衡种群的目标函数和约束违反程度,结合ε约束法设计了一种动态罚系数策略,其中罚系数随着种群质量和进化代数的改变而改变.采用差分进化算法更新种群直到搜索到最优解.对IEEE CEC...     

求解约束优化的带偏好双目标优化方法

文章提出了一种求解约束优化问题的新方法。它把约束优化问题转化为双目标优化问题,一个目标是原问题的目标,另一目标是由约束条件转化得到。转化得到的双目标优化与一般的双目标优化问题不同在于它偏好那些使约束条件满足的最优解。我们利用动态权值将这一带有偏好的双目标优化转化为无约束的单目标优化,并使其满足偏好特性。我们对四个标准测试函数进行了数据仿真实验,实验结果表明该算法是有效的。     

改进罚函数法与蝙蝠算法在约束优化中的应用

设计了一种基于自适应罚函数法和改进蝙蝠算法的约束优化问题求解方法。提出了一种自适应罚函数法,该处理方法综合考虑了约束违反的情况和进化过程的特点,如果某个约束违反的次数越多,则证明该约束越强,赋予惩罚系数越大;种群中的不可行解的数量越多,为保持种群的多样性,则约束应该取较小的值,即惩罚系数取较小的值。提出了一种改进的蝙蝠算法,利用混沌的遍历性特点产生初始种群,增强了初始种群的多样性和种群的质量;在考虑了脉冲响度的蝙蝠算法局部搜索中,融入了交叉操作;为防止算法在后期陷入局部最优解,引进了变异操作,保证了群体的多样性。将自适应罚函数法与改进的蝙蝠算法融合起来求解约束优化问题,4个复杂的标准测试函数和2个工程实际问题证明了该约束优化求解方法的可行性和有效性。     

A new algorithm inspired in the behavior of the social-spider for constrained optimization

During the past decade, solving constrained optimization problems with swarm algorithms has received considerable attention among researchers and practitioners. In this paper, a novel swarm algorithm called the Social Spider Optimization (SSO-C) is proposed for solving constrained optimization tasks. The SSO-C algorithm is based on the simulation of cooperative behavior of social-spiders. In the proposed algorithm, individuals emulate a group of spiders which interact to each other based on the biological laws of the cooperative colony. The algorithm considers two different search agents (spiders): males and females. Depending on gender, each individual is conducted by a set of different evolutionary operators which mimic different cooperative behaviors that are typically found in the colony. For constraint handling, the proposed algorithm incorporates the combination of two different paradigms in order to direct the search towards feasible regions of the search space. In particular, it has been added: (1) a penalty function which introduces a tendency term into the original objective function to penalize constraint violations in order to solve a constrained problem as an unconstrained one; (2) a feasibility criterion to bias the generation of new individuals toward feasible regions increasing also their probability of getting better solutions. In order to illustrate the proficiency and robustness of the proposed approach, it is compared to other well-known evolutionary methods. Simulation and comparisons based on several well-studied benchmarks functions and real-world engineering problems demonstrate the effectiveness, efficiency and stability of the proposed method.     

求解约束优化问题的复合人工蜂群算法

针对约束优化问题,提出一种复合人工蜂群算法。该算法引入多维随机变异操作和最优引导变异操作平衡算法的探索能力和开发能力。将[ε]约束和可行性规则相结合平衡目标函数与约束,加快算法的收敛。通过对CEC 2006中20个测试函数和CEC 2010中18个测试函数及3个实际工程优化问题的实验结果分析表明,该算法对约束优化问题可行有效。     

An evolutionary algorithm with directed weights for constrained multi-objective optimization

When solving constrained multi-objective optimization problems (CMOPs), keeping infeasible individuals with good objective values and small constraint violations in the population can improve the performance of the algorithms, since they provide the information about the optimal direction towards Pareto front. By taking the constraint violation as an objective, we propose a novel constraint-handling technique based on directed weights to deal with CMOPs. This paper adopts two types of weights, i.e. feasible and infeasible weights distributing on feasible and infeasible regions respectively, to guide the search to the promising region. To utilize the useful information contained in infeasible individuals, this paper uses infeasible weights to maintain a number of well-diversified infeasible individuals. Meanwhile, they are dynamically changed along with the evolution to prefer infeasible individuals with better objective values and smaller constraint violations. Furthermore, 18 test instances and 2 engineering design problems are used to evaluate the effectiveness of the proposed algorithm. Several numerical experiments indicate that the proposed algorithm outperforms four compared algorithms in terms of finding a set of well-distributed non-domination solutions.     

Concurrent product configuration and process planning: Some optimization experimental results

In nowadays industrial competition, optimizing concurrently the configured product and the planning of its production process becomes a key issue in order to achieve mass customization development. However, if many studies have addressed these two problems separately, very few have considered them concurrently. We therefore consider in this article a multi-criteria optimization problem that follows an interactive configuration and planning process. The configuration and planning problems are considered as constraint satisfaction problems (CSPs). After some recalls about this two-step approach, we propose to evaluate a recent evolutionary optimization algorithm called CFB-EA (for constraint filtering based evolutionary algorithm). CFB-EA, specially designed to handle constrained problems, is compared with an exact branch and bound approach on small problem instances and with another evolutionary approach carefully selected for larger instances. Various experiments, with solutions spaces up to 10¹⁷, permit us to conclude that CFB-EA sounds very promising for the concurrent optimization of a configured product and its production process.