Amine Boumaza
email: amine.boumaza@loria.fr

How to design good Tetris players

Introduction

Tetris is a single player game in which the goal is to place random falling pieces onto a game board. Each horizontal line completed is cleared from the board and scores points for the player [START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF]. It is a very popular game with simple rules which requires, however, lots of practice and elaborate strategies for human players to perform well. Although the rules of the Tetris are very simple, designing artificial players is a great challenge for the artificial intelligence (AI) community.

For instance, Demaine et al. [START_REF] Demaine | Tetris is hard, even to approximate[END_REF] proved the NP-Completeness of the offline version of the game 1 . In the offline version a deterministic finite sequence of pieces is fixed, and the player knows the identity and the order of all pieces that will be presented. The proof is based on a reduction between the 3-partition problem and Tetris. Later, Breukelaar et al. [START_REF] Breukelaar | Tetris is Hard, Made Easy[END_REF] proposed a simpler proof of the this. Intuitively these results on the off-line version of the game suggest that the on-line version, one in which the sequence is not known in advance, is of at least the same difficulty if not more. Interestingly, Burgiel [START_REF] Burgiel | How to lose at Tetris[END_REF] showed that it is impossible to win at Tetris in the sense that one cannot play indefinitely. There exist sequences of pieces, although rare, that if they occur will end the game with probability one.

When formulated as a decision problem or a learning problem, the number of states of the system becomes intractable. On the standard 10 × 20 game and 7 pieces, each cell in the board can be in 2 states (filled or empty) the total number of states is thus 2 10×2 × 7 ≈ 10 60 which approaches 10 60 states. This large state space cannot be explored directly, which pushes the need to use approximation mechanisms and thus design sub-optimal strategies for artificial players.

All these challenges render the problem of designing artificial players very appealing for the AI community, which addressed this problem in many publications using different techniques.

In this paper, we propose to use evolutionary algorithms to design artificial Tetris players. We discuss recent results that provide very successful players scoring many millions of lines on average and compare their performance with the best known artificial players. For that we will first, describe the problem of learning Tetris strategies and review some of the existing literature on the subject (section 3) that ranges from reinforcement learning to pure optimization and evolutionary algorithms. After which we will describe how to apply evolutionary algorithms to learn such players (section 4), and how to reduce the learning time which can be of a crucial concern. Each of our arguments is illustrated on different sets of experiments. Finally, we conclude our discussion and present future ideas we intend to follow to improve our findings.

The Tetris problem definition

In this section, we discuss the characteristics of the game of Tetris and the simplifications that are usually considered when designing artificial controllers. We also describe the components of the decision function that an agent uses to decide its actions.

Figure 1: On the left hand side, a sample game board (the wall). The size of the standard board is 10 squares wide and 20 squares tall. On the right hand side, the 7 Tetris pieces. From top to bottom and left to right "S", "Z", "L", "J", "T", "O" and "I".

In the game of Tetris, the player is faced with placing a randomly chosen piece (Fig. 1) on a 10 × 20 game board at each iteration. Pieces can be translated from left to right and rotated. When a piece is placed the player is faced with a new piece. When a row of the board is fully occupied, it is cleared and all pieces above the row collapse by one row. The game ends when the height of the wall reaches the top of the board. The aim of the player is to clear as many line as possible to delay the end of the game.

In the standard game, the pieces fall from the top of the game board with a certain speed that increases with the game level. The player has to decide where to place the falling piece before it reaches the other pieces in the board at which time it stops. The player has to plan its actions within this laps of time, which gets shorter as the player advances in the game.

Game simplifications

In the existing literature addressing learning Tetris controllers, authors usually address a simplified version of the problem where the dynamics of the falling pieces is not taken into account.

In the simplified version, the artificial player is given the current piece to place and the current state of the board and it has to decide where to place the piece. A decision in this case is a rotation (the orientation of the piece) and a translation (the column) to apply on the current piece. The player tests all possible rotations and all possible translations and decides, based on a decision function, on the best decision to take. Incidentally, this simplification does not affect the performance of artificial players on the original game as their decisions are usually made well within the shortest laps of time a piece takes to fall. Furthermore, except for few authors, most of the existing works address the so called "one piece strategies", where only the current piece is known and not the subsequent one, which is the case in the standard game. As it will be clearer in few paragraphs the extension to the original game's "two pieces strategy" is straightforward.

The decision function

In general, a Tetris game-playing agent decides which action (rotation and translation) to choose at a given state of the game based on the reward it will gain after performing that action. The agent chooses, among the several possible actions, the one that will return the best outcome. This reward may be instant i.e. at the next state of the game or delayed until the end of the game.

It is however difficult and sometimes not possible to judge the value of an action, and one way around this is to judge the value of the state to which the action leads. Generally this is achieved using an evaluation function that assigns numerical values to game states. The player then chooses among all possible actions the one that leads to the best valued state.

Figure 2: The decision tree of an artificial Tetris player exploring all possible actions for the current piece and evaluating all the outcomes. Given the current piece to place, the agent will choose the decision that will give the "best board", as illustrated on Figure 2. When a piece is to be placed, the agent simulates and evaluates all the possible boards that would result from all the possible moves of the piece, and then chooses the action that leads to the best valued game board (greedy strategy). In a "two pieces strategy", the player simulates two moves (one for the current and one for the subsequent piece) and selects the best one for the current piece. In this case the decision tree illustrated on Figure 2 is extended by an additional level.

Note that since the agent follows a greedy strategy, the evaluation function is the only component that enters into the decision making process. Hence, designing a Tetris player amounts to designing an evaluation function. Such a function should synthesize the game state giving high values to "good boards" and low values to "bad" ones. In this context "good boards" are ones that increase the chance of clearing lines in future moves.

We note s ∈ S a state of the game, s represents the configuration of the board at a given time. The evaluation function V : S → IR maps a state s to a number that estimates the value of the state s. Let us also consider P the set of the seven pieces and A the set of all possible actions. An action is a rotation of which there are 4 possibilities and a translation of which there are 10 possibilities2 i.e. |A| ≤ 40.

Further, we note a(p) ∈ A an action applied to the piece p ∈ P . We also note γ : S × A → S the transition function that maps a pair (s, a(p)), a state s and an action a(p), to a new state of the game after taking action a for the piece p in state s. The player's decision function π(s, p) : S × P → A, will select the action with the highest valued outcome:

π(s, p) = â(p) = arg max a(p)∈A V (γ(s, a(p))).
(1)

Feature functions

A state evaluation function V may be considered as mimicking the evaluation a human player makes when deciding where to drop the piece. It should rank higher game states that increase the chance to clear lines in subsequent moves. For example, such game boards should be low in height and should contain few holes (empty squares). Since the set of all possible game states is too large to be considered, a state is generally projected in a smaller set of features. These feature functions represent the most salient properties of a given state. These properties may be the height of the wall, the number of holes, etc. In the literature, many authors have introduced different features to synthesize different aspects of a game state. A comprehensive review of these features can be found in [START_REF] Thiery | Building Controllers for Tetris[END_REF].

The evaluation function V is a combination of these feature functions using generally a weighted linear sum. If we let f i and w i , with i = 1 . . . n, denote the n feature functions and their respective weights. Each f i maps a state s to a real value. The evaluation function V is then defined as:

V (s) = n i=1 w i f i (s) (2)
Other combinations of evaluation functions are also possible. For example, Langenhoven et al. [START_REF] Langenhoven | Swarm tetris: Applying particle swarm optimization to tetris[END_REF] use a feed forward neural network to which the value of each feature function is an input node. Böhm et al. [START_REF] Böhm | An Evolutionary Approach to Tetris[END_REF] proposed exponential combinations where they considered the feature functions powered to given constants.

In the remainder of this paper we consider eight features which are detailed on fig. 3. Six (f 1...6 ) of these were introduced by Dellacherie [START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF], and two (f 7 and f 8 ) were introduced by [START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF].

(f 1 ) (f 2 ) (f 3 ) (f 4 ) (f 5 ) (f 6 ) (f 7 ) (f 8 )

Related work on designing Tetris players

This section presents some of the works that addresses the design of artificial Tetris players. As described above, to design evaluation functions based controllers, one needs to select the set of feature functions, the way to combine them into the evaluation function and the parameters of this combination.

In most of the literature on the subject, the first two steps are generally performed by the expert designer and the only part left where learning algorithms are applied is the setting of the evaluation function's parameters. In other words, learning an artificial player for Tetris amounts to learning the correct set of parameters of the evaluation function. This task has been performed using different methods, that is what we will review briefly in the following.

Hand-tuning players

When the designer has enough insight about the desired behavior of the artificial Tetris player, it is possible to tune the parameters of the evaluation function by hand and experimentation. Dellacherie [START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF] proposed a set of six feature functions that were combined linearly (f 1 . . . f 6 in figure 3). He fixed the combination weights by hand based on the importance he gave to the individual features. Interestingly enough this controller was, until not long ago, one of the best performing ones, clearing 63 × 10 4 lines on average.

Learning to play

Others have used machine learning methods to learn correct values of the weights of the feature functions.

Most of the works to this end use reinforcement learning algorithms. Although little success has been achieved when compared to Dellacherie's hand tuned player; it however, provides insights on the difficulty of the task when the problem is formulated as a decision problem. In the following, we cite some of the works designing Tetris controllers, using reinforcement learning. A more comprehensive review may be found in Donald Carr's thesis [START_REF] Carr | Adapting Reinforcement Learning to Tetris[END_REF].

Among the first authors that addressed the problem of designing Tetris controllers, Tsitsiklis and Van Roy [START_REF] Tsitsiklis | Feature-based methods for large scale dynamic programming[END_REF] applied a feature based value iteration algorithm and reported a score of 30 cleared lines on average. The algorithm operates in the space of features rather than in the state space where the problem is intractable. Incidentally, the authors used only two features (the maximum height of the wall and the number of holes). At the same time, Bertsekas and Tsitsiklis discuss in their book [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF] the use of policy iteration algorithms, more precisely the λ-policy iteration algorithm. This algorithm iteratively refines a policy (playing strategy) using simulations. The authors chose a set of 2w + 2 features where w is the width of the game (22 features on the standard game). They extended Tsitsiklis and Van Roy's features with ones that represent the individual heights of each column and the differences of heights between two adjacent columns, and reported average scores around 3200 ± 20% lines. Later, on this same feature set, Kakade [START_REF] Kakade | A natural policy gradient[END_REF] applied a natural policy gradient method and reported scores of 6800 cleared lines on average. Farias and Van Roy [START_REF] Farias | Probabilistic and Randomized Methods for Design Under Uncertainty[END_REF] proposed to use linear programming for random constraints sampling and reported scores of 4700 lines on average.

