iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10898-013-0105-7
Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm | Journal of Global Optimization Skip to main content

Advertisement

Springer Nature Link
Log in

Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Several numerical methods for solving nonlinear systems of equations assume that derivative information is available. Furthermore, these approaches usually do not consider the problem of finding all solutions to a nonlinear system. Rather, most methods output a single solution. In this paper, we address the problem of finding all roots of a system of equations. Our method makes use of a biased random-key genetic algorithm (BRKGA). Given a nonlinear system, we construct a corresponding optimization problem, which we solve multiple times, making use of a BRKGA, with areas of repulsion around roots that have already been found. The heuristic makes no use of derivative information. We illustrate the approach on seven nonlinear equations systems with multiple roots from the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Aguiar e Oliveira, H., Jr., Ingber, L., Petraglia, A., Petraglia, M.R., Machado, M.A.S.: Nonlinear equation solving. In: Stochastic Global Optimization and Its Applications with Fuzzy Adaptive Simulated Annealing. Intelligent Systems Reference Library, vol. 35, pp. 169–187. Springer, Berlin Heidelberg (2012) ISBN 978-3-642-27478-7. doi:10.1007/978-3-642-27479-4_10

  2. Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: Probability distribution of solution time in GRASP: an experimental investigation. J. Heuristics 8, 343–373 (2002)

    Article  Google Scholar 

  3. Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: TTTPLOTS: a perl program to create time-to-target plots. Opt. Lett. 1, 355–366 (2007)

    Article  Google Scholar 

  4. Bean, J.C.: Genetic algorithms and random keys for sequencing and optimization. ORSA J. Comput. 6, 154–160 (1994)

    Article  Google Scholar 

  5. Ericsson, M., Resende, M.G.C., Pardalos, P.M.: A genetic algorithm for the weight setting problem in OSPF routing. J. Comb. Opt. 6, 299–333 (2002)

    Article  Google Scholar 

  6. Floudas, C.A.: Recent advances in global optimization for process synthesis, design, and control: enclosure of all solutions. Comput. Chem. Eng. 23, S963–S973 (1999)

    Article  Google Scholar 

  7. Floudas, C.A., Pardalos, P.M., Adjiman, C., Esposito, W., Gumus, Z., Harding, S., Klepeis, J., Meyer, C., Schweiger, C.: Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers, Dordrecht (1999)

    Book  Google Scholar 

  8. Gonçalves, J.F., Almeida, J.: A hybrid genetic algorithm for assembly line balancing. J. Heuristics 8, 629–642 (2002)

    Article  Google Scholar 

  9. Gonçalves, J.F., Resende, M.G.C.: An evolutionary algorithm for manufacturing cell formation. Comput. Ind. Eng. 47, 247–273 (2004)

    Article  Google Scholar 

  10. Hirsch, M.J., Pardalos, P.M., Resende, M.G.C.: Solving systems of nonlinear equations with continuous GRASP. Nonlinear Anal. Real World Appl. 10, 2000–2006 (2009)

    Article  Google Scholar 

  11. Hirsch, M.J., Pardalos, P.M., Resende, M.G.C.: Speeding up continuous GRASP. Eur. J. Oper. Res. 205, 507–521 (2010)

    Article  Google Scholar 

  12. Lester, I.: Adaptive simulated annealing (asa): lessons learned. Control Cybern. 25, 33–54 (1996)

    Google Scholar 

  13. Kearfott, R.B.: Some tests on generalized bisection. ACM Trans. Math. Softw. 13(3), 197–220 (1987)

    Article  Google Scholar 

  14. Kearfott, R.B., Novoa, M.: Algorithm 681: intbis, a portable interval newton/bisection package. ACM Trans. Math. Softw. 16(2):152–157 (1990) doi:10.1145/78928.78931

    Google Scholar 

  15. Kubicek, M., Hofmann, H., Hlavacek, V., Sinkule, J.: Multiplicity and stability in a sequence of two nonadiabatic nonisothermal CSTR. Chem. Eng. Sci. 35, 987–996 (1980)

    Article  Google Scholar 

  16. Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3–30 (1998)

    Article  Google Scholar 

  17. Merlet, J.P.: The COPRIN examples page. http://www-sop.inria.fr/coprin/logiciels/ALIAS/Benches/benches.html (2006)

  18. Oliveira Jr, H.: Fuzzy control of stochastic global optimization algorithms and VSFR. Naval Res. Mag. 16, 103–113 (2003)

    Google Scholar 

  19. Pramanik, S.: Kinematic synthesis of a six-member mechanism for automotive steering. ASME J. Mech. Design 124, 642–645 (2002)

    Article  Google Scholar 

  20. R Development Core Team. R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria (2011). URL: http://www.R-project.org/ ISBN 3-900051-07-0

  21. Reklaitis, G., Ragsdell, K.: Engineering Optimization. Wiley, New York (1983)

    Google Scholar 

  22. Royden, H.L.: Real Analysis, 3rd edn. Macmillan Publishing, New York (1988)

    Google Scholar 

  23. Spears, W.M., DeJong K.A.: On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 230–236 (1991)

  24. Tsai, L.W., Morgan, A.P.: Solving the kinematics of the most general six- and five-degree-of-freedom manipulators by continuation methods. J. Mech. Trans. Autom. Design 107, 189–200 (1985)

    Article  Google Scholar 

Download references

Acknowledgments

The research of R.M.A Silva was partially supported by the Brazilian National Council for Scientific and Technological Development (CNPq), the Foundation for Support of Research of the State of Minas Gerais, Brazil (FAPEMIG), Coordination for the Improvement of Higher Education Personnel, Brazil (CAPES), Foundation for the Support of Development of the Federal University of Pernambuco, Brazil (FADE), the Office for Research and Graduate Studies of the Federal University of Pernambuco (PROPESQ), and the Foundation for Support of Science and Technology of the State of Pernambuco (FACEPE).

Author information

Authors and Affiliations

  1. Centro de Informática, Universidade Federal de Pernambuco, Av. Jornalista Anibal Fernandes, s/n Cidade Universitária, Recife-PE, 50740-560, Brazil

    Ricardo M. A. Silva

  2. Algorithms and Optimization Research Department, AT&T Labs Research, 180 Park Avenue, Room C241, Florham Park, NJ, 07932, USA

    Mauricio G. C. Resende

  3. Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL, 32611, USA

    Panos M. Pardalos

Authors
  1. Ricardo M. A. Silva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mauricio G. C. Resende
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Panos M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ricardo M. A. Silva.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Silva, R.M.A., Resende, M.G.C. & Pardalos, P.M. Finding multiple roots of a box-constrained system of nonlinear equations with a biased random-key genetic algorithm. J Glob Optim 60, 289–306 (2014). https://doi.org/10.1007/s10898-013-0105-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-013-0105-7

Keywords

Search

Navigation