Because of wake e ects and geographical constraints, the search for optimal positions of wind turbines has an important part to play for their e ciency. The determination of their positions can be treated as optimization problem and can be solved by various methods. In this paper, we propose optimization approaches based on Simulated Annealing (SA) to improve solutions for the wind turbines placement problem. We de ne neighborhoods of solutions and analyze the in uence of speci c parameters, e.g., neighborhood distance and SA temperature in experimental studies. The experiments are based on a real-world scenario with a wind model, wind data from a meteorological service, and geographical constraints. Inspired by adaptive step size control applied in Evolutionary Strategies (ES), we propose an approach using an adaptive neighborhood distance and compare the results to optimization runs with a constant neighborhood distance. Also the best and worst optimization run and the corresponding placement results are shown and compared.
Planning and optimization of renewable energy resources is an important part of today's activities towards an ecologically friendly smart grid. As the environment of wind turbines is signi cant for their e ciency, the determination of their locations should be handled carefully and with consideration of various aspects. In this paper, we use a wind model based on wind distributions using data from the German Weather Service and take geographical constraints into account. We apply di erent optimization approaches using SA to the turbine placement problem with the objective to maximize the power output. SA is often used for combinatorial problems, but can also be applied to continuous solution spaces. For this, we de ne neighborhoods in the continuous solution space of turbine positions. We also propose an adaptive variant of neighborhoods for SA inspired by an adaptive method from the eld of ES, as the de nition of neighborhood corresponds to the step size of ES.
This paper is structured as follows. In Section 2, we give an overview to related work. The wind model is explained in Section 3 and includes the de nition of the employed scenario. In Section 4, we introduce the optimzation approaches, followed by the experimental results in Section 5. In Section 6, conclusions are drawn. 2
The wind turbine placement problem is widely known and there are a lot of
di erent models and approaches to solve it [
To solve the turbine placement problem, we employ stochastic search
algorithms [
In this section, we introduce the wind turbine model that we use in the experimental part of this work. This model computes the produced energy of a wind farm. The description is followed by the speci cation of the real-world scenario used in this paper. 3.1
As the objective in this work is to maximize the power output of a wind farm,
we apply a wind turbine model to calculate the produced energy of the turbines.
(1)
(2)
The wind turbine model f exploits a scenario that consists of wind turbines
and their power curves based on the Enercon E101, wind data from the German
Weather Service, wake e ects computation using the Jensen wake model [
p (ti; ) E (ti; )d with the power output E (ti; ) for one wind direction:
E (ti; ) =
i(v) pv(v; k(ti; ); c(ti; ))dv:
E(ti) =
The distribution of wind angles is described in p (ti; ), the function i(v)
speci es the power curve of the used wind turbine, and the Weibull distribution
pv(v; k(ti; ); c(ti; )) represents the wind speed distribution. In the evolutionary
optimization process, the geographical constraints are modeled by a variant of
death penalty that is similar to the approach used by Morales and Quezada [
The model f computes the power output of a solution x that describes the positions of multiple wind turbines for a de ned scenario, i.e., a scenario speci es the map section and the wind distributions. Thereby, the optimization objective is to maximize the sum of the power output E of all turbines t: f (x) = PiN==12 E(ti). The solution x is a vector of elements x = (x1; x2; : : : ; xN )T with the length N coding the x- and y-coordinate of every turbine xt and yt, i.e.:
x = (xt1; y1t; xt2; y2t; : : : ; xtN=2; yNt=2): With ti = (xit; yit) the solution vector can be written as:
x = (t1; t2; : : : ; tN=2): We denote the position ti of a speci c turbines of solution xj as tixj . This notation is required for the de nition of neighborhoods in Section 4.1. 3.2
To specify a scenario, we keep in mind the objective to model realistic settings
for Lower Saxony, Germany. There are more than 5; 000 wind turbines in Lower
Saxony. Most of them are grouped in wind farms smaller than 30 turbines [
SA is based on the cooling process of metallic elements that reduce defects in crystals. The algorithm starts with an initial solution x0. In our work, we start with a feasible randomly created solution. Then, the optimization algorithm creates a neighbor x0 of the actual solution x. The neighboring solution x0 is analyzed w. r. t. tness function f . If f (x0) > f (x) the solution x0 replaces x in the following iteration. For a better chance to leave local optima, SA can also accept worse solutions x0 with a tness function value f (x0) < f (x). The probability M that describes the chance to accept a worse solution is depending on the di erence of the tness function values f (x0) and f (x) and on a parameter T that is called temperature, i.e.:
M (x; x0; T ) = e f(x) Tf(x0) (3) The temperature T is variable during an optimization run with SA. Equation 3 shows how the temperature T a ects the probability M to accept a worse solution: The higher the temperature T is, the higher is the probability M . with 0 <
To de ne the neighborhood between two solutions xi and xj , we rst specify a neighborhood distance dn. Solution xj is in the neighborhood of solution xi, if one turbine tk with k 2 f1; : : : ; N=2g is di erent in both solutions but within the distance dn: and all other turbine positions from both solutions are equal: max txi k txj k
dn 8tl : tlxi = tlxj with l 2 f1; : : : ; N=2g and l 6= k. 4.2
In SA, the cooling process starts with a high probability M at the beginning of the optimization process, while M is reduced in the course of the optimization. Various options to reduce M have been introduced in the past, mainly by decreasing temperature T . A common rule to cool down is a deterministic temperature control with T 0 = T . De ning i as iteration number and T0 as starting temperature, the cooling process can be described by: (4) (5) (6)
To implement an optimization algorithm using SA with a deterministic cooling schedule, we have to determine the neighborhood distance dn, the initial temperature T0, and the cooling factor . In this work, we use a small and a large neighborhood distance dn. The small distance dn is set to 50 m, which means a turbine t can be shifted up to 50 m per iteration in both dimensions. With this distance the solution can reach the next local optimum, but is not able to shift a turbine t over a constraint like a street. Therefore, we de ne the large distance dn+ = 500 m which makes it possible to shift a turbine over a street but the ne-tuning is more di cult.
As we can see in Equation 3, the temperature T must be chosen depending on the scale of the di erence f = f (x) f (x0). Preliminary experiments show that the di erence f depends on the neighborhood distance dn. Using dn , in the rst 100 iterations with a new feasible solution x0, it applies for the di erence f that its mean value and standard deviation are f 0 6 with max( f ) 20. It means better and worse solutions are equally distributed, in about 70% of the iterations the di erence is smaller than 6, and the maximum value is approximately 20. Using d+, it applies for the rst 100 iterations with n a new feasible solution x0: f 10 30 with max( f ) 120. We de ne two di erent initial temperatures using this information. A high temperature T0h has the objective that at the beginning of the optimization process in 10% of the cases a worse solution is accepted. As we are not focusing on extreme values, we use the standard deviation. It applies for dn : 3:08 (7) And a low temperature T0l with the objective to accept 1% of the worse solutions at the beginning of the optimization process:
T0l =
6 ln(0:01=0:7) 0:71 For dn+, we are using T0h = 15:4 and T0l = 3:55. To determine , we de ne that the temperature T should be decreased by 10% every 100 iterations. So it applies: = 10p00:9 0:99895 4.4
In this section, we propose an approach based on the algorithm using the
deterministic cooling schedule from the last section extending it with an adaptive
technique. In the eld of ES, an adaptive step size control is a common tool
to improve optimization results. The idea is that the solution space conditions
change during an optimization run and therefore the optimal step size is not
the same during the whole run. At the beginning, a large step size allows the
exploration of the solution space, while at the end, a small step size allows the
ne-tuning of solutions. A well-known example is Rechenberg's step size
control [
Algorithm 1 Adaptive Neighborhood Distance Require: dn, T , x x0, i 1, o 0 while i I do
Create neighbor x0 from x if f (x0) > f (x) then x x0 o o + 1
f(x) Tf(x0) then else if U U [0; 1] > e x x0 dn dn 2:0 end if if i mod 100 = 0 then if o 20 then
dn dn 1:1 else
dn dn=1:1 end if o 0 end if
T T , i i + 1 end while return x
Preliminary experiments show that the acceptance of a worse solution can change the optimization process. The adaptive control may result in an inappropriate neighborhood distance dn. To prevent this, we implement a neighborhood distance boost bdn in case of accepting a worse solution. Hence, the optimization process can explore a larger area after taking a worse solution and thus it is less sensitive to changes in the solution space. We set this neighborhood distance boost to bdn = 2:0, which turned out to be reasonable in our experimental studies. The neighborhood distance dn is doubled after accepting a worse solution. Algorithm 1 shows the pseudocode of the optimization approach with the total number of iterations I and a random value U U [0; 1]. 5
Every optimization is run for 10; 000 iterations. As we use SA which is a heuristic
optimization approach and also apply random initializations, we repeat every
experiment 100 times and interpret the mean value and standard deviation.
Additionally, we test the signi cance of the experimental results with a Wilcoxon
signed rank-sum test [
We use eight di erent con gurations to test the capability of SA for the wind turbine placement problem with geographical constraints. The optimization runs are separated into two categories. First, runs that use the deterministic cooling schedule with a constant neighborhood distance and second, runs that use the adaptive neighborhood distance. In each category, we test the initial neighborhood distances dn and dn+ and the starting temperatures T0h and T0l. T0h. This is probably due to the fact, that a higher temperature increases the number of accepted worse solutions. As we have a highly complex 44-dimensional solution space, too many accepted worse solutions can reduce the quality of the optimization. This e ect is increased by the use of a larger neighborhood distance, as we can see comparing the results of SA with T0h & dn and SA with T0h & dn+ using a constant neighborhood distance.
The adaptive neighborhood distance adapts itself to the solution space and can counteract this e ect. But also here, we can observe that the worst mean value is achieved by SA with T0h & d+. Interestingly, this con guration created n the best overall solution. Although the higher acceptance rate of worse solutions decreases the optimization results in mean, there is a small chance that the algorithm chooses exactly the worst solutions which helps to leave local optima. A run with good choices is able to create the best solution with this con guration. This indicates that it might be promising future research to further analyze the highly complex solution space. This may allow better predictions, if accepting worse solutions may help to leave local optima. Between the approaches with the best mean values SA with T0l & dn , SA with T0h & dn , and SA with T0l & dn+ using the adaptive neighborhood distance is not signi cant di erence. With carefully chosen parameters, the adaptive neighborhood control is able to operate well. 13800 13400 13000 12600 best run worst run 0 4000
8000 5.2
Figure 3 shows the dynamic of the best with and the worst run. Both runs are achieved by SA with T0h & dn+ but the best run uses the adaptive neighborhood distance while the worst run uses the constant neighborhood distance. The important parts of the tness development are enlarged and visualized in Figure 4. The y-scale in Figure 4(a) and 4(b) is di erent by factor 5 because the changes in the worst run are larger than the changes in the best run. In the best run, we can see the acceptance of worse solutions, but only with few deteriorations of the tness function. This observation is di erent in case of the worst solution. Clearly worse solutions are accepted and the optimization process is unable to improve the tness function to the starting level. This also explains, why it is possible that the best solution optimized with SA with T0h & dn+ is worse than the best initial solution, see Table 2.
13540 13500 13460 best run 12900 12700 12500 worst run 0
1000 (a) Best run 2000 0
1000 (b) Worst run 2000 In the last experimental section, we show the placement results of the best solution, see Figure 5(a), and the worst solution, see Figure 5(b). The best solution maximizes the distances between the turbines w. r. t. the wind rose, see Figure 2. We can observe four lines of turbines. The largest line has been placed on the right, because most of the wind comes from direction south-west. This line of turbines does no cause wake e ects for other turbines. The second line on the right is curved, also reducing the wake e ects, e.g., for Turbine T 9 and T 18, as the wind comes from direction south-west. The geographical constraints are considered, e.g., on the left of the area with Turbines T 10, T 16, T 19 placed in the free areas between the constraints. The placement of the worst solution is interesting. The turbines are pulled to the upper right corner. The distances between the turbines are small, so major wake e ects reduce the power output. We can also see this behavior in other solutions created with a high temperature. Accepting to many worse solutions can lead to deadlock situations in the
T9
T5 T18 T16 T19 T10
T21 T4 T12
T17 T6
T7T1
T20 T2 T3
T22 T14 T15
T13
T8 T11 626 538 450 362 274
TT92 T21 T7T2T210T5T1T4T1T818
T17 T4T16 TT2103
T19 T6
T11
T12 T3 T15 636 536 436 336 236 (a) Best placement
(b) Worst placement optimization process, where multiple turbines blockade each other, i.e., increasing the distance between two turbines will decrease the distance to a di erent turbine. An aggravation of this e ect can be the geographical constraints. SA has serious di culties to resolve deadlock situations. Again, this con rms the need to analyze in detail, if accepting worse solutions in highly complex solution spaces may help to leave local optima and avoiding deadlock situations. 6
Finding optimal turbine locations is important for the power output of wind turbines. The optimization process to improve the positions of turbines induces a highly complex solution space. SA is able to optimize the solutions, but the choice of appropriate parameters for neighborhood distance and temperature is important. Our approach using an adaptive neighborhood distance is more reliable than the variant with constant neighborhood distance and can signi cantly improve the results.
Our experiments show that an intelligent choice of accepted worse solutions can be a promising eld for further research. Further, the integration of additional techniques from ES to SA may be an interesting research direction, e.g., the employment of a population like in parallel SA. The success of ES in turbine placement is an indicator that a smart combination of both elds could improve the results.