A variable reduction strategy for evolutionary algorithms handling equality constraints

Efficient constraint handling techniques are of great significance when Evolutionary Algorithms (EAs) are applied to constrained optimization problems (COPs). Generally, when use EAs to deal with COPs, equality constraints are much harder to satisfy, compared with inequality constraints. In this study, we propose a strategy named equality constraint and variable reduction strategy (ECVRS) to reduce equality constraints as well as variables of COPs. Since equality constraints are always expressed by equations, ECVRS makes use of the variable relationships implied in such equality constraint equations. The essence of ECVRS is it makes some variables of a COP considered be represented and calculated by some other variables, thereby shrinking the search space and leading to efficiency improvement for EAs. Meanwhile, ECVRS eliminates the involved equality constraints that providing variable relationships, thus improves the feasibility of obtained solutions. ECVRS is tested on many benchmark problems. Computational results and comparative studies verify the effectiveness of the proposed ECVRS.     

An adaptive penalty based covariance matrix adaptation–evolution strategy

Although most of unconstrained optimization problems with moderate to high dimensions can be easily handled with Evolutionary Computation (EC) techniques, constraint optimization problems (COPs) with inequality and equality constraints are very hard to deal with. Despite the fact that only equality constraints can be used to eliminate a certain variable, both types of constraints implicitly enforce a relation between problem variables. Most conventional constraint handling methods in EC do not consider the correlations between problem variables imposed by the problem constraints. This paper relies on the idea that a proper genetic operator, which captures mentioned implicit correlations, can improve performance of evolutionary constrained optimization algorithms. With this in mind, we employ a (μ+λ)-Evolution Strategy with a simplified variant of Covariance Matrix Adaptation based mutation operator along an adaptive weight adjustment scheme. The proposed algorithm is tested on two test sets. The outperformance of the algorithm is significant on the first benchmark when compared with five conventional methods. The results on the second test set show that algorithm is highly competitive when benchmarked with three state-of-art algorithms. The main drawback of the algorithm is its slightly lower speed of convergence for problems with high dimension and/or large search domain.     

A Multiobjective Optimization-Based Evolutionary Algorithm for Constrained Optimization

A considerable number of constrained optimization evolutionary algorithms (COEAs) have been proposed due to increasing interest in solving constrained optimization problems (COPs) by evolutionary algorithms (EAs). In this paper, we first review existing COEAs. Then, a novel EA for constrained optimization is presented. In the process of population evolution, our algorithm is based on multiobjective optimization techniques, i.e., an individual in the parent population may be replaced if it is dominated by a nondominated individual in the offspring population. In addition, three models of a population-based algorithm-generator and an infeasible solution archiving and replacement mechanism are introduced. Furthermore, the simplex crossover is used as a recombination operator to enrich the exploration and exploitation abilities of the approach proposed. The new approach is tested on 13 well-known benchmark functions, and the empirical evidence suggests that it is robust, efficient, and generic when handling linear/nonlinear equality/inequality constraints. Compared with some other state-of-the-art algorithms, our algorithm remarkably outperforms them in terms of the best, mean, and worst objective function values and the standard deviations. It is noteworthy that our algorithm does not require the transformation of equality constraints into inequality constraints     

A simple and efficient real-coded genetic algorithm for constrained optimization

This paper presents a simple and efficient real-coded genetic algorithm (RCGA) for constrained real-parameter optimization. Different from some conventional RCGAs that operate evolutionary operators in a series framework, the proposed RCGA implements three specially designed evolutionary operators, named the ranking selection (RS), direction-based crossover (DBX), and the dynamic random mutation (DRM), to mimic a specific evolutionary process that has a parallel-structured inner loop. A variety of benchmark constrained optimization problems (COPs) are used to evaluate the effectiveness and the applicability of the proposed RCGA. Besides, some existing state-of-the-art optimization algorithms in the same category of the proposed algorithm are considered and utilized as a rigorous base of performance evaluation. Extensive comparison results reveal that the proposed RCGA is superior to most of the comparison algorithms in providing a much faster convergence speed as well as a better solution accuracy, especially for problems subject to stringent equality constraints. Finally, as a specific application, the proposed RCGA is applied to optimize the GaAs film growth of a horizontal metal-organic chemical vapor deposition reactor. Simulation studies have confirmed the superior performance of the proposed RCGA in solving COPs.     

基于牛顿法的并行优化算法

针对非线性数值优化问题,提出一种在分布式环境下的基于牛顿法的并行算法。引入松弛变量,将不等式约束转换为等式约束,利用广义拉格朗日乘子将约束优化问题转换为无约束子优化问题。为了并行地求解这些子优化问题,将Newton迭代法中的Hessian矩阵进行适当的分裂,采用简单迭代法求解Newton法中的线性方程组。在理论上对该算法进行了收敛性分析。在HP rx2600集群上进行的数值实验结果表明并行效率达90%以上。     

约束优化进化算法

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

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

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

Solving linear generalized Nash equilibrium problems numerically

