Parallel Hierarchical Genetic Algorithm for Scattered Data Fitting through B-Splines

Jose Edgar Lara-Ramirez; Carlos Hugo Garcia-Capulin; Maria de Jesus Estudillo-Ayala; Juan Gabriel Avina-Cervantes; Raul Enrique Sanchez-Yanez; Horacio Rostro-Gonzalez

doi:10.3390/app9112336

journal article Open Access Jun 06, 2019

Parallel Hierarchical Genetic Algorithm for Scattered Data Fitting through B-Splines

Jose Edgar Lara-Ramirez

Carlos Hugo Garcia-Capulin

Maria de Jesus Estudillo-Ayala Juan Gabriel Avina-Cervantes

Raul Enrique Sanchez-Yanez

Horacio Rostro-Gonzalez

Applied Sciences Vol. 9 No. 11 pp. 2336 · MDPI AG

View at Publisher Save 10.3390/app9112336

Abstract

Curve fitting to unorganized data points is a very challenging problem that arises in a wide variety of scientific and engineering applications. Given a set of scattered and noisy data points, the goal is to construct a curve that corresponds to the best estimate of the unknown underlying relationship between two variables. Although many papers have addressed the problem, this remains very challenging. In this paper we propose to solve the curve fitting problem to noisy scattered data using a parallel hierarchical genetic algorithm and B-splines. We use a novel hierarchical structure to represent both the model structure and the model parameters. The best B-spline model is searched using bi-objective fitness function. As a result, our method determines the number and locations of the knots, and the B-spline coefficients simultaneously and automatically. In addition, to accelerate the estimation of B-spline parameters the algorithm is implemented with two levels of parallelism, taking advantages of the new hardware platforms. Finally, to validate our approach, we fitted curves from scattered noisy points and results were compared through numerical simulations with several methods, which are widely used in fitting tasks. Results show a better performance on the reference methods.

Topics

No keywords indexed for this article. Browse by subject →

References

51

[1]

Wendland, H. (2004). Scattered Data Approximation, Cambridge University Press. 10.1017/cbo9780511617539

[2]

Johnson "Scattered data reconstruction by regularization in B-spline and associated wavelet spaces" J. Approx. Theory (2009) 10.1016/j.jat.2009.02.005

[3]

Lee "Scattered Data Interpolation with Multilevel B-Splines" IEEE Trans. Vis. Comput. Graph. (1997) 10.1109/2945.620490

[4]

Martin, R., Sabin, M., and Winkler, J. (2007). Scattered Data Fitting on Surfaces Using Projected Powell-Sabin Splines. Proceedings of the Mathematics of Surfaces XII: 12th IMA International Conference, Sheffield, UK, 4–6 September 2007, Springer.

[5]

Tjahjowidodo, T., Dung, V., and Han, M. (2015, January 7–11). A fast non-uniform knots placement method for B-spline fitting. Proceedings of the 2015 IEEE International Conference on Advanced Intelligent Mechatronics (AIM), Busan, Korea. 10.1109/aim.2015.7222752

[6]

Li "A Heuristic Knot Placement Algorithm for B-Spline Curve Approximation" Comput.-Aided Des. Appl. (2004) 10.1080/16864360.2004.10738319

[7]

Adaptation in Natural and Artificial Systems

John H. Holland

10.7551/mitpress/1090.001.0001

[8]

Luque, G., and Alba, E. (2011). Parallel Models for Genetic Algorithms. Parallel Genetic Algorithms: Theory and Real World Applications, Springer. 10.1007/978-3-642-22084-5

[9]

Iske "Scattered data approximation by positive definite kernel functions" Rend. Semin. Mat. Univ. Politec. Torino (2011)

[10]

Ardjmand "Applying genetic algorithm to a new bi-objective stochastic model for transportation, location, and allocation of hazardous materials" Expert Syst. Appl. (2016) 10.1016/j.eswa.2015.12.036

[11]

Shahvari "Hybrid flow shop batching and scheduling with a bi-criteria objective" Int. J. Prod. Econ. (2016) 10.1016/j.ijpe.2016.06.005

[12]

Shahvari "An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes" Comput. Oper. Res. (2017) 10.1016/j.cor.2016.07.021

[13]

