Исследование влияния степени овражности целевой функции на погрешность определения координат ее минимума

Цели. Целью работы было исследование зависимостей, связывающих характеристики оврагов, т.е. участков рельефа минимизируемой функции, на которых ее изменение по одному из направлений значительно медленнее, чем по другим направлениям, с погрешностью определения координат ее минимума.

Методы. В экспериментах использовалась специально разработанная тестовая функция с изменяемыми в широких пределах параметрами овражности. В сериях опытов случайно задавались положение и параметры оврага и координаты стартовой точки поиска. Размерность и степень овражности оценивались по собственным числам аппроксимированного гессиана функции в точке окончания поиска минимума. Погрешность определялась как эвклидово расстояние между заданным положением минимума функции и конечной точкой поиска. Для статистической обработки результатов применены линейный регрессионный анализ и аппроксимация с помощью модели искусственной нейронной сети (ИНС).

Результаты. Установлено наличие линейной зависимости между логарифмами степени овражности и погрешности определения координат минимума функции. Коэффициент детерминации R² ~ 0.88. Дополнительный учет эвклидовой нормы градиента функции в точке окончания поиска позволил повысить коэффициент детерминации до R² ~ 0.95, а при использовании модели ИНС – до R² ~ 0.97.

Выводы. Найденные зависимости можно использовать для оценки ожидаемой погрешности определения координат экстремумов оптимизируемых функций. В дальнейшем необходимо расширить методику на функции с размерностью оврагов более единицы и на другие типы сложных для алгоритмов оптимизации участков рельефа.

1. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация; пер. с англ. М.: Мир; 1985. 509 с.

2. Нинул А.С. Оптимизация целевых функций. Аналитика. Численные методы. Планирование эксперимента. М.: Изд-во Физико-математической литературы; 2009. 336 с.

3. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие. М.: Изд-во МГТУ им. Н.Э. Баумана; 2017. 446 с.

4. Jasbir S.A. Introduction to Optimum Design. 4th edition. Elsevier; 2017. 670 p. https://doi.org/10.1016/C2013-0-15344-5

5. Mersmann O., Bischl B., Trautmann H., Preuss M., Weihs C., Rudolf G. Exploratory Landscape Analysis. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO’11). 2011. P. 829–836. https://doi.org/10.1145/2001576.2001690

6. Kerschke P., Trautmann H. Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-package flacco. In: Applications in Statistical Computing—From Music Data Analysis to Industrial Quality Improvement. Series: Studies in Classification, Data Analysis, and Knowledge Organization. Bauer N., Ickstadt K., Lübke K., Szepannek G., Trautmann H., Vichi M. (Eds.). Berlin/Heidelberg, Germany: Springer; 2019. P. 93–123. https://doi.org/10.1007/978-3-030-25147-5_7

7. Trajanov R., Dimeski S., Popovski M., Korosec P., Eftimov T. Explainable Landscape-Aware Optimization Performance Predicion. Preprint. 2021. https://arxiv.org/pdf/2110.11633v1

8. Черноруцкий И.Г. Методы оптимизации в теории управления: учебное пособие. СПб.: Питер; 2004. 256 с.

9. Смирнов А.В. Свойства целевых функций и алгоритмов поиска в задачах многокритериальной оптимизации. Russ. Technol. J. 2022;10(4):75−85. https://doi.org/10.32362/2500-316X-2022-10-4-75-85

10. He J., Xu T. New Methods of Studying Valley Fitness Landscapes. Preprint. 2018. https://arxiv.org/pdf/1805.00092.pdf

11. Ochoa G., Veerapen N. Mapping the Global Structure of TSP Fitness Landscapes. J. Heuristics. 2018;24(4):265–294. https://link.springer.com/article/10.1007/s10732-017-9334-0

12. Hansen N., Finck S., Ros R., Auger A. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Definitions. [Research Report] RR-6829, INRIA. 2009. https://hal.inria.fr/inria-00362633v2

13. Jamil M., Yang Xin-She. A literature survey of benchmark functions for global optimization problems. Int. J. Math. Model. Numer. Opt. 2013;4(2):150–194. https://doi.org/10.1504/IJMMNO.2013.055204

14. Большаков А.А., Каримов Р.Н. Методы обработки многомерных данных и временных рядов. М.: Горячая линия–Телеком; 2007. 522 с.

15. Хайкин С. Нейронные сети: полный курс; пер. с англ. М.: ООО «И.Д. Вильямс»; 2006. 1104 с.