This paper considers the numerical solution of linear generalized Nash equilibrium problems (LGNEPs). Since many methods for nonlinear problems require the nonsingularity of some second-order derivative, standard convergence conditions are not satisfied in our linear case. We provide new convergence criteria for a potential reduction algorithm (PRA) that allow its application to LGNEPs. Furthermore, we discuss a projected subgradient method (PSM) and a penalty method that exploit some known Nikaido–Isoda function-based constrained and unconstrained optimization reformulations of the LGNEP. Moreover, it is shown that normalized Nash equilibria of an LGNEP can be obtained by solving a single linear program. All proposed algorithms are tested on randomly generated instances of economic market models that are introduced and analysed in this paper and that lead to LGNEPs with shared and with non-shared constraints. It is shown that these problems have some favourable properties that can be exploited to obtain their solutions. With the PRA and in particular with the PSM we are able to compute solutions with satisfying precision even for problems with up 10,000 variables.     

Biogeography-based optimization for constrained optimization problems

Biogeography-based optimization (BBO) has been recently proposed as a viable stochastic optimization algorithm and it has so far been successfully applied in a variety of fields, especially for unconstrained optimization problems. The present paper shows how BBO can be applied for constrained optimization problems, where the objective is to find a solution for a given objective function, subject to both inequality and equality constraints.     

Greedy algorithms for a class of knapsack problems with binary weights

In this article we identify a class of two-dimensional knapsack problems with binary weights and related three-criteria unconstrained combinatorial optimization problems that can be solved in polynomial time by greedy algorithms. Starting from the knapsack problem with two equality constraints we show that this problem can be solved efficiently by using an appropriate partitioning of the items with respect to their binary weights. Based on the results for this problem we derive an algorithm for the three-criteria unconstrained combinatorial optimization problem with two binary objectives that explores the connectedness of the set of efficient knapsacks with respect to a combinatorial definition of adjacency. Furthermore, we prove that our approach is asymptotically optimal and provide extensive computational experiments that shows that we can solve the three-criteria problem with up to one million items in less than half an hour. Finally, we derive an efficient algorithm for the two-dimensional knapsack problems with binary constraints that only takes into account the results we obtained for the unconstrained three-criteria problem with binary weights.     

免疫克隆多目标优化算法求解约束优化问题

针对现有的约束处理技术的一些不足之处,提出一种用于求解约束优化问题的算法——免疫克隆多目标优化算法(immune clonal multi-objective optimization algorithm,简称ICMOA).算法的主要特点是通过将约束条件转化为一个目标,从而将问题转化为两个目标的多目标优化问题.引入多目标优化中的Pareto-支配的概念,每一个个体根据其被支配的程度进行克隆、变异及选择等操作.克隆操作实现了全局择优,有利于得到高质量的解;变异操作提高算法的局部搜索能力,有利于所得解的多样性;选择操作有利于算法向着最优搜索,而且加快了收敛速度.基于抗体群的随机状态转移过程,证明该算法具有全局收敛性.通过对13个标准测试问题的测试,并与已有算法进行比较。结果表明,该算法在收敛速度和求解精度上均具有一定的优势.     

A ranking selection-based particle swarm optimizer for engineering design optimization problems

Particle swarm optimization (PSO) algorithms have been proposed to solve optimization problems in engineering design, which are usually constrained (possibly highly constrained) and may require the use of mixed variables such as continuous, integer, and discrete variables. In this paper, a new algorithm called the ranking selection-based PSO (RSPSO) is developed. In RSPSO, the objective function and constraints are handled separately. For discrete variables, they are partitioned into ordinary discrete and categorical ones, and the latter is managed and searched directly without the concept of velocity in the standard PSO. In addition, a new ranking selection scheme is incorporated into PSO to elaborately control the search behavior of a swarm in different search phases and on categorical variables. RSPSO is relatively simple and easy to implement. Experiments on five engineering problems and a benchmark function with equality constraints were conducted. The results indicate that RSPSO is an effective and widely applicable optimizer for optimization problems in engineering design in comparison with the state-of-the-art algorithms in the area.     

组织进化数值优化算法

基于经济学中“组织”的概念 ,该文提出一种新的进化算法———组织进化算法 ,来解决无约束和有约束的数值优化问题 .该算法与传统遗传算法、进化规划、进化策略的运行机制完全不同 ,其进化操作不直接作用于个体上 ,而作用在组织上 ,为此 ,该文定义了三种组织进化算子———分裂算子、吞并算子和合作算子来引导种群进化 .理论分析证明组织进化算法具有全局收敛性 .实验中 ,用 4个无约束和 6个有约束标准函数对算法进行了测试 ,与 3个新算法作了比较 ,并对组织进化算法的性能作了深入分析 .结果表明 ,该文算法无论在解的质量上还是在计算复杂度上都优于其它算法 .对于有约束问题 ,只用了简单的静态罚函数就得到了良好的效果 ,这表明该文算法的搜索机制非常有效 ,不易陷入局部最优 .最后 ,参数分析的结果表明该文算法具有性能稳定、成功率高、对参数不敏感等优越的性能     

