Issue 
Int. J. Simul. Multisci. Des. Optim.
Volume 6, 2015



Article Number  A1  
Number of page(s)  13  
DOI  https://doi.org/10.1051/smdo/2015001  
Published online  29 April 2015 
Research Article
Modified Covariance Matrix Adaptation – Evolution Strategy algorithm for constrained optimization under uncertainty, application to rocket design
^{1}
IFMA, EA3867, Laboratoires de Mécanique et Ingénieries, Clermont Université, CP 104488, 63000
ClermontFerrand, France
^{2}
Onera – The French Aerospace Lab, BP 80100, 91123
Palaiseau Cedex, France
^{3}
CNES – Launchers Directorate, 52 rue Jacques Hillairet, 75612
Paris, France
^{*} email: mathieu.balesdent@onera.fr
Received:
9
October
2014
Accepted:
3
March
2015
The design of complex systems often induces a constrained optimization problem under uncertainty. An adaptation of CMAES(λ, μ) optimization algorithm is proposed in order to efficiently handle the constraints in the presence of noise. The update mechanisms of the parametrized distribution used to generate the candidate solutions are modified. The constraint handling method allows to reduce the semiprincipal axes of the probable research ellipsoid in the directions violating the constraints. The proposed approach is compared to existing approaches on three analytic optimization problems to highlight the efficiency and the robustness of the algorithm. The proposed method is used to design a two stage solid propulsion launch vehicle.
Key words: Evolutionary Strategy / Covariance Matrix Adaptation / CMAES / Uncertainty / Constrained optimization / Rocket design
© R. Chocat et al., Published by EDP Sciences, 2015
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1 Introduction
The design of complex systems, such as aerospace vehicles, can be expressed as a non linear constrained optimization problem solving. The determination of the optimal system architecture requires a global exploration of the design space involving repeated evaluations of computationally expensive black box functions used to model the different disciplines (e.g. in aerospace: structure, propulsion, aerodynamics). Moreover, in the early design phases, uncertainties arise due to lack of knowledge of the system characteristics and the environment (e.g. propellant combustion rate, wind gust) and to the use of low fidelity analyses (for instance analytic code instead of numerically costly finite element analysis). Therefore, the design of a complex system at the conceptual design phase entails a constrained optimization problem under uncertainty that can be formulated as:(1)
with:

z: the vector of design variables z ∈ ℝ^{n} (e.g. rocket diameter, propellant masses),

U: the vector of the uncertain variables U ∈ ℝ^{p} (e.g. wind gust during the rocket launch, material characteristics). In the paper, the probability theory is used to model uncertainty.

F: ℝ^{n} × ℝ^{p} → ℝ: the performance function (e.g. propulsive speed increment ΔV, Gross LiftOff Weight),

Ξ: a measure of uncertainty for the performance function F (e.g. the expected value, a linear combination of expected value and standard deviation),

g: the vector of the inequality constraint functions, g_{i}, i ∈ {1, …, m} (e.g. maximal allowed stress in the structures, maximal tolerance on orbit injection accuracy),

K: a vector of measures of uncertainty for the inequality constraint functions (e.g. linear combination of expected value and standard deviation, probability of failure),

z_{min} and z_{max} the lower and upper bounds for the design variables.
Being able to handle uncertainty at early design phases is essential to efficiently characterize the optimal system design and its performances. It can reduce time and cost of the next design phases by avoiding redesign process [18]. However, solving the optimization problem (Eqs. (1)–(3)) is challenging due to the presence of both the uncertainty and inequality constraints. A brief overview of the existing methods to handle uncertainty and inequality constraints is provided in the next paragraphs.
The presence of noise in the optimization problem (Eqs. (1)–(3)) results from the estimation of the measures of uncertainty (Ξ and K). Several methods exist to compute these measures and the most classical approach is a numerical approximation by the Crude Monte Carlo (CMC) method. The CMC estimator of the uncertainty measure is also a random variable. In order to numerically handle the presence of noise in optimization, several approaches have been proposed:

Resampling [3]: the resampling method consists of repeated evaluations of the objective and the constraint uncertainty measures for the same design variable value z. Then, a statistics of the repeated samples is used instead of the single evaluation of the objective and the constraint measures to decrease the impact of noise. The main drawback of this approach is the increase of the computational cost due to the repeated evaluations of expensive functions.

Surrogate model [3]: surrogate models of the objective function measure Ξ (and/or the constraint measures K) are built from the evaluated measures. In general, surrogates smooth the noisy functions and decrease the impact of uncertainty in the optimization. The main drawback lies in the difficulty to build accurate surrogate models in high dimensions.

Population based algorithms [10]: to address uncertainty, optimization algorithms relying on a population of candidates allow to increase the size of the population to enlarge its spread and to obtain more information and smooth the noise.
Moreover, the presence of uncertainty makes the use of classical optimization algorithms, such as gradient based optimization algorithms, not suited for optimization. Indeed, the gradients of the objective uncertainty measure or the constraint uncertainty measures are noisy resulting in possible erroneous descent directions. Diverse derivativefree algorithms have been proposed in the literature to solve optimization under uncertainty problems [15]. Among these, the population based optimization algorithms seem promising [6]. Swarm Intelligence (Particle Swarm Optimization [7], Artificial Bee Colonies [13], etc.), Differential Evolution [17], Evolutionary Algorithms (Genetic Algorithm [12]) or Evolution Strategies (Covariance Matrix Adaptation – Evolution Strategy [10]) have been investigated to solve noisy optimization problems. One of the current issue with the derivativefree algorithms is the constraint handling which relies mainly on heuristic approaches and is problem dependent [16]. A comprehensive overview of constraint handling in derivativefree algorithms is presented in the survey [16]. The most commonly applied methods to handle the constraints are:

Death penalty [19]: it is the simplest method to handle constraints. The solution that does not satisfy the constraints is rejected and another potential solution is reevaluated until one candidate solution satisfies the constraints. The advantage of the approach is that it does not modify the optimization algorithm but the method is very expensive because no information is learned from an unfeasible solution (a solution which does not satisfy the constraints) to characterize the non feasible space. Furthermore, if the feasible space is restricted compared to the design space, the computational cost becomes prohibitive because a high number of samples has to be generated to obtain feasible solutions.

Penalization [5, 6]: this approach consists in replacing the objective function Ξ [F(z, U)] by a combination of the objective function and a penalization function Π such as: Ξ [F(z, U)] + Π (K[g(z, U)]). The penalization function can be fixed or can change as a function of the number of iterations. When a solution violates the constraints, the objective function is deteriorated by a factor proportional to the penalization function and the value of the constraints. Despite its simplicity, the main drawback of this approach lies in the determination of a suitable penalization function which depends on the objective function and the constraints and is thus problem dependent.

Multiobjective [4]: this method transforms the optimization problem into a multiobjective optimization problem by considering the minimization of the violation of the constraints as an objective. Dedicated multiobjective optimization algorithms can be used, however, it often results in an increase of the computational cost [16].

Surrogate model [14]: this approach builds a surrogate model based on the unfeasible solutions in order to approximate the non feasible zones. However, this approach requires enough unfeasible solutions to construct accurate surrogate models. Moreover, it can be difficult to build the surrogates in high dimension or if the constraints are highly non linear.
Among the derivativefree algorithms, the Covariance Matrix Adaptation – Evolution Strategy (CMAES) [10] is particularly competitive for realvalued black box functions as highlighted in several extensive benchmarks [8, 9]. Moreover, a treatment of uncertainty has been proposed for CMAES and has been successfully tested in a benchmark of optimization under uncertainty problems [8]. However, the test problems used to evaluate the performances of CMAES are unconstrained optimization problems and only few studies focus on the application of CMAES to constrained optimization problems [2, 6]. An adaptive penalty function has been proposed to update the penalty coefficient as a function of the sum of the violated constraint values [6]. Arnold and Hansen [1] proposed a new approach to handle the constraints for a simplified version of CMAES: (1+1)CMAES which involves one offspring candidate generated from one parent. Modified (1+1)CMAES approximates the normal vector directions of the constraint boundaries in the vicinity of the current candidate solution. A control of the covariance of the distribution of the offspring candidate allows to get closer to the boundary of the feasible regions without violating them. The approach provides interesting results but is limited to (1+1)CMAES which becomes inefficient in high dimensions (local convergence, large number of calls to the functions) [1].
The main objective of this paper is to adapt CMAES(λ, μ), which involves λ offspring candidates generated from μ parents, to efficiently solve constrained optimization problem under uncertainty. The proposed approach is based on a control of the covariance of the distribution of the offspring candidates through a modification of the covariance matrix that characterizes the probable research hypervolume in order to generate candidates without violating the constraints. The proposed adaptations take into account the specificities of the update and the selection mechanisms of CMAES(λ, μ) that differ from (1+1)CMAES due to the presence of a population instead of a single candidate. The remainder of the paper is organized as follows. Section 2 provides an overview of the original CMAES(λ, μ) and the adapted (1+1)CMAES to handle constraints. Section 3 presents the modifications of CMAES(λ, μ) to handle constraints in optimization problems. Section 4 evaluates the algorithm efficiency on three analytic test functions and on the design of a two stage solid rocket. A comparison with penalized CMAES(λ, μ) and modified (1+1)CMAES is provided.
2 Description of CMAES(λ, μ) and modified (1+1)CMAES
2.1 CMAES(λ, μ) algorithm
The Covariance Matrix Adaptation – Evolution Strategy (CMAES) introduced by Hansen et al. [10] belongs to the Evolution Strategy algorithm family. A brief overview of CMAES(λ, μ) is provided in the section in order to understand the proposed modifications for the constraint handling, for more information on the algorithm see [10]. CMAES(λ, μ) is used to solve unconstrained optimization problems. CMAES relies on a distribution model of a candidate population (parametrized multivariate normal distribution) in order to explore the design space. It is based on a selection and an adaptation process of the candidate population. In CMAES(λ, μ), at each generation, λ offspring candidates are generated from μ parents. At the next generation, to select the new parents from the offspring candidates, a (λ, μ)selection is used, the μ best offspring candidates are chosen (with respect to their ranking according to the objective function). The multivariate normal distribution has an infinite support, but an isoprobability contour (for instance at ±3 standard deviation of the mean) is characterized by an ellipsoid delimiting a probable research hypervolume (Figure 1). Throughout the generations, the research hypervolume is updated in order to converge and to shrink around the global optimum. CMAES(λ, μ) generates the population by sampling a multivariate normal distribution:(4)with an offspring candidate generated from a mean vector m^{(k)}, a step size σ^{(k)} and a multivariate normal distribution with zero mean and a covariance matrix C^{(k)} ∈ ℝ^{n} × ℝ^{n}. λ is the size of the population generated at each iteration (k). The normal distribution is characterized by a positive definite covariance matrix C^{(k)} in order to allow homothetic transformations and rotations of the probable research hypervolume (Figure 1). The update of the covariance matrix incorporates dependence between the past generations and between the μ best candidates from the previous generation [10]. The mean vector characterizes the center of the next population and is determined by a combination process through the weighting of the μ best candidates: with , w_{1} > w_{2} > ⋯ > w_{μ} > 0 the weighting coefficients and the best candidates among the offspring ranked according to the fitness value. The weighting coefficients are determined based on the number of μ best candidates according to [10]. A simplified version of CMAES(λ, μ) is described in Algorithm 1. A detailed description of the selection and update mechanisms can be found in [10].
Figure 1. Three ellipsoids, depicting three different normal distributions, where I is the identity matrix, D is a diagonal matrix, and C is a positive definite covariance matrix. Thin dot lines depict objective function contour lines. 
Algorithm 1 CMAES(λ, μ) [10]
1) Initialize the covariance matrix C^{(0)} = I, the step size σ^{(0)} and the selection parameters [10]
2) Initialize the mean vector m^{(0)} to a random candidate, k ← 0
while CMAES convergence criteria are not reached do
31) Generate λ new offspring candidates according to:
32) Evaluate candidates and rank them based on the objective function
33) Determine the mean vector given the weighting coefficients of the μ best candidates:
34) Update covariance matrix C^{(k+1)} and the step size σ^{(k+1)} according to [10], k ← k + 1
end while
4) return best candidate z_{best}
The convergence criteria can either be based on the maximum number of iterations (function evaluations), the fitness value, the standard deviation of the current population smaller than a given tolerance, or the covariance matrix C which becomes numerically not positive definite. In the next paragraph, an adaptation of CMAES for uncertainty handling is described.
2.2 CMAES(λ, μ) algorithm for optimization under uncertainty
Several features ensure the CMAES robustness with respect to the presence of uncertainty in the objective function: the populationbased approach, the weighted averaging in the recombination process, the rank based and the nonelitist selection (not based on the best offspring candidate). However, if the noise is too high compared to the objective function (signal to noise ratio too low) it perturbs the algorithm convergence. An appropriate handling of uncertainty has been proposed by Hansen et al. [11] to overcome this issue. Modified selection and update mechanisms are performed when the noise is above a given threshold. It is based on a resampling approach and involves reevaluation of the objective function. Because CMAES(λ, μ) is only based on the rank of the candidates, the effective noise is evaluated by monitoring changes or stability of the offspring candidate ranking. If the offspring candidate ranking is changed after the reevaluation of the objective function, the ranking change of the offspring candidates is aggregated into a metric quantifying the uncertainty level [11]. If the noise is higher than a given uncertainty level threshold, the step size σ is increased. The increase of σ ensures that despite the noise, sufficient selection information is available [11].
A benchmark of algorithm dealing with optimization under uncertainty has been performed and the treatment of uncertainty with CMAES(λ, μ) allows to obtain accurate results [8]. However, CMAES(λ, μ) is not able to efficiently handle the constraints. Indeed, only penalization [5, 6] or surrogate based methods [14] have been proposed. These approaches can be effective but are problem dependent and require accurate tuning of hyper parameters. A simplified version of CMAES(λ, μ) called (1+1)CMAES has been adapted to handle constraints and is detailed in the next section.
2.3 (1+1)CMAES with constraint handling
(1+1)CMAES is a simplified version [1] of CMAES(λ, μ) with only one offspring generated from one parent, “+” means that the selection is done between the parent and the offspring. As in CMAES(λ, μ), the offspring candidate solution is generated as:(5)(1+1)CMAES is easier to implement as only one offspring z^{(k + 1)} is generated from one parent z^{(k)} at each generation and the selection is between the parent and the offspring. The update mechanisms for (1+1)CMAES are detailed in [1].
To incorporate the handling of constraints, Arnold and Hansen [1] proposed to reduce the covariance of the distribution of the offspring candidate in the approximated directions of the normal vectors of the constraint boundaries in the vicinity of the current parent candidate solution. For that purpose, the matrix A^{(k)}, which is the Cholesky decomposition of , is updated in case of constraint violations in order to avoid generating candidates in the next generations that will violate the constraints. A^{(k)} is used as it is easier to compute its inverse than for C^{(k)}. A vector characterizing the constraints is defined, initialized to be zero, and updated according to:(6)where is an exponentially fading record of steps that have violated the constraints and c_{c} a parameter characterizing how fast the information present in fades. In the generations in which the offspring candidate is unfeasible, the Cholesky matrix is updated according to:(7)with , the indicator function associated to the constraint and β a parameter controlling the reduction of the covariance of the distribution. For β = 0, the algorithm is identical to the standard (1+1)CMAES. The update of the matrix A^{(k)} allows to modify the scale and the orientation of the research hypervolume in order to be tangential to the constraints and to avoid its violation (Figure 2). Modified (1+1)CMAES for constraint handling is interesting because it is not problem dependent. Experimental evaluations have been performed highlighting its efficiency for unimodal constrained optimization problems. However, as (1+1)CMAES, it is not able to optimize multimodal functions and becomes inefficient in high dimensions [1].
Figure 2. The dot is the parent, the cross is the generated offspring, the solid line circle is characterized by A^{(k)} defining the ellipsoid delimiting an isoprobability research hypervolume. At the center, the red ellipsoid represents the update of A^{(k+1)} in order to take into account the constraint violation by the offspring. On the right figure, the offspring does not violate the constraint resulting in a standard covariance matrix update. 
To overcome these drawbacks, in the next section, an adaptation of CMAES(λ, μ) for constraint handling is proposed inspired from the (1+1)CMAES approach.
3 Proposed adaptation of CMAES(λ, μ) for constraint handling
The proposed approach of CMAES(λ, μ) for constraint handling is based on the same approach as modified (1+1)CMAES. However, it is necessary to adapt it to take into account the specificities of CMAES(λ, μ). Indeed, CMAES(λ, μ) generates a population instead of a single offspring candidate. Thus, each offspring candidate can potentially violate one or several constraints. Moreover, the selection of the μ best candidates is based on the rank of the objective function. However, these best candidates can also violate the constraints. Depending if the μ best candidates are feasible or not, or if only a fraction of them is feasible, or on the number of violated constraints, the covariance matrix used to generate the offspring candidates has to be modified in order to avoid the generation of unfeasible offspring candidates. The research hypervolume engendered by an isoprobability contour of the multivariate normal distribution can be represented by a ndimensional ellipsoid. In the proposed approach, the constraint handling method allows to reduce the semiprincipal axes of the research ellipsoid in the directions violating the constraints. The eigenvalues of the covariance matrix C control the length of the semiprincipal axes. The decrease of the eigenvalues reduces the semiprincipal axis lengths. The covariance matrix, which is symmetric positive definite, can be decomposed according to:(8)where P is an orthogonal matrix such that: PP^{T} = P^{T}P = I. The columns of P form an orthogonal basis of eigenvectors of C. is a diagonal matrix with the square roots of eigenvalues of C. As illustrated in Figure 3, the square roots of the covariance matrix eigenvalues are proportional to the semiprincipal axis lengths of the ellipsoid defining the sampling hypervolume.
Figure 3. Parametrization of the ellipsoid defining the probable research hypervolume. 
At the generation (k), between the step 33) and 34) of Algorithm 1, if any of the m constraints is violated by any of the μ best offspring candidates, the covariance matrix is modified according to Algorithm 2.
Algorithm 2 Proposed CMAES(λ, μ) covariance matrix modificiation(9)
The covariance matrix is diagonalized, equation (9) and the eigenvalues of the covariance matrix C^{(k)} are modified. The new eigenvalues are the former eigenvalues minus a term taking into account the violation of the constraints. , equation (12), is a function of the former eigenvalues , of the indicator function of the constraint , of the weighting coefficients w_{ij} and of the projection of the distance between an ordered candidate violating the constraints and the mean point m^{(k)} in the direction of the eigenvector corresponding to the eigenvalue . γ is a parameter similar to β in (1+1)CMAES. For γ = 0 the proposed algorithm is similar to the classical CMAES(λ, μ). For each constraint g_{j}, the μ_{cj} candidates among the μ best candidates that violate the constraint are ranked according to the constraint value. The weighting coefficients w_{ij} for each constraint g_{j} are defined according to the same rule as for the recombination process for the calculation of m^{(k)}:(13)and where: w_{1j} ≥ ⋯ ≥w_{μj} ≥ 0. w_{1j} is associated to the candidate that violates the most the constraint g_{j} and with the candidate that violates the less the constraint. For the candidates among the μ best that do not violate the constraint, the indicator function is equal to zero and therefore these candidates do not participate in the modification of the covariance matrix. The projection of the violation distance along the eigenvector (Figure 4) allows to reduce the covariance matrix in the direction orthogonal to the constraint violation.
Figure 4. Violation of the constraint and projection over the eigenvectors, blue = feasible, red = unfeasible candidates. 
Equation (11) allows to keep the hypervolume of the ellipsoid constant before and after the modification of the covariance matrix in order to avoid premature convergence. The volume of the ellipsoid is reduced in the direction orthogonal to the constraints but is increased in the direction tangential to the constraints (Figure 5). The modified CMAES(λ, μ) algorithm for constraint handling is detailed in Algorithm 3.
Figure 5. Evolution of the covariance matrix due to the constraint violation, blue = feasible, red = unfeasible candidates. 
Algorithm 3 Proposed modified CMAES(λ, μ) for constraint handling
1) Initialize the covariance matrix C^{(0)} = I, the step size σ^{(0)} and the selection parameters [10]
2) Initialize the mean vector m^{(0)} to a random candidate, k ← 0
while CMAES convergence criterion is not reached do
31) Generate λ new offspring candidates according to:
32) Evaluate candidates and sort them based on the objective function
if all the μ best candidates are infeasible then
Modify the covariance matrix according to Algorithm 2. Return to step 3.1)
else
If all the μ best candidates are feasible
Determine the mean vector given the weightings of the μ best candidates:
Update covariance matrix C^{(k + 1)} according to [10] end if
else
If at least one of the μ best candidates is infeasible and at least one is feasible
Modify the covariance matrix according to Algorithm 2.
Use the feasible candidates to determine the mean vector m^{(k + 1)}
Use the feasible candidates to update covariance matrix C^{(k + 1)} according to [10] end if
end if
33) Update the step size σ^{(k + 1)} according to [10], k ← k + 1
end while
4) return best candidate
The evolution of the ellipsoid between the generations (k) and (k + 1) if one of the μ best candidates violates a constraint is illustrated in Figure 5. The modification of C^{(k)} allows homothetic transformations in order to avoid to generate candidates in the non feasible zone.
If the mean vector m^{(k)} after the combination process is not feasible, instead of reducing the covariance matrix, the ellipsoid hypervolume is increased in order to generate candidates in the feasible zone. Therefore, the ellipsoid hypervolume is increased according to:(14)
The mean vector is displaced to the best feasible candidate generated at the next generation (Figure 6).
Figure 6. Modification of the covariance matrix due to the mean vector constraint violation, blue = feasible, red = unfeasible candidates. 
The modified CMAES(λ, μ) allows to take into account the constraints without degrading the objective function by penalization and avoids to tune the penalization parameters. Moreover, the proposed algorithm relies on the same update and selection mechanisms of the original CMAES(λ, μ) adapted for constraint handling and it keeps the invariance and unbiased design principles of CMAES(λ, μ) [10]. In the next sections, the proposed algorithm is tested on a benchmark of analytic functions and on the design of a two stage rocket in order to evaluate its performances.
4 Benchmark on analytic optimization problems
The proposed modified CMAES(λ, μ) is tested and compared to a penalized version of CMAES(λ, μ) with a constant penalization function, to the death penalty applied to CMAES(λ, μ) and to the modified (1+1)CMAES on a benchmark of three analytic functions. The benchmark consists of a modified Six Hump Camel problem in 2 dimensions, the G04 optimization problem [8] in 5 dimensions and a modified Rosenbrock problem in 20 dimensions. These optimization problems are used in order to evaluate the proposed algorithm for different design space dimensions and different types of and numbers of inequality constraints (linear, non linear). In the following, the benchmark problems are introduced with the results. A discussion and a synthesis of the results for all the tests are provided in Section 4.4.
In the three problem formulations, the expected value is computed by Crude Monte Carlo method (CMC). A sample of 1000 points is used to estimate the expected value of the objective function. For each method (Modified CMAES(λ, μ), Death Penalty CMAES(λ, μ), Penalization CMAES(λ, μ), Modified (1+1)CMAES) the optimization is repeated 50 times. The initialization is chosen randomly in the design space and the same initialization and the same random number seed are used for the four optimization algorithms. The same stopping criterion is used for all the algorithms: the distance in the design space between the mean vector and the best point found  m^{(k)} − z_{best} ^{2} < 10^{−3} must be lower than a tolerance 20 times in a row.
4.1 Modified Six Hump Camel problem
A modified version of the Six Hump Camel problem is used in order to introduce uncertainty and three inequality constraints. The formulation of the problem is the following:(15)
(19)with z ∈ [−3, 3] × [−2, 2], and U a random variable distributed according to a normal distribution .
Representations of the function and the constraints are provided in Figure 7. The problem has one local optimum and one global optimum. The results are presented in Table 1 and the convergence curves for one optimization are given in Figure 8.
Figure 7. Modified Six Hump Camel function and constraints. 
Figure 8. Convergence curves of the Six Hump Camel problem in 2 dimensions, based on one optimization run. 
Results of modified Six Hump Camel problem. Average over 50 optimizations (in parenthesis the Relative Standard Deviation (RSD) – ).
4.2 G04 optimization problem [8]
The G04 optimization problem involves 6 inequality constraints and is defined as following:(20)
(27)with z ∈ ℝ^{5}, z_{min} = [78, 33, 27, 27, 27], z_{max} = [102, 45, 45, 45, 45] and:(28)
The results are presented in Table 2 and the convergence curves for one optimization are given in Figure 9.
Figure 9. Convergence curves of the G04 optimization problem, based on one optimization run. 
Results of G04 optimization problem. Average over 50 optimizations (in parenthesis the RSD – ).
4.3 Modified Rosenbrock problem
The Rosenbrock optimization problem has been modified in order to incorporate uncertainty and an inequality constraint (Figure 10). The problem is formulated as following:(31)
(32)with n = 20, z ∈ ℝ^{20} and U a random variable distributed according to a uniform distribution.
Figure 10. Modified Rosenbrock function and the constraints in 2 dimensions. 
The results are presented in Table 3 and the convergence curves for one optimization are given in Figure 11.
Figure 11. Convergence curves of the modified Rosenbrock problem in 20 dimensions, based on one optimization run. 
Results of constrained Rosenbrock problem. Average over 50 optimizations (in parenthesis the RSD – ).
4.4 Result and synthesis
The analytic test cases involve different dimensions (2, 5 and 20) and different number of constraints (1, 3 and 6) in order to evaluate the efficiency of the proposed modified CMAES(λ, μ) on various optimization problems. A qualitative synthesis of the obtained results is given in Figure 12. For all the three criteria (number of evaluations, robustness to initialization and value of the optimum), the lower value the better the quality of the method for the given criterion.
Figure 12. Qualitative results obtained for the different test cases. 
The Six Hump Camel problem has one local optimum and one global optimum. All the optimization algorithms converge either to the local or the global optimum. It illustrates the robustness property of the algorithms with respect to the initialization (relative standard deviation ~0.85% for all the algorithms). The found optima are all feasible. Modified (1+1)CMAES converges in 48% of the optimization runs to the global optimum and the proposed modified CMAES (λ, μ) in 37% of the cases. The penalization and the death penality approaches converge only in 33% and 22% of the optimization runs to the global optimum. The number of calls to the objective function and the constraints is in increasing order: Modified (1+1)CMAES (781), modified CMAES(λ, μ) (1211), Death Penalty CMAES(λ, μ) (1395) and Penalization CMAES(λ, μ) (1618). Modified (1+1)CMAES is more efficient in this test case due to the low dimension and the simplicity of the optimization problem. The proposed modified CMAES(λ, μ) provides better results than the penalization and the death penalty approaches.
In the G04 problem, only the proposed modified CMAES(λ, μ) and the modified (1+1)CMAES converge to the global minimum (with sufficient robustness with respect to the initialization). The number of calls to the objective function and the constraints is lower in the proposed algorithm (1618) compared to modified (1+1)CMAES (7048) and the relative standard deviation is lower in the proposed approach. Moreover, the proposed approach converges efficiently to the global optimum. The Death Penalty and the penalization approaches do not succeed to reach the global optimum and are not robust to the initialization.
In the modified Rosenbrock problem, only the proposed modified CMAES(λ, μ) reaches the global optimum (with sufficient robustness (RSD: 0.12%) to the initialization). All the other algorithms are not robust to the initialization and do not converge to the global optimum. The number of calls to the objective function and the constraints is larger for the proposed approach (12 798) compared the other algorithms.
Consequently, from the benchmark, in small dimensions (<8), the modified (1+1)CMAES provides good results in terms of convergence to the global optimum and robustness with respect to the initialization, however, as expected, in large dimensions, it presents issues to converge to the global optimum. The proposed modified CMAES(λ, μ) succeeds in small and large dimensions to find the global optimum. Moreover, this algorithm appears as robust to the initialization. In the next section, the proposed algorithm is used to design a two stage solid rocket and is compared to the existing CMAES based optimization algorithms.
5 Two stage solid propulsion rocket design
A multidisciplinary design problem consisting in maximizing the propulsive speed increment ΔV provided by a two stage rocket under geometrical and physical feasibility constraints is solved. The conceptual design models use simplified analysis of a two stage cylindrical solid propellant rocket motor. The multidisciplinary analysis involves four disciplines: the propulsion, the mass and sizing, the structure and the performance and constraint assessment (Figure 13). At the early design phase, model uncertainties exist and are taken into account. Two uncertainties are considered: the density of the propellant ρ and the ultimate strength σ for the rocket case material (Figure 14).
Figure 13. Design Structure Matrix for the two stage solid rocket. 
Figure 14. Convergence curves of the propulsive speed increment for the two stage solid propulsion rocket. 
The problem is formulated as follows:(33)
(37)with: U = [U_{1}, U_{2}] with the uncertainty of the density of the propellant (ρ) and the uncertainty of the ultimate strength limit (σ) for the rocket case material. The design variables are described in Table 4. An overview of the disciplines is detailed in the next paragraphs.
Design variables for the twostage rocket.
Propulsion. The propulsion discipline computes for a given set of propellant characteristics (density ρ, combustion speed, flame temperature, heat capacity ratio), the thrust T, the mass flow rate , the thrust coefficient c_{T} and the characteristic velocity c*, under the assumption of constant thrust. The discipline takes nozzle shapes Dt, D_{s} and combustion pressure P_{c} as inputs. The used propellant is the Butargols with polybutadiene binder without aluminium additive.
Mass and Sizing. The mass and sizing discipline computes the dry mass m_{d} and the geometry of the two stage solid propulsion rocket. The dry mass involves the mass of the rocket case and the mass of the nozzle and the pyrotechnic igniter. The rocket geometry consists of the initial combustion area, the packaging ratio and the size of the central channel. The overall dimensions (rocket length L = 22 m and diameter D = 1.07 m) are considered as fixed.
Structure. The structure discipline computes the tank walls thickness (t) which is sized under the combustion pressure based on the material characteristics (yield strength, ultimate strength limit) and rocket geometry. Moreover, it computes the stress in the rocket case.
Performance and constraints. The performance is the propulsive speed increment ΔV and the expected value of ΔV is the objective function to be maximized. CMC based on 1000 samples is used to compute the expected value of the propulsive speed increment. The three constraints are: g_{1}(.) which ensures packaging ratio (Propellant volume/Available volume) that has to be inferior to 87%, g_{2}(.) which ensures that central channel diameter is 30% greater than the nozzle throat diameter and g_{3}(.) which ensures that combustion area is greater than the minimum feasible (area of central channel walls). The probabilities of failure for the three constraints have to be inferior to 1%. The probabilities of failure are computed with a CMC of 10^{4} samples, numerically corresponding to a relative standard error () of the probability estimation in the order of 5%.
5.1 Results
The optimization for each algorithm is repeated 10 times. All the optimizations start from the same baseline given in Table 4. The same stopping criterion is used for all the optimization algorithms: the distance in the design space between the mean vector and the best point found  m^{(k)} − z_{best} ‖ < 10^{−3} must be under a tolerance 20 times in a row. The algorithms do not converge to the same optimum. Modified CMAES (λ, μ) provides a better optimum in terms of propulsive speed increment: 6234.1 m/s with a better robustness. The proposed algorithm converges on the average in 1127 discipline evaluations. The other optimization algorithms converge in the same order of number of discipline evaluations (~1750). Only four constraints are active at the optimum. The better optimum found by the proposed approach is essential as it has a better propulsive speed increment which could be used to increase the payload mass (Table 5).
Results of the two stage rocket optimization. Average over 10 optimizations (in parenthesis the RSD – ).
6 Conclusion
The design of complex systems often induces a constrained optimization problem under uncertainty. In this paper, an adaptation of CMAES(λ, μ) has been proposed in order to efficiently handle the constraints. The probable research hypervolume engendered by an isoprobability contour of the multivariate normal distribution used to generate the candidate population is modified. The constraint handling method allows to reduce the semiprincipal axes of the isoprobable research ellipsoid in the directions violating the constraints by decreasing the eigenvalues of the covariance matrix C. The proposed approach has been tested with three analytic optimization problems highlighting the efficiency of the algorithm and the robustness with respect to the initialization. The proposed method has been used to design a two stage solid propulsion launch vehicle. A better optimum has been found with the proposed approach with respect to the existing CMAES based optimization algorithms resulting in a potential increase in the payload mass.
Acknowledgments
The work of L. Brevault is part of a CNES/ONERA PhD thesis.
References
 Arnold DV, Hansen N. 2012. A (1+1)CMAES for constrained optimisation, in Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference, New York, NY, USA, p. 297–304, ACM. [Google Scholar]
 Beyer HG, Finck S. 2012. On the design of constraint Covariance Matrix SelfAdaptation Evolution Strategies including a cardinality constraint. IEEE Transactions on Evolutionary Computation, 16(4), 578–596. [CrossRef] [Google Scholar]
 Branke J, Schmidt C. 2003. Selection in the presence of noise, in Genetic and Evolutionary Computation Conference, Chicago, IL, USA. [Google Scholar]
 Coello Coello CA. 2000. Constrainthandling using an evolutionary multiobjective optimization technique. Civil Engineering Systems, 17(4), 319–346. [CrossRef] [Google Scholar]
 Collange G, Reynaud S, Hansen N. 2010. Covariance Matrix Adaptation Evolution Strategy for multidisciplinary optimization of expendable launcher family, in 13th AIAA/ISSMO Multidisciplinary Analysis Optimization Conference, FortWorth, TX. [Google Scholar]
 De Melo VV, Iacca G. 2014. A modified Covariance Matrix Adaptation Evolution Strategy with adaptive penalty function and restart for constrained optimization. Expert Systems with Applications, 41(16), 7077–7094. [CrossRef] [Google Scholar]
 Eberhart RC, Kennedy J. 1995. A new optimizer using particle swarm theory. Proceedings of the sixth international symposium on micro machine and human science, New York, NY, p. 39–43. [Google Scholar]
 Hansen N. 2009. Benchmarking a BIpopulation CMAES on the BBOB2009 noisy testbed, in Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, Montreal, Qubec, Canada, p. 2397–2402, ACM. [Google Scholar]
 Hansen N, Auger A, Ros R, Finck S, Pošík P. 2010. Comparing results of 31 algorithms from the blackbox optimization benchmarking BBOB2009, in Proceedings of the 12th annual conference companion on Genetic and evolutionary computation, p. 1689–1696, ACM. [Google Scholar]
 Hansen N, Müller S, Koumoutsakos P. 2003. Reducing the time complexity of the derandomized Evolution Strategy with Covariance Matrix Adaptation (CMAES). Evolutionary Computation, 11(1), 1–18. [NASA ADS] [CrossRef] [Google Scholar]
 Hansen N, Niederberger AS, Guzzella L, Koumoutsakos P. 2009. A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion. IEEE Transactions on Evolutionary Computation, 13(1), 180–197. [CrossRef] [Google Scholar]
 Holland JH. 1975. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan, USA. [Google Scholar]
 Karaboga D. 2005. An idea based on honey bee swarm for numerical optimization, Technical report, Technical reporttr06, Erciyes University, engineering faculty, computer engineering department. [Google Scholar]
 Kramer O, Barthelmes A, Rudolph G. 2009. Surrogate constraint functions for CMA Evolution Strategies, in KI 2009: Advances in Artificial Intelligence, Springer, Verlag Berlin Heidelberg, p. 169–176. [CrossRef] [Google Scholar]
 Larson JM. 2012. Derivative free optimization of noisy functions. PhD thesis, University of Colorado. [Google Scholar]
 MezuraMontes E, Coello Coello CA. 2011. Constrainthandling in natureinspired numerical optimization: past, present and future. Swarm and Evolutionary Computation, 1(4), 173–194. [CrossRef] [Google Scholar]
 Price K, Storn RM, Lampinen JA. 2006. Differential evolution: a practical approach to global optimization, Springer, Verlag Berlin Heidelberg. [Google Scholar]
 Rowell LF, Korte JJ. 2003. Launch vehicle design and optimization methods and priority for the advanced engineering environment. NASA Technical Report NASA/TM2003, 212654. [Google Scholar]
 Schwefel HP, Rudolph G. 1995. Contemporary evolution strategies, Springer, Verlag Berlin Heidelberg. [Google Scholar]
Cite this article as: Chocat R, Brevault L, Balesdent M & Defoort S: Modified Covariance Matrix Adaptation – Evolution Strategy algorithm for constrained optimization under uncertainty, application to rocket design. Int. J. Simul. Multisci. Des. Optim., 2015, 6, A1.
All Tables
Results of modified Six Hump Camel problem. Average over 50 optimizations (in parenthesis the Relative Standard Deviation (RSD) – ).
Results of G04 optimization problem. Average over 50 optimizations (in parenthesis the RSD – ).
Results of constrained Rosenbrock problem. Average over 50 optimizations (in parenthesis the RSD – ).
Results of the two stage rocket optimization. Average over 10 optimizations (in parenthesis the RSD – ).
All Figures
Figure 1. Three ellipsoids, depicting three different normal distributions, where I is the identity matrix, D is a diagonal matrix, and C is a positive definite covariance matrix. Thin dot lines depict objective function contour lines. 

In the text 
Figure 2. The dot is the parent, the cross is the generated offspring, the solid line circle is characterized by A^{(k)} defining the ellipsoid delimiting an isoprobability research hypervolume. At the center, the red ellipsoid represents the update of A^{(k+1)} in order to take into account the constraint violation by the offspring. On the right figure, the offspring does not violate the constraint resulting in a standard covariance matrix update. 

In the text 
Figure 3. Parametrization of the ellipsoid defining the probable research hypervolume. 

In the text 
Figure 4. Violation of the constraint and projection over the eigenvectors, blue = feasible, red = unfeasible candidates. 

In the text 
Figure 5. Evolution of the covariance matrix due to the constraint violation, blue = feasible, red = unfeasible candidates. 

In the text 
Figure 6. Modification of the covariance matrix due to the mean vector constraint violation, blue = feasible, red = unfeasible candidates. 

In the text 
Figure 7. Modified Six Hump Camel function and constraints. 

In the text 
Figure 8. Convergence curves of the Six Hump Camel problem in 2 dimensions, based on one optimization run. 

In the text 
Figure 9. Convergence curves of the G04 optimization problem, based on one optimization run. 

In the text 
Figure 10. Modified Rosenbrock function and the constraints in 2 dimensions. 

In the text 
Figure 11. Convergence curves of the modified Rosenbrock problem in 20 dimensions, based on one optimization run. 

In the text 
Figure 12. Qualitative results obtained for the different test cases. 

In the text 
Figure 13. Design Structure Matrix for the two stage solid rocket. 

In the text 
Figure 14. Convergence curves of the propulsive speed increment for the two stage solid propulsion rocket. 

In the text 
Current usage metrics show cumulative count of Article Views (fulltext article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.