Thème Cog

Nikolaus Hansen

Adaptive Encoding for Optimization

Keywords: optimization, evolutionary algorithms, encoding, representation, coordinate system, covariance matrix adaptation, invariance

This report describes a general method for rendering search coordinate system independent, Adaptive Encoding (AE). Adaptive Encoding is applicable to any continuous domain search algorithm and includes (incremental) changes of the coordinate system, that is, changes of the representation of solutions. One attractive way to change the representation within AE is derived from the Covariance Matrix Adaptation (CMA). We prove that adaptive encoding recovers the CMA Evolution Strategy, when suitably applied to an evolution strategy with cumulative step-size adaptation. The proof implies that adaptive encoding provides the means to apply CMA-like representation changes to any search algorithm in continuous domain.

Introduction

In optimization or search, the problem encoding, that is the choice of the representation of the optimization problem is of utmost importance. A good representation, if available, can render any search problem trivial-finding a proper representation means essentially solving the problem. In an iterative search procedure, in principle, a good problem representation can be iteratively approached, just as a good solution to the problem is approached in the iteration sequence. Indeed, for example, variable metric methods like quasi-Newton methods [START_REF] Davidon | Variable Metric Method for Minimization[END_REF][START_REF] Goldfarb | A Family of Variable-Metric Methods Derived by Variational Means[END_REF], covariance matrix adaptation (CMA) [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF], or estimation of distribution algorithms (EDAs) [START_REF] Larrañaga | A review on estimation of distribution algorithms[END_REF] implicitly conduct a representational change. In evolutionary algorithms, given an additive (mutation) operator, a linear change of representation is equivalent with an appropriate linear transformation of the additive mutation [START_REF] Hansen | Invariance, self-adaptation and correlated mutations in evolution strategies[END_REF]. Linear transformations of additive mutation operators, parameterized in step-sizes or covariance matrices, are well studied in evolutionary algorithms [START_REF] Beyer | Evolution strategies: A comprehensive introduction[END_REF][START_REF] Larrañaga | A review on estimation of distribution algorithms[END_REF].

In this report, we sketch an explicit framework for an iterative incremental representation change, adaptive encoding. The framework by itself is just about trivial. While the framework is quite general, this report considers only linear changes of the representation in continuous domain.

Searching for a linear representational change in continuous domain complements the original n-dimensional search problem with a second search problem of size n 2 . The advantage from adaptive encoding is that these two search problems are decoupled. Consequently, any efficient representation change can be applied to any underlying search procedure.

In the next section we give the preliminary notations and definitions. In Section 3 the general idea of adaptive encoding is introduced. Section 4 explicates a few examples. In one of them adaptive encoding recovers an EDA. Section 5 proposes a universal, efficient update rule, AE CMA , for the representation. We prove that AE CMA -CSA-ES recovers CMA-ES.

Preliminary Notations and Definitions

Let f : R n → R be an objective function to be minimized. Let a search algorithm propose new candidate solutions, x, in an iterative procedure and typically evaluate them on f . Let further denote S the state space of the search algorithm;

A : S → S an iteration step of the search algorithm A; For convenience, we assume that all available and necessary information to update B is included in algorithm state s and we will regularly write U(B) instead of U(B, s);

From these definitions we first remark, that an iteration step of an algorithm can be surrounded by an encoding-decoding step according to

A B ≡ T B • A • T -1 B , (1)
defining a new algorithm A B : S → S. If T B is the identity the original algorithm A is recovered. By definition, encoded solutions (phenotypes) are represented in the given coordinate system, where also f is evaluated. Accordingly, the algorithm operates, by definition, on decoded solutions (genotypes). We assume, for convenience and w.l.o.g., that recently evaluated solutions are part of the algorithms state.

Remark 1 (Evaluation of solutions). In order to make use of Eq. (1), we have to ensure that candidated solutions are evaluated according to their original representation. Solutions must be encoded before evaluation. In other words, A operates on f • B.

Considering Remark 1, we can execute the algorithm A in any coordinate system of our choice. The new coordinate system, where the operations of A are effectively conducted, is given by B. Optimizing f • B instead of f already renders A independent of the given coordinate system (if B is chosen independent of the given coordinate system). Eq. ( 1) becomes meaningful when we additionally adapt B. Later we choose T B such that changes of B do not change the retained solutions in their original representation (encoded solutions).

Finally, we assume to have a performance measure when running an algorithm on a function.

INRIA

Remark 2 (Performance measure). In the following, we assume to have a performance measure for running a search algorithm on the objective function f .

The performance measure determines whether one algorithm is better than another. For example, a typical, quantitatively useful measure is the number of candidate solutions evaluated on f until a target function values is reached.

Further symbols which will be used repeatedly in this report are given in the next paragraph.

Symbols

• the composition of mappings, e.g., (f • B)(x) = f (B(x)) for all x.

← the assignment operation. We will write, for example, BB T ← C , meaning we assign B to a value such that BB T = C. If the asignment is not unique under the definition for B, any compliant value is assigned. µ, λ integers denoting the number of parental solutions and offspring solutions respectively.

µ w = 1 µ i=1 w 2 i
≥ 1 the effective parent number, also denoted as variance effective selection mass [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF].

I the identity n × n unit matrix. i(f ) the index of the i-the best solution in respect to function value f . N i (0, C) a multi-variate normal distribution with zero mean and covariance matrix C. The index i denotes a certain realization.

R i ∈ R n a random vector.
B T the transpose of B.

w i = ln(µ+1)-ln i µ ln(µ+1)-µ j=1 ln j , for i = 1, . . . , µ, positive weights summing to one.

Adaptive Encoding

Equation (1) represents an iteration step of a search algorithm with an additional encoding-decoding procedure. The encoding is, throughout this report, parameterized by a n × n-matrix; it therefore introduces n 2 additional degrees of freedom to the iteration step of the algorithm. Obviously, the idea is to find a "good" encoding for algorithm A.

Aim 1 (static encoding). The goal of finding a good encoding is to find a transformation T B , such that

T B • A • T -1 B outperforms A on f
The static encoding is usually part of the design of the objective function. Equivalently, the algorithm can be modified specifically in regard to the given objective function (the encoding-decoding can certainly be interpreted as modification of the algorithm). The formalism of Aim 1 is not very interesting. To get a more interesting situation, we need to consider an update or adaptation of the encoding T B . Definition 1. (Adaptive Encoding) Given an algorithm, A, an encoding, T B , determined by B, and an update, U, the iteration step of an adaptively encoded algorithm in state s ∈ S is defined as

s ← T B • A • T -1 B (s) (2) B ← U(B, s) (3)
where ← denotes the assignment operator and

T B •A•T -1 B (s) = T B (A(T -1 B (s))). We write T B • A • T -1 B ; U(T B ) (4)
to denote the iteration step defined by Equations ( 2) and (3).

Obviously, any iterative algorithm A can be plugged into the adaptive encoding mechanism.

