## 3 Relevant Research in Wind Farm Design and Optimization
### Solution Methods
#### 3.3.2 Heuristic Optimization  
Since obtaining an optimal solution to the WFDO problem may not be possible with a reasonable amount of computational resources, as pointed out in Section 2.5, or because of the natural limitations of the calculus-based solution procedures, the attention is turned to approaches that compute near-optimal solutions. Essentially, there is an interest to explore the trade-off between the final solution quality and the amount of computational resources spent. While many problems may not have polynomial time solutions, it may indeed be possible to find a solution that is optimal or very close to the optimal. Heuristics (commonly known as approximate algorithms, derivative-free algorithms or black-box methods) are deterministic or non-deterministic solution procedures based on semi-empirical rules that are used to find near-optimal solutions to complex problems. Generally, these approaches are very fast (fast enough to be used in practice), and have improved solutions over traditional calculus-based optimization techniques [140, 327]. However, they need to be executed several times to guarantee convergence to a high quality solution. Heuristics do not necessarily require the computation of gradients during optimization and do not necessarily require that the objective function is continuous. Heuristics are classified in two different groups: constructive and iterative. Constructive heuristics build a complete solution by performing multiple sequential deterministic or non-deterministic assemblies of the involved variables while considering all defined constraints (_i.e._, the value of each variable is decided based on deterministic or non-deterministic rules). Iterative heuristics attempt to improve a complete solution (that can be obtained from a constructive heuristic) by doing a controlled evaluation of the local search space of each of the involved variables. Constructive heuristics are faster than iterative heuristics, but in most cases converge to solutions of unacceptable quality. For highly constrained problems, constructive techniques may even fail to find a feasible solution. There are several general heuristic frameworks that have been demonstrated to perform well for various types of problems (e.g., the Traveling Salesman Problem (TSP) [333]). Determining which heuristic to use for solving a particular problem is one of the most common (and most difficult to solve) questions in heuristic search. It is common to suspect that some heuristics might perform better than other heuristics when considering a set of different optimization problems, but unfortunately the No Free Lunch Theorems (NFLT) [327, 334] suggest that this is not the case. A summary of the NFLT states \"for all possible performance measures, no algorithm is better than another when its performance is averaged over all possible optimization problems\" [334]. The most basic heuristic search algorithm, Random Search (RS), randomly samples a number of feasible solutions and determines the best solution from the sample. Apparently, any heuristic that evaluates problems more cleverly should always perform better than RS, but as the NFLT suggests, their performance will be the same when averaged over all possible optimization problems. While it may not be possible to perform better than RS over all optimization problems, research has shown that it is possible for heuristics to perform much better than RS for specific problems [335, 336, 337]. Such heuristics usually take advantage of the structure of the specific problem to obtain near-optimal solutions. This structure may include the constraints of the problem, how a feasible solution is represented (e.g., binary permutation, real-valued string, _etc._), or even the instance of the problem at hand. Since any heuristic is equivalent to RS when averaged over all possible optimization problems, any fine-tuning of the driving parameters of the considered heuristic algorithm(s) will inherently create weaknesses with respect to other optimization problems.