Как и большинство событий этого года, конференция GECCO вынуждена была переместиться в онлайн. На протяжении четырех с половиной дней специалисты в области эволюционных вычислений обменивались своими достижениями, обсуждая наиболее актуальные вопросы в своей области.
«Эволюционные вычисления ― это способ решать очень трудные задачи, такие трудные, что их не получается решать нормально какими-то другими методами, ― поясняет руководитель лаборатории «Эволюционные вычисления» Университета ИТМО Максим Буздалов. ― В первом приближении это способ применить разные метафоры, такие как эволюция, естественный отбор, мутации, скрещивания, для решения сложных задач. Потенциальное решение кодируется в виде некой особи, и эти особи участвуют в своеобразной эволюции, проходящей целиком на компьютере. Иногда берутся и другие метафоры из физики, из коллективного поведения. Изобретаются также и другие алгоритмы, которые используют не только и не столько эти метафоры, сколько накопившееся понимание процесса решения различных задач подобными алгоритмами. Тем не менее, основная черта всех таких алгоритмов в том, что одним алгоритмом можно решать много разных, слабо связанных между собой задач».
Конференция GECCO проводится уже более 30 лет. Здесь представляются доклады по различным областям эволюционных вычислений, включая, например, генетическое программирование, вещественнозначную оптимизацию, комбинаторную оптимизацию и другие тематики. В этом году общее количество докладов в программе, включая полные выступления, краткие постерные доклады и доклады на воркшопах, превысило 350.
«GECCO ― это вторая по размеру международная конференция по эволюционным вычислениям и первая по значимости, ― рассказывает Максим Буздалов. ― Основополагающие результаты ― те, которые обязательно нужно, чтобы все, кто в этом принимает участие, и те, кто этим пользуется, услышали ― приносятся именно на GECCO».
На протяжении последних лет сотрудники Университета ИТМО регулярно представляют свои научные достижения на этой конференции.
«Наш вуз начинает узнаваться как университет с хорошей наукой, ― комментирует важность постоянного участия в GECCO Максим Буздалов. ― Отчетливо помню, как в прошлом году идет наша делегация, нас было 10 человек примерно, и нас уже узнают, шутят, что "русская мафия" приехала. Наше постоянное присутствие в этой предметной области показывает вклад российской науки в эту область знаний: что мы есть, мы крепкие, мы постоянно приносим интересные результаты. Мне кажется, что нас уже видят как научную школу и относятся к нашей работе соответствующим образом, что дорого стоит».
В этом году наградами были отмечены две работы Университета ИТМО. В номинации human-competitive бронзовую награду получила команда, в которую вошли сотрудники Университета ИТМО Екатерина Носкова, Владимир Ульянцев, Стивен О’Брайен, Павел Добрынин. Команда исследователей, в которую вошли Денис Антипов и Максим Буздалов, получила приз за лучшую в своей области работу. Подробнее о своей работе ученые рассказали ITMO.NEWS.
Екатерина Носкова
инженер-исследователь Университета ИТМО, обладательница бронзовой награды в категории Human-competitive Results Awards
О конкурсе
Полученная нами награда впервые была учреждена в 2004 году и с тех пор конкурс по ней проводится в рамках конференции GECCO каждый год. Это конкурс для уже опубликованных работ, которые посвящены human-competitive, то есть каким-то методам, которые позволяют автоматически найти решения для таких задач, которые требовали использование человека. Причем полученные решения являются лучшими по сравнению с теми, которые мог бы придумать человек.
Конкурс проводится в несколько этапов: сначала нужно прислать описание своей работы, затем отбираются финалисты, которые должны сделать презентацию и выступить на конференции. По результатам выступлений жюри присуждает три, а иногда и четыре призовых места.
О научных результатах
Мы представили нашу работу по генетическому алгоритму для поиска эволюционных историй популяций. Наш новый метод позволяет автоматически построить такие истории по геномным данным. До нашей работы это делалось практически вручную ― отбирались разные модели, затем находились оптимальные параметры этих моделей, и они сравнивались между собой.
Наш алгоритм позволяет избежать всей этой процедуры: у нас все происходит автоматически, никакого перебора моделей теперь не требуется, можно просто запустить нашу программу и наслаждаться полученной историей. Также мы провели эксперименты на данных, для которых уже были выведены эволюционные истории в существующих статьях старым методом. И нам удалось показать, что практически во всех случаях можно найти что-то лучшее, чем было найдено. Мы попробовали 47 разных экспериментов и только в одном не удалось найти лучше, чем в оригинальной работе. А также наши результаты позволили получить какую-то новую информацию об истории популяций ― например, людей.
Мы продолжаем проверять истории, которые уже были получены в ходе каких-то других исследований и очень редко оказывается, что они действительно являются самыми лучшими. Поэтому наш метод позволит получить очень много новой информации о том, как развивались различные популяции и виды.
О конференции
Я впервые участвовала в подобного рода мероприятии, поэтому на самом деле мне было очень интересно просто попробовать. В этом году из-за того, что конференция проводится удаленно, мы записывали видео с профессиональным видеооператором (спасибо ему огромное). Это также был мой первый опыт, я сильно переживала.
А потом я увидела другие работы и они показались мне очень хорошими, так что я уже и не надеялась что-то получить. Из-за того, что у конкурса нет определенной области, очень сложно судить о том, насколько задача, которую решает проект, действительно сложная и насколько трудно было ее решать. Но потом объявили результаты и нам присудили третье место ― это очень здорово!
Денис Антипов
программист Университета ИТМО, лауреат Best Paper Award GECCO-2020
О награде
На большинстве научных конференций лучшие представленные статьи принято награждать так называемой Best Paper Award. На GECCO на каждой секции выделяют до трех номинантов, за которых голосуют участники, выбирая лучшие исследования и результаты.
Номинантов определяет узкий круг лучших специалистов по тематике секции. В случае, когда на секции не представлено много статей, несколько секций объединяют в одну группу. В этом случае борьба за награду становится более серьезной, так как идет уже между несколькими научными подсообществами, а не внутри одного. Можно сказать, что получение награды за лучшую статью отражает признание со стороны широкого научного сообщества, ее большого влияния на текущие исследования.
О научных результатах
Наша работа посвящена теоретическому анализу эволюционных алгоритмов. Математически описать такой процесс и сделать какие-то выводы о том, сколько алгоритму нужно времени для нахождения оптимума, часто является сложной задачей. В нашей работе присутствовала также дополнительная сложность ― мы исследовали эффективность случайного динамического выбора параметров на каждой итерации.
Неожиданно оказалось, что такой случайный выбор параметров работает лучше, чем любой статический выбор. Причем, экспериментальное исследование показало, что такая стратегия динамического выбора параметров оказывается эффективной не только на модельных задачах, на которых был проведен теоретический анализ, но и на более практических задачах.
Время работы эволюционных алгоритмов сильно зависит от значений параметров алгоритма, причем для максимальной эффективности надо выбирать параметры на ходу. Особенность нашей работы в том, что мы впервые доказали высокую эффективность метода динамического выбора параметров алгоритма, заключающегося в том, что на каждой итерации мы выбираем один из параметров алгоритма в соответствии со степенным законом с определенными параметрами.
Несмотря на кажущуюся простоту, этот метод оказался так же эффективен на модельной задаче OneMax, как и самые эффективные ранее предложенные методы. К тому же эти методы, предложенные ранее, были несколько заточены под задачу. Например, при решении более близких к практике задач приходилось вводить дополнительные ограничения на возможные значения параметров. Предложенный нами алгоритм работает «из коробки» в том числе и на таких более сложных практических задачах.
Мы показали, что такой выбор параметра из случайного распределения является очень интересным для использования на практике. Ранее в другой работе, рассматривающей более простой алгоритм, уже было показано, что данный метод может избавить пользователя алгоритма от необходимости поиска оптимальных параметров, практически не уменьшая производительность, достигаемую при оптимальном выборе параметров алгоритма (который на практике не всегда возможен).
Теперь же, когда мы показали, что такой метод выбора параметров способен даже улучшить время работы алгоритма, мы надеемся, что он найдет успешное применение и для сложных практических задач. Мы продолжаем исследования в рамках международного гранта РФФИ 20-51-15009 «Теоретические основы динамической настройки параметров в эволюционных алгоритмах».
Лично для меня это огромное достижение и кульминация моей учебы в аспирантуре. Когда объявили победителей, я радовался так, как не радовался четвертому голу Ливерпуля в ворота Барселоны. Мне очень приятно, что идея, которая родилась у нас с моими научными руководителями, была так хорошо принята научным сообществом, которое занимается исследованием эволюционных алгоритмов.
