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

Гибридный эвристический параллельный метод глобальной оптимизации

Авторы

  • К.В. Пушкарев
  • В.Д. Кошур

Ключевые слова:

глобальная оптимизация
эвристические методы
нейронные сети
параллельные вычисления
C++
MPI

Аннотация

Рассматривается задача нахождения глобального минимума непрерывной целевой функции многих переменных в области, имеющей вид многомерного параллелепипеда. Для решения сложных задач глобальной оптимизации предлагается гибридный эвристический параллельный метод глобальной оптимизации (ГЭПМ), основанный на комбинировании и гибридизации различных методов и технологии многоагентной системы. В состав ГЭПМ включены как новые методы (например, метод нейросетевой аппроксимации инверсных зависимостей, использующий обобщeнно-регрессионные нейронные сети (GRNN), отображающие значения целевой функции в значения координат), так и модифицированные классические методы (например, модифицированный метод Хука-Дживса). Кратко описывается программная реализация ГЭПМ в форме кроссплатформенной (на уровне исходного кода) программной библиотеки на языке C++, использующей обмен сообщениями через интерфейс MPI (Message Passing Interface). Приводятся результаты сравнения ГЭПМ с 21 современным методом глобальной оптимизации и генетическим алгоритмом на 28 тестовых целевых функциях 50 переменных.

Новые вычислительные технологии

Загрузки

Опубликован

2015-05-14

Выпуск

Том 16 (2015): Выпуск 2.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

К.В. Пушкарев

Сибирский федеральный университет,
Институт космических и информационных технологий
ул. Киренского, 26, 660074, Красноярск
• старший преподаватель

В.Д. Кошур

Сибирский федеральный университет,
Институт космических и информационных технологий
ул. Киренского, 26, 660074, Красноярск
• профессор

Библиографические ссылки

  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).