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

Размещено на http://www.allbest.ru/

Содержание

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

Введение

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. Разработанный в дипломной работе метод аппроксимации логического вывода экспертной системы может быть использован в реальных экспертных системах.

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

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

Экспертная система [41] -- компьютерная система, способная частично заменить специалиста-эксперта в разрешении проблемной ситуации. Современные экспертные системы начали разрабатываться исследователями искусственного интеллекта в 1970-х годах. Предтечи экспертных систем были предложены в 1832 году С.Н. Корсаковым, создавшим механические устройства, так называемые "интеллектуальные машины", позволявшие находить решения по заданным условиям, например определять наиболее подходящие лекарства по наблюдаемым у пациента симптомам заболевания.

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

Основные назначения экспертных систем [41]:

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

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

3) Прогнозирование - обоснованное описание последовательности событий, с возможностью обнаружения новых факторов.

4) Мониторинг - непрерывное оповещение о состоянии системы, приложения или процесса.

5) Проектирование - процесс создания новой информации об объекте, системе (имеется возможность исключения профессионала из процесса проектирования).

6) Диагностика - процесс распознавания состояния на основе имеющихся факторов.

7) Обучение - обучение пользователя, а так же самообучение системы, как на этапе приобретения знаний, так и в процессе работы ЭС (пополнение базы знаний (БЗ) ЭС новыми цепочками вывода).

Классификация экспертных систем:

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

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

Статические экспертные системы [36] предназначены для решения задач с неизменяемыми в процессе решения данными и знаниями, а динамические экспертные системы допускают такие изменения.

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

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

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

Продукционные экспертные сиситемы [2] представляют знания в форме предикатов первого порядка, а правила манипулирования ими - с помощью конструкций "ЕСЛИ - ТО". База правил состоит из множества фраз типа:

-ЕСЛИ объект системы управления не осуществил применение средства воздействия вида ПК (ПУСК = 0)

-И объект системы управления имеет разрешение применения средства воздействия вида ПК (ПУСК = 1)

-ТО система рекомендует применение средства воздейстия вида ПК.

Типовая структура экспертных систем:

Рис. 1 Типовая структура экспертных систем.

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

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

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

Механизм логического вывода (МЛВ) [49] предназначен для получения новых фактов на основе сопоставления исходных данных из рабочей памяти и знаний из базы знаний. Механизм логического вывода во всей структуре экспертной системы занимает наиболее важное место. Он реализует алгоритмы прямого и/или обратного вывода и формально может быть представлен четверкой: <v,s,k,w>. Где:

· V процедура выбора из базы знаний и рабочей памяти правил и фактов;

· S процедура сопоставления правил и фактов, в результате которой определяется множество фактов к которым применимы правила для присвоения значений;

· K процедура разрешения конфликтов, определяющая порядок использования правил, если в заключении правила указаны одинаковые имена фактов с разными значениями;

· W процедура, осуществляющая выполнение действий, соответствующих полученному значению факта (заключению правила).

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

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

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

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

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

(1)

где

В соотношении (1) выбор одной системы управления определяет выполнение условия .

Значение дополнительной компоненты управления определяем по функции дополнительных признаков состояния объекта

(2)

где - целочисленная функция выбора, y - целочисленный вектор признаков определения выбора

(3)

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

(4)

где

Соотношение (4) задаёт любая экспертная система, которая содержит запись вывода значения функции выбора по значениям векторов признаков

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

Рассмотрим идентификацию функции выбора , с помощью метода сетевого оператора.

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

(5)

Необходимо найти аналитический вид функции выбора

(6)

обеспечивающей минимум функционала

(7)

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

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

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

Генетический алгоритм - адаптивный метод поиска, который в последнее время часто используется для решения задач функциональной оптимизации. Он основан на генетических процессах биологических организмов: биологические популяции развиваются в течение нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" [6].

Подражая этому процессу генетический алгоритм способен "развивать" решения реальных задач, если те соответствующим образом закодированы. Генетический алгоритм может использоваться для проектирования структуры моста, поиска максимального отношения прочности, для использования интерактивного управления процессом или балансировании загрузки на многопроцессорном компьютере [8]. Основные принципы генетического алгоритма были сформулированы Голландом (Holland, 1975) [8]. Алгоритм моделирует те процессы в популяциях, которые являются существенными для развития. Генетический алгоритм работает с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи.

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