Finally, Lagoudakis et al. [START_REF] Lagoudakis | Least-squares methods in reinforcement learning for control[END_REF] proposed a reduced set of features with only ten: the maximum height, the total number of holes, the sum of absolute height differences between adjacent columns, the mean height, and the change of these quantities in the next step, plus the change in score and a constant term. Using these features, the authors applied the least square policy iteration algorithm and reported scores between 1000 and 3000 lines on average. On this same feature set, Thiery and Scherrer [START_REF] Thiery | Least-Squares λ Policy Iteration: Bias-Variance Trade-off in Control Problems[END_REF] used the least squareλ-policy iteration algorithm, a generalization of the aforementioned λ-policy in which the algorithm uses a linear approximation of the state space and reported scores of 800 lines.

Optimizing players

Some authors considered the problem differently and proposed to set the parameters of the evaluation function using optimization techniques. For instance, Szita and Lõrincz [START_REF] Szita | Learning tetris using the noisy cross-entropy method[END_REF] applied the noisy cross entropy method algorithm (NCE) [START_REF] De Boer | A tutorial on the cross-entropy method[END_REF] to optimize the weights of the features introduced by [START_REF] Bertsekas | Neuro-Dynamic Programming[END_REF] and reported a score of 35 × 10 4 ±36%. The algorithm treats the problem as a search in the space of all possible weight vectors (IR 22 ) for the one that maximizes the average score. Initially random, the search point is moved according to a normal distribution at each step. Incidentally, this method closely resembles evolution strategies [START_REF] Rechenberg | Evolution strategy[END_REF][START_REF] Bäck | Evolutionary Algorithms in Theory and Practice[END_REF][START_REF] Beyer | Evolution strategies: A comprehensive introduction[END_REF], with some differences in the step-size update rule.

More recently Thiery and Scherrer [START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF] used the same NCE algorithm to optimize the weights proposed by Dellacherie and other weights they proposed. They reported the impressive score of 35 × 10 6 ± 20% lines on average. Furthermore, the authors give a review of the existing works on learning Tetris players and argue on the difficulty to compare different players using different interpretation of the game since small implementation differences may lead to large discrepancies in the final score. They also provide a simulator of the game that implements most of the features that exist in the literature so that algorithms can be compared on the same basis. The work presented here uses the same simulator.

Evolving players

In the same spirit of the work above, some authors propose to optimize the parameters of the evaluation function using evolutionary computation.

To our knowledge Siegel and Chaffee [START_REF] Siegel | Genetically optimizing the speed of programs evolved to play tetris[END_REF] were the first to propose such a design method that uses genetic programming [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF]. Though their work focuses on improving the speed of evolved programs, they used the game of Tetris as an illustrative application and reported a mean score of 74 over 20 runs3 . Llima [START_REF] Llima | Xtris readme[END_REF] used genetic algorithms to optimize the weights of the artificial player proposed on the GNU Xtris simulator.

The evaluation function uses six features: the maximum height of the wall, the number of holes, the depth at which the current piece is dropped, the length of the frontier between empty and filled squares 4 , cumulative wells (f 6 in figure 3) and the sum of the depths of all places where a long piece (I) would be needed. The evolved controller scores 5 × 10 4 on average.

Furthermore, Böhm et al. [START_REF] Böhm | An Evolutionary Approach to Tetris[END_REF] used an evolutionary algorithm to design Tetris players for which the authors proposed new features along with Dellacherie's features and three different evaluation functions: a linear combination as in equation ( 2), an exponential combination and exponential with displacement. The last two functions rate differently differences in heights when the board is low than when it is high, reflecting the fact that the height of the wall is less critical when the wall is at the bottom of board. The authors considered the two piece game for which they reported scores in the millions lines. More recently, Langenhoven et al. [START_REF] Langenhoven | Swarm tetris: Applying particle swarm optimization to tetris[END_REF] proposed to use particle swarm optimization (PSO) [START_REF] Kennedy | Swarm Intelligence[END_REF] to optimize the weights of a feed forward neural network used as an evaluation function. The values of the feature functions are inputs to the network of which the output is the value of the state. The PSO algorithm is used to optimize the weights of the neural network. The authors reported scores around 15 × 10 4 lines on average.

Evolution strategies to learn Tetris

In this work, we propose to use evolutionary algorithms, more specifically an evolution strategy [START_REF] Rechenberg | Evolution strategy[END_REF][START_REF] Bäck | Evolutionary Algorithms in Theory and Practice[END_REF][START_REF] Beyer | Evolution strategies: A comprehensive introduction[END_REF] to learn the weights of an evaluation function for a Tetris player using the features of figure 3. We will begin by introducing briefly evolution strategies (ES), and the variant we use here: the covariance matrix adaptation evolution strategy (CMA-ES) [START_REF] Hansen | Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation[END_REF][START_REF] Hansen | Completely derandomized self-adaptation in evolution strategies[END_REF] and will then detail how we proceed to evolve artificial Tetris players.

The CMA evolution strategy

The covariance matrix adaptations evolution strategy is an evolutionary algorithm that operates in continuous search spaces, where the objective function f can be formulated as follows:

x = arg max x f (x) with f : IR n → IR.
It can be thought of as continuously updating a search point m ∈ IR n that is the centroid of a normally distributed population. The progress of the search point controls how the search distribution is updated over time to help the convergence of the algorithm.

Algorithm 1 describes the general procedure of CMA-ES. At each iteration, the algorithm samples λ points (the offspring) from the current distribution (line 5) :

x t+1 i ∼ m t + σ t z t i and z t i ∼ N (0, C t ) (i = 1 • • • λ),
where C t is the covariance matrix and σ > 0 is a global step-size. The µ ≤ λ best of the sampled points (the parents) are recombined by a weighted average (line 11) where

w 1 ≥ • • • ≥ w µ > 0 and µ i=0 w i = 1 to produce the new centroid m t+1 . Algorithm 1 Procedure (µ/µ, λ)-CMA-ES Require: (λ, m, σ, f , n) 1: Begin 2: µ := ⌊λ/2⌋, m 0 := m, σ 0 := σ, C 0 := I, t := 1, p 0 c = p 0 σ = 0 3: repeat 4:
for i := 1 to λ do 5:

z t i ∼ N i (0, C t )
x i := m t + σ t × z t i 7: f (x i ) := eval(x i ) 8:
end for 9:

m t+1 := µ i=1 w i x i:λ {Recombine µ best offspring, f (x 1:λ ) ≤ . . . ≤ f (x µ:λ )} 10: p t+1 σ := (1 -c σ ) p t σ + c σ (2 -c σ ) µ ef f (C t ) 1 2 m t+1 -m t σ t
{Update σ} 11:

σ t+1 := σ t exp cσ dσ p t+1 σ IE[ N (0,I) ] - 1
12:

p t+1 c := (1 -c c )p t c + c c (2 -c c ) µ co m t+1 -m t σ t
{Update C} 13:

C t+1 := (1 -c co ) C t + cco µco p t+1 c p t+1 c T + c co 1 -1 µco µ i=1 w i (z t i:λ ) (z t i:λ ) T 14:
t := t + 1 15: until stopping_criterion 16: return m t 17: End Adaptation of the search distribution in CMA-ES takes place in two steps, first updating the mutation step and then updating the covariance matrix. The step-size adaptation is performed using a cumulative step-size adaptation [START_REF] Ostermeier | A derandomized approach to self-adaptation of evolution strategies[END_REF], where the evolution path accumulates an exponentially fading path 5 of the mean m t (line 13) where the backward time horizon is determined by c -1 σ . The adaptation of the covariance matrix C t takes into account the change of the mean (rank-1 update), and the successful variations in the last generation (rank-µ update) (respectively lines 16 and 17). An in depth discussion on setting the parameters c σ , d σ , c c , µ ef f , µ co , c co and their recommended values can be found in [START_REF] Hansen | A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion[END_REF].

Some considerations

An important aspect of using evolutionary computation in problem solving is to gather as much information about the problem as possible to have some insight on the shape of the search space, exploit it and tune the algorithm to perform better. In the following we give some ideas about the shape of the search space we are addressing.

Weights normalization

