Наши «оптимисты» самые оптимистичные в мире! Сотрудники СибИПСА победили на всемирном соревновании в рамках Конгресса по эволюционным вычислениям

Дата публикации:

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

Видеть смысл происходящего намного глубже и точнее

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

Odoo изображение и текстовый блок

- Конечно. В том интервью я упоминал, что наши молодые ученые заняли второе место во всемирном соревновании оптимизационных алгоритмов 2018 года и что впереди у них – новые достижения. И вот не прошло и трех лет, как Владимир Становов и Шахназ Ахмедова разработали алгоритм – победитель этого ежегодного конкурса. Причем в этом году соревнование проводилось в рамках сразу двух главных ведущих мировых конференций по эволюционной оптимизации - Congess on Evolutionary Computation, CEC 2021, и Genetic and Evolutionary Computation Conference, GECCO 2021. Прогресс выглядит весьма оптимистично, не так ли?

Кроме того, понимание теории оптимизации позволяет быть что называется хорошо информированным оптимистом. Часто можно услышать в выступлениях и прочитать в различных текстах выражения вроде «… нам удалось найти более оптимальное решение…» или «… данное решение является наиболее оптимальным…» и т.п. Нам сразу понятно, что эта фраза принадлежит неграмотному человеку, пытающемуся выглядеть профессионалом. По определению, оптимальным является наилучшее решение в заданных условиях. Более наилучшего или наиболее наилучшего решения, конечно, не может быть. Если новое решение выглядит еще «лучше», чем известное «оптимальное», то либо изменились условия и то решение теперь не оптимальное, либо (если условия не изменились) то решение и не было оптимальным. А значит вновь найденное решение – просто оптимальное. Либо это грубая ошибка и новое решение вообще неправильное. Эти теоретические сведения, хорошо усвоенные и многократно примененные на практике, позволяют быть оптимистом. Хорошо информированным оптимистом. Видеть оптимальное решение и делать все, чтобы его реализовать. В сложившихся условиях. Великий немецко-российский математик Леонард Эйлер однажды сказал: «В мире не происходит ничего, в чем не был бы виден смысл какого-нибудь минимума или максимума». Владение наукой оптимизации позволяет видеть смысл происходящего намного глубже и точнее.

Просто точно выполнить всю работу

- В чем суть соревнования, кто участвует, как оно проходит?

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

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

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

Odoo изображение и текстовый блок
Odoo изображение и текстовый блок

Организаторы соревнования из Сингапура и Индии после тщательной проверки исходных кодов всех методов и независимого тестирования выявляют преимущества соревнующихся алгоритмов. Список участвующих алгоритмов приведен в таблице 1. Участвовали научные группы из Египта, Индии, Словении, Польши, Чехии, других стран. Алгоритм наших ученых в списке – шестой (Е-125).

Таблица 1.

Odoo изображение и текстовый блок

Наши оптимизаторы (В.В. Становов и Ш.А. Ахмедова) уже не первый раз участвовали в подобных международных соревнованиях ведущих научных групп.

Цель подобных соревнований – создание самых передовых универсальных алгоритмических схем, которые могут в дальнейшем быть приняты на вооружение в иных областях науки, где требуется решать задачи поиска наилучшего решения. В 2018 году предыдущая версия алгоритма, L-SHADE-RSP, заняла второе место на этом же соревновании, уступив разработке китайских исследователей, для которой, однако, требовалось существенно больше вычислительных ресурсов.

Повышая уровень оптимизма

- Итак, соревнование началось и что происходило?

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

В результате организаторы соревнования установили преимущество нового алгоритма NL-SHADE-RSP, разработанного доцентами кафедры высшей математики Станововым Владимиром Вадимовичем и Ахмедовой Шахназ Агасувар кызы, над другими методами (см. таблицу 2). В частности, NL-SHADE-RSP лучше всех справился с самыми сложными тестовыми функциями, которые обладали специфическими свойствами, значительно усложняющими работу алгоритмов. Таким образом, наши оптимисты не только самые оптимистичные в мире, но и обладают свойствами, повышающими уровень своего оптимизма в самых сложных условиях.

Таблица 2.

Odoo изображение и текстовый блок

Опередить преследователя на 15%

- И что же это за алгоритм, столь оптимистичный?

- Это стохастический, т.е. основанный на использовании случайности, алгоритм, имитирующий процессы эволюции, а если быть совсем точным, то это алгоритм дифференциальной эволюции, схема которого предложена ранее зарубежными учеными и доработана нашими исследователями. В списке участников соревнования можно видеть, что не только наши оптимизаторы модифицируют исходный алгоритм (DE), но у наших получилось значительно лучше. Серебряный призер отстал от наших на целых 15%. Новый алгоритм исследователей СибИПСА воплощает несколько оригинальных идей, в числе которых адаптивное использование архива ранее найденных решений, нелинейное изменение размеров популяции, сортировка вероятностей скрещивания и ранговое селективное давление. Проводимая в данный момент работа научной группы также показывает, что некоторые элементы поисковых алгоритмов могут быть спроектированы автоматически, без участия человека. Т.е., в ходе решения задачи оптимизации алгоритм, в зависимости от накопленного опыта, будет сам перепроектировать себя под решаемую задачу. А это уже автоматизация информированного оптимизма и прямой путь к оптимальному алгоритму оптимизации. Что бы это ни значило.

Наши поздравления чемпионам мира по эволюционному оптимизму!

#sibgu #ReshU #ReshetnevUniversity#МинобрнаукиРоссии

Наша справка

Odoo изображение и текстовый блок
Odoo изображение и текстовый блок

Конгресс IEEE по Evolutionary Computing (CEC) - одна из крупнейших и наиболее важных конференций в рамках Evolutionary computing (EC). CEC охватывает большинство подразделов EC, таких как Эволюционная робототехника, Оптимизация нескольких целей, Эволюционируемое оборудование, Эволюционный дизайн и т.д. Конференция обычно привлекает несколько сотен участников, по итогам - публикация сотен статей.