Создание начальной популяции

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

Для построения случайной программы нужно создать узел, поместив него случайно выбранную функцию, а затем – необходимое количество дочерних узлов, каждый из которых может иметь свои дочерние узлы и т. д. Как обычно при работе с деревьями, проще всего сделать это рекурсивно. Добавьте в файл gp.py функцию makerandomtree: def makerandomtree(pc,maxdepth=4,fpr=0.5,ppr=0.6): if random( )<fpr and maxdepth>0: f=choice(flist)

children=[makerandomtree(pc,maxdepth-1,fpr,ppr)

for i in range(f.childcount)] return node(f,children) elif random( )<ppr:

return paramnode(randint(0,pc-1)) else:

return constnode(randint(0,10)) Эта функция создает узел, содержащий случайно выбранную функцию, и проверяет, сколько у этой функции должно быть параметров. Для каждого дочернего узла функция вызывает себя рекурсивно, чтобы создать новый узел. Так конструируется все дерево, причем процесс построения ветвей завершается в тот момент, когда у очередного узла нет дочерних (то есть он представляет либо константу, либо переменную-параметр). Параметр pc, который будет встречаться на протяжении всей этой статьи, равен числу параметров, принимаемых деревом на входе. Параметр fpr задает вероятность того, что вновь создаваемый узел будет соответствовать функции, а ppr – вероятность того, что узел, не являющийся функцией, будет иметь тип paramnode. В сеансе интерпретатора постройте с помощью этой функции несколько программ и посмотрите, какие результаты будут получаться при различных параметрах:

>>> random1=gp.makerandomtree(2) >>> random1.evaluate([7,1]) 7

>>> random1.evaluate([2,4])

2

>>> random2=gp.makerandomtree(2) >>> random2.evaluate([5,3])

1

>>> random2.evaluate([5,20])

0

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

>>> random1.display( )

p0

>>> random2.display( )

subtract 7

multiply isgreater p0 p1 if

multiply p1 p1 p0

Выяснится, что некоторые деревья оказываются довольно глубокими, поскольку каждая ветвь продолжает расти, пока не встретится узел без потомков. Поэтому так важно ограничивать максимальную глубину, иначе растущее дерево может переполнить стек.

Проверка решения

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

Простой математический тест

Один из самых простых тестов, применяемых в генетическом программировании, – реконструкция простой математической функции. Предположим, что задана таблица входных и выходных данных (табл. 11.1).

Таблица 11.1. Входные и выходные данные неизвестной функции

Существует некая функция, отображающая заданные пары (X,Y) на результаты, но что это за функция, вам не сказали. Статистик мог бы попытаться применить к этой задаче регрессионный анализ, но для этого нужно знать структуру формулы. Другой вариант – построить прогностическую модель с помощью метода fe-ближайших соседей, описанного в ранее, но для этого требуется хранить все данные. В некоторых случаях нужна лишь формула, быть может, для встраивания в другую, гораздо более простую программу или чтобы объяснить человеку, что происходит.

Уверен, вы горите желанием узнать, какая функция скрыта за этими данными. Я вам скажу. Добавьте ее в файл gp.py:

def hiddenfunction(x,y): return x**2+2*y+3*x+5

Мы воспользуемся этой функцией для построения набора данных, на котором будем проверять сгенерированные программы. Добавьте функцию buildhiddenset для создания набора данных:

def buildhiddenset( ): rows=[]

for i in range(200): x=randint(0,40) y=randint(0,40)

rows.append([x,y,hiddenfunction(x,y)]) return rows

И вызовите ее в интерактивном сеансе:

>>> reload(gp)

<module ‘gp’ from ‘gp.py’>

>>> hiddenset=gp.buildhiddenset( )

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

Измерение успеха

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

def scorefunction(tree,s): dif=0

for data in s: v=tree.evaluate([data[0],data[1]]) dif+=abs(v-data[2]) return dif

Эта функция перебирает все строки набора данных, вычисляет функцию от указанных в ней аргументов и сравнивает с результатом. Абсолютные значения разностей суммируются. Чем меньше сумма, тем лучше программа, а значение 0 говорит о том, что все результаты в точности совпали. Проверим, насколько хороши оказались сгенерированные ранее программы:

>>> reload(gp)

<module ‘gp’ from ‘gp.py’>

>>> gp.scorefunction(random2,hiddenset)

137646

>>> gp.scorefunction(random1,hiddenset)

125489

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

Вы можете следить за любыми ответами на эту запись через 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