Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Ответы по СИИ - файл crib_ai.doc


Ответы по СИИ
скачать (35.2 kb.)

Доступные файлы (1):

crib_ai.doc162kb.20.02.2008 16:04скачать

содержание
Загрузка...

crib_ai.doc

Реклама MarketGid:
Загрузка...
Вопросы по курсам

«Системы искусственного интеллекта» и

«Интеллектуальные информационные системы»


  1. Генетические алгоритмы (основные понятия и определения, операторы ГА).

  2. Знания и данные. Представления знаний (логические модели).

  3. Знания и данные. Представления знаний (продукционные модели).

  4. Знания и данные. Представления знаний (сетевые модели).

  5. Знания и данные. Представления знаний (фреймовые модели).

  6. ИИ в играх и творчестве.

  7. Искусственная жизнь.

  8. Искусственные нейронные сети (основные понятия и определения, виды НС, область применения).

  9. Искусственные нейронные сети: алгоритмы обучения (алгоритм обратного распространения ошибки).

  10. Искусственные нейронные сети: алгоритмы обучения (алгоритм обучения по дельта-правилу).

  11. Исследователи ИИ: А. А Ляпунов, В.М. Глушков.

  12. Исследователи ИИ: А. Тьюринг.

  13. Исследователи ИИ: Д. А. Поспелов, Г. С. Поспелов.

  14. Исследователи ИИ: М. Минский, Ф. Розенблатт.

  15. Компьютеры V, VI поколения.

  16. Многоагентные системы.

  17. Нейронная сеть Кохонена.

  18. Нейронная сеть Хемминга.

  19. Нейронная сеть Хопфилда.

  20. Основные направления исследований в ИИ.

  21. Роботы: I , II, III поколение.

  22. Системы ИИ. Историческая справка.

  23. Системы поддержки принятия решений (определение, назначение структура, область применения).

  24. Теория нечетких множеств (нечеткие отношения).

  25. Теория нечетких множеств (основные понятия и определения, операции над множествами).

  26. Теория нечетких множеств (понятие лингвистической переменной, нечеткие высказывания).

  27. Эвристическое программирование.

  28. Экспертные системы (классификация, проектирование и разработка).

  29. Экспертные системы (определение, назначение, структура, область применения).

  30. Языки искусственного интеллекта: Prolog, Рефал, LISP.




^ 1. Различные подходы к определению понятия «искусственный интеллект»

Искусственный интеллект – св-во автоматических систем брать на себя отдельные функции человека. 4 подхода: 1)думают подобно людям; 2)думают рационально; 3)действуют подобно людям; 4)действуют рационально. Осн. черты интеллектуальной деятельности - способности к: 1)обучению, 2)обобщению; 3)накоплению опыта(знаний и навыков); 4)адаптации к изменяющимся условиям.



^ 2.Системы ИИ. Историческая справка.

1)Начальные работы – Ньюсли, Саймон, Шоу -1956 г.,программа «Логик-теоретик», «Общ.решатель задач» (головоломки, интегралы). 2)Шеннон,Тьюринг – конец 1950-. яз. ИПЛ1, далее ЛИСП ;А.Самуэль – программа игры в шашки -1962–победа в турнире; «Каисса»-СССР 1974 победа на шахматном турнире. Действуя по оценочным ф-циям, накапливала опыт, меняя коэф. в оценочных ф-циях.При созд. игровых программ применялся метод эвристики – выбора в усл. неопределённости. Конец 60х – Д.Маккарти –доказательство теорем, исчисление предикатов 1 порядка. 3)Персептрон -1957 г. – модель зрит. нервной системы (Френк Розенбладт). Решает только огр. задачи классификации. 4) работа с текстом на естеств. языках. 5)экспертные системы -70-е гг. Метод построения: 1) логический вывод; 2)немонотонные логики (с появлением новых фактов может меняться истинность старых);3) накопление знаний по голосованию за и против фактов. К.Грин – вопросо-ответная система. 6)Робототехника – эл-ты интеллекта служат прежде всего для организации целенапр. движений; +восприятие окр. среды с помощью иск. органов чувств. 7)нейронные сети – прогнозир.; шифрование; распознавание; В дальнейшем появились многосл. нейронный сети. 8)Агент – всё, что действует: способность автономно работать; восприн. свою среду; существовать в теч. длит. времени; адапт. к изменениям. Рац. агент – чтобы можно былодостичь наил. результата.

