# Parallel Hierarchical Genetic Algorithm for Scattered Data Fitting through B-Splines
## 2 Related Work  
Scattered data fitting can be posed as an optimization problem and it has been used in many fields and applications, such as applied mathematics, computer science, geology, biology and engineering, to name a few. Particularly, ref [2] used a standard regularized least square framework when using the wavelet domain instead of the B-spline domain. In [9], a scattered approximation method using a kernel-based multivariate interpolation and approximation was introduced. This was based on the Hilbert spaces, which construct and characterize their native kernels. In [3], authors describe a fast algorithm for scattered data interpolation and approximation making use of a coarse-to-fine hierarchy of control lattices to generate a sequence of bicubic B-spline functions. In [4], a method for fitting scattered data on a 2D smooth manifold was presented. The method was based on a local bivariate Powell-Sabin interpolation scheme. It was based on a split of the macro-triangle into three sub-triangles and there was a cubic polynomial on each piece. On the other hand, other works have focused their efforts on determine the placement and quantity of knots used for curve approximation, [5] presented a method for calculating knots placement for a cubic spline curve applying a half-split method to subdivide the data into a set of piecewise lineal functions using a predefined threshold compared with an error band calculated with the second derivative. Ref [6] presented a heuristic knots placement for B-splines curves approximation, this approach was based on smoothing discrete curvature characteristics as a criterion to determine if knots were correctly placed. Recently, several approaches based on meta-heuristics methods [10; 11; 12; 13] have been applied successfully to optimize a bi-objective function, which is expressed in the form of the weighted sum of two objectives. Particularity, [PERSON] et al. shows tabu search (TS)-based approaches to solving the batching and scheduling problems, which are combinatorial optimization problems that suit the TS methods [14; 15]. Although, the nature of the curve fitting problem is different, these approaches are successful examples of the use of the bi-objective models. However, there are some approaches that have used the TS method for nonlinear and parametric optimization problems with little success [16]. On the other hand, ref [10] use a GA with a two-dimensional chromosome structure to solve the hazardous materials routing and scheduling problem. Although there are similarities between our algorithm and the [PERSON] algorithm, there are important differences. First, the algorithms are applied to solve intrinsically different problems. The [PERSON]'s method is applied to solve a routing and scheduling problem, while our method is applied to solve a multivariate nonlinear optimization problem. Second, in the [PERSON] method they applied a GA while in our method we applied a PHGA. Third, the structure implemented to search in the solution space is distinctly different. [PERSON] proposed a two-dimensional structure that represents a route in one dimension and different route costs in the second dimension for each specific individual, while we proposed a structure that has two levels of chromosomes of different types with a hierarchical relationship that is a characteristic of the HGA. In our case, this work is a continuation of that presented in [17], where a HGA was used to approximate noisy and scattered data instead of uniform data, which implies a new parameters setting of the HGA. Additionally, in this work we contribute to a parallel implementation in two levels of parallelization, over the population and the individual. With this new approach the algorithm shows a better performance over the state of art algorithms and a speed up to 145 times over a sequential implementation presented in the previous work.