Shahvari "An efficient tabu search algorithm for flexible flow shop sequence-dependent group scheduling problems" Int. J. Prod. Res. (2012) 10.1080/00207543.2011.604051

[14]

Glover "Tabu search—Part I" ORSA J. Comput. (1989) 10.1287/ijoc.1.3.190

[15]

Piniganti, L. (2014). A Survey of Tabu Search in Combinatorial Optimization. [Master’s Thesis, University of Nevada].

[16]

Glover "Tabu Search for nonlinear and parametric optimization (with links to genetic algorithms)" Discret. Appl. Math. (1994) 10.1016/0166-218x(94)90211-9

[17]

Cuevas "A hierarchical genetic algorithm approach for curve fitting with B-splines" Genet. Program. Evol. Mach. (2015) 10.1007/s10710-014-9231-3

[18]

Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., and Zurada, J.M. (2015). OpenCL Implementation of PSO Algorithm for the Quadratic Assignment Problem. Artificial Intelligence and Soft Computing, Springer International Publishing.

[19]

Yoshimura "Hierarchical Parallel Processes of Genetic Algorithms for Design Optimization of Large-Scale Products" J. Mech. Des. (2004) 10.1115/1.1666889

[20]

Lim "Efficient Hierarchical Parallel Genetic Algorithms using Grid computing" Future Gener. Comput. Syst. (2007) 10.1016/j.future.2006.10.008

[21]

Plichta, A., Gaciarz, T., Baranowski, B., and Szominski, S. (2014, January 27–30). Implementation of the genetic algorithm by means of CUDA technology involved in travelling salesman problem. Proceedings of the 28th European Conference on Modelling and Simulation (ECMS), Brescia, Italy. 10.7148/2014-0475

[22]

Bhardwaj "Parallel Implementation of Travelling Salesman Problem using Ant Colony Optimization" Int. J. Comput. Appl. Technol. Res. (2014)

[23]

Zhou "Parallel ant colony optimization on multi-core SIMD CPUs" Future Gener. Comput. Syst. (2018) 10.1016/j.future.2017.09.073

[24]

Parallel genetic algorithm based automatic path planning for crane lifting in complex environments

Panpan Cai, Yiyu Cai, Indhumathi Chandrasekaran et al.

Automation in Construction 2016 10.1016/j.autcon.2015.09.007

[25]

Brookhouse, J., Otero, F.E.B., and Kampouridis, M. (2014, January 12–16). Working with OpenCL to speed up a genetic programming financial forecasting algorithm: Initial results. Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO Comp ’14), Vancouver, BC, Canada. 10.1145/2598394.2605689

[26]

Augusto "Accelerated parallel genetic programming tree evaluation with OpenCL" J. Parallel Distrib. Comput. (2013) 10.1016/j.jpdc.2012.01.012

[27]

Huang "Modified genetic algorithms for solving fuzzy flow shop scheduling problems and their implementation with CUDA" Expert Syst. Appl. (2012) 10.1016/j.eswa.2011.10.013

[28]

Rocha "A hybrid shared/distributed memory parallel genetic algorithm for optimization of laminate composites" Compos. Struct. (2014) 10.1016/j.compstruct.2013.07.049

[29]

Omkar "MPI-based parallel synchronous vector evaluated particle swarm optimization for multi-objective design optimization of composite structures" Eng. Appl. Artif. Intell. (2012) 10.1016/j.engappai.2012.05.019

[30]

Walker "Search engine case study: Searching the web using genetic programming and MPI" Parallel Comput. (2001) 10.1016/s0167-8191(00)00089-2

[31]

Prades "Enhancing large-scale docking simulation on heterogeneous systems: An MPI vs. rCUDA study" Future Gener. Comput. Syst. (2018) 10.1016/j.future.2017.08.050

[32]

Li "A hybrid particle swarm optimization algorithm for load balancing of MDS on heterogeneous computing systems" Neurocomputing (2019) 10.1016/j.neucom.2018.11.034

[33]

Spanos "Curve Fitting, the Reliability of Inductive Inference, and the Error-Statistical Approach" Philos. Sci. (2007) 10.1086/525643

[34]

Boor, C.D. (2001). A Practical Guide to Splines, Springer. Applied Mathematical Sciences.

[35]

Piegl, L., and Tiller, W. (1997). The NURBS Book, Springer. Monographs in Visual Communication. 10.1007/978-3-642-59223-2

[36]

Jong, E.D.D., Watson, R.A., and Thierens, D. (2005, January 25–29). On the Complexity of Hierarchical Problem Solving. Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation (GECCO ’05), Washington, DC, USA.

[37]

Man, K.F., Tang, K.S., and Kwong, S. (1999). Genetic Algorithms: Concepts and Designs, Springer. [2nd ed.]. Advanced Textbooks in Control and Signal Processing. 10.1007/978-1-4471-0577-0

[38]

Jong, E.D.D., Thierens, D., and Watson, R.A. (2004, January 18–22). Hierarchical Genetic Algorithms. Proceedings of the Parallel Problem Solving from Nature—PPSN VIII: 8th International Conference, Birmingham, UK.

[39]

Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc.

[40]

A new look at the statistical model identification

H. Akaike

IEEE Transactions on Automatic Control 1974 10.1109/tac.1974.1100705

[41]

Lee "Regression spline smoothing using the minimum description length principle" Stat. Probab. Lett. (2000) 10.1016/s0167-7152(99)00191-1

[42]

Mitchell, M. (1998). An Introduction to Genetic Algorithms, MIT Press. A Bradford Book.

[43]

Sivanandam, S., and Deepa, S. (2008). Introduction to Genetic Algorithms, Springer.

[44]

Deb "Simulated Binary Crossover for Continuous Search Space" Complex Syst. (1995)

[45]

Alba "A Survey of Parallel Distributed Genetic Algorithms" Complex (1999) 10.1002/(sici)1099-0526(199903/04)4:4<31::aid-cplx5>3.0.co;2-4

[46]

Belding, T.C. The Distributed Genetic Algorithm Revisited. Proceedings of the 6th International Conference on Genetic Algorithms.

[47]

Rucinski "On the impact of the migration topology on the Island Model" Parallel Computing. (2010) 10.1016/j.parco.2010.04.002

[48]

Dimatteo "Bayesian curve-fitting with free-knot splines" Biometrika (2001) 10.1093/biomet/88.4.1055

[49]

Denison "Automatic Bayesian Curve Fitting" J. R. Stat. Soc. Ser. B (Stat. Methodol.) (1998) 10.1111/1467-9868.00128

[50]

Pittman "Adaptive Splines and Genetic Algorithms" J. Comput. Graph. Stat. (2002) 10.1198/106186002448

Showing 50 of 51 references

Metrics

9

Citations

51

References

Details

Published: Jun 06, 2019
Vol/Issue: 9(11)
Pages: 2336
License: View

Authors

J

Jose Edgar Lara-Ramirez

Department of Electronics, University of Guanajuato, Salamanca 36885, Mexico; School of Biological Systems and Technological Innovation, Benito Juárez Autonomous University of Oaxaca, Oaxaca 68020, Mexico

C

Carlos Hugo Garcia-Capulin

Department of Electronics, University of Guanajuato, Salamanca 36885, Mexico

M

Maria de Jesus Estudillo-Ayala

Department of Electronics, University of Guanajuato, Salamanca 36885, Mexico; School of Biological Systems and Technological Innovation, Benito Juárez Autonomous University of Oaxaca, Oaxaca 68020, Mexico

J

Juan Gabriel Avina-Cervantes

Department of Electronics, University of Guanajuato, Salamanca 36885, Mexico

R

Raul Enrique Sanchez-Yanez

Department of Electronics, University of Guanajuato, Salamanca 36885, Mexico

H

Horacio Rostro-Gonzalez

Department of Electronics, University of Guanajuato, Salamanca 36885, Mexico

Funding

Consejo Nacional de Ciencia y Tecnología Award: FC2016-1961

Cite This Article

Jose Edgar Lara-Ramirez, Carlos Hugo Garcia-Capulin, Maria de Jesus Estudillo-Ayala, et al. (2019). Parallel Hierarchical Genetic Algorithm for Scattered Data Fitting through B-Splines. Applied Sciences, 9(11), 2336. https://doi.org/10.3390/app9112336

Parallel Hierarchical Genetic Algorithm for Scattered Data Fitting through B-Splines

You May Also Like