Поколение
Достигли цели
Самое быстрое прибытие
Наименьшее расстояние
  • В полёте
  • Достигли цели
  • Разбились
  • Лучший полёт прошлого поколения
  • Достигли цели
  • Разбились

Подробнее о генетических алгоритмах

Песочница генетического алгоритма

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

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

  1. Выберите препятствия или нарисуйте свои стены, проводя по полю, и задайте популяцию, частоту мутаций и время жизни.
  2. Нажмите «Запуск» и смотрите полёт каждого поколения; кнопка «Следующее поколение» пропускает остаток полёта.
  3. Следите в плитках и на графике за долей ракет, достигающих цели, и пробуйте другие частоты мутаций и способы отбора.

Как эволюционируют ракеты

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

Что меняют настройки

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

Часто задаваемые вопросы

Почему ракеты застревают за ступенчатыми стенами?

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

Так ли работает эволюция в природе?

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

Где применяются генетические алгоритмы?

В задачах с огромным пространством возможных ответов и простым способом оценить вариант: при подборе формы антенн, крыльев и деталей автомобилей, составлении расписаний, настройке параметров других алгоритмов, проектировании нейронных сетей, а также при создании произведений искусства и игровых стратегий. Известный пример — «эволюционная» антенна NASA на спутниках ST5 2006 года.

Почему лучшая ракета иногда летит хуже в следующем поколении?

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

Отправляется ли что-нибудь на сервер?

Нет. Ракеты летают и эволюционируют в вашем браузере, а нарисованные вами стены хранятся в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор