Человек - дитя природы, и от своего "родителя" он взял многое. Полет стрекозы, суперклей, застежки-липучки, множество алгоритмов - на последних хочется остановиться подробнее. Про муравьиный алгоритм я уже рассказывал, сегодня на очереди - генетический алгоритм. Применяется он в планировании ресурсов, в построении предсказательных моделей. А вдохновлен он, как видно из названия, самой эволюцией - конкретнее, работой генетического механизма.
Источник фото
Рассмотрим пример. Допустим, мы решаем задачу создания машинки, главная задача которой - уехать как можно дальше по сложному рельефу. Машинка наша состоит из колес и рамы. Причем все ее составляющие могут отличаться как в количественном, так и в качественном плане. Колес может быть сколь угодно и размер у них может отличаться. Задача алгоритма - подобрать такие параметры машины, чтобы они были оптимальными, т.е. могли уехать как можно дальше.
Как будет работать такой алгоритм? Сначала будет построена некая популяция из случайных машин - и все они будут проверены на успешность. Потом самые лучшие из них дадут потомство - и оценивать мы будем уже второе поколение. И так - практически до бесконечности:)
Рано или поздно такая система может "закостенеть": выродиться в одно стационарное состояние и перестать изменяться. В природе такой проблеме может противостоять механизм мутации - и это тоже внесем в наш алгоритм. Для этого пусть в каждое новое поколение машинок может вноситься случайный фактор, в результате чего один или несколько параметров меняются. Тогда получается, что потомства всегда будут отличаться от своих родителей. Случайный фактор не обязан улучшать наши автомобили, он может делать их хуже. Но такие модели будут менее удачливые - и эволюция их отбросит.
Другой вариант - скрещивание машинок, или кроссинговер. В этом случае часть одной машинки попадает в другую - по аналогии со смешиванием генов родителей в ребенке. Чаще всего применяют и кроссинговер, и мутацию - все как в реальном мире. В целом блок-схема работы генетического алгоритма выглядит довольно просто:
Когда же нам остановить процесс создания идеального автомобиля? Вариантов масса:
- когда нам удастся найти идеальное решение - автомобиль, движущийся в бесконечность;
- когда нам удастся найти достаточно хорошее, устраивающее нас решение - автомобиль проезжает необходимое для нас расстояние;
- когда количество поколений достигло заранее заданного предела;
- когда автомобили не изменяются на протяжении нескольких поколений.
А вот ссылка на занимательную игру, которая может продемонстрировать работу генетического алгоритма на практике: http://boxcar2d.com/index.html. Пример с машинками я почерпнул именно оттуда. На первом шаге тут генерируется 20 машинок, потом из них выбираются лучшие. Эти лучшие дают новое поколение - и так за несколько итераций получаются вполне приличные средства передвижения.
Примеры с http://boxcar2d.com/index.html:
1-е поколение
9-е поколение
Разница видна невооруженным глазом!
Тем, кому лень запускать flash-плейер, предлагаю посмотреть видео:
Создателем идеи генетических алгоритмов принято считать Джона Холланда, автора книги "Adaptation in Natural and Artifacial Systems", но у истоков стояли биологи, которые в 1950-х года моделировали процесс эволюции на компьютерах. А автором эволюции чаще всего принято считать природу:)
Генетические алгоритмы использутся в задачах оптимизации, которые сложно формализовать, но сравнительно просто оценить решение: хорошее оно или нет. Примеры таких задач:
- создание микросхем и антенных решеток;
- проектирование формы крыла самолета или концертного зала;
- распознавание символов;
- разработка игровых искусственных интелектов (для игры в шахматы или нарды).
Источник
Помните: выживает не сильнейший, выживает наиболее приспособленный. И чем больше человек знает и умеет - тем больше вероятность, что он будет жить, а не выживать:)
@vovochkin Поздравляю! Вы добились некоторого прогресса на Голосе и были награждены следующими новыми бейджами:
Награда за общую выплату получил
Вы можете нажать на любой бейдж, чтобы увидеть свою страницу на Доске Почета.
Чтобы увидеть больше информации о Доске Почета, нажмите здесь
Если вы больше не хотите получать уведомления, ответьте на этот комментарий словом
стоп
Ваш пост поддержали следующие Инвесторы Сообщества "Добрый кит":
ianboil, ukrainian, chiliec, archibald116, dikaniovs, brovaryleaks, vadbars, vasilisapor2, vict0r, ladyzarulem, svinsent, tnam0rken, karusel1, orezaku, yuriks2000, oksana0407, vika-teplo, kertar, nerengot, igrinov, all91, wedge, ksantoprotein
Поэтому я тоже проголосовал за него!
Узнать подробности о сообществе можно тут:
Разрешите представиться - Кит Добрый
Правила
Инструкция по внесению Инвестиционного взноса
Вы тоже можете стать Инвестором и поддержать проект!!!
Если Вы хотите отказаться от поддержки Доброго Кита, то ответьте на этот комментарий командой "!нехочу"
Больше таких статей! Очень познавательно. Поищу реализации алгоритма на пайтоне )) Заинтересовался
Уверен, что они есть. Но алгоритм простой, можно и самостоятельно реализовать. Главное - придумать наглядный пример. На Хабре, кажется, видел HelloWorld с помощью этого алгоритма:)
http://ninjaside.info/blog/ru/geneticheskie-algoritmy-hello-world/
@vovochkin Поздравляю! Вы добились некоторого прогресса на Голосе и были награждены следующими новыми бейджами:
Награда за количество голосов
Вы можете нажать на любой бейдж, чтобы увидеть свою страницу на Доске Почета.
Чтобы увидеть больше информации о Доске Почета, нажмите здесь
Если вы больше не хотите получать уведомления, ответьте на этот комментарий словом
стоп
@vovochkin Поздравляю! Вы добились некоторого прогресса на Голосе и были награждены следующими новыми бейджами:
Награда за Количество полученных комментариев
Вы можете нажать на любой бейдж, чтобы увидеть свою страницу на Доске Почета.
Чтобы увидеть больше информации о Доске Почета, нажмите здесь
Если вы больше не хотите получать уведомления, ответьте на этот комментарий словом
стоп
@vovochkin Поздравляю! Вы добились некоторого прогресса на Голосе и были награждены следующими новыми бейджами:
Награда за количество полученных голосов
Вы можете нажать на любой бейдж, чтобы увидеть свою страницу на Доске Почета.
Чтобы увидеть больше информации о Доске Почета, нажмите здесь
Если вы больше не хотите получать уведомления, ответьте на этот комментарий словом
стоп