Gabriela Ochoa

Automated Scheduling

Marco Tomassini
email: marco.tomassini@unil.ch

Seb Ástien V Érel

Christian Darabos
email: christian.darabos@unil.ch

A Study of NK Landscapes' Basins and Local Optima Networks

Keywords: I.2.8 [Artificial Intelligence]: Problem Solving, Control Methods, and Search-Heuristic methods; G.2.2 [Discrete Mathematics]: Graph Theory-Network problems Algorithms, Measurement, Performance Landscape Analysis, Network Analysis, Complex Networks, Local Optima, N K

. We use the well-known family of N K landscapes as an example. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We exhaustively extract such networks on representative small N K landscape instances, and show that they are 'small-worlds'. However, the maxima graphs are not random, since their clustering coefficients are much larger than those of corresponding random graphs. Furthermore, the degree distributions are close to exponential instead of Poissonian. We also describe the nature of the basins of attraction and their relationship with the local maxima network.

INTRODUCTION

A fitness landscape of a combinatorial problem can be seen as a graph whose vertices are the possible configurations. If two configurations can be transformed into each other by a suitable operator move, then we can trace an edge between them. The resulting graph, with an indication of the fitness at each vertex, is a representation of the given problem fitness landscape. Doye [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF][START_REF] Doye | Characterizing the network topology of the energy landscapes of atomic clusters[END_REF] has recently introduced a useful simplification of the fitness landscape graph for the energy landscapes of atomic clusters. The idea consists in taking as vertices of the graph not all the possible configurations, but only those that correspond to energy minima. For atomic clusters these are well-known, at least for relatively small assemblages. Two minima are considered connected, and thus an edge is traced between them, if the energy barrier separating them is sufficiently low. In this case there is a transition state, meaning that the system can jump from one minimum to the other by thermal fluctuations going through a saddle point in the energy hypersurface. The values of these activation energies are mostly known experimentally or can be determined by simulation. In this way, a network can be built which is called the "inherent structure" or "inherent network" in [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF]. We use a modification of this idea for studying the well-known N K combinatorial landscapes. In our case, a vertex of the graph is a local maximum, and there is an edge between two maxima if they lay on adjacent basins.

In the context of meta-heuristics, it is important to identify the features of landscapes that would influence the effectiveness of heuristic search. Such knowledge may be helpful for both predicting the performance and improving the design of meta-heuristics. Among the features of landscapes known to have a strong influence on heuristic search, is the number and distribution of local optima in the search space. An interesting property of combinatorial landscapes, which has been observed in many different studies, is that on average, local optima are very much closer to the global optimum than are randomly chosen points, and closer to each other than random points would be. In other words, the local optima are not randomly distributed, rather they tend to be clustered in a "central massif" (or "big valley" if we are minimising). This globally convex landscape structure has been observed in the N K family of landscapes [START_REF] Kauffman | The origins of order[END_REF], and in many combinatorial optimisation problems, such as the traveling salesman problem [START_REF] Boese | A new adaptive multi-start technique for combinatorial global optimizations[END_REF], graph bipartitioning [START_REF] Merz | Memetic algorithms and the fitness landscape of the graph bi-partitioning problem, Parallel Problem Solving from Nature V[END_REF], and flowshop scheduling [START_REF] Reeves | Landscapes, operators and heuristic search[END_REF].

In this study we seek to provide fundamental new insights into the structural organization of the local optima in combinatorial landscapes, particularly into the connectivity and characteristics of their basins of attraction, using N K landscapes as a case study. To achieve this, we first map the landscape onto a network, and then analyze the topology of this network for a number of small N K landscape instances for which complete networks can be obtained. Our analysis is inspired, in particular, by the work of Doye [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF][START_REF] Doye | Characterizing the network topology of the energy landscapes of atomic clusters[END_REF] on energy landscapes, and in general, by the field of complex networks [START_REF] Newman | The structure and function of complex networks[END_REF][START_REF] Watts | The "new" science of networks[END_REF][START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF]. The study of complex networks has already permeated the evolutionary computation field. Specifically, in the study of scientific collaborations [START_REF] Cotta | Where is evolutionary computation going? A temporal analysis of the EC community[END_REF][START_REF] Luthi | The genetic programming collaboration network and its communities, Genetic and Evolutionary Computation Conference[END_REF], the structure of a population in cellular evolutionary algorithms [START_REF] Giacobini | Effects of scale-free and small-world topologies on binary coded self-adaptive CEA[END_REF][START_REF] Giacobini | Takeover time curves in random and small-world structured populations[END_REF][START_REF] Payne | Takeover times on scale-free topologies[END_REF], and the evolution of networks of cellular automata [START_REF] Tomassini | Evolution of small-world networks of automata for computation[END_REF]. However, our study is the first attempt, to our knowledge, of using network analysis techniques in connection with the study of fitness landscapes and problem difficulty in combinatorial optimization.

The next section introduces the study of complex networks, and describes the main features of small-world and scale-free networks. Section 3 describes how landscapes are mapped onto networks, and includes the relevant definitions and algorithms. The empirical network analysis of our selected N K landscape instances is presented in Section 4, whilst Section 5 gives our conclusions and ideas for future work.

COMPLEX NETWORKS

The recent interest in the study of networks and networked systems was influenced by the seminal paper by Watts and Strogatz [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], who showed that many real-world networks are neither completely ordered nor completely random, but rather exhibit important properties of both. Some of these network properties can be quantified by simple statistics such as the clustering coefficient C, which is a measure of local density, and the average shortest path length l, which is a global measure of separation. It has been shown in recent years that many social, biological, and man-made system show what has been called a small-world topology [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], in which nodes are highly clustered yet the path length between them is small.

A second important aspect in the study of networks has been the realization that in many real-world networks, the distribution of the number of neighbours (the degree distribution) is typically right-skewed with a "heavy tail", meaning that most of the nodes have less-than-average degree whilst a small fractions of hubs have a large number of connections. These qualitative description can be described mathematically by a power-law [START_REF] Barabasi | Emergence of scaling in random networks[END_REF], which has the asymptotic form p(k) ∼ k -α . This means that the probability of a randomly chosen point having a degree k decays like a power of k, where the exponent α (typically in the range [START_REF] Boese | A new adaptive multi-start technique for combinatorial global optimizations[END_REF][START_REF] Cotta | Where is evolutionary computation going? A temporal analysis of the EC community[END_REF]) determines the rate of decay. A distinguishing feature of power-law distributions is that when plotted on a double logarithmic scale, a powerlaw appears as a straight line with negative slope α. This behavior contrasts with a normal distribution which would curve sharply on a log-log plot, such that the probability of a node having a degree greater than a certain "cutoff" value is nearly zero. The mean would then trivially represent a characteristic scale for the network degree distribution. Since networks with power-low degree distribution lack any such cutoff value, at least in theory, they are often called scale-free networks [START_REF] Watts | The "new" science of networks[END_REF]. Examples of such scale-free networks are the world-wide-web, the internet, scientific collaboration and citation networks, and biochemical networks.

LANDSCAPES AS NETWORKS

To model a physical energy landscape as a network, Doye [START_REF] Doye | Characterizing the network topology of the energy landscapes of atomic clusters[END_REF] needed to decide first on a definition both of a state of the system and how two states were connected. The states and their connections will then provide the nodes and edges of the network. For systems with continuous degrees of freedom, the author achieved this through the 'inherent structure' mapping [START_REF] Stillinger | A topographic view of supercooled liquids and glass formation[END_REF]. In this mapping each point in configuration space is associated with the minimum (or 'inherent structure') reached by following a steepest-descent path from that point. This mapping divides configuration into basins of attraction surrounding each minimum on the energy landscape.

