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

86 вычисляется окончательная оценка фильма – оценка, данная каждым критиком, умножается на коэффициент подобия этого критика и про- изведения суммируются. В самом конце оценки нормализуются путём деления на сумму коэффициентов подобия и возвращается отсортиро- ванный список результатов.
1. Запустите IDLE (Python GUI). Откройте в нём recommenda- tions.py (File -> Open).
2. Откроется новое окно с текстом программного кода. Запусти- те файл на выполнение (Run -> Run Module или нажмите F5).
3. В появившемся окне введите: import recommendations нажмите «Enter» recommenda- tions.getRecommendations(recommendations.critics,'Toby') скопируйте результат в отчёт введите (многоточие при вводе удалите): recommenda- tions.getRecommendations(recommendations.critics,'Toby',
... similarity=recommendations.sim_distance) скопируйте результат в отчёт
В результате выполнения этого задания, мы получили не только ранжированный список фильмов, но и прогноз оценок, которые задан- ный пользователь поставит каждому из них. Имея такую информацию, можно решить, стоит ли вообще смотреть фильм. В зависимости от приложения вы можете вообще не давать рекомендаций, если не нашлось ничего, отвечающего стандартам данного пользователя. По- экспериментировав, вы обнаружите, что выбор метрики подобия влия- ет на результаты очень слабо.
4. Проделайте вышеуказанную процедуру для все критиков из списка.
5. Сделайте выводы
Задание №8. Рекомендование предметов (другие данные)
1. Выполните рекомендование предметов для Ваших данных
(аналогично заданию №7).

87 2. Сделайте выводы.
Содержание отчёта:
5. Титульный лист.
6. Цель лабораторной работы.
7. Задание №1 и №2: Результаты выполнения пунктов 3-4.
8. Задание №3: Результаты выполнения пунктов 4-6.
9. Задание №4: Результаты выполнения пунктов 1-2.
10. Задание №5: Результаты выполнения пунктов 4-7.
11. Задание №6: Результаты выполнения пунктов 1-2.
12. Задание №7: Результаты выполнения пунктов 3-5.
13. Задание №8: Результаты выполнения пунктов 1-2.
Контрольные вопросы

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( )0: f=choice(flist) children=[makerandomtree(pc,maxdepth-1,fpr,ppr)

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»).