Что такое эволюционные алгоритмы
Эволюционные алгоритмы — метаэвристические методы поиска, которые часто используются для решения сложных, не поддающихся другим методам, задач оптимизации. Они основаны на метафорах, взятых из биологической эволюции: как и в природе, в эволюционных алгоритмах популяции, состоящие из множества особей, развиваются в течении нескольких поколений, подчиняясь законам естественного отбора по принципу «выживает наиболее приспособленный», сформулированному Чарльзом Дарвином.
Где они применяются
Эволюционные алгоритмы применяются для решения целого спектра задач, среди которых составление расписаний, задачи компоновки, синтез и оптимизация программ, построение объектов сложных форм и многое другое.
Основные термины
Предположим, у вас есть задача, для которой можно найти множество решений. Каждому решению соответствует некоторое значение целевой функции, которую требуется оптимизировать (например, максимизировать или минимизировать). Алгоритм может вычислить эту функцию, выбрать несколько лучших решений, создать на их основе новые и повторять этот процесс, пока не найдется удовлетворяющее решение.
Если описать этот метод определениями из «Происхождения видов» Чарльза Дарвина, то решение задачи — это «особь», набор решений — это «популяция», целевая функция — это «функция приспособленности» (которая определяет, насколько хорошо особь приспособлена к окружающей среде). Кроме того, в эволюционном алгоритме обязательно встретится «оператор мутации», соответствующий внесению случайных мутаций в геном особи, нередко также бывает «оператор скрещивания», совмещающий отдельные качества нескольких родительских особей в потомках, а «естественный отбор» представлен различными «операторами селекции».
Подробнее о том, где можно узнать о ключевых исследованиях в области эволюционных вычислений, об особенностях конференции GECCO и работе ученых Университета ИТМО мы поговорили с руководителем лаборатории «Эволюционные вычисления» Университета ИТМО Максимом Буздаловым и научным сотрудником факультета информационных технологий и программирования Ариной Буздаловой.
Ученые Университета ИТМО являются постоянными участниками конференции GECCO. Что отличает эту конференцию от других?
Максим: В целом в области эволюционных вычислений проводится три больших значимых конференции. Помимо GECCO, это IEEE Congress on Evolutionary Computation (CEC) и Parallel Problem Solving from Nature.
Конференцию GECCO выделяется одновременно очень высоким качеством рецензирования и масштабом. Одной из интересных черт GECCO является четкое отслеживание расписания докладов на секциях. Почему это важно? Достаточно много специалистов ходят не по секциям, а по наиболее интересным для них докладам. На GECCO это нормальная практика, так как за счет четкого тайминга вы можете успеть выслушать интересный доклад, задать вопросы и успеть на следующий, который читается уже совершенно в другом зале. Здесь нормально относятся к тому, что вы не будете сидеть на секции от начала до конца.
Арина: Это в том числе повышает мотивированность: люди ходят именно туда, где им интересно. Но, помимо этого, на GECCO есть возможность создать интересные коллаборации. Кто-то занимается одним направлением, например, применением эволюционных вычислений в играх, кто-то занимается теорией, и вдруг неожиданно они объединяются, делают что-то совместное. Это очень здорово. За счет столкновения разных направлений получается создать среду, в которой рождаются интересные проекты.
В этом году на конференции выступил Инго Рехенберг (Ingo Rechenberg), пионер в области эволюционных вычислений и искусственной эволюции. Он изобрел набор методов оптимизации, известных как эволюционные стратегии (термин исходно был предложен на немецком языке и звучит в нем как Evolutionsstrategie). Еще один интересный факт: в его честь назван паук-акробат Cebrennus rechenbergi, который обитает в пустыне Намиб. Рехенберг вдохновился его способом передвижения, который представляет собой серию непрерывных сальто, и создал по его подобию робота. Эту разработку ученый планирует использовать для исследования Марса. Что интересно, Рехенберг до сих пор является действующим ученым и много путешествует.
Какие актуальные тенденции участники конференции рассмотрели в этом году? И если говорить более широко, какие тренды существуют сейчас в вашей области?
Арина: Я бы выделила два разных направления. Во-первых, если говорить глобально о конференции, на мой взгляд, стало больше докладов, связанных с применением эволюционных вычислений в глубоком обучении и в обучении с подкреплением, в частности, в глубоком обучении с подкреплением. Я думаю, что это в целом актуальный тренд на современном этапе развития технологий, поэтому это не могло пройти мимо нас. Эволюционные вычисления в том числе применяются для генерации структуры нейронной сети.
Максим: Например, одним выводом из первого же пленарного доклада было следующее: что глубокое обучение, что разные ветви генетического программирования могут рассматриваться как точки на едином континууме похожих друг на друга методологий. И один из прогрессивных способов мышления заключается в том, чтобы не делать различий между ними.
Безусловно, с одной стороны, мы понимаем, что есть большие объемы данных, есть различные архитектуры нейронных сетей, все смотрят на Google с восхищением… С другой стороны, есть генетическое программирование, в котором данных, как правило, поменьше, но какие-то новые структуры, способные «склеить» программы и начать их выращивать, изобретают чуть ли не каждый год. Таким образом, наметился некоторый перелом в сторону того, чтобы не пытаться дистанцироваться от машинного обучения, в частности, глубокого обучения с подкреплением, и определенными направлениями, связанными с эволюционной тематикой.
Пионерами в этой области неожиданно выступают специалисты в области глубоких нейронных сетей — они смотрят на то, что было создано за это время в рамках генетического программирования, пытаются взять что-то из этого себе, но и, с другой стороны, поделиться чем-то своим.
Арина: И второе направление — это уже некий внутренний тренд. Дело в том, что в том же машинном обучении довольно хорошо выстроена традиция тестирования алгоритмов, сравнения их друг с другом, есть стандартные датасеты и так далее. В эволюционных вычислениях, особенно в части дискретной оптимизации, с этим гораздо хуже по определенным историческим, объективным причинам. Задачи дискретной оптимизации очень разные, поэтому сложно составить стандартизированный датасет. Но, тем не менее, специалистам очень важно иметь стандартные средства тестирования и сравнения алгоритмов. Поэтому научное сообщества движется в сторону выработки общей стратегии. Этому также было посвящено много секций в этом году.
Если возвращаться к машинному обучению, к каким интересным результатам может привести сближение этого направления с эволюционными вычислениями?
Максим: В этом можно разбираться достаточно долго, и думаю, что я могу дать только часть ответа. Есть мысль, что сейчас все активно занимаются большими данными, потому что где-то они являются доступными и на них проще натренироваться, поэтому и размеры сетей тоже получаются достаточно большими.
С другой стороны, время от времени в глубоком обучении возникают какие-то прорывы, которые позволяют делать все то же самое, но с гораздо меньшими усилиями (за меньшее время или с привлечением меньшего объема данных). Ряд таких вещей связан даже не с тем, что кто-то, скажем, придумывает радикально новую архитектуру нейронной сети, а с тем, что меняется сама постановка вопроса. И мне кажется, что в ряде случаев то, что будет наблюдаться на стыке генетического программирования и глубоких сетей, будет выглядеть примерно таким образом. То есть либо будут предложены невиданные ранее архитектуры, либо ранее невиданные способы ответа на уже существующие вопросы.
Арина: На мой взгляд, когда мы соединяем эволюционные алгоритмы и нейронные сети, мы приближаемся к идее об эволюционирующих роботах, высказанной еще в 50-е годы Тьюрингом. Смысл ее в том, что можно создать своего рода «робота-ребенка», он будет чему-то обучаться, но скорее всего будет не идеален, поэтому потребуется несколько поколений, как в природе. Возможно, мы оказываемся близки к тому моменту, когда нейронные сети смогут (образно говоря и не вдаваясь в детали) эволюционировать сами.
В этом году представительство ученых Университета ИТМО на конференции было рекордным — 11 докладов. С чем это связано?
Арина: Некоторое время назад мы начали сотрудничество с профессорами Каролой и Бенджамином Доеррами из Сорбонны и École Polytechnique. И такой всплеск публикационной активности в этом году я связываю с этими совместными исследованиями. Уже давно Бенджамин Доерр реализует совместную аспирантуру с нами. В этой программе также участвует наш коллега Денис Антипов, который стал набирать уже и своих студентов. Один из них — Виталий Караваев, который получил приз за лучший доклад на студенческой секции. Так что Виталия уже в каком-то смысле можно назвать нашим «научным внуком».
Кроме того, совместно с Каролой Доерр мы сформулировали достаточно много тем дипломных работ. И в этом году целых пять студентов под нашим и ее руководством успешно защитили свои работы. Помимо этого, что редко бывает в случае с бакалаврами, удалось сразу же написать статью на международную конференцию. Таким образом, сотрудничество, которое развивалось в последние годы, принесло свои плоды и позволило начинающим ученым так успешно выступить на конференции.
Например, еще один наш студент Иван Игнашов совместно с Каролой Доерр внес вклад в разработку библиотеки, или специальной платформы для тестирования эволюционных алгоритмов. В первую очередь, тех, которые решают задачи комбинаторной оптимизации. Иван разработал способ отображения информации, который бы позволял проследить взаимосвязь между качеством получаемых решений, вероятностью того, что мы получим, и временем, которое необходимо для нахождения результатов.
С какими направлениями связаны исследования вашей группы, представленные на GECCO в этом году?
Максим: Несмотря на то, что мы — небольшая группа, мы занимаемся достаточно разнообразными тематиками.
Так, один из докладов, который был представлен на конференции, представляет собой исследование, выполненное совместно с Владимиром Ульянцевым и Александром Семёновым (Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения РАН). Здесь, основываясь на идеях Александра Семёнова, мы предложили весьма серьезное применение эволюционных алгоритмов в криптоанализе. Чем это интересно? В нашем случае эволюционный алгоритм используется как один из элементов сложной, комбинированной методики. Мой вклад в работу заключался в том, как применить в этой методике математическую статистику, чтобы, в том числе, сократить время работы алгоритма. Конечно, получилось так, что главной целью этой работы оказалась возможность рассказать людям, что эволюционные алгоритмы в криптоанализе можно и нужно применять. И мы представили один из работающих, серьезных способов сделать это. Данная работа была поддержана грантом Российского научного фонда №18-71-00150.
Еще одно важное для нашей лаборатории направление — структуры данных. В последние два года я занимаюсь разработкой солверов для различных задач, близких к задачам вычислительной геометрии, которые возникают в многокритериальных эволюционных алгоритмах. В прошлом году я пришел на конференцию с постановкой задачи, к которой можно свести весьма много задач, возникающих в популяционных многокритериальных эволюционных алгоритмах. При этом вместе с постановкой задачи был предложен не только эффективный алгоритм ее решения, но и его весьма качественная реализация, которая может «из коробки» использоваться всеми заинтересованными исследователями.
В этом же году я перешел из разряда задач, когда все входные данные известны, к решению задач, когда входные данные дополняются со временем. Выяснилось, что здесь все гораздо менее радужно. Солвер не получился, но получилось несколько проверок концепции — иными словами, ряд сценариев, которые показывают, что эта задача, в отличие от предыдущих, гораздо менее однородна, а следовательно, более интересна. Данная работа была поддержана грантом Российского научного фонда №17-71-20178.
Где конкретно это может быть использовано?
Максим: Многокритериальные эволюционные алгоритмы, как правило, сложнее тех, где надо оптимизировать всего одну величину. Сегодня большинство таких алгоритмов оперирует в многомерных пространствах — каждому критерию соответствует своя ось координат. Таким образом, значению приспособленности каждого решения соответствуют точки в многомерном пространстве, с которыми нужно что-то делать. Но в силу того, что авторы таких алгоритмов и специалисты в области вычислительной геометрии почти не пересекаются, здесь господствует изобретение велосипедов. Причем очень медленно едущих велосипедов. Иными словами, на пустом месте возникают очень тяжелые, неповоротливые алгоритмы.
В свете своего олимпиадного прошлого (Максим Буздалов — чемпион мира по программированию — прим.ред.) я с этим борюсь. Мои нынешние подходы приводят к тому, что можно обобщить имеющийся алгоритмический материал, по результатам обобщения написать одну процедуру и собственноручно сделать ее как можно более эффективной, чтобы все остальные, кому лень вдумываться, как это работает, могли просто пользоваться этим. Упрощая, можно сказать, что получается вклад во все многокритериальные эволюционные алгоритмы сразу. Исследования такого рода составляют примерно половину работ, выполняемых под моим руководством в рамках гранта Российского научного фонда №17-71-20178.
Как вы отметили, в основном вы занимаетесь преимущественно фундаментальными вопросами, теорией эволюционных алгоритмов. Если говорить о прикладных исследованиях, как вы работаете в данном направлении?
Арина: Мы занимаемся теорией эволюционных алгоритмов, но не просто теорией, а сокращением разрыва между теорией и ее практическим применением, использованием. И это не только направление нашей лаборатории, но и в целом очень важная задача для теоретического сообщества эволюционных вычислений на данный момент. Есть специальные гранты, которые посвящены именно этому, мы в них тоже участвуем. И другие наши работы тоже можно охарактеризовать как работы, стремящиеся сократить разрыв между теорией и практикой.
Например, наши студенты Анна Родионова и Кирилл Антонов подготовили доклад в соавторстве с Каролой Доерр и мной. В этой работе ребята показали, что не всегда стоит слепо использовать асимптотические, или иными словами теоретические оценки.
Представьте, что существует алгоритм, про который доказано, что он оптимален для определенной задачи, что асимптотически он работает не хуже, чем все остальные возможные алгоритмы. Но здесь ключевое слово «асимптотически». Это значит, что он работает лучше в случае, когда определенные параметры достаточно велики. Например, когда у нас есть достаточно большая популяция. Но на практике большая популяция, особенно если мы хотим распараллеливать процесс вычисления приспособленности особей, означает то, что у нас должно быть очень много процессоров, несколько тысяч.
Реальнее использовать десятки, сотни процессоров, но здесь ситуация уже другая, в этом случае метод уже не является оптимальным. Кроме того, если у нас поколение порядка десятка особей, оптимальны одни методы, если сотни — другие. К сожалению, не всегда на текущем уровне исследований теоретические результаты позволяют это увидеть. Все это ребята показали в своей работе, которая поднимает очень важный вопрос о границах применимости теории в практических условиях.
Вы также отметили, что работа выпускника бакалавриата Виталия Караваева стала лучшей на студенческой секции. Что именно, на ваш взгляд, позволило одержать победу?
Максим: Важная тенденция последних десяти лет заключается в том, что ряд результатов замечательны не сами по себе, а тем, с помощью чего они были получены. То есть, если в процессе работы над конкретным алгоритмом или конкретной задачей исследователь придумал какую-то общую технику, которая может быть использована другими для достижения собственных целей, это ценится гораздо выше, чем просто результат, полученный с помощью стандартных методик. Например, даже в ряде случаев вопрос «Насколько новаторские техники были использованы?» выносится в качестве подсказки для рецензентов. Это важный критерий оценки и, если новаторские техники есть, это большой плюс. В работе Виталия такой плюс есть.
Для доказательства времени работы исследуемого алгоритма авторам работы понадобилось сильно уточнить одну из теорем. В изначальном виде она про математическое ожидание времени работы некоторого процесса, также разные варианты есть у нее для того, чтобы оценить, насколько значение случайной величины может отклониться от ее математического ожидания. В процессе получение основного заявленного результата работы Виталий вместе со своими научными руководителями как раз смог сильно уточнить это отклонение, что является важной частью исследования.
В целом то, что представлялось по этому исследованию на студенческой секции — предварительная версия. Расширенную статью по этой тематике также приняли на конференцию Foundations of Genetic Algorithms (FOGA), которая состоится уже в конце августа. Это очень престижная, влиятельная конференция, проходящая раз в два года, на которой, как правило, представляется очень немного докладов (в этом году их всего 13). И каждая работа (в частности, и работа Виталия) — это, без преувеличения, хит.
