Evolutionary computation for optimal knots allocation in smoothing splines of one or two variables

P. González; H. Idais; M. Pasadas; M. Yasin

doi:10.2991/ijcis.11.1.96

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 11, Issue 1, 2018, Pages 1294 - 1306

Evolutionary computation for optimal knots allocation in smoothing splines of one or two variables

Authors

P. Gonzálezprodelas@ugr.es, H. Idais^*^,hasan@correo.ugr.es, M. Pasadasmpasadas@ugr.es, M. Yasinyaseen@correo.ugr.es

Dept. of Applied Mathematics, University of Granada, Granada, 18071, Spain

^*

Email:hasan@correo.ugr.es

Received 6 February 2018, Accepted 11 July 2018, Available Online 26 July 2018.

DOI: 10.2991/ijcis.11.1.96 How to use a DOI?
Keywords: Approximation; Smoothing; Knots allocation; Bi-cubic splines
Abstract: Curve and surface fitting are important and attractive problems in many applied domains, from CAD techniques to geological prospections. Different methodologies have been developed to find a curve or a surface that best describes some 2D or 3D data, or just to approximate some function of one or several variables. In this paper, a new methodology is presented for optimal knots’ placement when approximating functions of one or two variables. When approximating, or fitting, a surface to a given data set inside a rectangle using B-splines, the main idea is to use an appropriate multi-objective genetic algorithm to optimize both the number of random knots and their optimal placement both in the x and y intervals, defining the corresponding rectangle. In any case, we will use cubic B-splines in one variable and a tensor product procedure to construct the corresponding bicubic B-spline basis functions in two variables. The proposed methodology has been tested both for functions of one or two independent variables, in order to evaluate the performance and possible issues of the procedure.
Copyright: © 2018, the Authors. Published by Atlantis Press.
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

1. Introduction

Function approximation, and curve/surface fitting to data, are major and important problems in many applied technical and scientific fields: as in CAD design, virtual reality and computer animation, data visualization of geological and medical imaging, artificial vision or scientific computing in general ¹⁰, ¹⁶.On the other hand, there are several different methodologies that have been used for selecting knots for best approximating or fitting curves/surfaces to data using B-splines. For instance, the methodology in ³ uses a least squares fitting method with B-spline surfaces, depending on a sensitive parametrization, in connection with a uniform distribution of knots. In the last decades, an increasing number of works and algorithms have been developed for this problem of approximating or fitting a surface to data using splines. For example, the authors in ¹⁴ developed a genetic algorithm to optimize both the number and the allocation of knots, in spline approximation of bio-medical data. Later, a new approach was introduced to improve the knot adjustment for B-spline curves, by using an appropriate elitist clonal selection algorithm ⁴. The methodology in ¹⁸ describe an iterative algorithm, that can also use heuristic criteria, for the optimal knots distribution in B-spline surface fitting. Kozera et al. in ⁸ gave a new method for choosing unknown knots that minimize the cost function, by using a special scale. Also, the development of surface fitting include several types of splines, for example some techniques without grids for medical image registration, by modification of several selected knots in P-splines ¹¹. The method in ¹⁷ describes the unified averaging technique, for both approximation and interpolation problems, concerning knots placement for B-spline curves. In ⁵ is presented a method to solve the curve fitting problem, using a hierarchical genetic algorithm (HGA). A computational methodology, based on the so called Artificial Immune Systems (AIS) paradigm, is used to solve the knots’ adjustment problem for B-spline curves. The goal of the application of this algorithm is to determine the location of knots automatically and efficiently. In ¹² the authors describe a powerful methodology, based on simulated annealing (SA), for optimal placement of the knots. Also the authors in ⁶ use sparse optimization techniques for this purpose. However, as pointed out in ¹³ and many other related works, a final and definitive methodology for optimal placement and selection of knots, for approximating/fitting curves or surfaces to data, using smoothing splines, is not still completely investigated, even in the one dimensional case.

