Эволюционные алгоритмы

Что это такое и для чего они нужны

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

Арина Буздалова, научный сотрудник лаборатории «Компьютерные технологии» Университета ИТМО:

— Как развивается жизнь на Земле? На этот вопрос отвечают эволюционные теории. И на основе эволюционных теорий были разработаны эволюционные алгоритмы. Они в своей основе содержат простые идеи из данных теорий. Я приведу пример: опишем форму антенны с помощью каких-то моделей, и набор возможных форм — пусть сначала неэффективных, пусть сгенерированных случайным образом — будем называть «популяцией» (по аналогии с эволюцией в природе). А каждую конкретную форму назовем «особью». Особям можно сопоставлять приспособленность. В нашем примере с антенной — это то, насколько хорошо антенна передает сигнал. Но в принципе эволюционные алгоритмы хороши тем, что применимы для любой задачи оптимизации.

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

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

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

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

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

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

В том числе эволюционные алгоритмы реально применяются для решения этих задач, а мы разрабатываем способы улучшения данных алгоритмов (способы управления ими). Один из подходов, например, управление эволюционным алгоритмом с помощью обучения с подкреплением. Обучение с подкреплением может подбирать параметры, с которыми эволюционный алгоритм работает лучше. Составление расписания нужно не только для логистики. Например, у нас есть проект, в котором строится расписание загрузки топливных стержней для атомного реактора. Применение в энергетике! Или в биоинформатике применяли эволюционные алгоритмы на моделях белков, чтобы предсказать переходы между конформациями белков (т.е. предсказать, каким образом будет меняться форма белка). Это важная задача, которая может реализоваться при разработке новых лекарств. Также с помощью эволюционных алгоритмов мы генерировали тесты для оценки эффективности программ. Можно сгенерировать сложный тест, по которому программа будет работать долго, и таким образом выявить плохие программы. Мы облегчаем работу тестировщиков — делаем ее более эффективной.

Источник: www.instagram.com

Комментарии: