Self-adaptation of the representation of a real-world design in an iterative optimization

The present invention relates to an iterative optimization method, to a method for optimizing spline coded structures, to a computer software product for executing such a method as well as to the use of such a method for the optimization of the shape of aerodynamic or hydrodynamic structures.

"Optimization" is to be understood as improving an encoded representation of an initial real-world structure, wherein the improvement can be expressed in terms of physical parameters. The result of the optimization is an encoded representation which, when being used as a building plan to implement again a real world structure, will lead to an improved real-world design which is superior to the initial real-world structure in terms of the said physical parameters .

The present invention particularly relates to the SeIf- adaptation of the representation of a real-world design in an iterative optimization.

"Iterative optimization" is an optimization where the representation is encoded using object parameters (encoding the real-world design) and strategy parameters controlling the step size of a modification of the object parameters from one step of the iterative optimization to

the subsequent step. The quality of the representation can be evaluated and used for setting up the representation for the next iteration step.

"Adaptation of the representation" means that not only the values of the object parameters may change from one step to the subsequent step of the iterative optimization, but also the topology of the representation, e.g. by changing the number and position of the object parameters and the associated strategy parameters.

Example for an iterative optimization: Evolution Strategy (ES) :

In the following the principles of Evolution Strategy, being an example for an iterative optimization based on parameter set with object parameters and strategy parameters, will be explained. Basic operations are mutation and recombination as a method for modifying structures or parameters. To eliminate unfavorable modifications and to proceed with modifications which increase the overall quality of the system, a selection operation is used. Principles of the evolution strategy can be found for example in Rechenberg, Ingo (1994) "Evolutionsstrategie" , Friedrich Frommann Holzboog Verlag.

With reference to figure 1 at first the known cycle of an evolution strategy will be explained.

In a step 1 the object parameters (representing a real- world structure in encoded form) to be optimized are

encoded as real numbers in a vector called individual or chromosome. One individual can alternatively also consist of several vectors. A number of such individuals are generated that comprise the initial parent generation and the quality (fitness) of each individual in the parent generation is evaluated. In a step S2 the parents are reproduced by applying operators called mutation and recombination. Thus, a new generation is produced in step S3, which is called the offspring generation. The quality of the offspring individuals is evaluated using a fitness function which is the objective of the optimization in step S4. Finally, depending on the calculated quality value, step S5 selects (possibly stochastically) the best offspring individuals (survival of the fittest) which are used as parents for the next generation cycle if the termination condition in step Sβ is not satisfied.

In particular for this application the real number vector, the object parameter, represents the coding for a spline which describes a two or higher dimensional body. This mapping from the parameter vector to the spline encoded structure is usually referred to as the genotype (=the parameter vector) - phenotype (=the two or higher dimensional body) mapping. In order to determine the fitness in step S4 , first the genotype is mapped to the phenotype and then the quality of the phenotype is derived. A particular example is the parameterization of an airfoil (=the phenotype) by a real-valued vector

(=genotype) describing a spline which determines the geometry of the airfoil. Finally, the quality of the airfoil can be determined, e.g. by methods known from computational fluid dynamics.

The mutation operator for the reproduction in step S2 is realized by adding normal or Gaussian distributed random numbers to the already existing object parameters. The step size of the mutation can be controlled by modifying the variance of the normal or Gaussian probability density function. The variances are called strategy parameters. In higher dimensions the strategy parameters can consist of all or some entries of the covariance matrix of the higher dimensional Gaussian probability density function. This method to control the mutation by means of strategy parameters particularly distinguishes evolution strategy from other evolutionary algorithms like genetic algorithms

(GA) or genetic programming (GP) .

Appropriate values for the strategy parameters are important for the convergence of the algorithm. The appropriate values depend on the problem and the actual position in the solution space. To adapt the mutation width online, different adaptation strategies are used. Some simple methods are the 1/5 rule (see Rechenberg) or the so-called mutative step size control. More complex methods are, for example, the de-randomized adaptation method or the co-variance matrix adaptation.

Evolution strategies have been shown to outperform other evolutionary algorithms like genetic algorithms or genetic programming for real-valued parameter optimization problems due to the above-mentioned possibilities of the adaptation or self-adaptation of the step size(s) of the mutation operator.

