Теги: IT

14:35 17 июня 2020

текст

Арина Буздалова: «Эволюционные алгоритмы — хорошие поставщики новизны»

Представьте, что к вам едет курьер. Вы ждете его уже пять часов, а заветная точка геолокации на карте всё не двигается... Ускорить процесс доставки могут эволюционные алгоритмы. Мы продолжаем рубрику «Молодые ученые России», и новый гость проекта — Арина Буздалова, научный сотрудник факультета информационных технологий и программирования Университета ИТМО. Мы поговорили о том, какие проблемы решают эволюционные алгоритмы, как объединить науку и искусство и почему конференции важны для ученых.

2823 0 0

отправить по e-mail

Арина Буздалова: «Эволюционные алгоритмы — хорошие поставщики новизны»

— Расскажите, пожалуйста, нашим читателям простым языком, чем Вы занимаетесь?

— Я занимаюсь теоретическим изучением эволюционных алгоритмов и их разработкой. Что такое эволюционные алгоритмы? Грубо говоря, это некоторые инструкции для компьютера. Они называются эволюционными, потому что вдохновлены идеями из природы, из биологической эволюции. Представьте, что у нас есть популяция особей, например, животных, и они находятся в некой среде и борются за выживание. Им могут угрожать хищники или неблагоприятные условия среды. Выжившие особи рожают потомство и передают ему полезные генетические свойства, позитивные для выживания. В процессе размножения происходят мутации: дети не только перенимают свойства родителей, но и приобретают новые.

— То есть мы как будто взяли естественный отбор из теории эволюции, вложили его в машину и попросили воспроизвести?

— Именно! Мы как бы подумали: «А давайте будем устраивать эволюцию не на животных, а на тех объектах, которые мы хотим оптимизировать». Популяцией в данном случае будут, например, маршруты в логистике. Первую популяцию мы генерируем случайно. Мы можем в случайном порядке обойти необходимые точки, сгенерировать много маршрутов, будет популяция. Потом выбираются две особи и проводится скрещивание, как в биологии, то есть создается новый маршрут из двух родительских. И в следующем поколении, поскольку мы отбирали наиболее быстрые, приспособленность вырастает. Природа — гениальный изобретатель. Сколько форм существует, сколько необычных животных! Вот этим мы вдохновляемся и так пытаемся решать инженерные задачи.

— А как это работает на практике? В каких областях применяется?

— Мы рассматриваем эволюционные алгоритмы как инструмент решения задач оптимизации. Когда мы что-то оптимизируем, мы хотим максимизировать или минимизировать некоторую величину — например, нужно осуществить доставку: хочется посетить несколько точек и вернуться в исходную. Сделав это как можно быстрее, мы минимизируем время. Можем минимизировать также расстояние, например. Это пример из логистики. Если формулировать его, как я сказала: «посетить все точки и вернуться в исходную», получится так называемая задача коммивояжера, сформулированная еще в XIX веке. Эта задача была своеобразной подопытной мышью для теории оптимизации. Многие алгоритмы предлагались для ее решения, не только эволюционные. Особенность задачи в том, что решить ее точно, перебором всех маршрутов и выбором самого короткого — невозможно за разумное время. Если число точек приближается к ста, перебор всех маршрутов может потребовать миллиарды лет. С помощью эволюционных алгоритмов можно найти маршрут, близкий к оптимальному, достаточно быстро.

Решают они и задачи генеративного дизайна. В 90-ые NASA искало такую форму антенны для спутника в космосе, чтобы мощность сигнала была максимальной. После применения эволюционных алгоритмов получили странной формы антенну, абсолютно не типичную. Непонятно, почему такая форма, инженеры не могли получить такой стандартными методами, и — о чудо! — она заработала, как нужно.

Форма антенны, которая получилась у NASA после использования эволюционных алгоритмов

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

— А как применять в искусстве?

— А вот тут как раз очень сложно. Чтобы применить эволюционные алгоритмы, нужно оценить, насколько качественно текущее решение. То есть, можем ли мы что-то оптимизировать, ускорить, улучшить с конкретными цифрами. В инженерных задачах это легко. Мы просто измеряем время, измеряем расстояние, а в искусстве — очень сложно. Как измерить эстетическую ценность изображения или звука? Но и здесь мы можем кое-что сделать. Есть так называемая интерактивная эволюция, когда мы показываем человеку промежуточный результат, а человек уже оценивает, например, по шкале от 1 до 10, насколько ему картинка нравится. Можно интерактивным образом — от поколения к поколению — такие картинки строить. Нельзя сказать, что это сразу будет искусством, но это подход, который позволяет получить что-то новое. В эволюционные алгоритмы вшита неопределенность, случайность. Эти алгоритмы могут предложить такие решения, до которых человек не додумается.

— Насколько это новое направление в IT?

— Это история довольно давняя. Вообще сама идея еще в 1950-ом году была высказана Аланом Тьюрингом в его труде «Могут ли машины мыслить?». Это основополагающий труд для искусственного интеллекта. Тьюринг высказал идею, что роботы могут эволюционировать. Эволюционные алгоритмы помогут с помощью мутаций вырастить робота и обучить его, как ребенка. Хотя последнее относится к обучению с подкреплением. Так или иначе, идея присутствовала уже тогда. А на практике начали применять примерно в 60-ые годы. И, насколько мне известно, насколько я нашла в литературе, первоначально эволюционные алгоритмы использовались для решения инженерных задач. Например, для создания электрических схем. В этом — особенность области. Она изначально была не теоретической, а практической, очень прикладной. То есть, представьте, эволюционные алгоритмы успешно работают, применяются на практике, но до сих пор не всегда понятно, как они работают, как доказать, насколько они будут эффективны. Теории не хватает. Мы пытаемся в область, возникшую из инженерного направления, привнести математические основания.

— А есть конкуренты у эволюционных алгоритмов? Чем они принципиально отличаются?

— Задачу коммивояжера, о которой я уже упоминала, решать с помощью эволюционных алгоритмов не стоит, потому что есть специальный алгоритм Кернигана-Лина именно для этой задачи. Но на практике такая задача не встречается в чистом виде. Жизнь вносит свои коррективы. Утром один маршрут эффективен, а вечером — нет, там пробки. Или дорогу перекрыли, не проехать. Качество меняется прямо сейчас. В начале запуска качественными могут быть одни решения, а в конце — совсем другие. Особенность эволюционных алгоритмов в том, что это общий подход, универсальное решение, которое применимо и в изменяющихся условиях. Еще одна особенность — их способность создавать что-то принципиально новое. Как в примере с антенной NASA. В решениях эволюционные алгоритмы — хорошие поставщики новизны. В них содержится случайность.

— Вы задачи сами генерируете или вам их дают?

— По-разному. Если это фундаментальные исследования, мы можем сами выбирать задачи разной сложности, чтобы понять, как ведут себя эволюционные алгоритмы. Но есть у нас задачи от реальных инженеров. Мы, например, оптимизировали с помощью эволюционных алгоритмов расписание загрузки стержней в атомный реактор. Речь идет об атомной энергетике, к нам обратился коллега из Чехии, у него есть выход на такую практическую задачу, а у нас — хорошая теоретическая база. Тогда пригодились наши разработки в области многокритериальных эволюционных алгоритмов, где нужно удовлетворить нескольким ограничениям одновременно, например, оптимизировать и стоимость, и качество.

Научная группа на международной конференции по эволюционным вычислениям GECCO 2019, Прага. Арина Буздалова – справа. Фото: из личного архива

— Где обычные люди смогут пользоваться алгоритмами?

— Не исключено, что маршрут, которым к вам доставляют покупки уже сейчас, был продуман именно эволюционными алгоритмами. Я знаю, что некоторые логистические компании Петербурга точно используют эти алгоритмы. Когда мой коллега Максим Буздалов был на международной конференции по эволюционным алгоритмам в США, там было много людей из индустрий, где они применяются, но это почему-то не на слуху. О глубинном обучении, например, много пишут и говорят. Об инженерных задачах, наверное, не так интересно говорить, но они сильно влияют на нашу жизнь.

Арина Буздалова читает лекцию на Дне науки в ПФМЛ № 239. Фото: пресс-служба ПФМЛ № 239

— Как Вы пришли в науку и почему выбрали для себя IT?

— Я училась в Президентском физико-математическом лицее 239 (Санкт-Петербург). Я думаю, это повлияло на всю мою жизнь и судьбу. Мне было интересно заниматься информатикой, это ведь значит — создавать что-то новое, что будет работать потом без моего участия. В программировании ты пишешь программу, она работает, что-то создает. Я была вдохновлена кафедрой компьютерных технологий ИТМО, Владимир Глебович Парфенов приходил в лицей, рассказывал, как всё устроено. У меня было ощущение, что на кафедре интенсивно работают. У кафедры были достижения, и сейчас есть, неоспоримые. Мы 7 раз становились чемпионами мира по олимпиадному программированию. Я почувствовала атмосферу успеха. Хотя, конечно, хотела себя попробовать и в чем-то другом, мне очень хорошо давалась литература, я писала и до сих пор пишу стихи, мне нравится философия.

— Но потом появились эволюционные алгоритмы?