We use a modification of this idea for the N K family of binary landscapes, which indeed can be applied to any combinatorial landscape. In our case, the vertexes of the graph are the local maxima of the landscape, obtained exhaustively by running a bestimprovement local search algorithm (see Algorithm 1) from every configuration of the search space. The edges in the network connect local optima of adjacent basins of attraction. An illustration for a model 2D landscape can be seen in Figure 1, which is inspired by a similar figure appearing in [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF][START_REF] Doye | Characterizing the network topology of the energy landscapes of atomic clusters[END_REF]. Here, we illustrate a network of local maxima (instead of local minima). A more formal definition of our inherent networks is given in Section 3.1. As it was the case in the study on physical energy landscapes [START_REF] Doye | Characterizing the network topology of the energy landscapes of atomic clusters[END_REF], we do not consider multiple edges, or weights in the edges. This may be a factor to consider in future work. Note that while a physical energy landscape is formally a continuous landscape, ours are strictly combinatorial, i.e. discrete and finite. Moreover, the energy landscape of a stable atomic cluster, crystal or molecule is relatively smooth and easy to search and has been called a "funnel" landscape [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF]. In contrast, in N K landscapes one can continuously vary the intrinsic landscape difficulty by changing the value of K. As a result, we shall see that N K landscapes show a number of different behaviors depending on K for a given N , and these different behaviors are reflected on their inherent networks. Indeed, N K landscapes can be seen as analogous to those of spin-glasses [START_REF] Kauffman | The origins of order[END_REF][START_REF] Stein | Disordered sytems: mostly spin glasses[END_REF]. In contrast to atomic cluster energy landscapes, spin glass landscapes may show frustration, i.e. configurations that must respect conflicting constraints, and solving for the ground state of the system that is, the minimum energy configuration is an NP-hard problem. Similar consequences are caused by the introduction of epistatic interactions through the increase of the K value in N K landscapes.

Below we present the relevant formal definitions and algorithms to obtain our combinatorial analogous of an energy landscape inherent network.

Definitions and Algorithms

Definition : Fitness landscape. A landscape is a triplet (S, V, f ) where S is a set of potential solutions i.e. a search space, V : S -→ 2 S , a neighborhood structure, is a function that assigns to every s ∈ S a set of neighbours V (s), and f : S -→ R is a fitness function that can be pictured as the height of the corresponding potential solutions.

In our study, the search space is composed by binary strings of length N , therefore its size is 2 N . The neighborhood is defined by the minimum possible move on a binary search space, that is, the 1-move or bit-flip operation. In consequence, for any given string s of length N , the neighborhood size is |V (s)| = N . Notice that in N K landscapes, two neighboring solutions never have the same fitness value. Therefore, neutrality is not present. Landscapes with neutrality will be considered in future work.

Definition:

Local Optimum. A local optimum is a solution s * such that ∀s ∈ V (s * ), f (s) < f (s * ).
The LocalSearch algorithm to determine the local optima and therefore define the basins of attraction, is given below:

Algorithm 1: LocalSearch Choose initial solution s ∈ S repeat choose s ′ ∈ V (s) such that f (s ′ ) = max x∈V(s) f (x) if f (s) < f (s ′ ) then s ← s ′ end if until s is a Local optimum
The LocalSearch algorithm defines a mapping from the search space S to the set of locally optimal solutions S * . We therefore define a basin of attraction as follows:

Definition : Basin of attraction. The basin of attraction of a local optimum i is the set bi = {s ∈ S | LocalSearch(s) = i}. The size of the basin of attraction of a local optima i is the cardinality of bi.

We then define the inherent network, or network of local optima as:

Definition : Local optima network. The local optima network G = (S * , E) is the graph where the nodes are the local optima, and there is an edge eij ∈ E between two local optima i and j if there is at least a pair of direct neighbors (1-bit apart) si and sj, such that si ∈ bi and sj ∈ bj. That is, if there exists a pair of direct neighbors solutions si and sj, one in each basin (bi and bj)

EMPIRICAL NETWORK ANALYSIS

Experimental Setting

The N K family of landscapes [START_REF] Kauffman | The origins of order[END_REF] is a problem-independent model for constructing multimodal landscapes that can gradually be tuned from smooth to rugged. In the model, N refers to the number of (binary) genes in the genotype (i.e. the string length) and K to the number of genes that influence a particular gene. By increasing the value of K from 0 to N -1, N K landscapes can be tuned from smooth to rugged. The k variables that form the context of the fitness contribution of gene si can be chosen according to different models. The two most widely studied models are the random neighborhood model, where the k variables are chosen randomly according to a uniform distribution among the n -1 variables other than si, and the adjacent neighborhood model, in which the k variables that are closest to si in a total ordering s1, s2, . . . , sn (using periodic boundaries). No significant differences between the two models were found in [START_REF] Kauffman | The origins of order[END_REF] in terms of global properties of the respective families of landscapes, such as mean number of local optima or autocorrelation length. Therefore, we explore here the adjacent neighborhood model, leaving the random model for future analysis.

In order to avoid sampling problems that could bias the results, we used the largest values of N that can still be analyzed exhaustively with reasonable computational resources. We thus extracted the local optima networks of landscape instances with N = 16, 18, and K = 2, 4, 6, ..., N -2, N -1. For each pair of N and K values, 30 instances were explored. Therefore, the networks statistics reported below represent the average behaviour of 30 independent instances.

General Network Statistics

Table 1 reports the average of the network properties measured on N K landscapes for N = 16, 18 and all even K values; K = N -1 is also given. Values are averages over 30 randomly generated landscapes. nv and ne are, respectively, the mean number of vertices and the mean number of edges of the graph for a given K rounded to the next integer. C is the average of the mean clustering coefficients 1 over all the generated landscapes. Cr is the average clustering coefficient of a random graph with the same number of vertices and mean degree. z is the average of the mean degrees. l is the average of the mean path lengths over all landscape instances. The last column contains the average degree assortativity coefficient ā, which measures whether nodes with similar degrees tend to pair up with each other. The assortativity coefficient is computed according to [START_REF] Newman | The structure and function of complex networks[END_REF].

Notice that the mean number of vertexes (nv) confirms that the number of local optima (and thus the search difficulty) increases with the value of K. Some other interesting inferences can be drawn from these metrics. First of all, looking at the l values one can conclude that the maxima networks are small worlds for all values of K since the growth of l is bounded by a function O(log nv). In a sense, this is not surprising as the whole configuration space spans the binary hypercube {0, 1} N of degree N with 2 N vertices, which has maximum distance (diameter) d = log2 N , i.e. 16 and 18 for our studied instances. However, while the base configuration space has constant degree for any node, the maxima network are degree-inhomogeneous (see next section) and have clustering coefficients well above those of equivalent random graphs, showing that there is local structure in the networks. For both N = 16 and 18, the mean degree z first increases with K and then goes down again for K > 8. The assortativity coefficients are always very small which means that there is almost no correlation between the degrees of neighboring nodes. For easy energy landscapes, Doye found that the networks were slightly disassortative [START_REF] Doye | Characterizing the network topology of the energy landscapes of atomic clusters[END_REF].

Degree Distributions

The degree distribution function p(k) of a graph represents the probability that a randomly chosen node has degree k [START_REF] Newman | The structure and function of complex networks[END_REF]. Random graphs are characterized by a p(k) of Poissonian form, while 1 The clustering coefficient Ci of a node i is defined as Ci = 2Ei/ki(ki -1), where Ei is the number of edges in the neighborhood of i. Thus Ci measures the amount of "cliquishness" of the neighborhood of node i and it characterizes the extent to which nodes adjacent to node i are connected to each other. The clustering coefficient of the graph is simply the average over all nodes:

C = 1 N N i=1 Ci [14].
Table 1: Network properties of N K landscapes for N = 16, 18 and all even K values; K = N -1 is also given. Values are averages over 30 randomly generated landscapes, standard deviations are shown as subscripts. nv and ne represent the number of vertexes and edges (rounded to the next integer), C, the mean clustering coefficient, whilst Cr is the clustering coefficient of a random graph with the same number of vertexes and mean degree, which is Cr ≃ z/nv. z represent the mean degree, l the mean path length , and ā the degree assortativity coefficient. social and technological real networks often show long tails to the right, i.e. there are nodes that have an unusually large number of neighbors. Sometimes this behavior can be described by a powerlaw, but often the distribution is less extreme and can be fitted by a stretched exponential or by an exponentially truncated powerlaw [START_REF] Newman | The structure and function of complex networks[END_REF].

Figure 2 shows all the curves for 30 randomly generated landscapes for N = 16 and K = 4, 10, whilst figure 3 does the same for N = 18. To smooth out fluctuations in the high degree region, the cumulative degree distribution function is plotted, which is just the probability that the degree is greater than or equal to k. The sin-gle curves are shown rather than the average curve because the sum of a sufficient number of independent random variables with arbitrary distributions, provided that the first few moments exist and are finite, tends to distribute normally according to a general formulation of the central limit theorem [START_REF] Feller | An introduction to probability theory and its applications[END_REF]. In other words, if the average of the sum were plotted, the original shapes would essentially be lost. The curves cannot be described by power-laws: this possibility is ruled out by the left parts of figs. 2, and 3 which are double logarithmic plots. In log-log plots, power laws should appear as straight lines, at least for a sizable part of abscissae range.

On the other hand, the right images in the same figures show that the distributions can be fitted approximately by exponentials of the type p(k) = (1/z)e -k/z where z is the mean degree, as most curves are approximately straight lines on these linear-log plots. This is true for the larger part of the degree range. When we approach the finite degree cutoff the fit is obviously less good. Small networks such as those with N = 16 and K = 4 show larger fluctuations and their tails decay faster than exponentially. Two particular examples with a medium value of K (K = 8) are shown in detail in fig. 4, together with an exponential fit. Table 2 gives the parameters of the regression lines for all N and K values. If we compare these results with Doye's [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF][START_REF] Doye | Characterizing the network topology of the energy landscapes of atomic clusters[END_REF] the most important difference is that we do not observe power-law distributions. Indeed, power-law degree distributions of the inherent energy landscape networks point to the "easiness" of those landscapes: due to the presence of highly connected nodes, which are also among the fittest, a simple gradient-descent would bring a searcher down to a local energy minimum, often the global one, starting anywhere in the configuration space. In other words, there exist the "funnel" effect described by Doye [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF]. In contrast, N K landscapes have tunable difficulty. How can random networks with exponential degree distributions be obtained? One way is the following: in each time step, just add a new node, and add a new link between two randomly chosen nodes, including the new one. Iterating this dynamical process produces graphs with an exponential distribution of the node degrees [START_REF] Dorogovtsev | Evolution of networks[END_REF]. But N K landscapes are static and thus it is difficult to see how this process could be implemented. However, the following qualitative explanation might help. Imagine that K is increased from 2 to N -1 in single steps. Then we could have the image of the previous landscape increasing its size and deforming itself when K goes from its current value to K + 1. The new maxima that appear could be considered as if they were added dynamically (of course some previous optima might disappear as well). Edges in the new landscape are selected essentially randomly, with more probability of selecting an already existing node. Thus, with this imaginary mechanism a distribution close to exponential would be obtained.

Thus, as the N K landscape difficulty varies smoothly when K is increased, the degree distribution of the corresponding maxima networks remains essentially exponential. We do not observe scalefree distributions for the easy landscapes as in the energy landscape case [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF]. This is understandable: standard energy landscapes in molecular chemistry and crystal physics do correspond to thermodynamically stable states which are naturally smooth and easy to reach when the system is forming or it is slightly perturbed. In contrast, N K landscape are synthetic and do not correspond to any physical principle in their construction. The only physical systems that resemble N K landscapes are spin glasses, in which conflicting energy minimization requirements lead to frustration and to landscape ruggedness [START_REF] Kauffman | The origins of order[END_REF][START_REF] Stein | Disordered sytems: mostly spin glasses[END_REF]. However, disordered condensed matter systems similar to spin glasses are only obtained in particular situations, for instance by fast cooling [START_REF] Stein | Disordered sytems: mostly spin glasses[END_REF].

Basins of Attraction

Besides the maxima network, it is useful to describe the associated basins of attraction as these play a key role in search algorithms. Furthermore, some characteristics of the basins can be related to the network features described above. The notion of the basin of attraction of a local maximum has been presented in sect. 3.1. We have exhaustively computed the size and number of all the basins of attraction for N = 16 and N = 18 and for all even K values plus K = N -1. In this section, we analyze the basins of attraction from several points of view as it is described below.

Global optimum basin size vs. K

In Figure 5 we plot the average size of the basin corresponding to the global maximum for N = 16 and N = 18, and all values of K studied. The trend is clear: the basin shrinks very quickly with increasing K. This confirms that the higher the K value, the more difficult for an stochastic search algorithm to locate the basin of attraction of the global optimum

Number of basins of a given size

Figure 6 shows the cumulative distribution of the number of basins of a given size (with regression line) for two representative instances with K = 4 and N = 16 (top) and N = 18. Table 3 shows the average (of 30 independent landscapes) correlation coefficients and linear regression coefficients (intercept ( ᾱ) and slope ( β)) between the number of nodes and the basin sizes. Notice that distribution decays exponentially or faster for the lower K and it is closer to exponential for the higher K. This observation is relevant to theoretical studies that estimate the size of attraction basins (see for example [START_REF] Garnier | Efficiency of local search with multiple local optima[END_REF]). These studies often assume that the basin sizes are uniformly distributed. From the slopes β of the regression lines (table 3) one can see that high values of K give rise to steeper distributions (higher β values). This indicates that there are less basins of large size for large values of K. In consequence, basins are broader for low values of K, which is consistent with the fact that those landscapes are smoother.

Fitness local optima vs. their basin sizes

The scatter-plots in figure 7 illustrate the correlation between the basin sizes of local maxima (in logarithmic scale) and their fitness values. Two representative instances for N = 18 and K = 4,8 are shown. Table 4 shows the averages (of 30 independent landscapes) of the correlation coefficient, and the linear regression coefficients between these two metrics (maxima fitness and their basin sizes). All the studied landscapes for N = 16 and 18, are reported. Notice that, there is a clear positive correlation between the fitness values of maxima and their basins' sizes. In other words, the higher the peak the wider tend to be its basin of attraction. Therefore, on average, with a hill-climbing algorithm, the global optimum would be easier to find than any other local optimum. This may seem surprising. But, we have to keep in mind that as the number of local optima increases (with increasing K), the global optimum basin is more difficult to reach by an stochastic local search algorithm (see figure 5). This observation offers a mental picture of N K landscapes: we can consider the landscape as composed of a large number of mountains (each corresponding to a basin of attraction), and those mountains are wider the taller the hilltops. Moreover, the size of a mountain basin grows exponentially with its hight.

Basins sizes of local optima vs. their degrees

The scatter plots in figure 8 illustrate the correlation between basin sizes of maxima and their degrees. Representative instances with N = 18, and K = 4, 8, are illustrated. There is a clear positive correlation between the degree and the basin sizes of maxima in the network. This observation suggests that landscapes with low K values can be searched more effectively since a given configuration has many neighbors belonging to the same large basin of attraction. It is also confirmed that the basins for low K are much larger than those for high K, not only the basin corresponding to the global maximum.

CONCLUSIONS

We have proposed a new characterization of combinatorial fitness landscapes using the well-known family of N K landscapes as an example. We have used an extension of the concept of inherent networks proposed for energy surfaces [START_REF] Doye | The network topology of a potential energy landscape: a static scale-free network[END_REF] in order to abstract and simplify the landscape description. In our case the inherent network is the graph where the vertices are all the local maxima and edges mean basin adjacency between two maxima. We have exhaustively obtained these graphs for N = 16 and N = 18, and for all even values of K, plus K = N -1. The maxima graphs are small worlds since the average path lengths are short and scale logarithmically in the size of the graphs. However, the maxima graphs are not random. This is shown by their clustering coefficients, which are much larger than those of corresponding random graphs and also by their degree distribution functions, which are not Poissonian but rather exponential. The construction of the maxima networks requires the determination of the basins of attraction of the corresponding landscapes. We have thus described the nature of the basins and their relationship with the local maxima network.

We have found that the size of the basin corresponding to the global maximum becomes smaller with increasing K. The distribution of the basin sizes is approximately exponential for all N and K, but the basin sizes are larger for low K, another indirect indication of the increasing randomness and difficulty of the landscapes when K becomes large. Finally, there is a strong positive correlation between the basin size of a maxima and their degree, which confirms that the synthetic view provided by the maxima graph is a useful one. This study represents our first attempt towards a topological and statistical characterization of easy and hard combinatorial landscapes. Much remains to be done. First of all, the results found should be confirmed for larger instances of N K landscapes. This will require good sampling techniques, or theoretical studies since exhaustive sampling becomes quickly impractical. Other landscape types should also be examined, such as those containing neutrality, which are very common in real-world applications. Work is in progress for neutral versions of N K landscapes. Finally, the landscape statistical characterization is only a step toward implementing good methods for searching it. We thus hope that our results will help in designing or estimating efficient search techniques and operators.

Figure 1 :

 1 Figure 1: A model of a 2D landscape (left), and a contour plot of the local optima partition of the configuration space into basins of attraction surrounding maxima and minima (right). A simple regular network of six local maxima can be observed.

Figure 2 :

 2 Figure 2: Cumulative degree distributions for N = 16 and K = 4 (top), K = 10 (bottom). All 30 curves are plotted. Left: Log-log plot. Right: Lin-log plot.

Figure 3 :

 3 Figure 3: Cumulative degree distributions for N = 18 and K = 4 (top), K = 10 (bottom). All 30 curves are plotted. Left: Log-log plot. Right: Lin-log plot.

Figure 4 :

 4 Figure 4: Cumulative degree distribution (with regression line) of two representative instances with K = 8, N = 16 (top) and N = 18 (bottom).

Figure 5 :

 5 Figure 5: Average of the relative size of the basin corresponding to the global maximum for each K over 30 landscapes.

Figure 6 :

 6 Figure 6: Cumulative distribution of the number of basins of a given size with regression line. Two Representative landscapes are visualized with N=16 (top) and N=18 (bottom) and K=4. A lin-log scale is used.

Figure 7 :

 7 Figure 7: Correlation between the fitness of local optima and their corresponding basin sizes, for two representative instances with N = 18, K = 4 (top) and K = 8 (bottom).

Figure 8 :

 8 Figure 8: Correlation between the degree of local optima and their corresponding basin sizes, for two representative instances with with N = 18, K = 4 (top) and K = 8 (bottom).

  .016 0.189 0.0115 187.07 4.650 1.82 0.012 -0.0279 0.00321 8 2, 093 70 214, 844 6793 0.41 0.007 0.098 0.0038 205.29 2.615 1.92 0.006 -0.0263 0.00184 10 3, 619 61 348, 761 5275 0.33 0.004 0.053 0.0011 192.76 1.150 2.05 0.009 -0.0199 0.00127 12 5, 657 59 476, 614 3416 0.27 0.002 0.030 0.0005 168.50 1.003 2.29 0.012 -0.0141 0.00072 14 8, 352 60 594, 902 2459 0.23 0.001 0.017 0.0002 142.46 0.652 2.56 0.007 -0.0102 0.00044 16 11, 797 63 707, 326 2296 0.21 0.001 0.010 0.0001 119.92 0.368 2.72 0.003 -0.0080 0.00036 17 13, 795 77 762, 197 2299 0.20 0.001 0.008 0.0001 110.51 0.377 2.79 0.005 -0.0072 0.00026

					N = 16
	K	nv	ne	C	Cr	z	l	ā
	2	33 15	261 166	0.68 0.095 0.507 0.1536	14.55 3.826	1.54 0.182 -0.0007 0.00591
	4	178 33	6, 334 1646	0.66 0.036 0.406 0.0615	70.48 6.615	1.60 0.062 -0.0162 0.00467
	6	460 29	26, 414 2035	0.55 0.013 0.250 0.0150 114.76 3.033 1.75 0.016 -0.0237 0.00283
	8	890 33	56, 022 1951	0.44 0.008 0.139 0.0061 124.52 1.800 1.88 0.008 -0.0219 0.00250
	10	1, 470 34	86, 446 1766	0.36 0.006 0.080 0.0023 117.62 1.137 2.00 0.009 -0.0170 0.00182
	12	2, 254 32	117, 085 1111 0.30 0.003 0.046 0.0009 103.91 0.695 2.19 0.012 -0.0122 0.00104
	14	3, 264 29	146, 390 1025 0.26 0.002 0.027 0.0003	89.70 0.349	2.47 0.009 -0.0092 0.00064
	15	3, 868 33	160, 690 829	0.25 0.002 0.021 0.0003	83.09 0.469	2.58 0.007 -0.0086 0.00059
					N = 18
	2	50 25	478 342	0.62 0.106 0.414 0.1697	17.08 4.930	1.66 0.210	0.00390 0.00530
	4	330 72	17, 576 4898	0.61 0.044 0.332 0.0573 105.39 8.106 1.67 0.058 -0.0168 0.00495
	6	994 73	93, 043 8588	0.51 0

Table 2 : Correlation coefficient (ρ), intercept ( ᾱ) and slope ( β) and slope of the linear regression between the cumulative num- ber of nodes and the degree of nodes : log

 2

(p(k)) = α + βk + ǫ.

The averages and standard deviations of 30 independent land- scapes, are shown.

			N = 16
	K	ρ	ᾱ	β
	2	-0.816 0.340 4.05 0.717 -0.1109 0.0379
	4	-0.932 0.026 6.07 0.276 -0.0295 0.0026
	6	-0.967 0.009 7.09 0.105 -0.0178 0.0009
	8	-0.986 0.006 7.60 0.107 -0.0144 0.0007
	10 -0.989 0.004 8.04 0.125 -0.0146 0.0008
	12 -0.990 0.004 8.51 0.156 -0.0170 0.0010
	14 -0.992 0.003 8.92 0.121 -0.0202 0.0010
	15 -0.991 0.004 9.11 0.144 -0.0220 0.0011
			N = 18
	2	-0.823 0.343 4.57 0.865 -0.1088 0.0325
	4	-0.951 0.025 6.71 0.225 -0.0198 0.0021
	6	-0.982 0.007 7.74 0.107 -0.0098 0.0005
	8	-0.991 0.004 8.28 0.096 -0.0076 0.0003
	10 -0.994 0.003 8.74 0.119 -0.0076 0.0004
	12 -0.995 0.003 9.19 0.161 -0.0088 0.0005
	14 -0.995 0.003 9.65 0.134 -0.0110 0.0005
	16 -0.994 0.003 10.1 0.173 -0.0139 0.0008
	17 -0.994 0.005 10.2 0.207 -0.0151 0.0008

Table 3 : Correlation coefficient (ρ), and linear regression co- efficients (intercept ( ᾱ) and slope ( β)) of the relationship be- tween the basin size of optima and the cumulative number of nodes of a given (basin) size ( in logarithmic scale: log

 3 (p(s)) = α + βs + ǫ).

The average and standard deviation values over 30 instances, are shown.

  .985 0.0141 7.24 0.372 -0.0077 0.0011 12 -0.989 0.0129 7.98 0.370 -0.0150 0.0019 14 -0.993 0.0072 8.69 0.276 -0.0272 0.0024 16 -0.995 0.0056 9.33 0.249 -0.0450 0.0036 17 -0.992 0.0113 9.49 0.386 -0.0544 0.0058

				N = 16
	K	ρ			ᾱ		β
	2	-0.944 0.0454 2.89 0.673 -0.0003 0.0002
	4	-0.959 0.0310 4.19 0.554 -0.0014 0.0006
	6	-0.967 0.0280 5.09 0.504 -0.0036 0.0010
	8	-0.982 0.0116 5.97 0.321 -0.0080 0.0013
	10 -0.985 0.0161 6.74 0.392 -0.0163 0.0025
	12 -0.990 0.0088 7.47 0.346 -0.0304 0.0042
	14 -0.994 0.0059 8.08 0.241 -0.0508 0.0048
	15 -0.995 0.0044 8.37 0.240 -0.0635 0.0058
				N = 18
	2	-0.959 0.0257 3.18 0.696 -0.0001 0.0001
	4	-0.960 0.0409 4.57 0.617 -0.0005 0.0002
	6	-0.967 0.0283 5.50 0.520 -0.0015 0.0004
	8	-0.977 0.0238 6.44 0.485 -0.0037 0.0007
	10 100 1000 10000 100000 10 -01 basin of attraction size				exp. regr. line
		0.56 0.58 0.6 0.62 0.64 0.66 0.68 0.7 0.72 0.74 0.76 0.78
				fitness of local optima
		10000				regr. line
	basin of attraction size	10 100 1000
		1
		0.5	0.55	0.6	0.65	0.7	0.75	0.8
				fitness of local optima

Table 4 : Correlation coefficient (ρ), and linear regression coef- ficients (intercept ( ᾱ) and slope ( β)) of the relationship between the fitness of optima and their basin size (in logarithmic scale: log

 4 (s) = α + βf + ǫ).

The average and standard deviation values over 30 instances, are shown

  -12.570 0.3769 24.880 0.5725 10 0.850 0.0050 -11.954 0.3501 23.561 0.5421 12 0.833 0.0065 -11.485 0.2993 22.519 0.4773 14 0.816 0.0047 -11.261 0.2008 21.864 0.3256 15 0.812 0.0044 -11.352 0.2109 21.876 0.3298 N = 18 2 0.839 0.0680 -16.585 6.0606 35.925 8.6640 4 0.842 0.0257 -14.458 2.1746 30.174 3.1520 6 0.852 0.0140 -14.542 0.9596 29.219 1.4147 8 0.867 0.0066 -14.515 0.3750 28.538 0.5988 10 0.866 0.0038 -13.914 0.3068 27.209 0.4621 12 0.854 0.0030 -13.180 0.1700 25.751 0.2804 14 0.836 0.0027 -12.602 0.1399 24.553 0.2214 16 0.822 0.0022 -12.502 0.1039 24.133 0.1633 17 0.817 0.0027 -12.583 0.1278 24.143 0.2066

			N = 16
	K	ρ	ᾱ	β
	2	0.832 0.0879 -15.476 5.9401 33.066 8.9252
	4	0.842 0.0259 -13.035 1.9907 27.094 2.8611
	6	0.852 0.0180 -12.977 0.9921 26.061 1.4908
	8	0.860 0.0088

ADDITIONAL AUTHORS


Aircraft Measurements During the BEMA Campaign (Burriana, Spain, June 97) N. Anastasio, A. Lopez, J. L. Attie and P. Durand Laboratoire d'Aerologie, UMR CNRS/UPS: 5560, 14 Ave. Edouard Belin, 31400 Toulouse, France Abstract. Our aim, within the framework of the BEMA programme, was to use airborne measurements as input for the initial conditions and boundary conditions for models (TVM/LCC and TVM/RACM meso-scale models)

developed by lSPRA, to study the influence of biogenic emissions on the ozone formation in a Mediterranean atmospheric boundary layer. This photochemical formation is connected to a non-linear reaction kinetics involving hydrocarbon and nitrogen oxide emissions [START_REF] Lopez | Simulation of the chemical processes in an atmospheric boundary layer-Influence of light and biogenic hydrocarbons on the formation of oxydants[END_REF]. These measurements also allowed the models to be validated.

I Introduction

The changes in a chemically reactive component in the atmospheric boundary layer can be described by its budget equation. For horizontal homogeneity this can be expressed as follows:

a� �ua�"oili._ +S -P Interpolation of the measurements obtained from vertical and horizontal runs enable the representation of wind, potential temperature, specific humidity and ozone fields in a plane-perpendicular to the coast,(Fig. 3,4 ).

-0.2 0.0 0.2 Longitude (deg�s) The data were then analysed to draw up a schematic representation of the structure of the atmosphere on a plane perpendicular to the coast (Fig. 5).

2

  the mean concentration at altitude z, $ the vertical flux, S and P the photochemical sources and sinks on the same level. The term oC/at represents the change in time of the concentrations, the term uoC! ax is the horizontal advection term and 8$/oz represents the divergence of vertical fluxes in the surface layer and at the top of the thermal internal boundary layer. Airborne measurements allow availability to these data and provide information on atmospheric circulation through vertical profiles of mean dynamical and thermodynamical parameters. Correspondence to: A.Lopez Presentation of the measurements A measurement campaign was implemented in June 1997 in the region of Castellon in Spain. The aircraft used was the French ARAT (Atmospheric and Remote under INSU's (National Institute for the Sciences of Universe) operational responsibility. The aircraft was a FOKKER 27-MK 700 equipped to acquire mean meteorological parameters (wind, T, H, radiation), mean physical and chemical parameters (aerosols and ozone) and turbulent parameters enabling the calculation of lateni, sensible, momentum and ozone fluxes. The experimental region was a coastal plain of thirty kilometres wide where the vegetation consisted mainly of orange trees. It was characterised by an heterogeneous distribution of man-made and industrial sources of pollution that can contribute to ozone formation due to emissions of nitrogen oxides and hydrocarbons.

Fig3

  Fig. I. Experimental area The airborne measurements were completed by a network of ground stations (points B,C,D and E, Fig. I) measuring biogenic emissions of the vegetation, the daily

Fig. 3 .Fig. 4 .

 34 Fig.3. Wind, potential temperature (degre) fields of the afternoon of 13/06

Fig. 5 .4

 5 Fig.5. Schematic representation of two dimensional structure of the atmosphere (afternoon 13/06/97)[START_REF] Cuvelier | Application of the mesoscale meteorology chemistry model TVM-LCC/RACM to the study of biogenic emissions[END_REF]

Figure 6 Fig. 6 .

 66 Figure 6 shows the change in ozone fluxes along an axis perpendicular to the coast. At low altitude the fluxes were fairly representative of the surface fluxes. The negative values correspond to deposition on the ground and vegetation.At intermediate altitudes, the fluxes were representative of entrainment fluxes between the Internal Boundary Layer and the breeze cell. Above the Thermal Internal Boundary Layer, flux values were lower

Acknowledgments. This study was supported by the European program BEMA


H Terfa
email: hani.terfa@univ-tlemcen.dz

L Baghli
email: lotfi.baghli@univ-tlemcen.dz

R Bhandari

Impact of renewable energy micro-power plants on power grids over Africa

Keywords: Micro-Power Plants, Smart grid, Distributed generation, Firebase Database, Power System Stabilizers

Providing electricity in African countries through the extension of the grid is very expensive, due to its highly distributed population. Thereby, the use of distributed renewable energy micropower plants is the proposed solution.

In this paper, we present the research studies at our laboratory to achieve building prototypes of smart distributed renewable energy micro-power plants. Four types of micro-power plants are being developed; a 1.5 kW Wind Turbine Emulator based on a Double Fed Induction Generator, a 1.5 kW Wind Turbine Emulator based on a Synchronous Generator, a 1.5 kW Photovoltaic system with Grid Tie Inverters and finally, a 250 W Photovoltaic micro-power plant connected through a self-made single-phase Grid Tie Inverter.

In addition, we have a simulated power grid with conventional power plants, power system stabilizers and automatic voltage controllers and other modelled power plants running in real time on embedded processors (Raspberry PI3). To ensure the data flow between all these micropower plants and the simulated power grid, we use a Firebase Database; the experimental benches send data and receive orders to/from the database thanks to Wi-Fi connected microcontrollers ESP8266. Load Flow and Transient Stability studies are considered.

HIGHLIGHTS

-Four experimental prototypes of micro-power plants are presented -MPPT extraction algorithms are performed on the micro-power plants -Communication technologies are the key to achieve the new approach on smart grids -Intermittent renewable sources have negative impacts on power grid stability -Power System Stabilizers are important to enhance the stability of power grids

INTRODUCTION

The United Nations estimates that the current population of Africa is more than 1.32 billion with more than 56 % of people living in non-urban areas [START_REF]Population of Africa[END_REF]. Although Africa is rich by renewable and non-renewable energy sources (A Photovoltaic panel produces twice energy in Africa than it will produce in Central Europe on average), the generation of electricity is not yet satisfied [START_REF] Ouedraogo | Modeling sustainable long-term electricity supply-demand in Africa[END_REF], [START_REF] Szabó | Energy solutions in rural Africa: mapping electrification costs of distributed solar and diesel generation versus grid extension[END_REF]; making a mismatch between the generation and the consumption, which lead to a low power service and many blackouts and outages [START_REF] Cole | Power outages and firm performance in Sub-Saharan Africa[END_REF]. This affects directly the economic growth of African countries [START_REF] Ouedraogo | Energy consumption and economic growth: Evidence from the economic community of West African States (ECOWAS)[END_REF], [START_REF] Ouedraogo | Energy consumption and human development: Evidence from a panel cointegration and error correction model[END_REF]. The conventional solution of extending the power grid face many constraints, among them; distributed population, difficult terrains, long distances between the utility grid and the loads and the expensive cost [START_REF] Li | Optimal design and techno-economic analysis of a solar-windbiomass off-grid hybrid power system for remote rural electrification: A case study of west China[END_REF]. However, with the development of renewable energy technologies, and with the increase of fuel prices [START_REF] Farmad | Integration of demand side management, distributed generation, renewable energy sources and energy storages[END_REF]- [START_REF] Park | Spatial prediction of renewable energy resources for reinforcing and expanding power grids[END_REF], the integration of distributed renewable energy Micro-Power Plants (MPP) is more favorable to enforce the weakness of the power grids in Africa.

Many countries on Africa continent are enabling high investments in solar and wind energies. Figure 1 shows the Law-Carbon scenario based on African Development Bank (AfDB) a New Deal on Energy for Africa policy document, Balmorel model [START_REF]Roadmap to the New Deal on Energy for Africa: An analysis of optimal expansion and investment requirements[END_REF]. This model shows the power sector expansion of the 54 African countries by 2030. It is a dynamic approach for the integration of renewable energies. It includes real data for wind and irradiance to match the supply with the demand through the day. It is shown that the installed capacity from renewable energies in Africa will exceed 50% of the total production by 2030. For example, Algeria, the biggest country in Africa, has launched an ambitious program (the Algerian Renewable Energy Development and Energy Efficiency Program-PENREE) which consist of installing up to 22000 MW of power generating capacity from renewable energy sources by 2030 [START_REF] Bouznit | Measures to Promote Renewable Energy for Electricity Generation in Algeria[END_REF]. These important capacities open the doors to study the impact of installing many renewable energy MPP and Power plants, and to analyse their mutual interaction not only in islanded mode, but also in grid-connected mode. The concept of integration of distributed renewable energy MPP for the development of microgrid will be most significant in the near future [START_REF] Basak | A literature review on integration of distributed energy resources in the perspective of control, protection and stability of microgrid[END_REF]. This new approach consists in putting many renewable energy MPP near the customers and some of them will be part of the home itself. The idea is to turn the consumer into a prosumer that can produce energy and consume it at the same time. These MPP are connected, through inverters [START_REF] Çelik | A novel control strategy for grid connected distributed generation system to maximize power delivery capability[END_REF] to the distribution network, which is connected to the high voltage power grid [START_REF] Montuori | Integration of renewable energy in microgrids coordinated with demand response resources: Economic evaluation of a biomass gasification plant by Homer Simulator[END_REF]. This approach is different from the conventional one where the power plants are located far from the loads and where there are many power losses in the transmission line (Copper losses, Magnetic Losses, Corona effect, and skin effect) [START_REF] Alumona | Overview Of Losses And Solutions In Power Transmission Lines[END_REF]. In addition, 30% of the cost for delivering electricity is due to the transmission system [START_REF] Dalwadi | Optimization of solar-wind hybrid system for distributed generation[END_REF]. Distributed renewable energy MPP are usually installed in combination with energy storage technologies (ESTs) such as Li-ion batteries, lead-acid, pumped hydro storage and supercapacitor energy storage [START_REF] Behabtu | A Review of Energy Storage Technologies' Application Potentials in Renewable Energy Sources Grid Integration[END_REF]. In general, the ESTs' principle is to charge a storage facility in the time of excess electricity production and discharge it when needed [START_REF] Mathiesen | Smart Energy Systems for coherent 100% renewable energy and transport solutions[END_REF]. This process is characterized by the round-trip efficiency which is the ratio of electricity stored into the facility that is subsequently recovered [START_REF]Utility-scale batteries and pumped storage return about 80% of the electricity they store -Today in Energy -U.S. Energy Information Administration (EIA)[END_REF].

Distributed renewable energy MPP give a clean energy and help to reduce the Green Houses Emissions (GHE) [START_REF] Ćosić | A 100% renewable energy system in the year 2050: The case of Macedonia[END_REF]. Nevertheless, as we cannot store as much energy as we want in the batteries, the integration of distributed renewable energy MPP brings new challenges for the stability of the power grid and for the quality of service [START_REF] Zhang | Microgrid: A strategy to develop distributed renewable energy resource[END_REF]. It is known that renewable energies have an intermittent generation that directly varies with weather conditions (Clouds, Sun, Wind, etc.), the energy output can go from zero on a cloudy day to the maximum value spontaneously and vice versa (Figure 2). Certainly, when its power capacity exceeds certain percentage, the disturbances will be more important [START_REF] Alves | Increasing the penetration of renewable energy sources in isolated islands through the interconnection of their power systems. The case of Pico and Faial islands, Azores[END_REF], [START_REF] Lund | From electricity smart grids to smart energy systems -A market operation based approach and understanding[END_REF]. To minimize the fast changes in the generated power and improve reliability and service, we need a new approach of power network control, making full use of communication technology. This will result in Smart Distributed Renewable Energy Micro-Power Plants.

The Figure 2 shows the intermittent aspect of generated power from two Photovoltaic (PV) panels (500W) in summer on a cloudy afternoon at Tlemcen, Algeria. The work presented in this paper is a part of a big project consisting in managing electricity produced from different types of renewable energy MPP to match the supply with the demand instantaneously and conserve the stability of the power grid. To achieve this goal, the project is divided into many parts: 1-Mastering the active and reactive power produced from all the MPP (both experimental and simulated ones). 2-Mastering the data flow between all the MPP, the emulated power grid, the external supervisor (android application or PC) and the firebase database. 3-Studying the impacts of integrating renewable energy MPP on power grids in term of frequency and voltage stability. 4-Develop strategies (centralized or decentralized control) to drive the swarm of MPP in a way that each one produces an amount of power proportional to its installed capacity and to other producers to respect the load/production equilibrium, to conserve the stability of the power grid, and to enhance the quality of service. In this paper, we present the overall MPP involved in our project in section II. In addition, we present the issues we faced when performing communication protocols between all the parts of the system (MPPs, emulated power grid, external supervisors, DB). In section III, we present the results and we discuss them. We emphasize in this section the impact of renewable energy MPP integration in power grids in term of frequency and voltage stability. Developed programs that compute the load flow, the transient stability, the power system stabilizers and the power injection from renewable energy MPP at the grid buses are also considered. Finally, we present the conclusion and the perspectives in section IV.

MATERIALS AND METHODS

Experimental micro-power plants

Experimental prototypes of smart MPP are developed at the Laboratoire d'Automatique de Tlemcen (LAT), Algeria.

Wind turbine emulator based on a Double Fed Induction Generator

Figure 3 shows the overall structure of the emulator of the wind energy conversion system [START_REF] Dekali | Indirect power control for a Grid Connected Double Fed Induction Generator Based Wind Turbine Emulator[END_REF], [START_REF] Zouheyr | Improved hardware implementation of a TSR based MPPT algorithm for a low cost connected wind turbine emulator under unbalanced wind speeds[END_REF]. The DC motor is directly coupled to the Double Fed Induction Generator (DFIG) and is powered by a chopper. The chopper is powered from the same DC bus as the DFIG rotor side inverter. This ensures that the delivered power from the rotor side of the DFIG through the Motor Side Converter (MSC) in hyper-synchronous mode will not increase the DC bus voltage and destroy the capacitors. Hence, we only need a simple three-phase diode-based rectifier as a Grid Side Converter (GSC). We use autotransformers for voltage adaptation as low as the DC machine maximum voltage (250V). The stator of the DFIG is connecter to the grid. The main part of the generated power Ps flows from the stator to the grid through the 13A autotransformer.

To control both the 3-phases inverter and the DC chopper, we use a dSPACE DS1104 single board control solution with reprogrammed firmware. Different wind profiles are applied through the control of the DC motor and an MPPT (Maximum Power Point Tracking) extraction algorithm allows the control of the speed of the Wind Turbine Emulator (WTE) in order to get the maximum power generated by the DFIG.

Wind turbine emulator based on a Synchronous Generator

A similar structure is used for the WTE based on a Synchronous Generator (SG) (Figure 4) [START_REF] Zouheyr | Grid Side Inverter Control for a Grid Connected Synchronous Generator Based Wind Turbine Experimental Emulator[END_REF], but we need back-to-back converters (MSC and GSC) between the grid and the stator of the SG. The Control Desk™ running on the host PC of the DS1104 permits the interaction with the embedded control program variables of the system in real time. This system is not yet fully operational; parameters identification and control parameters computation need to be performed. Six PV panels (250 W for each one) are connected each two with one Grid Tie Inverter (GTI) YC500. Each GTI has two independent DC input with dedicated MPPT per input. The three GTI are connected in parallel to the grid via a circuit breaker. The Energy Communication Unit (ECU) uses PLC (power line carrier) to communicate with the GTI and sends data over the Wifi router to an external database (Figure 5). The ECU acts also as a local web server. A Raspberry Pi3 (RPi3) connected to the LAN reads the data of the generated power from the web server of the ECU and sends them to the Firebase Database (DB) each 5 minutes. This time can be adjusted.

Photovoltaic self-made micro power plant

In order to study our own implementation of a GTI, we choose to build it with two interleave step-up DC-DC choppers that extract the power form the PV. Then, the inverter stage synchronizes to the grid using a Zero Cross Detection algorithm and allows the injection of the reference active power. The reactive power can also be absorbed or generated from the grid or work at a unity power factor [START_REF] Merah | Prototyping of photovoltaic grid-tie inverter with active and reactive power injection[END_REF]. The control is done using TI Launchpad F28069M as shown in Figure 6. The communication to the DB is done with a Wemos ESP8266.

In order to produce the maximum power available (MPPT), or the exact amount of needed power or to shut down the power production, the control is taking the reference point from the DB.

Figure 6. Experimental structure of the PV self-made micro power plant

Simulated micro-power plants

In parallel to the experimental prototypes, we created models of smart micro-power plants.

Wind turbine generator micro-power plant model

A simplified model of a DFIG expressed in a (d-q) axis is used with flux vector control. This strategy allows the linearity between the rotor currents (Iqr, Idr) and the stator powers (Ps, Qs) of the DFIG [START_REF] Dekali | Indirect power control for a Grid Connected Double Fed Induction Generator Based Wind Turbine Emulator[END_REF].

Figure 7 shows the active and reactive power control diagram. Where Psref, Qsref, Idrref, Iqrref, Vdrref and Vqrref are the references of active power, reactive power, direct rotor current, quadrature rotor current, direct rotor voltage and quadrature rotor voltage respectively. Ps, Qs, Idr, Iqr and Vs are the active power, reactive power, direct rotor current, quadrature rotor current and stator voltage respectively. Ls, Lr, M, Rr and sigma are the stator inductance, rotor inductance, mutual inductance, rotor resistance and insulation permittivity respectively. Ws and Wr are the stator pulsation (2𝜋𝜋𝑓𝑓 𝑠𝑠 ) and the slip pulsation respectively.

To extract the maximum power available, we used an MPPT algorithm that calculates the optimum mechanical speed Wm_opt of the DFIG and then generates the active power reference Psref thanks to a PI controller as shown in Figure 8. Where lambda_opt is the optimal relative speed, G is the gearbox ratio, R is the pale radius, Wsp is the wind speed and Wm is the mechanical speed of the DFIG.

Photovoltaic micro-power plant model

A PV panel is modelled as a current source in parallel to a diode and a parallel resistance Rp. All are in series with a resistance Rs. The output current Ipv of a PV panel is calculated as fallow [START_REF] Çelik | A novel control strategy for grid connected distributed generation system to maximize power delivery capability[END_REF], [START_REF] Dekali | Indirect power control for a Grid Connected Double Fed Induction Generator Based Wind Turbine Emulator[END_REF]:

𝐼𝐼 𝑝𝑝𝑝𝑝 = 𝐼𝐼 𝑝𝑝ℎ -𝐼𝐼 𝑜𝑜 � 𝑒𝑒 𝑞𝑞�𝑉𝑉+𝐼𝐼 𝑝𝑝𝑝𝑝 𝑅𝑅𝑅𝑅� 𝑎𝑎𝑎𝑎𝑎𝑎 -1� - 𝑉𝑉+𝐼𝐼 𝑝𝑝𝑝𝑝 𝑅𝑅 𝑅𝑅 𝑅𝑅 𝑝𝑝 (1)
Where Iph is the photon current, Io is the Diode saturation current, q is the electron's charge, V is the PV voltage, T is the temperature, k is the constant of Boltzmann and a is the quality factor. For a specific temperature and irradiance, the generated power of a PV panel varies in function of the voltage as shown in Figure 10. To extract the maximum power available, an MPPT algorithm searches the appropriate voltage that fulfils the equation 𝑑𝑑𝑑𝑑 ⁄ 𝑑𝑑𝑑𝑑 = 0. Where P is the generated power.

Emulating the power grid

For this step, we emulate the high-voltage utility grid by a 5-buses power grid [START_REF] Baghli | An Open Source Real-Time Power System Simulator with HIL[END_REF] (Figure 12) running in real time on the RPi3. It contains two Generator buses (nodes). SOUTH is a PV bus and NORTH is the Slack bus. There are three consumption nodes (ELM, LAKE, and MAIN).

To compute the power flow through the grid and the voltage at all the buses, we implemented the Load Flow (LF) program of a Lab developed program [START_REF] Baghli | An Open Source Real-Time Power System Simulator with HIL[END_REF] on the RPi3. In addition, the Transient Stability (TS) program is also implemented and adapted to the RPi3. Moreover, we implemented two power system stabilizers (PSS) to ensure the stability of the system. The first one is an Automatic Voltage Regulator (AVR) to stabilize the magnitude of the voltage and the second one is the speed governor to stabilize the speed of the power plant SG.

Figure 12. 5-buses power system [START_REF] Baghli | An Open Source Real-Time Power System Simulator with HIL[END_REF] The mathematical equations and the power system modelling for LF and TS studies are found in [START_REF] Baghli | An Open Source Real-Time Power System Simulator with HIL[END_REF]. The Runge-Kutta 4 and Gauss-Seidel are the numerical methods implemented for the iterative calculations of TS and LF respectively. The system of equations to be solved for TS studies to express the dynamic behavior of a SG is [START_REF] Baghli | An Open Source Real-Time Power System Simulator with HIL[END_REF]:

� 𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 = 𝜔𝜔 -𝜔𝜔 𝑠𝑠 𝑑𝑑 2 𝑑𝑑 𝑑𝑑𝑑𝑑 2 = 𝜔𝜔 𝑅𝑅 2 𝐻𝐻 �𝑑𝑑 𝑚𝑚 -𝑑𝑑 𝑒𝑒 -𝐷𝐷 𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 � (2)
Where 𝛿𝛿 is the internal angel, 𝜔𝜔 is the rotor speed, 𝜔𝜔 𝑠𝑠 is the synchronous speed, Pm is the mechanical power of the turbine, Pe is the electrical power, H is the inertia moment, and D is the damping for each generator.

Communication protocols and experimental issues

To study the impact of integrating renewable energy MPP on the stability of the 5-buses power grid and to analyze their mutual interaction in grid-connected mode, the smart prototypes of MPP should communicate to the DB in order to send information about their actual production and receive orders to inject to the grid the exact power needed, not more and not less. This helps us to control the smart MPP and to manage the power produced from renewable energies. For that, we implemented routines on the RPi3 to communicate with the DB in order to receive the generated power from the experimental MPP and to send orders for the reference power. Reading data and sending orders are done every 5 seconds. We developed an Android application (Figure 13) to check for any update in the DB and displays data; it is available on: https://play.google.com/store/apps/details?id=com.embesystems.microplants. We are still facing some experimental issues: The WTE based on DFIG is operational but it is not yet communicating to the DB. The WTE based on a SG is already communicating to the DB thanks to the microcontroller ESP8266, but it is not yet fully operational, we have some issues when controlling the SG. The 1.5 kW PV industrial MPP is only sending data thanks to the second RPi3 that reads data from the server of the ECU and send them to the DB, but this MPP cannot receive orders of the needed reference power, because the GTI YC500 produces always the maximum power thanks to its MPPT internal algorithms. The 250 W PV self-made MPP however will send and receive orders to / from the DB thanks to the microcontroller ESP8266 to produce the needed power, but this experimental bench is still under progress.

To deal with the communication issues of the experimental prototypes and the early stage of development of the MPP, we proceed by collecting experimental data of both PV and WTE based on DFIG micro-power plants in a laptop. The collected data in the RPi3, will be used by the LF and TS programs to be injected in the 5-buses power grid.

In this paper, four cases are presented: the first is when the 5-buses power grid functions without injecting the power of the MPP, the second is when we inject only the power of the PV micropower plant at ELM bus, the third is when we inject only the power of the WTE based on a DFIG at LAKE bus, and the last case is when we inject the power of both PV and WTE micropower plants in the corresponding buses. In the cases 1, 2, 3 and 4, the installed capacity from renewable energy MPP is 0%, 20%, 35% and 55% of the total production respectively. In all these cases, we consider all other loads constant. In addition, the data are received in Watt, and then transformed to per-unit (pu) in order to adapt them with LF and TS calculations that are in pu. The NORTH generator curves are represented by the blue color and the SOUTH ones are represented by the red color in the following figures.

RESULTS AND DISCUSSIONS

The characteristics of the two SG are presented in Table A.1. The TS and LF calculations are performed every 1ms to get the new values of the generated power, bus voltage, speed and internal angles of both SG. The AVR is called every 2 ms whereas the speed governor loop is performed every 10 ms. Table A.2 shows the initial data for TS calculations. They are obtained from a previous LF simulation, in steady state conditions, before starting the TS simulation.

Case 1

In this case, the 5-buses power grid are operating with no power injected from the MPP. The Figure 17 shows the variation of the electrical and mechanical quantities (Voltage, internal angle, speed and power) of both SG. The total active power production is 1.6957 pu (0.4 pu from SOUTH and 1.2957 pu from NORTH). We see that, all the electrical and mechanical quantities are constant in steady state. This is explained by the non-integration of MPP and that there is no modification or faults in the power network.

Figure 17. SG electrical and mechanical variables

Case 2

In this case, the PV MPP starts injecting power in the 5-buses power grid at ELM bus after t=10s. Figure 18 shows the variation of the PV power. A routine is added to the TS program to read these data from a file and to inject them in the 5-buses power grid as additional positive load that varies with time (positive values are for generated power).

Figure 18. The power of the PV prototype Figure 19 shows the variation of the electrical and mechanical quantities of both generators. We see that, when injecting the PV power in ELM bus, both generators will be affected due to the interconnection of the grid. A mismatch between the consumption and the production happened. Thus, both generators accelerate. Thanks to the PSS, the AVR and the speed governor that control respectively the e.m.f and the mechanical power of both SG, the generated power from the non-renewable sources is reduced. This fast acting makes the voltage and the speed come back to their nominal values spontaneously after each increase or decrease in the injected power. In addition, it makes the internal angels of both generators stay in the stability limit (δ < 90°). In this case, the DFIG-based WTE micro-power plant starts injecting its power at the LAKE bus. Figure 20 shows the variation of the injected power in pu which is more fluctuant compared to the injected PV power. This power is obtained with certain conditions: The wind profile (Figure 21) should be more than 5 m/s and less than 9 m/s [START_REF] Dekali | Indirect power control for a Grid Connected Double Fed Induction Generator Based Wind Turbine Emulator[END_REF]. which is equivalent to 1300 rpm and 1800 rpm for the WTE respectively. If, due to the wind profile, the control variable (voltage of the DC motor) exceeds its limits, the driven torque is no more controlled and we stops the power generation. This is shown between 5s and 10s.

Figure 22. SG electrical and mechanical variables, WTE power is injected

In this third case study, the mechanical and the electrical quantities are more affected by the high fluctuation of the WTE power (Figure 22) compared to the PV power of case 2 but, once again, the system is well controlled thanks to the PSS.

Case 4

Figure 23. SG electrical and mechanical variables when both PV and WTE are considered

In this last case study, the data of both PV and WTE are used for a power injection at ELM and LAKE buses respectively from t=10s. It is clear that the disturbances generated by the intermittent injected powers propagate rapidly to the grid connected affecting both generators as shown in Figure 23. In addition, the PSS present a fast reaction to the power mismatch making voltage and speed remaining to their nominal values for each disturbance.

Comparing case 2, 3 and 4, we conclude that, it is not the quantity of the injected power that makes important disturbances, but its variation rate. We see in case 4 that the disturbances are the same as case 3. Indeed, the generated power from the two SG is reduced much more in the case 4 compared to the case 2 and 3.

CONCLUSION

This paper presents the impact of integrating renewable energy MPP on power grids over Africa. Special designed experimental prototypes of renewable energy MPP have been used in this study. As there is less wind in Algeria, experimental emulations are used to emulate the wind turbines based on a DFIG or based on a SG. Corresponding wind profiles of moderate speeds are used.

In addition, simulated models that reflect the same behaviour as the experimental ones are presented. Communication protocols between all the MPP are done thanks to a developed firebase database and micro-controller (Wemos ESP8266) programs. An android application that plays the role of an external supervisor communicates with the DB and displays the data flow in real time. It was shown that the integration of distributed renewable energy production thanks to MPP will enforce the weakness of power grids in Africa. It reduces the generated power from the conventional generators, hence, reducing the consumption of fuel, minimizing the GHE, and reduce many types of losses. The drawbacks are the negative impact on the quality of service and on the stability of the power grid due to the intermittent availability of the sources.

With an appropriate control of the e.m.f. and the mechanical power of the conventional generators, we can reduce the apparatus and the disturbances results from the renewable MPP. A proper communication between the MPP, the power plants and the grid system operator will help in anticipating the control.

Due to the fact that apparatus and disturbances propagate rapidly in the connected network, the control and management of the generated power from renewable sources are very important to avoid fragilizing the power grid and to keep the system working at optimal efficiency.

ACKNOWLEDGEMENT

This study is financially supported by the German Federal Ministry of Education and Research (BMBF) via its project management agency DLR, under the project "Water and Energy Security in Africa (WESA-ITT)". This work is also supported by the Direction Generale de la Recherche Scientifique et du Developpement Technologique (DG RSDT) of Algeria.

ABBREVIATIONS

Figure 1 .

 1 Figure 1. The renewable energy transition in Africa, a view towards 2030

Figure 2 .

 2 Figure 2. Experimental curve of PV power in the summer at Tlemcen, cloudy afternoon

Figure 3 .

 3 Figure 3. Experimental hardware structure of the wind turbine emulator based on a DFIG.

Figure 4 .Figure 5 .

 45 Figure 4. Experimental structure of the wind turbine emulator based on a SG

Figure 7 .Figure 8 .

 78 Figure 7. DFIG active and reactive power control diagram

Figure 9 .

 9 Figure 9. Simulated wind power

Figure 10 .

 10 Figure 10. The variation of the PV power in function of the voltage

Figure 11 .

 11 Figure 11. Simulated solar power

Figure 13 .

 13 Figure 13. MicroPlants Android application

Figure 14 .

 14 Figure 14. Communication interactions between the MPP, emulated power grid and the Android application with the DB.

Figure 15 and

 15 Figure 16 show the AVR and the speed governor loops respectively; Where Eg0 and Pm0 are the nominal values of e.m.f and mechanical power respectively. Eg.ref and Pm.ref are the reference values for the e.m.f and the mechanical power respectively. Eg, Ig, V and Yg are the e.m.f, current, voltage and admittance of the SG respectively. Kp and Ki are the proportional and integral coefficients of the AVR or the speed governor.

Figure 15 .Figure 16 .

 1516 Figure 15. AVR loop for both generators

Figure 19 . 3 . 3 . Case 3 Figure 20 .Figure 21 .

 193332021 Figure 19. SG electrical and mechanical variables, PV power is integrated

Hydro 18% Solar 32% Wind 6% Other RE 2% Non-RE 42% Installed Capacity (% of total MW) by 2030

	Hydro
	Solar
	Wind
	Other RE
	Non-RE

  Where Pg is the generated power, PL is the consumed power (load) and Vb is the bus voltage.

		Transformer 2 (40VA)	12		Voltage differential probe
		Bus	Pg (pu) PL (pu)	Vb (pu)
		NORTH	1.2957 0.0000	1.0600
		SOUTH	0.4000 0.2000	1.0474
		LAKE	0.0000 0.4500	1.0000
		MAIN	0.0000 0.4000	1.0000
		ELM	0.0000 0.6000	1.0000
		Total production	1.6957 -	-
		Total consumption	-	1.6500	-
		Total line losses	0.0457 -	-
	Components Name	Components Name
	1	DFIG	6	Measure interfaces for DFIG
	2	DC Motor	7	Measure interfaces for DC Motor
	3	PC	8	Autotransformer (stator side)
	4	DS1104 interface	9	Autotransformer (rotor side)
	5	Inverter and Rectifier 10	Power supply (DC excitation)
	MPP: Micro-Power Plants
	AfDB: African Development Bank

Figure A.1. Experimental hardware setup of the WTE based on a DFIG Table A.3. WTE based on a DFIG hardware components Figure A.4. Experimental hardware setup of the PV industrial MPP

Table A.6. PV industrial MPP hardware components Component Name 1 Photovoltaic cells (250 W for each one) 2 GTI YC500

The active power Qs:

The reactive power Idr:

The direct rotor current Iqr:

The quadrature rotor current Vs:

Stator voltage Ls:

Stator inductance Lr:

Rotor inductance M:

Mutual inductance Rr:

Rotor resistance sigma: Insulation permittivity Ws:

Stator pulsation 𝑓𝑓 𝑠𝑠 :

Stator frequency Wr:

Slip pulsation Wm_opt: Optimum mechanical speed lambda_opt: Optimal relative speed G:

Gearbox ratio R:

Pale radius, Wsp: Wind speed Wm: Mechanical speed of the DFIG Rp:

Parallel resistance Rs:

Serial resistance Ipv:

The output current of a PV panel Iph:

The photon current Io:

The Diode saturation current q:

The electron's charge V:

The voltage T:

The temperature K

The constant of Boltzmann a:

The quality factor. P:

The PV generated power The internal angle of the Synchronous Generator 𝜔𝜔:

The rotor speed of the Synchronous Generator 𝜔𝜔 𝑠𝑠 :

The synchronous speed Pm:

The mechanical power of the turbine Pm.max: The maximum mechanical power of the turbine Pm.0: The nominal value of the mechanical power Pm.ref: The reference value of the mechanical power Pe:

The electrical power Pg:

The generated power PL:

The consumed power Vb:

The nominal value of the bus voltage Eg.max: The maximum electromotive force Eg:

The electromotive force Eg.0: The nominal value of the e.m.f Eg.ref: The reference value of the e.m.f Ig:

The generated current of the SG Yg:

The admittance of the SG Kp:

The proportional coefficient for the AVR or for the speed governor respectively Ki:

The integral coefficient for the AVR or for the speed governor respectively e:

The controller input error (voltage / speed) H:

The inertia moment D:

The damping R:

The resistance Xd:

The transient reactance APPENDIX A.