Разработка программы для решения задачи аппроксимации логического вывода экспертной системы на основе генетического программирования с сетевым оператором - Дипломная работа

Под интеллектуальной системой будем понимать объединенную информационным процессом совокупность технических средств и программного обеспечения, работающую во взаимосвязи с человеком (коллективом людей) или автономно, способную на основе сведений и знаний при наличии мотивации синтезировать цель, вырабатывать решение о действии и находить рациональные способы достижения цели. В данной дипломной работе ставится задача аппроксимации логического вывода экспертной системы, то есть ее цель заключается в том, чтобы для любого момента времени найти оптимальный выход экспертной системы в виде функции, с заданными параметрами. Актуальность выбранной темы состоит в том, что методов и подходов для решения задачи аппроксимации логического вывода экспертной системы на сегодняшний день известно не очень много. В работе при решении данной задачи используется подход на основе новых методов генетического программирования и сетевого оператора (А.И. В основе аппроксимации логического вывода экспертной системы заложен сетевой оператор, основная задача которого - поиск необходимого математического выражения, где можно определить состав математического выражения: входящие параметры, переменные и вычислительные операции.Экспертная система [41] - компьютерная система, способная частично заменить специалиста-эксперта в разрешении проблемной ситуации. В информатике экспертные системы рассматриваются совместно с базами знаний как модели поведения экспертов в определенной области знаний с использованием процедур логического вывода и принятия решений, а базы знаний - как совокупность фактов и правил логического вывода в выбранной предметной области деятельности. 5) Проектирование - процесс создания новой информации об объекте, системе (имеется возможность исключения профессионала из процесса проектирования). В системах первого типа осуществляется выбор решения из множества известных решений на основе анализа знаний, в системах второго типа решение синтезируется из отдельных фрагментов знаний. В зависимости от способа учета временного признака, экспертные системы делят на статические и динамические: Статические экспертные системы [36] предназначены для решения задач с неизменяемыми в процессе решения данными и знаниями, а динамические экспертные системы допускают такие изменения.Система управления использует базу знаний экспертной системы для выработки управления на основе функции логического вывода или принятия решений. Задача заключается в том, чтобы по входным данным, получаемым из базы знаний и известным решениям или выводам, полученным с помощью экспертов аппроксимировать функцию логического вывода.В соотношении (1) выбор одной системы управления определяет выполнение условия . Значение дополнительной компоненты управления определяем по функции дополнительных признаков состояния объекта В большинстве случаев функция выбора не задана в аналитическом виде, а определена в виде множеств значений векторов признаков и значений функции выбора Соотношение (4) задает любая экспертная система, которая содержит запись вывода значения функции выбора по значениям векторов признаков Синтез функции выбора , совместно с синтезирующими функциями , в общем виде затруднен, так как функционалы и начальные условия в задачах синтеза для каждой синтезирующей функции могут быть различны.Генетический алгоритм - адаптивный метод поиска, который в последнее время часто используется для решения задач функциональной оптимизации. Генетический алгоритм может использоваться для проектирования структуры моста, поиска максимального отношения прочности, для использования интерактивного управления процессом или балансировании загрузки на многопроцессорном компьютере [8]. Генетический алгоритм работает с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Однако, генетический алгоритм, как и другие методы эволюционных вычислений, не гарантирует обнаружения глобального решения за полиномиальное время, не гарантирует и того, что глобальное решение будет найдено, но они хороши для поиска "достаточно хорошего" решения задачи "достаточно быстро". Оно появилось при использовании генетического алгоритма для автоматического написания программ, то есть создание такой программы, которая могла бы создавать другие программы без детального описания алгоритма, используя только набор требований и условий.Функциональная зависимость может быть представлена в виде дерева, во внутренних узлах которого находятся операции, а во внешних - операнды. Любой граф может быть представлен в виде матрицы смежности в котором - количество строк и столбцов равное количеству узлов графа, а элементы равны 1, если существует дуга от узла к узлу и 0, если такой дуги нет. Для повышения эффективности вычислительных алгоритмов в работе используется метод сетевого оператора, позволяющий в наиболее удобной для поиска на компьютере форме представлять функциональные зависимости. Также сетевой оператор - ориентированный граф, который

Содержание аппроксимация экспертный сетевой вычислительный

Введение

1. Экспертные системы

2. Постановка задачи

2.1 Формальная постановка задачи

3. Разработка алгоритма решения задачи

3.1 Генетический алгоритм и генетическое программирование

3.2 Метод сетевого оператора

3.3 Матрица сетевого оператора

3.4 Метод вариаций сетевого оператора

4. Вычислительный эксперимент

4.1 Описание программы

4.2 Моделирование эксперимента

Заключение

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

Приложения

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

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

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

Главным достоинством экспертных систем является возможность накопления знаний и сохранение их длительное время.

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

Целью дипломной работы является разработка эффективного вычислительного метода аппроксимации логического вывода динамической экспертной системы.

Для достижения поставленной цели было осуществлено решение следующих задач: - обзор методов и подходов решения поставленной задачи аппроксимации логического вывода экспертной системы;

- разработка и исследование метода сетевого оператора для решения поставленной задачи;

- проведение вычислительного эксперимента.

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

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

В дипломной работе в качестве наглядного примера используется замкнутая комната с препятствиями, в которой мобильный робот должен переместиться в некоторые терминальные точки. Для этого была создана программа на основе генетического алгоритма. Для разработки эффективного вычислительного метода решения задачи аппроксимации логического вывода экспертной системы необходимо использовать последнее достижение в области вычислительных алгоритмов, которым является создание метода генетического программирования для решения различных математических задач с помощью ЭВМ. Наиболее важным результатом последних лет в этом направлении является создание метода генетического программирования в 1992 году (J.R. Koza) [8], которое позволяет получить с помощью вычислительной машины аналитические решения различных математических задач. В генетическом программировании для универсального описания математического выражения и его кодировки используется польская запись программного кода, которая представляет собой строку символов, описывающих операторы и операнды. Польская запись является промежуточным кодом, к которому преобразуют трансляторы исходные тексты программ при их переводе в машинные команды. Для строк польской записи Коза разработал генетические операции скрещивания и мутации.

Новый разработанный метод является развитием генетического алгоритма (Davis Lawrence, D.E. Goldberg, J.H. Holland), позволив реализовывать на вычислительной машине любые функциональные зависимости. Методы генетического программирования, основанные на использовании структуры данных в виде строк польской записи, обладают существенными недостатками, связанными с работой с динамической памятью и лексическим анализом строк, что приводит к значительным вычислительным затратам. Для повышения эффективности вычислительных алгоритмов в работе используется метод сетевого оператора, разработанный А.И. Дивеевым, позволяющий в наиболее удобной для поиска на компьютере форме представлять функциональные зависимости.

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

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