# Parallel Hierarchical Genetic Algorithm for Scattered Data Fitting through B-Splines
## 1 Introduction  
Curve fitting deals with the problem of reconstructing an unknown function from a finite set of data points, which are commonly noisy measurements without a regular structure [1], i.e., scattered data. In this regard, the most common methods applied to this problem are interpolation and approximation. The first one uses a fitting function to reconstruct a function from the given data and the second one tries to follow the behavior of the data to reconstruct the curve. Typically, interpolation is applied to noise-free data points, while approximation is applied to noisy data points [2]. Among the variety of approximation methods used to tackle the curve fitting problem (from scattered data), B-spline curves is one of the most widely used methods to define a mathematical function that best describes the behavior of the data [2; 3; 4; 5; 6]. Thus, a B-spline curve is a continuous piecewise polynomial function defined by two sets of parameters, knots and coefficients, being knot placement and their optimal number an important issue to consider in the search of the best approximation [6]. This means that we have to place the knots as precisely as possible and determine the optimal number of knots. In this sense, the problem is considered as a hard continuous multimodaland multivariate nonlinear optimization problem with many local optima. Additionally, we need to calculate the B-spline coefficients separately by ordinary least squares. Due to the number of degrees of freedom of the B-spline, the dimension of the search space tends to be huge and to the best of our knowledge, there is not solving method that simultaneously deals with all degrees of freedom. Besides, the data is generally scattered and presents some noise, making the problem harder to solve, therefore, it is difficult to obtain an optimal solution, and it requires a high processing power. Consequently, meta-heuristic methods, such as evolutionary algorithms and specifically genetic algorithms (GA) [7] have been used to efficiently solve the aforementioned optimization problem. The GAs have been applied successfully to find near-optimal or optimal solutions to problems with a difficult and huge search space. However, the computational cost to perform a solution by using GAs is high, due to their exhaustive evolution process, which mimics the natural evolution of a population of living organisms. This computational cost is still an open issue in GAs, few papers dealing partially with this issue have been proposed [8]. In such a paper, authors propose the design of new operators, parallel execution sequences and constraints to reach termination. Nevertheless, the way in which the population is structured and how the parallel process is synchronized are what really matters to improve the performance. In this paper, we tackle both, the curve fitting problem to noisy scattered data and its performance by implementing a parallel hierarchical genetic algorithm (PHGA). For the curve fitting problem, we use a novel hierarchical structure to represent both the model structure (number and placement of knots) and the model parameters (B-spline coefficients). This hierarchical structure combines binary and real encoding. We searched for the best B-spline model using a bi-objective fitness function. As a result, our method determines the number of knots and their place simultaneously and automatically, as well as B-spline coefficients. In addition, our approach is able to find the optimal solutions with the fewest parameters within the B-spline basis functions, without the need for any subjective parameters such as smoothing factor or other initialization values, i.e., our method is fully automatic. In order to improve the performance of the HGA (hierarchical genetic algorithm), the algorithm is implemented using a full parallel model, taking advantage of the capabilities of the new hardware platforms. This is one of the main contributions of this study. In this sense, our approach presents two levels of parallelism.