A known problem for the application of evolution strategy to design optimization is that the number of parameters which describe the model (the so-called object parameters) is fixed in traditional evolution strategy. Therefore, an automatic refinement of the phenotype represented by the object parameters during the optimization is impossible.

Mathematically, the mutation operation step can be expressed by the following equation (1) :

x°=x ^p + N$,σ _P ) (1)

thereby x° represents the parameter set of the offspring, x ^p represents the parameter set of the parents and Nψ,σ _p ) represents a vector whose elements are normal distributed random numbers with zero mean with variancesσ>,- ² . As can be seen from Fig. 3, a larger strategy parameter σ _pι increases the probability for larger steps in the offspring mutation.

More generally, the mutation operation can be represented by the following equation (2) :

x°=x ^p +δ (2)

wherein

(3)

Fig. 3a and b show the resulting probability distribution for placing an offspring, wherein Fig. 3a shows a 3D-plot and 3b shows a contour-plot . δ is a random vector with a general Gaussian probability density function as specified in Eq. (3) , if the covariance matrix σ is diagonal, Eq. (2) is reduced to Eq. (1) where the elements of the vector

(<Tp), the variances σ _Pi ² , are the diagonal elements of σ.

The covariance matrix σ has to be adapted to the local quality function. Fig. 4d shows the self-adaptation of the strategy parameters (covariance matrix σ) to the local quality function. Particularly, Fig. 3c shows the result of four cycles of the reproduction process, wherein the 3d surface represents the quality function. By the self- adaptation of the strategy parameters to the local quality function regarding the direction and the step size a good convergence towards the absolute maximum of the local quality function can be achieved.

Other examples of iterative optimization (or "search") with adaptive representation:

The present invention find equally application e.g. for the following approaches:

- Global Random Search: Strategy parameters in this case parameterize a probability density function which is adapted during the search.

- Real-coded Genetic Algorithm:

The real-coded algorithm uses a number of parameterized cross-over and recombination operators to determine the changes of the control points . Strategy parameters can parameterize crossover operators which can be adapted during the optimization (search) .

Object of the present invention:

The invention proposes a method for a self-adaptation of the representation of a real-world design in an iterative optimization and particularly with the adaptation and initiation of the strategy parameters, e.g. the strategy parameters controlling the step size of a modification of the object parameters from one step of the iterative optimization to the subsequent step.

This object is achieved by means of the features of the independent claims. The dependent claims develop further the central idea of the invention

Summary of the invention:

The invention proposes a computer-implemented method for iteratively optimizing a real-world structure, the method comprising the steps of: a.) encoding the structure in a parameter set comprising object parameters encoding the real-world structure and strategy parameters,

b.) modifying the parameter set wherein the strategy parameters control the modification of the value of the object parameters between two steps of the iterative optimization, c.) repeating step b.) until a termination criterion is met, wherein step b.) comprises the step of modifying the topology and not only the values of the parameter set, the topology of the parameter set being modified by adapting the number of object parameters as well as adapting the associated strategy parameters, wherein, when carrying out a modification of the topology of the parameter set, the object parameters and the strategy parameters are set such that after the modification step b.) the expectation value (E) and the variance (VAR) of the parameter set with modified topology are equal to the expectation value and the variance of the parameter set with unmodified topology.

The object parameters and strategy parameters can be inserted and/or removed.

The object parameters can be control points of a spline curve or surface .

The object parameters can be control points of a free form deformation representation.

The strategy parameters can be parameters of the density function of a Global Random Search.

According to a further aspect of the present invention, a computer software program for executing a method as said above is proposed.

Finally, the invention proposes the use of such a method for the optimization of the shape of aerodynamic or hydrodynamic structures.

Further features, objects and advantages of the present invention will become evident for the man skilled in the art when reading the following description of embodiments of the present invention when taken in conjunction with the figures of the enclosed drawings.

Fig.l shows a schematic representation of an evolutionary algorithm.

Fig.2 is a graphic representation showing the influence of the strategy parameter value.

Fig.3 shows the relation between the strategy parameter and the direction and step size of the evolution strategy process.

