Метод оценки выпуклости рельефа целевых функций в процессе поиска экстремума

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

Методы. Выпуклость рельефа характеризуется показателем степени степенной аппроксимации ЦФ в окрестностях экстремума. Оценка этого показателя осуществляется по парам пробных точек с учетом их расстояний до найденного экстремума и значений ЦФ в них. На основе анализа погрешностей такой оценки в методе предусмотрены отбор пробных точек по их расстояниям от найденного экстремума и отбор пар пробных точек по углу между направлениями на них из найденного экстремума. Для экспериментальной проверки метода использовались тестовые функции с различной выпуклостью, как выпуклые, так и вогнутые. В качестве метода поиска экстремума применялся алгоритм роя частиц (particle swarm optimization, PSO). Результаты экспериментов представлялись в виде статистических характеристик и гистограмм распределений значений оценки показателя степени степенной аппроксимации ЦФ.

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

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

1. Malan K.M. A Survey of Advances in Landscape Analysis for Optimisation. Algorithms. 2021;14(2):40. https://doi.org/10.3390/a14020040

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

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

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

5. Van Stein B., Long F.X., Frenzel M., Krause P., Gitterle M., Back T. DoE2Vec: Deep-learning Based Features for Exploratory Landscape Analysis. Preprint. 2023. https://arxiv.org/pdf/2304.01219v1

6. Поляк Б.Т. Введение в оптимизацию. М.: Наука; 1983. 384 с.

7. Nocedal J., Wright S. Numerical Optimization: 2nd ed. Springer; 2006. 684 p.

8. Bertsimas D., ten Eikelder S.C.M., den Hertog D., Trichakis N. Pareto Adaptive Robust Optimality via a Fourier-Motzkin Elimination Lens. Math. Program. 2024;205(9):485–538. https://doi.org/10.1007/s10107-023-01983-z

9. Смирнов А.В. Сравнение алгоритмов многокритериальной оптимизации характеристик радиотехнических устройств. Russian Technological Journal. 2022;10(6):42−51. https://doi.org/10.32362/2500-316X-2022-10-6-42-51

10. Doikov N., Stich S.U., Jaggi M. Spectral Preconditioning for Gradient Methods on Graded Non-convex Functions. Preprint. 2024. https://arxiv.org/pdf/2402.04843v1

11. Yaochu J. A Comprehensive Survey of Fitness Approximation in Evolutionary Computation. Soft Computing. 2005;9(1): 3–12. https://doi.org/10.1007/s00500-003-0328-5

12. Hong L.J., Zhang X. Surrogate-Based Simulation Optimization. Preprint. 2021. https://arxiv.org/pdf/2105.03893v1

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

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

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

16. Hansen N. The CMA Evolution Strategy: A Tutorial. Preprint. 2016. https://arxiv.org/abs/1604.00772v2