ES-2

Question 1

Covariance Matrix Adaptation

Answer 1

• continuous optimization of non-linear, non-convex functions
• handle ill-conditioned problems such as discontinuities, (sharp) ridges, or local optima
• on convex-quadratic objective functions, setting the covariance matrix of the search distribution to the inverse Hessian matrix is equivalent to rescaling the ellipsoid function into a spherical one
• increase the likelihood of repeating successful steps

Question 2

What is the objective of CMA ?

Answer 2

The final objective of covariance matrix adaptation is to closely approximate the contour lines of the objective function f

Increase the likelihood to repeat successful steps.

Question 3

What method is similar to CMA ?

Answer 3

Learning the covariance matrix in the CMA-ES is similar to learning the inverse Hessian matrix in a quasi-Newton method.

Question 4

How offspring are generated in CMA-ES

Answer 4

offspring is generated by sampling a multivariate normal distribution

Question 5

CMA-ES with convex-quadratic (ellipsoid) objective function.

Answer 5

-any convex-quadratic (ellipsoid) objective function is transformed into the spherical function

Question 6

what is the purpose to Combining Rank-μ-Update and Cumulation

Answer 6

handle various of population seize.

Question 7

Influence of population size in CMA-ES ?

Answer 7

• Small population sizes usually lead to faster convergence,
• large population sizes help to avoid local optima.

Question 8

Invariance property of cam es

Answer 8

• translation,
• rotation, and
• scaling of the coordinates

-strictly monotonic transformations
of function values

• Invariance to order preserving (i.e. strictly monotonic) transformations of the objective function value. The algorithm only depends on the ranking of function values.
• Invariance to angle preserving (rigid) transformations of the search space (rotation, re- flection, and translation) if the initial search point is transformed accordingly.
• Scale invariance if the initial scaling, e.g. σ(0), and the initial search point, m(0), are chosen accordingly.

Question 9

(1+1)-CMA-ES

Answer 9

• use rank-1 update
• update the C using AA^T
• 1+1 cma-es on convex quadratic functions, O(n2) iterations are required for the covariance matrix to approach the inverse Hessian

Question 10

(μ/μ, λ)-CMA-ES

Answer 10

• use rank-μ update

- using eigenvalue decompositions to obtain B and D such that C=AA^T where A=BDB^T

Question 11

what are the two variants of restart CMA-ES

Answer 11

-IPOP-CMA-ES:
detect stagnation
restart with doubled population size

-BIPOP-CMA-ES interlaces two restart strategies:
one strategy uses an increasing population size, the other one a small population size
both have the same computational budget

Question 12

what is differential evolution ?

Answer 12

differential evolution is a newer heuristic that uses differences between points in the population as mutation vectors

Question 13

what is Particle Swarm Optimization ?

Answer 13

candidate solutions are referred to as particles, the population as a swarm
each particle has a velocity; previous best positions bi are stored for each particle i

Question 14

Disadvantage of DE and PSO ?

Answer 14

like DE, PSO is not rotationally invariant

Question 15

what is Information Geometric Optimization ?

Answer 15

• optimization in a space of probability distributions choice of a statistical model
• stochastic relaxation of the objective
• stochastic natural gradient descent, where the gradient estimate is obtained through Monte Carlo estimation

Question 16

relation of CMA-ES and IGO ?

Answer 16

the CMA-ES is in essence an IGO algorithm (plus rank-based utility weights, lowpass filtering to reduce noise, separate step size adaptation, . . . )

Question 17

A B C D in CMA ES

Answer 17

A is symmetric AA(inv) is I

B is an orthogonal and normal matrix

D is a diagonal matrix

C is the covariance matrix BD can obtain from wife value decomposition of C