Генетический алгоритм — это довольно новый инструмент в арсенале решения задач. Использовать метод стало возможным благодаря вычислительной технике. ЭВМ позволяет человеку невиданную ранее (ещё каких то 30 лет назад) роскошь — выполнять много бесполезных расчетов за короткое время. :)
По закону диалектики количество переходит в новое качество. Этим качеством является метод в решении задач оптимизации — генетические алгоритмы.
Причем тут генетика?
Стоит пояснить почему прилипло такое название, в чем смысл метафоры.
Природа использует алгоритм оптимизации миллиарды лет — мы называем его естественным отбором. Она не имеет каких либо планов развития, готовых формул, не имеет определенной цели что то создать. Все развивается по воле случая.
Миллиарды лет природа бросает игральные кости, генерирует варианты кода, самые эффективные из которых передаются в генах потомству.
Решает природа какие то уравнения? Нет. Есть ли какой то генеральный план? Нет. Восхищаемся ли мы тем, что в итоге получилось? — несомненно, да.
Осталось только повторить трюки природы (и запастись временем).
Давайте проводить параллели
В природе конкуренция идет между особями внутри популяции живых организмов. Кто лучше приспособлен — тот и выживает.
Инициализация: Вначале, нам нужно найти хоть какое то решение задачи. Одно или несколько решений сформируют начальный набор. Эти решения не оптимальны, они далеки от идеала, но обладают формальными признаками решения.
В терминах природы, каждое решение — это особь. Набор таких решений — популяция.
Пример: Для решения задачи о поиске кратчайшего пути из точки А к точке Б — нам нужно будет придумать вообще какие то пути из точки А к точке Б.
Когда возникли живые организмы, и появился механизм наследования, — возник феномен естественного отбора, оптимизации. Чем лучше подходит геном особи под требования окружающего мира, тем больше у ней шансов выжить, оставить потомство и вытеснить менее эффективных особей популяции.
Критерий отбора: Мы говорим о задаче оптимизации, значит у нас должен быть метод, позволяющий сравнить разные решения и позволяющий определить какое из них лучше.
Пример: Для отбора кратчайшего пути необходимо посчитать длины маршрутов и сравнить их.
Кто больше приспособлен для этой жизни?
Менее эффективные особи вымирают. Их численность сокращается, они «уступают» место победителям в борьбе за выживание. Так происходит, потому что популяция не может расти бесконечно, ресурсы и ареол обитания ограничены.
Отбор: Самые неудачные решения мы отбрасываем. Какую часть отбросить, а какую оставить — решать вам.
Пример: Мы можем отбрасывать какую то часть самых длинных маршрутов, а можем оставлять только один — самый лучший. Только практика покажет, какой подход верен в контексте вашей задачи.
Набор генов не постоянен, он передается от предков к потомкам с некоторыми изменениями. Если новый набор генов дает меньше преимуществ, то вероятность выбыть из конкурентной борьбы увеличивается, и наоборот.
Формирование новой популяции: Мы только что отбросили какую то долю слабых решений, теперь надо восстановить численность нашей популяции, размножить особей.
Откуда берется новый набор генов в природе? Особенно таких, которых не было у родителей? Для этого у природы в рукаве спрятана эдакая игральная кость — мутация. Есть и другие механизмы.
Механизмы изменения решений: Это наиболее трудная часть задачи. Нам нужно придумать какой то механизм (один или несколько), благодаря которому мы, меняя готовое решение, получаем другое решение, пополняя наш банк решений (популяцию) до прежней численности.
Важно, чтобы изменения потенциально могли привести к оптимальному решению задачи.
Пример: Таким механизмом для алгоритма поиска оптимального пути может быть смещение уже существующих точек маршрута, добавление/удаление точек, через которые проходит маршрут и т.п.
Этапы генетического алгоритма
Изучая «тактику» природы, мы выделили несколько важных этапов —
- Инициализация,
- Отбор, используя критерий отбора,
- Формирование новых решений, используя механизмы изменения.
2й и 3й этапы мы будем повторять многократно. Мы не узнаем — являются ли новые решения идеальными. Когда оставить процесс — решать вам.
Парадокс генетического алгоритма
Как видите, решения природы не являются идеальными. Но мы можем восхищаться ими, т.к. природа имела много времени, чтобы их отшлифовать.
Я начал с того, что заявил о появлении генетических алгоритмов, как результате явного прогресса вычислительной техники. Казалось бы есть все шансы не гадать (а генетический алгоритм именно этим и занимается), а посчитать.
Но каков бы ни был прогресс, существуют задачи, которые нельзя решить аналитически (составив формулу или решив какое то уравнение).
К примеру, классическая задача о Коммивояжере. При большом числе точек, перебор всех вариантов путей, чтобы найти тот единственный кратчайший, невозможен за адекватное время, используя современные ЭВМ.
Но если нам достаточно приближенного решения, то мы воспользуемся тактикой природы.
И вот вы, не зная как получить точное решение, позволяете компьютеру бросать кости, чтобы он случайно нашел какое то решение.
Основным ограничением является время, которое вы готовы ждать в поисках решения. Чем больше у вас времени — тем лучше решение вы найдете.
Особенности генетического алгоритма
Вот что мы выяснили:
- Генетический алгоритм не позволяет оценить насколько далеко вы от идеального решения;
- Основной ресурс — время;
- Задача решается приближено.
В следующей статье я попробую наглядно решить одну из простых задач, используя метод генетического алгоритма.