Since the evaluation function (equation 2) is a linear combination, let us consider two actions a 1 and a 2 to place a piece p in state s such that V (s

1 = γ(s, a 1 (p)) > V (s 2 = γ(s, a 2 (p)). Then n i=1 w i f i (s 1 ) > n i=1 w i f i (s 2
). If we view w i and f i (•) as the coordinate of vectors w and f (•), we have w•f (s 1 ) > w•f (s 2 ) where "•" denotes the dot product. Let ŵ = w w , then

w ŵ•f (s 1 ) > w ŵ•f (s 2 ) or ŵ • f (s 1 ) > ŵ • f (s 2 )
. This shows that multiplying a weight vector by a constant will not change the ranking of the decisions. In other words, all vectors c × w, with c constant are equivalent with respect to the decisions of the player. This is important to consider since it states that all the points of the search space that fall on the n dimensional line passing through w will have the same fitness value. This phenomenon may reduce the performance of an evolutionary strategy that bases the adaptation of the step size and the adaptation of the covariance matrix on the progress of the search points, using path accumulation.

Experiments show that in this case the step sizes do not converge and keep increasing, which suggests that the algorithm is following an unattainable moving target. This behavior is illustrated on figure 4 where both the coordinate-wise step sizes and the solution (m t ) diverge.

One way, that we propose, to avoid such a behavior, is to add a slight modification to the algorithm to limit the search to weight vectors of unit length thus bounding the search space to the surface of the unit hyper-cube. After the sampling step (line 5 of algorithm 1), the vectors are normalized. Our experiments show that this procedure significantly improves the convergence of the algorithm.

Fitness landscape

One other feature of the search space worth mentioning is linked to the score distribution of a Tetris player. As stated above, the score of a Tetris player follows an exponential distribution. As a consequence, each point of the fitness landscape is a random variable. On stochastic objective functions, the fitness values of each individual follow a usually unknown distribution. On such problems, one cannot rely on a single evaluation of the offspring which is usually not a reliable measure, but needs to make several ones and compute statistics to estimate the true fitness.

In algorithms that rely only on the ranking of the population, as it is the case for CMA-ES, ranking based on fitness values is not appropriate if the variability of the values is not taken into account. In such cases the ranking may not be correct and may lead to poorly selected parents.

There is a thriving literature on methods to tackle these class of fitness landscapes [START_REF] Yaochu | Evolutionary optimization in uncertain environments-a survey[END_REF]. For example [START_REF] Hansen | A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion[END_REF] proposes UH-CMA-ES which, among other things, increases the population variance when a change in the ranking of the population is detected i.e. when noise is detected. Others [START_REF] Stagge | Averaging efficiently in the presence of noise[END_REF][START_REF] Schmidt | Integrating techniques from statistical ranking into evolutionary algorithms[END_REF] proposed methods to reduce the number of evaluations applicable when the distribution of the noise in the fitness function is of a particular type.

In section 5, we will describe more elaborate methods to reduce the number of evaluations, for the time being we will present a simple version of the learning strategy that estimates the fitness by averaging over fixed number of evaluations.

A candidate solution is evaluated (line 6 of the algorithm1) by playing a certain number of games and its fitness value is the average score. Furthermore, since selection is based on ranking, if the offspring plays different games their ranking may be flawed. In order to provide a coherent ranking of the offspring, we evaluate them on the same series of games. At each iteration, a series of independent games (random seeds) are drawn randomly and each individual of the λ offspring plays the same games. This way we can assess of the offspring's performance on the same setting.

Illustrative experiments

The experiments we conducted are divided in two parts: a learning phase and an evaluation phase. In the learning phase, the weights of the player's strategy are learned using CMA-ES. The player's strategy is then evaluated on a series of games which assess its performance. The games were simulated on the MDPTeris platform 6 . All the expriments were repeated 50 times and the curves represent median values.

Before going into further details, we begin by discussing the score distribution of the game of Tetris. Due to the stochastic nature of the game, the score histogram of an artificial player using a fixed strategy follows an exponential distribution. This observation was confirmed experimentally by [START_REF] Szita | Learning tetris using the noisy cross-entropy method[END_REF] where the authors argue that this distribution is an exponential distribution with 0.95 probability. Furthermore [START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF] extends the analysis and derives a way to compute confidence intervals of the empirical average score of the player:

|µ -μ| μ ≤ 2 √ N
where μ is the average score of the player, µ is the expected score and N is the number of games on which we average. Therefore when we compute the average score over 100 games, the confidence intervals is ±20% with probability 0.95. This is important for the remaining, since comparing different players solely on their average score does not make sense if they fall within the same confidence intervals. In the remaining, all the scores presented are the average of 100 games and thus have to be considered within 20%, unless otherwise stated.

In our experiments, a learning episode goes as follows: starting with a zero vector (m 0 = 0) and given an initial step size (typically σ 0 = 0.5), we run the algorithm for a fixed number of generations, in the presented experiments 50 iterations. At the end of one run we record the mean vector produced and we repeat this procedure for a certain number of times typically 20, thus ending with 20 mean vectors. Finally, the average of these mean vectors is the player's strategy we evaluate.

This experimental protocol is different from what is generally used in the literature. Often authors choose the best vector of one run as the player's strategy, which in our sense is not reliable due the nature of the score distribution. In our experiment, the fitness of each individual is the average of 100 games. As it is shown on the left of Figure 5 the fitness of the mean and the best individual fall within the 20% confidence interval. Furthermore, using our experimental protocol enables to reproduce experiments. Figures 5 and6 illustrate the behavior of the algorithm during a typical learning session. On the left of Figure 5 is given the fitness of the centroid (mean) of the population with the fitness of the best search point. The left hand side of Figure 5 shows also the evolution of the step size (σ). A decreasing value shows that the algorithm reduces its steps as it approaches the optimum, which suggests that the adaptation procedure works. This can be further supported by Figure 6, on which the eigenvalues of the covariance matrix also converge as do the coordinate-wise standard deviations.

Comments

Lastly, the right part of Figure 5 illustrates the evolution of the centroid of the population, each curve corresponds to a weight of the player's strategy. Most of the weights stabilize except for 4 and 5 (at the bottom of the curve) which seem to follow the opposite path, when one increases the other decreases and vice versa. This behavior is under investigation.

The results presented in Table 1 summarize the scores of players obtained using CMA-ES on Dellacherie's features [START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF] and Thiery's [START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF] features. As explained in section 4.3, these players are the mean of the weights vectors obtained by running 20 times CMA-ES. The scores are compared with the scores of the hand fixed weights from [START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF] obtained on the simulator we used, and the scores reported by [START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF]. As we can see on Table 1, the player learned on CMA-ES performs better than the player using hand fixed weights on both games sizes. On the other hand, it performs equivalently with the one learned on NCE, the average score is higher on the 10×20 game however it falls within the same confidence interval.

Similarly, NCE scores higher on the 10×16 game, but taking into account the confidence interval the scores are equivalent.

When the game size is small enough, an optimal policy may be computed. This has been done by Thiery and Scherrer [32] on the board of size 5×5 using the value iteration algorithm. On this configuration, they reported a mean score of 13.8±0.6% lines measured over 10 5 games. Interestingly we observe a similar average score (13.83974) on the controller learned on this game configuration. This suggest that players learned by CMA-ES are very close to the optimal player on the board of size 5×5. Using Dellacherie's features we obtain slightly lower average scores (13.2959).

Tetris is hard to learn !

Although a fascinating research question, designing artificial players for the game of Tetris can be a frustrating experience. This is due to different facts of the game. For instance, evaluating a decent player can take many hours on a modern computer which makes experiments on methods that rely on extensive evaluations such as evolutionary computation very time consuming. Furthermore, when candidate players learn better strategies throughout their evolution, the games last longer. On good players like the ones we present here, learning can last weeks on a state of the art desktop computer. Therefore the sensible thing which many authors often do is to adapt their algorithms to reduce the evaluation time.

One way to do so, is to reduce the number of games the player plays during the evaluation step. This however is not desirable since the estimation of the fitness of the player is less accurate. There are few methods to reduce the length of the evaluation time. In the following, we describe two, which helped us reduce drastically the length of our experiments. The first method changes the rules of the game to make it harder to play which consequently pushes the players to loose faster thus reducing the length of the evaluations. The second method reduces the number of games played such that only the necessary number of games for an accurate evaluation is played. Incidentally, both these methods can be combined.

Reducing the game length

To reduce the length of the games some authors have reduced the board size. When the board is smaller, the player looses faster. For example Böhm et al. [START_REF] Böhm | An Evolutionary Approach to Tetris[END_REF] evaluated players on games of size 6 × 12 during the learning process. Doing so reduces significantly the learning time however, our experiments showed that players learned on smaller game sizes do not scale up with others learned on larger ones.

We compared two players, one learned on a 10 × 20 game and the other on a 6 × 12 game. When tested on a 10 × 20 game, the one that learned on this game size performs better (36.3 ×10 6 versus 17 ×10 6 ). We drew the same observation for other smaller size except for 10 × 16 where the players seem to perform similarly. We think that learning on smaller games may specialize the players for that game size and does not enable them to generalize to larger games.

Rather than learning on smaller games, we propose a different approach to shorten the evaluation time, let the player learn on "harder games" of size 10 × 20. These games can be obtained by increasing the probability at which "Z" and "S" pieces appear (figure 1). These pieces are the hardest to place and are the ones that push the player to produce many holes in the board. Increasing their probabilities reduces the game length significantly and the learning time on a 10 × 20 game drops from months to hours.

Table 2 summarizes the scores of players learned on smaller games (size 6 × 12) and players learned on harder games (probability 3 11 for "Z" and "S") on games of size 10 × 16 and 10 × 20. The results show that a better way to reduce the learning time is to increase the probability of "Z" and "S" pieces.

Reducing the number of evaluation

As we argued in section 4.2.2, evaluating the offspring population should be done on multiple games since the fitness function follows an exponential distribution. However, in this case the evaluation time of the population is increased and can lead to long experiments. In this section we describe how to reduce significantly the number of evaluations needed to evaluate the fitness of the population while preserving the accuracy of the population ranking.

In order to reduce the number of re-evaluations, we need to disregard all those that are not necessary and that do not improve the information we have on the offspring fitness. In other words reevaluations are not wasted on poorly performing individuals once these are detected.

One way to perform this is to take into account confidence bounds around the estimated fitness value using racing methods [START_REF] Maron | Hoeffding races: Accelerating model selection search for classification and function approximation[END_REF][START_REF] Audibert | Tuning bandit algorithms in stochastic environments[END_REF][START_REF] Maron | The racing algorithm: Model selection for lazy learners[END_REF]. These methods adapt the number of evaluations dynamically until the algorithm reaches a reliable ranking in the population. [START_REF] Heidrich-Meisner | Hoeffding and bernstein races for selecting policies in evolutionary direct policy search[END_REF] proposed to use such methods on evolution strategies and reported some success on different machine learning problems. These methods reevaluate only individuals that are statistically indistinguishable from each other i.e. individuals whose confidence intervals (CI) around the mean fitness overlap.

Reevaluation in this case is used to reduce the confidence intervals. Once enough individuals with non overlapping intervals are found, the procedure stops. When the distribution of the fitness function is not known, this confidence intervals are computed using empirical methods using for example Hoeffding or Bernstein bounds which will be described below.

Computing confidence bounds

The racing procedure we propose to use is inspired from [START_REF] Heidrich-Meisner | Hoeffding and bernstein races for selecting policies in evolutionary direct policy search[END_REF]. At each iteration of Algo 1, the λ offspring undergo multiple evaluations until either : 1) µ outstanding individuals get out of the race, in which case we are sure (with probability (1δ)) that they are distinct. Or 2) the number of evaluations reaches some upper limit r limit in which case the evaluation budget is exhausted. Furthermore, the upper bound r limit is adjusted by the algorithm. If the actual number of evaluations necessary to distinguish µ individuals is less than the limit r limit , this one is reduced:

r limit := max(1/α r limit , 3) (3)
with α > 1, and 3 is the minimum number of evaluations. On the other hand if r limit evaluations where not enough to distinguish µ individuals, then r limit is increased:

r limit := min(α r limit , r max ) (4)
where r max is a maximum number of evaluations. Initially r limit = 3 and it is adapted at each iteration of Algo 1 using the above two rules.

After r re-evaluations, the empirical bounds c i,r around the mean fitness of each individual Xi,r = 1 r r j=1 f j (x i ) where i = 1 . . . λ, are computed with:

c h i,r = R log (2n b ) -log (δ) 2r (5)
using the Hoeffding bound and

c b i,r = σi,r 2 log (3n b ) -log (δ) r + 3R log (3n b ) -log (δ) r (6)
using Bernstein.

Where n b ≤ λr limit is the number of evaluations in the current race, σ2

i,r = 1 r r j=1 f j (x i ) -Xi,r 2
is the standard deviation of the fitness for individual x i , and (1δ) is the level of confidence we fix. R = |a -b| such that the fitness values of the offspring are almost surely between a and b. These two constants are problem dependent.

After each evaluation in the race the lower bounds lb i,r and the upper bounds ub i,r around the mean of each offspring are updated to the tightest values:

lb i,r = max lb i,r-1 , Xi,r -c h/b i,r and
ub i,r = min lb i,r-1 , Xi,r + c h/b i,r
Beside the above empirical bounds, there exists for the game of Tetris estimated bounds on the mean score of the player [START_REF] Thiery | Building Controllers for Tetris[END_REF] which we also used in the racing procedure. We have:

|X -X|/ X ≤ 2/ √ n (7)
with probability 0.95, where X is the average score of the player on n games and X is the expected score.

In the remainder we will refer to this bound as the Tetris bound.

Illustrative experiments

In the following, we present few experiments in different settings to compare the effect of the racing procedures described above and a version that does not use racing as well. In all experiments the initial search point x 0 was drawn randomly with x 0 = 1 and the initial step-size σ 0 = 0.5. We let the algorithm run for 25 iterations (improvements for larger values were not noticeable), we set r max = 100 and δ = 0.05. As in the previous section there are eight feature functions in the evaluation function therefore the dimension of the search space is n = 8. CMA-ES parameters c σ , d σ , c c , µ ef f , µ co and c co were set to their default values as presented in [START_REF] Hansen | A method for handling uncertainty in evolutionary optimization with an application to feedback control of combustion[END_REF].

In order to reduce the learning time, we adopt the same scheme as presented above and evaluate the offspring on harder games, in which "S" and "Z" appear four times more frequently than in the standard game.

The algorithm maximizes the score of the game i.e. the fitness function is the average of lines scored by a search point on a number of games. When racing is applied, this number of games can go from 3 to r max . When it is not applied, it is r max . The initial bounds a and b used to compute R (eq. 6) were fixed experimentally to a = 150 and b = 2000.

Finally, as described in the previous section, offspring are normalized and at each iteration a series of r max independent games (random seeds) are drawn randomly such that each individual of the λ offspring plays the same series of games.

Comments

The effect of racing is clear on the learning time of the algorithm. The number of evaluations is indeed reduced without a loss of performance. Figure 7 on the right shows the fitness function of the mean vector (the centroid of the distribution) for the different racing procedures and without racing. All algorithms reach the same performance at different evaluation costs. Hoeffding bounds perform the best, reaching the performance for the smallest evaluation time, followed by Tetris bounds and Bernstein. Figure 7 on the left shows the median rate of evaluations (r limit being 100%) used in the races. With Tetris bounds this number of evaluations is reduced at the beginning of the learning process and increases towards the end reaching r limit . For Hoeffding bounds the number of evaluations oscillates between r limit and lower values. Finally, Bernstein bounds were not efficient compared to Hoeffding bounds, the number of evaluations is not reduced and at each race each individual is evaluated r limit times. This is due to the fact that the standard deviation of the fitness is of the same order of its average. This is the case for Tetris, the standard deviation of the score distribution is almost equal to its mean. In other words σ i,t is large compared to R in equation 6. When this is the case, Hoeffding bounds are tighter than Bernstein's, and this is the case in all our experiments.

Recall that r limit is adapted using equations 3 and 4 and is initially set to 3, which explains why in the right of Figure 7, Bernstein races used less evaluations than in the case without racing.

We noticed also that there is a large variability in the racing procedure. Figure 8 shows the rate of evaluation out of r limit of all 50 runs for Hoeffding and Tetris bounds. It is interesting to notice that the racing procedures reduce the number of evaluations early in the process and do not perform as well at the end. At this stage the racing procedure cannot distinguish between the offspring and selection is made only based on the fitness values (averaged over the r limit reevaluation).

The CI around the offspring's fitness overlap indicating that they perform equally well. This also suggests (see below) that the ranking of the offspring might not be correct. Incidentally, this corresponds to the time where the convergence of step-sizes start to "flatten" (Figures 10 and11).

The effect of the population size on the racing procedure can be seen on Figure 9 where is shown the number of evaluations out of r limit for different population sizes. Apparently increasing the population size reduces the number of evaluations within the race using Hoeffding bounds. On the other hand the opposite can be seen when using Tetris bounds.

Furthermore the population size does not effect the performance of the algorithms, the median value of the mean vector fitness reaches similar values for different population sizes. This is the case for both Tetris and Hoeffding bounds (figures 10 and 11).

Figure 12 shows the effect of the confidence value on the evaluation time. It presents four setting with different confidence (1δ) levels. Using Hoeffding bounds, if we reduce the confidence value the algorithm stops earlier. This is the expected behavior: reducing the confidence reduces the bounds and races are decided faster. On the other hand, Bernstein bounds are not affected at all. The races are not able to distinguish statistical differences between the offspring even with low confidence values.

In order to assess the results of the racing procedure, we test the learned players on a standard game 7 and compare the scores with previously published scores. We follow the same scheme as in Sec. 4.3 to construct the player. We record the last mean vector m t of each run of the algorithm and compute the mean of all these vectors (in our setting 50). This is merely a convention and others are possible 8 . The score of a player is the average score on 100 games. Taking into account variability of the score distribution, a confidence bound of ±20% is to be taken into account (see equation 7).

Further thoughts and considerations

One other aspect we are interested in is the nature of the learned weight vectors and consequently the strategies. Surprisingly, we notice that even thought the search space (fitness function) is noisy, which suggests a hard optimization problem, the learned vectors throughout different independent experiments seem close to each other. In other words the algorithm converges toward the "same" region of the search space. This is more noticeable in the case of features f 1 . . . f 6 than for the case of features f 1 . . . f 8 . and the hand fixed weights by Dellacherie [START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF]. On the right, features functions f 1...8 and the weights given by [START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF] learned using NCE Figure 13 shows a series of learned vectors produced by 20 independent runs using box and whiskers plot. In the case of the feature set f 1 . . . f 8 the quartiles are larger, which suggests that the corresponding weights did not converge. This said, the average vector (the solid line) for which the score is given in Table 1 performs well.

Furthermore, even though both feature sets share features f 1 . . . f 6 , the learned weights for these features do not converge to the same values in both experiments. This behavior suggests that features f 7 and f 8 conflicts somehow with f 4 and f 5 . This is purely speculative since these features measure different things, however this phenomenon should be further investigated.

If we compare the learned vectors with the vectors provided by Dellacherie [START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF] and Thiery [START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF], we notice that on some features our vectors have similar weights. Although we cannot compare directly these vectors since they were produced using different experimental protocols 9 . However, on the one hand this observation further supports our previous argument stating that the search space may not be extremely multimodal 10 . On the other hand, it was interesting to realize that some of the weights our vectors learned are close to the weights that an expert has fixed by hand. Though our player performs better than his when tested (table 1), the major differences in the weights resides in features f 4 and f 5 that Dellacherie weights respectively higher and lower than CMA-ES. The same conclusion can be drawn from Figure 13 between the weights learned using CMA-ES and NCE, on which they seem very close.

Finally, if we consider values of the weights obtained we notice that the algorithm produces a "sensible" playing strategy. It minimizes the landing height (f 1 ), the number of transitions from filled to empty vertically and horizontally (f 3 , f 4 ), the number of holes (f 5 ) and the number of rows with holes (f 8 ). It also minimizes the depth of the wells (f 6 ) and the depth of the holes (f 7 ). The only feature that is maximized is the number of eroded pieces (f 2 ) which is directly related to the number of lines scored. Furthermore, features f 4 and f 8 were considered by the algorithm as more important than the others without considering f 2 .

Conclusions

The game of Tetris is probably among the few games that are popular worldwide and designing artificial players is a very challenging question. Our aim in this paper is to show that evolutionary computation can be applied to design good strategies for the game of Tetris that can compete with the best reported players. The player strategy uses a feature-based game evaluation function to evaluate the best moves for a given state and which is optimized using the CMA evolution strategy.

We have shown that by analyzing the shape of the search space, we were able to adapt the algorithm to converge better in this particular case. We also discuss how to reduce the length of the games which serves greatly when running lengthy learning algorithms. The racing procedures presented allow to learn very good player at a fraction of the learning cost.

We think that designing good artificial players should not rely only in optimizing the weights of a set of features, but also in choosing good feature functions. In fact our different experiments showed us that for the feature set presented here, we have probably obtained the best player and further improvements will not be significant if we take into account confidence intervals. Improvements could be achieved using better feature functions, ones that synthesize the game better. An interesting research question would be to devise algorithms to learn new feature functions rather than only learn the weights.

Figure 3 :

 3 Figure 3: Features functions. (f 1 ) Landing height: the height at which the current piece fell (8 in the figure). (f 2 ) Eroded pieces: the contribution of the last piece to the cleared lines time the number of cleared lines (2 × 2 in the figure). (f 3 ) Row transitions: number of filled cells adjacent to empty cells summed over all rows (58 in the figure). (f 4 ) Column transition: same as (f 3 ) summed over all columns (45 in the figure) note that borders count as filled cells. (f 5 ) Number of holes: the number of empty cells with at least one filled cell above. (f 6 ) Cumulative wells: the sum of the accumulated depths of the wells ((1 + 2 + 3) + 1 + 1 on the figure). (f 7 ) Hole depth: the number of filled cells above holes summed over all columns. (f 8 ) Row hole: the number of rows that contains at least one hole (8 in the figure).

Figure 4 :

 4 Figure 4: Divergence of the coordinate-wise step sizes in log-scale (left) and the solution variables (right). Typical run without normalization.

Figure 5 :Figure 6 :

 56 Figure 5: (Left) Fitness of the centroid (m), the best search point (x 1:λ ) and the step size (σ) scaled up by 10 3 to fit on the figure. (Right) Weights of the features function (components of mean vector m)

Figure 7 :

 7 Figure 7: On the left, the number of evaluations with racing using different bounds versus iterations. On the right, log of the fitness of the mean vector m t versus the number of evaluations. Median values over 50 runs.

Figure 8 :

 8 Figure 8: The number of evaluations for 50 runs thick line represent the median value. With Hoeffding races (left). Races with Tetris bounds(right).

Figure 9 :

 9 Figure 9: The median number of evaluations over 50 runs for different population sizes. Using Hoeffding races (left). Using Tetris bounds (right)

Figure 10 :

 10 Figure 10: CMA-ES and Tetris bounds with multiple population sizes. Log of the fitness of the mean vector m t (left) and the step-size σ (right). Median values over 50 runs.

Figure 11 :

 11 Figure 11: CMA-ES and Hoeffding races with multiple population sizes. Log of the fitness of the mean vector m t (left) and the step-size σ (right). Median values over 50 runs.

Figure 12 :

 12 Figure 12: Log of the fitness of the population centroid for different confidence values. Hoeffding races (left) and Bernstein races (right). Median values over 50 runs.

Figure 13 :

 13 Figure 13: The learned weights of 20 independent runs of CMA-ES. On the left, features functions f 1...6and the hand fixed weights by Dellacherie[START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF]. On the right, features functions f 1...8 and the weights given by[START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF] learned using NCE

Table 1 :

 1 Scores of the players obtained by the CMA-ES.

		CMA-ES	[11]		[33]
	Size	f 1...6	f 1...8	f 1...6	f 1...6	f 1...8
	10×16 4.7×10 5	8.7×10 5 2.5×10 5 5.3×10 5 9.1×10 5
	10×20 16.6×10 6 36.3×10 6 6.6×10 6 17×10 6	35×10 6

Table 2 :

 2 Learning on smaller vs. learning on harder games.

	Game size Smaller games Harder games
	10 × 16 10 × 20	8.79×10 5 17×10 6	8.7×10 5 36.3×10 6

One of the theorems in the paper states that maximizing the number of rows cleared in a Tetris game is NP-complete

The actual number of possible actions may depend on the shape of the current pieces and the size of the game.

To be more precise their artificial player does not use an evaluation function, the evolved programs use strategies of their own discovered through evolution.

For one empty square surrounded by filled squares, the value of the frontier is 4.

The comparison of the travelled path with a path under random selection is used to adjust the step-size.

MDPTetris is available at http://mdptetris.gforge.inria.fr

A game of size 10 × 20 with all seven pieces equally probable.

One could also choose the best performing vector out of the whole set. However testing them all on a reasonable number of games might be long. For example testing one player on 10 games took 15 hours on a 2 Ghz CPU.

Recall that our vectors are averaged over several runs (section 4.3) which is not the case for[START_REF] Thiery | Construction d'un joueur artificiel pour tetris[END_REF] and also not the case for[START_REF] Fahey | Tetris AI, Computer plays Tetris[END_REF] since they were fixed by hand

This argument may only be valid for these sets of features.


Omar Hazem Mohammed

Yassine Amirat

Mohamed Benbouzid

Tianhao Tang

Hybrid Generation Systems Planning Expansion Forecast: A Critical State of the Art Review

Keywords: Hybrid energy systems, renewable power generation, generation systems planning expansion, generation unit sizing, energy cost, power generation economics

In recent years the electric power generation has entered into a new development era, which can be described mainly by increasing concerns about climate change, through the energy transition from hydrocarbon to clean energy resources. In order to power system enhance reliability, efficiency and safety, renewable and nonrenewable resources are integrated together to configure so-called hybrid systems. Despite the experience accumulated in the power networks, designing hybrid system is a complex task. It has become more challenging as far as most renewable energy resources are random and weather/climatic conditions-dependant.

In this challenging context, this paper proposes a critical state-of-the-art review of hybrid generation systems planning expansion and indexes multi-objective methods as strategies for hybrid energy systems optimal design to satisfy technical and economical constraints.

I. INTRODUCTION

In the last ten years production of electric power has significantly increased due to the increased load demand. World statistics indicate that the coming years will see a significant increase in power consumption, which requires the search for energy extra sources that should be of eco-friendly nature (i.e. renewable energies). Although renewable energy penetration in electricity is expected to have a spectacular growth in the forthcoming years, it still however has very low participation rate compared to other nonrenewable energies (Fig. 1) [1].

Renewable energies, such as solar, wind, marine, hydropower, geothermal, and biomass constitute a type of distributed electricity resources and have recently received much attention as alternatives for electricity generation. O.H. Mohammed and M.E.H Benbouzid are with the University of Brest, EA 4325 LBMS, Rue de Kergoat, CS 93837, 29238 Brest, France (e-mail: Omar-Hazem-Mohammed.Mohammed@univ-brest.fr, Mohamed.Benbouzid@univ-brest.fr).

Y. Amirat is with ISEN, EA 4325 LBMS, 20, Rue Cuirassé Bretagne, 29200 Brest, France (e-mail: Yassine.Amirat@isen.fr).

T. Tang is with the Shanghai Maritime University, Department of Electrical Automation, 201306 Shanghai, China (email: thtang@shmtu.edu.cn).

They supply now somewhere between 15 to 20% of the world total energy demand. Many studies have investigated the potential contribution of renewables to global energy supplies, indicating that in the second half of the 21 st century their contribution might range from the present figure of nearly 20% to more than 50% with the right policies in place: About of 30% contribution to world energy supply from renewable energy sources by year 2020 as proposed in [START_REF] Akella | Social economical and environmental impacts of renewable energy systems[END_REF].

The main problems with the use of renewable energies have always been how to tap efficiently on the sources and produce sufficient energy for the load demand. Indeed, the energy production using renewable energy sources is often highly dependent on weather and nature conditions. For example, not all climates are suitable for tapping on solar energy; they are more suited for areas near the equator where energy from the sun is accessible all year round. Winds do not blow all the time during these periods. Wind farm turbines would therefore be left idle. To solve this problem and to enhance the energy system reliability, these generation unit should be working together in two or more sources in the so-called hybrid system concept. Hybrid power station concept is not new, but has gained popularity and rapid development in the recent year. There are many types of hybrid energy systems including renewable and nonrenewable sources that have been considered (Fig. 2). Indeed, they offer an alternative and emerging solution for areas where there are substantial resources, leading to a best electricity generating opportunities [START_REF] Nehrir | A review of hybrid renewable/alternative energy systems for electric power generation: Configurations, control, and applications[END_REF]. The main hybrid energy system layout use diversified renewable resources such as: In this important energy context, this paper is therefore intended as a comprehensive critical state-of-the-art review. In particular, it will deal with a comparative study of methods carried-out to forecast Generation Expansion Planning (GEP) for small stand-alone power systems and general power grid. The GEP problem is an important issue for decision makers in power utilities. Indeed, GEP specifies optimal sizing schemes, placement, and investments dynamics on generation units to meet the expected energy demand over long-term horizon. The GEP problem is well-known to be a constrained, nonlinear, and discrete optimization problem. Moreover, it inherently involves multiple, conflicting, and incommensurate objectives that should be considered simultaneously [START_REF] Aghaei | Integrated renewable-conventional generation expansion planning using multiobjective framework[END_REF].

II. HYBRID GENERATION EXPANSION PLANNING METHODS

The methods behind Hybrid Generation Expansion Planning (HGEP), for small autonomous and utility grid power systems, can be classified into three main categories, namely: Reliability analysis; Optimization; and Enumeration.

A. Reliability Analysis

Reliability analysis gathers all the constraints and limitations that are applied and developed in power systems the design to ensure balance between power source and load.

There are many factors for reliability evaluation that are linked to the probability for imbalance between electricity supply and load. The main factors are the LPSP (Loss of Power Supply Probability), the ELF (Equivalent Loss Factor), the LOLP (Loss of Load Probability), and the LCE (Levelized Cost of Energy) model [START_REF] Abbes | Eco-design optimisation of an autonomous hybrid wind-photovoltaic system with battery storage[END_REF][START_REF] Erdinc | Optimum design of hybrid renewable energy systems: Overview of different approaches[END_REF].

B. Optimization

It consists of methods for the objective function representation in optimization equations that use a set of algorithmic steps. As example, for a wind/PV hybrid system optimal sizing and operation, many parameters are considered: wind turbine type, wind turbine capacity, PV panels best tilt angle, etc. Moreover, the followings could also be considered: minimizing the generation system annualized cost (capital cost, replacement cost, operation, and maintenance cost), reduce the fuel consumption while retaining the reliability requirement and CO 2 emission limit, etc. [START_REF] Arabali | Genetic-algorithm-based optimization approach for energy management[END_REF][START_REF] Luna-Rubio | Optimal sizing of renewable hybrids energy systems: A review of methodologies[END_REF].

C. Enumeration

Enumeration method and programming algorithm considers various types of techniques to solve the objective function and expansion policy for a given period. There are many computational methods and algorithms to achieve the optimized solution [START_REF] Pourmousavi | Real-time energy management of a stand-alone hybrid wind-microturbine system using particle swarm optimization[END_REF][START_REF] Yuan | Optimal operation strategy of energy storage unit in wind power integration based on stochastic programming[END_REF][START_REF] Thounthong | Intelligent model-based control of a standalone photovoltaic/fuel cell power plant with supercapacitor energy storage[END_REF].

III. HYBRID GENERATION SYSTEMS OPTIMIZATION MODEL

Figure 3 illustrates hybrid generation system energy sources diversity. Indeed, it is clearly shown that there are many hybrid possibilities depending on the available renewable energy sources (i.e. solar, wind, etc.), as well as near or beyond the grid region. In addition to this diversity, there is also power system goals diversity such as size optimization, total coat reduction, gaseous emission reduction, etc.

