Что такое генетическое программирование

Генетическое программирование – это методика машинного обучения, прототипом которой является биологическая эволюция. В общем случае мы начинаем с большого набора программ (именуемых популяцией), сгенерированных случайным образом или написанных вручную, о которых известно, что это достаточно хорошие решения. Затем эти программы конкурируют между собой в попытке решить некоторую поставленную пользователем задачу. Это может быть игра, в которой программы соревнуются между собой напрямую, или специальный тест, призванный определить, какая программа лучше. По завершении состязания составляется ранжированный список программ – от наилучшей к наихудшей.

Затем – и вот тут-то вступает в дело эволюция – лучшие программы копируются и модифицируются одним из двух способов. Самый простой называется мутацией; в этом случае некоторые части программы случайным образом и очень незначительно изменяются в надежде, что от этого решение станет лучше. Другой способ называется скрещиванием (или кроссовером) – часть одной из отобранных программ перемещается в другую. В результате процедуры копирования и модификации создается много новых программ, которые основаны на наилучших особях предыдущей популяции, но не совпадают с ними. На каждом этапе качество программ вычисляется с помощью функции выживаемости (fitness function). Так как размер популяции не изменяется, программы, оказавшиеся плохими, удаляются из популяции, освобождая место для новых. Создается новая популяция, которая называется «следующим поколением», и весь процесс повторяется. Поскольку сохраняются и изменяются самые лучшие программы, то есть надежда, что с каждым поколением они будут совершенствоваться, как дети, которые могут превзойти своих родителей. Новые поколения создаются до тех пор, пока не будет выполнено условие завершения, которое в зависимости от задачи может формулироваться одним из следующих способов:

•          Найдено идеальное решение.

•          Найдено достаточно хорошее решение.

•          Решение не удается улучшить на протяжении нескольких поколений.

•          Количество поколений достигло заданного предела.

Рис. 11.1. Блок-схема генетического программирования

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

Блок-схема, изображенная на рис. 11.1, дает представление о процессе генетического программирования.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100