Файл: Интеллектуальные системы.pdf

95
Если все листовые узлы оказываются константами, то программа вообще не принимает параметров, поэтому результат её работы не за- висит от того, что Вы подадите на вход. С помощью функции, исполь- зованной ранее, можно распечатать случайно сгенерированные дере- вья.
8. Введите следующую строку: random1.display( ), а после выво- да результата на экран: random2.display( ).
У меня получилось два таких дерева: p0 и if p1 multiply add multiply
9 p1 p0 multiply p0 p1 add add multiply
6 p1 p0 p0
В этом задании программа построила два дерева, которые сгене- рировала случайным образом (исходя из заданных настроек).
Некоторые деревья оказываются довольно глубокими, поскольку каждая ветвь продолжает расти, пока не встретится узел без потомков.
Поэтому так важно ограничивать максимальную глубину, иначе рас- тущее дерево может переполнить стек.
Задание №4. Проверка решения
В данном задании будут рассмотрены способы проверки пра- вильности получаемых решений.

96
Простой математический тест
Один из самых простых тестов, применяемых в генетическом программировании, – реконструкция простой математической функ- ции. Предположим, что задана таблица входных и выходных данных.
Табл.14
X
Y
Результат
26 35 829 8
24 141 20 1
467 33 11 1215 37 16 1517
Существует некая функция, отображающая заданные пары (X, Y) на результаты, но что это за функция, - неизвестно. Статистик мог бы попытаться применить к этой задаче регрессионный анализ, но для этого нужно знать структуру формулы. Другой вариант – построить прогностическую модель с помощью метода k-ближайших соседей, но для этого требуется хранить все данные. В некоторых случаях нужна лишь формула, быть может, для встраивания в другую, гораздо более простую программу или чтобы объяснить человеку, что происходит.
Для генерации этих данных использовалась следующая функция:
5 3
2 2



x
y
x
. В файле gp.py эта функция представлена в сле- дующем виде: def hiddenfunction(x,y): return x**2+2*y+3*x+5
Воспользуемся этой функцией для построения набора данных, на котором будем проверять сгенерированные программы. Функция для создания набора данных buildhiddenset: def buildhiddenset( ): rows=[]

97 for i in range(200): x=randint(0,40) y=randint(0,40) rows.append([x,y,hiddenfunction(x,y)]) return rows
Измерение успеха
Необходимо научиться измерять качество найденного решения. В данном случае мы сравниваем результаты работы программы с извест- ными числами, поэтому для проверки нужно посмотреть, насколько мало оказалось расхождение. 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 говорит о том, что все результаты в точности совпали. Проверим, насколько хороши оказались сгенериро- ванные ранее программы. Проделайте:
>>> import gp
>>> hiddenset=gp.buildhiddenset()
>>> random1=gp.makerandomtree(2)
>>> random2=gp.makerandomtree(2)
>>> gp.scorefunction(random2,hiddenset)
117926
>>> gp.scorefunction(random1,hiddenset
115744
Поскольку мы сгенерировали лишь две программы, причём со- вершено случайные, шансы на отыскание правильной функции ни- чтожно малы. Однако теперь у нас есть способ проверить, насколько хорошо программа даёт прогноз математической функции.

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

99 относительно малую вероятность того, что какой-либо узел будет из- менён.
Далее вы начинаете обход дерева от корня, и если случайно вы- бранное число оказалось меньше пороговой вероятности, то узел му- тирует одним из описанных выше способов. В противном случае про- веряются дочерние узлы.
Ради простоты, в данной работе будет рассмотрен только второй способ.
Рис. 35
Функция mutate начинает с корня дерева и решает, следует ли из- менить узел. def mutate(t,pc,probchange=0.1): if random( )
return makerandomtree(pc) else: result=deepcopy(t)

100 if isinstance(t,node): result.children=[mutate(c,pc,probchange) for c in t.children] return result
Если нет, она рекурсивно вызывает mutate для дочерних узлов.
Может случиться, что мутации подвергнутся все узлы, а иногда дерево вообще не изменится.
Запустите несколько раз функцию mutate для случайно сгенери- рованных программ и посмотрите, как она модифицирует деревья: import gp random1=gp.makerandomtree(2) random1.display( )
Будет выведено дерево muttree=gp.mutate(random1,2) muttree.display( )
Будет выведено изменённое дерево gp.scorefunction(random1,hiddenset)
105357 – результат gp.scorefunction(muttree,hiddenset)
105688 – изменённый результат
Напомним, что мутации случайны, они необязательно должны ве- сти к улучшению решения. Мы лишь надеемся, что в каких-то случаях результат станет лучше. Изменение будет продолжаться, и после сме- ны нескольких поколений мы все-таки найдём (если повезёт) наилуч- шее решение.
Скрещивание
Другой вид модификации программ – это скрещивание. Для этого две успешные программы комбинируются с целью получения новой.
Обычно это делается путём замены какой-то ветви одной программы ветвью другой. На рис. 36 приведён соответствующий пример

101
Рис. 36
Функции, выполняющей скрещивание, передаются два дерева, и она обходит оба. Если случайно выбранное число не превышает поро- говой вероятности, то функция возвращает копию первого дерева, в которой одна из ветвей заменена какой-то ветвью, взятой из второго дерева. Поскольку обход выполняется параллельно, то скрещивание произойдёт примерно на одном уровне каждого дерева.
Это реализуется функцией crossover: def crossover(t1,t2,probswap=0.7,top=1): if random( )
return deepcopy(t2) else: result=deepcopy(t1)

102 if isinstance(t1,node) and isinstance(t2,node): result.children=[crossover(c,choice(t2.children),probswap,0) for c in t1.children] return result
Попробуйте применить эту функцию: random1=gp.makerandomtree(2) random1.display( )
На экране будет отображено дерево
random2=gp.makerandomtree(2) random2.display( )
На экране будет отображено дерево
cross=gp.crossover(random1,random2) cross.display( )
На экране будет отображено дерево, полученное в результате скре-
щивания
Вероятно, вы заметили, что перестановка ветвей может радикаль- но изменить поведение программы. Кроме того, результат работы каждой программы может оказаться близок к правильному по совер- шенно различным причинам, поэтому скрещенная программа может давать результаты, совершенно не похожие ни на одного из родителей.
Как и раньше, мы надеемся, что в результате некоторых скрещиваний решение удастся улучшить, и оно перейдёт в следующее поколение.
Задание №5. Построение окружающей среды
Вооружившись средством для измерения успеха и двумя метода- ми модификации наилучших программ, мы можем перейти к созданию конкурентной среды, в которой программы будут эволюционировать.
Необходимые шаги представлены блок-схемой на рис. 37. Смысл в том, чтобы создать набор случайных программ, отобрать из них наилучшие для копирования и модификации и повторять процесс, пока не будет выполнено некое условие останова.
Функция evolve реализует эту процедуру:

103 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)
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]

