Инженерия знаний

Федеральное агентство связи Федеральное государственное бюджетное образовательное учреждение высшего образования «Поволжский государственный университет телекоммуникаций и информатики» Кафедра Экономических и информационных систем Конспект лекций по дисциплине Инженерия знаний для студентов 2 и 2у курсов заочной и дистанционной форм обучения по направлению подготовки 09.03.01 «Информатика и вычислительная техника» Самара 2015 1 Содержание Введение…………………………………………………………………… 1. Основные понятия Инженерии знаний……………………………… 2. Экспертные системы………………………………………………….. 2.1 Понятие, назначение, структура……………………………………. 2.2 База знаний и модели представления знаний……………………… 2.2.1 База знаний……………………………………………………….. 2.2.2 Модели представления знаний………………………………….. 3. Технология проектирования и разработки ЭС……………………… 3.1 Участник процесса проектирования……………………………….. 3.2 Этапы разработки ЭС………………………………………………. 4. Методы извлечения, приобретения и формирования знаний ……… 4.1 Описание методов извлечения знаний……………………………... 4.2 Теоретико -методические аспекты извлечения и структурирования знаний………………………………………………… 4.3 Классификация методов извлечения знаний………………………. 5. Искусственные нейронные сети……………………………………... 5.1 Биологические нейронные сети…………………………………….. 5.2 Модель искусственного нейрона (персептрон)……………………. 5.3 Классификация нейронных сетей…………………………………... 5.4 Функции активации в нейронных сетях…………………………… 5.5 Парадигмы обучения нейронных сетей. Алгоритмы обучения нейронных сетей………………………………………………………….. 5.5.1 Парадигмы обучения нейронных сетей………………………… 5.5.2 Алгоритм обратного распространения ошибки……………….. 5.5.3 Обучение без учителя. Алгоритм Хебба………………………... 6. Генетические алгоритмы……………………………………………... 6.1 Вводные понятия…………………………………………………….. 6.2 Этапы разработки генетического алгоритма ………………………. 6.2.1 Кодирование фенотипов в хромосомы …………………………. 6.2.2 Генерация начальной выборочной популяции ………………… 6.2.3 Функция приспособленности……………………………………. 6.2.4 Селекция хромосом………………………………………………. 6.2.5 Операции репродукции (применение генетических алгоритмов)……………………………………………………………….. 6.2.6 Формирование новой популяции……………………………….. 7. Гибридные системы…………………………………………………... 7.1 Классификация гибридных интеллектуальных систем…………… 7.2 Программные средства реализации ГиИС………………………… 3 5 8 8 11 11 12 32 32 32 36 36 38 41 45 45 47 48 51 55 55 56 57 58 58 60 62 64 65 67 70 74 75 76 81 2 Введение Инженерия знаний - научная дисциплина, связанная с разработкой систем, основанных на знаниях - интеллектуальных систем. Она изучает методы и средства извлечения, представления, структурирования , формализации и использования знаний. Человек в свое практической деятельности постоянно вынужден принимать решения, причем эти решения и соответствующие им действия должны быть правильными, т.е. приводить к желаемому результату. В основе решений, принимаемых человеком, всегда лежат его опыт и знание. Во второй половине ХХ века были предприняты небезуспешные попытки создания систем искусственного интеллекта. Такие системы должны не только уметь обрабатывать комбинации количественной и качественной информации, но и каким-либо образом формализовать знания человека об окружающем мире либо свойственные человеку приемы мышления, посредством которых он изучает окружающий мир и подчиняет его своим интересам. Интеллектуализация систем поддержки принятия решений началась с математической логики и ее приложений, которые позволили анализировать достаточно сложные ситуации при помощи простейших характеристик – «да» и «нет». Позднее появились нечеткие множества и нечеткая логика, позволившие существенно расширить семантику (смысл) качественных характеристик. Были созданы различные системы моделирования знаний, на их основе разработаны базы знаний и механизмы принятия решений, например, в виде правил «если ситуация такая-то действия должны быть такими». Это, в конечном счете, привело к созданию экспертных систем, имитирующих действия и решения наиболее квалифицированных специалистов – экспертов. В основе экспертных систем лежат знания, получаемые от экспертов, отсюда их синоним – когнитивные системы (лат. cognition – познание) или системы, основанные на знаниях. 3 Существует другой подход к созданию систем искусственного интеллекта, называемый структурным, к которому относят ся искусственные нейронные сети. Таким сети имитируют деятельность человеческого мозга, образуя совокупность заимствованных из нейрофизиологии моделей параллельных вычислительных структур. Третье направление реализуется в рамках эволюционных методов, к которым можно отнести генетические алгоритмы. В основу эволюционных методов легло заложенное самой природой свойство живых организмов осуществлять правильный выбор, в частности, на основе эволюционного отбора. Генетические алгоритмы являются мощным универсальным средством решения задач глобальной оптимизации, с помощью которого выбираются решения, если не оптимальные, то достаточно близкие к ним. Отдельное направление составляют системы, которые для решения задач используют сочетания различных методов искусств енного интеллекта: экспертных систем, искусственных нейронных сетей, генетических алгоритмов и нечеткой математики. Такие сочетания получили название гибридных методов искусственного интеллекта. Инженерия знаний как научная дисциплина включает в круг изуче ния собственно научные, технологические и методологические вопросы создания программных систем, основанных на знаниях. 4 1. Основные понятия Инженерии знаний При изучении систем, основанных на знаниях, традиционно возникает вопрос — что же такое знания и чем они отличаются от обычных данных, десятилетиями обрабатываемых ЭВМ. Данные представляют собой элементарные описания предметов, событий, действий, которые классифицированы и сохранены, но не организованы для передачи какого -либо специального смысла. Данные – это конкретные факты, такие как температура воздуха, высота здания, фамилия сотрудника, адрес сайта и т.д. Элементы данных могут быть числовыми, алфавитно-числовыми, цифровыми, звуковыми или образными. Информация – это данные, которые организованы так, ч то они имеют значение и ценность для получателя. Любая компьютерная информационная система, реализующая информационный процесс, выполняет следующие функции: воспринимает вводимые пользователем информационные запросы (цели решения задачи) и необходимые исхо дные данные, обрабатывает введенные и хранимые в системе данные в соответствии с известным алгоритмом и формирует требуемую выходную информацию. С точки зрения реализации перечисленных функций информационную систему можно рассматривать как фабрику, произво дящую информацию, в которой заказом является информационный запрос, сырьем – исходные данные, продуктом – требуемая информация, а инструментом (оборудованием) – знание, с помощью которого данные преобразуются в информацию. Знания состоят из данных или информации, которые организованы и обработаны с целью передачи понимания, накопленного профессионального опыта, практической деятельности, результатов обучения и экспертизы таким образом, что они могут использоваться для решения текущих проблем или выполнения действий. По степени обобщенности описания знания можно разделить на: 5 Поверхностные – знания о видимых взаимосвязях между отдельными событиями и фактами в предметной области. Глубинные – абстракции, аналогии, схемы, отображающие структуру и природу процессов, протекающих в предметной области. Эти знания объясняют явления и могут использоваться для прогнозирования поведения объектов. Пример. Поверхностные знания: если ввести правильный пароль – на экране компьютера появится изображение рабочего стола. Глубинные знания: понимание принципов работы операционной системы и знания на уровне квалифицированного системного администратора. Современные системы работают, в основном, с поверхностными знаниями. Это связано с тем, что на данный момент нет универсальных методик, позволяющих выявить глубинные структуры знаний и работать с ними. По степени отражения явлений знания делятся на: Жесткие – позволяют получить четкие однозначные рекомендации при задании начальных условий. Мягкие – допускают множественные расплывчатые решения и многовариантные рекомендации. Представление знаний Представление знаний является одной из наиболее важных проблем при создании системы искусственного интеллекта (СИИ). Форма представления знаний оказывает существенное влияние на характеристики и свойства системы. Представление знаний - это соглашение о том, как описывать реальный мир. Основная цель представления знаний - строить математические модели реального мира и его частей, для которых соответствие между системой 6 понятий проблемного знания может быть установлено на основе совпадения имен переменных модели и имен понятий без предварительных пояснений и установления дополнительных неформальных соответствий. 7 2. Экспертные системы 2.1 Понятие, назначение, структура Экспертные системы – это интеллектуальные системы моделирования знаний, имитирующих действия и решения квалифицированных специалистов – экспертов. Экспертная система (ЭС) – программно-техническая система, в которой представлены знания специалистов в некой конкретной узко специализированной предметной области и которая в рамках этой области способна принимать решения (решать задачи) на уровне экперта- профессионала. Экспертная система моделирует не столько физическую (или иную) природу определенной проблемной или предметной области, сколько механизм мышления человека применительно к решению задач в этой области. Это существенно отличает ЭС от систем математического моделирования. Технология построения ЭС базируется на непосредственном контакте эксперта с инженером по знаниям с целью передачи информации для разработки системы. Эксперт может необходимой передавать информацию на своем языке, отличном от языка представления знаний в машине. Инженер по знаниям «извлекает» информацию из слов или иных действий эксперта и встраивает ее в систему, перево дя на соответствующий язык представления знаний. Этот процесс можно изобразить следующей схемой (рис.1). 8 Рис.1 – Структурная схема процесса извлечения знаний от эксперта Любая ЭС включает обязательные, основные компоненты, ст руктурная схема которых показана на рис. 2. Рис.2 – Структурная схема основных компонентов ЭС Очевидно, что для ввода знаний на этапе создания ЭС, их обновления и дополнения в процессе эксплуатации ЭС инженеру по знаниям необходим специальный интерфейс, который называется интерфейсом обучения ЭС. Следует обратить внимание на то, что входом интерфейса обучения может являться не только информация от инженера по знаниям, но и 9 непосредственно статистические данные о предметной области, хранящиеся в базе данных системы. Знания в системе представлены, как правило, на некотором специальном языке, соответствующем той или иной модели представления знаний. Этот компонент ЭС принято называть базой знаний. Блок обучения предназначен для заполнения базы знаний на этапе ее проектирования и эксплуатации. Его основная задача – формализация знаний, полученных от эксперта, в соответствии с выбранной проектировщиком (инженером по знаниям) моделью знаний. В состав ЭС входит интерфейс пользователя, отличный от интерфейса обучения. Пользователь не обязан владеть принятым в системе языком представления знаний, поэтому он формулирует свои вопросы и получает ответы на языке, максимально приближенном к естественному языку. Отсюда возникает необходимость в ыделения в интерфейсе пользователя интерпретатора запросов. Интерпретатор запросов производит редактирование обращения пользователя и формирует на его основе задачу для системы. В интерпретаторе предусмотрены средства устранения неопределенности запросов, а также производятся синтаксический и семантический анализы запросов. Механизм вывода предназначен для формирования новых понятий, т.е. решений в рамках определенной предметной области. Как правило, механизм вывода тесно связан с конкретной моделью знаний и оперирует терминологией этой модели. Существуют общие понятия для всех моделей знаний: стратегия вывода, управляющая структура. В ЭС применяется стратегия вывода в виде прямой или (и) обратной цепочек рассуждения. Прямая стратегия ведет от фактов к гипот езам, а обратная пытается найти данные для доказательства или опровержения гипотезы. В современных ЭС применяются комбинированные стратегии, которые на одних этапах используют прямую, а на других – обратную цепочки рассуждения. 10 Управляющая структура – это способ применения или активизации правил в процесс формирования решений. Управляющая структура полностью зависит от выбранной проектировщиком модели. Блок оценки решений и объяснения результатов (блок объяснений) служит для объяснения полученного решения, доказательства его обоснованности. Подсистема объяснений в ЭС обосновывает, аргументирует ответ в максимально естественной форме. Объясняется, как получено решение, как использована некоторая информация (факты, правила), почему не использована некоторая ин формация (факты, правила). 2.2 База знаний и модели представления знаний 2.2.1 База знаний База знаний (БЗ) – часть системы, основанной на знаниях или экспертной системы, содержащая предметные знания, отображенные той или иной формальной моделью. Базы знаний являются логическим развитием баз данных. Необходимо подчеркнуть, что база знаний не отвергает и не заменяет базы данных, база данных и база знаний рассматриваются как разные уровни представления информации в интеллектуальной системе (рис. 3). Рис. 3 – Структура системы баз знаний 11 Интенсиональные знания описывают абстрактные объекты, события, отношения, например, такие как ПОСТАВЩИК, ПОТРЕБИТЕЛЬ, ТРАНСПОРТ. Экстенсиональные знания представляют собой данные, характеризующие конкретные объекты, их состояния, значения параметров в определенные моменты времени. ПОСТАВЩИК может быть ЗАВОД Так, экстенсионалом А, понятия понятия ПОТРЕБИТЕЛЬ – ТОРГОВОЕ ПРЕДПРИЯТИЕ В, понятия ТРАНСПОРТ – АВТОМОБИЛЬ С ГРУЗОПОДЪЕМНОСТЬЮ С. 2.2.2 Модели представления знаний Модели представления знаний можно подразделить на декларативные и процедурные. В более тонком разбиении выделяют еще один класс специальных моделей, характеризующихся сочетанием декларативности и процедурности. Декларативные модели предполагают представление знаний как некоторой совокупности общезначимых утверждений. Декларативные модели (факты) – это знания вида «А есть…» Декларативные знания могут (при необходимости) подразделяться с точки зрения семантики на факты и эвристики. Факты, как правило, указывают на устоявшиеся в рамках предметной области обстоятельства, а эвристики основываются на интуиции и опыте экспертов предметной области. Декларативные знания подразделяются на объекты, классы объектов и отношения. Объект – это факт, который задается своим значением. Класс объектов – это имя, под которым объединяется конкретная совокупность объектов-фактов. Отношения определяют связи между классами объектов и отдельными объектами, возникшие в рамках предметной области. В процедурных моделях знания представляются в виде совокупности процедур над состояниями предметной области. Процедурные модели – это знания вида «Если А, то процедура или действие». 12 К процедурным знаниям относятся совокупности правил, которые показывают, как вывести н овые отличительные особенности классов или отношения для объектов. В правилах используются все виды декларативных знаний, а также логические связки. Помимо собственно знаний БЗ должна содержать так называемые метазнания. Метазнания могут задавать способы использования знаний, свойства знаний и т.д., т.е. процедуры, необходимые для управления логическим выводом и обучением системы. Кроме того, являются средством разрешения конфликта между имеющимися знаниями и входной информацией. Методы (модели) представления знаний – совокупность взаимосвязанных средств формального описания знаний и оперирования (манипулирования) этими описаниями. Выделяют следующие виды моделей: 1) Логические модели 2) Процедурные правила 3) Нечеткие модели 4) Семантические сети 5) Фреймы Логические модели Объектами изучения математической логики являются высказывания и предикаты. Оба эти объекта – повествовательные предложения, различие между ними в том, что предикат содержит так называемые предметные переменные, определенные на соответствующих множествах, при присвоении которым конкретных значений их этих множеств предикат обращается в высказывание. Таким образом, высказывание является частным случаем предиката. В математической логике исследуются способы (правила) формального представления высказываний и предикатов, построение новых высказываний и предикатов из имеющихся с помощью логически правильных 13 преобразований. А также способы установления истинности или ложности высказываний и предикатов (логический вывод или доказательство). Предикатом или логической функцией называется функция от любого числа аргументов, принимающая истинные значения 0 и 1. Обозначение предиката, содержащего предиката): P( x1 , x2 ,..., xn ) , при n переменных ( n -местного этом предполагается, что x1 ∈ M1; x2 ∈ M 2 ;...; xn ∈ M n . В качестве примера рассмотрим три высказывания: А – «рубль – валюта России»; В – «доллар – валюта России»; С – «доллар – валюта США». Высказывания А и С истинны, В – ложно. Если вместо конкретных наименований валюты в выражениях А, В подставить предметную переменную x и определить ее на множестве наименований денежных единиц x ∈ {рубль, доллар, фунт стерлингов ,..., марка}, то получим одноместный предикат P(x) - « x - валюта России». Если в выражениях А, В и С вместо конкретных наименований валюты и государства подставить соответственно переменные x и y, где y ∈ {Россия , США, Англия,..., Германия }, получим двухместный предикат P( x, y ) - « x - валюта y ». Предикаты могут объединяться в разнообразные логические формулы с помощью логических связок и скобок. Такие формулы называются предикатными формулами . Логические связки Отрицание (логическое НЕ) или инверсия (обозначение ¬ ) есть унарная операция, значение которой есть отрицание значения операнда. Конъюнкция (обозначение ∧ ) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F = F1 ∧ F2 , описывающую сложное высказывание. На естественном языке эта операция 14 выражается соединительными словами: «…и…», «…также…», «как…, так…», «…несмотря на…» и т.п. Дизъюнкция (обозначение ∨ ) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F = F1 ∨ F2 , описывающую сложное высказывание. На естественном языке эта операция выражается разъединительными словами: «…или…», «…либо…» и т.п. Импликация (обозначение → ) есть двухместная операция, посредством которой из формул F1 и F2 получают формулу F = F1 → F2 , отражающую сложное высказывание. Импликация играет особую роль в математической логике, так как многие доказательства представляются в условной форме: «если…, то…». На естественном языке эта операция выражается словами «если…, то…», «тогда…, когда…», « постольку…, поскольку…», «при наличии…, следует…», «…есть достаточное условие для…» и т.п. Эквивалентность (обозначается ↔) есть двухместная операция, посредством которой из двух формул F1 и F2 получают новую формулу F = F1 ↔ F2 , описывающую сложное высказывание. На естественном языке это выражается словами «для того, чтобы…», «необходимо и достаточно…», «…лишь при условии…» и т.п. Из предикатов можно образовывать составные предикат ы – формулы логики предикатов. Важную роль в логическом представлении систем, процессов и явлений с использованием предикатов играют операторы логики предикатов: квантор общности ∀ и квантор существования ∃ . Суждение, в котором утверждается или отрицается наличие каких-либо признаков или отношений у части предметных переменных области определения, называют частным суждением. Как правило, эти суждения на естественном языке отражают словами «один», «несколько», «час ть» и т.п. Для формализации таких суждений используют логическую операцию, ограничивающую область определения предиката. Этот оператор получил название квантор существования, который обозначается ∃x . Предикат 15 записывается после квантора существования в круглых скобках ∃x ( P( x )) . На естественном языке эта запись означает «существуют такие элементы x , что Pn (x) истинно (или ложно)». Суждение, в котором утверждается или отрицается налич ие каких-либо признаков или отношений для всех предметных переменных области определения, называют общими суждениями. Как правило, эти суждения в естественном языке отмечают словами «все», «каждый», «любой» и т.п. Для формализации этих суждений используют логическую операцию над всей областью определения предиката. Оператор этой логической операции получил название квантора общности, который обозначается: ∀ x . Предикат записывается после квантора общности в круглых скобках ∀ x ( Pn ( x)) . На естественном языке эта формальная запись означает «для всех x истинно (или ложно) значение Pn (x) . Логический вывод на основе исчисления предикатов Основные формы логического вывода. Индукция (лат. навед ение) - это форма мышления, посредством которой мысль наводится на какое -либо общее правило, общее положение, присущее всем единичным предметам какого -либо класса. Индуктивный логический вывод является перспективным направлением инженерии знаний, здесь не рассматривается. Выводы по индукции позволяют на основе обобщения частных фактов получить общие закономерности. В процессе индуктивного обучения формируются новые правила, теории и структуры. Индуктивный вывод (от частного к общему) – вывод на основе множества частных утверждений общих утверждений (из примеров реальной практики правил). В отличие от дедуктивных выводов, где диапазон порождаемых представлений не может быть шире диапазона, заданного априори, в 16 процессе индуктивного вывода диапазон представления шире, чем диапазон, заданный изначально. Дедукция (лат. выведение) – такая форма мышления, когда новая мысль выводится чисто логическим путем (т.е. по законам логики) из предшествующих мыслей. Такая последовательность мыслей называется выводами, а каждый компонент этого вывода является либо ранее доказанной мыслью, либо аксиомой, либо гипотезой. Последняя мысль данного вывода называется заключением. Дедуктивный вывод (от общего к частному) – вывод частных утверждений путем подстановки в общие утверждения других известных частных утверждений. Различают прямую (от данных к цели) и обратную (от цели к данным) цепочки рассуждений. Дедукция обычно выполняется с помощью попытки вывести противоречие из получаемого в результате п реобразований множества аксиом. Выводом системы представления знаний на предикатах являются формулы, выводимые из аксиом с помощью правил вывода. Для организации логического вывода могут использоваться правила. Для решения конкретной задачи начальное состояние и доступные операторы действий переводятся в формулы исчисления предикатов и добавляются к множеству аксиом. Целевое состояние также выражается формулой и рассматривается как теорема, которая должна быть выведена из аксиом с помощью активного механизма вывода. Продукционная модель Продукционная модель Поста или модель, основанная на правилах, базируется на понятии формальной теории и представляет знания в виде предложений типа: ЕСЛИ (посылка), ТО (следствие) называемыми продукциями или продукционными правилами. 17 Посылки (антецедент) – некоторый исходный факт, по которому осуществляется поиск в базе знаний; Следствие (консеквент) – факт или действие, устанавливаемое при успешном исходе поиска. В экспертных системах, основанных на правилах, предметные знания представляются набором правил, которые затем проверяются на группе фактов или знаний о текущей ситуации. Когда часть правила «ЕСЛИ» удовлетворяет фактам, тогда следствие, указанное в части «ТО» выполняется. Основное отличие продукционной модели от логической в том, что здесь не используется понятие логической формулы, а вывод делается без осуществления логических операций. В классических продукционных системах БЗ представляет собой переменную часть системы, в то время как правила и интерпретатор чаще всего не меняются. Будучи реализован ы процедурно, классические продукционные модели обладают весьма привлекательным свойством модульности. Поэтому правила могут быть добавлены или удалены без возникновения неожиданных побочных эффектов. Вывод в продукционной модели можно представить в виде г рафа, начальные вершины которого соответствуют описанию исходной ситуации (исходные посылки), ребра – применение продукций, а пути из выделенной вершины в данную – возможные выводы данного слова (следствия). Организация вывода в продукционных моделях Существует два важных способа использования правил в продукционной системе: 1) прямая цепочка рассуждений, в которой реализуется стратегия «от фактов к заключению»; 2) обратная цепочка рассуждений, при которой выдвигаются гипотезы вероятностных заключений, кот орые могут быть подтверждены или опровергнуты на основании фактов, поступающих в рабочую память. 18 Помимо выбора способа поиска в пространстве состояний, необходимо определиться с методом и стратегией перебора – в глубину, в ширину, по подзадачам или альфа-бета-алгоритм. При поиске в глубину в качестве очередной подцели выбирается та, которая соответствует следующему, более детальному уровню описания задачи. При этом методе поиск ведется сначала по одной из ветви дерева решений (рис.4). При поиске в ширину проверяются вершины, находящиеся на одном уровне дерева решений (рис.4). Прямой вывод Обратный вывод Поиск в глубину Поиск в ширину Рис. 4 – Стратегии вывода Разбиение на подзадачи подразумевает выделение подзадач, решение которых рассматривается как достижение промежуточных целей на пути к 19 конечной цели. Если удается правильно понять сущность задачи и оптимально разбить ее на систему иерархически связанных целей-подцелей, то можно добиться того, что путь к ее решению в пространстве поиска будет минимален. Альфа-бета-алгоритм позволяет уменьшить пространство состояний путем удаления ветвей, не перспективных для успешного поиска. Поэтому просматриваются только те вершины, в которые можно попасть в результате следующего шага, после чего неперспективные направления исключаются. Альфа-бета-алгоритм нашел широкое применение в основном в системах, ориентированных на различные игры, например, в шахматных программах. Нечеткие модели Понятия, которыми оперирует человек в различных областях знаний, являются по своей природе слишком сложными и многоплановыми для того, чтобы использовать для их представления только традиционные, точные, хорошо определенные модели и алгоритмы. Многие понятия вследствие субъективности человеческого мышления, приблизительного характера умозаключений и лингвистического их описания оказываются нечеткими по своей природе и требуют для своего представления соответствующего аппарата. Основные понятия теории нечетких (расплывчатых) множеств Предложенная Л.Заде в 1965 г. теория нечетких множеств представляет собой формализм, предназначенный для получения данных, т.е. измерения, в расплывчатых (нечетких ситуациях). Как известно, одним из способов задания множеств является задание с помощью характеристической функции . Пусть U - так называемое универсальное множество, из элементов которого образованы остальные множества. Характеристическая функция множества A ⊆ U - это функция, значения которой указывают, является ли x ∈ U элементом множества A : ⎧1, если x ∈ A, µ A ( x) = ⎨ ⎩0, если x ∉ A. 20 Особенностью этой функции является бинарный характер ее значений: 1 или 0. Пример. Подмножество A = {2,4,5,7} множества цифр может быть задано с помощью характеристической функции следующим образом: {0 / 0; 1 / 0; 2 / 1; 3 / 0; 4 / 1; 5 / 1; 6 / 0; 7 / 1; 8 / 0; 9 / 0}, где перед разделительным знаком «/» стоит элемент x универсального множества (в примере – множество цифр), а после этого знака – значение характеристической функции µ A (x ) . Нечеткое множество – это такое множество, которое образуется путем введения обобщенного понятия принадлежности, т.е. расширения двухэлементного множества значений функции принадлежности {0,1} до отрезка [0,1]. С точки зрения характеристической функции нечеткие множества являются естественным обобщением обычных множеств, когда отказыва ются от бинарного характера этой фун кции и предполагается, что она может принимать любые значения из отрезка [0,1]. В теории нечетких множеств характеристическая функция называется функцией принадлежности, а ее значения µ A~ ( x ) - степенью принадлежности элемента x нечеткому ~ множеству A . Т.е. функцией принадлежности называется функция, которая позволяет вычислить степень принадлежности произвольного элемента универсального множества к нечеткому множеству. По определ ению 0 < µ A~ ( x ) < 1 . Степень принадлежности называют факторами или коэффициентами уверенности. Итоговые факторы уверенности получаемых решений главным образом отражают порядок достоверности результата, а не его точность, что вполне приемлемо во многих задачах. Функция принадлежности может быть представлена несколькими способами: 21 1) Таблицей определения. Она используется тогда, когда множества базовых и нечетких значений содержат несколько дискретных элементов. 2) Математическими формулами. Данное представление используется в основном, если множество базовых значений непрерывно. 3) Графическим непрерывном представлением. характере множества Также базовых используется значений. Оно при очень содержательно, легкое для понимания, но его трудно применить в автоматической обработке. Понятие нечеткой и лингвистической переменных ~ Нечеткая переменная характеризуется тройкой ( x, U , A) , где x - значение переменной, например «молодой»; U - универсальное множество, т.е. область определения x , например [0, 100]; ~ A - нечеткое множество на U , интерпретирующее значение x с помощью функции принадлежности µ A~ ( x ) . Введение понятия нечеткой переменной приобретает актуальность в связи с возможностью использования традиционных методов выбора и управления применительно к нечетким системам. Лингвистической называется переменная, значениями которой являются слова или предложения естественного или искусственного языка. Значениями лингвистической переменной могут быть и нечеткие переменные (т.е. лингвистическая переменная находится на более высоком уровне, чем нечеткая переменная). Например, «возраст» - лингвистическая переменная, если она принимает лингвистические, а не числовые значения, т.е. значения «молодой», «не молодой», «очень молодой», «не очень старый» и.т.п. (которые, в свою очередь, являются и нечеткими переменными). На математическом языке лингвистич еская переменная описывается следующим кортежем: ( X , T ( X ), U , G , M ) , 22 где X - название переменной, например «возраст»; - терм-множество T (X ) X , задаваемое перечислением значений, например, «молодой», «старый» и т.д., или (и) с помощью синтаксического правила G , порождающего термы множества X , например «не очень старый», синтаксически верно, в отличие от «очень старый не»; U - универсальное множество, например возраст от 0 до 120 лет; M - семантическое правило, интерпретирующее значения X, в соответствии с которым каждому лингвистическому значению X ставится в однозначное соответствие его смысл нечеткое подмножество интерпретируется множества M (X ) , U. следующим причем Например, M ( X ) обозначает терм нечетким «молодой» подмножеством {23 / 0,7; 24 / 0,85; 25 / 1; 26 / 0,85; 27 / 0,7}. Назначение семантического правила – связать совместимости так называемых первичных лингвистическом значении термов с (молодой, союзами старый) «и», «или», в составном частицей «не», неопределенностями «очень», «вполне», «чрезвычайно» и.т.п., которые понимаются как нелинейные операторы, преобразующие смысл соответствующих термов. Значения лингвистической переменной определяются через нечеткие множества, которые в свою очередь определены на некотором базовом наборе значений или базовой числовой шкале, имеющей размерность. Каждое значение лингвистической переменной определяется как нечеткое множество (например, нечеткое множество «молодой»). Функция принадлежности определяет субъективную степень уверенности эксперта в том, что данное конкретное значение базовой шкалы соответствует определенному нечеткому множеству. Пусть перед нами стоит задача интерпретации значений лингвистической переменной «возраст», базовый набор значений которой следующий: 23 Возраст = {младенческий, детский, юный, молодой, зрелый, преклонный, старческий} Для лингвистической переменной «возраст» базовая шкала – это числовая шкала от 0 до 120, обозначающая количество прожитых лет, а функция принадлежности определяет, насколько мы уверены в том, что данное количество лет можно отнести к данной категории возраста. На рис5. Отражено, как одни и те же значения базовой шкалы могут участвовать в определении различных нечетких множеств. Например, определить значение нечеткого множества «младенческий» можно так: 2 3 4 5 10 ⎫ ⎧ 0,5 1 " младенческий" = ⎨ + + + + + + ⎬. ⎩ 1 0,9 0,8 0,7 0,6 0,3 0,1⎭ Рис.5 - Формирование нечетких множеств Из вышесказанного можно сделать следующие выводы: 1) нечеткие множества описывают неопределенные понятия (младенческий возраст, хорошая рентабельность, высокий человек); 2) нечеткие множества допускают возможность частичной принадлежности к ним (пятница – частично выходной день (укороченный)); 3) степень принадлежности объекта к нечеткому множеству определяется соответствующим значением функции принадлежности на интервале [0,1] (пятница принадлежит к выходным дням со степенью принадлежности 0,3); 24 4) функция принадлежности ставит в соответствие объекту (или логической переменной) значение степени его принадлежности к нечеткому множеству. Семантические сети Семантика – это наука, устанавливающая отношения между символами и объектами, которые они обозначают. В семантических сетях знания, необходимые для решения задач и организации взаимодействия с пользователем представляются в виде объектов (понятий) и связей (отношений) между ними. Семантическая сеть – это ориентированный граф, вершины которого соответствуют понятиям (объектам), а дуги – отношения между ними. Пара соединенных дугою вершин представляет простой факт. Пример. «В производственном отделе работает Иванов» представлено графом, изображенным на рис.6. Рис.6 – Фрагмент семантической сети С позиции логики базовую структуру семантической сети можно рассматривать в качестве эквивалента предиката с двумя аргументами. Эти два аргумента представляются двумя вершинами, а собственно предикат – дугой. При соответствующем выборе отношений можно выразить достаточно сложные совокупности фактов. Многообразие семантических отношений условно делят на классы: лингвистические, логические, теоретико- множественные и квантифицированные. К лингвистическим относятся отношения типа: «объект – принадлежность», «объект – свойство»; «событие – кто или что его вызывает» и т.п. Логические отношения соответствуют операциям, используемым в исчислении высказываний – дизъюнкции, конъюнкции, импликации и др. 25 Теоретико -множественные отношения представляют собой подмножество, элемент множества, отношение части и целого и др. Этот класс отношений применяется для построения иерархических структур с целью представления обобщенной информации. Квантифицированные отношения – это логические кванторы общности и существования. Логические кванторы применяются для представления знаний декларативного типа, например, для записи утверждений типа «все товары должны быть проданы до конца месяца», или «существует такой товар, который должен быть реализован в течение дня». Формальная запись таких предложений опирается на исчисление предикатов. На рис. 7 показано одно из возможных представлений фактов, относящихся к служащему с фамилией Иванов. Рис.7 – Пример представления фактов с помощью семантической сети Механизм логического вывода в семантических сетях По сети можно осуществить поиск, используя знания о смысле отношений и операции: сопоставление с образцом, поиск, замена, взятие копии. Проблема поиска решения в базе знаний сводится к задаче поиска фрагмента сети, соответствующего некоторой подсети, отражающей поставленный запрос к базе. 26 Отличительной особенностью семантических сетей является сложность в разграничении базы знаний и механизма логического вывода. Также большой проблемой для семантических сетей является то, что результат вывода не гарантирует достоверности, так как вывод есть просто наследование свойств ветви is-a. Для отображения иерархических отношений между объектами и введения единой семантики в семантические сети, осуществляющих их интерпретацию, используются процедуры. Можно выделить два способа организации процедур: - способ сопоставления частей сетевой структуры; - способ перекрестного поиска. Способ сопоставления основан на построении подсети по определенному запросу и сопоставлении ее с базой данных сети. При сопоставлении с базой данных вершинам переменных подсети присваиваются гипотетические значения. При перекрестном поиске осуществляется поиск отношений между концептуальными объектами и ответ на вопрос путем обнаружения узла, в котором пересекаются дуги, идущие от двух различных узлов. Другими словами, это обнаружение третьего узла, в котором пересекаются дуги, идущие от двух других узлов. Семантические сети нашли применение в основном в системах обработки естественного языка, частично в вопросно-ответных системах, а также в системах искусственного видения. В последних семантические сети используются для хранения знаний о структуре, форме и свойствах физических объектов. Фреймы Для представления и описания стереотипных объектов, событий или ситуаций были введены понятия «фреймы», которые являются сложными структурами данных. 27 Фреймы – это минимальные структуры информации, необходимые для представления класса объектов, явления или процессов. Термин фрейм от английского frame, что означает каркас или рамка. Различают фреймы-образцы или прототипы, хранящиеся в базе знаний, и фреймы-экземпляры, которые создаются для отображения реальных фактических ситуаций на основе поступающих данных. Модель фрейма является достаточно универсальной, поскольку позволяет отобразить все многообразие знаний о мире через: - фрейм-структуры, использующиеся для обозначения объектов и понятий (заем, залог, вексель); - фрейм-роли (менеджер, кассир, клиент); - фрейм сценарии (банкротство, собрание акционеров); - фрейм-ситуации (тревога, авария, падение ставок на бирже) и др. В общем виде фрейм может быть представлен как список свойств или, более наглядно, в виде таблицы. Структура фрейма Имя фрейма Значение слота Тип значения слота Имя слота Присоединительная процедура Имя фрейма уникально в пределах фреймовой системы, служит для идентификации фрейма в системе. Имя слота – это идентификатор, присваиваемый слоту. Уникально в пределах фрейма. Число слотов в каждом фрейме устанавливается проектировщиком системы, при этом часть слотов определяется самой системой для выполнения специфических функций (системные слоты), примерами которых являются: слот -указатель родителя данного фрейма, слот -указатель дочерних фреймов, слот для ввода имени пользователя, слот для ввода даты 28 определения фрейма, слот для ввода даты изменения фрейма и т.д. Каждый слот, в свою очередь, также представлен определенной структурой данных. Тип значения слота указывает, что слот имеет значение, либо служит указателем другого фрейма (т.е. показывает имя фрейма). К типам данных относятся: указатель, целый, действительный, булевый, присоединительная процедура, текст, список, таблица, выражение и др. Значение слота. Вводится значение слота. Значение слота должно соответствовать указанному типу данных и условию наследования. Присоединительная процедура . В качестве значения слота можно использовать программу процедурного типа, называемую служебной (в языке LISP) или методом (в языках объектно-ориентированного программирования, например, в языке Smaltalk). Выделяют два вида процедур: процедуры-демоны и процедуры-слуги. Демоном называется процедура, автоматически запускаемая при выполнении некоторого условия. В основном демоны ограничиваются условием ЕСЛИ-ТОГДА. Процедуры-демоны активизируются при каждой попытке добавления или удаления данных из слотов (по умолчанию). Демоны запускаются при обращении к соответствующему слоту. Существуют НЕОБХОДИ МО, следующие типы ЕСЛИ-ИЗМЕНЕНО, процедур-демонов: ЕСЛИ- ЕСЛИ-ДОБАВЛЕНО, ЕСЛИ- УДАЛЕНО. Процедуры-слуги активизируются по сообщению, переданному из другого фрейма, или при выполнении условия, определенных пользователем при создании фрейма. В языках представления знаний фреймами отсутствует спец иальный механизм управления выводом, поэтому пользователь должен реализовать данный механизм с помощью присоединительной процедуры. Для уменьшения информационной избыточности во фреймовых системах реализуют принцип наследования информации, позволяющий 29 общую (глобальную) для системы информацию хранить в отдельном фрейме, а во всех остальных фреймах указывать лишь ссылку на место хранения этой информации, т.е. организация системы основывается на отношении «абстрактное-конкретное». Указатели наследования. Показывают, какую информацию атрибутах слотов из фрейма верхнего уровня наследуют слоты об с аналогичными именами во фрейме нижнего уровня. В конкретных системах указатели наследования могут быть организованы различными способами и иметь разные значения: - значение слота не наследуется; - значение слота наследуется; - значение слота должно находиться в пределах интервала значений, указанных в одноименном слоте родительского слота; - при отсутствии значения в текущем слоте оно наследуется из фрейма верхнего уровня. Наследование происходит по специальным АКО -связям (A-Kind-of = это) или через слот-указатель родителя данного фрейма (IS-A - ЯВЛЯЕТСЯ). IS-A Умеет Человек Млекопитающее Мыслить IS-A Возраст Рост Любит Ребенок Человек 0 – 16 лет 50 – 180 см Сладкое IS-A Учится Возраст Носит Ученик Ребенок В школе 7 – 17 лет Форму Рис.8 – Пример иерархии фреймов 30 Вывод во фреймовой системе Средствами управление выводом во фреймовой модели служат присоединительные процедуры и указатели наследования. Во фреймовых моделях могут выполняться как прямая, так и обратная аргументация, когда в прямом направлении в зависимости от состояния слотов фреймов запускаются процедуры-демоны, а обратная аргументация срабатывает путем запуска присоединительных процедур при обращении к неизвестным значениям атрибутов. Многие ЭС, основанные на фреймах для оценки информации, содержащейся во фреймах, используют множество правил. Каждое правило имеет структуру ЕСЛИ-ТОГДА и каждое правило соотносит данную информацию или факты в своей части ЕСЛИ с некоторым действием в своей части ТОГДА. Исходя из этого, нет существенных различий между правилами, используемыми в ЭС, основанных на правилах (продукционных моделях) и такими же правилами, используемым в ЭС, основанных на фреймах. Однако в системах, основанных на фреймах правила часто используют предложения, сопоставляемые с образцами. Эти предложения содержат переменные, которые используются для нахождения сопоставимых условий между всеми фреймами-экземплярами. 31 3. Технология проектирования и разработки ЭС 3.1 Участники процесса проектирования В разработке ЭС участвуют представители следующих специальностей: 1) Эксперты в проблемной области, задачи которой будет решать ЭС. Эксперт определяет знания (данные и правила), характеризующие проблемную область, обеспечивает полноту и правильность введенных в ЭС знаний. 2) Инженер по знаниям – специалист по разработке ЭС. Он помогает эксперту выявить и структурировать знания, необходимые для работы ЭС; осуществляет выбор того ИС, которое наиболее п одходит для данной проблемной области, и определяет способ представления знаний в этом ИС; выделяет и программирует стандартные функции, которые будут использоваться в правилах, вводимых экспертом. 3) Программист по разработке инструментальных средств (ИС). Он разрабатывает ИС (если ИС разрабатывается заново) и осуществляет его сопряжение с той средой, в которой оно будет использовано. Перед тем, как приступить к разработке ЭС, инженер по знаниям должен рассмотреть вопрос целесообразности разработки ЭС для данного приложения. Положительно решение принимается тогда, когда разработка ЭС возможна, оправданна и методы инженерии знаний соответствуют решаемой задаче. 3.2 Этапы разработки ЭС Традиционная технология разработки ЭС включает шесть основных этапов: идентификацию, концептуализацию, формализацию, выполнение, тестирование, опытную эксплуатацию (рис.9). 32 На этапе идентификации определяются цели разработки; задачи, подлежащие решению; определяются эксперты и типы пользователей. Результатом этого этапа является о твет на вопросы: «что нужно сделать?» и «какие ресурсы нужно использовать?» Переформулирование Идентификация проблемной области Требования Переформулирование Концептуализация проблемной области Модель Перепроектирование Формализация баз знаний Структура Уточнение Выполнение (реализация баз знаний) Правила Тестирование баз знаний Опытная эксплуатация Рис.9 – Этапы разработки экспертных систем Идентификация задач заключается в составлении неформального вербального описания решения задач (общие характеристики задач, подзадачи, ключевые понятия объекта, характеристики отношений, входные и выходные данные, предположительный вид решения, знания, необходимые для решения данных задач). На этапе концептуализации проводится содержательный анализ проблемной области, выявляются используемые понятия и их взаимосвязи, определяются методы решения задач. 33 От качества построения концептуальной модели проблемной области зависит тот факт, насколько в дальнейшем по мере развития проекта будет выполняться перепроектирование базы знаний. Хорошая концептуальная модель может только уточняться (детализироваться), но не перестраиваться. Результат концептуализации проблемной области обычно фиксируется в виде наглядных графических схем на объектном, функциональном и поведенческом уровнях моделирования: − объектная модель описывает структуру предметной области как совокупность взаимосвязанных объектов; − функциональная модель отражает действия и преобразования над объектами; − поведенческая модель рассматривает взаимодействие объектов во временном аспекте. Первые две модели описывают статические аспекты функционирования проблемной области, а третья модель – динамику изменения её состояний. На этапе формализации базы знаний осуществляется выбор метода представления знаний, в рамках которого проектиру ется логическая структура базы знаний. Методы представления знаний различаются характером представления объектного, функционального, поведенческого видов знаний и реализацией неопределенностей, т.е. ориентацией на определение структуры объектов или действи й над ними. На этапе реализации базы знаний происходит физическое наполнение базы знаний и настройка всех программных механизмов в рамках выбранного инструментального допрограммирование средства, специализированных а при необходимости модулей и программног о инструмента. На выбор инструментальных средств ЭС основное влияние оказывает класс решаемых задач (проблемных областей) и соответственно характер полученной концептуальной модели, определяющий множество требований 34 в части отображения объектов, действий над объектами, методов обработки неопределенностей, механизмов вывода. Этап тестирования оценивает экспертную систему с позиции двух основных групп критериев: точности и полезности. Точность работы: правильность заключений, адекватность базы знаний проблемной области, соответствие методов решения проблемы экспертным. Полезность: ответы на запросы пользователя; удобство интерфейса; объяснение получаемых результатов, надежность, адаптируемость, производительность и стоимость эксплуатации. Этап внедрения и опытной эксплуатации - переход от тестовых примеров к решению реальных задач. Проверяется пригодность ЭС для конечных пользователей. Процесс создания ЭС не сводится к строгой последовательности перечисленных выше этапов. В ходе разработки приходится неоднок ратно возвращаться на более ранние этапы и пересматривать принятые там решения. 35 4. Методы извлечения, приобретения и формирования знаний 4.1 Описание методов извлечения знаний Ключевым вопросом построения экспертной системы является процесс получения знаний (рис.10), когда происходит перенос компетентности экспертов на инженеров по знаниям. Рис.10 - Структурная схема процесса извлечения знаний от эксперта Знания от экспертов в определенной предметной области получают в форме: 1) набора фактов (предметные знания), например, установление отношений, в том числе нечетких (А равно или приблизительно равно В); 2) эвристических приемов (эмпирических правил), в том числе нечетких. Например, из А следует В, а из В следует С. При этом возможны два пути получения знаний: 1) непосредственное взаимодействие эксперта и инженера по знаниям, в результате которого появляется соответствующий фрагмент базы знаний; 2) автоматизированный, когда эксперт заполняет исходными (элементарными) знаниями входы соотве тствующих инструментальных 36 программ, разработанных инженерами по знаниям, на выходе которых формируются готовые фрагменты взаимосвязанных фактов и правил, помещаемых в базу знаний. Для того чтобы различать пути получения знаний в современной литературы предлагается использовать термин извлечение знаний (knowledge elicitation), как более емкий и более точно выражающий смысл процедуры переноса компетентности эксперта через инженера по знаниям в базу знаний экспертной системы, предлагается использовать при неп осредственном взаимодействии эксперта с инженером по знаниям. Термин приобретение знаний (knowledge acquisition) используется применительно к процессу наполнения базы знаний экспертом с использованием специализированных методов и программных средств. Термин формирования знаний (machine learning или более точно knowledge discovery in databases) традиционно закрепился за процессом анализа обучающих выборок и аналогий, т.е. это процесс анализа данных и выявления скрытых закономерностей с использованием специального математического аппарата и программных средств. Таким образом, три основные стратегии проведения стадии получения знаний при разработке ЭС можно представить в следующем графическом виде (рис.11) Рис.11 – Стратегии получения знаний 37 4.2 Теоретико-методические аспекты извлечения и структурирования знаний Извлечение знаний – процесс получения знаний от экспертов. Извлечение знаний – сложная и трудоемкая процедура, в результате которой инженеру по знаниям необходимо создать с обственную модель предметной области на основе информации, полученной от экспертов. Процесс извлечения знаний рассматривают в трех основных аспектах: психологическом, лингвистическом и гносеологическом. Психологический аспект Это самый важный из всех аспектов, поскольку он определяет успешность и эффективность взаимодействия инженера по знаниям с основным источником знаний – экспертом-профессионалом. Модель общения включает участников общения, средства общения и предмет общения (знания). В соответствии с этими компонентами выделяются три слоя психологических проблем: контактный, процедурный, когнитивный. Степень информативности общения инженера по знаниям и эксперта на уровне контактного слоя зависит в основном от пола, возраста, темперамента личности и мотивации участников общения. Пол и возраст Установлено, что хорошие результаты дают гетерогенный пары (мужчина/женщина), т.к. повышается мотивация. При этом соотношение возрастов: 5<(Вэ - Ва)<20, где Вэ – возраст эксперта, Ва – возраст аналитика. Личность Под личностью обычно понимается устойчивая система психологических черт, характеризующая индивидуальность человека. 38 Желательно, чтобы участники процесса общения обладали такими качествами, как доброжелательность, аналитичность, хорошая память, внимание, наблюдательность, воображение, впечатлительность, собранность, настойчивость, общительность и находчивость. Темперамент Со времен Галена и Гиппократа, выделивших четыре классических типа темперамента, вошли в научную терминологию понятия – холерик, сангвиник, меланхолик, флегматик. Наиболее успешными в рамках контактного слоя являются сангвиники и холерики. Мотивация На эффективность коллективного решения задач влияет также и мотивация, т.е. стремление к успеху. Инженер по знаниям в зависимости от условий разработки должен изыскивать разнообразные стимулы для экспертов (включая, разумеется, и материальные). Эксперт передает аналитику один из самых дорогих в мире продуктов – знания. И если одни люди делятся опытом добровольно и с удовольствием, то другие весьма неохотно приоткрывают свои профессиональные тайны. Иногда полезно, оказывается, возбудить в эксперте дух соперничества, конкуренции (не нарушая, естественно, обстановки кооперативности в коллективе). Параметры процедурного слоя обеспечиваю эффективность извлечения знаний. К этим параметрам относятся: ситуация общения (место, время, продолжительность); оборудование (вспомогательные средства, освещенность, мебель); профессиональные приемы (темп, стиль, методы и др.) Когнитивный слой (от англ. сognition – познание) связан с изучением семантического пространства памяти эксперта и с воссозданием его понятийной структуры и модели рассуждений. 39 Лингвистический аспект Актуальность исследования этого аспекта определяется тем, что язык является основным средством общения в процессе извлечения знаний. В области лингвистических проблем наиболее важными являются понятия: общий код, понятийная структура и словарь пользователя. Общим кодом называется специальный промежуточный язык общения между экспертом и инженером по зна ниям. Этот язык включает совокупность общенаучных и специальных понятий из профессиональной литературы, элементов базового языка, неологизмов и т.п . (рис.12). Бытовой язык Специальная терминология эксперта Общий код Эксперт Специальные термины из литературы Инженер по знаниям Общенаучные термины Рис.12 – Структура формирования общего кода В дальнейшем общий код преобразуется в понятийную структуру, или семантическую сеть, которая связывает понятия, хранящиеся в памяти человека. Известно, что естественные знания человека представляют собой связанные структуры, а не разрозненные фрагменты. Однако до настоящего времени при разработке БЗ учитывается весьма ограниченный набор связей между понятиями, в то время как в действительности существует большое разнообразие таких отношений. Д.А.Поспелов выделяет более 200 базовых видов отношений между понятиями. 40 Разработка словаря пользователя необходима в связи с тем, что конечный пользователь не обязан владеть профессиональным языком предметной области, который использовался при постро ении БЗ. Интерфейс пользователя создается, как правило, путем доработки словаря общего кода. Гносеологический аспект Гносеология – теория познания (греч. gnosis – познание и логия). Он научного объединяет знания, методологические так как процесс проблемы познания получения часто нового сопровождается появлением новых понятий и теорий. В процессе разработки БЗ эксперт довольно часто впервые формулируют некоторые закономерности на основе накопленного эмпирического факт→обобщенный опыта. факт→эмпирический Последовательность закон→теоретический закон называется гносеологической цепочкой. Теория – это не только система обобщения накопленных знаний, но и способ получения нового знания. 4.3 Классификация методов извлечения знаний Многообразие задач, ситуаций и источников знаний обусловило появление большого количества методов извлечения, приобретения и формирования знаний (рис.13). Коммуникативные методы В пассивных методах ведущую роль играет эксперт, в активных — инженер по знаниям. Активные методы делятся на индивидуальные и групповые. В групповых методах знания получают от множества экспертов, в индивидуальных — от одного (более широкое применение). Пассивные коммуникативные методы Метод наблюдений заключается в фиксировании всех действий эксперта, его реплик и объяснений. Инженер по знаниям не вмешивается в работу эксперта, а только наблюдает за процессом решения реальных задач либо за решением проблем, имитирующих реальные задачи. Является 41 наиболее применяемым на начальных этапах разработки экспертной системы. Извлечение знаний Коммуникативные методы Пассивные Наблюдение Протокол «мыслей вслух» Лекции Текстологические методы Активные Индивидуальные Анкетирование Анализ учебников Групповые «Мозговой штурм» Интервью Диалог Круглый стол Экспертные игры Ролевые игры Анализ литературы Анализ документов Рис.13 – Методы извлечения знаний Метод анализа протоколов «мыслей вслух» отличается от метода наблюдения тем, что эксперт не только комментирует свои действия, но и объясняет цепочку своих рассуждений, приводящих к решению. Проблемой является принципиальная сложность для любого человека словесного описания собственных мыслей и действий. Метод извлечения знаний из лекций предполагает, что эксперт передает свой опыт инженеру по знаниям в форме лекций. При этом инженер по знаниям может заранее сформулировать темы лекций, процесс передачи информации происходит в форме конспектирования лекций. Активные индивидуальные методы включают методы анкетирования, интервьюирования, свободного диалога и игры с экспертом. 42 Преимуществом методов анкетирования является то, что анкета или вопросник составляются инженером по знаниям заранее. Эксперту предлагается ответить на сформулированные вопросы. Метод интервьюирования отличается от метода анкетирования тем, что позволяет инженеру по знаниям опускать ряд вопросов в зависимости от ситуации, вставлять новые вопросы в анкету, изменять темы и разнообразить ситуацию общения. Метод свободного диалога позволяет извлекать знания в форме беседы с экспертом, поэтому здесь не предусматривается использование жесткого вопросника или плана. В то же время подготовка к свободному диалогу должна проводиться по специальной методике, в которую входит общая (овладение научной эрудицией ), специальная, конкретная и психологическая подготовка. Экспертные игры предназначены для извлечения знаний эксперта при помощи средств вычислительной техники и базируются на деловых, диагностических и компьютерных играх. Компьютерные экспертные игры в настоящее время используются в основном в целях обучения. Они полезны для «разминки» экспертов перед сеансом извлечения знаний. Игры с применением тренажеров позволяют зафиксировать трудно уловимые знания, которые возникают в реальных ситуациях и могут быть потеряны при выходе из них. Ролевые игры в группе предусматривают участие в игре нескольких специалистов. Участники игры наделяются определенными ролями, а собственно игра проводится по составленному инженером по знаниям сценарию. Текстологические методы Текстологические методы о снованы на изучении текстов учебников, специальной литературы и документов. Схема извлечения знаний представлена на рис.14. 43 М1 Эксперт или автор книги М2 Вербализация Текст книги Понимание V I Инженер по знаниям T М1 — смысл, заложенный автором и основанный на его собственной модели мира; М2 — смысл, который постигает инженер по знаниям; V — результат вер бализации; Т — словесное изложение знаний; I — интерпретация текста, изложенного словесно. Рис.14 – Схема извлечения знаний Научный текст, который формируется автором на основе модели M 1, включает пять компонентов: первичный материал наблюдений; система научных понятий; субъективный взгляд автора; дополнительная информация, не касающаяся научного знания (общие места); заимствования. На процесс понимания (интерпретации) и на модель М 2 влияют следующие компоненты: совокупность компонентов, почерпнутый из те кста; предварительные знания инженера по знаниям о предметной области; общенаучная эрудиция инженера по знаниям; его личный опыт. Схема процесса извлечения знаний из текста показывает, что смысл М 1, заложенный автором книги, отличается от смысла М2, который постигает читатель (инженер по знаниям). 44 5. Искусственные нейронные сети Теория искусственных нейронных сетей включает в себя большой спектр вопросов из разных областей науки: биофизики, информатики, математики, схемотехники и т. д. Нейронные сети - это адаптивные системы для обработки и анализа данных, которые имитирующую представляют некоторые собой аспекты математическую работы человеческого структуру, мозга и демонстрирующие такие его возможности, как способность к неформальному обучению, способность к обобщению и кластеризации неклассифицированной информации, способность самостоятельно строить прогнозы на основе уже предъявленных временных рядов. Главным их отличием от других методов, например таких, как экспертные системы, является то, что нейронные сети в принципе не нуждаются в заранее известной модели, а строят ее сами только на основе предъявляемой информации. 5.1 Биологические нейронные сети Идея построения искусственных нейронных сетей основывается на моделировании работы человеческого мозга. Нервная система и мозг человека состоят из клеток – нейронов, объединенных в биологическую нейронную сеть. Поэтому, прежде чем приступать к изучению искусственных нейронных сетей, полезно познакомиться с устройством их биологического прототипа. Элементом клеточной структуры мозга является особая биологическая клетка – нейрон. 45 Биологический нейрон содержит следующие структурные единицы (рис. 15): 1) тело клетки или сома (soma), которое содержит ядро, митохондрии (обеспечивают клетку энергией), другие органеллы, поддерживающие жизнедеятельность клетки; 2) два типа внешних древоподобных ветвей: - аксонов (axon), представляющих собой длинное, иногда больше метра выходное нервное волокно клетки. У каждой клетки может быть один или ни одного аксона. Импульс ген ерируется в аксонном холмике. Аксон обеспечивает проведение импульса и передачу воздействия на другие нейроны или мышечные волокна. Ближе к концу аксон часто ветвится; - дендритов (dendrites) – входные волокна, собирающие информацию от других нейронов. Рис. 15 – Строение биологического нейрона Синапс – место контакта нервных волокон – передает возбуждение от клетки к клетке. Передача через синапс почти всегда однонаправленная. В человеческом мозге нейроны объединяются в сети, причем можно выделить два основных слоя: сенсорный и моторный. Сенсорный слой – принимает информацию от органов чувств и передает сигналы головному и спинному мозгу. Сенсорные нейро ны представляют собой зерна или 46 гранулы. Моторный слой ответственен за формирование команд для произвольных движений мышц, передает сигналы от головного и спинного мозга к мышцам и железам. Моторный нейрон представляет собой пирамиду. 5.2 Модель искусстве нного нейрона (персептрон) Нейрон представляет собой единицу обработки информации в нейронной сети. Простая нейронная модель (персептрон), показанная на рис. 16. На вход поступает только двоичный сигнал, т.е. либо 0 либо 1. Элемент Σ умножает каждый вход xN на вес wN и суммирует взвешенные входы. Если эта сумма больше заданного порогового значения, выход равен единице, в противном случае – нулю. Рис. 16 – Модель персептрона Персептроны состоят из одного слоя (т.е. количество слоев нейронов между входом X и выходом OUT равно одному) искусственных нейронов, соединенных с помощью весовых коэффициентов с множеством входов. Модель искусственного нейрона состоит из трех основных элементов: - синапсы, каждый из которых характеризуется своим весом или силой. Осуществляют связь между нейронами, умножают входно й сигнал xi на весовой коэффициент синапса wi , характеризующий силу синапсической связи; 47 - сумматор - аналог тела клетки нейрона. Выполняет сложение внешних входных сигналов или сигналов, поступающих по синапсическим связям от других нейронов. Определяет уровень возбуждения нейрона; - функция активации определяет окончательный выходной уровень нейрона, с которым сигнал возбуждения (торможения) поступает на синапсы следующих нейронов. Функционирование нейрона определяется формулами: NET = ∑ wi xi ; i OUT = F ( NET − θ ) , где xi - входные сигналы, совокупность которых формируют вектор X; wi - весовые коэффициенты, совокупность которых образуют вектор весов W ; NET - взвешенная сумма входных сигналов, значение NET передается на нелинейный элемент; θ - пороговый уровень данного нейрона; F - нелинейная функция, называемая функцией активации. Нейрон имеет несколько входных сигналов xi и один выходной сигнал OUT . Модель нейрона имитирует в первом приближении свойства биологического нейрона. На вход искусственного нейрона поступает некоторое множество сигналов, каждый из которых является выходом других нейронов. Каждый вход умножается на соответствующий вес, пропорциональный синапсической силе, и все произведения суммируются, определяя уровень активации нейрона. 5.3 Классификация нейронных сетей Нейронная сеть представляет собой упорядоченную связи нескольких нейронов, распределенных по слоям. 48 Существует несколько видов нейронных сетей. Также существуют разные виды классификации нейронных сетей. Рассмотрим два вида классификации. Первый вид классификации (рис. 17) более общий, нейронные сети группируются согласно определенным признакам. По характеру обучения нейронные сети делятся на: - нейронные сети, использующие обучение с учителем; - нейронные сети, использующие обучение без учителя. По настройке весов нейронные сети можно разделить на: - сети с фиксированными связями – весовые коэффициенты выбираются сразу, исходя из условий задачи; - сети с динамическими связями – для них в процессе обучения происходит настройка синапсических весов. Рис. 17 – Классификация нейронных сетей по характерным признакам По типу входной информации нейронные сети делятся на: - аналоговые – входная информация представлена в форме действительных чисел; - двоичная – вся входная информация представляется в виде нулей и единиц. 49 Согласно применяемой модели нейронные сети делятся на: - сети прямого распространения – все связи направлены строго от входных нейронов к выходным. Сети являются статическими в том смысле, что на заданный вход они вырабатывают одну совокупность выходных значений, не зависящих от предыдущего состояния сети; - рекуррентные нейронные сети – сигнал с выходных нейронов или нейронов скрытого слоя частично передается обратно на входы нейронов входного слоя ; - радиально-базисные функции – вид нейронной сети, имеющий скрытый слой из радиальных элементов и выходной слой их линейных элементов; - самоорганизующиеся карты или сети Кохонена – класс сетей, обучающихся без учителя. Успешно применяется в задачах распознавания. Сети такого класса способны выявлять новизну во входных данных. Вторая классификация в основном представляет разновидности нейронных сетей в зависимости от применяемой модели (рис. 18). Рис. 18 – Классификация искусственных нейронных сетей Помимо рассмотренных ранее разновидностей сетей здесь можно выделить следующие: - соревновательные сети характеризуются тем, что в них может быть одновременно активен только один выход. При обучении таких сетей 50 выходные нейроны Соревновательные соревнуются сети часто за право применяются активизироваться. для решения задач автоматической кла ссификации (кластеризации) входных образов; - сети Хопфилда характеризуются тем, что весовые коэффициенты синапсов рассчитываются только однажды перед началом функционирования сети на основе информации об обрабатываемых данных, и все обучение сети сводится именно к этому расчету. Сеть состоит из единственного слоя нейронов, число которых является одновременно числом входов и выходов сети. Используется для организации ассоциативной памяти; - модель АРТ – сеть адаптивной резонансной теории – рекуррентная нейронная сеть с алгоритмом обучения «без учителя», включает в себя два слоя. Сущность состоит в сочетании способностей к идентификации образов новых, ранее не встречавшихся классов со способностями к стабильному распознаванию используется образов для уже решения встречавшихся задач классов. автоматической Эффективно классификации (кластеризации). 5.4 Функции активации в нейронных сетях Функция активации – функция, вычисляющая выходной сигнал искусственного нейрона. В качестве аргумента принимает сигнал Y (NET ) , получаемый на выходе входного сумматора Σ . Наиболее часто используются следующие функции активации. 1) Единичный скачок или жесткая пороговая функция (жесткая ступенька). Простая кусочно-линейная функция (рис. 19). Если входное значение меньше порогового, то значение функции активации равно минимально допустимому; иначе – максимально допустимому. 51 Работа описывается следующей формулой: ⎧0, NET < θ ; OUT = ⎨ ⎩1, NET ≥ θ . OUT θ NET Рис. 19 – График жесткой пороговой функции 2) Линейный порог или гистерезис Несложная кусочно-линейная функция (рис. 17). Имеет два линейных участка, где функция активации тождественно равна минимально допустимому значению и есть участок, на котором функция строго монотонно возрастает. Рис. 20 – График функции линейный порог 52 3) Сигмоидальная функция или сигмоид (функция Ферми) Монотонно возрастающая всюду дифференцируемая S -образная нелинейная функция с насыщением. Сигмоид позволяет усиливать слабые сигналы и не насыщаться от сильных сигналов. Примером сигмоидальной функции активации может служить логистическая функция (рис. 21), задаваемая следующим выражением: OUT = 1 , 1 + exp( −αY ) где α - параметр наклона сигмоидальной функции активации. Изменяя этот параметр, можно построить функции с различной крутизной. Рис. 21 – График логистической функции Еще одним примером сигмоидальной функции активации является гиперболический тангенс (рис. 19), задаваемый следующим выражением: e NET − e − NET ⎛Y ⎞ OUT = th⎜ ⎟ = th( NET ) = NET , e + e − NET ⎝α ⎠ где α - также параметр, влияющий на наклон сигмоидальной функции. 53 Рис. 22 – График функции гиперболического тангенса 4) SOFTMAX-функция Данная функция описывается формулой: OUT = e NET . ∑ e NETi i В данном случае суммирование ведется по всем нейронам данного слоя сети. Такой выбор обеспечивает сумму выходов слоя, равную единице при любых значениях сигнала NETi данного слоя. Это позволяет трактовать выход OUTi как вероятность событий, совокупность которых образует полную группу. Функции активации типа единичного скачка и линейного порога встречаются очень редко и, как правило, используются на учебных примерах. В практических задачах почти всегда применяется сигмоид альная функция активации. Выбор функции активации зависит от решаемой задачи, определяется удобством программной (аппаратной) реализации, а также алгоритмом обучения. 54 5.5 Парадигмы обучения нейронных сетей. Алгоритм обучения нейронной сети 5.5.1 Парадигмы обучения нейронных сетей Самым важным свойством нейронных сетей является их способность обучаться на основе данных окружающей среды и в результате обучения повышать свою производительность. Обучение – это процесс, в котором свободные параметры нейронной сети настраиваются посредством моделирования среды, в которую эта сеть встроена. Тип обучения определяется способом подстройки этих параметров. Существует две парадигмы обучения нейронных сетей – с учителем и без учителя. В первом случае, на входной вектор имеется готовый ответ, во втором случае нейронная сеть самообучается. Обучение нейронной сети с учителем предполагает, что для каждого входного вектора из обучающего множества существует требуемое значение выходного вектора, называемого целевым. Эти векто ра образуют обучающую пару. Веса сети изменяют до тех пор, пока для каждого входного вектора не будет получен приемлемый уровень отклонения выходного вектора от целевого. Примером является алгоритм обратного распространения ошибки. Обучение нейронной сети без учителя является намного более правдоподобной моделью обучения с точки зрения биологических корней искусственных нейронных сетей. Обучающее множество состоит лишь из входных векторов. Алгоритм обучения нейронной сети подстраивает веса сети так, чтобы получались согласованные выходные вектора, т.е. чтобы предъявление достаточно близких входных векторов давало одинаковые выходы. Примеры: алгоритм Хебба, Кохонена. 55 На данный момент придумано и запатентовано большое количество архитектур нейронных сетей и методов их обучения. Но основными (исходными) являются: - для обучения с учителем – это алгоритм обратного распространения ошибки; - для обучения без учителя – алгоритмы Хебба и Кохонена. Также в последнее время сформировалась новая, третья парадигма – смешанное обучение с подкреплением. В этой парадигме есть и обучение с учителем и обучение без учителя. 5.5.2 Алгоритм обратного распространения ошибки Алгоритм обратного распространения ошибки является одним из методов обучения многослойных нейронных сетей прямого распространения. Обучение данным алгоритмом предполагает два подхода по всем слоям сети: прямого и обратного. При прямом проходе входной вектор подается на входной слой нейронной сети, после чего распространяется по сети от слоя к слою. В результате генерируется набор выходных сигналов, который и является фактической реакцией сети на данный входной образ. Во время прямого прохода все синапсические веса сети фиксированы. Во время обратного прохода все синапсические веса настраиваются в соответствие с правилом коррекции ошибок, а именно: фактический выход сети вычитается из желаемого, в результате чего формируется сигнал ошибки. Этот сигнал впоследствии распространяется по сети в направлении, обратном направлению синапсических связей. Отсюда и название а лгоритма. Синапсические веса настраиваются с целью максимального приближения выходного сигнала сети к желаемому. Целью обучения сети алгоритмом обратного распространения ошибки является такая подстройка ее весов, чтобы приложение некоторого множества входов приводило к требуемому множеству выходов. Для 56 краткости это множества входов и выходов будут называться векторами. При обучении предполагается, что для каждого входного вектора существует парный ему целевой вектор, задающий требуемый выход. Вместе они называются обучающей парой. Сеть обучается на многих парах. Алгоритм обратного распространения ошибки следующий: 1) Инициализировать синапсические веса маленькими случайными значениями. 2) Выбрать очередную обучающую пару из обучающего множества; подать вход ной вектор на вход сети. 3) Вычислить выход сети. 4) Вычислить разность между выходом сети и требуемым выходом (целевым вектором обучающей пары). 5) Подкорректировать веса сети для минимизации ошибки. 6) Повторять шаги со 2 по 5 для каждого вектора обучающ его множества до тех пор, пока ошибка на всем множестве не достигнет приемлемого уровня. 5.5.3 Обучение без учителя. Алгоритм Хебба В рассмотренном алгоритме обратного распространения ошибки есть и входные значения и ответы, которые нейронная сеть должна воспроизвести. Но существует широкий пласт задач, в которых ответы заранее не известны, например, в задачах многомерной классификации. Обучение без учителя – самообучение сети. Процесс обучения без учителя строится на том же принципе, что и обучение с учителем – подстраивании синапсических весов. Очевидно, что подстройка синапсов может происходить только на основании информации, доступной в нейроне, то есть его состояния и уже имеющихся весовых коэффициентов. Рассмотрим сигнальный метод обучения Хебба. Веса по данному методу изменяются исходя из формулы: w p − q (i + 1) = w p − q (i ) + ηOUTpOUTq , (1) 57 где η - коэффициент «скорости обучения». При обучении данным методом усиливаются связи между возбужденными нейронами, что видно из второго слагаемого фор мулы. Также имеется и дифференциальный метод обучения Хебба. wij (t ) = wij (t − 1) + α [ yi( n −1) (t ) − yi( n −1) (t − 1)][ y (j n) (t ) − y (jn ) (t − 1)]. (2) Как видно из формулы сильнее всего обучаются те синапсы, которые наиболее динамично изменились в сторону увеличения. Полный алгоритм обучения методом Хебба выглядит с ледующим образом: 1) При инициализации сети всем весовым коэффициентам присваиваются небольшие случайные значения. 2) На входы подается выбранный случайным образом образец , и сигналы возбуждения распространяются по всем слоям согласно принципам прямопоточных сетей. 3) На основании полученных выходных значений нейронов по формулам (1) или (2) происходит коррекция весовых коэффициентов. 4) Цикл с шага 2 повторяется, пока выходные значения сети не стабилизируется с заданной точностью. Отметим, что вид откликов на каждый класс входных образов заранее не известен и будет представлять собой произвольное сочетание состояний нейронов выходного слоя, обусловленной случайным распределением весов на стадии инициализации. При этом сеть способна обобщать схожие образцы, относя их к одному классу. 58 6. Генетические алгоритмы 6.1 Вводные понятия Генетические алгоритмы – самый известный на сегодняшний день из эволюционных алгоритмов, он представляет собой модель размножения живых организмов. Идею генетических алгоритмов высказал американский ученый Дж. Холланд в конце 1960 -х – начале 1970-х гг. Он заинтересовался свойствами процессов естественной эволюции, посредством которой в природе решаются сложные задачи совершенствования живых организмов. Как известно, происходит это путем эволюционирования хромосом живых организмов: внутри популяции живых особей осуществляется отбор наиболее приспособленных и жизнестойких. Целью исследований Холланда было составление алгоритмов, оперировавших последовательностями 0 и 1 (двоичных чисел), получивших название хромосом . Эти алгоритмы имитировали эволюционные процессы в «поколениях» таких хромосом. В них были реализованы механизмы селекции (отбора) и репродукции (воспроизведения), аналогичные применяемым при естественной эволюции. Так же как и в природе, генетические алгоритмы осуществляли поиск «лучших» хромосом и, соответственно, выбор лучших «особей» (оптимальных или близких к оптимальным) из некоторого множества (популяции) альтернатив. Рассмотрим основные, заимствованные из генетики понятия, используемые в генетических алгоритмах. Популяция – конечное множество альтернативных вариантов или особей. Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами, в большинстве случаев одной хромосомой. Хромосома – упорядоченная последовательность генов, значение (аллель) которых выбирается из множества {0, 1}. 59 Генотип или структура – это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы или единичные хромосомы в довольно распространенном случае, когда генотип состоит из одной хромосомы. Локус или позиция указывает место размещения данного гена в хромосоме. Множество позиций генов – это локи. Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразовывается, и проблема сводится к максимизации. Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков». 6.2 Этапы работы генетического алгоритма Генетический алгоритм работает следующим образом (рис.23). В первом поколении все хромосомы генерируются случайно, т.е. из исходной (генеральной) популяции созда ется случайная выборка хромосом определенного объема (этап генерации начальной популяции). Определяется их приспособленность или «полезность» с точки зрения цели решаемой задачи. Приспособленность отображается в виде числовой функции (критерия). Отбираются хромосомы из начальной выборки с учетом 60 их приспособленности, и только эти хромосомы участвуют в создании новой популяции или популяции нового поколения ( этап селекции). Рис. 23 – Блок-схема генетического алгоритма Генетический алгоритм начинает генерировать новую популяцию (этап репродукции). Обычно размер выборочной популяции постоянен в различных поколениях. Репродукция состоит из трех генетических операторов (порядок применения неважен): кроссовер (кроссинговер), мутация, инверсия. После образования такого же числа хромосом в новой популяции, что и в исходной, новое поколение полностью замещает предыдущее и итерация 61 повторяется. В процессе моделирования эволюционных изменений решения (популяции) становятся все более близкими к оптимальным с точки зрения критерия приспособленности, изменения критерия на каждой итерации уменьшается. В отличие, например, от алгоритма полного перебора генетический алгоритм не гарантирует нахождения точного оптимального решения. Можно быстро найти хорошее решение, но оно не всегда будет оптимальным. Однако большинство реальных оптимизационных задач не требует нахождения оптимального решения. Генетические алгоритмы применяются при разработке программного обеспечения, в системах искусственного интеллекта, оптимизации, искусственных нейронных сетях и в других отраслях знаний. Следует отметить, что с их помощью решаются задачи, для которых ранее использовались только нейронные сети. В этом случае генетические алгоритмы выступают просто в роли независимого от нейронных сетей альтернативного метода, предназначенного для решения той же самой задачи. 6.2.1 Кодирование фенотипов в хромосомы Этап кодирования фенотипов в хромосомы - один из важнейших в реализации генетических алгоритмов, поскольку выбор метода кодирования оказывает самое существенное влияние на эффективность его работы. В классическом генетическом алгоритме применяется двоичное кодирование, т.е. аллели всех генов в хромосоме равны 0 или 1. Длина хромосомы зависит от условий задачи – от количества точек в пространстве поиска. Например, двоичная последовательность 10011 представляет собой код числа 19, поскольку 1 ⋅ 24 + 0 ⋅ 23 + 0 ⋅ 2 2 + 1 ⋅ 21 + 1 ⋅ 20 = 19 . В генетических алгоритмах можно, например, использовать код Грея, который характеризуется тем, что двоичные п оследовательности, соответствующие двум последовательным целым числам, отличаются только 62 одним битом. Такой способ кодирования хромосом может оказаться оправданным при использовании операции мутации. Для решения задач, например, максимизации функции на f (x ) промежутке [a, b] с точность до q знаков после запятой для каждой переменной xi . В такой ситуации требуется разбить промежуток [a, b] на (b − a ) ⋅ 10q одинаковых дискретизации с шагом подинтервалов. r = 10− q . Это означает применение Наименьшее натуральное число mi , удовлетворяющее неравенству (b − a) ⋅ 10 q ≤ 2m − 1 , определяет необходимую и достаточную длину двоичн ой последовательности, требуемой для кодирования числа из промежутка [a, b] с шагом r. Каждой такой двоичной последовательности соответствует десятичное значение числа, представляемого данным кодом. Пусть y обозначает десятичное значение сдвига двоичной последовательности, кодирующей x ; тогда выражение для декодирования имеет вид: x=a+ y b−a . 2m − 1 Логарифмическое кодирование (logarithmic coding) применяется в генетических алгоритмах для уменьшения длины хромосом. Оно используется, главным образом, в задачах многомерной оптимизации с большими пространствами поиска решений. При логарифмическом кодировании первый бит (α) кодовой последовательности – это бит знака показательной функции, второй бит ( β ) – бит знака степени этой функции, а остальные биты ( bin ) представляют значение самой степени: [αβ bin] = (−1) β e ( −1) α [ bin ]10 , где [bin]10 означает десятичное значение числа, закодированного в виде двоичной последовательности bin . Например, [10110 ] 63 представляет собой кодовую последовательность числа 1 x1 = (−1)0 e( −1) [110 ]10 = e −6 = 0,00247852 , а [01010] представляет собой код овую последовательность числа x2 = (−1)1 e ( −1) [ 010 ]10 = −e 2 = −7,389056099 . Таким образом, с помощью пяти битов можно закодировать числа из интервала [−e7 , e7 ] . Логарифмическое кодирование реализовано в программе FlexTool в качестве дополнительной опции для задач повышенной сложности. Еще одна модификация классического генетического алгоритма основана на кодировании действительными, а не двоичными числами. Это означает, что гены хромосом принимают действительные значения (аллели являются действительными числами). Такой способ кодирования применяется, в частности в программе Evolver. 6.2.2 Генерация начальной выборочной популяции Выбор начальной популяции - единственный этап эволюционного алгоритма, не имеющий естественных аналогов в живой природе. Работа генетического алгоритма с выборочной популяцией, как правило, много меньше полной совокупности фенотипов, - вынужденное ограничение, связанное с понятными трудностями описания и организации репродукции сразу всех особей. В определенном смысле здесь уместна аналогия с выборочным методом математической статистики, позволяющим работать не со всей генеральной совокупностью, а с некоторой выборкой из нее, определяемой случайным образом. Однако в отличие от задач статистики, где для целого ряда задач необходимый объем выб орки можно оценить, в генетических алгоритмах объем начальной популяции не имеет на сегодняшний день формализованной связи с какими -либо характеристиками решения. Выбор объема начальной популяции сегодня основывается на 64 эмпирических или эвристических соображениях для каждой конкретной задачи и, по крайней мере, не может быть меньше двух. Практически тоже можно сказать и о способе формирования выборки. Основной способ – случайный выбор, и лишь для некоторых задач удается определить начальную популяцию таким образом, чтобы обеспечивались наилучшие стартовые условия алгоритма. 6.2.3 Функция приспособленности Рассмотрим следующие блоки алгоритма реализации генетического алгоритма: оценка приспособленности, выбор наилучшей хромосомы; условия завершения поиска, т.е. блоки, непосредственно связанные с оценкой приспособленности. Оценка приспособленности Оценка приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. Чем больше значение этой функции, тем выше «качество» хромосомы. Форма функции приспособленности зависит от характера решаемой задачи. Предполагается, что функция приспособленности всегда принимает неотрицательные значения и, кроме того, что для решения оптимизационной задачи требуется максимизировать эту функцию. Если исходная форма функции приспособленности выполняется не соответствующее неотрицательности функции удовлетворяет преобразование. приспособленности этим условиям, то Для обеспечения можно выполнить, например, линейный сдвиг точки отсчета измерительной шкалы. В генетических алгоритмах рассматривается два вида приспособленности хромосом: нормализованная и относительная. Нормализованная приспособленность каждого генотипа chi (хромосомы) представляет собой отношение 65 p(chi ) = yi . N ∑y i i =1 В случае неотрицательные если функции значения, приспособленности то нормализованная yi принимают приспособленность принимает значения из отрезка [0, 1] . Поэтому в классическом генетическом алгоритме она рассматривается как вероятность и ее можно непосредственно использовать для селекции хромосом. Относительная приспособленность приспособленность особи (генотипа, рассматривается хромосомы), как нормализованная относительно средней приспособленности популяции: ~ yi = yi N yi N = . N ∑y /N ∑y i i =1 i i =1 Относительная приспособленность характеризует, насколько лучше или хуже приспособленность конкретной особи текущей популяции по сравнению со средним значением приспособленности. Средняя приспособленность популяции y= 1 N ∑ yi N i =1 может быть использована для формирования условий завершения работы генетического алгоритма. Здесь следует обратить внимание на то, что в процессе поиска лучших особей показателем эффективности поиска служит не максимальное значение функции приспособленности в полученной на очередном этапе популяции, а именно средняя приспособленность популяции. Максимальное значение функции приспособленности y max = max {y1 ,..., y N } может на определенных этапах поиска и уменьшаться, и оставаться практически неизменным, в то время как средняя приспособленность популяции должна возрастать. 66 В процессе работы генетического алгоритма решения становятся все более близкими к оптимальным, т.е. в текущей популяции начинают преобладать более приспособленные хромосомы и, в конце концов, в очередных поколениях популяция будет характеризоваться практически неизменной средней приспособленностью, а приспособленности хромосом популяции будут близки между собой и средней приспособленностью. Прекращение эволюционного изменения хромосом в процессе работы генетического алгоритма определяет его сходимость. 6.2.4 Селекция хромосом Селекция хромосом в выборочной популяции или отбор наиболее приспособленных родительских пар отражает соответствующий этап природной эволюции. Действительно, в природе не каждая особь, в силу тех или иных своих недостатков, хорошо приспособлена для продолжения рода. В то же время наличие множества случайных факторов порождает ситуации, в которых хорошо приспособленные особи выбывают из цепочки продолжения рода, и наоборот, особи, приспособленные не лучшим образом, дают потомство. В генетическом алгоритме селекция осуществляется на основе двух принципов: случайности и приспособленности. В классическом генетическом алгоритме селекция, т.е. формирование р одительского пула из текущей популяции, осуществляется методом рулетки. Который позволяет в процессе случайного выбора хромосом для скрещивания выбирать из начальной популяции более приспособленные хромосомы с большей вероятностью. Следует отметить, что метод рулетки можно применять тогда, когда значения функции приспособленности положительны. Этот метод может применяться только в задачах максимизации функции (но не минимизации). Очевидно, что проблему минимизации можно легко свести к задаче максимизации функции и обратно. В некоторых реализациях генетического 67 алгоритма метод рулетки применяется для поиска минимума функции. Это результат соответствующего преобразования, выполняемого программным путем для удобства пользователей, поскольку в большинстве прикла дных задач решается проблема минимизации (например, затрат, расстояния, погрешности и т.п.). Однако возможность применения метода рулетки всего лишь для одного класса задач, т.е. только для максимизации (или только для минимизации) можно считать его несомненным недостатком. Другой слабой стороной метода рулетки является возможность быстрого исключения из родительского пула особей с малой приспособленностью, что может привести к преждевременной сходимости генетического алгоритма. Для предотвращения такого эф фекта применяется масштабирование функции приспособленности. С учетом отмеченных недостатков метода рулетки созданы и используются альтернативные алгоритмы селекции. Один из них называется турнирным методом (турнирной селекцией tournament selection), при которой все особи текущей популяции случайным образом разбиваются на подгруппы с последующим выбором в каждой из них особи с наилучшей приспособленностью. Различают два способа выбора: детерминированный выбор и случайный выбор. Детерминированный выбор осуществляется с вероятностью, равной 1, а случайный выбор – с вероятностью меньше 1. Подгруппы могут иметь произвольный размер, но обычно включают по 2 – 3 особи. Турнирный метод пригоден для решения задач, как максимизации, так и минимизации функции. Помимо того, он может быть легко распространен на задачи, связанные с многокритериальной оптимизацией, т.е. на случай одновременной оптимизации нескольких функций. В турнирном методе допускается изменение размера подгрупп, на которые подразделяется популяция. Исследования подтверждают, что турнирный метод действует эффективнее, чем метод рулетки. 68 На рис.24 представлена схема, которая иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей. Такую схему легко обобщить на подгруппы большего разме ра. При ранговой селекции (ranking selection) особи популяции ранжируются по значениям их функции приспособленности. Это можно представить себе как отсортированный список особей, упорядоченных по направлению от наиболее приспособленных к наименее приспособленным (или наоборот), в котором каждой особи приписывается число, определяющее ее место в списке и называемое рангом. Количество копий M (k ) каждой особи, введенных в родительскую популяцию, рассчитывается по априорно заданной функции в зависимости от ранга особи. Пример такой функции приведен на рис. 25. Рис. 24 – Схема турнирной селекции для подгрупп, состоящих из двух особей Рис. 25 – Пример функции, определяющей зависимость количества копий особи в родительском пуле от его ранга при ранговой селекции 69 Достоинство рангового метода заключается в возможности его применения как для максимизации, так и для минимизации функции. Он также не требует масштабирования из-за проблемы преждевременной сходимости, как в методе рулетки. Существуют различные варианты алгоритмов селекции. Представленные методы (рулетки, турнирный и ранговый) применяются чаще всего. Другие методы представляют собой либо их модификации, либо комбинации – например, метода рулетки с турнирным методом, когда пары родительских хромосом выбираются случайным образом, после чего из каждой пары выбирается хромосома с наибольшим значением функции приспособленности. В результате процесса селекции создается родительская по пуляция, также называемая родительским пулом с численностью N, равной численности текущей популяции. 6.2.5 Операции репродукции (применение генетических операторов) Применение генетических операторов к хромосомам, отобранным с помощью селекции, приводит к формированию новой популяции потомков от созданной на предыдущем шаге родительской популяции. Репродукция особей из родительских пар предыдущего поколения, осуществляется обычно с помощью операторов кроссовера, мутации и инверсии. Воздействуя с некоторой вероятностью на генотипы родительских особей, каждый из операторов этой триады, с одной стороны, обеспечивает передачу потомству жизненно важных принципов (наследование), а с другой – поддерживает на протяжении эволюционно значимого п ериода достаточно высокий уровень его изменчивости. В классическом генетическом алгоритме применяются два основных генетических оператора: кроссовер и мутация. Кроссовер (операция скрещивания) является наиболее важным генетическим оператором. Он генерирует новую хромосому, объединяя генетический материал двух родительских. Существует несколько вариантов 70 реализации кроссовера (одноточечный, многоточечный, с частичным случайным выбором аллелей). Оператор кроссовер обычно рассматривается как детерминированный оператор, т.е. его применен ие осуществляется с вероятностью pk = 1 . Мутация представляет собой случайное изменение хромосомы. Если кроссовер обязательный оператор, то мутация может и не использоваться. Такой подход соответствует природной, естественной эволюции, где мутация – довольно редкое явление. Мутация обеспечивает появление у потомков новых, отличных от родительских, фенотипических признаков и открывает для популяции дополнительные возможности для адаптации, т.е. способствует сохранению ею поисковой способности. При использовании вероятностного подхода к применению мутации вероятность этого применения обычно лежит в пределах 0 ≤ pm ≤ 0,1 . Оператор мутации может применяться и детерминировано, если он используется для исправления наследственных признаков, не отвечающих принятым допущениям. Инверсия инвертирует (изменяет) порядок бит в хромосоме путем циклической перестановки (случайное количество раз). Многие модификации генетических алгоритмов обходятся без данного генетическ ого оператора. Оператор скрещивания (кроссовер). На первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из предназначенных хромосом, для отобранных дальнейших в результате преобразований селекции и операторами скрещивания и мутации с целью формирования новой популяции потомков . На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания pc . Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей 71 состоит из L генов, то очевидно, что точка скрещивания lk представляет собой натуральное число, меньшее L . Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1, L − 1] . В классическом генетическом алгоритме обычно используются точечные кроссоверы. Простейший детерминированный одноточечный кроссовер в котором каждая родительская хромосома делится на две равные части и хромосома потомка образуется п о схеме, приведенной на рис.26. Рис.26 – Пример одноточечного кроссовера Детерминированный трехточечный кроссовер можно проиллюстрировать схемой, приведенной на рис. 27. Рис. 27 – Пример детерминированного трехточечного кроссовера В предыдущих схемах точки деления хромосом выбраны вполне определенно, в данном случае исходя из принципа равенства локов (позиций) в каждом отрезке деления. Вообще можно использовать и другие принципы детерминированного деления. Точечный кроссовер (одноточечный и многоточечный) может основываться и на случайном принц ипе выбора точек деления родительских хромосом. 72 Вообще говоря, схем реализации оператора кроссовер можно придумать достаточно много. В качестве примера предлагается схема кроссовера (рис. 28), основанная на следующем правиле: совпадающие аллели родительских хромосом сохраняются у потомков, а не совпадающие выбираются случайным образом из множества {0, 1}. Рис. 28 – Пример кроссовера с частичным случайным выбором аллелей Оператор мутации В классическом представлении основная задача мутации – обеспечить возможность перехода к тем решениям, к которым невозможно перейти с помощью кроссоверов из начального состояния популяции. Именно поэтому вероятность возникновения мутации – это предмет особого исследования. С одной стороны, мутация не должна вносить хаос в популяцию, разрушая «хорошие» решения (такая ситуация будет наблюдаться при большой вероятности возникновения мутации). С другой стороны, мутация должна обеспечить широкие возможности перебора решений. Недаром в природе мутация играет ключевую роль; без нее эволюция была бы невозможной. В классическом генетическом алгоритме оператор мутации с некоторой малой вероятностью изменяет значения генов, полученные в результате применения кроссовера, на противоположные. Например, если в результате в ыполнения оператора кроссовера получена хромосома (10011000100), то в результате применения оператора мутации эта хромосома примет вид (01100111011). Выбор той или иной схемы реализации кроссовера, как правило, определяется спецификой и условиями решаемой задачи, выбором метода кодирования и другими рациональными соображениями. Основная функция 73 кроссовера и мутаций – это перебор вариантов решений. Конкретная реализация алгоритма должна обеспечить потенциальную возможность получения любого решения из всего пространства возможных решений только с помощью кроссоверов и мутаций. Действительно, кроссовер позволяет эффективно перебирать достаточно большое число вариантов (поскольку начальные решения формировались случайным образом). 6.2.6 Формирование новой популяции Хромосомы, полученные в результате применения генетических операторов к хромосомам временной родительской популяции, включа ются в состав новой популяции. Она становится так называемой текущей популяцией для данной итерации генетического алгоритма. На каждой очередной итерации рассчитываются значения функции приспособленности для всех хромосом этой популяции, после чего проверяется условие остановки алгоритма и либо фиксируется результат в виде хромосомы с наибольшим значением функции приспособленности, либо осуществляется переход к следующему шагу генетического алгоритма, т.е. к селекции. В классическом генетическом алгоритме вся предшествующая популяция хромосом замещается новой популяцией потомков, имеющих ту же численность. Выбор наилучшей хромосомы (завершение работы генетического алгоритма). Завершение работы генетического алгоритма обычно связано с анализом значений функций приспособленности. Признаком завершения работы может быть, например, достижение заданной минимальной скорости изменения значений средней приспособленности популяций - y j +1 − y j ≤ ε . 74 7. Гибридные системы Под гибридной интеллектуальной системой (ГиИС) принято понимать систему, в которой для решения задачи используется более одного метода имитации интеллектуальной деятельности человека. Таким образом, ГиИС – это совокупность: - экспертные системы, - нечеткие системы, - искусственные нейронные сети, - генетические алгоритмы. Междисциплинарное направление «гибридные интеллектуальные системы» объединяет ученых и специалистов, исследующих применимость не одного, а нескольких методов, как правило, из различных классов, к решению задач управления и проектирования. История возникновения термина Термин «интеллектуальные гибридные системы» появился в 1992 году. Авторы вкладывали в него смысл гибридов интеллектуальных методов, таких как экспертные системы, нейросети и генетические алгоритмы. Экспертные системы представляли символьные, а искусственные нейронные сети и генетические алгоритмы – адаптивные методы искусственного интеллекта. Однако, в основном новый термин казался достаточно узкой области интеграции – экспертные системы и нейронные сети. Объединение нейронной сети с нечеткой системой – позволяют с одной стороны привнести способность к обучению и вычислительную мощность нейронных сетей в системы с нечеткой логикой, а с другой стороны – усилить интеллектуальные возможности нейронных сетей свойственными «человеческому» способу мышления нечеткими правилами выработки решений. Простейшей гибридной системой является система, объединяющая в себе имитационную модель и блок оптимизации. Блок оптимизации 75 реализует один из алгоритмов поисковой оптимизации (например, простейший генетический алгоритм), а имитационная модель служит для вычисления значений критерия оптимизации (функции пригодности) для выбираемых вариантов решения. Использование гибридных ИС особенно эффективно в медицине, банковском деле, при распознавании образов, при обнаружении неисправностей в технических системах и т.д., то есть в тех отраслях, где приходится иметь дело как четкими, так и с нечеткими знаниями. 7.1 Классификация гибридных интеллектуальных систем Гибридные ИС можно классифицировать, в зависимости от архитектуры, на следующие типы: 1) комбинированные (combination), 2) интегрированные (integration), 3) объединенные (fusion) и 4) ассоциативные (association) гибридные интеллектуальные системы. Комбинированные ГиИС Ассоциативные ГиИС Интегрированные ГиИС Объединенные ГиИС Рис. 29 - Типы архитектур ГиИС 76 Кроме того, можно рассматривать и еще один тип гибридных ИС, появление которого обусловлено стремительным ростом объемов знаний и данных, которые могут храниться в распределенных базах данных, доступных через глобальную сеть Internet. Архитектуру гибридной ИС такого типа можно назвать распределенной (distributed). Internet Рис. 30 - Архитектура распределенной гибридной ИС Комбинированные (combination) гибридные интеллектуальные системы Примером комбинированных гибридных ИС служат гибридные экспертные системы, представляющие собой интеграцию экспертных систем и нейронных сетей и соединяющие как формализуемые знания (в экспертных системах), так и неформализуемые знания (в нейронных сетях). Примерами комбинированных систем могут служить: гибридная экспертная система для анестезиологии тяжелых пациентов, экспертная система адаптивного обучения, гибридная экспертная система для медицинской диагностики. В состав гибридной экспертной системы для медицинской диагностики входят три основных компонента: 1) нечеткая нейронная сеть, 2) нечеткая экспертная система и 3) модуль принятия и объяснения решений. Кроме того, в состав гибридной экспертной системы входят еще два дополнительных интерфейсных модуля, соединяющие нейронную сеть и экспертную систему 77 и позволяющие взаимно преобразовывать данные нечеткой нейронной сети и нечеткой экспертной системы. Гибридная экспертная система для медицинской диагностики сочетает в себе численное и лингвистическое представление знаний, в системе используется иерархическая интеграция самоорганизующейся нечеткой нейронной сети (с возможностью online-обучения) и нечеткой экспертной системы, оптимизированной посредством генетического алгоритм а. Нейронная сеть способствует быстрому обучению, в то время как экспертная система позволяет выполнить интерпретацию нечетких данных и объяснить полученное решение. Нейронная сеть может обучаться как с учителем, так и без учителя, может обучаться без переподготовки старой информации. Внешние входные данные поступают в гибридную систему как через экспертную систему, так и через нейронную сеть. Выходные данные экспертной системы и нейронной сети поступают на вход модуля, находящего и объясняющего решения. Интегрированные (integration) гибридные интеллектуальные системы В архитектуре интегрированных гибридных ИС главенствует основной модуль-интегратор, который, в зависимости от поставленной цели и текущих условий нахождения решения, выбирает для функциониро вания те или иные интеллектуальные модули, входящие в систему, и объединяет отклики задействованных модулей. Примерами интегрированных гибридных ИС могут служить: гибридная экспертная система RAISON, гибридная интеллектуальная система для создания планов движения роботов. Объединенные (fusion) гибридные интеллектуальные системы Характерной особенностью нейронных сетей и генетических алгоритмов является их способность к обучению и адаптации посредством оптимизации. Соединение этих методов с другими метода ми искусственного 78 интеллекта позволяет увеличить эффективность их способности к обучению. Такую архитектуру гибридной ИС можно отнести к объединенному типу. Примерами объединенных гибридных ИС могут служить: гибридная экспертная система для инвестиционных рекомендаций, гибридная экспертная система для определения неисправностей в энергетических системах. Гибридная экспертная система для определения неисправностей в энергетических системах состоит из модуля входного условия и модуля вывода. Модуль вывода п редназначен для оценки местонахождения и типа неисправности с помощью искусственной нейронной сети (многослойного персептрона). В рассматриваемой гибридной экспертной системе применены методы, основанные на использовании искусственных нейронных сетей, и отличающиеся от традиционных использованием приема входного условия (предусловия), когда входной вектор подается не непосредственно на вход нейронной сети, а на вход предусловного модуля. В свою очередь, выходной сигнал предусловного модуля подается на вход нейронной сети, что позволяет сделать работу сети более эффективной. В системе применены два предусловных метода: один из них использует быстрое преобразование Фурье для измерения детерминированную отклонений нелинейную тока, другой кластеризацию для – применяет результатов, полученных с помощью преобразования Фурье. Ассоциативные (association) гибридные интеллектуальные системы Архитектура ассоциативных гибридных систем предполагает, что интеллектуальные модули, входящие в состав такой системы, могут раб отать как автономно, так и в интеграции с другими модулями. В настоящее время, из-за недостаточного развития систем такого типа, системы с ассоциативной архитектурой еще недостаточно надежны и не получили широкого распространения. 79 Распределенные (distributed) гибридные интеллектуальные системы. Следующим уровнем в развитии гибридных систем могут стать распределенные мультиагентный интеллектуальные подход в области системы, представляющие распределенного искусственного интеллекта. При этом подходе каждый функциональный интеллектуальный модуль работает автономно и взаимодействует с другими модулями (агентами) путем передачи сообщений через сеть. Существующие в настоящее время интеллектуальные системы, такие как экспертные системы, нейронные сети и т.п. могут быть преобразованы в агенты. В процессе преобразования интеллектуальные модули могут быть дополнены управляющими и коммуникативными знаниями, необходимыми для их объединения в мультиагентную интеллектуальную распределенную систему. Примером распределенной интеллектуальной системы может служить интеллектуальная обучающая система для обучения преподавателей высшей школы новым обучающая технологиям, система основанная формирует на Web. обучающий Интеллектуальная курс (презентацию образовательного материала, адаптированную к требованиям пользователей с использованием определения технологий модели искусственного каждого пользователя, интеллекта а также для для точного создания педагогических решений), отвечающий нуждам пользователей с различными уровнями знаний и различными способностями в освоении нового материала. Интеллектуальная обучающая система основана на экспертной системе, направленной на управление процессом обучения. Экспертная система использует формализм гибридного представления знаний, названного нейроправилами. Система состоит из следующих компонентов: 1) домена знаний, 2) модели пользователя, 3) педагогической модели, 4) машины логического вывода и 5) пользовательского интерфейса. Домен знаний содержит знания, относящиеся к изучаемой теме и представляющие актуальный обучающий 80 материал. Домен состоит из двух частей: 1) понятий знаний и 2) курсовых блоков. Курсовые блоки содержат обучающий материал, представляемый пользователям системы ассоциируется с как Web -страница. определенным числом Каждый понятий курсовой знаний. блок Система поддерживает варианты одной и той же страницы (курсового блока) с различными представлениями знаний. Модели пользователя применяются для записи информации, связанной с пользователем. Модели пользователей обновляются в течение всего процесса обучения. Педагогическая модель формирует процесс обучения. Она предлагает инфраструктуру знаний для адаптации презентации изучаемого материала в соответствии с данными, содержащимися в модели пользователя. Формализм представления знаний в экспертной системе основан на нейроправилах, гибридных правилах, интегрирующих символические правила с нейровычислениями. Нейроправила создаются либо на основе эмпирических данных (обучающих шаблонов), либо на основе символических правил. Каждое нейроправило индивидуально обучается посредством специального алгоритма. Механизм вывода основан на стратегии обратного вывода. 7.2 Программные средства реализации ГиИС Существуют различные программные средства, в которых реализуются ГиИС. 1) CubiCalc – программа фирмы HyperLogic, является одной из наиболее мощных экспертных систем на основе нечеткой логики. Пакет содержит интерактивную оболочку для разработки нечетких экспертных систем и систем управления. Фактически пакет CubiCalc 2.0 представляет собой своего рода экспертную систему, в которой пользователь задает набор правил типа «если – то», а система пытается на основе этих правил адекватно реагировать на 81 параметры текущей ситуации. Отличие состоит в том, что вводимые правила содержат нечеткие величины, т.е. имеют вид «если X принадлежит A , то Y принадлежит B », где A и B - нечеткие множества. Аппарат нечеткой логики, заложенный в CubiCalc, дает возможность оперировать нечеткими понятиями как точными и строить на их основе целые логические системы. 2) RAISON – это интегрированная, основанная на знаниях, экспертная система, включающая нейронную сеть, базу данных, геоинформационную систему, картографический анализатор, графическую и программно - языковую компоненты. Экспертная система является интегрирующим модулем и связана с другими компонентами гибридной системы. Вспомогательные подсистемы, такие как база данных и геоинформационная система, служат связующими звеньями экспертной системы с полнофункциональными внешними базами данных и геоинформационными системами. Функционирование экспертной системы основано на использовании алгоритма с применением индукционного дерева (алгоритм позволяет генерировать правила на основе образцов наборов данных), известные и существующие правила предлагаются экспертом. Правила могут использоваться как для прямой, так и для обратной последовательности запросов. Так как структура дерева является поч ти оптимальной, число запросов, требующихся для получения заключения, является минимальным. База данных и карты геоинформационной системы также доступны и нейронной сети. Нейронная сеть используется в системе RAISON как инструмент обучения. Нейронная сеть может принимать входные данные и использовать их в качестве образцов для обучения (обучаться с учителем). Выходные данные системы RAISON могут быть сохранены в базе данных, отображены, например, в графическом виде (в виде геоинформационных карт). Гибридная интеллектуальная система для создания планов движения роботов включает в себя объектно-ориентированную базу знаний для моделирования окружающей среды и адаптивный алгоритм планирования 82 движения (ААПД). На основе полученных данных (предварительно сформированных карт окружающей обстановки и последующей динамической информации об окружении робота) ААПД определяет путь и генерирует последовательность команд для навигации робота. Гибридная система состоит из четырех модулей: 1) планировщика, 2) помощников, 3) исполнителей движений и 4) управляющего центра. В системе реализована архитектура с использованием управляющего центра, который связан с перечисленными модулями и координирует их функционирование. Для управления достаточно сложной концепцией совместно использующейся информации в системе применена иерархическая база знаний, которая включает в себя три информационные области: 1) модель окружающей среды, 2) персептрон и 3) супервизор, осуществляющий настройку управляющего режима. В системе используется упрощенная схема нечеткого вывода для определения дистанции до препятствия и ширины пути. Для уменьшения объема вычислений применяются нечеткие треугольные функции принадлежности. Машина нечеткого вывода работает с нечеткими правилами и нечеткими треугольными ф ункциями принадлежности. Для поиска подходящего пути в системе используется сеть Хопфилда. Для генерации команд поведения используются правила нечеткого вывода. 3) Anfis (Adaptive-Network-Based Fuzzy Inference System) – адаптивная сеть нечеткого вывода. Была предложена Янгом (Jang) в начале девяностых годов. ANFIS является одним из первых вариантов гибридных нейро нечетких сетей – нейронной сети прямого распространения сигнала особого типа. ANFIS реализует систему нечеткого вывода Сугено в виде пятислойной нейронной сети прямого распространения сигнала. Назначение слоев следующее: - первый слой – термы входных переменных; - второй слой – антецеденты (посылки) нечетких правил; 83 - третий слой – нормализация степеней выполнения правил; - четвертый слой – заключения правил; - пятый слой – агрегирование результата, полученного по различным правилам. 84