A hybrid heuristic parallel method of global optimization

Authors

  • K.V. Pushkaryov Siberian Federal University
  • V.D. Koshur Siberian Federal University

DOI:

https://doi.org/10.26089/NumMet.v16r224

Keywords:

global optimization, heuristic methods, neural networks, parallel computing, C++, MPI

Abstract

The problem of finding the global minimum of a continuous objective function of multiple variables in a multidimensional parallelepiped is considered. A hybrid heuristic parallel method for solving of complicated global optimization problems is proposed. The method is based on combining various methods and on the multi-agent technology. It consists of new methods (for example, the method of neural network approximation of inverse coordinate mappings that uses Generalized Regression Neural Networks (GRNN) to map the values of an objective function to coordinates) and modified classical methods (for example, the modified Hooke-Jeeves method). An implementation of the proposed method as a cross-platform (on the source code level) library written in the C++ language is briefly discussed. This implementation uses the message passing via MPI (Message Passing Interface). The method is compared with 21 modern methods of global optimization and with a genetic algorithm using 28 test objective functions of 50 variables.

Author Biographies

K.V. Pushkaryov

V.D. Koshur

References

  1. D. Izzo and T. Vinkó, “Global Trajectory Optimisation Problems Database,”
    http://www.esa.int/gsp/ACT/inf/projects/gtop/gtop.html . Cited April 20, 2015.
  2. D. Izzo and T. Vinkó, “Messenger (full version),”
    http://www.esa.int/gsp/ACT/inf/projects/gtop/messenger_full.html . Cited April 20, 2015.
  3. S. Palani and U. Natarajan, “Prediction of Surface Roughness in CNC End Milling by Machine Vision System Using Artificial Neural Network Based on 2D Fourier Transform,” Int. J. Adv. Manuf. Technol. 54 (9-12), 1033-1042 (2011).
  4. W. M. Spears, K. A. De Jong, T. B854ck, et al., “An Overview of Evolutionary Computation,” in Lecture Notes in Computer Science (Springer, Heidelberg, 1993), Vol. 667, pp. 442-459.
  5. A. Corana, M. Marchesi, C. Martini, and S. Ridella, “Minimizing Multimodal Functions of Continuous Variables with the, “Simulated Annealing’’ Algorithm,” ACM Trans. Math. Softw. 13 (3), 262-280 (1987).
  6. A. I. Ruban, Global Optimization by the Coordinate Averaging Method (Krasnoyarskii Tekh. Univ., Krasnoyarsk, 2004) [in Russian].
  7. Ya. D. Sergeev and D. E. Kvasov, Diagonal Methods of Global Optimization (Fizmatlit, Moscow, 2008) [in Russian].
  8. Yu. G. Evtushenko, “Numerical Method for Finding Global Extrema (Case of a Non-Uniform Mesh),” Zh. Vychisl. Mat. Mat. Fiz. 11 (6), 1390-1403 (1971) [USSR Comput. Math. Math. Phys. 11 (6), 38-54 (1971)].
  9. V. D. Koshur, “Global Optimization Based on Hybrid Method of Coordinates Averaging and Particle Swarm Optimization,” Vychisl. Tekhnol. 18 (4), 36-47 (2013).
  10. G. V. Protsykov, E. S. Semenkin, and K. A. Tokmin, “The Effectiveness of Co-Evolutionary Approach in Practical Optimization Problems,” Vestn. Kranoyarsk. Univ. Ser. Fiz. Mat. Nauk, No. 4, 233-239 (2005).
  11. A. Yu. Gornov, “A Parallel Algorithm of Searching for Optimal Control in Problems with Parallelepipedic Constraints,” Vestn. Irkutsk. Univ., No. 2, 104-110 (2004).
  12. Esa/pagmo.
    https://github.com/esa/pagmo . Cited April 20, 2015.
  13. D. Izzo, “PyGMO and PyKEP: Open Source Tools for Massively Parallel Optimization in Astrodynamics (the Case of Interplanetary Trajectory Optimization),” in Proc. 5th Int. Conf. on Astrodynamics Tools and Techniques, ICATT. 2012.
    http://www.esa.int/gsp/ACT/doc/MAD/pub/ACT-RPR-MAD-2012-(ICATT)PyKEP-PaGMO-SOCIS.pdf.Cited April 20, 2015.
  14. A. Kleymenov and A. Semenov, “Using a Cooperative Solving Approach to Global Optimization Problems,” in Lecture Notes in Computer Science (Springer, Heidelberg, 2005), Vol. 3478, pp. 86-100.
  15. Yu. Evtushenko, M. Posypkin, and I. Sigal, “A Framework for Parallel Large-Scale Global Optimization,” Comput. Sci. Res. Develop. 23 (3-4), 211-215 (2009).
  16. Sh. А. Akhmedova and E. S. Semenkin, “New Optimization Metaheuristic Based on Co-Operation of Biology Related Algorithms,” Vestn. Sib. Aerokosmich. Univ., No. 4, 92-99 (2013).
  17. H. Wang and O. Ersoy, “Novel Evolutionary Global Optimization Algorithms and Their Applications,” Purdue University Technical Report.
    http://docs.lib.purdue.edu/ecetr . Cited April 20, 2015.
  18. B. D. Bunday, Basic Optimisation Methods (Arnold, London, 1985; Radio Svyaz’, Moscow, 1988).
  19. A. A. Zhigliavsky and A. G. Zhilinskas, Methods of Global Optimization (Nauka, Moscow, 1991) [in Russian].
  20. V. D. Koshur and K. V. Pushkaryov, “Global Optimization Based on Neural Network Approximation of Inverse Dependences,” in Proc. 13th All-Russia Conf. on Neuroinformatics, Moscow, Russia, January 24-28, 2011 (Mosk. Inzh. Fiz. Inst., Moscow, 2011), pp. 89-98.
  21. V. D. Koshur and K. V. Pushkaryov, “Global Optimization via Neural Network Approximation of Inverse Coordinate Mappings,” Optical Memory Neural Networks 20 (3), 181-193 (2011).
  22. V. D. Koshur and K. V. Pushkaryov, “Dual Generalized Regression Neural Networks for Solving Global Optimization Problems,” in Proc. 12th All-Russia Conf. on Neuroinformatics, Moscow, Russia, January 25-29, 2010 (Mosk. Inzh. Fiz. Inst., Moscow, 2010), pp. 219-227.
  23. MPI: A Message-Passing Interface Standard. Version 2.2.
    http://mpi-forum.org/docs/mpi-2.2/mpi22-report.pdf . Cited April 20, 2015.
  24. Special Session & Competition on Real-Parameter Single Objective Optimization at CEC-2013.
    http://www.ntu.edu.sg/home/EPNSugan/index_files/CEC2013/CEC2013.htm . Cited April 20, 2015.
  25. J. J. Liang, B. Y. Qu, P. N. Suganthan, and A. G. Hernández-Diaz, Problem Definitions and Evaluation Criteria for the CEC 2013 Special Session on Real-Parameter Optimization , Technical Report.
    http://www.ntu.edu.sg/home/EPNSugan/index_files/CEC2013/Definitions%20of%20%20CEC%2013%20benchmark%20suite%200117.pdf . Cited April 20, 2015.
  26. M. G. Kendall and A. Stuart, The Advanced Theory of Statistics (Hafner, New York, 1968; Nauka, Moscow, 1973).

Published

14-05-2015

How to Cite

Пушкарев К., Кошур В. A Hybrid Heuristic Parallel Method of Global Optimization // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2015. 16. 242-255. doi 10.26089/NumMet.v16r224

Issue

Section

Section 1. Numerical methods and applications