104
Рис. 37
Эта функция создаёт случайную исходную популяцию. Затем она выполняет не более maxgen итераций цикла, вызывая каждый раз функцию rankfunctionдля ранжирования программ от наилучшей до наихудшей. Наилучшая программа автоматически попадает в следую- щее поколение без изменения. Иногда эту стратегию называют эли- тизмом. Все остальные особи в следующем поколении конструируют- ся путём случайного выбора программ, расположенных близко к нача- лу списка, и применения к ним операций мутации и скрещивания.
Процесс повторяется, пока не будет получено идеальное совпадение
(расхождение с известным результатом равно 0) или не исчерпаются все итерации.
У функции есть несколько параметров, управляющих различными аспектами окружающей среды: rankfunction - функция, применяемая для ранжирования списка программ от наилучшей к наихудшей. mutationrate - вероятность мутации, передаваемая функции mutate.

105 breedingrate - вероятность скрещивания, передаваемая функции crossover. popsize - размер исходной популяции. probexp - скорость убывания вероятности выбора программ с низ- ким рангом; чем выше значение, тем более суров процесс естественно- го отбора, то есть производить потомство разрешается только про- граммам с наивысшим рангом. probnew - вероятность включения в новую популяцию совершен- но новой случайно сгенерированной программы. Смысл параметров probexp и probnew будет пояснён далее.
Функция getrankfunction возвращает функцию ранжирования для имеющегося набора данных: def getrankfunction(dataset): def rankfunction(population): scores=[(scorefunction(t,dataset),t) for t in population] scores.sort( ) return scores return rankfunction
Итак, переходим к автоматическому созданию программы, кото- рая будет искать математическую формулу, соответствующую набору данных: import gp rf=gp.getrankfunction(gp.buildhiddenset( )) gp.evolve(2,500,rf,mutationrate=0.2,breedingrate=0.1,pexp=0.7,pnew=0.1)
У меня получилось следующее:
18680 8048 4018 3615 2666 2478 2478 2438 2438 2420 2420

106 2340 2340 2215 2002 2002 2002 1309 1309 1309 1264 1264 1190 1190 1190 1190 400 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 0 subtract multiply p0 add p0 6 subtract p0 subtract

107 subtract add add
6 if multiply p0 0 isgreater multiply multiply p1 p0 1 multiply add
5 5 add p0 p1 subtract if add
3 4
8 isgreater p0 7 p0 if
2 p1 add add if multiply isgreater p1 p1

