Using variable reduction strategy to accelerate evolutionary optimization

In this study, we introduce a novel approach of variable reduction and integrate it into evolutionary algorithms in order to reduce the complexity of optimization problems. We develop reduction processes of variable reduction for derivative unconstrained optimization problems (DUOPs) and constrained optimization problems (COPs) with equality constraints and active inequality constraints. Variable reduction uses the problem domain knowledge implied when investigating optimal conditions existing in optimization problems. For DUOPs, equations involving derivatives are considered while for COPs, we discuss equations expressing the equality constraints. From the relationships formed in this way, we obtain relationships among the variables that have to be satisfied by optimal solutions. According to such relationships, we can utilize some variables (referred to as core variables) to express some other variables (referred to as reduced variables). We show that the essence of variable reduction is to produce a minimum collection of core variables and a maximum number of reduced variables based on a system of equations. We summarize some application-oriented situations of variable reduction and stress several important issues related to the further application and development of variable reduction. Essentially, variable reduction can reduce the number of variables and eliminate equality constraints, thus reducing the dimensionality of the solution space and improving the efficiency of evolutionary algorithms. The approach can be applied to unconstrained, constrained, continuous and discrete optimization problems only if there are explicit variable relationships to be satisfied in the optimal conditions. We test variable reduction on real-world and synthesized DUOPs and COPs. Experimental results and comparative studies point at the effectiveness of variable reduction.     

Integrating Variable Reduction Strategy With Evolutionary Algorithms for Solving Nonlinear Equations Systems

Nonlinear equations systems (NESs) are widely used in real-world problems and they are difficult to solve due to their nonlinearity and multiple roots. Evolutionary algorithms (EAs) are one of the methods for solving NESs, given their global search capabilities and ability to locate multiple roots of a NES simultaneously within one run. Currently, the majority of research on using EAs to solve NESs focuses on transformation techniques and improving the performance of the used EAs. By contrast, problem domain knowledge of NESs is investigated in this study, where we propose the incorporation of a variable reduction strategy (VRS) into EAs to solve NESs. The VRS makes full use of the systems of expressing a NES and uses some variables (i.e., core variable) to represent other variables (i.e., reduced variables) through variable relationships that exist in the equation systems. It enables the reduction of partial variables and equations and shrinks the decision space, thereby reducing the complexity of the problem and improving the search efficiency of the EAs. To test the effectiveness of VRS in dealing with NESs, this paper mainly integrates the VRS into two existing state-of-the-art EA methods (i.e., MONES and DR-JADE) according to the integration framework of the VRS and EA, respectively. Experimental results show that, with the assistance of the VRS, the EA methods can produce better results than the original methods and other compared methods. Furthermore, extensive experiments regarding the influence of different reduction schemes and EAs substantiate that a better EA for solving a NES with more reduced variables tends to provide better performance.      

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 computational method for parameter optimization problems arising in control†

A parameter optimization procedure is presented for large-scale problems arising in linear control system design that include equality and inequality constraints. The procedure is based on a novel min—max algorithm for locating a constrained relative minimum without the use of penalty functions or slack variables. This algorithm is constructed from an auxiliary minimization problem with equality constraints. Inequality constraints then are introduced using the notion of an effective constraint. Typical problem formulations are discussed, and an extensive design example is presented.     

Comparing evolutionary algorithms on binary constraint satisfaction problems

Constraint handling is not straightforward in evolutionary algorithms (EAs) since the usual search operators, mutation and recombination, are 'blind' to constraints. Nevertheless, the issue is highly relevant, for many challenging problems involve constraints. Over the last decade, numerous EAs for solving constraint satisfaction problems (CSP) have been introduced and studied on various problems. The diversity of approaches and the variety of problems used to study the resulting algorithms prevents a fair and accurate comparison of these algorithms. This paper aligns related work by presenting a concise overview and an extensive performance comparison of all these EAs on a systematically generated test suite of random binary CSPs. The random problem instance generator is based on a theoretical model that fixes deficiencies of models and respective generators that have been formerly used in the evolutionary computing field.     

Designer’s preferences regarding equality constraints in robust design optimization