— Они просто были в учебной программе, нам нужно было выполнить курсовую работу. В ИТМО часто студенты старших курсов участвуют в обучении младших. Максим Буздалов учился на 6-ом курсе и давал работы 3-ему курсу. И я начала заниматься эволюционными алгоритмами. Показалось, что у них как будто есть какая-то своя жизнь. Анатолий Абрамович Шалыто (прим.ред.: профессор факультета информационных технологий и программирования), мой наставник, говорил на своих лекциях, что в большой компании человек растворяется, а в науке все-таки остается индивидуальностью. Мне захотелось попробовать, получится ли у меня.

— Не разочаровались?

— Наука привлекает меня своей объективностью. В искусстве, например, очень сложно понять, хорошо ты делаешь или нет, и если нет внутреннего стержня, уверенности, что картина, например, гениальна, то ты всегда будешь метаться. Оценка общества — тоже не показатель, оно может не понять. В искусстве — высокая степень неопределенности. В науке можно творить, придумывать новое, но всегда есть четкие критерии. Ты что-то доказал, да, ты мог ошибиться, но можно исправить неточность, и в конце концов будет результат. И он не зависит от чужого мнения и субъективных оценок. Если программа работает, она работает. Наука с человеческой точки зрения дает больше уверенности в своем пути. С другой стороны, в науке выражать свою индивидуальность сложнее. Это не цель науки. Цель — объективность. Конечно, внутренние качества влияют на профессиональный путь. Ты сам выбираешь, куда направить исследование, как его представить. Я мечтаю когда-нибудь совместить в своей деятельности науку и искусство. Сейчас очень активно развивается направление Science Art, в ИТМО есть даже магистратура.

— Так, а как можно объединить эти вещи?

— Приведу пример, который меня очень впечатлил. Существует интернет вещей, когда бытовые приборы связаны в сеть и по сети могут общаться. По этой же сети можно передавать текст на приборы. И был такой перформанс: художница сгенерировала с помощью ИИ текст, похожий на библейский, и передала на разные приборы. Представьте, у вас холодильник начинает говорить, еще и в таком стиле! Люди были в шоке. Не только науку можно использовать для искусства, но и искусство может быть источником задач для научных исследований. Я мечтаю с помощью эволюционных алгоритмов создать инструмент для музыкантов.

— Универсальный инструмент?

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

— Звучит потрясающе!

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

Арина Буздалова на конференции ITMO Open Science 2019. Фото: пресс-служба ИТМО

— Что бы Вы могли посоветовать молодым ученым?

— Пробовать и не отчаиваться. Не всегда получается сразу. Нужно прикладывать усилия. Нужно быть готовым к тому, что будет не получаться. Это нормально.

— Чем Вы гордитесь?

— Я горжусь тем путем, который прошла. Когда я начинала, всё было иначе. Помню, мы приехали на первую нашу конференцию. Зарубежные коллеги казались светилами, мы никого не знали, переживали. Прошло восемь лет, и в прошлом году мы поехали в совершенно другом качестве — уже как руководители. С нами было пятеро студентов и четверо аспирантов. И эти студенты были совсем, как мы тогда, но они были не одни. Мы знакомили их со старшими коллегами, помогали делать первые шаги. И это невероятное ощущение: когда-то ты сам был студентом, а сейчас ты открываешь новый мир для других студентов. Начинать в одиночку очень тяжело.

— А что поддерживает, если хочется бросить?

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

— Расскажете о самой запомнившейся?

— В Computer Science конференции важны, потому что быстро появляются новые результаты. Существуют и воркшопы, менее формальные события, когда обсуждают не готовый научный результат, а текущие исследования. И вот из таких мне, наверное, больше всего запомнился семинар в городе Дагштул, Германия. Физически это замок, невероятно вдохновляющее место, где собираются ученые из области Computer Science. Когда нас начали туда приглашать — а туда приглашают, нельзя просто податься на отбор, — это был мощный стимул для исследований. Ученые там живут, там же проходят семинары, обеды. На обедах участников рассаживают случайным образом. Приглашают как выдающихся ученых, так и молодых. Очень важный показатель — разнообразие участников на семинаре. Мы, кстати, там познакомились с коллегой из омского отделения Института математики им. С.Л. Соболева. В России не представилось случая познакомиться, а там — встретились.

В Дагштуле в самом замке есть комната с музыкальными инструментами и шахматами. Прощальный вечер обычно проходит там. Помню, как мы играли на гитаре вместе с коллегами из Италии, Англии, Германии. Днем обсуждаем науку, вечером — поем песни, играем. Это и есть межкультурное общение. У нас возникла идея гранта с Университетом Сорбонны как раз в Дагштуле. Этот обмен нужен всем нам, нужен человечеству.

Наш журнал ММ Поддержать ММ

Наука

Яна Титоренко

Машины и Механизмы