Proposition 1. (Adaptive Encoding is universal) The Adaptive Encoding from Definition 1 can be applied to any search algorithm.

Proof. The proposition follows directly from the definition of T B as invertible mapping from S to S.

Even though Proposition 1 is just about trivial, it is of utmost importance for the implications of our results, because it establishes the general applicability of an effective adaptive encoding update rule.

Analogous to Aim 1, we consider the merits of an adaptive encoding.

Aim 2 (adaptive encoding). Find an update U, such that for a given T 0 and a given (initial)

T B T B • A • T -1 B ; U(T B ) outperforms T 0 • A • T -1 0 on f .
The left iteration step updates the encoding, the right iteration step applies a constant encoding, T 0 , to algorithm A.

Taking only a single iteration step, Aim 2 does not depend on the update U and it reduces to Aim 1. Consequently, Aim 2 becomes only interesting, when an iteration sequence is considered. Indeed, in a realistic automated scenario, Aim 2 can only be achieved in the iteration sequence.

Finally, we define three cases/scenarios when considering Aim 2.

Scenario 1. (Standard scenario)

The initial T B equals to T 0 . Aim 2 shall be satisfied for most given T 0 .

Scenario 2. (Ambitious scenario) The initial T B equals to T 0 . Aim 2 shall be satisfied for all given T 0 .

INRIA

Satisfying the ambitious scenario implies that no fixed optimal encoding T B exists and a changing encoding can, in principle, be better than any fixed encoding. Both, the standard and the ambitious scenario are reasonable objectives, depending on the given objective function.

Scenario 3. (Unrealistic scenario) For all T B = T 0 , Aim 2 shall be satisfied.

As we might be able to choose T B arbitrarily bad, it seems unrealistic that Aim 2 can be satisfied for any

T B = T 0 in general.
The remainder of this report further investigates the idea of adaptive encoding as given in Definition 1.

Example Applications of Adaptive Encoding

In this section, we give two examples of how an evolutionary algorithm is reformulated as a simple base algorithm with adaptive encoding.

In order to define an adaptive encoding, we need to specify the encoding of the algorithms state space, T B : S → S, and the update of the encoding, U. Both mappings depend, to a certain extend, on the baseline algorithm they are applied to.

The Scaling Adaptive Evolutionary Algorithm

We define in Algorithm 1 a "Baseline (µ, λ)-EA" with µ parental solutions, a recombination operator reco, λ offspring which are generated by adding a random vector R i ∈ R n , and a selection operator. The (µ, λ)-selection was chosen for notational simplicity. The results generalize to any selection operator that uses only the objective function values to take decisions (and not the parameter values of the candidate solutions itself).

The adaptive encoding of the baseline (µ, λ)-EA, AE-(µ, λ)-EA, is given in Algorithm 2. It adds a decoding step in the beginning, encodes solutions for evaluation, adds an encoding step at the end and finally updates the encoding. Remark 3. The encoding T B in the adaptively encoded (µ, λ)-EA (Algorithm 2) is of the form

T B : (x 1 , . . . , x µ , σ, y) → (Bx 1 , . . . , Bx µ , σ, y) , (5)
where y denotes remaining state variables.

Algorithm 1: Baseline (µ, λ)-EA The R i ∈ R n denote random vectors let µ, λ positive integers and µ < λ

1 initialize {x 1 , . . . , x µ } ∈ R n (a set of candidate solutions) 2 repeat 3 x i = reco(x 1 , . . . , x µ ) + R i , for i = 1, . . . , λ 4 f i = f (x i ) , for i = 1, . . . , λ 5 {x 1 , . . . , x µ } ← select({x i , f i } i=1,...,λ ) 6 until stopping criterion is met 7 RR n°6518
We aim at investigating the relation of the adaptive encoding of the baseline (µ, λ)-EA to conventional adaptations in evolutionary algorithms. Algorithm 3 complements the baseline (µ, λ)-EA with an adaptive scaling of mutations. We will prove in the following that, given the appropriate T B and U, the adaptively encoded algorithm (Algorithm 2) is equivalent to the scaling adaptive Algorithm 3, where mutations are scaled according to a diagonal matrix σ.

Assumption 1. Let select pick solutions only depending on the function values (not depending on the actual solutions), and let reco commute with B, in that

B • reco(x 1 , . . . , x µ ) = reco(Bx 1 , . . . , Bx µ ) (6)
for all B and all x 1 , . . . , x µ .

Theorem 1. Given Assumption 1, the adaptively encoded (µ, λ)-EA (Algorithm 2) implements the scaling adaptive (µ, λ)-EA (Algorithm 3), if x i = reco(x 1 , . . . , x µ ) + R i , for i = 1, . . . , λ Proof. Let initialize B = σ in Algorithm 2 and let the initial x i be identical in both algorithms. We consider one iteration step of both algorithms. First, we show that the same solutions are evaluated in both algorithms and consequently f i = f i . That means, we have to prove that Bx i in line 7 of Algorithm 2 equals to x i in line 5 of Algorithm 3, for all i = 1, . . . , λ.

U(σ) = adapt σ (σ) (7)
6 f i = f • B (x i ) = f ( B x i ), for i = 1, . . . ,
x i = reco(x 1 , . . . , x µ ) + σ× R i , for i = 1, . . . , λ 4 f i = f (x i ) , for i = 1, . . . , λ 5 {x 1 , . . . , x µ } ← select({x i , f i } i=1,...,λ ) 6 σ ← adapt σ (σ)
Bx i = B (reco(x 1 , . . . , x µ ) + R i ) = B reco(B -1 x 1 , . . . , B -1 x µ ) + BR i = reco(BB -1 x 1 , . . . , BB -1 x µ ) + σ × R i = reco(x 1 , . . . , x µ ) + σ × R i = x i for i = 1, . . . , λ (8)
Second, we prove that all x i are identical after one iteration step in both algorithms. According to Eq. ( 8), Bx i in line 7 of Algorithm 2 equals to x i and therefore f i = f i . Because select only depends on the function values, the individuals with the same indices are selected in both algorithms, respectively. Decoding in line 10 of Algorithm 2 assigns the desired equality.

Third, we remark that Eq. ( 7) implies that B = σ remains valid after the iteration step.

We have proven that under Assumption 1, adaptive encoding can equivalently replaced adaptively scaled mutations. We conclude by a few remarks on the applicability of this result.

Remark 4. The update, U, can always be chosen, such that Eq. [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF] holds, if all necessary information is included in the algorithms state.

Remark 5. Some typical recombination operators [START_REF] Beyer | Evolution strategies: A comprehensive introduction[END_REF] commute with linear transformations. Remark 6. The diagonal matrix σ in the scaling adaptive algorithm resembles (overall) step-size adaptation, if all diagonal entries remain identical.

EDA (Estimation of Distribution Algorithm)

Algorithm 4 implements a very simple Estimation of Distribution Algorithm (EDA) [START_REF] Larrañaga | A review on estimation of distribution algorithms[END_REF], denoted as sEDA in the following. Only the mean vector of the distribution is estimated for the next generation. Adaptive encoding for the sEDA is elementary and outlined in Algorithm 5. Only the mean vector m needs to be transformed according to T -1 B (m) = B -1 m. The adaptation of the encoding is given in line 11 of Algorithm 5. The adaptation resembles the estimation of a covariance matrix in a common EDA. The common EDA is given in Algorithm 6, where the empirical covariance matrix is computed in line 7.

The next theorem states that the adaptively encoded sEDA unconditionally implements the common EDA.

Theorem 2. The adaptively encoded sEDA (Algorithm 5) implements the common EDA (Algorithm 6).

Proof. We assume that initially BB T = C and that the initial m is the same in both algorithms. We prove that the same holds true after one iteration step.

Algorithm 4: Simple EDA (sEDA) N (0, I) denotes a normal distribution with covariance matrix I; i(f ) indicates the index of the i-th best solution initialize m ∈ R n (distribution mean) x i = m + N i 0, C , for i = 1, . . . , λ Proof. Assuming that x 1 , . . . , x µ are the µ best solutions in the recent iteration step, line 5 computes m according to Eq.( 3) in [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF]. Lines 7 and 10 of Algorithm 7 AE CMA -Update replicate the covariance matrix update equations ( 17) and ( 22) in [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF] with added or renamed normalization coefficients, denoted as α. Substituting the coefficients as given results in the original equations.

1 repeat 2 x i = m + N i (0, I) , for i = 1, . . . , λ 3 f i = f (x i ) , for i = 1, . . . , λ 4 m ← 1 µ µ i=1 x i(f )
4 f i = f (x i ) , for i = 1, . . . , λ 5 m ← 1 µ µ i=1 x i(f ) 6 C ← 1 µ µ i=1 (x i(f ) -m)(x i(f ) -m) T
The Algorithm 7 AE CMA -Update implements the covariance matrix update of CMA-ES with additional coefficients α to be specified (see Section 5.1). In the context of CMA-ES, this update works well for any choice of µ [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF].

Depending on the application of AE CMA -Update, a slow change of B might be desirable (see also Section 5.3). While C will only change slowly, as long as c 1 and c µ are small, the decomposition of C does not ensure a similar behavior for B • and D. For this reason, the diagonal elements are sorted in D. We conjecture, that lines 11 to 13 can be replace by a cholesky decomposition, or, more promising, by an incremental cholesky update, similar to [START_REF] Igel | A computational efficient covariance matrix update and a (1+1)-CMA for evolution strategies[END_REF], that ensures small changes, as long as c 1 and c µ are small. In this case, it might be sufficient to only encode the solutions for the function evaluation and, as an approximation, completely abandon the encoding-decoding of the algorithms state.

In the next section, we will discuss the choice of the coefficients and of the remaining parameters of the procedure. Section 5.2 shows how AE CMA -Update recovers CMA-ES. 3) in [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF] 5 set scalars α i ≥ 0, for i = 0, . . . , µ, cf. Sect. 5.1 In Algorithm 7, the scalars α p and α i for i = 0, . . . , µ, need to be chosen. They normalize the input entries for the covariance matrix update (most of them are the difference between a new solution and the former mean). In the original CMA, we can derive the expected lengths of the input entries from the sampling procedure. Under random selection the normalized entries are distributed according to

6 p ← (1 -c p ) p + c p (2 -c p ) α 0 (m -m -) // Eq.(17) in [6] 7 C µ = µ i=1 w i α 2 i (x i -m -)(x i -m -) T // rank-µ matrix 8 set scalar α p ≥ 0, cf. Sect. 5.1 9 C ← (1 -c 1 -c µ ) C + c 1 α p pp T + c µ C µ // Eq.(22) in [6] 10 B • DDB • ← C //
N (0, C) = B N (0, I) . (12)
In general, we cannot assume to know the expected lengths of the input entries, therefore we need to normalize them. In Eq. ( 12), the expected squared length of the decoded input entry, E B -1 B N (0, I) 2 , computes to n suggesting a normalization to length √ n. Keeping this in mind, we discuss the choice of the scalar coefficients in turn.

1 α 0 = √ n B -1 (m-m -) , normalizes the difference B -1 (m -m -) to length √ n.
Consequently, only the direction is relevant and the absolute size of the difference is disregarded.

α i = √ n B -1 (xi-m -)
, for i = 1, . . . , µ, is the conservative choice, where the length of the difference B -1 (x i -m -) is disregarded. In general, we recommend to choose

α i = √ n max l i β , median j=1,...,µ (l j ) for i = 1, . . . , µ , (13)
where l i = B -1 (x i -m -) . In this way, the median is set to "length" √ n and the maximal length is set to β √ n with β ≥ 1. We recommend β = 2. Unusual large entries may, for example, occur if solutions are originally sampled from a distribution with heavy tails. By chance, an outranging solution could enter the procedure despite a bad objective function value and an unjustified very large change of B would result. α p = 1 will be the usual choice, while α p = √ n p is a conservative alternative and will not allow to utilize the evolution path effectively; α p = 0 would be even more conservative.

Finally, we give the default settings for the constants used in AE CMA -Update and discuss the choices in turn.

c p = 1
√ n is the learning constant for the evolution path, which should be usually between 1 √ n and 2 n+1 [START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF]. For larger c p , the effect of the evolution path will attenuate. The backward time horizon for the evolution path is roughly c p -1 . We choose as default the "conservative" limit of the useful range, i.e. a comparatively large c p . The most conservative choice would be c p = 1.

w i = ln(µ+1)-ln i µ ln(µ+1)-µ j=1 ln j , for i = 1, . . . , µ are the recombination weights. They (must) sum to one and obey w 1 ≥ • • • ≥ w µ ≥ 0. Generally, we choose µ being half of the overall generated number of solutions per iteration (before selection).

c 1 = α c 0.2 (n+1.
3) 2 +µw is the learning rate for the rank-one update in line 10 of AE CMA -Update (middle summand), with α c = 1 as default. The denominator being quadratic in n reflects the degrees of freedom in the encoding matrix B. The formula is derived as a simplification from the original formulation in [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF].

c µ = α c 0.2 µw-2 + 1 µw (n+2) 2 +αµµw
is the learning rate for the rank-µ update (right summand in line 10), with α c = 1 and α µ = 0.2 as default. With increasing µ w , the learning rate increases and gets close to one. α c = 1 must be chosen positive and such that c 1 + c µ ≤ 1. The default value of one is about ten times smaller, i.e. considerably more conservative, than for CMA-ES. Too large values for α c potentially lead to a failure. Too small values slow down the adaptation. In any case, at least a minimalistic parameter study for α c is recommended.

The final parameter setting needs to be decided specifically for a given algorithm. We believe that the given guidelines will be usually sufficient to find good settings with reasonable effort. For AE CMA -CSA-ES (meaning CMA-ES), a good setting works across many objective functions and the identification needed to be conducted only once on a few simple test functions.

