Journal Home > Volume 1 , Issue 1

Nonlinear Equations (NEs), which may usually have multiple roots, are ubiquitous in diverse fields. One of the main purposes of solving NEs is to locate as many roots as possible simultaneously in a single run, however, it is a difficult and challenging task in numerical computation. In recent years, Intelligent Optimization Algorithms (IOAs) have shown to be particularly effective in solving NEs. This paper provides a comprehensive survey on IOAs that have been exploited to locate multiple roots of NEs. This paper first revisits the fundamental definition of NEs and reviews the most recent development of the transformation techniques. Then, solving NEs with IOAs is reviewed, followed by the benchmark functions and the performance comparison of several state-of-the-art algorithms. Finally, this paper points out the challenges and some possible open issues for solving NEs.


menu
Abstract
Full text
Outline
About this article

Nonlinear Equations Solving with Intelligent Optimization Algorithms: A Survey

Show Author's information Wenyin GongZuowen Liao*( )Xianyan Mi*( )Ling WangYuanyuan Guo
School of Computer Science, China University of Geosciences, Wuhan 430074, China
Beibu Gulf Ocean Development Research Center, Beibu Gulf University, Qinzhou 535000, China
College of Economics and Management, Beibu Gulf University, Qinzhou 535000, China
Department of Automation, Tsinghua University, Beijing 100084, China
Cvent Company, Fredericton, E3B 5H8, Canada

Abstract

Nonlinear Equations (NEs), which may usually have multiple roots, are ubiquitous in diverse fields. One of the main purposes of solving NEs is to locate as many roots as possible simultaneously in a single run, however, it is a difficult and challenging task in numerical computation. In recent years, Intelligent Optimization Algorithms (IOAs) have shown to be particularly effective in solving NEs. This paper provides a comprehensive survey on IOAs that have been exploited to locate multiple roots of NEs. This paper first revisits the fundamental definition of NEs and reviews the most recent development of the transformation techniques. Then, solving NEs with IOAs is reviewed, followed by the benchmark functions and the performance comparison of several state-of-the-art algorithms. Finally, this paper points out the challenges and some possible open issues for solving NEs.

Keywords: Nonlinear Equations (NEs), Intelligent Optimization Algorithms (IOA), multiple roots location, transformation techniques, diversity preservation

References(94)

[1]
J. Pintér, Solving nonlinear equation systems via global partition and search: Some experimental results, Computing, vol. 43, no. 4, pp. 309-323, 1990.
[2]
M. Kastner, Phase transitions and configuration space topology, Rev. Mod. Phys., vol. 80, pp. 167-187, 2008.
[3]
F. Facchinei and C. Kanzow, Generalized nash equilibrium problems, Annals of Oporation Research, vol. 5, no. 3, pp. 173-210, 2007.
[4]
D. Guo, Z. Nie, and L. Yan, The application of noise-tolerant ZD design formula to robots’ kinematic control via time-varying nonlinear equations solving, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 48, no. 12, pp. 2188-2197, 2017.
[5]
H. D. Chiang and T. Wang, Novel homotopy theory for nonlinear networks and systems and its applications to electrical grids, IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1051-1060, 2017.
[6]
G. Li, P. Niu, W. Zhang, and Y. Zhang, Control of discrete chaotic systems based on echo state network modeling with an adaptive noise canceler, Knowledge-Based Systems, vol. 35, pp. 35-40, 2012.
[7]
D. Mehta and C. Grosan, A collection of challenging optimization problems in science, engineering and economics, in Proc. of 2015 IEEE Congress on Evolutionary Computation (CEC), Sendai, Japan, 2015, pp. 2697-2704.
DOI
[8]
S. Smale, Mathematical problems for the next century, Math. Intell., vol. 20, no. 2, pp. 7-15, 1998.
[9]
C. T. Kelley, Numerical methods for nonlinear equations, Acta Numerica, vol. 27, pp. 207-287, 2018.
[10]
H. Ramos and M. Monteiro, A new approach based on the newton’s method to solve systems of nonlinear equations, Journal of Computational and Applied Mathematics, vol. 318, pp. 3-13, 2017.
[11]
H. Liu, Y. Zhou, and Y. Li, A Quasi-Newton population migration algorithm for solving systems of nonlinear equations, Journal of Computers, vol. 6, no. 1, pp. 36-42, 2011.
[12]
A. Bouaricha and R. B. Schnabel, Tensor methods for large sparse systems of nonlinear equations, Mathematical Programming, vol. 82, no. 3, pp. 377-400, 1998.
[13]
Y. Gao, P. Zhao, L. S. Turng, and H. Zhou, Intelligent Optimization Algorithms. John Wiley & Sons, 2013, pp. 283-292.
DOI
[14]
T. Bäck, Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford, UK: Oxford University Press, 1996.
DOI
[15]
J. Kennedy and R. Eberhart, Particle swarm optimization, in Proceedings of IEEE International Conference on Neural Networks IV, Perth, Australia, 1995, pp. 1942-1948.
[16]
R. Storn and K. Price, Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, vol. 11, no. 4, pp. 341-359, 1997.
[17]
N. Hansen, S. D. Müller, and P. Koumoutsakos, Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evolutionary Computation, vol. 11, no. 1, pp. 1-18, 2003.
[18]
O. E. Turgut, M. S. Turgut, and M. T. Coban, Chaotic quantum behaved particle swarm optimization algorithm for solving nonlinear system of equations, Computers & Mathematics with Applications, vol. 68, no. 4, pp. 508-530, 2014.
[19]
M. Abdollahi, A. Bouyer, and D. Abdollahi, Improved cuckoo optimization algorithm for solving systems of nonlinear equations, The Journal of Supercomputing, vol. 72, no. 3, pp. 1246-1269, 2016.
[20]
M. Jaberipour, E. Khorram, and B. Karimi, Particle swarm algorithm for solving systems of nonlinear equations, Computers & Mathematics with Applications, vol. 62, no. 2, pp. 566-576, 2011.
[21]
C. A. Floudas, Recent advances in global optimization for process synthesis, design and control: Enclosure of all solutions, Computers & Chemical Engineering, vol. 23, pp. 963-973, 1999.
[22]
X. Li, M. G. Epitropakis, K. Deb, and A. Engelbrecht, Seeking multiple solutions: An updated survey on niching methods and their applications, IEEE Transactions on Evolutionary Computation, vol. 21, no. 4, pp. 518-538, 2017.
[23]
W. Song, Y. Wang, H. X. Li, and Z. Cai, Locating multiple optimal solutions of nonlinear equation systems based on multiobjective optimization, IEEE Transactions on Evolutionary Computation, vol. 19, no. 3, pp. 414-431, 2015.
[24]
W. Gong, Y. Wang, Z. Cai, and L. Wang, Finding multiple roots of nonlinear equation systems via a repulsion-based adaptive differential evolution, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 50, no. 4, pp. 1499-1513, 2020.
[25]
W. Gao, G. Li, Q. Zhang, Y. Luo, and Z. Wang, Solving nonlinear equation systems by a two-phase evolutionary algorithm, IEEE Transactions on Systems, Man, and Cybernetics: Systems, .
[26]
L. Wu, H. Ren, and W. Bi, Review of the genetic algorithm for nonlinear equations, Electronic Science and Technology, vol. 4, pp. 173-178, 2014.
[27]
C. Karr, B. Weck, and L. Freeman, Solutions to systems of nonlinear equations via a genetic algorithm, Engineering Applications of Artificial Intelligence, vol. 11, no. 3, pp. 369-375, 1998.
[28]
M. D. Stuber, V. Kumar, and P. I. Barton, Nonsmooth exclusion test for finding all solutions of nonlinear equations, Bit Numerical Mathematics, vol. 50, no. 4, pp. 885-917, 2010.
[29]
J. A. Koupaei and S. Hosseini, A new hybrid algorithm based on chaotic maps for solving systems of nonlinear equations, Chaos, Solitons & Fractals, vol. 81, pp. 233-245, 2015.
[30]
J. Wu, W. Gong, and L. Wang, A clustering-based differential evolution with different crowding factors for nonlinear equations system, Applied Soft Computing, vol. 98, p. 106733, 2021.
[31]
N. Henderson, L. Freitas, and G. Platt, Prediction of critical points: A new methodology using global optimization, Aiche Journal, vol. 50, no. 6, pp. 1300-1314, 2004.
[32]
L. Freitas, G. Platt, and N. Henderson, Novel approach for the calculation of critical points in binary mixtures using global optimization, Fluid Phase Equilibria, vol. 225, pp. 29-37, 2004.
[33]
M. J. Hirsch, P. M. Pardalos, and M. G. Resende, Solving systems of nonlinear equations with continuous GRASP, Nonlinear Analysis: Real World Applications, vol. 10, no. 4, pp. 2000-2006, 2009.
[34]
N. Henderson, W. F. Sacco, and G. M. Platt, Finding more than one root of nonlinear equations via a polarization technique: An application to double retrograde vaporization, Chemical Engineering Research and Design, vol. 88, nos. 5&6, pp. 551-561, 2010.
[35]
E. Pourjafari and H. Mojallali, Solving nonlinear equations systems with a new approach based on invasive weed optimization algorithm and clustering, Swarm and Evolutionary Computation, vol. 4, pp. 33-43, 2012.
[36]
G. C. Ramadas, E. M. Fernandes, and A. A. Rocha, Multiple roots of systems of equations by repulsion merit functions, in Proc. of Computational Science and Its Applications-ICCSA 2014, Banff, Canada, 2014, pp. 126-139.
DOI
[37]
G. C. V. Ramadas, A. M. A. C. Rocha, and E. M. G. P. Fernandes, Testing nelder-mead based repulsion algorithms for multiple roots of nonlinear systems via a two-level factorial design of experiments, PLos One, vol. 10, no. 4, p. e0121844, 2015.
[38]
A. F. Kuri-Morales, Solution of simultaneous non-linear equations using genetic algorithms, WSEAS Transactions on Systems, vol. 2, no. 1, pp. 44-51, 2003.
[39]
A. Pourrajabian, R. Ebrahimi, M. Mirzaei, and M. Shams, Applying genetic algorithms for solving nonlinear algebraic equations, Applied Mathematics and Computation, vol. 219, no. 24, pp. 11483-11494, 2013.
[40]
C. Maranas and C. Floudas, Finding all solutions of nonlinearly constrained systems of equations, Journal of Global Optimization, vol. 7, no. 2, pp. 143-182, 1995.
[41]
A. A. Mousa and I. M. El-Desoky, GENLS: Co-evolutionary algorithm for nonlinear system of equations, Applied Mathematics and Computation, vol. 197, no. 2, pp. 633-642, 2008.
[42]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182-197, 2002.
[43]
Q. Zhang and H. Li, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. on Evol. Comput., vol. 11, no. 6, pp. 712-731, 2007.
[44]
C. Grosan and A. Abraham, A new approach for solving nonlinear equations systems, IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, vol. 38, no. 3, pp. 698-714, 2008.
[45]
B. Li, J. Li, T. Ke, and Y. Xin, Many-objective evolutionary algorithms: A survey, ACM Computing Surveys, vol. 48, no. 1, pp. 1-35, 2015.
[46]
S. Qin, S. Zeng, W. Dong, and X. Li, Nonlinear equation systems solved by many-objective hype, in Proc. of 2015 IEEE Congress on Evolutionary Computation, Sendai, Japan, 2015, pp. 2691-2696.
DOI
[47]
W. Gong, Y. Wang, Z. Cai, and S. Yang, A weighted biobjective transformation technique for locating multiple optimal solutions of nonlinear equation systems, IEEE Transactions on Evolutionary Computation, vol. 21, no. 5, pp. 697-713, 2017.
[48]
Y. R. Naidu and A. K. Ojha, Solving multiobjective optimization problems using hybrid cooperative invasive weed optimization with multiple populations, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 48, no. 6, pp. 821-832, 2018.
[49]
W. Gao, Y. Luo, J. Xu, and S. Zhu, Evolutionary algorithm with multiobjective optimization technique for solving nonlinear equation systems, Information Sciences, vol. 541, pp. 345-361, 2020.
[50]
Z. Liao, W. Gong, and L. Wang, Memetic niching-based evolutionary algorithms for solving nonlinear equation system, Expert Systems with Applications, vol. 149, p. 113261, 2020.
[51]
W. He, W. Gong, L. Wang, X. Yan, and C. Hu, Fuzzy neighborhood-based differential evolution with orientation for nonlinear equation systems, Knowledge-Based Systems, vol. 182, p. 104796, 2019.
[52]
I. Tsoulos and A. Stavrakoudis, On locating all roots of systems of nonlinear equations inside bounded domain using global optimization methods, Nonlinear Analysis: Real World Applications, vol. 11, no. 4, pp. 2465-2471, 2010.
[53]
W. Sacco and N. Henderson, Finding all solutions of nonlinear systems using a hybrid metaheuristic with fuzzy clustering means, Applied Soft Computing, vol. 11, no. 8, pp. 5424-5432, 2011.
[54]
R. M. A. Silva, M. G. C. Resende, and P. M. Pardalos, Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm, Journal of Global Optimization, vol. 60, no. 2, pp. 289-306, 2014.
[55]
M. Mahdavi, M. Fesanghary, and E. Damangir, An improved harmony search algorithm for solving optimization problems, Applied Mathematics and Computation, vol. 188, no. 2, pp. 1567-1579, 2007.
[56]
Z. Liao, W. Gong, X. Yan, L. Wang, and C. Hu, Solving nonlinear equations system with dynamic repulsion-based evolutionary algorithms, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 50, no. 4, pp. 1590-1601, 2020.
[57]
R. Brits, A. P. Engelbrecht, and F. van den Bergh, Solving systems of unconstrained equations using particle swarm optimization, in Proc. of IEEE International Conference on Systems, Man and Cybernetics, Yasmine Hammamet, Tunisia, 2002, pp. 1-6.
[58]
L. Zhou and C. Jiang, New method for solving nolinear equation systems, Journal of Chinese Computer Systems, vol. 9, no. 4, pp. 1709-1713, 2008.
[59]
Z. Liao, W. Gong, and L. Wang, A hybrid swarm intelligence with improved ring topology for nonlinear equations, Scientia Sinica Informationis, vol. 50, no. 3, pp. 396-407, 2020.
[60]
Z. Liao, W. Gong, L. Wang, X. Yan, and C. Hu, A decomposition-based differential evolution with reinitialization for nonlinear equations systems, Knowledge-Based Systems, vol. 191, p. 105312, 2020.
[61]
J. Bader and E. Zitzler, HypE: An algorithm for fast hypervolume-based many-objective optimization, Evolutionary Computation, vol. 19, no. 1, pp. 45-76, 2011.
[62]
R. Tanabe and A. Fukunaga, Success-history based parameter adaptation for differential evolution, in Proc. 2013 IEEE Congress on Evolutionary Computation (CEC), Cancun, Mexico, 2013, pp. 71-78.
DOI
[63]
B. Qu, P. Suganthan, and J. Liang, Differential evolution with neighborhood mutation for multimodal optimization, IEEE Trans. on Evol. Comput., vol. 16, no. 5, pp. 601-614, 2012.
[64]
A. Rovira, M. Valdés, and J. Casanova, A new methodology to solve non-linear equation systems using genetic algorithms. Application to combined cyclegas turbine simulation, International Journal for Numerical Methods in Engineering, vol. 63, no. 10, pp. 1424-1435, 2005.
[65]
P. S. Mhetre, Genetic algorithm for linear and nonlinear equation, International Journal of Advanced Engineering Technology, vol. 3, no. 2, pp. 114-118, 2012.
[66]
J. Wang, Immune genetic algorithm for solving nonlinear equations, in Proc. of 2011 International Conference on Mechatronic Science, Electric Engineering and Computer (MEC), Jilin, China, 2011, pp. 2094-2097.
[67]
H. Ren, L. Wu, W. Bi, and I. K. Argyros, Solving nonlinear equations system via an efficient genetic algorithm with symmetric and harmonious individuals, Applied Mathematics and Computation, vol. 219, no. 23, pp. 10967-10973, 2013.
[68]
G. Joshi and M. B. Krishna, Solving system of non-linear equations using genetic algorithm, in Proc. of 2014 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Delhi, India, 2014, pp. 1302-1308.
DOI
[69]
Y. Mo, H. Liu, and Q. Wang, Conjugate direction particle swarm optimization solving systems of nonlinear equations, Computers & Mathematics with Applications, vol. 57, nos. 11&12, pp. 1877-1882, 2009.
[70]
C. Voglis, K. Parsopoulos, and I. Lagaris, Particle swarm optimization with deliberate loss of information, Soft Computing, vol. 16, no. 8, pp. 1373-1392, 2012.
[71]
G. C. V. Ramadas and E. M. G. P. Fernandes, Combined mutation differential evolution to solve systems of nonlinear equations, AIP Conference Proceedings, vol. 1558, no. 1, pp. 582-585, 2013.
[72]
Y. Zhou, Q. Luo, and H. Chen, A novel differential evolution invasive weed optimization algorithm for solving nonlinear equations systems, Journal of Applied Mathematics, vol. 2013, p. 757391, 2013.
[73]
A. M. Ibrahim and M. A. Tawhid, A hybridization of differential evolution and monarch butterfly optimization for solving systems of nonlinear equations, Journal of Computational Design and Engineering, vol. 6, no. 3, pp. 354-367, 2019.
[74]
X. Wang and N. Zhou, Pattern search firefly algorithm for solving systems of nonlinear equations, in Proceedings of 2014 7th International Symposium on Computational Intelligence and Design, ISCID 2014, Hangzhou, China, 2014, pp. 228-231.
DOI
[75]
M. Ariyaratne, T. Fernando, and S. Weerakoon, Solving systems of nonlinear equations using a modified firefly algorithm (MODFA), Swarm and Evolutionary Computation, vol. 48, pp. 72-92, 2019.
[76]
A. Ariyaratne, T. Fernando, and S. Weerakoon, A self-tuning algorithm to approximate roots of systems of nonlinear equations based on the firefly algorithm, International Journal of Swarm Intelligence, vol. 5, no. 1, p. 60, 2020.
[77]
Y. Zhou, J. Liu, and G. Zhao, Leader glowworm swarm optimization algorithm for solving nonlinear equations systems, Electrical Review, vol. 88, no. 1, pp. 101-106, 2012.
[78]
H. E. Oliveira and A. Petraglia, Solving nonlinear systems of functional equations with fuzzy adaptive simulated annealing, Applied Soft Computing, vol. 13, no. 11, pp. 4349-4357, 2013.
[79]
J. Xie, Y. Zhou, and H. Chen, A novel bat algorithm based on differential operator and lévy flights trajectory, Computational Intelligence and Neuroscience, vol. 2013, p. 453812, 2013.
[80]
J. Wu, Z. Cui, and J. Liu, Using hybrid social emotional optimization algorithm with metropolis rule to solve nonlinear equations, in Proc. of IEEE International Conference on Cognitive Informatics & Cognitive Computing, Banff, Canada, 2011, pp. 405-411.
DOI
[81]
M. Abdollahi, A. Isazadeh, and D. Abdollahi, Imperialist competitive algorithm for solving systems of nonlinear equations, Computers & Mathematics with Applications, vol. 65, no. 12, pp. 1894-1908, 2013.
[82]
X. Zhang, Q. Wan, and Y. Fan, Applying modified cuckoo search algorithm for solving systems of nonlinear equations, Neural Computing and Applications, vol. 31, pp. 553-576, 2019.
[83]
J. Pei, Z. Dražić, M. Dražić, N. Mladenović, and P. M. Pardalos, Continuous variable neighborhood search (C-VNS) for solving systems of nonlinear equations, INFORMS Journal on Computing, vol. 31, no. 2, pp. 235-250, 2019.
[84]
M. Črepinšek, S. H. Liu, and M. Mernik, Exploration and exploitation in evolutionary algorithms: A survey, ACM Comput. Surv., vol. 45, no. 3, pp. 35:1-35:33, 2013.
[85]
E. L. Yu and P. N. Suganthan, Ensemble of niching algorithms, Information Sciences, vol. 180, no. 5, pp. 2815-2833, 2010.
[86]
X. Li, Niching without niching parameters: Particle swarm optimization using a ring topology, IEEE Trans. on Evol. Comput., vol. 14, no. 1, pp. 150-169, 2010.
[87]
A. K. Jain, M. N. Murty, and P. J. Flynn, Data clustering: A review, ACM Comput. Surv., vol. 31, no. 3, pp. 264-323, 1999.
[88]
A. Rodriguez and A. Laio, Clustering by fast search and find of density peaks, Science, vol. 344, no. 6191, pp. 1492-1496, 2014.
[89]
A. Zhou, B.-Y. Qu, H. Li, S.-Z. Zhao, P. N. Suganthan, and Q. Zhang, Multiobjective evolutionary algorithms: A survey of the state of the art, Swarm and Evolutionary Computation, vol. 1, no. 1, pp. 32-49, 2011.
[90]
E. Zitzler, M. Laumanns, and L. Thiele, SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization, in Proc. of Evolutionary Methods for Design, Optimisation and Control with Application to Industrial Problems (EUROGEN 2001), Athens, Greece, 2002, pp. 95-100.
[91]
K. Deb, An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, vol. 186, nos. 2&4, pp. 311-338, 2000.
[92]
A. Song, G. Wu, and W. Pedrycz, Integrating variable reduction strategy with evolutionary algorithm for solving nonlinear equations systems, arXiv preprint arXiv: 2008.04223, 2020.
[93]
F. Wang, Y. Li, A. Zhou, and K. Tang, An estimation of distribution algorithm for mixed-variable Newsvendor problems, IEEE Transactions on Evolutionary Computation, vol. 24, no. 3, pp. 479-493, 2020.
[94]
F. Wang, H. Zhang, and A. Zhou, A particle swarm optimization algorithm for mixed-variable optimization problems, Swarm and Evolutionary Computation, vol. 60, p. 100808, 2021.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 16 February 2021
Accepted: 25 February 2021
Published: 30 April 2021
Issue date: March 2021

Copyright

© The author(s) 2021

Acknowledgements

This work was partly supported by the National Natural Science Foundation of China (No. 62076225), the Natural Science Foundation of Guangxi Province (No. 2020JJA170038), and the High-Level Talents Research Project of Beibu Gulf (No. 2020KYQD06).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return