Файл: Учебнометодическое пособие по лабораторному практикуму. Спб ниу итмо, 2013. 35 с. В учебнометодическом пособии предлагаются лабораторные работы, охватывающие основные понятия теории искусственного интеллекта.pdf

10 вычислений, поэтому чаще используется проверка того, что максимальное по популяции значение фитнесс-функции перестает заметно расти от поколения к поколению. Все эти критерии останова соответствуют критериям останова в методе градиентного спуска, но учитывают ту специфику генетических алгоритмов, что в них на каждой итерации одновременно рассматривается не одно, а несколько решений.
Особенности реализации генетических операторов в эволюционных
стратегиях
Рассмотрим особенности реализации генетических операторов в эволюционных стратегиях на примере объектов, описаниями которых являются двухкомпонентные векторы: (x,y).
1. Генерация начальной популяции может осуществляться путем выбора случайных векторов из области
[
] [
]
max min max min
,
,
y
y
x
x
×
, где величины max min max min
,
,
,
y
y
x
x
задают ожидаемые минимальные и максимальные значения переменных x и y искомого положения экстремума фитнесс-функции.
2. При выборе родителей особенность эволюционных стратегий выражается в способе задания меры родства. В данном случае, мерой родства двух особей
)
,
(
1 1
y
x
и
)
,
(
2 2
y
x
может служить евклидово расстояние:
(
) (
)
2 1
2 2
1 2
y
y
x
x
−
+
−
3. Результатом скрещивания двух особей в рассматриваемом случае будет являться особь
(
)
)
)
1
(
,
)
1
(
(
2 1
2 1
y
y
x
x
ε
−
+
ε
ε
−
+
ε
, где
]
1
,
0
[
∈
ε
– случайная величина.
4. Результатом мутации для особи
)
,
(
y
x
будет являться особь
)
,
(
y
x
y
x
δ
+
δ
+
, где
y
x
δ
δ
,
– случайные величины
Их распределение вероятностей может быть выбрано гауссовым или
, для простоты программной реализации
, равномерным в
некотором интервале
Дисперсия этих величин определяет скорость мутаций
5 и
6.
Операторы отбора и
критерии останова в
эволюционных стратегиях не имеют особых отличий от тех
, которые используются в
генетических алгоритмах
Экспериментальная часть
В
данной работе проводят анализ зависимости характеристик работы генетических алгоритмов или эволюционных стратегий
(
скорости их сходимости и
возможности обнаружения глобального экстремума фитнесс
- функции
) от установочных параметров
– размера начальной популяции и
скорости мутаций
, а
также от вида оптимизируемой функции

11
Для этого необходимо выполнить следующую последовательность действий
1.
Выполнить реализацию генетического алгоритма или эволюционной стратегии и
описать ее детали
2.
Для нескольких выпуклых
(
обладающих единственным максимумом
) функций построить графики зависимости
(
) (
)
2
*
2
*
y
y
x
x
m
m
−
+
−
(
где
( )
*
*
, y
x
– истинное положение глобального экстремума
, а
(
)
m
m
y
x
,
–
максимальное по текущей популяции значение фитнесс
- функции
) от номера популяции
i при различных значениях скорости мутации и
размера начальной популяции
Следует обратить внимание на выбор диапазона
[
] [
]
max min max min
,
,
y
y
x
x
×
Графики необходимо построить для двух случаев
: когда точка
( )
*
*
, y
x
попадает в
этот диапазон и
когда она находится вне него
3.
Для нескольких функций с
многими локальными экстремумами провести те же исследования
, что и
для функций с
единственным экстремумом
4.
Проанализировать полученные результаты
Определить
, какое именно влияние оказывает скорость мутаций на функционирование алгоритма поиска
Определить
, может ли большая скорость мутаций быть заменена большим размером популяции
Установить различия в
характере работы алгоритма поиска для функций с
единственным и
многими экстремумами
Сделать выводы по работе
Литература
1.
Назаров, А.В. Нейросетевые алгоритмы прогнозирования и
оптимизации систем
/
А
В
Назаров
,
А
И
Лоскутов
. –
СПб
.:
Наука и
Техника
, 2003. –
С
. 254-281.
2.
Люгер, Д.Ф. Искусственный интеллект: стратегии и методы
решения сложных проблем
/
Д
Ф
Люгер
. – 4- е
изд
.:
Пер с
англ
. –
М
.:
Изд дом
“
Вильямс
”, 2003. –
С
. 483-516.
Вопросы для самопроверки:
1.
В
чем основное отличие генетических алгоритмов от эволюционных стратегий
?
2.
Из каких основных шагов состоят генетические алгоритмы
?
3.
Как влияет скорость мутаций на скорость сходимость алгоритмов поиска
?
4.
При использовании какого типа родства
: ближнего или дальнего
, – скорость сходимости алгоритма будет больше
?

12 5.
Если при использовании эволюционных стратегий область задания начальной популяции
[
] [
]
max min max min
,
,
y
y
x
x
×
не содержит искомого экстремума
, то благодаря какому из генетических операторов этот экстремум все же может быть найден
?
Или при таких условиях он не может быть найден в
принципе
?
6.
Благодаря какому генетическому оператору эволюционные методы существенно отличаются от градиентного спуска
, и
в чем именно заключается это отличие
?
2. Методы построения ассоциативных сетей
Цель работы
– ознакомиться с
методами извлечения ассоциативных связей между понятиями на основе психофизических экспериментов
, а
также с
методами построения баз знаний
, включающих понятия и
взаимосвязи между ними
, которые описаны в
рамках логических представлений
Данная работа имеет два варианта выполнения
Вариант 1
Задание по работе:
1.
Изучить теоретическую часть работы
2.
Реализовать программу проведения тестирования в
некоторой предметной области для выявления ассоциативных связей между понятиями
3.
Провести тестирование группы людей
Усреднить и
проанализировать интервалы времени
, необходимые испытуемым для установления наличия или отсутствия ошибок в
утверждениях
, связывающих два понятия
, на основе чего определить длину пути в
ассоциативной сети между соответствующими узлами
Восстановить ассоциативную сеть
Теоретическая часть
Описание
методики
построения
ассоциативных
сетей
Очень давно было замечено
, что человек имеет склонность к
ассоциированию
Это послужило отправной точкой для создания ассоционистских теорий
, в
которых смысл некоторого понятия определяется через его ассоциативные связи с
другими понятиями
, которые в
совокупности образуют своего рода сеть
Понятия являются основой нашего знания о
мире
, поэтому такую ассоциативную сеть можно рассматривать в
качестве представления знаний
Ассоциативные связи возникают на основе опыта и
выражают эмпирические отношения между признаками или поведением объектов

13
Например
, на основании опыта мы ассоциируем понятие
«
снег
» с
другими понятиями
, такими как
«
зима
», «
холод
», «
белый
», «
лед
» и
т д
Наши знания о
снеге и
истинность утверждений типа
«
снег белый
» выражаются в
виде сети ассоциаций
Если такая сеть реально используется человеком
, то можно ли узнать
, какова она
?
Для ответа на этот вопрос психологами проводится следующий эксперимент
Людям задают вопросы из некоторой области
, например
, об особенностях и
поведении птиц
Эти вопросы выбираются очень простыми
: «
Может ли голубь летать
?», «
Может ли канарейка петь
?»,
«
Является ли ворона птицей
?».
При этом проверяется
, конечно же
, не правильность ответов на вопросы
Вместо этого оценивается время
, требуемое для ответа
Все вопросы составляются так
, что в
них фигурируют два понятия
Наличие непосредственной ассоциации между этими понятиями должно было сказываться на времени ответа
Как оказывается
, времена ответов действительно различаются
Так
, например
, для ответа на вопрос
«
Может ли канарейка летать
?» требуется больше времени
, чем для ответа на вопрос
: «
Может ли канарейка петь
?».
Коллинс и
Квиллиан
, ставившие этот эксперимент впервые
, объясняли большее время ответа на некоторый вопрос тем
, что участвующие в
вопросе понятия
, хотя и
расположены достаточно близко в
ассоциативной сети
, не являются непосредственно связанными
При этом оказалось
, что свойства объектов запоминаются людьми на наиболее абстрактном уровне
Вместо того чтобы запоминать каждое свойство для каждой птицы
(
канарейки летают
, вороны летают
, голуби летают
), люди хранят информацию о
том
, что канарейки
– птицы
, а
птицы
, как правило
, способны летать
Поскольку поют не все птицы
, то способность к
пению
– более частное свойство
, которое запоминается на менее абстрактном уровне
, чем способность летать
, поэтому и
ответ на вопрос
«
Может ли канарейка петь
?» требует меньше времени
, так же
, как и
ответ на вопрос
«
Является ли канарейка желтой
?».
Таким образом
, быстрее всего вспоминаются самые конкретные свойства объектов
Как оказалось
, и
исключения из правил также запоминаются на самом нижнем
, детальном уровне
Примером может служить вопрос
«
Может ли страус летать
?», который для ответа требует меньше времени
, чем тот же вопрос о
канарейке или другой
«
нормальной
» птице
На рис
. 1 представлен пример фрагмента ассоциативной сети
, которая могла бы быть построена в
результате такого эксперимента
В
рамках данной работы предполагается
, что в
областях
, относящихся к
здравому смыслу
, ассоциативные связи у
разных людей устанавливаются сходным образом
, поэтому для получения надежных значений времен ответов можно и
нужно проводить усреднение по некоторой группе людей
При этом выпор сферы понятий для тестирования нужно выбирать таким

14 образом
, чтобы ответы на составленные вопросы были очевидными для всех испытуемых
При малом числе испытуемых может использоваться повторное тестирование одного и
того же человека
, но необходимо
, чтобы были выполнены следующие условия
: база вопросов является достаточно большой
(
порядка
100 вопросов
) и
время перед повторным тестированием должно быть значительным
(
не менее суток
).
Экспериментальная часть
В
данной работе производят построение ассоциативной сети для некоторой ограниченной системы общеизвестных понятий на основе времени ответа человека на вопросы
, связывающие пары понятий
Для этого необходимо выполнить следующую последовательность действий
1.
Реализовать программу тестирования
, которая выбирает из базы случайные
, но неповторяющиеся вопросы и
определяет с
высокой точностью
(
порядка
0.1 секунды
) время ответа
Ввод ответа рекомендуется осуществлять по факту нажатия одной из двух заранее определенных клавиш
Не рекомендуется использовать способы ввода
, требующие перемещения мышки или ввода слов с
нажатием
Enter, поскольку это существенно снижает точность оценки времени
Показ очередного вопроса рекомендуется осуществлять только при готовности человека
(
о чем он может сообщать программе путем нажатия некоторой третьей клавиши
).
Рекомендуется
, чтобы программа автоматически записывала результаты ответов в
лог
- файл
2.
Составить базу вопросов
Для этого следует выбрать область со сложными
(
иерархическими
) отношениями между понятиями
, которые предположительно описываются ассоциативной сетью
, подобной представленной на рис
. 1.
Однако сами понятия должны быть общеизвестными
, а
ответы на вопросы
– не требующими привлечения дополнительных знаний
Рис
. 1.
Пример фрагмента ассоциативной сети
Животное
Птица
Канарейка
Страус
Летать
Перья
Дышать
Кожа
Желтый
Петь

15 3.
Провести тестирование группы людей
При этом требуется установить предпочтительную продолжительность тестирования одного человека
Для этого необходимо определить
, спустя какой промежуток времени начинает систематически увеличиваться время ответов или число ошибок
При тестировании каждого человека требуется объяснить ему условия эксперимента и
продемонстрировать их на нескольких вопросах
, которые затем не учитываются при анализе результатов
4.
Произвести усреднение времен ответов на вопросы по группе людей и
вычислить дисперсии времен для каждого вопроса
Установить достоверность различия средних времен ответов на разные вопросы
5.
Построить ассоциативную сеть
, если времена ответов на вопросы достоверно различаются
Построение сети рекомендуется начинать с
пар понятий
, которым соответствуют наименьшие времена ответов
Эти понятия должны быть непосредственно связаны в
сети
6.
Проанализировать полученные результаты
Если построение ассоциативной сети осуществлено удачно
, то проанализировать ее структуру
, в
противном случае определить возможные причины неудачи
Сделать выводы по работе
Литература
1.
Люгер, Д.Ф. Искусственный интеллект: стратегии и методы
решения сложных проблем
/
Д
Ф
Люгер
. – 4- е
изд
.:
Пер с
англ
. –
М
.:
Изд дом
“
Вильямс
”, 2003. –
С
. 226-230.
Вопросы для самопроверки:
1.
На основе какого принципа формируются тестовые вопросы
, используемые при построении ассоциативной сети
?
2.
Какой критерий используется при определении
«
ассоциативного расстояния
» между понятиями
?
3.
Почему не все пары понятий
, имеющих отношение друг к
другу
, в
ассоциативной сети связаны непосредственно
?
4.
Насколько корректно производить усреднение результатов
(
времени ответов
), полученным при тестировании разных людей
?
5.
Какие группы понятий предпочтительнее использовать при построении ассоциативной сети и
почему
?
Если требуется построить ассоциативную сеть для специальных понятий
, как следует подбирать тестируемых людей
?
Что означает различие структуры ассоциативной сети
, построенной по разным группам людей
?
6.
Какие ограничения имеет представление знаний в
форме ассоциативных сетей
, и
как эти ограничения могут быть сняты в
рамках других представлений
?

16
Вариант 2
Задание по работе:
1.
Изучить теоретическую часть работы
2.
Выбрать систему понятий из некоторой предметной области и
описать взаимосвязи между этими понятиями
3.
Реализовать программу на языке
Пролог
, в
которой установленные взаимосвязи описываются логическими формулами в
исчислении предикатов в
виде общих правил и
частных фактов
Определить возможности интерпретатора
Пролога по ответу на вопросы из данной области
Теоретическая часть
Краткое
описание
основ
языка
Пролог
Программа на языке
Пролог преимущественно состоит из списка логических утверждений
, которые можно разделить на факты и
общие правила
Эти утверждения составляются из имен предикатов
, переменных и
их значений
, которые представляют собой символьную строку
, начинающуюся с
буквы
, а
также совокупности логических операций
В
конце каждого утверждения ставится точка ".".
Переменные обязательно начинаются с
прописной буквы
, поэтому все значения должны начинаться со строчной буквы
Использующиеся в
Прологе обозначения логических операций представлены в
табл
. 1.
Табл
. 1.
Логические операции в
Прологе
Имя операции
Логическая операция
Обозначение в
Прологе и
∧
, или
∨
; если
⇐
:– не
¬
not
Рассмотрим некоторые примеры утверждений на языке
Пролог
Ниже приведен пример списка фактов
, не содержащих переменных man(serg). man(alex). father(serg, alex). mother(kat, serg).
Эти факты говорят
, что предикаты "man", "father", "mother" истинны при указанных значениях аргументов
Пролог работает в
рамках предположения о
замкнутости базы знаний
Это означает то
, что все

17 предикаты будут ложны для всех значений переменных
, для которых не было указано обратное
Общие правила в
Прологе записываются так же
, как и
факты
, но в
них присутствуют переменные
При этом подразумевается
, что общее правило верно при всех значениях всех входящих в
него переменных
Иными словами
, правило p1(X) :– p2(X,Y). означает логическое выражение
(
)
)
(
)
,
(
,
1 2
X
p
Y
X
p
Y
X
⇒
∀
Рассмотрим некоторые примеры общих фактов
, записанных на языке
Пролог
, и
приведем для них соответствующие формулы в
логике предикатов father(X, Y) :– man(X), parent(X, Y).
(
)
)
,
(
)
,
(
)
(
,
Y
X
father
Y
X
parent
X
man
Y
X
⇒
∧
∀
Если некто
X является мужчиной и
родителем
Y, то
X – отец
Y. parent(X, Y) :– mother(X, Y); father(X, Y).
(
)
)
,
(
)
,
(
)
,
(
,
Y
X
parent
Y
X
father
Y
X
mother
Y
X
⇒
∨
∀
X
является родителем
Y, если
X – отец или мать
Y. grandfather(X, Y) :– father(X, Z), parent(Z, Y).
(
)(
)
)
,
(
)
,
(
)
(
)
,
(
,
Y
Z
parent
Z
X
father
Z
Y
X
r
grandfathe
Y
X
∧
∃
⇐
∀
X
является дедушкой
Y только тогда
, когда
X является отцом
(
некоторого
) родителя
Y.
За исполнение программы на языке
Пролог отвечает интерпретатор
, который интерактивно взаимодействует с
пользователем
, отвечая на его запросы
Запрос к
интерпретатору также представляется в
виде логического выражения
, истинность которого требуется установить
Рассмотрим следующую простую программу mother(X, Y) :– woman(X), parent(X, Y). father(X, Y) :– man(X), parent(X, Y). grandfather(X, Y) :– father(X, Z), parent(Z, Y). man(serg). man(alex). woman(kat). parent(serg, victor). parent(kat, victor). parent(victor, alex).
И
посмотрим на следующие запросы
, начинающиеся с
приглашения "?–", на которые интерпретатор возвращает некоторый ответ
?– father(serg, victor).
Yes
?– grandfather(serg, alex).