AE CMA Recovers CMA-ES

The CMA-ES implements two separate adaptation mechanisms, one for stepsize control and another for covariance matrix adaptation. Our next application of AE CMA is based on cumulative step-size adaptation (CSA, also denoted as path length control ). The (µ/µ w , λ)-CSA-ES is explicated in Algorithm 8. Its default parameters are

c σ = µ w + 2 n + µ w + 3 and d σ = 1 + 2 max 0, µ w -1 n + 1 -1 + c σ . (14)
For applying adaptive encoding, we choose the following invertible encoding for the state variables in CSA-ES,

T B : (m, p σ , σ) → (Bm, B • p σ , σ) . (15)
The x i = m + σN i (0, I) , for i = 1, . . . , λ x i = m + σN i (0, I) , for i = 1, . . . , λ

5 f i = f (x i ) , for i = 1, . . . , λ 6 m -= m 7 m ← µ i=1 w i x i(f ) 8 p σ ← (1 -c σ ) p σ + c σ (2 -c σ )µ w 1 σ (m -m -) 9 σ ← σ exp cσ
9 f i = f ( B x i ) , for i = 1, . . . , λ 10 m -= m 11 m ← µ i=1 w i x i(f ) 12 p σ ← (1 -c σ ) p σ + c σ (2 -c σ )µ w 1 σ (m -m -) 13 σ ← σ exp cσ dσ p σ E N(0,I) -1 14 end 15 m = Bm 16 p σ = B • p σ 17 AE CMA -Update({Bx 1 , . . . , Bx µ })
18 until stopping criterion is met

Application of AE CMA -Update

The scaling adaptive (µ, λ)-EA, Algorithm 3, samples new solutions without dependencies between variables in the given coordinate system, because σ is a diagonal matrix. Rendering the scaling adaptive (µ, λ)-EA coordinate system independent means that the distribution can reveal correlations with respect to the given coordinate system (if σ = I is not the identity).

For the scaling adaptive (µ, λ)-EA the encoding T B : (x 1 , . . . , x µ , σ, y) → (Bx 1 , . . . , Bx µ , σ, y)

suggests itself, where y denotes all further state variables. The step-size matrix σ is not transformed. An appropriate mapping for a covariance matrix σ 2 → Bσ 2 B T would not preserve the diagonal property. A transformation of the diagonal of σ with B can lead, by chance, to very small entries-a very undesirable result for a step-size. Because σ is not encoded, it is important that changes of B are modest.

A vector r, that denotes a direction rather than a solution point in state space (as for example a velocity in Particle Swarm Optimization [START_REF] Clerc | The particle swarm-explosion, stability, and convergence in a multidimensional complex space[END_REF]), would arguably map to Br.

Using B • instead of B in Eq. ( 20) is a possible alternative. Then, the stepsize matrix σ needs to learn the scaling which can be otherwise provided by the diagonal matrix D.

We experimented using the Cauchy distribution for the random vector R i in Algorithm 3 as a rather different example compared to CSA. The adaptive encoding was successfully applied in this case and made the Baseline (µ, λ)-EA roughly thousand times faster on proto-typical non-separable problems.

Summary and Conclusions

We have outlined an adaptive change of representation in continuous domain search, denoted as adaptive encoding (AE). The idea is simple: after each iteration step, (i) the algorithms state is "encoded", (ii) the encoding is adapted, and (iii) the algorithms state is "decoded" again for the next iteration, using the updated inverse encoding. Further, candidate solutions are encoded for their evaluation on the objective function, respectively. The implications from this simple procedure are surprisingly far-reaching.

1. Well-known evolutionary algorithms can be recovered from basic algorithms in that a specific adaptive encoding is applied.

2. The update of the covariance matrix in the CMA-ES can be entirely formulated by adaptive encoding, as adaptation of a representation matrix B (Proposition 2). The respective update rule is given in AE CMA -Update (Algorithm 7). Applied to the cumulative step-size adaptation (CSA) evolution strategy, the AE CMA can recover the CMA-ES (Theorem 3).

3. Adaptive encoding can be applied to any search algorithm. Consequently, with the AE CMA , the "covariance matrix update" of CMA becomes applicable to any continuous domain search algorithm. The AE CMA can render any search algorithm independent of the coordinate system, in particular

T 1 B

 1 B : S → S an invertible transformation, the encoding of the state space or change of representation. The transformation T B is here parameterized by a matrix B and uniquely depends on the values in B. The inverse T -denotes the decoding of the state space; B ∈ R n×n a full rank matrix. Columns of B represent a new coordinate system and B represents the respective a coordinate system transformation in R n . The linear encoding of candidate solutions reads B : x → Bx; U : R n×n × S → R n×n , (B, s) → U(B, s) = B new the change of representation by updating the matrix B.

Algorithm 2 : 2 repeat 3 x

 223 Adaptively Encoded (µ, λ)-EA Shaded areas implement the adaptive encoding. The begin-end block implements the baseline (µ, λ)-EA minimizing f • B. initialize {x 1 , . . . , x µ } ∈ R n (a set of solutions) 1 initialize B ∈ R n×n (a transformation matrix) i = B -1 x i , for i = 1, . . . , µ // decode state 4 begin 5

7 until stopping criterion is met 8 INRIA

 78 holds with probability one.

5 until stopping criterion is met 6 Algorithm 5 : 1 initialize B = I 2 repeat 3 m = B -1 m 4 begin 5 x 6 fAlgorithm 6 : 1 initialize C = I (empirical covariance matrix) 2 repeat 3

 5651234566123 Adaptively Encoded sEDA Shaded lines implement the adaptive encoding; the begin-end block embraces the sEDA; i(f ) indicates the index of the i-th best solution according tof i initialize m ∈ R n (distribution mean) i = m + N (0, I) , for i = 1, . . . , λ i = f ( B x i ) , for i = 1, . . . i(f ) -m)(Bx i(f ) -m) T11 until stopping criterion is met 12 Common EDA Shaded areas add to the simple EDA initialize m ∈ R n (distribution mean)

7 until stopping criterion is met 8 INRIAProposition 2 .

 782 Let σ denote a step-size and µ-1 w = µ i=1 w 2 i . Let α p = 1, α 0 = √ µw σand α i = σ -1 , for i = 1, . . . , µ. Then, the algorithm AE CMA -Update implements the update equations for the evolution path, p, and the covariance matrix, C = BB T , in the (µ/µ w , λ)-CMA-ES.

Algorithm 7 : 1 1 3 sorted in ascending order m -= m 4 m

 7134 AE CMA -Update({x 1 , . . . , x µ }) updates the encoding matrix B using the µ recent best-ranked candidate solutions given parameters w i , c p , c 1 , c µ from Section 5.given m ∈ R n , p ∈ R n and C ∈ R n×n from last iteration 2 let matrices B • orthogonal, and D diagonal, with diagonal elements ← µ i=1 w i x i // Eq.(