^ 3.Области применения ИИ.

1)Восприятие и распознавание образов – получение исх.данных от органов восприятия. С этим лучше всего справляются нейронные сети. 2)Математика и автоматическое доказательство теорем – теория доказательств. Применяется в робототехнике, поиске информации и базах данных. 3)Игры. – шашки, шахматы и др. игры, где нет однозначного алгоритма выигрыша. 4)Экспертные системы - В некоторых слабо формализ. областях системы иск. инт. явл. единств. возможностью заменить человека компьютерной программой. 5) Понимание естественного языка. - Анализ и генерация текстов, выявление знаний, необходимых для понимания текстов, т.е. знаний синтаксических, прагматических и семантических, модели нечёткой логики. 6)Управление динамическими объектами. – задача может быть решена с помощью нейронных сетей и нечёткой логики. 7)Получение новых знаний. – задача обучения нейронных сетей без учителя.

^ 4.Области применения ИИ. Экспертные системы

ЭС- это набор программ, выполняющий ф-ции эксперта при решении задач из некоторой предметной области.

Экспертная система состоит из базы знаний (части системы, в которой содержатся факты), подсистемы вывода (множества правил, по которым осуществляется решение задачи), подсистемы объяснения(пользователь должен иметь возможность узнать, почему было получено решение), подсистемы приобретения знаний(возможность обучения и развития) и диалогового процессора (интерфейс пользователя). Для функционирования экспертной системы сначала формируются эвристики (правила, записанные на естественном языке), затем они записываются в форме правил (предложений, построенных по схеме «если..то»), потом переписать правила в виде предикатов истинности. Теперь можно задавать экспертной системе вопросы, и она будет на них отвечать, используя механизм логического вывода.

^ 5.Области применения ИИ. Системы машинного зрения.

Система машинного зрения состоит из камеры, платы захвата ввода изображения и блока анализа (программные средства). Изображение с камеры поступает на плату ввода, затем анализируется и в результате система машинного зрения принимает решение, что делать. Часто системы машинного зрения применяются в промышленном контроле качества продукции: напр. если внешний вид продукта не соответствует стандарту, конвейер останавливается. Создание систем машинного зрения достаточно трудоемко и технически сложно, так как требуется объединить решение задач, связанных с извлечением информации из поступающих с необходимой скоростью и качеством изображений (задача технического зрения) и с высокой точностью принять решение, т.е. разработать компоненты, отвечающие за техническое зрение и принятие решений, и объединить их единую в систему..

^ 6. Области применения ИИ. Системы понимания естественного языка.

Бывают 2 типов: основанные на 1.правилах и 2.примерах. В первых лучше проработаны правила и грамматика. Системы, основанные на примерах – самообучающиеся, могут выводить правила, исходя из конкретных примеров. В любом случае такие системы используют словари и правила работы со словарями + учёт семантических (смысловых) связей между словами, когда любое слово включается в граф как запись со следующей структурой: <I, C1…Cn, G> где I-информационная единица(слово, знак препинания или устойчивое выражение): С – связи этой единицы с другими единицами –вершинами графа G.



^ 7.Представление знаний. Логические модели.

Представление знаний – это их описание в доступной форме. их черты: 1)внутренняя интерпретируемость – каждая инф.единица должна иметь уникальное имя, по кот. ИС находит её и отвечает на запросы, в кот. это имя упомянуто.

2)структурированность. (иерархическая или люб. др. организация); 3)связность (связи отражают отношения м/у инф. един. в ИС должна быть возможность устранения связи м/у инф. един.). Возможны след. отн.: а)совместимость; б)аргумент-функция; в)причина-следствие; г)релевалентность(ситуационная близость); 4)активность(выполнение программ в ИС может инициализироваться текущим состоянием инф. базы) Выполнение программ может вкл. в себя добавление новых эл-тов и связей.

