Лабораторные по МИСПИТ. ЛР. Интеллектуальные системы
 Скачать 1.43 Mb.
|
|
1. Как работает алгоритм коллаборативной фильтрации? 2. Как вычислить оценку подобия при помощи евклидова рас- стояния? 3. Как вычислить оценку подобия при помощи коэффициента корреляции Пирсона? 4. Поясните, как выполняется ранжирование критиков? 5. Поясните, как выполняется рекомендование предметов? Список литературы 2. Тоби Сегаран. Программируем коллективный разум. 3. Марк Лутц. Изучаем Python. 88 Лабораторная работа №10. Генетическое программирование Введение Генетическое программирование – это методика машинного обу- чения, прототипом которой является биологическая эволюция. В об- щем случае, мы начинаем с большого набора программ (популяция), сгенерированных случайным образом или написанных вручную, о ко- торых известно, что это достаточно хорошие решения. Затем эти про- граммы конкурируют между собой в попытке решить некоторую по- ставленную пользователем задачу. Это может быть игра, в которой программы соревнуются между собой напрямую, или специальный тест, призванный определить, какая программа лучше. По завершении состязания составляется ранжированный список программ – от наилучшей к наихудшей. Затем – здесь в дело вступает эволюция – лучшие программы ко- пируются и модифицируются одним из двух способов. Самый простой называется мутацией. В этом случае некоторые части программы слу- чайным образом и очень незначительно изменяются в надежде, что от этого решение станет лучше. Другой способ называется скрещиванием (или кроссовером) – часть одной из отобранных программ перемеща- ется в другую. В результате процедуры копирования и модификации создаётся много новых программ, которые основаны на наилучших особях предыдущей популяции, но не совпадают с ними. На каждом этапе качество программ вычисляется с помощью функции выживаемости (fitness function). Так как размер популяции не изменяется, программы, оказавшиеся плохими, удаляются из популя- ции, освобождая место для новых. Создаётся новая популяция, которая называется «следующим поколением», и весь процесс повторяется. Поскольку сохраняются и изменяются самые лучшие программы, то есть надежда, что с каждым поколением они будут совершенствовать- ся, как дети, которые могут превзойти своих родителей. Новые поколения создаются до тех пор, пока не будет выполнено условие завершения, которое в зависимости от задачи может форму- лироваться одним из следующих способов: Найдено идеальное решение. Найдено достаточно хорошее решение. Решение не удаётся улучшить на протяжении нескольких по- колений. Количество поколений достигло заданного предела. 89 Для некоторых задач, например, определения математической функции, отображающей один набор значений на другой, можно найти идеальное решение. Для других, например, когда речь идёт о настоль- ной игре, найденное решение может быть не идеальным, поскольку его качество зависит от стратегии противника. Генетический алгоритм – это метод оптимизации, в основе ко- торого лежит идея естественного отбора как средства достижения наилучшего результата. При любом способе оптимизации изначально имеется некоторая метрика или алгоритм, и мы просто пытаемся подо- брать для него наилучшие параметры. Как и в случае оптимизации, для генетического программирова- ния необходим способ измерения качества решения. Но, в отличие от оптимизации, решением является не просто набор параметров задан- ного алгоритма. Путём естественного отбора автоматически проекти- руется сам алгоритм со всеми своими параметрами. Для создания программ, которые можно тестировать, подвер- гать мутации и скрещиванию, необходимо как-то представлять их в виде кода на языке Python и запускать. Представление должно допус- кать простую модификацию и, что более существенно, быть настоя- щей исполняемой программой. Поэтому просто генерировать случай- ные строки и пытаться трактовать их как Python-программу не полу- чится. Было предложено несколько способов представления программ для генетического программирования, но самым распространённым является древовидное представление. Каждый узел представляет либо операцию над дочерними узла- ми, либо является листовым, например, параметром или константой. Может показаться, что подобные деревья годятся только для построения совсем простых функций. Но следует отметить две вещи. Во-первых, узлы, входящие в дерево, могут представлять очень слож- ные компоненты. Во-вторых, дерево может быть рекурсивным, если допускаются ссылки на узлы, расположенные выше. С помощью таких деревьев можно организовывать циклы и более сложные управляющие структуры. Задание №1. Представление деревьев на языке Python. Построение и вычисление деревьев Прежде, чем переходить к выполнению задания, ознакомьтесь с той частью файла gp.py, которая понадобится Вам для этого. 90 from random import random,randint,choice from copy import deepcopy from math import log class fwrapper: def __init__(self,function,childcount,name): self.function=function self.childcount=childcount self.name=name class node: def __init__(self,fw,children): self.function=fw.function self.name=fw.name self.children=children def evaluate(self,inp): results=[n.evaluate(inp) for n in self.children] return self.function(results) class paramnode: def __init__(self,idx): self.idx=idx def evaluate(self,inp): return inp[self.idx] class constnode: def __init__(self,v): self.v=v def evaluate(self,inp): return self.v В этом фрагменте программного кода присутствуют 4 класса: fwrapper Обёртка для функций, которые будут находиться в узлах, представля- ющих функции. Его члены – имя функции, сама функция и количество принимаемых параметров. node Класс функциональных узлов (имеющих потомков). Инициализирует- ся экземпляром класса fwrapper. Метод evaluate вычисляет значения дочерних узлов и передаёт их представленной данным узлом функции в качестве параметров. 91 paramnode Класс узлов, которые просто возвращают один из переданных про- грамме параметров. Его метод evaluate возвращает параметр, соответ- ствующий значению idx. constnode Узлы, возвращающие константы. Метод evaluate просто возвращает то значение, которым экземпляр был инициализирован. Кроме классов в вышеуказанном файле присутствует ряд функ- ций, которые будут вызываться при посещении узлов. addw=fwrapper(lambda l:l[0]+l[1],2,'add') subw=fwrapper(lambda l:l[0]-l[1],2,'subtract') mulw=fwrapper(lambda l:l[0]*l[1],2,'multiply') def iffunc(l): if l[0]>0: return l[1] else: return l[2] ifw=fwrapper(iffunc,3,'if') def isgreater(l): if l[0]>l[1]: return 1 else: return 0 gtw=fwrapper(isgreater,2,'isgreater') flist=[addw,mulw,ifw,gtw,subw] С помощью класса node строим дерево программы: def exampletree( ): return node(ifw,[ node(gtw,[paramnode(0),constnode(3)]), node(addw,[paramnode(1),constnode(5)]), node(subw,[paramnode(1),constnode(2)]), ] ) 1. Запустите графическую оболочку. 2. Из-под неё откройте файл gp.py. 3. Запустите его на выполнение. 4. Введите следующие строки: import gp exampletree=gp.exampletree( ) exampletree.evaluate([2,3]) 5. Нажмите «Enter». 92 6. Введите следующую информацию: exampletree.evaluate([5,3]) 7. Нажмите «Enter». 8. На экране будут отображены результаты работы программы. Пока не очень понятно? Однако в этом задании был построен ми- ниязык для представления древовидных программ и написан интер- претатор для него. Последующие задания внесут ясность в вопрос, рассматриваемый в данной лабораторной работе. Задание №2. Визуализация программы Древовидные программы будут создаваться автоматически, об их структуре Вы заранее ничего знать не будете. Поэтому необходим способ визуализации программы, так чтобы её было легко интерпре- тировать. При проектировании класса node было предусмотрено, что в каждом узле будет храниться имя представляемой им функции в виде строки, поэтому функция вывода должна просто вернуть эту строку и отображаемые строки от своих дочерних узлов. Чтобы программу бы- ло проще читать, строки дочерних узлов нужно печатать с отступом, тогда будут сразу видны отношения родитель–потомок, существую- щие в дереве. Для реализации вышеуказанного: в классе node присутствует метод display, который выводит представление дерева в виде строки: def display(self,indent=0): print (' '*indent)+self.name for c in self.children: c.display(indent+1) в классе paramnode присутствует метод display, который печа- тает индекс возвращаемого параметра: def display(self,indent=0): print '%sp%d' % (' '*indent,self.idx) классе constnode также присутствует метод display: def display(self,indent=0): print '%s%d' % (' '*indent,self.v) 1. Запустите графическую оболочку. 2. Из-под неё откройте файл gp.py. 3. Запустите его на выполнение. 4. Введите следующие строки, чтобы распечатать: 93 exampletree=gp.exampletree( ) exampletree.display( ) 5. На экране должен появиться такой результат: if isgreater p0 3 add p1 5 subtract p1 2 Так выглядит дерево, построенное при помощи класса node. Код для него приведён в предыдущем задании (если p0>3, то p1+5 иначе p1-2). Задание №3. Создание начальной популяции Хотя программы для генетического программирования можно со- здавать и вручную, но обычно начальная популяция состоит из слу- чайно сгенерированных программ. Это упрощает запуск процесса, по- скольку отпадает необходимость проектировать несколько программ, которые почти решают задачу. Кроме того, таким образом в началь- ную популяцию вносится разнообразие, тогда как разные программы для решения одной задачи, написанные одним программистом, скорее всего, были бы похожи и, хотя давали бы почти правильный ответ, идеальное решение могло бы выглядеть совершенно иначе. Для построения случайной программы нужно создать узел, поме- стив в него случайно выбранную функцию, а затем – необходимое ко- личество дочерних узлов, каждый из которых может иметь свои до- черние узлы и т. д. Как обычно при работе с деревьями, проще всего сделать это рекурсивно. В файле gp.py это реализовано при помощи функции makerandomtree: def makerandomtree(pc,maxdepth=4,fpr=0.5,ppr=0.6): if random( ) 94 for i in range(f.childcount)] return node(f,children) elif random( ) return paramnode(randint(0,pc-1)) else: return constnode(randint(0,10)) Эта функция создаёт узел, содержащий случайно выбранную функцию, и проверяет, сколько у этой функции должно быть парамет- ров. Для каждого дочернего узла функция вызывает себя рекурсивно, чтобы создать новый узел. Так конструируется все дерево, причём процесс построения ветвей завершается в тот момент, когда у очеред- ного узла нет дочерних (то есть он представляет либо константу, либо переменную-параметр). Параметр pc равен числу параметров, прини- маемых деревом на входе. Параметр fpr задаёт вероятность того, что вновь создаваемый узел будет соответствовать функции, а ppr – веро- ятность того, что узел, не являющийся функцией, будет иметь тип paramnode. 1. Запустите графическую оболочку. 2. Из-под неё откройте файл gp.py. 3. Запустите его на выполнение. 4. Введите следующие строки: random1=gp.makerandomtree(2) random1.evaluate([7,1]) На экране появится некоторое число (у меня это было «7»). 5. Введите следующую строку: random1.evaluate([2,4]) На экране появится некоторое число (у меня это было «2»). 6. Введите следующие строки: random2=gp.makerandomtree(2) random2.evaluate([5,3]) На экране появится некоторое число (у меня это было «480»). 7. Введите следующую строку: random2.evaluate([5,20]) На экране появится некоторое число (у меня это было «18500»). 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 111 lastmove[i]=move if move==0: location[i][0]-=1 # Доска ограничена if location[i][0]<0: location[i][0]=0 if move==1: location[i][0]+=1 if location[i][0]>max[0]: location[i][0]=max[0] if move==2: location[i][1]-=1 if location[i][1]<0: location[i][1]=0 if move==3: location[i][1]+=1 if location[i][1]>max[1]: location[i][1]=max[1] # Если противник захвачен в плен, вы выиграли if location[i]==location[1-i]: return i return -1 Программа возвращает 0, если выиграл первый игрок, 1 – если второй, и –1 – в случае ничьей. Попробуйте создать две случайные программы и заставить их сыграть между собой: import gp p1=gp.makerandomtree(5) p2=gp.makerandomtree(5) gp.gridgame([p1,p2]) Программы ещё не подвергались эволюции, поэтому, скорее все- го, они будут проигрывать, делая два хода подряд в одном направле- нии. В идеале эволюционировавшая программа должна понять, что так делать нельзя. Круговой турнир Следуя идеологии коллективного разума, надо было бы проверять пригодность программ в игре против людей и соответственно прово- дить эволюцию. Было бы замечательно учесть при разработке «умной» программы поведение тысяч людей. Но при большой популяции и многих поколениях пришлось бы сыграть десятки тысяч игр, в боль- шинстве своём с очень слабыми противниками. На практике это нере- 112 ализуемо, поэтому сначала мы разовьём программы, заставив их со- стязаться друг с другом на турнире. Функция tournament принимает на входе список игроков и орга- низует игру каждого из них со всеми другими, отслеживая, сколько раз каждая программа проиграла. За проигрыш программе начисляется два очка, за ничью – одно. def tournament(pl): # Массив для подсчета проигрышей losses=[0 for p in pl] # Каждый игрок встречается со всеми другими for i in range(len(pl)): for j in range(len(pl)): if i==j: continue # Кто выиграл? winner=gridgame([pl[i],pl[j]]) # Два очка за поражение, одно за ничью if winner==0: losses[j]+=2 elif winner==1: losses[i]+=2 elif winner==-1: losses[i]+=1 losses[i]+=1 pass # Отсортировать и вернуть результаты z=zip(losses,pl) z.sort( ) return z В конце функция сортирует результаты и возвращает их вместе с программами, которые потерпели меньше всего поражений. Именно эта информация необходима функции evolve, чтобы организовать эво- люцию, поэтому функция tournament может использоваться в качестве аргумента evolve, следовательно, у вас всё готово для выбора про- граммы-победителя. Выполните в интерактивном сеансе следующие команды (на это может уйти заметное время): import gp winner=gp.evolve(5,100,gp.tournament,maxgen=50) 113 Игра с человеком Вы получили в ходе эволюции программу, которая победила всех своих кибернетических соперников. Теперь самое время сыграть с ней самому. Класс humanplayer: class humanplayer: def evaluate(self,board): # Получить мою позицию и позиции других игроков me=tuple(board[0:2]) others=[tuple(board[x:x+2]) for x in range(2,len(board)-1,2)] # Нарисовать доску for i in range(4): for j in range(4): if (i,j)==me: print 'O', elif (i,j) in others: print 'X', else: print '.', print # Показать ходы, для справки print 'Ваш последний ход %d' % board[len(board)-1] print ' 0' print '2 3' print ' 1' print 'Введите ход: ', # Вернуть введенное пользователем число move=int(raw_input( )) return move Начинайте игру в интерактивном сеансе: import gp gp.gridgame([winner,gp.humanplayer( )]) . O . . . . . X Ваш последний ход -1 114 0 2 3 1 Введите ход: Если программа хорошо эволюционировала, то победить её будет довольно трудно. Ваша программа почти наверняка научилась не хо- дить два раза подряд в одном направлении, поскольку это влечёт не- медленную гибель, но то, в какой мере она освоила другие стратегии, зависит от конкретного прогона evolve. Содержание отчёта: 1. Титульный лист. 2. Цель лабораторной работы. 3. Скриншоты результатов работы программы Контрольные вопросы |