Hybrid generation system optimization general model is illustrated by Fig. 4. This model show that the objective function mainly depends the system building purposes (i.e. optimal sizing, optimal operation, fuel consumption reduction, etc.). As shown in Fig. 3, a typical hybrid generation system comprises different power sources or units. These power units have different impacts on cost, environment, and reliability. In a hybrid generation system, they are integrated together and complement one another in order to serve the load while satisfying certain economic, environmental, and reliability criteria. The hybrid system can be operated autonomously or connected to the utility grid whose power is from the conventional fossil fuel-fired generators. The optimum design of hybrid generation systems is related to the determination of the optimal configuration of the power system and optimal location, type and sizing of generation units, so that the system meets load requirements, while subjected to physical and operational constraints/strategies [START_REF] Erdinc | Optimum design of hybrid renewable energy systems: Overview of different approaches[END_REF], [START_REF] Wang | Modern Power System Planning[END_REF][START_REF] Wang | Multicriteria design of hybrid power generation systems based on a modified particle swarm optimization algorithm[END_REF].

A. Objective Function

Hybrid generation systems design can be evaluated through its lifetime cost and emission. The lifetime cost typically consists of Capital Cost (CC) and Maintenance Cost (MC), together referred to as the fixed cost; in addition to the operational cost. The optimal hybrid generation system therefore seeks a combination of generator types and sizes that result in the lowest lifetime cost and/or emission. Among all possible hybrid system configurations that are optimally dispatched, the configuration with the lowest Net Present Cost (NPC) is supposed to be the optimal configuration or the optimal design [START_REF] Erdinc | Optimum design of hybrid renewable energy systems: Overview of different approaches[END_REF].

( )

1 ( , ) L i i i i i i NPC N CC RC K MC PWA ir R = = + × + × ∑ (1)
Where L is the hybrid source number, N i is the number of each hybrid energy source, and RC is the replacement cost. K i allows converting replacement cost to present as

1 2 1 1 (1 ) l i nl n K ir = = + ∑ (2)
where l 1 and l 2 are the hybrid unit replacement time and lifespan, respectively (for sources, that lifespan is equal to the project one, K i = 0), ir the interest rate (sometimes considered equal to 0.05 or 0.06). PWA is used to convert operation and maintenance annual costs to present as

(1 ) 1 ( , ) (1 )
R R ir PWA ir R ir ir

+ - = + ( 3
)
where R is hybrid power system lifespan. The optimization methods aim is therefore minimizing the NPC objective function.

B. Reliability Analysis

Owing to the intermittence of renewable energy sources, power system reliability is considered as an important step in the hybrid power system design process. Power system reliability concept is extremely broad and covers the system ability aspects to satisfy load requirements. There is a reasonable subdivision of the concern designated as system reliability, which is represents two basic aspects of a power system: system adequacy and security.

Reliability analyses generally involve LPSP, LOLP, and ELF, which implies the probability for imbalance between electricity supply and load [START_REF] Billinton | Reliability Evaluation of Power Systems[END_REF][START_REF] Hong | Optimal sizing of hybrid wind/PV/Diesel generation in a stand-alone power system using Markov-based genetic algorithm[END_REF][START_REF] Katsigiannis | A novel colored fluid stochastic Petri net simulation model for reliability evaluation of wind/PV/Diesel small isolated power systems[END_REF].

1) LPSP. The most used approach to the application of LPSP in a hybrid system design uses probabilistic techniques to integrate the fluctuating nature of the resource and the load. LPSP, is in this case described by

( ) 0 Time ( ) ( ) T available needed t P t P t LPSP T = < = ∑ (4)
Where T is hours number (with hourly weather input).

The power deficit time is defined as the time where the load demand is not satisfied by renewable energy sources and the storage is depleted (battery state of charge SOC falls below the allowed value SOC min = 1 -DOD, where DOD is the depth of discharge).

The needed power by the load side can be expressed as

= + + + + ′ ⎡ ⎤ - ′ × = ⎢ ⎥ Δ Δ ⎢ ⎥ ⎣ ⎦ ( 6
)
where C is a constant (0 for a battery charging process and 1 for the discharging process), C' bat is the available or practical battery capacity, and

SOC(t) is ( ) ( 1) ( ) 1 24 bat bat bat I t t t SOC t SOC t C Δ η σΔ ⎛ ⎞ + = - + ⎜ ⎟ ′ ⎝ ⎠ (7)
σ is the self-discharge rate that depends on the accumulated charge and the battery state of health [START_REF] Guasch | Dynamic battery model for photovoltaic applications[END_REF].

2) LOLP. It is a basis for accurate and consistent reliability evaluation of hybrid power systems, where component failure and load demand are stochastic in nature [START_REF] Karki | Reliability/cost implications of PV and wind energy utilization in small isolated power systems[END_REF][START_REF] Billinton | Capacity expansion of small isolated power systems using PV and wind energy[END_REF]. Hybrid renewable energy systems reliability analysis uses a capacity outage probability table, which is an array of capacity levels and the associated existence probabilities. This is achieved by combining the generating unit availability and unavailability using probability basic concepts. From the individual probability table, a cumulative probability one is derived. Figure 5, schematically shows the basic elements used to assed power generation adequacy [START_REF] Huang | An efficient probabilistic assessment method for electricity market risk management[END_REF].

A hybrid power system is considered to operate successfully as long as it has enough generating capacity to provide the load demand. The cumulative probability of a particular capacity outage state of X-MW after adding a 2-state unit of capacity C-MW with a forced outage rate γ is given as [START_REF] Billinton | Capacity expansion of small isolated power systems using PV and wind energy[END_REF], [START_REF] Narasimhan | A fuzzy-based approach for generation system reliability evaluation[END_REF] Generation ( )

'( ) 1 '( ) '( ) P X P X P X C = -γ + γ - (8)
where P'(X) and P(X) denote the cumulative probabilities of the capacity outage state of X-MW before and after the unit is added. P(X) is also the capacity outage probability being greater or equal to X. The above expression is initialized by setting 1 for 0 '( ) 0 otherwise

X P X ≤ ⎧ = ⎨ ⎩
and the forced outage rate γ is given by Forced outage (hours) Forced outage (hours) in service hours γ =

Equation ( 8) can be modified to include multi-state unit representations.

( ) ( )

n i i i P X pP X C = ′ = - ∑ ( 10
)
Where n is the unit states number, C i is state i capacity outage for the unit being added, and p i is unit state i existence probability [START_REF] Billinton | Capacity expansion of small isolated power systems using PV and wind energy[END_REF], [START_REF] Narasimhan | A fuzzy-based approach for generation system reliability evaluation[END_REF] (1 )

n Z n Z i Z k n p Z - = ⎛ ⎞ = γ -γ ⎜ ⎟ ⎝ ⎠ ∑ ( 11
)
where k is the required units minimum number and

! ( )! ! n n Z n Z Z ⎛ ⎞ = ⎜ ⎟ - × ⎝ ⎠ (12)
The overall probability that the load demand will not be met, which is LOLP (loss of load probability on hour j for state i) is finally given by ( )

n i j i r k LOLP p P L C = = > ∑ (13)
where L j is the forecast peak load on hour j and P is the loss of load probability on hour j.

3) ELF. It is the ratio of the effective forced outage hours to the total number of hours [START_REF] Garcia | A Wind-Diesel system with hydrogen storage: Joint optimization of design and dispatch[END_REF].

1 1 () ( ) H i Q i ELF H D i = = ∑ (14)
Where Q the loss of load, D is the load demand, and H is the time step number. The ELF contains information about both the number of outages and their magnitude.

C. Enumeration Methods

There are many approaches to provide the above discussed optimal design criteria. Several approaches have been used for hybrid power systems optimal design; such as: linear programming [START_REF] Garcia | A Wind-Diesel system with hydrogen storage: Joint optimization of design and dispatch[END_REF], evolutionary algorithms [START_REF] Conti | Optimal dispatching of distributed generators and storage systems for MV islanded microgrids[END_REF], Artificial Neural Networks (ANN) [START_REF] Chaouachi | Multiobjective intelligent energy management for a microgrid[END_REF][START_REF] Yuan | Optimal operation strategy of energy storage unit in wind power integration based on stochastic programming[END_REF], Fuzzy Logic (FL) [START_REF] Thounthong | Intelligent model-based control of a standalone photovoltaic/fuel cell power plant with supercapacitor energy storage[END_REF], [START_REF] Narasimhan | A fuzzy-based approach for generation system reliability evaluation[END_REF], [START_REF] Chaouachi | Multiobjective intelligent energy management for a microgrid[END_REF], simplex algorithm, dynamic programming, stochastic approach [START_REF] Yuan | Optimal operation strategy of energy storage unit in wind power integration based on stochastic programming[END_REF] [START_REF] Yuan | Optimal operation strategy of energy storage unit in wind power integration based on stochastic programming[END_REF], iterative and probabilistic approaches [START_REF] Huang | An efficient probabilistic assessment method for electricity market risk management[END_REF], design space based approach, parametric and numerical approaches, response surface methodology, matrix approach, and quasi-Newton algorithm [START_REF] Erdinc | Optimum design of hybrid renewable energy systems: Overview of different approaches[END_REF], [START_REF] Luna-Rubio | Optimal sizing of renewable hybrids energy systems: A review of methodologies[END_REF].

For sizing hybrid renewable energy systems, it has been particularly proposed the so-called methaheuristic methods that include Genetic Algorithms (GAs) [START_REF] Arabali | Genetic-algorithm-based optimization approach for energy management[END_REF], [START_REF] Hong | Optimal sizing of hybrid wind/PV/Diesel generation in a stand-alone power system using Markov-based genetic algorithm[END_REF], [START_REF] Yuan | Optimal operation strategy of energy storage unit in wind power integration based on stochastic programming[END_REF][START_REF] Katsigiannis | Multiobjective genetic algorithm solution to the optimum economic and environmental performance problem of small autonomous hybrid power systems with renewables[END_REF], Simulated Annealing (SA) [START_REF] Katsigiannis | Hybrid simulated annealing-Tabu search method for optimal sizing of autonomous power systems with renewables[END_REF], Tabu Search (TS) [START_REF] Katsigiannis | Hybrid simulated annealing-Tabu search method for optimal sizing of autonomous power systems with renewables[END_REF], and Particle Swarm Optimization (PSO) among others [START_REF] Pourmousavi | Real-time energy management of a stand-alone hybrid wind-microturbine system using particle swarm optimization[END_REF], [START_REF] Wang | Multicriteria design of hybrid power generation systems based on a modified particle swarm optimization algorithm[END_REF]. Metaheuristics orchestrate an interaction between local improvement procedures and higher-level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space.

