Фреймворк и бенчмарк глобальной оптимизации

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

Целью данной работы является создание программно-алгоритмического инструментария, обеспечивающего для разработчиков алгоритмов возможность проведения быстрого сравнительного анализа с существующими методами на ряде представительных задач.
Задачи:
1. разработка программного фреймворка с постоянно пополняемой библиотекой методов и набором методических указаний по реализации новых алгоритмов;
2. создание бенчмарка – пополняемого банка, включающего задачи, классифицированные по различным характеристикам (размерность, характер целевой функции и т.п.) и указания по тестированию методов;
3. создание банка результатов тестирования библиотечных алгоритмов, включая наборы стартовых точек.

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

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

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

1. метод сопряженных градиентов (Conjugate gradient method, CGM);

2. алгоритм Бройдена-Флетчера-Гольдфарба-Шанно с ограниченным использованием памяти  (Limited-memory Broyden — Fletcher — Goldfarb — Shanno algorithm,  L-BFGS);

3. метод имитации отжига (Simulated Annealing, SA);

4. эволюционный алгоритм (Evolutionary Algorithm, EA);

5. метод дифференциальной эволюции (Differential Evolution, DE);

6. метод роя частиц (Particle Swarm Optimization);

7. поиск с запретами (Tabu Search, TS);

8. эволюционная стратегия адаптации матрицы ковариаций (Covariance Matrix Adaptation Evolution  Strategy, CMA-ES);

9. гибридный алгоритм на основе EA и PSO;

10. гибридный алгоритм на основе DE и CGM.

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

 

В рамках данной работы были получены следующие результаты:

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

Разработанный программный комплекс внедрен в учебный процесс Института математики и информатики БГУ в рамках учебной практики.

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

1. Гилл Ф. Практическая оптимизация / Ф. Гилл, У. Мюррей, М. Райт. – Москва: Мир, 1985. – 510 с.
2. Сороковиков П. С., Кононова О. В. Фреймворк и бенчмарк методов глобальной оптимизации. // Международный молодежный научный форум «Ломоносов-2015», Москва, 2015.
3. Хабитуев Б. В., Хаптахаева Н. Б., Сороковиков П. С., Кононова О. В., Лиджеев А. В. Выбор оператора мутации в эволюционных алгоритмах // Современные проблемы науки и образования. – 2014. – № 6; URL: www.science-education.ru/120-15732 (05.12.2014).
4. Kennedy J. Particle swarm optimization / J. Kennedy, R. C. Eberhart // In Proceedings of IEEE International Conference on Neural Networks. – 1995. – P 1942–1948.
5. Mitchell M. An Introduction to Genetic Algorithms. Cambridge: MIT Press, 1999. – 158 p.
6. Nocedal J. Numerical Optimization / J. Nocedal, S. Wright. – 2nd ed. –Springer, 2006. – 664 p.

The global optimization with parallelepiped limitations is one of the most common and popular areas of mathematics in the light of current applications for data analysis and machine learning. Due to the subject relevance and the increased computer production one can observe a growing interest of researchers and practitioners - quite a lot of new approaches, methods and algorithms are being developed. Among the most urgent problems there are the issues of effective implementation and comparative analysis of algorithmic software. For the empirical comparison, as a rule one has to implement not only the algorithm, but also a number of third-party algorithms, and to spend a large number of testing hours on the same set of test problems. This research discusses the approaches on creating of a software framework of the global optimization designed to simplify the process of testing of the developed algorithmic support