Performance of a bell-curve based evolutionary optimization algorithm

An evolutionary search strategy utilizing two normal distributions to generate children is presented. This Bell-Curve Based (BCB) evolutionary algorithm is similar in spirit to (μ+μ) evolutionary strategies but with fewer parameters to adjust. Extensive tests regarding the sensitivity of BCB parameters to performance are provided. The test suite includes continuous variable constrained hub design problems, mixed discrete and continuous variable constrained hub design problems, and an unconstrained highly multimodal discrete optimization problem. Received March 23, 2000     

SO-MI: A surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems

This paper introduces a surrogate model based algorithm for computationally expensive mixed-integer black-box global optimization problems with both binary and non-binary integer variables that may have computationally expensive constraints. The goal is to find accurate solutions with relatively few function evaluations. A radial basis function surrogate model (response surface) is used to select candidates for integer and continuous decision variable points at which the computationally expensive objective and constraint functions are to be evaluated. In every iteration multiple new points are selected based on different methods, and the function evaluations are done in parallel. The algorithm converges to the global optimum almost surely. The performance of this new algorithm, SO-MI, is compared to a branch and bound algorithm for nonlinear problems, a genetic algorithm, and the NOMAD (Nonsmooth Optimization by Mesh Adaptive Direct Search) algorithm for mixed-integer problems on 16 test problems from the literature (constrained, unconstrained, unimodal and multimodal problems), as well as on two application problems arising from structural optimization, and three application problems from optimal reliability design. The numerical experiments show that SO-MI reaches significantly better results than the other algorithms when the number of function evaluations is very restricted (200–300 evaluations).     

大规模过程系统优化方法

基于非线性约束的序列界无约束极小化方法,对大规模过程系统稳态优化的序列界约束极小化方法(SBCMM)进行了研究.对工程模型引进松弛变量处理后,SBCMM的罚函数仅包含等式约束的惩罚项,不包含界约束及不等式约束的惩罚项.原问题的解由求解一系列界约束极小化子问题而非无约束极小化子问题来获得.最后,用一类规模可变的非线性规划...     

A parallel boundary search particle swarm optimization algorithm for constrained optimization problems

During the past decade, considerable research has been conducted on constrained optimization problems (COPs) which are frequently encountered in practical engineering applications. By introducing resource limitations as constraints, the optimal solutions in COPs are generally located on boundaries of feasible design space, which leads to search difficulties when applying conventional optimization algorithms, especially for complex constraint problems. Even though penalty function method has been frequently used for handling the constraints, the adjustment of control parameters is often complicated and involves a trial-and-error approach. To overcome these difficulties, a modified particle swarm optimization (PSO) algorithm named parallel boundary search particle swarm optimization (PBSPSO) algorithm is proposed in this paper. Modified constrained PSO algorithm is adopted to conduct global search in one branch while Subset Constrained Boundary Narrower (SCBN) function and sequential quadratic programming (SQP) are applied to perform local boundary search in another branch. A cooperative mechanism of the two branches has been built in which locations of the particles near boundaries of constraints are selected as initial positions of local boundary search and the solutions of local boundary search will lead the global search direction to boundaries of active constraints. The cooperation behavior of the two branches effectively reinforces the optimization capability of the PSO algorithm. The optimization performance of PBSPSO algorithm is illustrated through 13 CEC06 test functions and 5 common engineering problems. The results are compared with other state-of-the-art algorithms and it is shown that the proposed algorithm possesses a competitive global search capability and is effective for constrained optimization problems in engineering applications.     

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.     

矩阵方程的分布式求解算法研究概述

近年来,随着大规模网络的兴起和分布式优化理论的广泛应用,矩阵方程的分布式求解算法研究也受到了越来越多的重视.矩阵方程的计算求解在理论和工程领域都有着重要的意义.在多智能体网络下的分布式计算问题中,矩阵方程中的数据信息按照各种方式进行划分,单个智能体只能够获取其中的一份数据,然后通过与其邻居智能体进行信息交互,最终合作求解出不同类型的符合方程要求的解.本文集中讨论了近几年来针对线性代数方程、几类不带约束和带约束线性矩阵方程、以及其他矩阵相关的分布式计算和求解问题,介绍了投影一致方法、转化成分布式优化问题再求解的方法、以及针对特殊矩阵如稀疏矩阵的信息传递方法等分布式算法设计方法.最后,简要总结全文以及对分布式矩阵计算方向的研究进行了展望.     

State estimation for linear systems with state equality constraints

This paper deals with the state estimation problem for linear systems with linear state equality constraints. Using noisy measurements which are available from the observable system, we construct the optimal estimate which also satisfies linear equality constraints. For this purpose, after reviewing modeling problems in linear stochastic systems with state equality constraints, we formulate a projected system representation. By using the constrained Kalman filter for the projected system and comparing its filter Riccati equation with those of the unconstrained and the projected Kalman filters, we clearly show, without using optimality, that the constrained estimator outperforms the other filters for estimating the constrained system state. Finally, a numerical example is presented, which demonstrates performance differences among those filters.