In this paper we propose a new methodology for optimal placement of random knots, for approximating/fitting curves or surfaces to data, using cubic smoothing splines of one or two independent variables. A new technique is presented to optimize both the number of knots and its optimal placement by cubic spline approximations, using a developed multi-objective genetic algorithm. Our scheme give very accurate results, even for curves or surfaces with discontinuities and/or cusps; it also determines the optimal number of knots automatically.

The paper is organized as follows: after this Introduction, Section 2 presents the basic definitions concerning multi-objective optimization problems; in Section 3 the proposed methodology for smoothing approximation with bicubic splines is explained in detail; in Section 4 we present the optimization strategy for placement of the knots in bi-cubic smoothing splines; in Section 5 we show some results that confirm the performance of the proposed methodology; and some final conclusions are drawn in section 6.

2. Basic definitions and ideas about multi-objective optimization problems

Definition 1.

In general, a multi-dimensional optimization problem consists in searching for the minimum of a function f : ℝ^N → ℝ such that there exists s ∈ ℝ^N with f (s) ⩽ f(x) for all x ∈ ℝ^N. The function f(x) is called the fitness or cost function, for that optimization problem.

But a multi-evaluated or multi-objective problem (see ²) always tries to optimize more than one parameter or function at the same time. The multiobjective optimization problems are important not only in Mathematics, because they can also be very effective in Physics, Engineering and many other scientific fields. We give now the definition

Definition 2.

A multi-objective optimization problem can be viewed as a quadruple (X, Y, f, ξ), where X indicates the search or decision space, Y denotes the objective space, being f : X → Y a function that assigns to each x ∈ X a corresponding objective vector y = f(x) ∈ Y; ξ is a binary relation over Y that characterizes a partial order on the objective space.

So, the main idea is trying to minimize all the objective functions in Y at the same time, to obtain the optimal solution. At the end, the goal is to get at least one solution that is one of the best; because not always it will be clear what is the “best” one, and we can have an entire set (called Pareto front) of possible best solutions.

3. Proposed Methodology

3.1. Introduction.

In this section we extend the classical cubic B-splines of class 𝒞² in one independent variable, to the bicubic B-splines of class 𝒞² of two independent variables. For this, let a, b, c, d ∈ ℝ and consider R = [a, b] × [c, d].

3.2. Bicubic spline spaces of class 𝒞².

Bicubic splines of two variables are an extension of cubic splines in one variable. We start with two partitions or knot sequences of [a, b] in m subintervals and [c, d] in n subintervals; i.e. increasing sequences, that can be uniform or not.

Let denote Δ_m and Δ_n the two partitions of [a, b] and [c, d] respectively, where Δ_m ≡ {a = x₀ < x₁ < ... < x_m = b} and Δ_n ≡ {c = y₀ < y₁ < ... < y_n = d}.

We define the bicubic spline functions

S:[a,b]×[c,d]→ℝ

such that:

i)
S ∈ 𝒞²([a, b] × [c, d]),
ii)
S |_{[x_i, x_i+1]} × _{[y_j, y_j+1]} ∈ ℙ₃([x_i, x_i+1] × [y_j, y_j+1]), i = 0, ..., m −1, j = 0, ..., n−1,

where ℙ₃([x_i, x_i+1] × [y_j, y_j+1]) is the space of all restrictions of two-variable polynomials of partial degree less than or equal to three on the rectangle [x_i, x_i+1] × [y_j, y_j+1].

Given x₋₃, x₋₂, x₋₁, x_m+1, x_m+2, x_m+3 and y₋₃, y₋₂, y₋₁, y_n+1, y_n+2, y_n+3 real numbers, such that,

x−3≤x−2≤x−1≤a<b≤xm+1≤xm+2≤xm+3,y−3≤y−2≤y−1≤c<d≤yn+1≤yn+2≤yn+3,

then

(1)Bi0(x)={1,xi−3⩽x<xi−20,otherwise,i=0,…m+5

and Bik(x) , k = 1, 2, 3,... can be defined from the recursive relation, for i = 0, ..., m + 5 − k:

(2)Bik(x)=x−xi−3xi+k−3−xi−3Bik−1(x)=xi+k−2−xxi+k−2−xi−2Bi+1k−1(x).

These functions verify the following properties:

i)
they are positive in the interior of their support,
Bik(x)⩾0,∀x∈[a,b];
ii)
they form a partition of unity,
∑i=0m+5−kBik(x)=1,∀x∈[a,b];
iii)
{B0k,…,Bm+5−kk} are linearly independent for all k = 0, 1, 2, 3....

We consider the analogous definitions (1,2), in the variable y, of the functions {B0k,…,Bn+5−kk} for the partition in [c,d].

Meanwhile, if 𝒮₃(Δ_m × Δ_n) represents the set of bi-cubic spline functions of degree less than or equal to three and class 𝒞², then dim 𝒮₃(Δ_m × Δ_n) = (m + 3)(n + 3); and if {B03(x),…,Bm+23(x)} and {B03(y),…,Bn+23(y)} are the basis of 𝒮₃(Δ_m) and 𝒮₃(Δ_n) respectively, then a basis of 𝒮₃(Δ_m × Δ_n) will be

{Bq3(x,y)≡Bi3(x)Bj3(y),i=0,…,m+2,j=0,…,n+2,q=(m+3)j+i+1}.

3.3. Formulation of the problem

The main goal of this section is to solve the following problem: Given the data sets

{ul:l=1,…,N}⊂R⊂ℝ2

and

{βl:l=1,…,N}⊂ℝ,

find S ∈ 𝒮₃(Δ_m × Δ_n) such that

S(ul)≈βl,∀l=1,…,N

i.e. S approximates the data set

{(ul,βl)∈R×ℝ}l=1N.

We define the smoothing variational bicubic spline associated with U = {u_l}_{l=1, ..., N} ⊂ R, {β_l}_{l=1, ..., N} ⊂ ℝ, and ɛ ∈ (0, ∞) as the unique S ∈ 𝒮₃(Δ_m × Δ_n) minimizing the functional

J=𝒮3(△m×△n)→[0,∞)

defined by

(3)J(v)= ∑l=1N(βl−v(ul))2

(4)+ɛ∑|α|=2∫ab∫cd(∂αv(x,y))2dxdy

where |α| = α₁ + α₂, ∀α = (α₁, α₂) ∈ℕ², and ∂αv(x,y)≡∂|α|v∂xα1∂yα2 .

This problem has a unique solution (see⁷) that can be expressed as a linear combination of our bicubic basis functions

S(x,y)≡∑q=1(m+3)(n+3)αqBq3(x,y), (x,y)∈R.

where α = (α₁, ..., α_(m+3)(n+3)) is the unique solution of the following linear system

(AA⊤+εR)α⊤=Aβ⊤

being A ∈ ℝ⁽^m⁺³⁾⁽ⁿ^+3),^N and R ∈ ℝ⁽^m⁺³⁾⁽ⁿ⁺³⁾^,⁽^m⁺³⁾⁽ⁿ⁺³⁾

A=(Bq3(xl,yl))q=1,…,(m+3)(m+3)l=1,…,N,

R=(∑|α|=2∫ab∫cd∂αBr3(x,y)∂αBs3(x,y)dxdy)r,s.

The corresponding formulation in the one variable case is just evident and may be written easily from this general formulation in two variables. It is also well known, and may be consulted in ¹³ and the references therein.

4. Optimization strategy for knots’ placement in the cases of cubic and bicubic smoothing splines

In order to verify the ability of the new multiobjective strategy for the determination of the knots placement for the proposed bicubic smoothing splines, we will use at least two approximate discretizations of normalized error estimations, in 𝒞(R) and ℒ²(R) for example, given by the expressions:

(5)Ec≡maxi=1,…,M|f(ai)−S(ai)|maxi=1,…,M|f(ai)|

(6)El≡∑i=1M(f(ai)−S(ai))2∑i=1M(f(ai))2

