Построение окружающей среды

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

Создайте новую функцию evolve, реализующую эту процедуру:

def evolve(pc,popsize,rankfunction,maxgen=500,

mutationrate=0.1,breedingrate=0.4,pexp=0.7,pnew=0.05):

#    Возвращает случайное число, отдавая предпочтение более маленьким числам

#    Чем меньше значение pexp, тем больше будет доля маленьких чисел def selectindex( ):

return int(log(random( ))/log(pexp))

#    Создаем случайную исходную популяцию population=[makerandomtree(pc) for i in range(popsize)] for i in range(maxgen):

scores=rankfunction(population) print scores[0][0] if scores[0][0]==0: break

#      Две наилучшие особи отбираются всегда newpop=[scores[0][1],scores[1][1]]

#       Строим следующее поколение while len(newpop)<popsize:

if random( )>pnew: newpop.append(mutate(

crossover(scores[selectindex( )][1], scores[selectindex( )][1], probswap=breedingrate), pc,probchange=mutationrate))

else:

# Добавляем случайный узел для внесения неопределенности newpop.append(makerandomtree(pc))

population=newpop scores[0][1].display( ) return scores[0][1]

Эта функция создает случайную исходную популяцию. Затем она выполняет не более maxgen итераций цикла, вызывая каждый раз функцию rankfunction для ранжирования программ от наилучшей до наихудшей. Наилучшая программа автоматически попадает в следующее поколение без изменения. Иногда эту стратегию называют элитизмом. Все остальные особи в следующем поколении конструируются путем случайного выбора программ, расположенных близко к началу списка,

и применения к ним операций мутации и скрещивания. Процесс повторяется, пока не будет получено идеальное совпадение (расхождение с известным результатом равно 0) или не исчерпаются все итерации. У функции есть несколько параметров, управляющих различными аспектами окружающей среды: rankfunction

Функция, применяемая для ранжирования списка программ от наилучшей к наихудшей.

mutationrate

Вероятность мутации, передаваемая функции mutate.

breedingrate

Вероятность скрещивания, передаваемая функции crossover.

popsize

Размер исходной популяции.

probexp

Скорость убывания вероятности выбора программ с низким рангом. Чем выше значение, тем более суров процесс естественного отбора, то есть производить потомство разрешается только программам с наивысшим рангом.

probnew

Вероятность включения в новую популяцию совершенно новой случайно сгенерированной программы. Смысл параметров p robexp и p robnew мы рассмотрим в разделе «Важность разнообразия».

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

def getrankfunction(dataset): def rankfunction(population):

scores=[(scorefunction(t,dataset),t) for t in population] scores.sort( ) return scores return rankfunction

Все готово для автоматического создания программы, которая будет искать математическую формулу, соответствующую набору данных. Сделаем это в интерактивном сеансе: >>> reload(gp)

>>> rf=gp.getrankfunction(gp.buildhiddenset( ))

>>> gp.evolve(2,500,rf,mutationrate=0.2,breedingrate=0.1,pexp=0.7,pnew=0.1)

16749 10674 5429 3090 491 151 151

0

add multiply p0 add

p0 add add p0 4

add p1

p1

isgreater 10 5

Числа изменяются медленно, но должны убывать, пока не достигнут 0. Интересно, что найденная функция правильна, но выглядит несколько сложнее той, с помощью которой набор был сгенерирован. (Вполне вероятно, что получившееся у вас решение тоже покажется сложнее, чем есть на самом деле.) Но с помощью простых алгебраических преобразований легко убедиться, что функции в действительности одинаковы – напомним, что p0 – это X, а p1 – Y. Получившееся дерево представляет следующую функцию: (X*(2+X))+X+4+Y+Y+(10>5) = 2*X+X*X+X+4+Y+Y+1 = X**2 + 3*X + 2*Y + 5

Мы продемонстрировали важную особенность генетического программирования: найденные решения могут быть правильными или очень хорошими, но из-за способа построения часто оказываются гораздо сложнее, чем то, что мог бы придумать человек. Нередко в программе обнаруживаются крупные участки, которые вообще не выполняют ничего полезного или вычисляют по сложной формуле одно и то же значение. Обратите внимание на узел (10>5) в построенной программе – это просто странный способ записи значения 1.

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

Важность разнообразия

Функция evolve среди прочего ранжирует программы от лучших к худшим, поэтому возникает искушение просто взять две-три программы, оказавшиеся в начале списка, и модифицировать их для включения в новую популяцию. В конце концов, зачем отказываться от лучшего? Но проблема в том, что, выбирая всякий раз два лучших решения, мы быстро приходим к чрезмерно однородной популяции (если хотите, назовите это вырождением). Все решения в ней достаточно хороши, но мало изменяются, так как операции скрещивания порождают практически то же, что было раньше. Таким образом, мы выходим на локальный максимум – хорошее, но не идеальное состояние, в котором малые изменения не приводят к улучшению результата.

Как выясняется, комбинирование самых лучших решений с большим количеством умеренно хороших дает более качественные результаты. Поэтому у функции evolve есть два дополнительных параметра, которые позволяют внести разнообразие в процесс селекции. Уменьшая значение probexp, вы позволяете более слабым решениям принять участие в формировании результата, так что процесс описывается уже не фразой «выживают сильнейшие», а фразой «выживают сильнейшие и самые удачливые». Увеличивая значение probnew, вы позволяете иногда включать совершенно новые программы. Оба параметра повышают степень разнообразия эволюционного процесса, но не вмешиваются в него чрезмерно, так как худшие программы в конечном итоге все равно «вымирают».

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