^ Формальная(логическая) модель представления знанийплюсы: в основе лежит строгая математическая теория; основная операция – логический вывод; минусы: закрытость, жесткость. Осн. мн-ва: 1)В – мн-во базовых эл-тов 2)Р - мн-во синтаксических правил; 3)А – мн-во аксиом; 4)V – мн-во правил вывода.

^ 8.Представление знаний. Продукционные модели.

Продукционные модели представления знаний состоят из правил вывода конечного результата – продукций. Применяется следующая схема: i: Q,P,AB;N где i- имя продукции. Q – сфера применения. Р – условие выполнения ядра. АB – ядро продукции. N – действие постусловия(что произойдёт после выполнения ядра). Р может выступать как функция вероятности того, что из А последует В. Можно ввести в модель ядро АB,C. Тогда из значения Р прогнозируется результат: В или С? Выбор правила для данной конкретной ситуации происходит в 2 этапа: 1)Включение метаправил (правил вывода правил); 2)распределение всех продукций по категориям; 3)отсеивание ненужных продукций. Плюсы продукционных моделей – простота обслуживания и модернизации.

^ 9.Представление знаний. Сетевые модели.

Сетевая модель представляет собой семантическую сеть, состоящую из объектов, событий и связей между ними. Эти элементы объединяются в граф. При этом каждый эл-т можно представить в след. виде: <I, C1…Cn, G> где I-информационная единица(слово, знак препинания или устойчивое выражение): С – связи этой единицы с другими единицами –вершинами графа G. Связи определяют тип отношения м/у 2 единицами – напр. «подмножество», «начало», «конец». Семантические сети часто применяются для переводов с естественных языков. При этом используются отношения, например:

Сети бывают 2 видов: статические и динамические (сценарии) – в последних узлы являются событиями.

^ 10.Представление знаний. Фреймовые модели.

Фрейм – структура, состоящая из заголовка, имён слотов и их значений. Применяется для описания типовых ситуаций. Различают фрейм-прототип и фрейм-экземпляр. Первый является описанием класса фреймов, а второй – его конкретной реализацией. Например: фрейм-прототип – название: работник; название слотов: фамилия, имя, должность; фрейм-экземпляр: значения слотов: Иванов, Сергей, слесарь. Значениями слота могут быть: тексты, математические отношения, ссылки на другие фреймы, набор слотов более низкого уровня. При этом возможно создавать новые фреймы на основе предыдущих, добавляя новые слоты и наследуя имеющиеся от фрейма более высокого уровня.




^ 11. Формальные системы (определение, формальное доказательство)

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

Нельзя заменять слова-связки: ЕСЛИ, СЛЕДОВАТЕЛЬНО.

Заданная формальная система – если:

  • задан конечный алфавит,

  • определена процедура построения формул формулой системы,

  • определено некоторое множество формул – аксиомы,

  • задано конечное множество правил вывода, которое позволяет получать из некоторого конечного множества формул другое множество формул.

^ Формальное доказательство – конечная последовательность формул, каждая из которых является аксиомой или получена из предыдущей формулы.

Формула называется теоремой, если существует доказательство, в котором она является последней.

Правила:

  1. постановки

  2. продукционные

1)x<y и y<z -> x<z – продукционное.

2)x – x -> 0 – правило подстановки(переписывания).


1) {a,b,[]} – символы.

2) Любая цепочка из этих символов – формула.

3) a[]a – аксиома.

4) с1[]c2 -> c1b[]c2b – правило вывода.

5) теорема – ba[]ba, bba[]bba.

6) не теорема – baba[]baab.



^ 12. Формальные системы. Разрешимость и интерпретация.

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

Интерпретация – распространение положений какой-либо формальной системы на реальный мир. Между символом формальной системы и объектом реального мира устанавливается взаимнооднозначное соответствие.

frame1



^ 13. Формальные системы. Алгоритмы унификации.

H -> C

E

(a+b)2 -> a2+2ab+b2;

Sin2x+cos2x -> 1;