Рис. 2 Основные этапы генетического алгоритма.

Особенности генетического алгоритма:

1.варианты решения кодируются битовой строкой (хромосома);

2.поиск осуществляется в кодовом пространстве параметров;

3.оценка вариации решения осуществляется по значению функции приспособленности, которая строится на основе целевой функции и ограничений оптимизационной задачи;

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

5.селекция осуществляет отбор пар кодов возможных решений для скрещивания по значению функции приспособленности;

6.скрещивание обеспечивает построение пары новых кодов решений на основе двух отобранных;

7.мутация обеспечивает случайную вариацию кода возможного решения;

8.завершение вычислений осуществляется по удовлетворительному значению функции приспособленности или по конечному числу циклов воспроизводства популяций возможных решений (поколения);

9. решение - хромосома, которая дает наилучшее значение функции приспособленности.

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

Главным же преимуществом генетического алгоритма является то, что они могут применяться даже на сложных задачах, там, где не существует никаких специальных методов. Генетическое программирование [6, 8, 28] впервые предложил Джон Коза в 1992 году, которое является развитием метода генетического алгоритма. Оно появилось при использовании генетического алгоритма для автоматического написания программ, то есть создание такой программы, которая могла бы создавать другие программы без детального описания алгоритма, используя только набор требований и условий. Преимуществом автоматического написания программ является то, что заранее не надо указывать размер, форму, сложность структуры решения. Генетическое программирование является поиском необходимой программы адаптивным и интеллектуальным способом. Интеллектуальный поиск на любом множестве начинается с выбора одной или более структур из данного множества и оценки ее пригодности при решении задачи. Затем эту информацию используем для изменения, улучшения и направления поиска видов выбора структур из множества. В алгоритме выбираем точку, ее пригодность сравниваем с пригодностью близлежащих точек, затем осуществляем движение точки в направлении точки с наилучшей пригодностью. Траектория движения точки зависит от информации, полученной на предыдущих итерациях.

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

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

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

Символьная запись:

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

2. префиксная (используется сначала символ операции, затем символьный аргумент);

3. постфиксная (используется сначала аргумент, затем операция);

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

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

Но генетическое программирование имеет и свои значительные минусы.

Недостатки генетического программирования:

1. требуется анализатор на стадиях преобразования для расшифровки символов при выполнении вычисления с помощью строки символов;

2. число входящих переменных должно равняться числу листьев на дереве;

3. необходимо определять подстроки символов при выполнении операции скрещивания;

4. операция скрещивания может варьировать формулу;

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

Пример 1:

Рис. 3 Функция 1, представленная в древовидной форме.

Операция	Символ	Число аргументов
+	+	2
	*	2
	#	1
	^	1
exp	-	1
y=x	@	1
x	X	0
y	Y	0
z	Z	0

Рис. 4 Функция 2, представленная в древовидной форме.

Произведем скрещивание первой записи и второй.

Рис. 5 Оператор скрещивания для древовидного представления программ.

1.

2.

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

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

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

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

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

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

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

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

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

Сетевой оператор [8] - структура данных, которая позволяет представить математическое выражение в форме графа.

Также сетевой оператор - ориентированный граф, который обладает следующими свойствами:

1. граф не имеет циклов;

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

3. каждый узел графа, который не является стоком, имеет путь до какого - либо узла - стока;

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

5. каждая дуга графа соответствует какой - либо унарной операции ;

6. каждый узел - источник графа связан с каким - либо элементом из множества параметров или переменных.

Для четкого понятия сетевого оператора, напишем ряд необходимых определений:

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

Множество параметров - это упорядоченное множество чисел, не меняющихся в процессе вычислений.

Множество унарных операций - это упорядоченное множество функций, заданных на числовом множестве.

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

Любой сетевой оператор соответствует какому - либо математическому выражению. , где - множество чисел, - множество пар чисел.



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

Пример 2: , где - параметры, - переменные, - унарная операция, - бинарные операции. Таким образом, введем множество параметров , множество переменных , множество унарных операций , множество бинарных операций . Причем берем такие операции, которые

