Некоммерческое  акционерное общество

АЛМАТИНСКИЙ УНИВЕРСИТЕТ  ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра Компьютерных Технологий

 

 

СИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

Методические указания к выполнению курсовых работ

для студентов - бакалавров специальности

5В070400- «Вычислительная техника и программное обеспечение»

  

 

Алматы 2013

СОСТАВИТЕЛИ: Ахметова М. Системы Искусственного Интеллекта. Методические указания к выполнению курсовых работ для студентов - бакалавров специальности 5В070400 - «Вычислительная техника и программное обеспечение»,  - Алматы: АУЭС, 2013 -  29 с.

 

Методические указания содержат материал по выполнению курсовых работ  с примерами. Методические указания рекомендуются для студентов-бакалавров специальности 5В070400 - «Вычислительная техника и программное обеспечение».

Ил. 10, табл 5., библиогр. -  6 назв.

 

Рецензент:  ст.преп. Елеукулов Е.Р.

 

Печатается по плану издания некоммерческого акционерного общества «Алматинский университет энергетики и связи» на 2012 г.

 

© НАО «Алматинский университет энергетики и связи», 2013 г.

Введение

 

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

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

  

1         Общие положения о курсовом проектировании

 

1.1 Основные разделы курсового проектирования

 

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

1)     Введение в Искусственный Интеллект.

2)     Введение в Экспертные Системы.

3)     Стратегии поиска.

4)     методы поиска в пространстве состояний.

5)     методы поиска в пространстве разбиение задач.

6)     методы с использованием исчисление предикатов.

7)     Эвристические методы.

8)     Модели представления знаний.

9)     логическая модель.

10)   продукционная модель.

11)   модель, основанная на использовании фреймов.

12)   модель семантической сети.

13)   понимание естественного языка.

14)   методы нейронной сети.

15)   методы машинного обучения.

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

1)     Общее описание предметной области.

2)     Функции предметной области.

3)     Используемые документы.

4)     Ограничения.

5)     Форма выходного отчета.

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

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

  

1.2 Содержание основных этапов курсового  проекта

 

В процессе курсового проектирования выполняются следующие этапы работы:

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

2)    Выполнение постановки задачи с определением характера входных документов, форма выходной информации, с результатами решения задачи на компьютере.

3)    Выполнение информационного анализа описания  знаний предметной области и описание структуры данных, и если это необходимо, то построение базы данных.

4)    Определение модели представления знаний, при разработке экспертных систем, определение структур и форм данных, если это разработка игровых программ.

5)    Определение видов выходных форм: рисунки. текст, графика. Конкретные типы документов указываются в тексте индивидуального задания.

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

7)    Выбор и обоснование языков логического и функционального  программирования.

8)    Разработка контрольного примера и их кодов.

9)    Создание компьютерных программ на основе контрольного примера.

10)  Разработка инструкции пользователю, системному программисту, системному администратору.

11)     Сделать определенные выводы после выполнения курсового проекта.

 

1.3 Структура отчета курсового  проекта

 

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

Выполнение курсового проекта должно завершаться оформлением отчета. Отчеты должны быть оформлены по фирменному стандарту АУЭС и содержать принскрины, также он должен содержать:

1)     Титульный лист (пример приведен в таблице 1).

2)     Цель и задание работы.

3)     Оглавление или содержание.

4)     Введение.

5)     Описание работы.

6)     Основная часть.

7)     Графическая часть.

8)     Результаты проделанной работы (принскрины по каждому пункту задания с пояснением).

9)     Заключение.

10)  Список литературы(пример приведен в таблице 2).

11)  Приложения (листинги программ).

 

Пример титульного листа курсового проекта

Таблица 1

Некоммерческое акционерное общество АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ Кафедра «Компьютерных технологий»   КУРСОВОЙ  ПРОЕКТ по дисциплине «Системы искусственного интеллекта» на тему: «Решение интеллектуальной задачи с применением метода  поиска в пространстве состояний»   Выполнил: студент  группы БВТ- 09 Кубен Г. Руководитель:доц. Ахметова М.А   Алматы 2012

 

 Пример списка литературы

Таблица 2

Список литературы   1.       Братко И.  Программирование на языке Пролог для искусственного интеллекта.- М: Мир 1990г. 2.       Логическое программирование http: //ru.wukipedia.org/wiki/    3.       Доорс Дж. И др. Пролог- язык программирования будущего /Пер.с англ. – М.: Финансы и статистика, 1990. - 144 с. 4.       Хъювенен Э., Сеппянен Й. Мир Лиспа В 2-х т. Т.1: Введение в язык Лисп и функциональное программирование. пер. с финск. – М.:Мир, 1990. – 447с.

 

1.4 Задание на курсовое  проектирование

 

Задание на курсовое  проектирование содержит:

1)    Описание предметной области задач.

2)    Текст индивидуального задания, на основании которого выполняется курсовое  проектирование.

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

По дисциплине «Системы искусственного интеллекта»  для курсового проектирования мы предлагаем несколько тем.  Студенту предоставляется право на согласование с руководителем курсового проекта предлагать свою тему.  Ниже приводится описание предметной области.

 

2 Описание предметной области

 

При выполнении курсового проектирования по дисциплине «Системы искусственного интеллекта» в качестве примера предметной области рассмотрим два примера. К ним относятся разработка игровых программ с выбором метода поиска и разработка экспертной системы по определенной предметной области.   

2.1 Описание игровых программ с выбором метода поиска

 

Пример будет содержать следующие разделы: Введение, Описание задачи, Постановка задачи, Общие сведения о содержании решения задачи, Применяемый метод решения задачи, Выбор метода поиска.

Введение. Одним из важных вопросов, возникающих при проектировании управляющей компоненты систем, основанных на знаниях, является выбор метода поиска решения, т.е. стратегии вывода. От выбранного метода поиска будет зависеть порядок применения и срабатывания правил. Процедура выбора сводится к определению направления поиска и способа его осуществления. Работы по игровым программам развивались независимо от  математических исследований в области  «теории игр». Эти два направления имеют различные цели [1]. Математический анализ игр изучает стратегии, которым должен следовать идеализированный совершенный игрок.  При  программировании  действие игрока пытаются добиться приемами игры. Для того чтобы написать игровую программу, надо решить проблему представления структуры игры, т.е. необходимо определить сами понятия, составляющие структуру. Структура игры будет напрямую связана с методом   поиска решения. Имеется два аспекта  в решении задач: представление и поиск. Но пока, к сожалению, в исследованиях по искусственному интеллекту ещё не выработан универсальный метод для нахождения точных формулировок задач. Однако имеются подходы к постановке задач. Остается рассмотреть различные методы поиска. В данной работе мы попытаемся на примере классической игры «Волк, коза и капуста»  применить метод поиска в пространстве состояний.

 

Описание задачи. В качестве примера мы выбрали классическую игру «Волк, коза и капуста», так как на ее примере очень удобно описать построение игровой программы. Словесное описание задачи выглядит следующим образом: крестьянину нужно перевезти через реку:

-          волка;

-          козу;

-          капусту.

Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как должен перевезти свой груз крестьянин?

Постановка задачи. Написать и отладить программу решения задачи искусственного интел­лекта «Волк, коза и капуста», используя метод поиска в пространстве состояний.

 

2.2 Разработка алгоритмов задачи.

 

Общие сведения о содержании решения задачи. Есть два способа решить эту задачу:

1)       Приходится начать с козы. Крестьянин, перевезший козу, возвращается и берет волка, которого перевозит на другой берег, где его и оставляет, но зато берет и везет обратно на первый берег козу. Здесь он оставляет ее и перевозит к волку капусту. Вслед затем, возвратившись, он перевозит козу, и переправа оканчивается благополучно.

2)       Вначале крестьянин опять-таки перевозит козу. Потом можно взять капусту, отвезти ее на другой берег, оставить там и вернуть на первый берег козу. Затем перевезти на другой берег волка, вернуться за козой и снова отвести ее на другой берег. В этом случае количество рейсов (7) точно такое же, как и в первом варианте.

Применяемый метод решения задачи.  В литературе при решении данной задачи обычно применяют метод называемый  «Графа автомата Мура» [2]. Чтобы перейти от словесных описаний к таблицам, графам и схемам, мы предлагаем закодировать состояния игры следующим образом: выделим четыре двоичных разряда. Каждый разряд отвечает за то, какие существа на каком берегу реки находятся. Если в этом разряде хранится 1, то существо на первом (исходном) берегу, если 0 – на втором. Для наглядности продемонстрируем это на следующем рисунке:

 

Рисунок 1- Начальное состояние игры

 Из условия задачи становится ясно, что без присмотра крестьянина находиться вместе не могут: коза и капуста; коза и волк. Значит, следующие четыре комбинации являются проигрышными:

Рисунок 2-  Проигрышные состояние игры

 

Теперь, как мы все помним, нужно от словесного описания перейти к графическому описанию - графу. Это должно быть не сложно. Отметим начальное состояние С_ст - с него наша игра будет начинаться и им же оканчиваться.  Предполагается, что некая кнопка «СТАРТ» переводит автомат из состояния «0000» в состояние «1111». Обратите внимание на то, что так мы кодируем выходные слова, а вот состояния придётся закодировать другим образом. Значит, придётся ввести комбинационную схему, которая будет заниматься формированием выходных слов. Для управления крестьянином и остальными сущностями понадобятся четыре (см.таблицу 3) входных слова:

 

                       Таблица 3

Таким образом, входные и выходные слова названы, состояния обозначены. Применяем Граф автомата Мура. Будем изображать состояния следующим образом:

1)         Из нулевого состояния игра переводится в начальную позицию по приходу любого слова.

2)         Очевидно, что только тогда, когда крестьянин отвезёт козу первой (а1), игра может быть продолжена, иначе (а2, а3, а4) придётся начать всё заново.

3)    Отразим эти два факта на графе (см.рисунок 3):

Рисунок 3 -  Граф начального состояния

 

Рассуждаем дальше:

1)    Если сейчас подать на вход слова а2 или а3, то ясно, что крестьянин не сможет переправить волка или капусту, поэтому состояние игры не изменится. Однако он может отвезти козу обратно, и игра вернётся в начальное состояние.

2)    Значит единственным не тупиковым действием будет возвращение крестьянина на первый берег.

3)    Добавим это к нашему рисунку 4:

Рисунок 4 -  Граф нетупикового состояния

 

Теперь надо выбрать, кого везти на второй берег: капусту или волка. Неплохо было бы рассмотреть оба варианта (приведем рисунок 5 частично, чтобы легче воспринималось):

Рисунок 5 -  Граф двух вариантного состояния

 

То есть видно, что на первом берегу после этого перемещения останется либо капуста, либо волк. Если продолжить рассуждения в том же ключе, то можно прийти вот к такой нехитрой схеме: при попытке в 3, 4, 5 и 8 состояниях крестьянина уехать на другой берег, коза остаётся без присмотра рядом с волком или капустой, что чревато и ведёт к концу игры. Ну, или просто посмотрите в таблицу недопустимых состояний выше. При попытке перейти на них игра оканчивается.

 

 

Рисунок 6 -  Граф окончательного состояния

 

Теперь вспомним, как строятся таблицы переходов/выходов, и приведем таблицу 4.

Таблица 4

 

Выбор метода поиска. Процедура выбора сводится к определению направления поиска и способа его осуществления. Мы рассмотрим следующие методы, используемые в подходе пространстве состояний: а) метод полного перебора; б) метод поиска в глубину; в) эвристический метод. Чтобы построить описание задачи с использованием  пространства состояний, мы должны иметь определенное  представление о том, что такое состояние в этой задаче. Важным этапом построения какого-либо описания задачи с использованием пространства состояний является выбор некоторой конкретной формы описания состояний этой задачи.  В сущности, любая структура величин может быть использована для описания состояний. Это могут быть строки символов, векторы, двухмерные массивы, деревья и списки. Оператор преобразует одно состояние в другое. В общем случае мы будем предполагать, что операторы - это вычисления, преобразующие одни описания состояний в другие. Для полного представления задачи в пространстве состояний необходимо задать: а) форму описания состояний и, в частности, описание начального состояния; б) множество операторов и их воздействий  на описания состояний; в) свойства описания целевого состояния.

Рассмотрим первый из методов поиска в пространстве состояний.

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

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

Эвристический метод. Этот способ позволяет во всех случаях найти некоторый путь от начальной вершины к целевой, стоимость которого минимальна.  В то время как в вышеописанных алгоритмах распространяются линии равной длины пути от начальной вершины, в более общем алгоритме распространяются линии равной стоимости пути [3].  Для решения нашей задачи мы выбрали метод поиска в глубину. Для упрощения программирования пути в программе представлены в виде списков с узлами в обратном порядке. Параметр Локальное_решение нужен для распознава­ния циклов; для формирования решения. Как показала практика, этот поиск достаточно эффективен на коротких примерах. Однако в общем случае с бесконечными ветвями может привести к зависанию про­граммы. Циклы же он исключает из рассмотрения, и это позволяет найти наикротчайшее решение нашей задачи. Например, предикат не(содержит(Положение_2, Пройдено)), позволяет исключить из рассмотрения циклы, и потому можно утверждать, что ал­горитм достаточно надежен. Полный перебор по состояниям позволяет судить, что мы ничего не пропустим и найдем все решения. Приведем часть вывода программы, соответствующую данному алгоритму (см.таблицу 5). Через две пустых строки идут различные решения. Состояния выводятся в обратном порядке, можно было бы их записать и в прямом, но это менее наглядно отражало бы реальность. 

 

ПРОСТОЙ ПОИСК В ГЛУБИНУ БЕЗ ЗАЦИКЛИВАНИЯ

Таблица 5

 

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

Выбор языка программирования и реализация проекта.

Программа написана на Python с использованием логической системы SWI-prolog. Использовался модуль pyswip, который делает доступными возможности swi-prolog из Python. Было очень интересно интегрировать prolog с какими-либо часто ис­пользуемыми языками программирования. Мы выбрали Python. Это не только интересно, но и полезно, т.к. широкие возмож­ности логического программирования тут расширяют возможности Python. Программа представлена набором строк, которые впоследствии становятся программой на Прологе [4].

 

2.3 Описание разработки экспертных систем

 

Пример будет содержать следующие разделы: Введение, Описание задачи, Постановка задачи, Общие сведения о содержании решения задачи, Применяемый модель представления знания, Выбор метода поиска.

Введение. Экспертная система (ЭС) представляет собой компьютерную про­грамму, позволяющую автоматизировать достоверные рассуждения че­ловека-эксперта в конкретной предметной области. Основная цель, достигаемая при использовании ЭС, состоит в тиражи­ровании знаний высококвалифицированных экспертов. Это приводит к удешевлению процесса экспертизы, обращение к высококвалифициро­ванному человеку-эксперту не всегда возможно и стоит достаточно дорого, а также, вообще говоря, к повышению достоверности и надеж­ности результатов экспертизы. Последний аспект особенно ярко прояв­ляется в задачах принятия решений в условиях критических ситуаций, когда требуется быстро и безошибочно указать способ поведения реаль­ного объекта. В настоящее время ситуация такова, что существующие и проектируемые ЭС направлены на принятие решений в достаточно узких предметных областях, что, вообще говоря, соответствует практике использования живых экспертов [5].  Традиционным примером предметной области, где целесообразно при­менение ЭС, является область медицинской диагностики. Основываясь на данных анализов и внешних симптомах проявления болезни, а также на основе имеющейся дополнительной информации, ЭС должна указать наиболее правдоподобный диагноз, моделируя рассуждения человека-эксперта, в данном случае — лечащего врача или врача-диагноста. Неоспоримый факт, что предупредить болезнь легче и дешевле, чем впоследствии ее лечить. Современная медицина, особенно в условиях недружелюбной окружающей среды мегаполиса, опирается на два ключевых понятия - диагностику и профилактику. Диагностические программы  – это популярное направление современной профилактической медицины. Потребность врача в анализе больших объемов клинического материала, устранение ошибок субъективного характера делают актуальным создание автоматизированной диагностической системы для топической диагностики заболеваний нервной системы, дифференциальной диагностики неврологических и соматоневрологических синдромов, в том числе редких нозологических форм. На примере нашего курсового проекта реализована  медицинская диагностическая система - «врач-невропатолог».

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

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

Общие сведения о содержании решения задачи. В проектировании экспертных систем можно выделить следующие этапы: идентификация, концептуализация, формализация,  тестирование,  опытной эксплуатации. На этапе идентификации определяются задачи, которые подлежат решению, выявляются цели разработки, ресурсы, эксперты и категории пользователей. На этапе концептуализации проводится содержательный анализ проблем­ной области, выявляются используемые понятия и их взаимосвязи, определяют­ся методы решения задач.  На этапе формализации определяются способы представления всех видов знаний, формализуются основные понятия, определяются способы интерпрета­ции знаний, моделируется работа системы, оценивается адекватность целям системы зафиксированных понятий, методов решения, представления и манипулирования знаниями. На этапе выполнения осуществляется наполнение экспертом БЗ системы. На этапе тестирования эксперт в интерактивном режиме, используя диалоговые и объяснительные средства, проверяет компе­тентность ЭС. Процесс тестирования продолжается до тех пор, пока эксперт не решит, что система достигла требуемого уровня компетентности. На этапе опытной эксплуатации проверяется пригодность ЭС для конечных пользователей. По результатам этого этапа может потребоваться существенная модификация ЭС. Инструментальные средства создания ЭС можно классифицировать на: средства для создания простых ЭС; и для создания сложных ЭС.

Применяемая модель представления знания. Типичными моделями представления знаний являются: логическая модель; продукционная модель; модель, основанная на использовании фреймов; модель семантической сети.  Язык, используемый для разработки систем, спроектированных на основе этих моделей, называется языком представления знаний. Мы используем продукционную модель знаний. Продукционная модель имеет вид:

(i); P; Q: A_i => B_j ; N;

где i - номер правила; P- приоритет правила; Q- область применения правила;  A_i => B_j – ядро продукции; i,  j- с какой части берется утверждение, чаще всего i = БД, БЗ, диалог, О (блок объяснения)  j- тоже самое,  и помимо этого добавляется блок БЗ. А_БД => В_БД ; N- комментарии к продукции. Таким образом,  действия модели продукционного типа  основаны на применении правила вывода, суть которого состоит в следующем: пусть известно, что истинно утверждение А и существует правило вида: «Если А, то В», тогда утверждение В так же истинно. Правила срабатывают, когда находятся факты, удовлетворяющие их левой части: если истинна посылка, то должно быть истинно и заключение. Типичная ЭС состоит из следующих основ­ах компонентов (схема); решателя (интерпретатора), рабочей памяти (РП), называемой также базой данных (БД), базы знаний (БЗ), компонентов приобре­тения знаний, объяснительного и диалогового [6].

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

 

3 Пример выполнения курсового проекта

 

3.1 Пример разработки игровых программ

 

Программу на Python мы записываем в файл geneated.pl. Также мы подаем ее интерпретатору Пролога и получаем ре­шение вызовом функции query. Для решения задачи непосредственно использовался только Пролог. Что дает Python + Пролог:

1) Можно управлять Пролог-программой извне.

2) Можно посылать параметры извне, что мы и делаем.

3)    Мы получаем в руки не приложение для работы с Прологом, а инструмент для создания приложений

4)    Удобная и эффективная работа со стоками в Python, большое число расшире­ний + логического программирование становятся сильным средством в разработке ИИ.

5) Опыт в создании многоязычных систем.

Мы решили писать программу только по-русски, не используя ни одного английского слова, для этого, правда, приходится, заменять русское отрицание не() на not(). Приведем некоторые части программы и рекомендуем посмотреть ее код.

Вспомогательные функции

 

1        def consultFromString(string, prologEngine):

2                      

3                       ## В данной системе нет необходимости

4                       ## ставить точку в конце каждого утверждения.

5                       ## Потому разобьем строку по символу '.' и составим

6                       ## список из утверждений.

7                       ##

8                       ## Передаем системе swi—prolog каждый символ этого списка.

9                       ## Согласно разбиению последний содержит пустую строку.

10                    ##

11                    ## Ее мы НЕ передаем системе swi-prolog.

12                    ## об этом гласит "[:-1]"

13                    ##

14                    ## К сожалению, мы не можем передать список целиком,

15                    ## потому что система swi-prolog отдельно обрабатывает каждое утверждение.

16                     

17                    for str in string.split('.')[: — 1]:

18                    prologEngine.assertz(str)

19                     

20                    def ne2not(string):

21                    ## Для того чтобы,

22                    ## не было смеси

23                    ## заменим в программе 'not()' на 'не()'

24                    ## признаем, что это нарушение стандарта,

25                    ## но многие prolog системы и без того

26                    ## бессовестно его нарушают

27                    ## При подачи Пролог—программы, интерпретатору,

28                    ## придется совершить обратное преобразование.

29                     

30                    not_string = 'not('

31                    ne_string = 'не('

32                     

33                    If (ne_string in string):

34                           result = string.replace(ne_string, not_string)

35                           return result

36                    return string

 

Поиск

 

1         ## Опишем функции Python для каждого вида поиска

2                      

3         from time import *

4                       # для точного замера времени

5                      

6         def depthSearch(situation, prologEngine):

7                      t1 = clock()

8                       results = list(prologEngine.query(

9                                                    '''поиск_в_глубину( %s, Pешение )^;;%(situation)))

10                      t2 = clock()

11                      pretty_print(results, 'ПРОСТОЙ_ПОИСК_В_ГЛУБИНУ_БЕЗ_

ЗАЦИКЛИВАНИЯ', t2 - t1);

12                   

13         def iterativeDepeeng_1(situation, prologEngine):

14                      t1 = clock()

15                       results = list(prologEngine.query(

16                       ”’итеративное_углубление_грубое( %s, Pешение )’”%(situation)))

17                       t2 = clock()

18                       pretty_print(results, 'ИТЕРАТИВНОЕ_УГЛУБЛЕНИЕ_(ГРУБОЕ)',t2 -t1);

19                        

20                       def iterativeDepeeng_2(situation, prologEngine):

21                       t1 = clock()

22                       results = list(prologEngine.query(

23                       '''итеративное_углубление_изящное( %s, Pешение )’”%(situation)))

24                       t2 = clock()

25                       pretty_print(results, 'ИТЕРАТИВНОЕ_УГЛУБЛЕНИЕ_(ИЗЯЩНОЕ)',t2 - t1);

26                        

27                       def breadthSearch(situation, prologEngine):

28                       t1 = clock()