Sin23a+cos2a – нельзя унифицировать.

  • Выражение Е и гипотезу Н рассматриваем на одну и ту же глубину.

  • Выполняются только те подстановки, которые необходимы.

  • Если удастся прийти от Н к Е, то унификация успешна и результат применения правила находится в заключении С, модифицированном с помощью тех же подстановок.

  • Можно замещать только свободные переменные.

  • Если мы заменяем Х термом, то этот терм не может содержать переменную Х.

  • Нельзя замещать операторы и константы, они должны находиться в Е и Н на аналогичных позициях, иначе невозможна унификация.

  • Выражения Е и Н представляются в виде дерева.

  • Этот алгоритм распространяется и на Н1, Н2, Н3 … -> C.


frame2Пример:

1) p^q -> q^p;

2) p^(q^r) -> (p^q)^r;

3) p^(pЭq) -> q;

4) ¬q^(pЭq) -> ¬p;

5) ¬¬p -> p;

6) p -> ¬¬p.

Доказать что (sЭ¬t)^t -> ¬s.

Д-во:


^ 14. Алгоритмы унификации. Принцип резолюций.

Впервые был описан Робинсоном в 1965 г. Вместо многих правил вывода системы автоматического доказательства теорем используют единственное – принцип резолюций. Пусть имеются выражения U и С, такие, что U=(U1,U2…), C=(C1,C2,…) и Ui=¬(не)Сi. Тогда U’=U¬Ui,С’=C¬Ci и £= U' & ф' – резольвента шага резолюции. Основная компонента систем автоматического доказательства теорем – система опровержения резолюций: Для того чтобы доказать, что р следует из некоторого описания состояния (или теории) Т, нужно положить —р и попытаться доказать, что из этого предположения следует утверждение, противоречащее Т. Если это удастся сделать, то тем самым подтверждается утверждение р, а в противном случае оно опровергается. Основная операция сопоставления в доказательстве теорем с помощью резолюций называется унификацией. Например, выражения БЕЖИТ_БЫСТРЕЕ_ЧЕМ(Х, улитка) и БЕЖИТ_БЫСТРЕЕ _ЧЕМ (черепаха, Y) превращаются в идентичные при подстановке {Х=черепаха, Y=улитка}. Такая подстановка называется унификатором. Цель алгоритма - отыскать наиболее общую подстановку такого рода.

^ 15. Классификация задач по мере сложности.

Сложная задача – функция, которая зависит от размера входных данных, является верхней границей числа операций необходимости для решения задач.

^ Самые хорошие алгоритмы – линейные.

Класс полиноминальных алгоритмов – сложность представляет полином некоторой степени, зависящих от входных данных. (Сортировки, эйлеровый цикл, обнаружение в тексте слова длины n, алгоритм Декстера).

^ Проверка планарности графов – ее сложность составляет nc. В 70-х гг. разработаны алгоритмы для n2, nlog, nm.

Экспоненциальная задача – fn, где f – константа или полином от n переменных. К этому классу относятся задачи – нужно построить все подмножества заданного множества, задача распознания всех возможностей, написанных на разных языках.

^ Решение систем уравнений в целых числах – цикл Гамильтона, составление расписаний, оптимальная загрузка емкости. Эти задачи решаются перебором, сначала перебираются решения, которые могут быть реальными алгоритмами для этих задач. Механизм с помощью машины Тьюринга + еще одна функция «выбор» - создает столько копий текущих состояний, сколько…


Для всех перечисленных задач была доказана их эквивалентность: если мы решаем одну из них, то мы можем автоматически решить и другие: недетерминированные задачи – автомат, который выполняет «+», «-», читать информацию, записывать информацию, «и», «или», «если то», повторение.

^ 16. Стратегии решения задач. Поиск в глубину.

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

^ Алгоритм перебора в глубину:

1) Раскрывается начальная вершина, соответствующая начальному состоянию.

2) Раскрывается первая вершина, получаемая в результате раскрытия начальной. Ставится указатель.

3) Если она раскрывается, то следующей будет раскрываться вновь порожденная вершина. Если вершина не раскрывается, то процесс возвращается в предыдущую вершину.