Robust design optimization (RDO) problems can generally be formulated by appropriately incorporating uncertainty into the corresponding deterministic optimization problems. Equality constraints in the deterministic problem need to be carefully formulated into the RDO problem because of the strictness associated with their feasibility. In this context, equality constraints have been generally classified into two types: (1) those that must be satisfied regardless of uncertainty, examples include physics-based constraints, such as F = ma, and (2) those that cannot be satisfied because of uncertainty, which are typically designer-imposed, such as dimensional constraints. This paper addresses the notion of preferred degree of satisfaction of deterministic equality constraints under uncertainty. Whether or not a particular equality constraint can be exactly satisfied depends on the statistical nature of the design variables that exist in the constraint and on the designer’s preferences. In this context, this paper puts forth three contributions. First, we develop a comprehensive classification of equality constraints in a way that is mutually exclusive and collectively exhaustive. Second, we present a rank-based matrix approach to interactively classify equality constraints, which systematically incorporates the designer’s preferences into the classification process. Third, we present an approach to incorporate the designer’s intra-constraint and inter-constraint preferences for designer-imposed constraints into the RDO formulation. Intra-constraint preference expresses how closely a designer wishes to satisfy a particular constraint; for example, in terms of its mean and standard deviation. A designer may express inter-constraint preference if satisfaction of a particular designer-imposed constraint is more important than that of another. We present an optimization formulation that incorporates the above discussed constraint preferences, which provides the designer with the means to explore design space possibilities. The formulation entails interesting implications in terms of decision making. Two engineering examples are provided to illustrate the practical usefulness of the developments proposed in this paper.     

一种并行工程约束分解方法

在并行工程产品开发过程中,往往按照问题的结构特点将较大规模的问题分解成一些子问题,并希望通过求解子问题来获得原问题的解。实际中,分解得到的子问题之间往往不是完全独立的,一般的简单分解方法只能有限地降低求解难度和简化问题规模。如何进一步分解各个子问题间的关系,使各个子问题的设计结果不但满足原问题的总体要求而且还能由此获得优化的总体设计结果是一个重要问题。该文给出了分解的意义,提出了基于约束的优化分解方法。     

Excessively duplicating patterns represent non-regular languages

A constrained term pattern s:φ$s:\phi$ represents the language of all instances of the term s satisfying the constraint φ. For each variable in s, this constraint specifies the language of its allowed substitutions. Regularity of languages represented by sets of patterns has been studied for a long time. This problem is known to be co-NP-complete when the constraints allow each variable to be replaced by any term over a fixed signature, and EXPTIME-complete when the constraints restrict each variable to a regular set. In both cases, duplication of variables in the terms of the patterns is a necessary condition for non-regularity. This is because duplications force the recognizer to test equality between subterms. Hence, for the specific classes of constraints mentioned above, if all patterns are linear, then the represented language is necessarily regular. In this paper we focus on the opposite case, that is when there are patterns with “excessively duplicating” variables. We prove that when each pattern of a non-empty set has a duplicated variable constrained to an infinite language, then the language represented by the set is necessarily non-regular. We prove this result independently of the kind of constraints used, just assuming that they are mappings from variables to arbitrary languages. Our result provides an efficient procedure for detecting, in some cases, non-regularity of images of regular languages under tree homomorphisms.     

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.     

Controller design with multiple objectives

In this paper we study multi-objective control problems that give rise to equivalent convex optimization problems. We develop a uniform treatment of such problems by showing their equivalence to linear programming problems with equality constraints and an appropriate positive cone. We present some specialized results on duality theory, and we apply them to the study of three multi-objective control problems: the optimal l₁ control with time-domain constraints on the response to some fixed input, the mixed H₂/l₁ -control problem, and the l₁ control with magnitude constraint on the frequency response. What makes these problems complicated is that they are often equivalent to infinite-dimensional optimization problems. The characterization of the duality relationship between the primal and dual problem allows us to derive several results. These results establish connections with special convex problems (linear programming or linear matrix inequality problems), uncover finite-dimensional structures in the optimal solution, when possible, and provide finite-dimensional approximations to any degree of accuracy when the problem does not appear to have a finite-dimensional structure. To illustrate the theory and highlight its potential, several numerical examples are presented     

Exact fuzzy optimal solution of fully fuzzy linear programming problems with unrestricted fuzzy variables

Kumar et al. (Appl. Math. Model. 35:817?C823, 2011) pointed out that there is no method in literature to find the exact fuzzy optimal solution of fully fuzzy linear programming (FFLP) problems and proposed a new method to find the fuzzy optimal solution of FFLP problems with equality constraints having non-negative fuzzy variables and unrestricted fuzzy coefficients. There may exist several FFLP problems with equality constraints in which no restriction can be applied on all or some of the fuzzy variables but due to the limitation of the existing method these types of problems can not be solved by using the existing method. In this paper a new method is proposed to find the exact fuzzy optimal solution of FFLP problems with equality constraints having non-negative fuzzy coefficients and unrestricted fuzzy variables. The proposed method can also be used to solve the FFLP problems with equality constraints having non-negative fuzzy variables and unrestricted fuzzy coefficients. To show the advantage of the proposed method over existing method the results of some FFLP problems with equality constraints, obtained by using the existing and proposed method, are compared. Also, to show the application of proposed method a real life problem is solved by using the proposed method.     

一种基于时间戳的简单表缩减算法

表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容（generalized arc consistency,简称GAC）是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction（STR）是一类高效的维持GAC的算法.在回溯搜索中,STR动态地删除无效元组,降低了查找支持的开销,并拥有单位时间的回溯代价,在高元表约束上获得了广泛运用,并有大量基于STR的改进算法被提出,其中,元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想,为STR提出一种检测并删除无效元组和为变量更新支持的算法,作用于原始表约束并拥有单位时间的回溯代价.实验结果表明,该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.     

A surrogate-assisted evolution strategy for constrained multi-objective optimization

In many real-world optimization problems, several conflicting objectives must be achieved and optimized simultaneously and the solutions are often required to satisfy certain restrictions or constraints. Moreover, in some applications, the numerical values of the objectives and constraints are obtained from computationally expensive simulations. Many multi-objective optimization algorithms for continuous optimization have been proposed in the literature and some have been incorporated or used in conjunction with expert and intelligent systems. However, relatively few of these multi-objective algorithms handle constraints, and even fewer, use surrogates to approximate the objective or constraint functions when these functions are computationally expensive. This paper proposes a surrogate-assisted evolution strategy (ES) that can be used for constrained multi-objective optimization of expensive black-box objective functions subject to expensive black-box inequality constraints. Such an algorithm can be incorporated into an intelligent system that finds approximate Pareto optimal solutions to simulation-based constrained multi-objective optimization problems in various applications including engineering design optimization, production management and manufacturing. The main idea in the proposed algorithm is to generate a large number of trial offspring in each generation and use the surrogates to predict the objective and constraint function values of these trial offspring. Then the algorithm performs an approximate non-dominated sort of the trial offspring based on the predicted objective and constraint function values, and then it selects the most promising offspring (those with the smallest predicted ranks from the non-dominated sort) to become the actual offspring for the current generation that will be evaluated using the expensive objective and constraint functions. The proposed method is implemented using cubic radial basis function (RBF) surrogate models to assist the ES. The resulting RBF-assisted ES is compared with the original ES and to NSGA-II on 20 test problems involving 2–15 decision variables, 2–5 objectives and up to 13 inequality constraints. These problems include well-known benchmark problems and application problems in manufacturing and robotics. The numerical results showed that the RBF-assisted ES generally outperformed the original ES and NSGA-II on the problems used when the computational budget is relatively limited. These results suggest that the proposed surrogate-assisted ES is promising for computationally expensive constrained multi-objective optimization.     

Relatively quantified constraint satisfaction