In addition to the above popular optimization techniques, some promising techniques have been recently indexed for future use in hybrid system sizing; among them: Ant Colony Optimization (ACO) [START_REF] Kannan | Application and comparison of metaheuristic techniques to generation expansion planning problem[END_REF], Artificial Immune System (AIS) [START_REF] Ahuja | An AIS-ACO hybrid approach for multi-objective distribution system reconfiguration[END_REF], Artificial Bee Colony (ABC) [START_REF] Nasiraghdam | Optimal hybrid PV/WT/FC sizing and distribution system reconfiguration using multi-objective artificial bee colony (MOABC) algorithm[END_REF].

Each sizing methodology has its own features and the recently proposed new methodologies have potential for future use to reach a techno-economically optimum hybrid renewable energy system.

IV. HYBRID POWER SYSTEMS SAMPLE APPLICATIONS

To illustrate the above presented techniques and methods, Table 1 shows a brief evaluation of the above presented hybrid renewable energy systems sizing approaches in relevant selected literature. This brief presentation clearly illustrate that selection of the suitable approach may change due to the application type, user requirements, etc. However, it is suggested that metaheuristics are particularly well-adapted for HGEP problem.

V. CONCLUSION

Hybrid renewable power generation systems optimal design is a very challenging task as far as most renewable energy resources are random and weather/climatic conditionsdependant. In this challenging context, this paper has attempted to propose a state-of-the art review that should help in the optimal design of hybrid generation systems to satisfy technical and economical constraints.

LCE, sensitive analysis

Hybrid SA and TS [START_REF] Kannan | Application and comparison of metaheuristic techniques to generation expansion planning problem[END_REF] GEP problem Investment and operation cost minimization under constraints LOLP Metaheuristics comparison: GA, PSO, SI, TS, ACO, etc.

[30] Wind turbine, PV, fuel cell Multi objective optimization: total power loss, total electrical energy cost, and total produced emission minimization, and voltage stability index maximization.

LCE

Multi objective ABC [START_REF] Santarelli | Mathematical optimization of a RES-H2 Plant using a black box algorithm[END_REF] PV, Micro hydro turbine, fuel cell Optimal economic analysis and design, optimal sizing minimum investment cost

Black box algorithm constraints

Black box algorithm in the basic Downhill Simplex method [START_REF] Halamay | Reserve requirement impacts of large-scale integration of wind, solar, and ocean wave power generation[END_REF] Wind turbine, PV, marine turbine Optimal sizing , optimal combination, optimal operation Timescales for reserve requirements, forecasting Interaction analysis between the variability characteristics of the utility load, wind power generation, solar power generation, and ocean wave power generation.

[33] Utility grid, wind turbine, PV, marine turbine Renewable energy sources optimal mixture, optimal control and stability Limitations and constraints built-on in largescale integration program Administration of large-scale integration

Fig. 1 .

 1 Fig. 1. World electricity energy generation [© IEA].

  (1) Diesel, wind turbine, storage battery; (2) Diesel wind turbine, photovoltaic, storage battery; (3) Hydro generation, wind turbine, photovoltaic, storage battery; (4) Wind turbine, marine turbine, photovoltaic, storage battery; (5) Wind turbine, photovoltaic, multi-storage energy; and (6) other configurations that uses classical gas turbine and furl cells.

Fig. 2 .

 2 Fig. 2. Hybrid generation systems general architecture.

Fig. 3 .

 3 Fig. 3. General hybrid power system configuration.

Fig. 4 .

 4 Fig. 4. Hybrid generation system optimization general model.

Fig. 5 .

 5 Fig. 5. Generation reliability evaluation basic elements.

Table 1 .

 1 Brief comparison of some main approaches applied for the sizing of hybrid renewable energy systems.

	Optimization Approaches		Linear programming, FL		Sequential Quadratic Programming and	multi objective programming		PSO		GA, Markov model, FL, stochastic	programming	GA, ANN	Multi objective GA
	Reliability Technique		LCE		LPSP	LCE, LOLP, and LOLF (Loss of Load	Frequency)		LOLP and CO2 constraints		LCE	LCE
	Objective Function	Multiple objectives (i.e. minimization of total costs,	emissions, energy consumption and portfolio investment	risk as well as system reliability maximization)	Satisfy energy requirements with lowest environmental	impact	Power balance constraint, design variable bounds,	optimal energy management, optimal cost, technical	constraints	Optimal sizing, optimal economic analysis, optimal	operation control, optimal annualized cost, reduce fuel	consumption and CO2 emission	Decrease the bid imbalance, ESU optimal operation	Cost minimization, minimization of total greenhouse gas	emissions of the system during its lifetime	Cost minimization, optimal design
	Hybrid Sources		GEP problem		Diesel, wind turbine, PV, battery	Utility grid, wind turbine, PV, micro	turbine, battery	Diesel, wind turbine, PV, battery or	multi-storage energy	Large scale wind farm, energy	storage unit ESU)	Diesel, different renewable sources	Diesel, wind turbine, PV, biodiesel	generator, battery
	Ref.		[4]		[5]	[9],	[13]		[15]		[25]	[26]	[27]


Yassine Amirat
email: yassine.amirat@isen.fr

Mohamed E H Benbouzid
email: mohamed.benbouzid@univ-brest.fr

Tianzhen Wang
email: tzwang@shmtu.edu.cn

Sylvie Turri
email: sylvie.turri@univ-brest.fr

Smart Grid Voltage Sag Detection using Instantaneous Features Extraction

Keywords: Smart grid, voltage sag detection, power quality (PQ), Hilbert Transform (HT), ensemble empirical mode decomposition (EEMD)

Smart grids have initiated a radical reappraisal of distribution networks function where the integration of renewable energy sources, load demand control, and effective use of the network are indexed as the most important keys for smart grid expansion and deployment regardless each country policies. One of the most efficient ways of effective use of these grids would be to continuously monitor their conditions. This allows for early detection of power quality degeneration facilitating therefore a proactive response, prevent a fault ride-through the renewable power sources, minimizing downtime, and maximizing productivity.

In this smart grid context, this paper proposes the evaluation and comparison of advanced signal processing tools, namely the Hilbert transform and the ensemble empirical mode decomposition method for the detection of voltage sags as they are the most commonly encountered power quality disturbances.

I. INTRODUCTION

Renewable energy conversion systems are the fastestgrowing sources of new electric generation in the world and it is expected to remain so for sometimes. These systems offer an alternative and emerging solution by deploying hybrid power plant offshore or onshore, where there are substantial renewable resources, leading to a best electricity generating opportunities. With the deployment of distributed renewable power generation; the electricity networks are undergoing wholesale changes both from generation and users sides because the power flow is becoming bidirectional and the users are playing an active role in managing their demand for electricity [START_REF] Brown | Smart grid policies: an international review[END_REF]. Despite accumulated experienced in the conventional electric distribution networks, the task of distributed networks is still an art. It has become more challenging as far as the generation system is moved nearby the distribution level and this is achieved by using a set of micro grids and energy islands based on renewable sources, connected to the main grid as illustrated in Fig. 1 [START_REF] Simões | A comparison of smart grid technologies and progresses in Europe and the US[END_REF][START_REF] Glinkowski | Advances in wind energy technologies in the context of smart grid[END_REF].

The philosophy of smart grids is giving the distribution network more flexibility by rending it able to meet the power demand needs and have islanding fast capabilities when a fault occurs such as voltage sags or power outage. So, key considerations when deploying smart grids are their availability, reliability, and profitability; in order to fulfill power demand according to PQ standards. In this context, voltage sags automated detection is indexed as an essential requirement for a condition monitoring system in order to meet PQ standards [START_REF] Gómez-Lázaro | Characterization and visualization of voltage dips in wind power installations[END_REF][START_REF] Ignatova | Space vector method for voltage dips and swells analysis[END_REF]. Since smart grids are a collection of diverse set of power generation sources, including large power plants and distributed generation sources, energy storage systems, it is then difficult to deal with such a complex system through conventional procedures used in classical distribution networks particularly during faults and system emergencies.

It is therefore obvious that real-time monitoring and remote control is a key issue that needs to be addressed to make a grid more intelligent and self-healing. This requires much more sophisticated computer-oriented monitoring than in a classical grid [START_REF] Simões | A comparison of smart grid technologies and progresses in Europe and the US[END_REF]. In this context, signal processing is certain to play a significant role in dealing with the complexity and uncertainty associated with a smart grid [START_REF] Xia | Adaptative frequency estimation in smart grid applications[END_REF].

For voltage sag detection, there is a wide range of technology and methods derived from contemporary power systems [START_REF] Fitzer | Voltage sag detection technique for a dynamic voltage restorer[END_REF][START_REF] Mcbee | Utilizing a smart grid monitoring system to improve voltage quality of customers[END_REF][START_REF] Milioudis | Enhanced protection scheme for smart grids using power line communications techniques-Part I: Detection of high impedance fault occurrence[END_REF][START_REF] Milioudis | Enhanced protection scheme for smart grids using power line communications techniques-Part II: Location of high impedance fault position[END_REF]. These methods are based on electrical quantity signatures analysis (current, voltage, power, etc.). Indeed, those quantities are easily accessible or evaluated during operation. Electrical quantities analysis usually involves the use of reference frame transformations such as Park's vector [START_REF] Orcajo | Diagnosis of electrical distribution network short circuits based on voltage Park's vector[END_REF] or three-phase system symmetrical components or space vector [START_REF] Ignatova | Space vector method for voltage dips and swells analysis[END_REF], and other techniques based upon them. These techniques however assume that voltage and current quantities are pure sine waves, while in real-world the electrical quantities are polluted by harmonics produced by power electronic devices in both sides of the smart grid, and transient spikes due to grid apparatus maneuvers. It is therefore obvious the Fast Fourier Transform (FFT), and other techniques based upon it, are no longer valid even they has been used in some cases [START_REF] Fitzer | Voltage sag detection technique for a dynamic voltage restorer[END_REF]. Advanced signal processing techniques are therefore required to deal with the complexity and uncertainty associated with a smart grid. In [START_REF] Kamwa | Robust Detection and analysis of power system oscillation using Teager-Kaiser energy Operator[END_REF], a Teager-Kaiser energy operator has been proposed for power system oscillations detection and analysis. However, this operator is highly affected by noises. In [START_REF] Labos | Application of wavelets and Prony method for disturbance detection in fixed speed wind farms[END_REF], wavelets and Prony method were used. Wavelets however require properly windowed disturbing events, to ensure accurate computations. Moreover, Prony method highly depends on the system parameters and operating modes. As voltage sags lead to transient phenomena (voltage unbalance and voltage/current waveform disturbances) [START_REF] Muscas | Power quality monitoring in modern electric distribution systems[END_REF], it seems that the focus should be on transient signal processing techniques. In this disturbing and transient context, it is therefore proposed to assess and to compare two advanced non stationary signal processing techniques: Hilbert transform and the ensemble empirical mode decomposition method. In particular, distinct features will be extracted from the instantaneous power for voltage sags detection and characterization [START_REF] Ozgonenel | A new classification for power quality events in distribution systems[END_REF][START_REF] Amirat | A smart grid voltage sag detector using an EEMD-based approach[END_REF].