4) По получении целевой вершины процесс раскрытия заканчивается и по указателям строится путь, ведущий к корню. Соответствующие дугам операторы образуют решение задачи.

5) Если для заданной глубины раскрытия целевая вершина не найдена, то весь процесс повторяется снова, а в качестве новой вершины рассматривается самая левая из полученных на данном этапе.



^ 17. Стратегии решения задач. Поиск в ширину.

Вершины раскрываются в том порядке, в котором они строются. ^ Основной алгоритм состоит в выполнении следующих действий:

1) Начальная вершина раскрывается до тех пор, пока ее можно раскрыть, применяя один и тот же (или разные, смотря по условию) оператор. При этом образуются вершины первого уровня s2, s3, s4. Они раскрываются, образуя в свою очередь вершины второго уровня и т.д.

2) Расставляются указатели, ведущие от новых вершин к корню.

3) Проверяется, не ли среди полученных вершин целевой. Если есть, то формируется решение на основе соответствующего оператора. Если целевых вершин нет, то рассматривается первая порожденная вершина и к ней применяется тот же алгоритм. После этого переходят ко второй и т.д., пока среди получаемых вершин не окажется целевой.

Полный перебор в ширину гарантирует нахождение целевой вершины как раз потому, что перебор полный. Путей достижения цели, вообще говоря, может быть много. В этом случае имеется возможность выбрать наикратчайший (самый дешевый\легкий\быстрый и т.п.) путь. Но может быть случай, когда граф поиска окажется бесконечным, и тогда этот алгоритм никогда не кончит свою работу. Имеется класс задач, для которых этот метод эффективен. Классическим примером является задача «лабиринтного поиска», впервые решенная К.Шенноном. Здесь пространство различных вариантов действия невелико: «повернуть направо», «налево», «вперед» и решение обычно лежит на некоторой заданной (обычно небольшой) глубине.



^ 18. Представление задач в виде И\ИЛИ графов. Базовые процедуры поиска в И\ИЛИ графах.

И/ИЛИ-граф - это направленный граф, вершины которого соответствуют задачам, а дуги отношениям между задачами.

И/ИЛИ-представление основано на философии сведения задач к подзадачам.

Вершины И/ИЛИ-графа соответствуют задачам. связи между вершинами - отношениям между задачами.

Вершина, из которой выходят ИЛИ-связи, называется ИЛИ-вершиной. Для того, чтобы решить соответствующую задачу, нужно решить одну из ее задач-преемников.

Вершина, из которой выходят И-сзязи, называется И-вершиной. Для того, чтобы решить соответствующую задачу, нужно решить все ее задачи-преемники.

При заданном И/ИЛИ-графе конкретная задача специфицируется заданием стартовой вершины и целевого условия для распознавания целевых вершин.

Целевые вершины соответствуют тривиальным задачам.

Решение представляется в виде решающего графа - подграфа всего И/ИЛИ-графа.

Представление задач в форме пространства состояний можно рассматривать как специальный частный случай И/ИЛИ-представления, когда все вершины И/ИЛИ-графа являются ИЛИ-вершинами.

И/ИЛИ-представление имеет преимущество в том случае, когда вершинами, находящимися в отношении И, представлены подзадачи, которые можно решать независимо друг от друга. Критерий независимости можно несколько ослабить, а именно потребовать, чтобы существовал такой порядок решения И-задач, при кото­ром решение более «ранних» подзадач не разрушалось бы при решении более «поздних» подзадач.

Дугам или вершинам, или и тем, и другим можно приписать стоимости с целью получить возможность сформулировать критерий оптимальности решения.


Простейший способ организовать поиск в И/ИЛИ-графах средствами Пролога - это использовать переборный механизм, заложенный в самой пролог-системе. Пролог-система производит поиск в глубину в дереве и проходит через все вершины подграфа.

^ 19. Эвристический поиск.

Этап 1. Выбрать из множества возможных действий некоторое.

Этап 2. Осуществить выбранное действие и изменить текущую ситуацию.

Этап 3. Оценить ситуацию.

Этап 4. Отбросить бесполезные ситуации.