Fig.4 shows schematically the structure mutation for individual step size adaptation of the strategy parameter. Note, that the neighboring control points and strategy parameters might also be affected by the structure mutation.

Fig.5 shows schematically the structure mutation for the covariance matrix adaptation of the

strategy parameter. Note, that the neighboring rows and columns in the covariance matrix might also be affected.

Fig.6 shows a flow chart for the process of adapting the structure of a parameter set by- inserting/removing strategy and object parameters .

Fig.7 shows different hierarchies of mutations.

Fig.8 is a schematic flow chart showing the mutation of the structure of a parameter set.

Figs.9 and 10 show an application example of the present invention: the optimization of spline coded shapes .

Fig.11 shows the application of the present invention to the optimization of the shape of an aerodynamic or hydrodynamic body.

Fig. 12 shows a control loop comprising the adaptation of the strategy parameters according to a further embodiment of the invention.

Fig. 13 is an illustration of basis functions with inserting a knot.

Fig. 14 is an illustration of knot insertion in one embodiment of the invention.

According to the invention both the number of object parameters and strategy parameters of a parameter set of an iterative optimization method can be changed. Therefore, the optimization process can start with a relatively low number of parameters and the complexity of the parameter set can be refined during the optimization process.

With reference to Figs.4 and 5, the time point and/or the location for the insertion of a new object parameter in the existing parameter set can be defined for example by means of a random function or by measure of the progress of the optimization process. When inserting a new object parameter, at the corresponding location of the strategy parameters a new strategy parameter is inserted. The concept shown in Fig.4 refers to the so called individual mutative step size adaptation. Note that neighboring object and strategy parameters might also change after the modification.

The structure mutation of the covariance matrix is schematically shown in Fig.5. The strategy parameter according to this embodiment is represented as the covariance matrix σ (see equation (3) further above) . When inserting a new object parameter, the covariance matrix σ is adapted by inserting a new row and a new column, thus generating a new expanded covariance matrix σ' . The parameter set according to this representation is composed of the object parameter set and the strategy parameter, e.g. the co-variance matrix σ. Note, that neighboring rows

and columns of the covariance matrix might be affected by the modification.

Application Scenario Spline Coding:

A known approach for a representation (encoding) of a real-world design or structure is spline coding, the principles of which will now be explained. An example of a spline coded problem is shown in Figs. 10 to 12. Typically in such spline coded problems, all attributes of the shape are encoded in the parameter set (control points, knot points) which comprise the object parameters and the strategy parameters. Attributes which are not encoded cannot be represented and therefore cannot be subject of the optimization. As a consequence thereof, attributes cannot evolve during the optimization as long as they are not included in the parametric description of the parameter set .

The present invention now allows for a modification of the parametric description in order to allow new attributes in the encoding and therefore also in the shape to be inserted. The parameter set can not only be expanded by inserting new object and strategy parameters, but also be reduced by removing these parameters. This can be the case f.e. if an object parameter shows to be not sufficiently useful for further optimization.

When new components (new control points in the case of spline coded problems) are inserted in the encoding or the encoding is modified, the values of the existing and

possibly the newly inserted strategy parameters have to be recalculated.

One of the suitable ways is to utilize the parameterized curve or surface to encode the designed shapes. There are several shape parameterization techniques for the shape representation and manipulating. For convenience and without loss of generality, we here only focus on the problem with the two 2 -dimensional boundary curves as the target and corresponding designed curve which is defined by the B-splines.

Let

be a set of s-dimensional control points and also let the vector U = (u _o ,...,u _π+p )be the knot vector where a < U ₀ ≤ ... < b, a B-spline curve may be formulated as:

C{u)= ∑Z ^~ _Q Bi, _p {u)Pi a≤u≤b, (1)

where, the p-degree B-spline basis functions Bi, _p (u) may be formulated as the Cox-de-Boor recursion formula:

*«.o(«) if Ui < u < u _{i+x (2)} otherwise

+ _u Ui"+ ⁱ p ⁺ + ^P _l ⁺¹ — ^~ U _i ^U ₊ ι J iM ⁽³⁾

By using the B-spline family of curves, one obtains the following merits for optimization algorithms to manipulate the designed curve to fit the target:

- The B-spline curves have a local behavior, i.e., a point on the curve is only affected by several neighbored control points.

The low-degree B-spline form can represent complex curves efficiently and accurately.

The sensitivity derivatives of geometry C(u) with respect to Pi is the B-spline basis function Bi _(P/ which stays fixed when providing a fixed knot vector.

Therefore, each designed curve can be encoded by the coordinates of the control points and its knot vector. Furthermore, for evolutionary algorithms to operate the designed curves, e.g. Evolution Strategies, an individual can be represented basically by the components of the relevant curve: control points, knots; and by the strategy parameters for those control points. For the adaptive representation, which has the growing number of control points and related additional knots, the structural element is also encoded into the individual representation.

As already shown above, the optimization method may e.g. proceed as follows:

- An parameter set is set up comprising strategy parameters and object parameters (control points) , in

which each dimensional component of a control point takes a position in the parameter set, e.g. for a 2- dimensional curve with n control points, one has the individual representation as (c _Xχ ,c _α ,c _Xi ,c _yi ,...,c _x ,c _y ) .

The strategy parameters determine the strength of the modifications between two iteration steps. All components may share a common strategy parameter for the isomorphic mutation; each component has its own strategy parameter for the independent mutation or even more strategy parameters for the correlated mutation.

- The variation of the designed curve is realized by means of moving the control points. Together with the bases of the relevant splines, the exact variation step for each point in the designed curve can be calculated.

Obviously, the design optimization process is conducted by variation of the control points. Thus the strategy parameter is critical for its corresponding control point to perform the variation operation. While much attention has already been paid to the adaptation of the strategy parameters, a side effect on the adaptation of strategy parameters, brought out by the consecutive variation mechanism, will now be discussed in connection with figure 12.

Given a designed B-spline curve C(u) defined as (1) with n control points P ₁ and the basis functions Bi, _p (u) . For convenience and without loss of generality, let each control point have a strategy parameter vector σ..

Therefore, the representation of an individual is the set of pairs (^. ,σ ₍ . ) where usually σ, are standard deviations of the normal distributions. The adaptation process of σ. is shown in figure 12.

On the one hand, the adaptation of σ, is to adjust its value to vary the designed curve δC(u) in order to realize gradual improvement for the design task; on the other hand, the operation of σ, on the designed curve is indirect, but only to trail by means of affecting its related control point P ₁ and then combined with the basis functions Bi _/P (u) to determine the amount to change the designed curve. As a result, the goal of adaptation of strategy parameters lies in the current state of the designed curve, rather than the coordinates of control points.

Generally, evolutionary strategies are working in the following manner for design optimization:

σ,- adaptation (10)

where N(O, 1) is a normally distributed random number.

One always expects that with a sophisticated adaptation mechanism for strategy parameters σ,. , the curve C(u) can gradually move closer to the optimized design, by means of the variation of the control points P ₁ . This may be achieved when the basis functions {Bi, _p (u) | i 0,1,..., (n-

1)} are static, i.e. the knot vector U = (u ₀ , U ₁ u _n+p ) is fixed and the relationship between these control points and the designed curve is linear, since for given u, Bi, _p (u) are constants with respect to i. Therefore, the goal of following the variation of the designed curve is almost equivalent to moving the control points except for the combination of variations of the control points.

Unfortunately, when the bases are changing, which occurs in the context of the adaptive representation (i.e. a representation with adaptive topology and not only changing values of its parameters) , this relationship shifts to an undecidable mapping. Specifically when inserting a control point, the knot vector will then change with adding ^" a knot or be completely rebuilt and the basis functions will accordingly change. Such a variation of bases serves as nonlinear disturbance for the whole adaptation of strategy parameters.

In practice, for expanding the description length of the designed curve the knot insertion method is used rather than completely rebuild knot vectors. By means of the knot insertion method, one may add a new knot into the knot vector without changing the curve's shape. While a knot is inserted, the basis functions are then locally distorted, e.g., that shown in Fig. 13; and the neighbored control points have to be rearranged in order to keep the original

shape of the curve. This brings about two matters for evolutionary strategies to conduct consecutive searching:

related control points are rearranged but the corresponding strategy parameters remain previous values; the settings of strategy parameters for the newly added control point need to be determined reasonably.

Both of the problems are related to the settings of the strategy parameters when extending the description length for design optimization. The principle for suitable settings is that while holding the curve unchanged with the knot insertion, we need a further invariance that the strength of random variation keeps for each point in the curve.

The following shows how, according to the present invention, the object and strategy parameters of the representation (parameter set) are adapted and initiated when modifying the topology of the parameter set:

In the following the invention will be explained using a spline-coded curve as one illustrative example for a set of object parameters. Given the original curve C(u) and the topology-modified curve C'(u). By the standard knot insertion method (knot insertion being an illustrative example for a topology modification of a parameter set) , one has the basic invariance, i.e. C(u) = C'(u). In other words, the topology adaptation is made such that topology-

modified curve is equal to the original curve (i.e. the curve without topology modification) .

Further, let C (ύ) and C' (u) be the one step modification of C(u) and C' (u) , the (parameter value) modifications of which are controlled by their respective strategy parameters. The further principle for the invariance of strength of random variation requires that and are satisfied, where E[.] is the expectation and Var[.] is the variance. Moreover, the first term is referred to as the first-order invariance and the second term is denoted as the second order invariance.

In other words, when modifying the topology of the parameter set according to the present invention, the object parameters and the strategy parameters are set such that, after carrying out a modification step b.), the expectation value (E) and the variance (VAR) of the parameter set with modified topology are equal to the expectation value and the variance of the parameter set with unmodified topology.

