Genetic and Evolutionary Computation Conference
Конференция Genetic and Evolutionary Computation Conference (GECCO) является ведущей в области эволюционных вычислений и в этом году проходила в японском городе Киото.
В конференции приняли участие Максим и Арина Буздаловы, Нина Буланова, Владимир Миронович, Денис Антипов, Маргарита Маркина и Илья Якупов. Такое большое число участников стало возможным благодаря обширной грантовой поддержке. Помимо средств программы 5/100 и гранта Российского научного фонда под руководством Максима Буздалова, участники получили гранты Ассоциации вычислительной техники (Association for Computing Machinery, ACM): Маргарита выиграла конкурс на стипендию ACM-Women Scholarship, а Денис, Нина и Илья получили студенческий travel grant.
Максим Буздалов представил доклад о том, как свести обширный перечень задач внутри многокритериальных эволюционных алгоритмов к одной обобщенной задаче. Для такой задачи Максим уже реализовал быстрый алгоритм решения.
Работа Ильи Якупова была посвящена структуре данных для многопоточной инкрементальной недоминирующей сортировки — операции, которая используется в многокритериальных эволюционных алгоритмах. Такая структура данных позволит реализовывать подобные алгоритмы асинхронно. В этом случае множество потоков, не дожидаясь друг друга, могут эффективно работать с одной популяцией. Однако наиболее эффективный способ реализации алгоритма оказался весьма неожиданным. О деталях можно узнать в расширенной версии.
Владимир Миронович представил совместную с Максимом Буздаловым и Валерием Вяткиным работу по применению анализа ландшафта функции приспособленности к практической задаче автоматической генерации промышленных систем управления. Исследование пространства поиска позволило разработать эффективный популяционный алгоритм, который решает данную задачу значительно быстрее простых алгоритмов оптимизации. Работа является примером удачного применения теоретических подходов к сложным практическим оптимизационным задачам. Доклад был номинирован на лучший в студенческой секции.
Денис Антипов и Арина Буздалова представили метод выбора вспомогательных критериев оптимизации, основанный на использовании популяционных алгоритмов и обучения с подкреплением. Удалось доказать, что применение этого метода существенно снижает время работы, необходимое для оптимизации сложной модельной функции с большим числом плато. Доклад также был номинирован на лучший в студенческой секции.
Еще одна работа Дениса была выполнена в соавторстве с Бенджамином Доерром. Авторы провели анализ времени работы (𝜇+𝜆) эволюционного алгоритма и дали точные верхние и нижние асимптотические оценки времени работы данного алгоритма на модельной задаче OneMax. Работа расширила понимание поведения популяционных эволюционных алгоритмов. Также был разработан новый метод анализа популяционных алгоритмов, который позволил дать нижнюю оценку времени работы подобных алгоритмов на всех унимодальных функциях.
Работа Нины Булановой была посвящена вычислительной сложности задачи OneMax для так называемых непредвзятых алгоритмов с операторами, использующими ограниченное число аргументов. Формулировка задачи OneMax довольно проста: особи являются битовыми строками фиксированной длины N, а максимизируемой функцией является число единичных бит. Непредвзятые алгоритмы — это алгоритмы, которые не имеют права отдавать предпочтение нулям перед единицами (или наоборот) или, например, первому биту перед вторым.
Уже это является довольно сильным ограничением, но в дополнение к нему рассматривается еще одно — алгоритм может порождать новые особи на основе лишь не более K уже имеющихся особей. Например, при K=1 алгоритм может использовать только оператор мутации, а при K=2 могут использоваться еще и операторы скрещивания. Ранее уже было понятно, что чем больше K, тем более быстрый алгоритм можно построить для решения задачи OneMax. Однако авторы доказывают, что существуют алгоритмы, делающие это за 2N/(K-1) шагов. Остается, казалось бы, немного — получить соответствующие нижние оценки, но над этой задачей исследователи бьются уже почти пятнадцать лет. Если задача будет решена, станет ясно, хватает ли обычных операторов скрещивания для эффективного решения задач эволюционными алгоритмами. Это интересно не только для эволюционных алгоритмов. Например, в эволюционной биологии еще не до конца решен вопрос, очень похожий на поставленный в этом исследовании: в каких случаях преимущество получают организмы, не имеющие полового размножения (что эквивалентно K=1), а в каких случаях половое размножение (K=2) более эффективно. Интересно было бы также понять, есть ли в биологии аналог случая K>2, содержащий в половом размножении более двух участников, и имеются ли при этом дополнительные преимущества.
К конференции было приурочено и онлайн-соревнование по решению задач оптимизации «Black Box Optimization Competition (BBComp)», в котором студент третьего курса кафедры компьютерных технологий Данил Шкарупин занял второе место. Данил участвовал в соревновании в рамках студенческой практики под руководством Владимира Мироновича.