108 if
9 4 p1 p0 isgreater p0 p0 10 4 subtract
9 p1 p0
Числа изменяются медленно, но должны убывать, пока не до- стигнут 0. Интересно, что найденная функция правильна, но выглядит сложнее той, с помощью которой набор был сгенерирован (p0 – это Х, p1 – Y).
В этом задании продемонстрирована важная особенность генети- ческого программирования: найденные решения могут быть правиль- ными или очень хорошими, но из-за способа построения часто оказы- ваются гораздо сложнее, чем то, что мог бы придумать человек. Не- редко в программе обнаруживаются крупные участки, которые вообще не выполняют ничего полезного или вычисляют по сложной формуле одно и то же значение.
Можно заставить алгоритм строить простые программы, но во многих случаях это лишь затруднит поиск хорошего решения. Гораздо лучше позволить программам свободно эволюционировать, а потом упростить найденное хорошее решение, исключив лишние участки дерева. Иногда это можно сделать вручную, а иногда – автоматически с помощью алгоритма отсечения ветвей.
Важность разнообразия
Функция evolve среди прочего ранжирует программы от лучших к худшим, поэтому возникает искушение просто взять две-три програм- мы, оказавшиеся в начале списка, и модифицировать их для включе- ния в новую популяцию. В конце концов, зачем отказываться от луч- шего?

109
Но проблема в том, что, выбирая всякий раз два лучших решения, мы быстро приходим к чрезмерно однородной популяции (если хоти- те, назовите это вырождением). Все решения в ней достаточно хоро- ши, но мало изменяются, так как операции скрещивания порождают практически то же, что было раньше. Таким образом, мы выходим на локальный максимум – хорошее, но не идеальное состояние, в котором малые изменения не приводят к улучшению результата.
Как выясняется, комбинирование самых лучших решений с большим количеством умеренно хороших даёт более качественные результаты. Поэтому у функции evolve есть два дополнительных пара- метра, которые позволяют внести разнообразие в процесс селекции.
Уменьшая значение probexp, вы позволяете более слабым решениям принять участие в формировании результата, так что процесс описы- вается уже не фразой «выживают сильнейшие», а фразой «выживают сильнейшие и самые удачливые». Увеличивая значение probnew, вы позволяете иногда включать совершенно новые программы. Оба пара- метра повышают степень разнообразия эволюционного процесса, но не вмешиваются в него чрезмерно, так как худшие программы в конеч- ном итоге всё равно «вымирают».
Задание №5. Простая игра
Более интересной задачей для генетического программирования является создание искусственного интеллекта для игры. Программы можно заставить эволюционировать, принудив их состязаться между собой или с людьми, причём победителям предоставляются более вы- сокие шансы перейти в следующее поколение. В этом задании вы по- знакомитесь с симулятором для очень простой игры «Погоня» (см. рис).
Два игрока по очереди делают ходы на небольшой расчерченной на клеточки доске. Можно перейти на любую из четырёх соседних клеток, но размеры доски ограничены, поэтому игрок, пытающийся выйти за её пределы, пропускает ход. Цель игры – взять соперника в плен, перейдя в свой ход на ту же клетку, где он сейчас стоит. Налага- ется лишь одно ограничение – нельзя два раза подряд ходить в одном и том же направлении, иначе будет засчитано поражение. Игра очень простая, но, поскольку в ней сталкиваются интересы двух участников, на её примере можно изучить конкурентные аспекты эволюции.

110
Рис. 38
Функция gridgame имитирует игру двух участников. Она попере- менно передаёт каждой программе текущее положение ходящего иг- рока и его противника, а также последний сделанный ходящим игро- ком ход и возвращает в качестве результата новый ход.
Ход представляется числом от 0 до 3, обозначающим одно из че- тырёх возможных направлений. Но так как случайные программы мо- гут вернуть любое целое число, функция должна как-то привести ре- зультат к допустимому диапазону. Для этого она возвращает остаток от деления полученного числа на 4. Случайная программа может так- же создать игрока, который будет ходить по кругу, поэтому число хо- дов ограничивается – после 50 ходов объявляется ничья. def gridgame(p):
# Размер доски max=(3,3)
# Запоминаем последний ход каждого игрока lastmove=[-1,-1]
# Запоминаем положения игроков location=[[randint(0,max[0]),randint(0,max[1])]]
# Располагаем второго игрока на достаточном удалении от первого location.append([(location[0][0]+2)%4,(location[0][1]+2)%4])
# Не более 50 ходов до объявления ничьей for o in range(50):
# Для каждого игрока for i in range(2): locs=location[i][:]+location[1-i][:] locs.append(lastmove[i]) move=p[i].evaluate(locs)%4
# Если игрок два раза подряд ходит в одном направлении, ему
# засчитывается проигрыш if lastmove[i]==move: return 1-i