According to the scheme of (10), let the variation of an arbitrary curve be,

and the expectation and the variance be

»=o

and

Then given the original curve C(w)and the topology- modified curve C' (w) , one has the first-order and second- order invariance for this modification, that is that

Therefore, the following conditions,

^(B _i)P (u)) ² (cf,) ² = £(β; _(P ( _U )) ² (α;) ² (17) i=0 »=0

are obtained. Note that the first-order condition (16) is equivalent to the basic invariance for knot insertion and the second-order condition provides a channel to reasonable settings of strategy parameters.

Given an original curve of a degree p consisting of a control point vector (P ₀ ,ϊ^,...,P _n _,} and a knot vector {M ₀ ,M,,...,M _n+/ ,} . Suppose the knot to be inserted lies in the span [Uk ₇ U)C ₊ I) , according to the convex hull property, the knot insertion computation is restricted on control points

P _k ,P _k+l ,...,P _k _ _p } . A way of modifying the control points is illustrated in Fig. 14 and formally stated as below:

Qi = (1 - Qi)Pi- _I + (XiPi (18) where t — u- oti = — for k - p + 1 < i < k. u _i+p - Ui

Using equation (18) , the whole control point vector may be reconstructed.

Furthermore, to rebuild the individual representation for evolutionary strategies, one also needs to find the values for the strategy parameters of the related control points. Due to the local behavior in a B-spline curve, calculation can be restricted on part basis functions rather than that for the whole curve .

The strategy parameters are determined by the second-order invariance and calculated as follows. Lets choose 2p+l knots as {w _t - _2/ ,.n _> ^M *- _2p+2> —.«*»'} / where t is the new knot and p is the degree. According to these parameters, 2p+l points may be calculated for each of both original and modified curves . From the second-order invariance presented in (17) , one obtains the linear equations in (19) with respect to the given 2p+l knots. Note that the matrix is a lower triangular matrix, therefore, the settings for strategy parameters can be recursively computed.

Equation (19) is as follows:

= σ - B = [ (^_ _2p+1 ) ² (<n_ _2p+2 ) ² rø <n ₊₁ ⁾² ]

^■B *-2p+l,p( ^W *-2p+l)

^{: ■B} *-2p+2,p("*-2p+2)

^-p,p(«*-p)

Further examples for the application of the present invention apart from airfoil shapes are compressor/turbine blades for gas turbines (stator and rotor blades) and other aerodynamic or hydrodynamic structures . The invention also finds application for the optimization of engine parts (engine valve design) or automotive chassis design. Other fields of application are architecture and civil engineering, computer science, wing design, engine valve design and scheduling problems.