^ Этап 5. Если достигнута конечная ситуация—конец; если нет, выбрать новую исходную ситуацию и начать сначала.

Методы эвристического поиска:

1)• с учетом соответствия цели:

- уменьшение некоторого нежелательного различия,

- непосредственное решение той или иной подзадачи;

• с учетом опыта: повторение прошлого, обнаружение ключевого действия;

• с учетом необходимых условий:

- решение, обусловленное анализом ситуации,

- исключение неосуществимого варианта;

- с учетом фактора случайности:

- предпочтение отдается разнообразию.

3)• по аналогии: известна сама задача, известна подзадача;

• по величине расстояния до цели:

— расстояние между двумя ситуациями,

— количество усилий, затрачиваемых на поиск;

• по математическому критерию:

— составление перечня необходимых и/или достаточных для получения данного решения характеристик,

— численная оценочная функция, верхние и нижние границы,

— сумма стоимостей, выбранных подходящим способом;

• по ожидаемому выигрышу (критерий, связанный с прошлым опытом):

— простота ситуации, коэффициент расширения поиска,

— любой другой критерий (сложность задачи, затрачиваемое на ее решение время и т. д.). Этап 5. Выбор следующего шага

• двигаться только вперед:

— систематическое развитие последней порожденной ситуации;

• выполнять все действия параллельно:

— поочередное выполнение всех действий;

в качестве исходной выбирать самую многообещающую ситуацию:

— в отношении оценочной функции,

— в отношении незначительного числа входящих в нее действий;

• идти на компромисс между:

— глубиной поиска, оценкой ситуации.

^ 20. Метод ветвей и границ.

Метод ветвей и границ — метод решения переборных задач.


В основе этого метода лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия «разделяй и властвуй»). Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод был сначала предложен A. H. Land и A. G. Doig в 1960 г. для решения задач целочисленного линейного программирования.


Общая идея метода может быть описана на примере нахождения решения задачи минимизации функции f(x) по множеству допустимых решений x. Как f, так и x могут быть произвольными. Метод ветвей и границ использует две процедуры: ветвление и нахождение оценок (границ). Ветвление покрывает область допустимых решений областями допустимых решений меньших размеров. Процедура называется ветвлением, так как она повторяется рекурсивным образом далее к каждой из полученных подобластей, образуя дерево, называемое деревом поиска или деревом ветвей и границ. Вершины этого дерева соответствуют построенным подобластям. Другая процедура — нахождение оценок, которая является быстрым методом нахождения верхних и нижних границ оптимального решения в подобласти допустимых решений.


В основе метода ветвей и границ лежит простое наблюдение, что если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения. Это обычно выполняется с помощью глобальной переменной m, в которой запоминается минимальная верхняя граница, полученная для всех просмотренных до настоящего времени вариантах; любая вершина дерева поиска, нижняя граница которой больше m, может быть исключена из дальнейшего рассмотрения.




^ 21. Игры. Минимаксные методы. Альфа-бета алгоритм.


Под игрой понимают поиск в условиях противодействия. 2 противника, ходы делаются поочередно в условиях полной определенности. Изучает теория игр. В отличие от простых задач поиска, решение находится очень трудно. Например, в шахматах дерево поиска ~10^154 узлов. Дерево игры – определяется возможными ходами противников. Т.к. ходы противников делаются поочередно, в дереве «слои» ходов разных противников перемежаются.


В игре есть:

^ 1) функция определения преемника – возвращает список пар «допустимых ход, состояние»;

2) функция полезности (результат) для любого возможного терминального состояния (окончания игры).


^ Минимаксное (мм) значение для узла дерева – наш наивысший результат игры, достижимый из данного узла. Мы делаем лучшие ходы, т.е. выбираем ходы с наибольшим мм-значением. Противник делает лучшие ходы, т.е. выбирает ходы с наименьшим мм-значением. Минимаксный алгоритм – вычисляет мм-значение для текущего состояния.


^ Альфа-бета отсечение позволяет не рассматривать те вершины, для которых заранее известно, что они не оптимальны. Значение 7 в ветви «7» больше, поэтому противник пойдет по ветви 5 (ему нужен минимум). Поэтому ветвь «7» можно исключить из рассмотрения. Аналогично, значение 3 меньше, чем 5, а нам нужен максимум. Поэтому ветвь «3» можно исключить.