where f ∈ 𝒞²(R) is the function we want to approximate, S ∈ 𝒮₃(Δ_m × Δ_n) is the smoothing variational bicubic spline associated with the given data sets and {a₁, ..., a_M} ⊂ R is a given random point set where the errors will be computed. In the case of functions of only one variable (or 2D point sets), the expressions are totally equivalent, changing the rectangle R by the corresponding interval of real numbers.

We will be using a Non-dominated Sorting Genetic Algorithm (NSGA); that is, a Multiple Objective Optimization Genetic Algorithm (MOGA) whose objective is to improve the adaptive fit of a population of candidate solutions to a Pareto front, constrained by a set of objective functions. In this paper the algorithm developed to obtain optimal knots placement of B-spline basis functions uses an evolutionary methodology, with replacement and the usual operators, including: selection, genetic crossover, and mutation.

For the correct use of the NSGA-II algorithm (an important improvement of the original NSGA one, see ¹) it is necessary to describe three fundamental issues:

(i)
Solution Representation: The chosen representation characterizes each individual of interest to be evaluated. The representation determines how the problem is structured in the NSGA-II and also determines its behavior.
(ii)
Genetic Operators: We must define some important parameters before running any MOGA algorithm. The important agents in this part are ¹:
1. (a)
  Number of Generations: We can use 5 or more generations, but in this work we usually take 20 to 40 generations as stopping criteria of the algorithm, depending on the case.
2. (b)
  Population size: This number determines the number of possible good candidates to be taken into account in all the genetic process. Depending on the problem, we are using a population size of about 20 or more members.
3. (c)
  Selection function: The selection function chooses the individuals, called parents, that contribute to the population at the next generation.
4. (d)
  Crossover and mutation functions: in this algorithm, we use binary crossover function which combines two parents to form children for the next generation; the crossover fraction is 0.9 and use polynomial mutation.
5. (e)
  Pareto fraction: It keeps the others than most fit population down to the specified fraction in order to maintain a diversity of the population; a value of 0.4 is of common use in this case.
(iii)
Fitness function: different forms can be used in a NSGA-II algorithm; but the main goal is to minimize the errors E_c and E_l, between the original function and the smoothing variational bicubic spline constructed from each population of random knots.

5. Simulation examples

The objective of this study is to analyze the performance of the explained MOGA procedure for the optimization of the knots placement for the construction of B-spline basis functions in order to obtain an optimal approximating cubic or bicubic spline.

Different experiments have been carried out, both with functions of one and two variables. In this section, we will show the results of approximations for each of these functions, and we present the evolution of the optimal distribution of knots, together with the related Pareto fronts, using the proposed methodology.

5.1. Examples of one independent variable

The examples below are mainly chosen from the existent literature on the subject in the 1D case: example 1 coincide with the example 3 in ¹³, and the examples 3 and 4 have been also extracted from the simulations included in the papers ¹⁵ and ⁹, respectively.

Example 1:

f₁ : [0, 1] → ℝ

f1(x)=90/(1+e100(x−0.4)).

Example 2:

f₂ : [0, π] → ℝ

f2(x)=0.12+0.25e−4(x−π4)2cos(2x)sin(2πx).

Example 3:

f₃ : [0, 4π] → ℝ

f3(x)=0.2e−.05xsin(5x)+0.4.

Example 4:

f₄ : [−1, 1] → ℝ

f4(x)=1−e−50|x|.

To test the behavior of the presented methodology for the optimization of knots placement of the B-spline basis in this case, all the procedure have been also adapted to this one-dimensional case. Not a large number of knots have been necessary to obtain sufficiently good results, as you can see in the corresponding figures.

We can also see clearly, in the right column of Figure 1, how the evolution of the knots’ distribution tends to be located in the region where the function f₁(x) change the most within its domain. The left column also shows the results of the approximating function, compared with the original one, using this B-spline function approximation. The corresponding Pareto front, taking also into account one of the errors in the approximations vs. the number of knots used, is shown in Figure 2.