The constraint satisfaction problem (CSP) is a convenient framework for modelling search problems; the CSP involves deciding, given a set of constraints on variables, whether or not there is an assignment to the variables satisfying all of the constraints. This paper is concerned with the more general framework of quantified constraint satisfaction, in which variables can be quantified both universally and existentially. We study the relatively quantified constraint satisfaction problem (RQCSP), in which the values for each individual variable can be arbitrarily restricted. We give a complete complexity classification of the cases of the RQCSP where the types of constraints that may appear are specified by a constraint language.     

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.     

From an individual to a population: an analysis of the firsthitting time of population-based evolutionary algorithms

Almost all analyses of time complexity of evolutionary algorithms (EAs) have been conducted for (1 + 1) EAs only. Theoretical results on the average computation time of population-based EAs are few. However, the vast majority of applications of EAs use a population size that is greater than one. The use of population has been regarded as one of the key features of EAs. It is important to understand in depth what the real utility of population is in terms of the time complexity of EAs, when EAs are applied to combinatorial optimization problems. This paper compares (1 + 1) EAs and (N + N) EAs theoretically by deriving their first hitting time on the same problems. It is shown that a population can have a drastic impact on an EA's average computation time, changing an exponential time to a polynomial time (in the input size) in some cases. It is also shown that the first hitting probability can be improved by introducing a population. However, the results presented in this paper do not imply that population-based EAs will always be better than (1 + 1) EAs for all possible problems     

Constrained,mixed-integer and multi-objective optimisation of building designs by NSGA-II with fitness approximation

Reducing building energy demand is a crucial part of the global response to climate change, and evolutionary algorithms (EAs) coupled to building performance simulation (BPS) are an increasingly popular tool for this task. Further uptake of EAs in this industry is hindered by BPS being computationally intensive: optimisation runs taking days or longer are impractical in a time-competitive environment. Surrogate fitness models are a possible solution to this problem, but few approaches have been demonstrated for multi-objective, constrained or discrete problems, typical of the optimisation problems in building design. This paper presents a modified version of a surrogate based on radial basis function networks, combined with a deterministic scheme to deal with approximation error in the constraints by allowing some infeasible solutions in the population. Different combinations of these are integrated with Non-Dominated Sorting Genetic Algorithm II (NSGA-II) and applied to three instances of a typical building optimisation problem. The comparisons show that the surrogate and constraint handling combined offer improved run-time and final solution quality. The paper concludes with detailed investigations of the constraint handling and fitness landscape to explain differences in performance.     

Constraint Retraction in CLP(FD): Formal Framework and Performance Results

Constraint retraction can be described, in general, as the possibility of deleting a previously stated piece of information. This is obviously very convenient in many programming frameworks, especially in those that involve some level of interaction between the user and the system, or also in those concerning rescheduling or replanning. Nevertheless, constraint retraction is usually not provided in current constraint programming environments. This is mainly due to its high complexity and also to its non-monotonic nature, which would make most of such systems much more complex to reason with. In this paper we avoid these problems by considering a specific constraint programming framework, called clpFD, that is, constraint logic programming (CLP) over finite domain (FD) constraints. We propose an algorithm which deletes a constraint from a set of FD constraints, while maintaining partial arc-consistency, which is usual in this programming framework. What is crucial is that the retraction operation we propose is incremental, in that it follows the chain of dependencies among variables which are set by the nature of the FD constraints, and by doing so it updates only the part of the constraint set which is affected by the deletion. We also detail how constraint retraction can be incorporated in the FD constraint solver and we evaluate its behavior within the clpFD system. Experimental results on usual benchmarks, on classes of problems of increasing connectivity, and also on a real-life problem show that in almost all cases the use of our retraction algorithm provides great speed-up with respect to standard methods while not slowing down the clpFD system when no retraction is performed. This provides the system with an efficient way of retracting constraints while not changing its performance when the user does not want to use this new feature.     

A constraint-space conjugate gradient method for function minimization and optimal control problems†

First, an algorithm is presented for minimizing an algebraic function subject to general algebraic equality constraints. The algorithm is based formally on the conjugate gradient method for solving unconstrained minimization problems but has the property that each iterate satisfies the constraint conditions exactly. Next, an extension of the algorithm is given which makes it applicable to optimal control problems with terminal state constraints. The computational characteristics of the method are demonstrated with numerical examples.