29                       results = list(prologEngine.query(

30                       '''поиск_в_ширину( %s, Pешение )’”%(situation)))

31                       t2 = clock()

32                       pretty_print(results, 'ПОИСК_В_ШИРИНУ',t2 - t1);

 

Рабочая часть

 

1        from pyswip import Prolog

2                       ## импортируем из pyswip класс Prolog

3                      

4         if(___ name___ == '_____ main___ '):

5                       # Выполняем в пространсве имен_______ main___

6                      

7                       ## сформируем строку, содержащую

8                       ## программу на прологе

9                      

10                      programString = string_With_Prolog_Std_Lib \

11                                                                                             + bankConditionString \

12                                                                                             + boardConditionString \

13                                                                                             + depthSearchString \

14                                                                                             + iterativeDepeengString_1 \

15                                                                                             + iterativeDepeengString_2 \

16                                                                                             + breadthSearchString \

17                   

18                       ## переведем нашу строку с 'русского' на стандарт языка,

19                       ## всего лишь заменив все вхождения слова 'не' не слово 'not'

20                   

21                       prologString = ne2not(programString)

22                   

23                        ## запишем эту строку на всяий случай в файл,

24                        ## этот файл можно будет запустить в системе SwiProlog

25                   

26                       preambul = '''%% для SWI-prolog

27          %% Эта программа была сгенерирована автоматически

28          %% не пытайтесь ее редактировать

29          %% запросы задавать в виде:

30          %% было(Положение), поиск_в_глубину( Положение, Pешение ).

31          %% было(Положение), итеративное_углубление_грубое( Положение, Pешение ).

32          %% было(Положение), итеративное_углубление_изящное( Положение, Pешение).

33          %% было(Положение), поиск_в_ширину( Положение, Pешение ).

34                        '''

35                       fileWithPrologString = open('geneated.pl', 'w')

36                       fileWithPrologString.write(preambul + prologString)

37                      fileWithPrologString.close()

38                   

39                      ## ТУТ НАЧИНАЕТСЯ ВОЛШЕБСТВО

40                   

41                      ## Создадим объект класса Prolog (из pyswip)

42                      prologEngine = Prolog()

43                   

44                      ## отдадим строку с программой интерпертатору Пролога

45                      consultFromString(prologString, prologEngine)

46                   

47                      ## Опишем начальную ситуацию

48                      situation = "[берег_1,^^берег_1,^^берег_1,^^берег_1]"

49                   

50                      ## Произведем 'ПРОСТОЙ ПОИСК В ГЛУБИНУ БЕЗ ЗАЦИКЛИВАНИЯ'

51                      depthSearch(situation, prologEngine)

52                   

53                      ## Произведем 'ИТЕРАТИВНОЕ УГЛУБЛЕНИЕ (ГРУБОЕ)'

54                      iterativeDepeeng_1(situation, prologEngine)

55                   

56                      ## Произведем 'ИТЕРАТИВНОЕ УГЛУБЛЕНИЕ (ИЗЯЩНОЕ)'

57                      iterativeDepeeng_2(situation, prologEngine)

58                   

59                      ## Произведем 'ПОИСК В ШИРИНУ'

60                      breadthSearch(situation, prologEngine)

 

3.2 Пример разработки экспертных систем

 

База Знаний в разрабатываемой экспертной системе представлена в виде диалога пациента и врача-невропатолога. В качестве примера рассмотрим правило, словесное описание которого выглядит так:  (см.рисунок 7).

 

 

Рисунок 7- Граф Ядра продукционной модели

 

Ядро продукции для рассмотренного правила имеет вид:

 А1 И А2 И А3  Þ В1 где  A1-  резкие головные боли , А2-красные глаза, А3- расстройство сна, В1-мигрень. Общая логика программы состоит в следующем: после того, как пациент ответит на вопросы, заданные ему в основном диалоге, соответствующие параметры передадутся в процедуры, привязанные к кнопке «получить диагноз», где произойдет анализ базы знаний.

 

 

Рисунок 8- Окно диалога пользователя и системы

 Также пациент может получать рекомендации и уточнять свой диагноз. Чтобы перейти к диагностике, Вам нужно нажать на картинку. Основное окно диалога пациента и системы представлено на рисунке 8. Пользователю нужно выбрать симптомы, которые у него имеются и нажать на «Получить Диагноз».  После этого открывается новое окно с диагнозом (см.рисунок 9).

В нем Вы узнаете свой диагноз. Также Вы сможете получить рекомендации по лечению заболевания, нажав на кнопку «Рекомендации». Если вы не понимаете, почему у Вас тот или иной диагноз, Вы можете уточнить его, нажав на кнопку «Почему у меня такой диагноз?» (см.рисунок 10). Если Вы некорректно указали ваши симптомы или не получили диагноз, Вы можете вернуться к началу диагностики, нажав кнопку «Вернуться к началу диагностики». Вы можете выйти из режима работы с системой в любой момент, нажав на кнопки «Выход», или на красный крестик в правом верхнем углу, присутствующие в любом окне программы.

 

Рисунок 9- Окно диагноза

 

Рисунок 10- Уточнение диагноза

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

Пример из листинга задачи «Экспертная система: Врач-невропатолог»

procedure TForm2.BitBtn1Click(Sender: TObject);

begin

Form3.Show;

Form2.Close;

Form3.ClientWidth:=361;

Bolezni[1]:='У Вас первые признаки мигрени.';

Bolezni[2]:='У Вас первые признаки неврастении.';

Bolezni[3]:='Атеросклероз сосудов головного мозга.';

Bolezni[4]:='Ваш диагноз не точен. Вам следует пройти обследование.';

Simptomi[1]:='Высокое давление';

Simptomi[2]:='Резкие головные боли';

Simptomi[3]:='Покраснение глаз';

Simptomi[4]:='Расстройство сна';

Simptomi[5]:='Нервозность';

Simptomi[6]:='Потливость и сухость во рту';

Simptomi[7]:='Ослабление внимания';

Simptomi[8]:='Головокружения';

Simptomi[9]:='Слабость';

 //правило для первой болезни

 if  ((Radiogroup2.ItemIndex=0)  and  // основные симптомы

 (Radiogroup3.ItemIndex=0) and (Radiogroup4.ItemIndex=0))

and   ((Radiogroup8.ItemIndex=0) or (Radiogroup8.ItemIndex=-1)

  or (Radiogroup8.ItemIndex=1))   //побочные симптомы

and   ((Radiogroup9.ItemIndex=0) or (Radiogroup9.ItemIndex=-1)

  or (Radiogroup9.ItemIndex=1))  //побочные симптомы

and  ((Radiogroup1.ItemIndex=-1)or (Radiogroup1.ItemIndex=1)) and

  ((Radiogroup5.ItemIndex=-1) or (Radiogroup5.ItemIndex=1)) and

  ((Radiogroup6.ItemIndex=-1)or (Radiogroup6.ItemIndex=1))  and

   ((Radiogroup7.ItemIndex=-1) or (Radiogroup7.ItemIndex=1))

then  Form3.Edit1.Text:=Bolezni[1]

 else

//правило для второй болезни

 if  ((Radiogroup4.ItemIndex=0)  and  // основные симптомы

 (Radiogroup5.ItemIndex=0) and (Radiogroup6.ItemIndex=0))and

  (Radiogroup7.ItemIndex=0)

and   ((Radiogroup8.ItemIndex=0) or (Radiogroup8.ItemIndex=-1)

  or (Radiogroup8.ItemIndex=1))   //побочные симптомы

and   ((Radiogroup9.ItemIndex=0) or (Radiogroup9.ItemIndex=-1)

  or (Radiogroup9.ItemIndex=1))  //побочные симптомы

and   ((Radiogroup3.ItemIndex=0) or (Radiogroup3.ItemIndex=-1)

  or (Radiogroup3.ItemIndex=1))  //побочные симптомы

and  ((Radiogroup1.ItemIndex=-1) or (Radiogroup1.ItemIndex=1)) and

  ((Radiogroup2.ItemIndex=-1)or(Radiogroup2.ItemIndex=1))

then  Form3.Edit1.Text:=Bolezni[2]

else

//правило для третьей болезни

begin

if  ((Radiogroup1.ItemIndex=0)  and  // основные симптомы

 (Radiogroup2.ItemIndex=0) and (Radiogroup4.ItemIndex=0))and

  (Radiogroup7.ItemIndex=0)

and   ((Radiogroup8.ItemIndex=0) or (Radiogroup8.ItemIndex=-1)

  or (Radiogroup8.ItemIndex=1))   //побочные симптомы

and   ((Radiogroup3.ItemIndex=0) or (Radiogroup3.ItemIndex=-1)

  or (Radiogroup3.ItemIndex=1))  //побочные симптомы

and   ((Radiogroup9.ItemIndex=0) or (Radiogroup9.ItemIndex=-1)

  or (Radiogroup9.ItemIndex=1))  //побочные симптомы

and  ((Radiogroup5.ItemIndex=-1) or (Radiogroup5.ItemIndex=1)) and

  ((Radiogroup6.ItemIndex=-1)or(Radiogroup6.ItemIndex=1))

  then  Form3.Edit1.Text:=Bolezni[3] 

else

      Form3.Edit1.Text:=Bolezni[4];

end;

end;

 

4.Разработка инструкции пользователю, системному программисту, системному администратору.

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

 

5 Разработка раздела выводов курсового проекта

 5.1 Разработка выводов по интеллектуальным задачам.

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

Заключение. При  программировании игр действие игрока пытаются добиться приемами игры. Для того чтобы написать игровую программу, надо решить проблему представления структуры игры, т.е. необходимо определить сами понятия составляющие структуру. Структура игры будет напрямую связана с методом поиска решения. В качестве игровой программы мы выбрали классическую игру «Волк, коза и капуста». Для ее решения мы применили метод называемый  «Графа автомата Мура». При выполнении этой работы мы использовали симбиоз Python и Пролог. Это позволило нам, например, точно измерить время работы различных видов поис­ка. Мы приобрели опыт в сращении нескольких языков различных парадигм. Кроме того,  мы можем сами контролировать вывод и направить его не в файл, а на текстовое поле окна, разукрасив его предварительно всеми цветами радуги. Пролог — язык логического программирования. Эту парадигму весьма легко воспри­нимать, если не знаком с другими. В Японии его преподают в школе. А чем мы хуже? Мы стали выполнять свою курсовую исключительно на русском языке, нарушая стандарт, потому что хотели бы попытаться написать некое подобие современной системы ло­гического программирования для школьников. Использование русского облегчило бы процесс обучения. Мы познакомились со стратегией использования пространства состояний. Это оказа­лось очень удобно, нам не нужно было для каждого поиска формулировать задачу заново или вносить в формулировку изменения. Поиск в глубину весьма экономичен по памяти, но в своей реализации неустойчив, и расточителен по времени. Его модификации дают значительно лучшие результаты, но сами программы ста­новятся менее читаемы. В поиске в ширину со временем и памятью все наоборот. А читаемость программы еще хуже, более того пришлось использовать встроенные предикаты, без которых программист до сих пор обходился. Мы думаем, что для различных задач подходят различные виды поиска, и выбор должен зависеть от цели. Таким образом, решая поставленную задачу, мы научились делать постановки игровых программ, изучили разные методы ее решения, научились выбирать среду программирования для решения таких задач. И наконец, научились программировать в стиле логического программирования.

 

5.2 Разработка выводов по экспертным системам.

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

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

6 Перечень тем курсового проекта

 6.1 Темы по интеллектуальным системам

 

1.     Создать игровую программу с поиском на основе данных.

2.     Создать игровую программу с поиском на основе от цели.

3.     Создать игровую программу с описанием в виде И/ИЛИ графа. 

4.     Создать компьютерную программу использующий метод редукций.

5.     Создать программу, использующую эвристический алгоритм для «Робот ищет яблоко».

6.     Создать игровую программу, с описанием из множества ППФ «Робот ищет в комнате цветок».

7.     Создать свою игровую программу стратегией полного перебора «Робот находит студента».

8.     Разработка программы на Прологе как справочная служба туриста.

9.     Составить базу данных на Прологе -  родословную «Шежире».

10. Составить программу на Прологе игры «Крестики - нолики».

11. Разработать программу на Прологе игры в «Морской бой».

12. Разработать программу на Прологе эксперта-кулинара.

13.  Составить базу данных на Прологе марки автомашины «Форд».

14. Составить базу данных на Лиспе прогноза погоды: «Месячный прогноз для Алматы».

15. Составить программу на Лиспе «Язык сплетника» с использованием секретных ключевых слов.

16. Составить программу на Лиспе «Животные», классифицирующий тип животных.

17. Составить программу на Лиспе игры «Реверси».

18. Составить программу на Лиспе игры «Рикошет».

19. Составить программу обучения по методам нейронных сетей.

20. Составить программу обучения  по готовым шаблонам словаря.

21. Составить программу распознавания простого текста.

22. Составить базу данных на Прологе справочной системы «Планеты Солнечной системы».

23. Составить базу данных на Лиспе «Помощник по Информатике».

24. Разработка программы на Прологе - как справочной службы АУиЭС

25. Разработка программы на Прологе - как справочной службы ФИТ.

26. Составить базу данных на Лиспе «Помощник абитуриенту АУиЭС».

27. Разработка программы на Прологе - как справочной кафедры КТ

28. Составить базу данных на Лиспе «Помощник Заочнику АУиЭС».

29. Разработка программы на Лиспе, как справочная служба библиотеки АУиЭС

30. Составить базу данных на Лиспе «Помощник по Дистанционному обучению АУиЭС».

 

6.2 Темы по Экспертным системам

 Спроектировать экспертную систему по следующим темам:

а)планирование

1.     Спроектировать продукционную модель «Электронная сваха».

2.     Создать все компоненты ЭС для «Оценка стоимости косметических услуг».

3.     Спроектировать фреймовую модель «Риэлтор».

4.     Построить фреймовую модель в области «Торговый центр».

5.     Создать все компоненты ЭС для модели «Трудовая биржа».

б)диагностика

6.     Спроектировать продукционную модель «Глазной врач».

7.     Спроектировать фреймовую модель для «Библиотека».

8.     Спроектировать продукционную модель «Маклер».

9.     Построить фреймовую модель в области «Железная дорога».

10. Построить модель семантической сети «Врач-терапевт».

11. Построить модель семантической сети «Автомеханик».

в)прогноз

12. Создать ЭС для продукционной модели «Помощь по ипотеке».

13. Построить фреймовую модель в области «Автозаправка».

14. Построить ЭС для финансового прогноза работы предприятия.

15. Построить ЭС для отдела логистики автотранспортного предприятия.

г)анализ

16. Построить фреймовую модель для «Ресторан».

17. Построить фреймовую модель «Аэропорт».

18. Построить фреймовую модель в области «Турист».

19. Построить продукционную модель в области «Университет».

20. Построить ЭС для оценки активов малого предприятия.

д)обучение

21. Построить модель семантической сети «Зоопарк».

22. Построить фреймовую модель «Информационные системы».

23. Построить ЭС обучения по пониманию простых предложений казахского языка.

24.  Построить ЭС обучения терминам «Системы Искусственного интеллекта».

25. Построить ЭС обучения по методам нейронных сетей.

26. Построить ЭС по нейропакетам искусственных нейронных сетей.

е)распознование

27. Построить ЭС речевого распознавания .

28. Построить ЭС распознавания простых геометрических фигур.

29. Построить ЭС распознавания по простым звукам животных.

30. Построить ЭС распознавания  выражения казахского языка.

 

 Список литературы

5.Нильсон Н. Искусственный интеллект. Методы поиска решений./ Пер. с анг. –М.:Мир, 1973. - С. 270

6.     Люгер, Джордж,,Ф. Искусственный интеллект: стратегии и методы решения сложных проблем.- М, 2003г.- 864 с.

7.Большакова. И., Мальковский М. Г., Пильщиков В. Н.  Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие) - М.: Издательский отдел факультета ВМК МГУ, 2002.83 с.

8.Логическое программирование http: //ru.wukipedia.org/wiki/.   

9.Джексон Питер, Введение в экспертные системы. / Пер.с англ.: Уч.пособие, 2001. – 624 с.

10.Ахметова М. Функционалдық-логикалық программалау және жасанды зерде жүйелері: Оқу құралы. - Алматы: «Бастау» баспасы.  2012.- 330 б.

 

Содержание

	Введение	3
1	Общие положения о курсовом проектировании	4
1.1	Основные разделы курсового проектирования	4
1.2	Содержание основных этапов курсового  проекта	5
1.3	Структура отчета курсового  проекта	5
1.4	Задание на курсовое  проектирование	7
2	Описание предметной области	7
2.1	Описание игровых программ с выбором метода поиска	7
2.2	Разработка алгоритмов решения задачи.	8
2.3	Описание разработки экспертных систем	15
3	Пример выполнения курсового проекта	17
3.1	Пример разработки игровых программ	17
3.2	Пример разработки экспертных систем	20
4	Разработка инструкции пользователю, системному программисту, системному администратору.	24
5	Разработка раздела выводов курсового проекта	24
5.1	Разработка выводов по интеллектуальным задачам.	24
5.2	Разработка выводов по экспертным системам	25
6	Перечень тем курсового проекта	27
6.1	Темы по интеллектуальным системам	27
6.2	Темы по Экспертным системам	28
	Список литературы	29

Сводный план 2012 г. поз.225