Генетический алгоритм

Большое кольцо автодрома «Сокол» — 4,3 километра асфальта с длинными прямыми и крутыми поворотами. Где на дороге ехать, чтобы пройти круг быстрее всего? Зажать поворот изнутри, сократив путь, или войти широко и сохранить скорость? Опишем траекторию 74 числами — насколько машина отклоняется от оси дороги через каждые 60 метров — и дадим эволюции 40 случайных траекторий. По оси дороги наша машина проходит круг за 100,4 секунды. Посмотрите, что сделают поколения.

Первые траектории виляют от бровки к бровке, и машина еле ползёт: каждый излом — это поворот, в котором надо тормозить. Через несколько десятков поколений лучшая линия разглаживается, а потом начинает проходить повороты по более широкой дуге, чем ось дороги: в отдельных поворотах видно и гоночное правило «снаружи — внутрь — наружу», когда машина перед поворотом уходит к внешнему краю, у вершины касается внутреннего и снова выходит наружу. Этого правила алгоритму никто не сообщал — он нашёл его, перебирая варианты. Приблизьте карту кнопками, чтобы рассмотреть повороты. Переключите метод на «без скрещивания», «отжиг» и «случайные» — внизу останутся кривые всех прогонов, и их можно сравнить на одном графике.

Идея

Держать не одно решение, а целую популяцию. Каждое оценивается числом — приспособленностью. Лучшие чаще становятся родителями; потомок собирается из кусков двух родителей — это скрещивание, — и в нём случайно меняется несколько генов — это мутация. Поколение за поколением хорошие куски решений распространяются и сочетаются друг с другом. Расчёт на то, что у задачи есть такие куски: удачный проход одного поворота от одного родителя и удачный проход другого — от другого.

Всё это слова из биологии, и сам алгоритм придуман по образцу естественного отбора. Но биология здесь — только метафора: «гены» — это числа, «особи» — варианты решения, а «естественным» отбор делает функция, которую пишет программист.

Как это работает

Кодировка. Поперёк дороги через каждые три точки осевой — примерно 60 метров — стоят «ворота», всего 74. Ген — положение машины в воротах: 21 вариант от −5 до +5 метров от оси с шагом полметра (дорога в модели 12 метров шириной, машина — около двух). Между воротами машина смещается равномерно. Особь — 74 гена, то есть вся траектория круга.

Приспособленность — время круга, и его нужно сделать поменьше. Для каждой точки линии радиус поворота R считается по ней и двум соседним, и скорость в ней не может превышать √(a·R) — иначе машину вынесет; a = 1,5 g. Потом два прохода по кругу: вперёд, где скорость растёт не быстрее, чем позволяет разгон 0,6 g, и назад, где она должна успеть упасть перед поворотом при торможении 1,5 g. Так же — прямым и обратным проходом — профиль скорости считают и настоящие системы беспилотных гоночных машин, например у Александра Хайльмайера и соавторов (2020). Модель грубая: в ней нет ни веса, ни шин, ни аэродинамики, — но повороты, разгон и торможение в ней настоящие.

Отбор. Родителя выбирают турниром: берут трёх случайных особей и оставляют самую быструю. Хорошие траектории чаще выигрывают турниры, но и плохие иногда становятся родителями, и популяция не сходится к одному решению слишком рано.

Скрещивание. Два случайных разреза делят круг на три куска; потомок берёт средний кусок у второго родителя, а остальное — у первого. На трассе это значит буквально: «проходи этот участок, как отец, а остальной круг — как мать». Делается с вероятностью 0,9, иначе потомок — копия первого родителя.

Мутация. Каждый ген с вероятностью 2/74 сдвигается на величину от −1,5 до +1,5 метра. В среднем меняются два гена из 74.

Поколение. Две лучшие траектории переходят в новое поколение без изменений — так лучший результат не теряется; остальные 38 мест занимают потомки. Каждый потомок — одна оценка времени круга, так что поколение стоит 38 оценок.

