# Parallel Hierarchical Genetic Algorithm for Scattered Data Fitting through B-Splines
## 3 Background  
### Curve Fitting with B-Spline Curves  
Fitting curve is known as the process of finding the equation of the curve which may be most suitable for predicting unknown values. The curve fitting problem assumes that there is a relationship \(f(x_{i})=y_{i}\) between \(n\) pairs of values \((x_{i},y_{i})\) in order to find the best curve \(\hat{f}(x_{i})\) that fits the existing data, estimating \(f(x_{i})\) well enough to be used to predict new values adequately. The problem of curve fitting comprises two stages: choosing a family of curves and selecting the best fitting curve [33].  
In this paper, we have used functions \(f\) that can be approximated on the interval \([a,b]\) by a B-spline curve. The B-spline curve is a piecewise polynomial function of \(k\) order joined at certain \(n\) locations called knots and into an interval \([a,b]\). A B-spline function of \(k\) order on a given set of \(k\) knots can be written as a linear combination:  
\[\sum_{i=1}^{m+k}\alpha_{i}B_{i,k}(x), \tag{1}\]  
where \(\alpha_{i}\) are B-spline coefficients and \(B_{i,k}(x)\) are the basis function of \(k\) order obtained by means of the recursive formula Cox-de Boor  
\[B_{i,k}(x)=\frac{x-t_{i}}{t_{i+k-1}-t_{i}}B_{i,k-1}(x)+\frac{t_{i+k}-x}{t_{i+k }-t_{i+1}}B_{i+1,k-1}(x) \tag{2}\]  
\begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Problem** & **Technique** & **Platform** & **Technology** & **Reference** \\ \hline Travelling salesman & Genetic Algorithms & GPU & CUDA & [21] \\ \hline Travelling salesman & Ant Colony & GPU, CPU & OpenCL & [22] \\ \hline Traveling salesman & & & & \\ problem & Ant Colony & GPU, CPU & OpenCL & [23] \\ \hline Financial Forecasting & Genetic & & & \\ Algorithm & Programming & GPU, CPU & OpenCL & [25] \\ \hline Automatic path & & & & \\ planning & Genetic Algorithm & GPU & CUDA & [24] \\ \hline Tree evaluation & Genetic Algorithms & GPU, CPU & OpenCL & [26] \\ \hline Flow shop & & & & \\ scheduling & Genetic Algorithms & GPU & CUDA & [27] \\ \hline Optimization of & & & & \\ composite laminate & Genetic Algorithms & CPU & OpenMP, MPI & [28] \\ plates & & & & \\ \hline Optimization of & & & & \\ composite laminate & Particle Swarm, & & & \\ plates & Genetic Algorithms & CPU & MPI & [29] \\ \hline Search engine & & & & \\ Programming & CPU & MPI & [30] \\ \hline Quadratic & & & & \\ Assignment Problem & Particle Swarm & GPU & OpenCL & [18] \\ \hline Molecular docking & Genetic Algorithms & GPU & & \\ \hline Molecular dynamics & Particle Swarm, & & & \\ simulation & Genetic Algorithms & GPU, CPU & OpenMP, CUDA & [32] \\ \hline \hline \end{tabular}
\end{table}
Table 1: Overview of parallel metaheuristic implementations.  
\[B_{i,1}(x)=\left\{\begin{array}{ll}1,&\text{if }t_{i}<x<t_{i+1}\\ 0,&\text{otherwise}\end{array}\right., \tag{3}\]  
where \(t_{i}\) is an element of the knot vector \(t=t_{1},...,t_{m+2k}\) defined by:  
\[t_{i}=\left\{\begin{array}{ll}a,&\text{if }i\leq k\\ \tau_{i-k},&\text{if }k<i<k+m\\ b,&\text{if }i\geq+m\end{array}\right., \tag{4}\]  
with \(\tau_{1},...,\tau_{1}\) a set of \(m\) interior knots placed along the domain of \(x\), such that \(a=x_{1}<\tau_{1}<...<\tau_{m}<x_{n}=b\).  
If the order \(k\) for B-spline is defined beforehand, a B-spline function \(f\) can be defined completely by pairs \(\theta=\{\tau,\alpha\}\), where \(\tau=\{\tau_{1},...,\tau_{m}\}\) and \(\alpha=\{\alpha_{1},...,\alpha_{m}\}\). Then, the challenge is to find de number of knots \(\tau_{i}\), and their coefficients \(\alpha_{i}\). A more detailed discussion of B-splines can be found in [34; 35].