- 1 10until stopping criterion is met 11 Algorithm 9 : 3 initialize B = B • = I 4 repeat 5 m = B -1 m 6 p σ = B •T p σ 7 begin 8

 1119345678 AE CMA -CSA-ES Shaded lines implement the adaptive encoding, AE CMA , including the update of B and B • . The begin-end block marks the original CSA-ES initialize m ∈ R n (distribution mean) 1 initialize p σ = 0 (evolution path) 2 initialize σ > 0 (step-size)

  AE CMA -(µ/µ w , λ)-CSA-ES applies adaptive encoding according to Algorithm 7, AE CMA -Update, to the (µ/µ w , λ)-CSA-ES and is given in Algorithm 9. The µ best (encoded) solutions are used as input to AE CMA -Update (line 18 in Algorithm 9). The encoding T B solely depends on the matrix B, as B • can be computed from B by normalizing its columns to length one. As in our previous proofs, we assume the same initial state for AE CMA -(µ/µ w , λ)-CSA-ES and (µ/µ w , λ)-CMA-ES and first consider the sampled and

	Theorem 3 (Recovery of CMA-ES). Given T B as in Eq. (15) and the scalars initialize m ∈ R n (distribution mean) 1 initialize p σ = 0 (evolution path) 2 initialize σ > 0 (step-size) 3 for Algorithm 7 AE Algorithm 8: CSA-ES repeat 4

CMA -Update in each iteration as given in Proposition 2, then the AE CMA -(µ/µ w , λ)-CSA-ES (Algorithm 9) implements the (µ/µ w , λ)-CMA-ES.

INRIA

Proof.

RR n°6518

We ignore the case of denominators being zero, where the respective coefficient α can be set to any positive number.RR n°6518

http://www.inria.fr ISSN 0249-6399

First, we recognize that the same solutions are evaluated in both algorithms, because

in line 7 in Alg. 5

= BB -1 m + BN i (0, I)

The equation holds almost surely, if the random number realizations are chosen correspondingly in both algorithms. Consequently, f i = f i and i(f ) = i(f ) for all i = 1, . . . , λ. Therefore, the same solutions are used in the remaining operations and we find

It remains to be shown that after the iteration step BB T = C. This follows directly from the choice of the update rule.

5 A Universal Update Rule: AE CMA In order to define an adaptive encoding, we needed to specify the encoding of the algorithms state space, T B : S → S, and the update rule, U, of the encoding matrix B. In this section, our aim is to derive a universal update U, leaving only the choice of T B as remaining, algorithm specific design issue. Previously, we have used two update rules, both in order to recover a known evolutionary algorithm. In the first case, we had chosen U = adapt σ without further specification. In the second case, we had computed the decomposition of an empirical covariance matrix to derive B. The latter depends in particular on a sufficiently large number of solutions µ. In the following, we explicate a more universal update rule for the representation matrix B. The update is derived from the equations for the covariance matrix update in the (µ/µ w , λ)-CMA-ES [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF][START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF], denoted as AE CMA , and explicated in Algorithm 7 AE CMA -Update.

All parameters and coefficients of AE CMA -Update are in detail discussed in Section 5.1. The state variables are m, p and C. The mean m is initialized to the mean of initial solutions of the search algorithm to which AE CMA -Update is applied, and initially p = 0 and C = I. The covariance matrix update is based on differences between new solutions and the (former) mean. evaluated solutions Bx i , for i = 1, . . . , λ, in Algorithm 7. We have

which is the equation for generating new solutions in CMA-ES (Eq. ( 2) in [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF]).

Consequently, the same (encoded) solutions are generated (given respective random number realizations) and evaluated in AE CMA -CSA-ES and CMA-ES. Also i(f ) = i(f ) and the corresponding solutions are selected for the remaining updates.

We need to show that AE CMA -CSA-ES recovers the update of all five state variables of CMA-ES, m, p σ , σ, p and C. We treat each variable in turn.

The new mean in AE CMA -CSA-ES obeys

which is the equation for updating the mean in CMA-ES (Eq. ( 3) in [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF]). Next, we investigate the evolution path for the step-size, starting from line 17.

We compute the rightmost term to

where B = B • D holds according to Algorithm 7. Equations ( 18) and ( 19) recover the update rule for the evolution path p σ in CMA-ES (Eq. ( 23) in [START_REF] Hansen | The CMA evolution strategy: a comparing review[END_REF]). The update of step-size σ computes p σ = B • p σ . Because B • is orthogonal we have B • p σ = p σ . Consequently, the step-size update is identical in AE CMA -CSA-ES and CMA-ES.

Finally, completing the proof, p and C are updated in Algorithm AE CMA -Update according to the CMA-ES, see Proposition 2.

Theorem 3 supports the hypothesis that AE CMA -Update is an efficient way to update the representation matrix B, as CMA-ES is known to efficiently adapt the principle axes of the coordinate system, where the independent sampling takes place. In the next section, another application of AE CMA -Update is sketched.

INRIA


Yannick Gouchan

Writing Lives in Contemporary Italy

The article provides a historical survey of the practice of biography in contemporary Italy. Addressing topics ranging from the particular relationship between biography and the nation-building processthe effort 'to make the Italians' in the late nineteenth and the early twentieth centuriesto the different forms of telling lives in contemporary Italy, I will also examine the outlook of certain great intellectuals and historians on biography and discuss the importance of publishing firms and certain editorial collections for the practice of biography in order to understand several specific issues: national lives versus local ones; the selection of historical characters; the importance of microhistory; the biography boom of the 1970s and the 1980s; the studies about biography and the current state of research on it.

According to Maria Pia Casalena's impressive essay on the practice of biography in nineteenth century Italy, 8,000 biographies were published between 1800 and 1915. 1 Casalena provides considerable statistical information about the publishing houses and the cities where biographies were released. As expected, Rome, Bologna, Milan, Torino, Florence and Naples prevail over the rest of the peninsula. Nevertheless, the minor centers of culture show an interesting output of biographies dedicated to local public figures. Furthermore, one should recall that many biographies were actually translations from other languages and originated abroad, above all in France, the origin of 74% of the translated biographies in Italy before the Unification in 1861. The remainder of the translations came mainly from the United Kingdom (11%), Austria, and the United States. 2 Excepting these translations, Italian biographies were concerned mostly with the lives of saints, with historical models for youth (the genre of plutarchi), and with political heroes. The influence of these foreign biographical and historiographical works brought French and the English theories and doctrines, such as those of Samuel Smiles, to Italy. In 1865 the Barbèra publishing house released a very successful biographical essay by Michele Lessona entitled Volere è Potere, inspired by Smiles's theory of Self-help. 3 It was meant primarily to suggest examples of contemporary personal success across the country. More generally, the book intended to 'make the Italians'citizens had to be shaped in conformity to historical exempla. Another landmark of British influence is the earlytwentieth-century importance in Italy of Thomas Carlyle and his On Heroes, Hero-Worship, and the Heroic in History.

What is striking straightaway is the coexistence of two main types of biographies, the first dealing with religious figures, considered as a genre because of the specific editorial market and audience for these books, the other treating biographies of national and foreign historical characters (politicians, leaders, artists, etc.).

Given the context of nineteenth-century publishing and writing, biographers at this time, unsurprisingly, were mostly men (only 3% were women). Catholic hagiography was also very influential. The writing and reading of lives had a strong effect on nation-building, as in every other European country of the period. Indeed, the nineteenth century in Italy was the era of the country's emancipation from Austria, which had ruled, directly or indirectly, half the peninsula. After the Unification many biographies were written and published to justify a national culture and to create national models. Throughout the Risorgimento biographies enhancedin addition to the traditional history of the saintsthe tradition of national patriotic martyrs that held sway during the Austrian occupation. Important examples of these national symbols are Dante Alighieri, Ludovico Ariosto, Ugo Foscolo, and Christopher Columbus. Regarding the famous navigator, Angelo Sanguineti's book La vita di Cristoforo Colombo (1846) is particularly noteworthy in comparison with the Vita di Cristoforo Colombo (1895) of Cesare De Lollis, a scholar who also studied and edited Columbus's written works. These writers give two very different views on the colonization of the New World. [START_REF] Sanguineti | La vita di Cristoforo Colombo[END_REF] We should pay particular attention to great historians who wrote biographies, such as Gaudenzio Claretta, who specialized in the lives of Piedmontese nobility in the 1850s and 1860s, using thoroughly new sources. [START_REF] Gaudenzio | Dizionario biografico e genealogico del Piemonte[END_REF] We can also refer to Pasquale Villari, who integrated the new input of the historical sciences and of scientific historiography in his biographies of Savonarola (1859) and Machiavelli (1877), and to Angelo De Gubernatis, who initiated in 1878 the Dizionario biografico degli scrittori contemporanei and in 1889 the Dizionario degli artisti italiani viventi. [START_REF] Villari | La storia di Girolamo Savonarola e de' suoi tempi[END_REF] After 1861, the year of the proclamation the Italian Kingdom, the intention of 'making the Italians' involved a politics of memory. Biography now strongly served to create a national sense of belonging, celebrating the great figures of the past and the Risorgimento, such as Camillo Cavour, King Vittorio Emanuele II, Giuseppe Mazzini, and Giuseppe Garibaldi. These efforts were aimed at establishing a national pantheon. In the 1870s and 1880s the school curricula for History included biographies of national figures such as ancient Roman notables, warriors, generals, poets, inventors, and navigators. These plutarchi, written for young boys, intended to teach courage and fortitude. Indeed, the conservative governments told their version of the Risorgimento and its heroes with a particular taste for the anecdote and an overriding sense of morality.

After World War II, when communists and socialists nearly dominated the whole of Italian culture, a different biographical vision of the Risorgimento emerged. [START_REF]For instance the biographer and politician Giuseppe Massari[END_REF] This new view differed from the consensus of the late nineteenth century, when popular biographies of the Unification's protagonists still flourished and were inevitably connected with the heroism and the struggle for independence. [START_REF] Cosimo | Le grandi biografie popolari nell'editoria italiana del secondo Ottocento[END_REF] As a result, the life of Giuseppe Garibaldi as rendered in biographies changed, in accordance with the respective political views of his biographers ranging from the time of the first government in 1861 through to Fascism, when his character endured nationalist distortions. He was regarded either as a hero of the independence or as a rebel, either as a savior of Southern Italy or as a dangerous republican. [START_REF] Garibaldi | the wife of Giuseppe, won the Giovanni Comisso Prize in 2018[END_REF] Analogously, there are the biographies of the politician Giuseppe Mazzini, regarded sometimes as a disturbing figure for the government and sometimes as a saint of the newborn nation, a man at the center of an authentic cult because 'he became a God' in the twentieth century. [START_REF] Della | L'eroe scomodo e la sua ombra. L'immagine di Mazzini e la letteratura del Risorgimento[END_REF]

Biography, as Conceived by Certain Italian Intellectuals and the Research on Biography in the Twentieth Century

Benedetto Croce was a philosopher and historian whose influence strongly marked Italian culture for several generations. In 1947 he founded the Istituto per gli studi storici in Naples, which became a breeding ground for great historians. Croce briefly accounted for his own conception of biography in his essay La storia come pensiero e azione. Here he asserts an aversion to biography on the theoretical level, even though he used to practice the genre as a writer. For Croce, biography is deprived of a specific function because 'the individual character is thought and judged only by his own work and at the same time by what is not, the work he does and that which goes beyond him.' [START_REF] Croce | L'individuo è pensato e giudicato solo nell'opera che è sua e insieme non sua, che egli fa e che lo oltrepassa[END_REF] According to Croce, writers such as André Maurois, Emil Ludwig, and Lytton Strachey wrote merely 'pleasant historiographical literature'their biographies were bound to be forgotten and would soon be out of date. But after many decades we know that Croce's judgement was completely wrong. [START_REF] Croce | Storia della storiografia italiana nel secolo decimonono[END_REF] Today the biographies written by Croce are usually considered minor works. But his beautiful Vite di avventure, di fede e di passione contained six accurate biographies dedicated respectively to Filippo di Fiandra, il conte di Campobasso, il marchese di Vico, Isabella di Morra, Diego Duque de Estrada, and Carlo Lauberg. These were deliberately written in a spirit counter to the much-deplored fictionalized biographies. [START_REF] Croce | di fede e di passione (Bari: Laterza[END_REF] In contrast to Croce, Antonio Gramsci (one of the founders of the Italian Communist Party) recognized that the biographies written by Maurois, Ludwig, and Strachey had enabled the middle classes to come closer to history and politics than they had through the historical novels of Dumas and Hugo. 14 For Gramsci, indeed, biography has a function in the teaching of history, although, except for the plutarchi and the hagiographies, the Italian tradition suffered from a shortage of great popular biographies. By the way, a very recent essay on Gramsci has demonstrated that a biographical method allows for a qualification of the traditional teleological conception of his political outlook. [START_REF] Gerratana | Gramsci: Una nuova biografia[END_REF] In the same way, a famous historian of ancient Greece, Arnaldo Momigliano, considered biography to be not the means of creating a work of literature but rather an instrument for researching social history. He attributed importance to the relationship between biography and historiography in his four lectures at Harvard in 1968, which were published in English in his now-classic essay The Development of Greek Biography. [START_REF] Momigliano | The Development of Greek Biography[END_REF] So did Franco Venturi and, more recently, Carlo Capra (biographer of Pietro Verri and Giovanni Ristori) in their biographies of eighteenth-century politicians and intellectuals: they considered biography to be no less than the very foundation of history. [START_REF] Pierre | Usages de la biographie historique: Le cas italien entre Lumières et Restauration (2 e partie)[END_REF] The next generation of historians, born in the 1930s and 1940s and influenced by the social sciences, developed the 'new history' in Italy. They read and practiced biography in locales such as the Fondazione Einaudi in Turin (created in 1970) and the Istituto Universitario Europeo in Fiesole (created in 1972). They exposed Italian historiography to international influences due to their activity in France, especially at the École des Hautes Études en Sciences Sociales, and in the United States. Their new interest in mentalities and in the individual led to a new conception of the writing of lives. One of these historians, Carlo Ginzburg, published an important and celebrated book in 1976, The Cheese and the Worms: The Cosmos of a Sixteenth-Century Miller, which perceives biography to be a narrative genre belonging to the historical studies. [START_REF] Ginzburg | Il formaggio e i vermi: Il cosmo di un mugnaio del Cinquecento[END_REF] This biography tells the life of an obscure Renaissance miller called Menocchio in the Friuli (in the northeast of Italy).