^ 22. Генетические алгоритмы. Основные принципы. Применение.


Это эвристический способ решения задачи, напоминающий процессы эволюции в природе. Представляет из себя последовательный подбор и комбинирование искомых параметров. Позволяет найти неточное удовлетворительное решение для задачи. Стадии генетического алгоритма:


0) Определение начальной популяции. Популяция – набор способов решения задачи (особей).

1) Определение функции полезности для каждой особи.

2) Селекция.

3) Мутация и/или скрещивание (кроссовер).

4) Возврат к 1) или окончание по некоторому условию.


Селекция. Выбор особей, участвующих в шаге 3. Производится по результатам ф. полезности. Пусть нам нужно N особей. Подходы выбора:

1) пропорциональный (отношение целое(ф.п./ф.п.средн) для особи – сколько раз участвует, если <1 то с такой вероятностью участвует);

2) турнирный (N раз проводится соревнование по несколько особей, выбираются победители);

3) усечения (N особей, у которых ф.п. лучшая);

4) рулеточный (берётся круг, под каждую особь выделяется сектор пропорционально ф.п., случайным образом N раз тыкают в круг и выбирают проткнутых).


Скрещивание – две особи делятся одинаково на две части. Затем пара одинаковых частей у особей обменивается.


Мутация – произвольное изменение особи.


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


К каким задачам не нужно применять эвристические алгоритмы:

1) Если варианты немногочисленны (использовать перебор)

2) Решение может быть достигнуто методом спуска

3) Известно конкретное эвристическое решение.

^ 23. Нейронные сети. Основные компоненты.


НС – устройство параллельных вычислений, математическая модель, представляющая собой систему соединенных простых процессоров (нейронов). Нейронные сети обучаемы и направлены на определенную задачу (напр. распознавание символов, прогнозирование валютных счетов, классификация образцов).


Нейронная сеть состоит из нейронов и связей между ними (синаптических связей).


Нейроны бывают входные, промежуточные и выходные. На входные подаются параметры исследуемого образца. Промежуточные нейроны, как правило, выделяют в слои.


^ Соединительная связь между нейронами i и j характеризуется весовым коэффициентом (передачи) Wij. Состояние нейрона с индексом j определяется суммой по i: NETj = Σ Xi*Wij, где Xi – выходы предшествующих нейронов. Выход нейрона Xj определяется его функцией активации Gj(NETj) и передается далее. Весовые коэффициенты играют важнейшую роль при обучении сети.


Функция активации нейрона чаще бывают двух типов: скачкообразная (в некоторой точке скачком изменяется от -1 до 1) или сигмоидальная = 1/(1 + exp(NET)) – ((выглядит наподобие синуса от –π/2 до π/2)).



^ 24. Обучение нейронной сети.


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


^ Процесс обучения проходит так:

0) весовые коэффициенты устанавливаются случайным образом

1) на вход НС подается обучающий образец, на выходе получается результат;

2) если результат нас удовлетворяет, процесс обучения окончен, иначе переход к шагу 3;

3) некоторые весовые коэффициенты слегка меняются (случайным образом или по специальной функции);

4) переход к шагу 1.


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


Обучение НС может вестись «с учителем» – обучение ведется по примерам или «без учителя» – сеть самообучается с помощью специальных функций.

Алгоритмы обучения делятся на детерминистские (жесткая последовательность действий) и стохастические (исп. случайные процессы).


^ 25*. Решение задач классификации с помощью нейронных сетей.


Классификация – это отнесение образца к определенному классу. В отличие от кластеризации, рамки каждого класса четко или нечетко, но определены. Классификация образцов – одна из задач, решаемых нейронными сетями.


Например, если нужно классифицировать самолеты:

если Вес > 0.8 & Скорость < 0.55 то Бомбардировщик

если Вес < 0.9 & Скорость > 0.25 то Истребитель


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