Честное сравнение

Эволюцию легко полюбить за красоту, поэтому её надо сравнивать с соперниками на одинаковых условиях: один и тот же круг, одна и та же модель машины и одинаковое число оценок времени круга — самой дорогой операции. Соперники: тот же алгоритм без скрещивания (только мутации и отбор), имитация отжига, которая сдвигает один ген и принимает ухудшения по правилу Метрополиса, и случайный перебор траекторий. Ниже медиана трёх прогонов: на сколько секунд лучший найденный круг медленнее 98 секунд.

Что видно на графике.

• Случайный перебор безнадёжен. Даже лучшая из 8000 случайных траекторий проходит круг за 104,4 секунды — на четыре секунды хуже, чем просто ехать по оси. Случайная траектория виляет, а 74 гена дают 21⁷⁴ вариантов: число из 98 цифр, и почти все они плохие.
• Скрещивание работает. После тысячи оценок алгоритм со скрещиванием отстаёт от 98 секунд на 2,3 секунды, а без скрещивания — на 4,9; после 8000 — на 0,28 и 0,57. Хорошо пройденные повороты появляются у разных траекторий, и скрещивание собирает их в одну, а одна мутация за другой должна находить их по очереди.
• Отжиг не хуже. На 500 и 1000 оценках генетический алгоритм впереди, на 2000, 4000 и 8000 — отжиг (0,21 секунды против 0,28 после 8000 оценок). Для этой задачи это честный итог: популяция не даёт выигрыша в числе оценок по сравнению с хорошим локальным поиском.

Зато у популяции есть преимущество, которого на этом графике не видно. Все 38 потомков поколения оцениваются независимо друг от друга, и если у вас 38 процессоров, поколение считается за время одной оценки: 8000 оценок — это 210 «тактов». Отжиг устроен как цепочка: следующий шаг нельзя сделать, не узнав результат предыдущего, и 8000 оценок — это 8000 тактов. Когда одна оценка — минутная симуляция, а не несколько микросекунд, как у нас, разница становится решающей. Именно так в 2017 году исследователи Uber AI обучали нейросети с четырьмя миллионами весов играть в игры Atari: простой генетический алгоритм учился одной игре примерно за час на 720 процессорных ядрах, а на одном настольном компьютере — за четыре часа. Скрещивания в их алгоритме, к слову, не было вовсе — «для простоты», как пишут авторы.

Что обещает теорема о схемах

Почему скрещивание вообще должно помогать? Джон Холланд, придумавший генетические алгоритмы в их классическом виде, ответил на это теоремой о схемах. Пусть особи — строки длины l из нулей и единиц. Схема — это шаблон, где часть позиций зафиксирована, а остальные помечены звёздочкой «что угодно»: схеме 1**0 подходят 1000, 1010, 1100 и 1110. У схемы H есть порядок o(H) — число фиксированных позиций — и длина δ(H) — расстояние между крайними фиксированными позициями: у 1**0 порядок 2 и длина 3. Обозначим через m(H, t) число строк поколения t, подходящих под схему, через f(H, t) — их среднюю приспособленность, а через f̄(t) — среднюю приспособленность всего поколения.

Читается теорема так: схема, которая лучше среднего (f(H) > f̄), короткая и низкого порядка, в среднем размножается — от поколения к поколению её становится больше. Холланд и потом Дэвид Голдберг в книге 1989 года вывели из этого «гипотезу строительных блоков»: генетический алгоритм находит короткие удачные схемы и собирает из них решение, как из кирпичей. На трассе это знакомо: «хорошо пройденный поворот» — и есть короткая схема из нескольких соседних генов.

Но обещает теорема гораздо меньше, чем кажется.

