Студенты кафедры компьютерных технологий и сотрудники одноименной лаборатории являются постоянными участниками конференции GECCO, которая проводится организацией ACM SIGEVO – подразделением Association for Computing Machinery по генетическим и эволюционным вычислениям. О результатах своих научных исследований в области эволюционных алгоритмов ученые и инженеры со всего мира докладывают с 1999 года. На конференции обсуждаются самые актуальные вопросы и темы в таких областях, как генетические алгоритмы, сложные системы, цифровая индустрия развлечений и искусство, машинное обучение, численная оптимизация и многое другое.
Максим Буздалов и Бенджамин Доерр представили на GECCO-2017 результаты своих исследований, в ходе которых им удалось определить, при каких условиях недавно предложенный генетический алгоритм (1+(λ, λ)) эффективно решает задачу о выполнимости (SAT), и математически это доказать (ознакомиться с расширенной версией статьи на arXiv можно по ссылке).
Что такое генетические алгоритмы
Главная задача генетических алгоритмов – это, как правило, решение различных задач оптимизации. Предположим, есть задача, для которой можно найти множество решений. Каждому решению соответствует некоторое значение целевой функции, которую требуется оптимизировать. Алгоритм может вычислить эту функцию, на основе полученных результатов выбрать несколько лучших решений, создать на их основе новые и повторять этот процесс, пока не найдется удовлетворяющее решение. Если описать этот метод определениями из «Происхождения видов» Чарльза Дарвина, то решение задачи — это «особь», набор решений — это «популяция», целевая функция — это «функция приспособленности» (которая определяет, насколько хорошо особь приспособлена к окружающей среде), а генетический алгоритм — это «естественный отбор». Подробнее о генетических алгоритмах можно прочитать здесь.
Генетические алгоритмы, а также другие алгоритмы из области эволюционных вычислений, являются, главным образом, инструментом для решения практических задач. Но и для применения на практике необходимо понимание того, когда, почему и насколько хорошо работают такие алгоритмы, а значит, нужны теоретические исследования. В последние двадцать лет стало понятно, что наиболее значимые теоретические результаты получаются, если рассматривать простые (с точки зрения описания) задачи оптимизации и простые же эволюционные алгоритмы и математически строго доказывать оценки на время работы этих эволюционных алгоритмов на этих задачах. При этом под временем работы чаще всего подразумевается число вычислений функции приспособленности.
Двумя «рабочими лошадками» теории эволюционных вычислений является задача OneMax и так называемый «эволюционный алгоритм (1+1)». В задаче OneMax особями являются строки фиксированной длины, состоящие из нулей и единиц, оптимумом является строка из всех единиц, а функцией приспособленности — число единиц, которое требуется максимизировать. Эволюционный алгоритм (1+1) является, пожалуй, самым простым эволюционным алгоритмом. В нем есть родительская особь и дочерняя особь, получаемая из родительской применением оператора мутации, при котором каждый ген особи с некоторой небольшой вероятностью заменяется на противоположный. Если дочерняя особь получается не хуже, чем родительская, то она заменяет родительскую особь.
Долгое время алгоритм (1+1) оставался «чемпионом» среди практически используемых эволюционных алгоритмов по решению задачи OneMax. В частности, более продвинутые алгоритмы (например, генетические алгоритмы, использующие еще и оператор скрещивания, оперирующий сразу с двумя особями), как правило, работали хуже. Остро стоял вопрос — а нужен ли вообще оператор скрещивания? Кроме того, было известно, что алгоритм (1+1) не является теоретически оптимальным — когда оптимизация практически подходит к концу, этот алгоритм извлекает все меньше и меньше информации из каждого вычисления функции приспособленности, а значит движется к цели все медленнее и медленнее. Причиной этому является то, что информацию из «плохих» особей этот алгоритм извлекать не умеет, а «хорошие» особи становятся слишком похожими друг на друга.
Как компенсировать эти недостатки?
В 2013 году Бенджамином Доерром с соавторами был предложен новый генетический алгоритм, получивший название (1+(λ, λ)), который компенсировал указанные выше недостатки. Итерации нового алгоритма двухэтапные — на первом этапе особи генерируются с помощью более агрессивного оператора мутации (что позволяет извлекать информацию из «плохих» особей), на втором этапе лучшая особь «отдает все самое лучшее» родителю с помощью оператора скрещивания. За счет этого новый алгоритм стал решать задачу OneMax асимптотически быстрее как в теории, так и на практике.
Производительность этого алгоритма возросла по сравнению с известными алгоритмами не только на задаче OneMax, но и на ряде других задач. В частности, в 2014 году было показано, что этот алгоритм достаточно хорошо справляется с решением задачи о выполнимости (SAT). Эта задача занимает центральное место в теории вычислительной сложности. В другой работе 2015 года было показано, что при определенных условиях задача SAT, с точки зрения эволюционного алгоритма (1+1), может напоминать задачу OneMax. А значит есть шанс, что алгоритм (1+(λ, λ)) будет быстрее, чем алгоритм (1+1), и на задаче SAT. На конференции GECCO Максим Буздалов и его коллаборатор Бенджамин Доерр рассказали, как это получилось доказать.
«Мы не только доказали теоретически, что алгоритм (1+(λ, λ)) работает быстро, но и сделали действительно быструю его реализацию. Мы научились решать задачи о выполнимости с 1 000 000 переменных и десятками миллионов дизъюнкций всего лишь за 45 минут на обычном ноутбуке, а задачу OneMax размером в 16 миллионов переменных — за пару минут. Наши соперники на конференции отставали от нас в обеих "номинациях" или по числу переменных, или по времени работы как минимум в 10 раз», – рассказал Максим Буздалов.
Он добавил, что разработанный им и его коллегой алгоритм еще требует доработки, но уже сейчас используется другими программистами-теоретиками для решения исследовательских задач. В будущем он совместно с коллегами-теоретиками и другой научной группой, находящейся примерно посередине между эволюционными алгоритмами и SAT-солверами, хочет разработать алгоритм, вбирающий все самое лучшее из имеющихся разработок, который вполне может стать достойным «оружием» против задач дискретной оптимизации. Не исключено и то, что разработанные Максимом Буздаловым и Бенджамином Доерром решения могут найти некоторое применение в алгоритмах глубокого машинного обучения при синтезе структуры нейронной сети.
Кроме того, на GECCO-2017 совместная работа Максима Буздалов и аспирантки кафедры компьютерных технологий Нины Булановой была признана лучшей на студенческой секции. Эта работа была посвящена следующему вопросу: в теоретических исследованиях обычно при скрещивании двух особей в генетическом алгоритме на выходе получается одна особь. По-видимому, так происходит потому, что в случае задачи OneMax после определения приспособленность одной «дочерней» особи сразу же станет известна приспособленность другой. При этом на практике чаще используют операторы скрещивания, результатом которых являются две особи. Исследователи из Университета ИТМО доказали, что и в теоретических исследованиях — как в случае задачи OneMax, так и в некоторых других задачах — можно получить ускорение, если использовать в эволюционных алгоритмах обе «дочерние» особи.
