По пунктам:

 

  1. Я прочитал, что существуют эволюционные вычисления. Что это такое?
  2. Как все это работает?
  3. Эволюционные вычисления ведут люди или это сложные компьютерные алгоритмы?
  4. То есть Дарвин и теория эволюции тут ни при чем?
  5. А насколько мы можем быть уверены в ответе? Можно ли перепроверить?
  6. Почему?
  7. Где применяются эволюционные вычисления?
  8. Есть ли какие-то известные задачи, которые удалось решить таким образом?
  9. А еще?

Я прочитал, что существуют эволюционные вычисления. Что это такое?

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

 

Читать также: Ученые Университета ИТМО получили две награды престижной конференции по эволюционным вычислениям GECCO-2020

Как все это работает?

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

Эволюционные вычисления ведут люди или это сложные компьютерные алгоритмы?

Люди определяют то, как будет вычисляться приспособленность решений и как эти решения должны представляться в компьютере. Иногда разрабатываются специальные операторы мутации и скрещивания, учитывающие особенности решаемой задачи. Сам процесс поиска оптимального решения, как правило, выполняется без участия человека с помощью эволюционного алгоритма, реализованного в виде специальной компьютерной программы. Однако бывают случаи, когда автоматизировать вычисления очень сложно. Например, как численно определить эстетическую ценность сгенерированного изображения или мелодии? В подобных случаях может использоваться так называемая интерактивная эволюция: эволюционный алгоритм в ходе своей работы «просит» человека оценивать промежуточные решения. В других случаях для определения приспособленности может требоваться, например, проведение химического или физического эксперимента ― тогда эволюционный алгоритм будет «ждать», когда ученые получат необходимые данные.

 

Читать также: Ученые Университета ИТМО представили рекордное количество работ на конференции по эволюционным вычислениям GECCO-2019 в Праге

То есть Дарвин и теория эволюции тут ни при чем?

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

А насколько мы можем быть уверены в ответе? Можно ли перепроверить?

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

Почему?

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

 

Читать также: Ученые Университета ИТМО получили приз на GECCO-2017 в Берлине за новый генетический алгоритм

Где применяются эволюционные вычисления?

Сфера применения эволюционных вычислений очень обширна ― они полезны везде, где нужно что-нибудь оптимизировать, и используются как в индустрии, например, в промышленном дизайне, логистике и управлении, так и в других областях науки: в биоинформатике, медицине, робототехнике, машинном обучении (например, для генерации структуры нейронных сетей). Активным направлением в рамках эволюционных вычислений является так называемая поисковая инженерия программного обеспечения, в которой решаются вопросы автоматической генерации, изменения и тестирования программного кода. Также эволюционные вычисления могут применяться для создания объектов искусства и генерации уровней или персонажей в компьютерных играх.

Есть ли какие-то известные задачи, которые удалось решить таким образом?

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

А еще?

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