[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Fat-tailed distributions for continuous variable neighborhood search

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

Abstract

Using the Gaussian normal distribution on the whole solution space in the continuous variable neighborhood search method has shown similar success as the use of traditional bounded neighborhoods, but with less parameters to be specified. For unbounded problems with distant optimal solutions, although not limited by bounded geometrical neighborhoods, it showed to be inefficient due to the exponential decrease of the normal density function. In order to reach distant solutions more efficiently, six more “fat-tailed” distributions, which can be easily generated, are tested in this paper. The experiments on test functions showed greater efficiency for most new distributions opposite to a normal distribution. Moreover, following the “less is more approach”, this paper presents a very efficient algorithm for both close and distant optimal solutions. It combines two neighborhood structures: one being efficient for near solutions, and the other more efficient for distant solutions. This approach, with a reduced number of parameters the user must define in advance, has shown to be robust when the position of the optimal point is unknown.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Ahrens, J.H., Dieter, U.: Efficient table-free sampling methods for the exponential, Cauchy, and normal distributions. Commun. ACM 31(11), 1330–7 (1988)

    Article  Google Scholar 

  2. Aloise, D., Xavier-De-Souza, S., Mladenović, N.: Less is more: simplified Nelder–Mead method for large unconstrained optimization. Yugosl. J. Oper. Res. 28(2), 153–169 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  3. Audet, C., Béchard, V., Le Digabel, S.: Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search. J. Global Optim. 41(2), 299–318 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Brimberg, J., Mladenović, N., Todosijević, R., Urošević, D.: Less is more: solving the max-mean diversity problem with variable neighborhood search. Inf. Sci. 382, 179–200 (2017)

    Article  Google Scholar 

  5. Carrizosa, E., Dražić, M., Dražić, Z., Mladenović, N.: Gaussian variable neighborhood search for continuous optimization. Comput. Oper. Res. 39(9), 2206–2213 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  6. Costa, L.R., Aloise, D., Mladenović, N.: Less is more: basic variable neighborhood search heuristic for balanced minimum sum-of-squares clustering. Inf. Sci. 415, 247–253 (2017)

    Article  Google Scholar 

  7. Dražić, M., Kovačević-Vujčić, V., Čangalović, M., Mladenović, N.: GLOB—A New VNS-Based Software for Global Optimization. Global optimization, pp. 135–154. Springer, Boston (2006)

    MATH  Google Scholar 

  8. Dražić, M., Lavor, C., Maculan, N., Mladenović, N.: A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule. Eur. J. Oper. Res. 185(3), 1265–1273 (2008)

    Article  MATH  Google Scholar 

  9. Dražić, M., Dražić, Z., Mladenović, N., Urošević, D., Zhao, Q.H.: Continuous variable neighbourhood search with modified Nelder–Mead for non-differentiable optimization. IMA J. Manag. Math. 27(1), 75–88 (2014)

    MathSciNet  MATH  Google Scholar 

  10. Dražić, M.: Influence of a neighborhood shape on the efficiency of Continuous Variable Neighborhood Search. Yugosl. J. Oper. Res. 30(1), 3–17 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  11. Easom, E.E.: A survey of global optimization techniques. Doctoral dissertation, University of Louisville (1990)

  12. Fishman, G.S.: Monte Carlo: Concepts, Algorithms, and Applications. Springer, Berlin (1996)

    Book  MATH  Google Scholar 

  13. Gendreau, M., Potvin, J.: Handbook of Metaheuristics. Springer, Berlin (2010)

    Book  MATH  Google Scholar 

  14. Hansen, P., Mladenović, N.: An introduction to variable neighborhood search. In: Metaheuristics, pp. 433–458. Springer, Boston (1999)

    Google Scholar 

  15. http://tracer.lcc.uma.es/problems/ackley/ackley.html

  16. http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedarfiles/-TestGOfiles/Page295.htm

  17. Kovačević-Vujčić, V., Čangalović, M., Dražić, M., Mladenović, N., An, L.H., Tao, P.D.: VNS-based heuristics for continuous global optimization. In: Modelling, Computation and Optimization in Information Systems and Managemant Sciences. Hermes Science Publishing, London (2004)

    Google Scholar 

  18. Liberti, L., Dražić, M.: Variable neighbourhood search for the global optimization of constrained NLPs. In: Proceedings of GO Workshop, Almeria, Spain, pp. 1–5 (2005)

  19. Mikić, M., Todosijević, R., Urošević, D.: Less is more: general variable neighborhood search for the capacitated modular hub location problem. Comput. Oper. Res. 110, 101–115 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  20. Mishra, S.K.: Some new test functions for global optimization and performance of repulsive particle swarm method. Available at SSRN 926132 (2006)

  21. Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Mladenović, N., Petrović, J., Kovačević-Vujčić, V., Čangalović, M.: Solving spread spectrum radar polyphase code design problem by Tabu search and variable neighborhood search. Eur. J. Oper. Res. 151, 389–399 (2003)

    Article  MATH  Google Scholar 

  23. Mladenović, N., Dražić, M., Kovačević-Vujčić, V., Čangalović, M.: General variable neighborhood search for the continuous optimization. Eur. J. Oper. Res. 191(3), 753–770 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mladenović, N., Todosijević, R., Urošević, D.: Less is more: basic variable neighborhood search for minimum differential dispersion problem. Inf. Sci. 326, 160–171 (2016)

    Article  Google Scholar 

  25. Mladenović, N., Alkandari, A., Pei, J., Todosijević, R., Pardalos, P.M.: Less is more approach: basic variable neighborhood search for the obnoxious p-median problem. Int. Trans. Oper. Res. 27(1), 480–493 (2020)

    Article  MathSciNet  Google Scholar 

  26. Pei, J., Dražić, Z., Dražić, M., Mladenović, N., Pardalos, P.: Continuous variable neighborhood search (C-VNS) for solving systems of nonlinear equations. INFORMS J. Comput. 31(2), 235–250 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  27. Rajab, R.S., Dražić, M., Mladenović, N., Mladenović, P., Yu, K.: Fitting censored quantile regression by variable neighborhood search. J. Global Optim. 63(5), 481–500 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  28. Trefethen, N.: A hundred-dollar, hundred-digit challenge. SIAM News 35(1), 3 (2002)

    Google Scholar 

Download references

Acknowledgements

The author is partially supported by Serbian Ministry of Science, project number 174010.

Author information

Authors and Affiliations

  1. Faculty of Mathematics, University of Belgrade, Studentski trg 16, Belgrade, 11000, Serbia, Serbia

    Zorica Dražić

Authors
  1. Zorica Dražić
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zorica Dražić.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dražić, Z. Fat-tailed distributions for continuous variable neighborhood search. Optim Lett 17, 2299–2320 (2023). https://doi.org/10.1007/s11590-023-01999-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-023-01999-6

Keywords

Search

Navigation