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

Человек - дитя природы, и от своего "родителя" он взял многое. Полет стрекозы, суперклей, застежки-липучки, множество алгоритмов - на последних хочется остановиться подробнее. Про муравьиный алгоритм я уже рассказывал, сегодня на очереди - генетический алгоритм. Применяется он в планировании ресурсов, в построении предсказательных моделей. А вдохновлен он, как видно из названия, самой эволюцией - конкретнее, работой генетического механизма.

Источник фото

Рассмотрим пример. Допустим, мы решаем задачу создания машинки, главная задача которой - уехать как можно дальше по сложному рельефу. Машинка наша состоит из колес и рамы. Причем все ее составляющие могут отличаться как в количественном, так и в качественном плане. Колес может быть сколь угодно и размер у них может отличаться. Задача алгоритма - подобрать такие параметры машины, чтобы они были оптимальными, т.е. могли уехать как можно дальше.

Как будет работать такой алгоритм? Сначала будет построена некая популяция из случайных машин - и все они будут проверены на успешность. Потом самые лучшие из них дадут потомство - и оценивать мы будем уже второе поколение. И так - практически до бесконечности:)

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

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

Когда же нам остановить процесс создания идеального автомобиля? Вариантов масса:

• когда нам удастся найти идеальное решение - автомобиль, движущийся в бесконечность;
• когда нам удастся найти достаточно хорошее, устраивающее нас решение - автомобиль проезжает необходимое для нас расстояние;
• когда количество поколений достигло заранее заданного предела;
• когда автомобили не изменяются на протяжении нескольких поколений.

А вот ссылка на занимательную игру, которая может продемонстрировать работу генетического алгоритма на практике: http://boxcar2d.com/index.html. Пример с машинками я почерпнул именно оттуда. На первом шаге тут генерируется 20 машинок, потом из них выбираются лучшие. Эти лучшие дают новое поколение - и так за несколько итераций получаются вполне приличные средства передвижения.

Примеры с http://boxcar2d.com/index.html:

1-е поколение

9-е поколение

Разница видна невооруженным глазом!
Тем, кому лень запускать flash-плейер, предлагаю посмотреть видео:

Создателем идеи генетических алгоритмов принято считать Джона Холланда, автора книги "Adaptation in Natural and Artifacial Systems", но у истоков стояли биологи, которые в 1950-х года моделировали процесс эволюции на компьютерах. А автором эволюции чаще всего принято считать природу:)

Генетические алгоритмы использутся в задачах оптимизации, которые сложно формализовать, но сравнительно просто оценить решение: хорошее оно или нет. Примеры таких задач:

• создание микросхем и антенных решеток;
• проектирование формы крыла самолета или концертного зала;
• распознавание символов;
• разработка игровых искусственных интелектов (для игры в шахматы или нарды).

Источник

Помните: выживает не сильнейший, выживает наиболее приспособленный. И чем больше человек знает и умеет - тем больше вероятность, что он будет жить, а не выживать:)