In Italy, Giovanni Levi, Edoardo Grandi, and Carlo Ginzburg expressed interest in partial biography, no longer seeking to write an exhaustive survey of an individual's entire life. In Inheriting Power: The Story of an Exorcist, for example, Levi observed the behavior and the overall freedom of his subject within the interstices of a cohesive collection. [START_REF] Levi | L'eredità immateriale: Carriera di un esorcista nel Piemonte del Seicento[END_REF] Fundamental to the microhistorian's practice of biography is a reduction in the scale of observation, which has led to a new interest in the individual, in what is private or intimate, in individual customs, and in the promotion of singular phenomena. By doing research on a microscopic level, by using previously neglected sources, and by paying attention to tiny details, microhistorians were able to reveal factors that had previously been overlooked. [START_REF] Gylfi | The Life Is Never Over: Biography as a Microhistorical Approach[END_REF] Biographical studies, under the influence of microhistory, came to address the difference between uniqueness and representativeness, as well as the particulars of sexual life, eating and drinking customs, work habits, and the anthropology of the family. Giovanni Levi worked as a historian in France for the famous review Annales ESC, and in his labors there he considered the practice of biography to be related to sociology, anthropology, and psychology. According to Levi, the individual biography is not merely a private enterprise. It cannot be studied in an unequivocal way, because then it might be restricted to illustrating the links of individual behavior to common or expected social conditions. [START_REF] Levi | The Uses of Biography[END_REF] In the 1980s, microhistory inspired the Einaudi publishing house to create its Microstorie imprint, featuring biographies taking a strong interest in the mentalities manifested in the lives of individuals, especially the obscure ones. 22 In Italy, in the 1970s and the 1980s, the genre of historical biography was thriving. Biografia e storiografia, a collective essay published in 1983, symbolizes this period. 23 It was a time of intense debate in which the distinction between biography and historiography was no longer pertinent, because biography was considered part of the historical sciences. Italy was now expressing profound interest in biographies, but why? First, as we might expect, the biographical approach reflected the crisis of mass ideologies. Biography enabled Italians to imbue historical facts with meaning in a country where biography had no great tradition comparable to that of the English-speaking world. [START_REF] Rebeschini | La biografia come genere storiografico tra storia politica e storia sociale. Questioni di metodo[END_REF] Second, social history was taking a methodologically new direction toward the political and the institutional sphere. In the wake of this development there arose many new historical and political biographies. [START_REF]See the collective article 'La biografia: un genere storiografico in trasformazione[END_REF] For instance, we can recall the successful translation of Robert A. Rosenstone's John Reed: Rivoluzionario romantico in 1976, which became something of a new model for a generation of Italian biographers. [START_REF] Rosenstone | Rivoluzionario romantico[END_REF] In Italy collective reality had long prevailed over individual facts, mainly due to the cultural influence of both the Annales School and Marxist ideology. Furthermore, unlike in the English-speaking world, the biographer is hardly regarded as a professional in contemporary Italy. He is not really taken seriously, because he is often a journalist and not a historian. [START_REF] Turi | La biografia: un genere storiografico in trasformazione[END_REF] As a result, two horizons of expectation have emerged among readers: biographers primarily tell life stories addressed to a larger audience, whereas only historians can fashion biographically meticulous works, which are mainly addressed to other historians.

In the 1980s the genre of the historical biography became rather popular, as did writers' biographies. The case of the early-twentieth-century poet Dino Campana is significant: Campana was discovered again by virtue of a novelized biography by Sebastiano Vassalli published in 1984. This treatment led to a groundswell of enthusiasm for the Tuscan poet, who was regarded as a poète maudit because of his madness. In the wake of Vassalli's welldocumented book several biographies of Campana have appeared. [START_REF] Vassalli | The Night of the Comet[END_REF] Today the Istituto Nazionale Ferruccio Parri in Bologna is committed to conducting research on the history of the Italian Resistance and of the contemporary period. It promotes notable projects that elaborate a contemporary form of biographical investigation: the biographies of a community. In the wake of the emergence of the microhistorical tradition, the biografia di comunità, particularly in the northern part of Italy, has attempted to rebuild collective memory through a biographical method. It involves the collection of documents, such as interviews and recollections of evidence, in order to gather information about many different forms of local life. This research addresses the history of a specific community during times of notable and often shocking events that, most of the time, brought with them widespread trauma or an important turn in economic life. For example, biographies have been written about a community in Tuscany shaken by a reprisal during World War II, and have addressed the impact of industrialization on a village in the Emilia province. These biographies deal with many individual memories that have been brought together to constitute an archive of local collective memory. Their method tries to combine the historical investigation of individual lives with a partial reconstruction of the life and outlook of a community at a specific time. 29 The Importance of Certain Editorial Collections and the Dizionario Biografico In the early twentieth century the Formiggini publishing house in Genoa established its Profili imprint. Between 1909 and 1938, the publisher Angelo Fortunato offered 128 books to a wide audience, which on the whole were dedicated to great or lesser-known Italian or foreign figures, among them artists, politicians, writers, and scientists. New books were regularly and successfully released every two months. The challenge was to find the right balance between popularization and the presentation of facts, and to do so without distorting history or reducing its complexity. Later, Mondadori's popular collection Le Scie [the Wake] published the disordered and overabundant 'Collana di memorie, epistolari, biografie e curiosità.' This series, founded in 1926 by Arnaldo Mondadori, took a huge interest in passionate historical figures, women, heroism, and the private lives of great figures. 30 Many translated biographies by Emil Ludwig were published under this imprint. From the '60s onwards, the publishing house UTET brought out 'La vita sociale della nuova Italia,' an important series that was perhaps the first contemporary collection of high-quality biographies, 31 responding to the new appetite for the genre, especially for the lives of politicians. 32 One of its titles was Piero Pieri and Giorgio Rochat's biography of Marshal Pietro Badoglio, which was written more as a political biography than a story of the private life of a man who left his mark during World War II. 33 Between 1962 and 1995 the imprint, under the direction of Nino Valeri, released 42 books, making up 13% of the 288 biographies dedicated to post-Unification Italian figures in this period. The series mainly paid attention to individuals belonging to the ruling class or to the bourgeoisie, whose values were personified through their lives. 34 Among these biographies we find great historical figures, mainly politicians and writers, as well as artists, economists, and scientists. Examples of these now-classic books include Giovanni Boldini by Dario Cecchi, Edmondo De Amicis by Lorenzo Gigli, Pirandello by Gaspare Giudice, and Verga by Giulio Cattaneo, all published between 1962 and 1963. The later Benito Mussolini (1969), by Gaspare Giudice, was reflective of an innovative psychological turn. The biographers that contributed to this collection of publications were principally formidable scholars of history or literature, such as Dario Cecchi and Lorenzo Gigli, but there were also professional writers specializing in the genre, such as Massimo Grillandi, the author of many biographies. 35 In the wake of the Italian economic miracle of the '50s and the '60s, a new audience emerged for biographies dedicated to the imprenditori, those emblematic businessmen of Italian capitalism such as Giovanni Agnelli and Vittorio Valletta. 36 In the end, the imprint succeeded in creating an editorial pantheon of exemplary portraits. 29 Lorena Mussini, 'Un ponte culturale tra memoria e storia: la biografia di comunità', in E-Review 3 (2015). 30 Gabriele Turi, Storia dell'editoria nell'Italia contemporanea (Florence: Giunti Editore, 1997), 434. 31 Claudia Gollini, 'Biografia e divulgazione: la collana 'La vita sociale della nuova Italia'', in Italia contemporanea 193 (December 1993): 707-716. 32 Sergio Romano, 'Considerazioni sulla biografia', in Storia della storiografia 3 (1983): 113-123. 33 Piero Pieri and Giorgio Rochat, Badoglio (Turin: UTET, 1974). 34 Claudia Gollini, 'Biografia e divulgazione', 714-715. 35 Massimo Grillandi wrote two biographies for the UTET collection (Francesco Crispi in 1969 and Emilio Treves in 1977) and then wrote about the countess of Castiglione, Belli, Rasputin, Mata Hari, Lucrezia Borgia, etc. 36 Respectively: Valerio Castronuovo, Giovanni Agnelli (Turin: UTET, 1971) and Piero Bairati, Vittorio Valletta (Torino: UTET, 1983). Bruno Caizzi had written a double biography of Camillo and Adriano Olivetti in 1962 for the same series.