• Это неравенство для одного поколения и для математического ожидания. О том, что будет через десять поколений в популяции из сорока строк, где случайность велика, оно ничего не говорит.
• f(H, t) — средняя приспособленность строк схемы в текущем поколении, а не «настоящая» ценность схемы. Она меняется вместе с популяцией, и когда популяция сходится, f̄ догоняет её, и «экспоненциальный рост» хороших схем, о котором иногда пишут, останавливается.
• Теорема считает только разрушение схем и ничего не говорит о главном — как скрещивание соединяет хорошие схемы. Гипотеза строительных блоков не доказана.
• По теореме Вольперта и Макриди «о бесплатном обеде нет» (1997), в среднем по всем возможным задачам никакой алгоритм поиска не лучше любого другого, в том числе случайного. Если генетический алгоритм в чём-то хорош, то благодаря устройству конкретной задачи, а не сам по себе.

Самую наглядную проверку гипотезы устроили в 1992–1993 годах Мелани Митчелл, Стефани Форрест и сам Холланд. Они придумали функцию, которая будто создана для неё, — «королевскую дорогу»: строка из 64 битов разбита на восемь блоков по восемь, и за каждый блок из одних единиц дают 8 очков. Строительные блоки здесь в чистом виде. Ожидали, что генетический алгоритм обгонит восхождение на холм. Вышло наоборот.

В опыте Митчелл, Холланда и Форрест генетический алгоритм находил строку из одних единиц в среднем за 61 334 оценки, а простейшее восхождение — поменять случайный бит и оставить, если не стало хуже, — за 6179, почти вдесятеро быстрее. В нашем замере тридцать прогонов дают в среднем 32 175 оценок у генетического алгоритма и 7134 у восхождения.

Причину видно в сцене. Как только у какой-то строки складывается полный блок, она быстро размножается, и вместе с блоком по популяции расходятся её нули в остальных блоках — авторы назвали это «автостопом». Другие строки, у которых уже были почти собраны другие блоки, вытесняются, и популяция теряет разнообразие, ради которого её держали. Восхождение же собирает блоки по одному: однобитовая мутация, которая не портит собранное, принимается, и блок рано или поздно складывается. Авторы посчитали, что для N блоков по K битов восхождению нужно в среднем около 2^K·N·(ln N + γ) оценок, где γ ≈ 0,577 — постоянная Эйлера; для восьми блоков по восемь это примерно 5400.

Код

Программа читает осевую линию кольца из файла с данными, строит нормали, считает время круга и запускает эволюцию дважды: со скрещиванием и без. Арифметика с плавающей точкой одинакова в Python и Go до последнего бита — для этого в Go произведения обёрнуты в float64(…): иначе компилятор на процессорах ARM склеивает a*b + c в одну операцию с другим округлением, и эволюция уходит по другой дорожке.

Запуск короткий — по 40 поколений из 24 траекторий, — чтобы уложиться в песочницу сайта, но разница видна и тут: со скрещиванием траектория доходит до 100,35 секунды, без скрещивания — до 101,64. Буквы в последней строке — гены лучшей траектории: «a» — пять метров вправо от оси, «u» — пять влево, «k» — по оси.

Обратите внимание, как мало в программе собственно эволюции: турнир, разрез, сдвиг генов и сортировка ради двух лучших. Почти весь код и почти всё время работы — функция приспособленности. Так бывает почти всегда: генетический алгоритм пишется за полчаса, а модель, которую он оценивает, — неделями.

Сколько это стоит

Поколение из N особей длины l стоит N оценок приспособленности плюс O(N·l) на скрещивание и мутации и O(N log N) на сортировку ради лучших. Если оценка стоит c, то G поколений — O(G·N·c), и почти всегда c перевешивает всё остальное. У траектории c = O(l): два прохода по 221 точке. Памяти — O(N·l) на популяцию.

Гарантий времени нет, как и у отжига: генетический алгоритм не знает, нашёл ли он лучшее, и останавливают его по бюджету или когда лучший результат перестал меняться. А N оценок поколения независимы и делятся между процессорами без всякой переделки кода — это и есть главная сила метода.