II. VOLTAGE SAGS CHARACTERIZATION

Voltage sags are indexed as the most important power quality issue. They are a transient deviation of the RMS supply voltage from a reference value with typical dip depths ranging from 0.9 to 0.5 pu of a 1 pu nominal [START_REF] Fitzer | Voltage sag detection technique for a dynamic voltage restorer[END_REF]; lasting from few milliseconds to few cycles; caused by abrupt increases in loads such as phase to phase or phase to ground short circuits, they are also caused by abrupt increases in source impedance, typically caused by a loose connection [START_REF] Muscas | Power quality monitoring in modern electric distribution systems[END_REF].

The most usual voltage sags signatures are depicted in Fig. 2 [START_REF] Ignatova | Space vector method for voltage dips and swells analysis[END_REF]. During a voltage sag three-phase system balanced conditions are no longer valid leading to possible disastrous consequences on the user end-loads and on the smart grid itself.

Voltage sag characterization concerns events quantification through a limited number of parameters. These parameters depend on the field of study. However, main characterization methods use two parameters to determine the severity of a voltage sag: magnitude (or "remaining voltage") and duration [START_REF] Glinkowski | Advances in wind energy technologies in the context of smart grid[END_REF]. In the context of a smart grid, it is therefore important to know whether voltage sag exists and afterward estimate its duration. Figure 3 depicts the acquired voltage and currents when a fault occurs on a transmission line during a thunderstorm causing SARFI-70 sag [START_REF] Leborgne | Differences in voltage dip exposure depending upon phase-to-phase and phase-toneutral monitoring connections[END_REF].

Since voltage sags effect arises in voltages and currents, it seems more relevant to use the three-phase instantaneous power given by Fig. 3. Phase voltages, currents, and the total instantaneous power before, during and after voltage sag.

, , ( ) ( ) ( )

k k k a b c p t v ti t = = ∑ (1)
The instantaneous power depicted in Fig. 3 clearly show that, for voltage sags detection (occurrence time), it is more convenient to track the power Instantaneous Amplitude (IA). Estimating IA will therefore allow extracting statistical features for the fault characterization. In this context, there exist many IA estimation techniques in the literature and the most popular include Hilbert Transform (HT) [START_REF] Oppenheim | Discrete-Time Signal Processing[END_REF][START_REF] Amirat | Hilbert transform-based bearing failure detection in DFIG-based wind turbines[END_REF]. Furthermore for non stationary signals the Empirical Mode Decomposition (EMD) can be investigated as it is considered as one of the emerging methods for transient signal processing [START_REF] Lei | A review on empirical mode decomposition in fault diagnosis of rotating machinery[END_REF][START_REF] Amirat | Wind turbine bearing failure detection using generator stator current homopolar component ensemble empirical mode decomposition[END_REF].

Figure 4 is given to illustrate the adopted approach for feature extraction and therefore comparison of the two chosen techniques.

A. Hilbert Transform

Hilbert transform is used to estimate the instantaneous amplitude since it is usually more robust against noise than the Teager energy operator. The instantaneous power p(t) Discrete Hilbert Transform (DHT) is given by

[ ] { } { } 1 ( ) ( ) ( ) H F F p n u n p n - = (2)
where F{.} and F -1 {.} correspond to the FFT and Inverse FFT, respectively, and u(n) is defined as

1, 0, 2
( ) 2, 1, 2, ....., 1 2 0, 1, ..., 1 2 N n N u n n N n N ⎧ = ⎪ ⎪ ⎪ = = - ⎨ ⎪ ⎪ = + - ⎪ ⎩ (3)
and N is the data sample number.

Using (1), the instantaneous amplitude ˆ( ) p n is given by

2 2 ˆ( ) ( ) ( [ ( )]) p n p n H p n = + (4)
Figure 5 show therefore the instantaneous power and its instantaneous amplitude.

The shortest path to the IA information is the statistic variance σ 2 given by For voltage sags characterization, HT is carried-out during equal segments as depicted in Fig. 6. The achieved IAs for each segment are illustrated by Fig. 7 (for 70 samples of the instantaneous power). Since the 1 st segment is fault-free, all the other segments are therefore compared to it by computing the IA static variance ratio of each segment (i.e. 2, 3, …, 20) over the reference one. The achieved results are summarized in Table 1.

B. Ensemble Empirical Modal Decomposition

The EMD is an adaptive time-frequency data analysis method for nonlinear and non-stationary signals, and has focused considerable attention and has been indexed recently for power system fault detection and analysis [START_REF] Kamwa | Robust Detection and analysis of power system oscillation using Teager-Kaiser energy Operator[END_REF], [START_REF] Ozgonenel | A new classification for power quality events in distribution systems[END_REF]. Indeed and contrary to well-known decomposition techniques, EMD is intuitive and direct, with the basic functions based on and derived from the data. It is used to decompose the multicomponent signal into a series of IMFs based on the signal time-scale local characteristics. However, one major drawback of the EMD is the mode mixing. This phenomenon means that the detail related to one scale can appear in two different intrinsic modes. To overcome this drawback, the EEMD was introduced [START_REF] Lei | A review on empirical mode decomposition in fault diagnosis of rotating machinery[END_REF][START_REF] Amirat | Wind turbine bearing failure detection using generator stator current homopolar component ensemble empirical mode decomposition[END_REF]. The EEMD is described as a new noiseadded method, which mitigate automatically the EMD modemixing. It is described in the flowchart given in Fig. 8.

After decomposing the instantaneous power according to the EEMD algorithm, several IMFs were obtained. The most energized is the 4 th one. Figure 9 depicts then the instantaneous power and its 4 th IMF. In particular, it is clearly shown that this IMF is very sensitive to the voltage sag occurrence and its duration. This is confirmed when intrinsic modes decomposition is carried-out during the same abovedescribed 20 segments (for the 70 samples of the instantaneous power).

After the EEMD processing, the same statistical criterion is computed for the 4 th IMF for each segment. The achieved results are summarized in Table 2.

In order to have more readable information for comparison purposes, Tables 1 and2 are results are summarized in Fig. 11. According to the electrical quantities waveforms (Fig. 3), from the 2 nd to the 4 th segment, normal operation is confirmed by the variance reduced value, for both techniques. At a voltage sag occurrence (5 th segment), the criterion increases to 85 times for HT and to 132 times for EEMD; this means that both HT and EEMD are able to detect voltage sag occurrence. It should be noted that the EEMD seems slightly more sensitive the fault occurrence. Moreover, and for estimation of the voltage sag duration, it seems obvious that EEMD remains sensitive to the voltage sag (from segments 6 to 18).

From this brief comparative analysis, it seems that EEMD, using the instantaneous power 4 th IMF, could be considered as a reliable technique for voltage sag detection and characterization (occurrence and duration), using instantaneous power segmentation and a reduced set of sample.

IV. CONCLUSION

This paper dealt a comparative analysis of advanced signal processing tools, namely the Hilbert transform and the ensemble empirical mode decomposition method, for the detection of voltage sags, in this smart grid context. It has been proposed a specific features extraction approach using the instantaneous power as the prime variable. Indeed, it has been first sample in regular segment.

Instantaneous features are afterwards extracted through the Hilbert transform and the EEMD. It was therefore found that EEMD, using the instantaneous power 4 th IMF, is more fault-sensitive and could be considered as a reliable technique for voltage sag detection and then smart grid monitoring.

Fig. 1 .

 1 Fig. 1. A smart grid topology [© SAET].

Fig. 2 .

 2 Fig. 2. Voltage sag main signatures [5].

Fig. 4 .

 4 Fig. 4. Adopted approach for feature extraction.

Fig. 5 .

 5 Fig. 5. Instantaneous power and its amplitude before, during and after voltage sag.

Fig. 6 .

 6 Fig. 6. Instantaneous power segmentation.

Fig. 7 .

 7 Fig. 7. Instantaneous power IA in each segment.

Fig. 8 .

 8 Fig. 8. EEMD algorithm flowchart.

Fig. 9 .Fig. 10 .

 910 Fig. 9. Instantaneous power and its 4 th IMF before, during and after voltage sag.

Fig. 11 .

 11 Fig. 11. HT and EEMD voltage sag detection criterion comparison.

Table 1 .

 1 IA statistics for each segment.

	Segment	1	2	3	4	5
	2 2 1 th st σ i segment segment σ	1.000	0.903	0.925	0.978	85.223
	Segment	6	7	8	9	10
	2 2 1 th st σ i segment segment σ	5.210	0.604	0.538	0.241	0.451
	Segment	11	12	13	14	15
	2 2 1 th st σ i segment segment σ	0.186	4.418	6.636	3.522	2.285
	Segment	16	17	18	19	20
	2 2 1 th st σ i segment segment σ	1.071	0.664	0.809	0.5821	0.604

Table 2 .

 2 4 th IMF statistics for each segment.

	Segment	1	2	3	4	5
	2 2 1 th st σ i segment segment σ	1.0000	1.2687	5.0897	5.0476	132.446
	Segment	6	7	8	9	10
	2 2 1 th st σ i segment segment σ	64.6928	3.4446	1.5039	3.6355	31.211
	Segment	11	12	13	14	15
	2 2 1 th st σ i segment segment σ	1.6115	46.4227 48.2043 19.0097	0.178
	Segment	16	17	18	19	20
	2 2 1 th st σ i segment segment σ	16.4797	4.1726	8.2415	0.6626	0.392