В некоторых случаях нельзя отделить образцы одного класса от образцов другого класса прямой линией. В этом случае проблема называется нелинейной. Она может быть решена только многослойными сетями.

26*. Решение задач кластеризации с помощью нейронных сетей.



^ 27. Ассоциативные сети.


Ассоциативные сети – нейронные сети, которые могут по неполному образцу воссоздать его вид. Это используется, например, в оптическом распознавании символов.


^ Сеть Хопфилда является такой сетью. В ней каждый элемент связан со всеми другими, но не связан с самим собой. За 1 шаг обновляется только один элемент сети (это делается в случайном порядке).


1. Входной образец задает начальное состояние элементов сети.

2. Случайным образом выбирается элемент для обновления.

3. Выбранный элемент получает сигналы от других.

4. Переход к 2, пока не будет достигнуто устойчивое состояние (т.е. сеть рекуррентна).


Функция активации – sgn, т.е значение на выходе каждого нейрона – знак его состояния sgn(NET). Матрица коэффициентов передачи связей вычисляется как трансп(X)*X, где X – вектор-образец, который нужно запомнить (правильный). На диагонали матрицы следует поставить нули, т.к. сам с собой элемент не связывается.

^ 28. Логические программы. Основные конструкции.


Логическая программа решает задачи, в которых используются понятия математической логики. Используются декларативные (описательные) языки программирования, в программы можно добавлять новые предложения: факты, правила, вопросы. Основная конструкция – предикат – определяет свойство для одного или нескольких объектов:

родитель(петя, вася).


Это был факт – конкретный предикат над конкретными константами. Правило определяет новый предикат на основе существующих, используя переменные:

дедушка(X, Y) :- родитель(X, Z), родитель(Z, Y).


Правила могут быть определены рекурсивно, т.е. через самих себя:

предок(X, Y) :- родитель(X, Y).

предок(X, Y) :- родитель(X, Z), предок(Z, Y)


Запятая понимается как конъюнкция «И», точка с запятой – дизъюнкция «ИЛИ». После задания вопроса (в ходе вычисления) переменные конкретизуются (c помощью операции сопоставления):

?- родитель(петя, X).

yes X =вася

^ 29. Декларативный и процедурный смысл Пролог-программы.


Декларативный смысл определяет, является ли цель достижимой и, если да, то при каких значениях переменных. ^ Процедурный смысл определяет, как будут выполняться предложения на Прологе.


Например, если записано:

P :- Q.

P :- S, T.


Декларативный смысл: P истинно, если истинно Q, или S и T.

Процедурный смысл: для вычисления P нужно вычислить Q, а если значение не определено, вычислить S, затем ещё T.


Декларативный подход предпочтительнее с точки зрения программирования. Процедурный – с точки зрения эффективности программ.

^ 30. Списки. Основные операции над списками.


Список – это структура данных, которая либо пуста, либо состоит из головы (это первый элемент) и хвоста (оставшиеся). Список представляется перечислением элементов в квадратных скобках через запятую. Элемент списка тоже может быть списком. Операция [X|Y] в Прологе разделяет список на эти две части:


[a,b,c,d] => [X|Y] => X=a; Y=[b,c,d]


Списки в Прологе могут использоваться для представления множеств. Наиболее распространенные операции: добавление, удаление проверка на принадлежность элемента списку, конкатенация списков.


1. Принадлежность. Первый параметр – элемент, который нужно проверить, второй – список. Результат – yes/no.

принадлежит(X, [X|L]).

принадлежит(X, [Z|L]) :- принадлежит(X, L).


^ 2. Конкатенация (сцепление). 1, 2 параметр – списки, 3 параметр – результат – их соединение.

конк([], L, L).

конк([X|L1], L2, [X|L3]) :- конк(L1, L2, L3).


3. Добавление. 1 параметр – элемент, 2 – список, 3 – результат – список с добавленным элементом (в начало списка).

добавить(X, L, [X|L]).


4. Удаление. 1 параметр – элемент, 2 – список, 3 – результат – список без элемента X.

удалить(X, [X|L], L).

удалить(X, [Y|L], [Y|L1]) :- удалить(X, L, L1).



Скачать файл (35.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru