Global optimization by continuous grasp | Optimization Letters
Skip to main content
Springer Nature Link
Log in

Global optimization by continuous grasp

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We introduce a novel global optimization method called Continuous GRASP (C-GRASP) which extends Feo and Resende’s greedy randomized adaptive search procedure (GRASP) from the domain of discrete optimization to that of continuous global optimization. This stochastic local search method is simple to implement, is widely applicable, and does not make use of derivative information, thus making it a well-suited approach for solving global optimization problems. We illustrate the effectiveness of the procedure on a set of standard test problems as well as two hard global optimization problems.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Anderssen, R.S.: Global optimization. In: Anderssen, R.S., Jennings, L.S., Ryan, D.M. (eds.) Optimization, pp. 26–48. Queensland University Press, (1972)

  2. Barhen J., Protopopescu V., Reister D. (1997). Trust: a deterministic algorithm for global optimization. Science, 276:1094–1097

    Article  MathSciNet  Google Scholar 

  3. Butler R.A.R., Slaminka E.E. (1992). An evaluation of the sniffer global optimization algorithm using standard test functions. J. Comput. Phys. 99(1):28–32

    Article  MATH  MathSciNet  Google Scholar 

  4. Chen L., Zhou T., Tang Y. (2005). Protein structure alignment by deterministic annealing. Bioinformatics 21(1):51–62

    Article  MATH  Google Scholar 

  5. Cvijović D., Klinowski J. (1995). Taboo search: an approach to the multiple minima problem. Science 267:664–666

    Article  MathSciNet  Google Scholar 

  6. Feo T.A., Resende M.G.C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8:67–71

    Article  MATH  MathSciNet  Google Scholar 

  7. Feo T.A., Resende M.G.C. (1995). Greedy randomized adaptive search procedures. J. Global. Optim. 6:109–133

    Article  MATH  MathSciNet  Google Scholar 

  8. Festa P., Resende M.G.C. (2002). GRASP: an annotated bibliography. In: Ribeiro C.C., Hansen P., (eds) Essays and Surveys in Metaheuristics, pp. 325–367. Kluwer, Dordrecht

    Google Scholar 

  9. Floudas, C.A., Pardalos P.M.: A collection of test problems for constrained global optimization algorithms. In: Goods, G., Hartmanis, J., (eds.) Lecture Notes in Computer Science, vol. 455. Springer Berlin Heidelberg New York (1990)

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

    MATH  Google Scholar 

  11. Granvilliers L., Benhamou F. (2001). Progress in the solving of a circuit design problem. J. Global Optim. 20(2):155–168

    Article  MathSciNet  Google Scholar 

  12. Hedar A.R., Fukushima M. (2002). Hybrid simulated annealing and direct search method for nonlinear unconstrained global optimization. Optim. Methods Softw. 17:891–912

    Article  MATH  MathSciNet  Google Scholar 

  13. Hedar A.R., Fukushima M. (2003). Minimizing multimodal functions by simplex coding genetic algorithms. Optim. Methods Softw. 18:265–282

    Article  MATH  MathSciNet  Google Scholar 

  14. Hedar A.R., Fukushima M. (2006). Tabu search directed by direct search methods for nonlinear global optimization. Eur. J. Oper. Res. 170:329–349

    Article  MATH  MathSciNet  Google Scholar 

  15. Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd Revised Edition. Springer Berlin Heidelberg New York (1993)

  16. Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Dordrecht 2nd edn. (2000)

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

    Article  MATH  MathSciNet  Google Scholar 

  18. Koon, G.H., Sebald, A.V.: Some interesting test functions for evaluating evolutionary programming strategies. In Proceedings of the Fourth Annual Conference on Evolutionary Programming, pp. 479–499 (1995)

  19. Krokhmal, P., Murphey, R., Pardalos, P.M., Uryasev, S., Zrazhevsky, G.: Robust decision making: addressing uncertainties in distributions. In: Butenko, S., Murphey, R., Pardalos, P.M.: (eds.) Cooperative Control: Models, Applications, and Algorithms, pp. 165–185. Kluwer Dordrecht (2003)

  20. Krokhmal, P., Murphey, R., Pardalos, P.M., Uryasev, S.: Use of conditional value-at-risk in stochastic programs with poorly defined distributions. In: Butenko, S., Murphey, R., Pardalos, P.M., (eds.) Recent Developments in Cooperative Control and Optimization, pp. 225–243. Kluwer Dordrecht (2004)

  21. Meintjes K., Morgan A.P. (1987). A methodology for solving chemical equilibrium systems. Appl. Math. Comput. 22:333–361

    Article  MATH  MathSciNet  Google Scholar 

  22. Meintjes K., Morgan A.P. (1989). Element variables and the solution of complex chemical equilibrium problems. Combust. Sci. Technol. 68:35–48

    Article  Google Scholar 

  23. Meintjes K., Morgan A.P. (1990). Chemical equilibrium systems as numerical test problems. ACM Trans. Math. Softw. 16(2):143–151

    Article  MATH  Google Scholar 

  24. Pardalos P.M., Resende M.G.C. (eds) (2002). Handbook of Applied Optimization. Oxford University Press, New York

    MATH  Google Scholar 

  25. Park S., Miller K. (1988). Random number generators: good ones are hard to find. Commun ACM 31:1192–1201

    Article  MathSciNet  Google Scholar 

  26. Pham, D.T., Karaboga, D.: Intelligent Optimization Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing, and Neural Networks. Springer Berlin Heidelberg New York (2000)

  27. Ratschek H., Rokne J. (1993). Experiments using interval analysis for solving a circuit design problem. J. Global Optim. 3(3):501–518

    Article  MATH  MathSciNet  Google Scholar 

  28. Resende, M.G.C., Ribeiro, C.C.: Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics, pp. 219–249. Kluwer Dordrecht (2003)

  29. Siarry P., Berthiau G., Durbin F., Haussy J. (1997). Enhanced simulated annealing for globally minimizing functions of many continuous variables. ACM Trans. Math. Softw. 23(2):209–228

    Article  MATH  MathSciNet  Google Scholar 

  30. Trafalis T.B., Kasap S. (2002). A novel metaheuristics approach for continuous global optimization. J. Global Optim. 23:171–190

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  32. Vanderbilt D., Louie S.G. (1984). A Monte Carlo simulated annealing approach to optimization over continuous variables. J. Comput. Phys. 56:259–271

    Article  MATH  MathSciNet  Google Scholar 

  33. Wales D.J., Scheraga H.A. (1999). Global optimization of clusters, crystals, and biomolecules. Science, 285:1368–1372

    Article  Google Scholar 

  34. Yang, J.-M., Kao, C.Y.: A combined evolutionary algorithm for real parameters optimization. In: Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 732–737, (1996)

  35. Zabarankin, M., Uryasev, S., Murphey, R.: Aircraft routing under the risk of detection. Naval Res. Logist. (2006), accepted for publication

Download references

Author information

Authors and Affiliations

  1. Raytheon, Inc., Network Centric Systems, P.O. Box 12248, St. Petersburg, FL, 33733-2248, USA

    M. J. Hirsch

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

    M. J. Hirsch, C. N. Meneses & P. M. Pardalos

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

    M. G. C. Resende

Authors
  1. M. J. Hirsch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. C. N. Meneses
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P. M. Pardalos
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. M. G. C. Resende
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. J. Hirsch.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hirsch, M.J., Meneses, C.N., Pardalos, P.M. et al. Global optimization by continuous grasp. Optimization Letters 1, 201–212 (2007). https://doi.org/10.1007/s11590-006-0021-6

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-006-0021-6

Keywords

Search

Navigation