Мутация программ

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

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

Рис. 11.3. Мутация путем изменения функции в одном из узлов

 

Рис. 11.4. Мутация путем замены поддерева

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

Простоты ради мы реализуем только второй вид мутации. Создайте для выполнения этой операции функцию mutate:

def mutate(t,pc,probchange=0.1): if random( )<probchange:

return makerandomtree(pc) else:

result=deepcopy(t) if isinstance(t,node):

result.children=[mutate(c,pc,probchange) for c in t.children] return result

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

Несколько раз запустим функцию mutate для случайно сгенерированных программ и посмотрим, как она модифицирует деревья: >>> random2.display( )

subtract 7

multiply isgreater p0 p1 if

multiply p1 p1 p0 2

>>> muttree=gp.mutate(random2,2) >>> muttree.display( )

subtract 7

multiply isgreater p0 p1 if

multiply p1 p1

p0 p1

Посмотрим, существенно ли изменились результаты, возвращаемые функцией scorefunction после мутации, стали они лучше или хуже:

>>> gp.scorefunction(random2,hiddenset)

125489

>>> gp.scorefunction(muttree,hiddenset)

125479

Напомним, что мутации случайны, они необязательно должны вести к улучшению решения. Мы лишь надеемся, что в каких-то случаях результат станет лучше. Изменение будет продолжаться, и после смены нескольких поколений мы все-таки найдем наилучшее решение.

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