Besides this imprint, there was also Laterza, one of the main and more serious publishing houses for historical books, which sought a balance between its aim to maintain high scholarly standards and its intention of reaching many readers. [START_REF] Caracciolo | Il mercato dei libri di storia, 1968-1978: Elementi per una analisi[END_REF] Its catalogue now offers masterpieces of the genre including Rosario Romeo's Cavour e il suo tempo (1969-84), Denis Mack Smith's Garibaldi (1973), and Giorgio Bocca's Palmiro Togliatti (1973). In the wake of the microhistory boom, another large national publishing house, Einaudi, initiated in the 1980s its Microstorie series focusing on partial biographies: its titles included Pietro Redondi's Galileo eretico (1983), specifically dedicated to the trial of the scientist; Roberto Zapperi's Annibale Carracci (1989), limited to the origins and the youth of the painter; and Sara Caribbo and Marilena Modica's La santa dei Tomasi: Storia di Suor Maria Crocifissa (1989), which homed in on a process of sanctity in sixteenth-century Sicily.

A current example of a biographical series, in this case developed by the Gribaudo publishing house in the 2000s, is 'Le opere, i giorni, i luoghi: una biografia per immagini'. These biographies are especially dedicated to contemporary writers. They give preference to the places where their subjects lived (Calvino, Gadda, Fenoglio, Quasimodo, Pasolini, Pavese, etc.) and incorporate substantial iconographic documents and a considerable amount of testimonies. They have been published as large-format biographical albums.

In considering here how the publishing houses have played an important role in the flourishing of biography over more than four decades, the existence of the DBI (Dizionario Biografico degli Italiani) must be mentioned. With origins in the nationalist desire to praise noteworthy Italians, the project ultimately led to a necessary correction of the nation's historical narrative. In the nineteenth century, there was the Galleria dei contemporanei, published by Pomba, and the Dizionario biografico degli scrittori contemporanei, edited by De Gubernatis. Afterwards Leone Caetani constituted a corpus of 7,000 forms and notices for the Dizionario biobibliografico italiano, created in 1925 as a project of the Istituto Treccani, the Italian encyclopedia that had been founded by Giovanni Treccani and Giovanni Gentile. During the Fascist period the Dizionario was dominated by hagiographical lemmas that faithfully supported patriotism, nation-building, and national history as tinged by the aims and values of the Mussolini regime. Its celebrated figures were seen as reflections of the soul of the motherland. After Fascism, however, the DBI did not cease; it frequently kept up with new information obtained through historical research on eras ranging from the Roman Empire to the present. The dictionary opened itself to varied fields such as economy, business, the sciences, and the mass media. In addition, many women were included in the DBI, although they represented a minority at the beginning. It is not surprising that its contributors include important scholars such as Giovanni Levi, Arnaldo Momigliano, and Eugenio Garin. [START_REF] Pignatelli | editor of the Dizionario since 1964)[END_REF] Nowadays we can consult the 31,000 biographies collected in the Dizionario degli Italiani della Repubblica online, which contains an index of all the biographies published since the start of the First Republic in 1946. 39 Having presented this overview of the Italian biographical tradition, I would like to remind you of an important issue specific to this tradition of writing lives. The selection of figures has always been controversial with regard to where they properly belong: that is, are they part of the national or of a regional history?given that before 1861 every Italian simply belonged to a (sometimes great) local history having its own tradition and culture. 40 How could a biographer forget the inherent contrast between a late, unfinished common history and a rich, long-lasting local history? For example, since Unification biographical figures from southern Italy have relatively limited space, and what treatments there were mainly came from the Kingdom of Naples. Instead, more importance on the whole was given to members of the Piedmontese upper and middle classes, which were considered to be the collective protagonist of the Risorgimento. These groups imposed their rules, their particular conception of national historiography. Writing good biographies in Italy today means challenging what seems obvious: it should problematize the country's senses of national identity and of belonging, and strike a balance in emphasis between individual famous or minor local lives on the one hand, and a complex collective history on the other. [START_REF] Francesco | Dalle biografie individuali alla identità nazionale[END_REF]

See Valeria Sgambati, 'Le lusinghe della biografia', in Studi Storici 36, no. 2 (1995): 397-413.

Biografia e storiografia, Atti del Seminario promosso dalla fondazione G. Brodolini e dall'Istituto del diritto del lavoro e di politica sociale dell'Università degli Studi di Milano, ed. Alceo Riosa (Milan: Angeli, 1983).