We can view clearly in all these cases that our results are quite better than the corresponding results included in the specified articles, with less interior knots; and always obtaining lower errors when using the same number of them or less number of generations.

Now we show in Figure 5 our results (with discrete errors of orders of 10⁻⁴ and 10⁻⁵ in any case) for the Example 3, also used as test example in ¹⁵.

And finally, in Figure 6 some graphical and numerical result for the Example 4, also considered in a classical paper ⁹ about this subject.

5.2. Examples of functions of two independent variables

We begin with a quite simple example of a paraboloid of revolution in the following example

Example 5:

F₅ : [0, 1] × [0, 1] → ℝ

F5(x,y)=x2+y2.

In order to analyze the behavior of the B-spline approximation in these cases, not too many knots will be used (just 10 to 20 knots in each variable interval). In Figure 7 it can be seen some particular results of the approximation of function F₅(x, y) using bi-cubic smoothing variational splines.

Similar results can be obtained for a more complicated Example 6, where the well-known Franke’s function is considered. Graphics in Figure 9 show the results of the approximation with Bi-cubic smoothing variational splines in this case.

6. Conclusions

In this paper, a novel evolutionary MOGA methodology is presented for knots placement in the problem of cubic spline approximation of functions of one or two variables, showing the effectiveness of the strategy for different types of functions.

So, the goal of using a MOGA for placement of the knots in such cases of approximating functions by cubic or bi-cubic splines, of one or two variables, respectively, can be summarized as follows:

Example 6:

F₆ : [0, 1] × [0, 1] → ℝ

F6(x,y):=34e−((9x−2)2+(9y−2)2)/4+34e−((9x+1)2/49−(9y+1)/10)+12e−((9x−7)2+(9y−3)2)/4−15e−((9x−4)2+(9y−7)2).

Figures 8 and 10 represent the Pareto fronts for the application of this MOGA procedure to these last two examples. It is clear that the errors with the MOGA tends to be reduced when the number of knots to construct the smoothing B-spline basis increases, but also increases (significantly in this case) the corresponding computational effort.

(1)
It has been sufficiently proven that the placement of the knots in spline approximation has an important and considerable effect on the behavior of the final results, but the optimal placement or location of knots is not known a priori;
(2)
The number of knots to be used in classical approaches, should be selected a priori by the designer; but using MOGA, a Pareto front for different or variable number of knots used can also be directly optimized.

Many simulations have been carried out, showing that increasing the number of knots in the definition of the cubic, or bi-cubic B-splines, also increases the accuracy of the approximation, but only up to a certain limit, where the corresponding computation effort is not worth enough comparing with the small possible reduction in the corresponding errors. So we can affirm without any doubt, that this proposed procedure have much better performance and results than such as the selected knots within an equally spaced distribution of them, and many other classical approaches.

References

1.K Deb, A Pratap, S Agarwal, and T Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. on Evol. Comput, Vol. 6, No. 2, 2002, pp. 182-197.

2.M Emmerich and A Deutz, Multicriteria Optimization and Decision Making, Autumn/Winter, 2006. LIACS Master Course

3.Y-K Lai, S-M Hu, and H Pottmann, Surface fitting based on a feature sensitive parametrization, Computer-Aided Design, Vol. 38, 2006, pp. 800-807.

4.A Gálvez, A Iglesias, A Avila, C Otero, R Arias, and C Manchadoca, Elitist clonal selection algorithm for optimal choice of free knots in B-spline data fitting, Applied Soft Computing, Vol. 26, 2015, pp. 90-106.

5.CH García-Capulín, FJ Cuevas, G Trejo-Caballero, and H Rostro-González, A hierarchical genetic algorithm approach for curve fitting with B-splines, Genet. Program. Evolvable Machines, Vol. 16, 2015, pp. 151-166.

6.H Kang, F Chen, Y Li, J Deng, and Z Yang, Knot calculation for spline fitting via sparse optimization, Computer-Aided Design, Vol. 58, 2015, pp. 179-188.

7.A Kouibia and M Pasadas, Approximation of surfaces by fairness bicubic splines, Advances in Computational Mathematics, Vol. 20, No. 1–3, 2004, pp. 455-467.

8.R Kozera and L Noakes, Optimal Knots Selection for Sparse Reduced Data, Springer International Publishing Switzerland, Vol. LNCS 9555, 2016, pp. 3-14.

9.T Lyche and K Mørken, A data-reduction strategy for splines with applications to the approximation of functions and data, IMA Journal of Numerical Analysis, Vol. 8, 1998, pp. 185-208.

10.H Pottmann, S Leopoldseder, M Hofer, T Steiner, and W Wang, Industrial geometry: recent advances and applications in CAD, Comput. Aided Des, Vol. 37, 2005, pp. 751-766.

11.S Prahan and D Patra, Non-grid medical image registration using adaptive knot selection in P-spline, IEEE Students Technology Symosium, 2016, pp. 250-254.

12.O Valenzuela and M Pasadas, Using simulated annealing for knot placement for cubic spline approximation, Math. Models Eng. Sci, 2010, pp. 148-154.

13.O Valenzuela, B Delgado-Márquez, and M Pasadas, Evolutionary computation for optimal knots allocation in smoothing splines, Applied Mathematical Modelling, Vol. 37, 2013, pp. 5851-5863.

14.O Valenzuela, M Pasadas, F Ortuño, and I Rojas, Optimal Knots Allocation in Smoothing Splines using intelligent system, IWBBIO, 2013.

15.O Valenzuela, M Pasadas, I Rojas, A Guillén, and H Pomares, Automatic Knot Asjustment For B-Spline Smoothing Approximation Using Improved Clustering Algorithm, in IEEE International Conference on Fuzzy Systems (2013).

16.T Varady and RR Martin, Reverse engineering, G Farin, J Hoschek, and M Kim (editors), Handbook of Computer Aided Geometric Design, Elsevier Science, 2002.

17.Wei Wang, Fazhong Shi, Gang Zhao, and Xiaoxiao Du, A new method for knot placement of B-Spline curve approximation and interpolation, in 3rd International Conference on Materials Engineering, Manufacturing Technology and Control (ICMEMTC 2016), pp. 1527-1532.

18.Yuhua Zhang, Juan Cao, Zhonggui Chen, Xin Li, and Xiao-Ming Zeng, B-spline surface fitting with knot position optimization, Computer and Graphic, Vol. 58, 2016, pp. 73-83.

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 11 - 1
Pages: 1294 - 1306
Publication Date: 2018/07/26
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.11.1.96 How to use a DOI?
Open Access: This is an open access article under the CC BY-NC license (http://creativecommons.org/licences/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - P. González
AU  - H. Idais
AU  - M. Pasadas
AU  - M. Yasin
PY  - 2018
DA  - 2018/07/26
TI  - Evolutionary computation for optimal knots allocation in smoothing splines of one or two variables
JO  - International Journal of Computational Intelligence Systems
SP  - 1294
EP  - 1306
VL  - 11
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.11.1.96
DO  - 10.2991/ijcis.11.1.96
ID  - González2018
ER  -

download .riscopy to clipboard

International Journal of Computational Intelligence Systems

Evolutionary computation for optimal knots allocation in smoothing splines of one or two variables

1. Introduction

2. Basic definitions and ideas about multi-objective optimization problems

Definition 1.

Definition 2.

3. Proposed Methodology

3.1. Introduction.

3.2. Bicubic spline spaces of class 𝒞2.

3.3. Formulation of the problem

4. Optimization strategy for knots’ placement in the cases of cubic and bicubic smoothing splines

5. Simulation examples

5.1. Examples of one independent variable

Example 1:

Example 2:

Example 3:

Example 4:

5.2. Examples of functions of two independent variables

Example 5:

6. Conclusions

Example 6:

References

Cite this article

3.2. Bicubic spline spaces of class 𝒞².