1. коммутативны

2. ассоциативны

3. операции должны иметь единичный элемент .

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

Правила вычисления по сетевому оператору:

1. Вычисления начинаются с дуги, выходящей из узла, в который не входит никакая другая дуга;

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

3. Исключается узел и дуга. Найденный узел исключается, если этот узел не является узлом - стоком, не имеет ни одной выходящей дуги. Дугу исключаем во всех случаях, если операция, которая соответствует данной дуге, выполнена.

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

Пример 3:



Пример 4:

Запишем множество параметров , множество переменных , множество унарных операций , множество бинарных операций .

Построение математического выражения в виде сетевого оператора:

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

Пример 5:

Пример 6:

Пример 7:

2. Графическая запись - программная запись, которая отвечает следующим свойствам:

а) внешняя операция бинарная;

б) аргументами бинарной операции могут быть только унарные операции;

в) аргументами унарной операции могут быть либо бинарная операция, либо параметр; (либо )

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

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

Пример 8:

Правило построения графа по графической записи:

Номер унарной операции соответствует дуге, а бинарной операции - узлу.

1.

2.

3.

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

Пример 9:

Граф для графической записи является сетевым оператором.

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

Сетевой оператор [8, 28] представляет собой ориентированный граф без циклов, поэтому его структуру можно описать с помощью матрицы смежности верхнего треугольного вида. Утверждение: матрица смежности любого ориентированного графа без циклов с помощью изменения номеров узлов всегда может быть представлена в верхнем треугольном виде. Матрица сетевого оператора - это целочисленная матрица, на диагонали которой расположены номера бинарных операций , а остальные элементы либо нули, либо номера унарных операций , причем при замене диагональных элементов на нули, а ненулевых недиагональных элементов на единицы получаем матрицу смежности графа сети. Чтобы представить граф в памяти компьютера используется матрица смежности (показывает какой узел, с каким узлом соединяется), которая состоит из 1 и 0, имеет размерность , где - число узлов в графе. 1 находится на пересечении - строки и - столбцы, где - номер узла, откуда выходит дуга, а - номер узла, куда входит дуга. Для графической записи желательно пронумеровать узлы так, чтобы номер узла от дуги выходит, был меньше, куда дуга входит. Для ориентированного графа без циклов это всегда можно сделать. Матрица сетевого оператора имеет ту же структуру, что и матрица смежности, только вместо единиц стоят номера унарных операций , а на диагоналях стоят номера бинарных операций .

Пример 10:



Для более четкого представления и вычисления формулы по матрице сетевого оператора используем следующий алгоритм: Шаг 0. Задана матрица сетевого оператора в верхнем треугольном виде , , если , , Определены векторы номеров узлов входных переменных , параметров и вектор номеров узлов выходных переменных

Шаг 1. Задаем начальные значения вектора узлов

, ,

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

Шаг 2. .

Шаг 3. .

Шаг 4. Если , то .

Шаг 5. . Если , то переходим на шаг 4.

Шаг 6. . Если , то переходим на шаг 3, иначе завершаем вычисления.

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

Вариация сетевого оператора [8] - это такое изменение сетевого оператора, которое приводит к однотипному сетевому оператору. Верхний треугольный вид матрицы сетевого оператора вычисляется по шагам сетевого оператора. Он проходит строки матрицы и вычисляет их с помощью унарных операций , у которых ненулевые недиагональными элементы в строке, и бинарные операции , где номера являются диагональными элементами, расположенные в столбцах с ненулевыми недиагональными элементами. Вектор узлов , с помощью которого можно легко совершать вычисления и хранить результаты, где - количество узлов сетевого оператора. Для первого шага вычислений необходимо задать начальные значения вектора узлов. Векторы аргументов определяют номера узлов источников сетевого оператора. Если в бинарной операции имеется сложение, то единицей для данной операции является ноль, а, если умножение, то единица. Начальное значение вектора узлов , последовательно проходим в матрице сетевого оператора все строки по столбцам. Если встречаем в строке в столбце не нулевой элемент, то выполняем сначала унарную операцию , номер которой определяем по элементу матрицы сетевого оператора, над значением элемента вектора узлов. Затем над результатом вычислений выполняем бинарную операцию , номер которой определяем по элементу матрицы сетевого оператора, причем первым аргументом бинарной операции является последнее значение элемента вектора узлов. Результат вычислений присваиваем элементу вектора узлов. Рассмотрим операции по шагам, которые необходимо выполнить при каждой вариации. Для некоторых вариаций необходимо выполнить проверку ее допустимости. Вариация выполняется, если она допустима. При выполнении вариаций необходимо выполнить следующие действия:

Шаг 0. Определяем дугу и меняем номер унарной операции, с которой связана дуга, .

Шаг 1. Определяем узел и меняем номер бинарной операции, с которой связан узел, , если .

Шаг 2. Определяем два узла и добавляем дугу между ними вместе с унарной операцией .

Шаг 3. Определяем дугу , проверяем, если в узел входит еще одна дуга, , то удаляем дугу , , .

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

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

Шаг 6. Добавляем еще один узел с бинарной операцией и дугу с унарной операцией . Шаг 7. Удаляем последний узел , , с входящей в него дугой . Задаем унарные и бинарные операции:

0 - единица для сложения, 1 - единица для умножения, Пример 11:

- матрица смежности,

- матрица сетевого оператора.

- матрица сетевого оператора, - вектор узлов.

Строка 1:

Строка 2:

Строка 3:

Строка 4:

- базисное решение.

Вариации сетевого оператора:

0 - изменение унарной операции, связанной с дугой сетевого оператора; 1 - добавление дуги вместе с унарной операцией; 2 - изменение бинарной операции, связанной с узлом сетевого оператора; 3 - удаление дуги, если узел, куда дуга входит, имеет еще и входящую дугу; 4 - увеличение номеров узлов; 5 - уменьшение номеров узлов; 6 - добавление узла с бинарной операцией и входящей в узел дуги, связанной с унарной операцией; 7 - удаление узла вместе с входящей в него дугой, если узел является узлом - стоком и в него входит только одна дуга.

Рассмотрим пример 11 далее:

Строка 1:

Строка 2:

,

Строка 3:

Строка 4:

Находим вариацию для данного примера, где - вектор вариации, - номер вариации; - номер строки; - номер столбца; - номер операции, - длина вариации.

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

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

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

Рис. 6 Комната с препятствиями (пример)

Координаты терминальных точек (целей):

Расположение управления:

Далее приведена небольшая часть экспертной системы:

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

Таким образом, если робот находится в точке (0,1) и движется к цели №3, то он выбирает путь движения (управление) 2, исходя из выхода экспертной системы. Либо, если робот находится в точке (5,14) и движется к цели №2, то он выбирает путь движения (управление) 1.

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

Часть программного кода, разработанного в среде Delphi 6, представлена в приложении А.

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

Эксперимент проводится на программном комплексе для аппроксимации логического вывода экспертной системы в среде Delphi 6.



Рис. 7 Главное меню программы

Главное меню содержит следующие разделы:

1) Раздел Initial data:

a. Parameters of initial data - ввод количества входов, выходов, а так же количества точек.

b. Initial data - отображение введённой части экспертной системы. В этом окне можно загрузить экспертную систему из файла, сохранить её в файл, а так же изменять введённую экспертную систему.

2) Раздел Load ExpSys - загрузка полной экспертной системы (для проверки)

3) Раздел Network operator:

a. Parameters of Network Operator Matrix - ввод параметров матрицы сетевого оператора.

b. Network operator - матрица сетевого оператора. Её можно загрузить или сохранить, а так же изменять в этом окне.

4) Раздел Genetic algorithm:

a. Create object - Parameters of object for GA with NOM - Создание объекта для генетического алгоритма (ввод количества хромосом в популяции, количества функционалов и количества вариаций в одной хромосоме).

b. Parameters of GA - Genetic algorithm with network operator - Ввод параметров генетического алгоритма.

c. Search of Pareto Set - поиск множества Парето

5) Раздел Solution:

a. Show - просмотр полученных выражений

b. Print to file - запись полученных выражений в файл

c. Clear - очистить окно

6) Раздел The set of Pareto:

a. Pareto set - множество Парето

7) Раздел Simulation:

a. Simulation after the teaching - Показывает полученные графики (совпадение точек, полученных с помощью выведенной формулы с точками из взятой нами полной экспертной системы). Так же в этом окне производится расчет выходного значения по заданным входам и цели.

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

Проводим эксперимент, используя часть составленной нами экспертной системы. Для поиска решений используем генетический алгоритм с параметрами, приведёнными в Таблице № 1 и программу из Приложения A для аппроксимации логического вывода экспертной системы методом сетевого оператора.

Таблица 1

Параметры генетического алгоритма

Параметр	Значение
Размер начальной популяции хромосом или возможных решений	512
Число поколений	512
Число пар в одном поколении	128
Число изменений в одной хромосоме	8
Число функционалов	2
Число искомых параметров	3
Число поколений в одной эпохе между сменой базисного решения	10
Число элитарных хромосом	32
Параметр для скрещивания	0.4
Вероятность мутации	0.7
Размер матрицы сетевого оператора	32
Число переменных	3
Число выходных параметров	2

Рис. 8 Базисная матрица сетевого оператора.

Для решения используем множество унарных и бинарных операций из Приложения Б.

z_0=x_0

z_1=x_1

z_2=x_2

z_3=And2(2,z_0)

z_4=And2(2,z_1,z_0)

z_5=And2(2,z_2,not z_1,z_0)

z_6=Equ2(0,z_5,z_4,z_3)

z_7=Xor2(0,z_5,z_4,z_3)

z_8=Or2(0,z_7,z_6)

z_9=Or2(0,z_8)

z_10=And2(2,z_9)

z_11=Xor2(0,z_10)

z_12=Or2(0,z_11)

z_13=Or2(0,z_12)

z_14=Or2(0,z_13)

z_15=Or2(0,z_14,not z_12)

z_16=Or2(0,z_15)

z_17=Or2(0,z_16)

z_18=Or2(0,z_17,z_2)

z_19=Or2(0,z_18)

z_20=Or2(0,z_19)

z_21=Or2(0,z_20,not z_18)

z_22=Or2(0,z_21)

z_23=Or2(0,z_22)

z_24=Or2(0,z_23,not z_18)

z_25=Or2(0,not z_24)

z_26=Or2(0,z_25)

z_27=Or2(0,z_26,not z_3)

z_28=Xor2(0,z_27)

z_29=And2(2,z_28,not z_22)

z_30=Or2(0,z_29)

z_31=Or2(0,z_30)

Исследование 1:

Рассмотрим область Парето:

Рис. 9 Множество Парето

Условное множество Парето

№	Кол-во решений	F_0	F_1
0	0	85	110
1	46	85	110
2	53	85	110
3	71	85	110

По значению F_0 видно, что из 299 введённых точек экспертной системы, мы смогли обучить робота только на 214 точек (299-85=214). Значение F_1 показывает сумму, на которую отличается требуемое и полученное управления.

Результаты моделирования представлены на рис. 10, 11 (Остальные графики моделирования представлены в приложении Г).

Рис. 10 Результат сравнения работы полученной функции с выходами экспертной системы

Рис. 11 Результат сравнения работы полученной функции с выходами экспертной системы

Из полученных графиков мы можем сделать вывод, о количестве совпавших точек:

Взяли выборку из 100 случайных точек: , и получили 73% совпадений, учитывая то, что введённая часть экспертной системы даёт только совпадений. Следовательно, полученная нами функция даёт достаточно хороший результат и может уже сейчас заменить собой данную экспертную систему.

Исследование 2:

Для получения более точного результата алгоритм был запущен ещё несколько раз.

Рассматриваем область Парето:

Рис. 12 Множество Парето

Таблица 2

Условное множество Парето

№	Кол-во решений	F_0	F_1
0	0	72	93
1	1	72	93
…	…	…	…
96	230	72	93
…	…	…	…
213	511	72	93

В таблице 2 приведены номера возможных решений во множестве. В условном множестве Парето 512 точек.

По значению F_0 видно, что из 299 введённых точек экспертной системы, мы смогли обучить робота только на 227 точек (299-72=227). Значение F_1 показывает сумму, на которую отличается требуемое и полученное управления.

Базисное решение, записанное с помощью матрицы сетевого оператора размерностью , имеет вид :

0 4 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0

0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 3 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0