Когда генетический алгоритм уместен

Наш опыт и опыт с «королевской дорогой» вместе дают трезвую картину. Генетический алгоритм — не волшебный универсальный оптимизатор, а разумный выбор при определённых условиях.

• Оценка — чёрный ящик. Приспособленность считается симуляцией, экспериментом, другой программой, и про её устройство ничего не известно: ни градиента, ни быстрого пересчёта после маленького изменения. Отжигу тогда тоже приходится оценивать всё заново, и его преимущество в простоте пропадает.
• Оценки можно считать параллельно. Поколение — это пачка независимых задач, а ядер и машин сегодня много.
• У решения есть независимые части, которые можно найти порознь и сложить, — как повороты трассы. Тогда скрещивание действительно экономит оценки: у нас вдвое.
• Нужен не один ответ, а набор. Популяция естественно хранит много разных хороших решений, а в многокритериальных задачах — когда важно и быстро, и дёшево — сразу всю границу компромиссов; так работает алгоритм NSGA-II Калянмоя Деба и соавторов (2002).

И когда не стоит. Если у задачи есть точный или специальный метод, берите его: траекторию гоночной машины на практике считают квадратичным программированием и оптимальным управлением, а не эволюцией. Если ход дешёвый и его цену легко пересчитать, начните с локального поиска или отжига. И всегда сравнивайте с простым соперником при равном числе оценок, как мы сделали выше: «королевская дорога» показывает, что даже задача, придуманная под генетический алгоритм, может оказаться проще для восхождения на холм.

Где работает

• Антенны. Для трёх спутников миссии NASA Space Technology 5 инженеры Джейсон Лон, Грегори Хорнби и Дерек Линден вырастили антенну эволюционным алгоритмом: она оказалась лучше антенны, спроектированной вручную подрядчиком, и 22 марта 2006 года улетела в космос — авторы называют её первым железом, придуманным компьютерной эволюцией, в космосе.
• Нейросети без градиента. «Глубокий ГА» Uber AI (2017) обучал сети с миллионами весов играть в Atari и местами обгонял обучение с подкреплением; эволюционные стратегии OpenAI того же года — родственный метод — тоже держались на массовом параллелизме.
• Многокритериальное проектирование: NSGA-II и его потомки выдают инженеру набор компромиссов между весом, прочностью и ценой, из которого выбирает уже человек.
• Подбор параметров симуляций, расписаний, других алгоритмов, где каждая оценка — запуск чего-то долгого.

История

Идея моделировать эволюцию на вычислительной машине появилась почти одновременно у нескольких групп в 1950–1960-е годы. В 1960-е Инго Рехенберг и Ханс-Пауль Швефель придумали эволюционные стратегии — чтобы подбирать форму тел в аэродинамической трубе, — а Лоуренс Фогель — эволюционное программирование конечных автоматов. Джон Холланд со студентами в те же годы изучал адаптивные системы и в 1975 году выпустил книгу «Adaptation in Natural and Artificial Systems», где описал генетический алгоритм с популяцией, скрещиванием и мутацией и доказал теорему о схемах. Широко метод разошёлся после книги его ученика Дэвида Голдберга «Genetic Algorithms in Search, Optimization, and Machine Learning» (1989).

Критика тоже пришла изнутри: опыты Митчелл, Форрест и Холланда с «королевской дорогой» в начале 1990-х показали, что гипотеза строительных блоков объясняет далеко не всё, а теорема Вольперта и Макриди (1997) напомнила, что универсально лучшего метода поиска не бывает.

Задачи

Первая — сердце нашего примера: время круга по траектории, двумя проходами по кольцу; один из тестов — настоящий «Сокол». Вторая — теорема о схемах в деле: оценить, сколько строк схемы окажется в следующем поколении.