Генетический алгоритм: когда решение «выводят», а не пишут

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

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

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

Четыре кирпичика эволюции

Дарвиновская эволюция держится на нескольких простых принципах, и все они переносятся в код почти без изменений:

• Популяция. Множество разных вариантов решения существуют одновременно.
• Приспособленность. Каждый вариант оценивается: насколько он хорош для задачи.
• Отбор. Лучшие чаще дают «потомство», худшие отсеиваются.
• Мутации и скрещивание. Потомки немного отличаются от родителей и комбинируют их черты.

Как это выглядит на практике

Шаг 1. Случайный старт

Сначала создаётся популяция из множества случайных вариантов решения. На старте они почти наверняка ужасны — но это нормально, как первые слепые формы жизни.

Шаг 2. Оценка

Для каждого варианта считается приспособленность — число, говорящее, насколько он близок к цели. Это сердце алгоритма: нужно уметь сравнивать, кто «лучше».

Шаг 3. Размножение лучших

Самые приспособленные варианты отбирают и скрещивают — берут часть от одного «родителя», часть от другого, получая потомка. Так удачные находки комбинируются.

Шаг 4. Мутации

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

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

Шаг 5. Повтор

Новое поколение снова оценивают — и цикл повторяется сотни или тысячи раз. С каждым поколением средняя приспособленность растёт, и решения становятся всё лучше.

Где это правда работает

Генетические алгоритмы хороши там, где вариантов слишком много для перебора, а формулы нет: проектирование форм деталей, составление сложных расписаний, настройка параметров систем. Иногда они находят неожиданные, «нечеловеческие» решения — антенны странной формы или хитрые конструкции, до которых инженер не додумался бы.

Цена и границы

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