9290

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

ции»; «Вывести список потенциальных покупателей некоторого товара».

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

Естественно-языковой интерфейс предполагает трансляцию естественно-

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

Естественно-языковый интерфейс используется для:

доступа к интеллектуальным базам данных;

контекстного поиска документальной текстовой информации;

голосового ввода команд в системах управления;

машинного перевода c иностранных языков.

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

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

стем распространения знаний (Knowledge Publishing) и создаются как приложе-

ние к системам документации (например, технической документации по экс-

плуатации товаров).

11

Системы когнитивной графики позволяют осуществлять интерфейс поль-

зователя с ИИС с помощью графических образов, которые генерируются в со-

ответствии с происходящими событиями.

Самообучающаяся система – это ИИС, которая на основе примеров ре-

альной практики автоматически формирует единицы знаний.

В основе самообучающихся систем лежат методы автоматической класси-

фикации примеров ситуаций реальной практики (обучения на примерах). При-

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

знаков классификации. Причем обучающая выборка может быть:

–«с учителем», когда для каждого примера задается в явном виде значение признака его принадлежности некоторому классу ситуаций;

–«без учителя», когда по степени близости значений признаков классифи-

кации система сама выделяет классы ситуаций.

В результате обучения системы автоматически строятся обобщенные пра-

вила или функции, определяющие принадлежность ситуаций классам, которы-

ми обученная система пользуется при интерпретации новых возникающих си-

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

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

Раздел 3. Адаптивные системы с генетическими алгоритмами.

Рассматриваются основные понятия и принципы эволюционного модели-

рования систем, а также генетических алгоритмов – адекватного аппарата его проведения.

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

мах и их возможностях в эволюционном моделировании.

12

На лекциях рассматриваются простой генетический алгоритм и его моди-

фикации, их математические основы, разбираются примеры построения генети-

ческих алгоритмов для решения задач оптимизации.

Основные понятия генетических алгоритмов:

1)Особь (генотип, индивидуум, структура) – вариант решения задачи в за-

кодированном виде. Иначе, это точка в многомерном пространстве для оптимизируемой функции f(x1,x2,….,xn)max.

2)Популяция – множество особей, образованное на i-m шаге выполнения генетических алгоритмов.

3)Поколение – очередная популяция на i-м шаге.

4)Хромосома – вектор (последовательность) из нулей и единиц (или других значений).

5)Ген – одна позиция (бит) хромосомы.

6)Аллель – значение гена.

7)Локус – позиция (номер гена) в хромосоме

8)Фенотип – множество декодированных значений, соответствующих гено-

типу.

9)Кроссовер – операция, при которой хромосомы обмениваются частями.

10)Мутация – случайное изменение одной (нескольких) позиций в хромо-

соме.

11) Функция приспособленности (fitness function) – функция оценки, которая определяет меру приспособленности данной особи в популяции и позво-

ляет выбрать из множества особей наиболее приспособленную в соответ-

ствии с эволюционным принципом выживания сильнейших.

Виды функций приспособленности:

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

к максимизации.

13

В задачах теории управления ФП – это функция ошибки ε.

В теории игр ФП – это стоимостная функция.

Работа ГА представляет собой итерационный процесс, который продолжа-

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

Блок-схема классического генетического алгоритма.

конец

14

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

Согласно репродуктивному плану Холланда генетические схемы поиска оптимальных решений включают следующие этапы процесса эволюции:

1. Конструируется начальная популяция. Вводится начальная точка отсчё-

та поколений t = 0. вычисляются приспособленность хромосом популяции (це-

левая функция) и средняя приспособленность всей популяции.

2. Устанавливается значение t = t+1. выбираются два родителя (хромосо-

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

нально жизнеспособности хромосом, которая характеризуется значениями це-

левой функции.

3. Формируется генотип потомка. Для этого с заданной вероятностью над генотипами выбранных хромосом производится операция кроссинговера. Слу-

чайным образом выбирается один из потомков А(t), который сохраняется как член новой популяции. Далее к потомку А(t) последовательно с заданными ве-

роятностями применяются операторы инверсии и мутации. Полученный в ре-

зультате генотип потомка сохраняется как А(t).

4.Обновление текущей популяции путём замены случайно выбранной хромосомы на А(t).

5.Определение приспособленности А(t) и пересчёт средней приспособ-

ленности популяции.

6. Если t=Т, где Т – заданное число шагов, то переход к этапу 7, в против-

ном случае – переход к этапу 2. 7. конец работы.

Проверка условия остановки ГА.

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

Некоторые из возможных условий остановки

1.По времени.

2.По количеству итераций.

15

3.По отсутствию улучшения функции приспособленности.

4.По достижению максимума (если он известен).

Достоинства генетических алгоритмов.

1)ГА не имеет значительных математических требований к видам целевых функций и ограничений (отсутствует ограничение на дифференцируе-

мость функций). Исследователь не должен упрощать модель объекта, те-

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

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

2)Гибкость – хорошо работает при минимуме информации об окружающей среде (при высокой степени априорной неограниченности).

3)При использовании классических пошаговых методик глобальный опти-

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

ских алгоритмов позволяют эффективно отыскивать глобальный опти-

мум.

4)В ряде случаев ГА может находить только локальный минимум (макси-

мум). Несмотря на это, дает быстрое нахождение приемлемого решения.

5)Комбинируется с другими методами искусственного интеллекта и его эф-

фективность может повышаться.

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

зации.

7)Минимизация ошибок. Высокая скорость поиска решений. Возможность распараллеливания вычислений.

16

Раздел 4. Экспертные системы. Инженерия знаний. Модели знаний.

Автоматическое формирование знаний.

Цель лекции: дать систематическое представление о возможностях совре-

менных методов извлечения и представления знаний в современных информа-

ционных технологиях, об автоматическом формирование знаний и системах ав-

томатического формирования знаний.

На лекциях дается классификация экспертных систем, рассказывается об истории, этапах разработки экспертных систем, рассматриваются примеры промышленных ЭС.

Технология их разработки ЭС, включает в себя шесть этапов:

1) На этапе идентификации необходимо выполнить следующие дей-

ствия:

определить задачи, подлежащие решению и цели разработки,

определить экспертов и тип пользователей.

2)На этапе концептуализации:

проводится содержательный анализ предметной области,

выделяются основные понятия и их взаимосвязи,

определяются методы решения задач.

3) На этапе формализации:

17

выбираются программные средства разработки ЭС,

определяются способы представления всех видов знаний,

формализуются основные понятия.

4) На этапе выполнения (наиболее важном и трудоёмком) осуществляет-

ся наполнение экспертом БЗ, при котором процесс приобретения знаний раз-

деляют:

на "извлечение" знаний из эксперта,

на организацию знаний, обеспечивающую эффективную работу ЭС,

на представление знаний в виде, понятном для ЭС.

Процесс приобретения знаний осуществляется инженером по знаниям на основе деятельности эксперта.

5) На этапе тестирования эксперт и инженер по знаниям с использова-

нием диалоговых и объяснительных средств проверяют компетентность ЭС.

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

6) На этапе опытной эксплуатации проверяется пригодность ЭС для конечных пользователей. По результатам этого этапа возможна существен-

ная модернизация ЭС.

Процесс создания ЭС не сводится к строгой последовательности этих эта-

пов, так как в ходе разработки приходится неоднократно возвращаться на более ранние этапы и пересматривать принятые там решения.

Схема обобщенной экспертной системы имеет вид:

18

1. Лингвистический процессор (интерфейс с пользователем) – осуществля-

ет диалоговое взаимодействие с пользователем (экспертом) на естественном для него языке (естественный язык, профессиональный язык, язык графики и т.

д.). В экспертных системах применяются различные варианты реализации ин-

терфейса: меню-ориентированный. Графический, командный, речевой.

1. База знаний – обеспечивает хранение знаний, представленных с помо-

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

2.Рабочая память (база данных) – хранит данные, имеющие отношения к анализируемой системой ситуации.

3.Интерпретатор (машина вывода) – на основе входных данных, продук-

ционных правил и общих фактов о проблемной области формирует решение за-

дачи.

4. Компонента приобретения знаний используется как с целью автоматиза-

ции процесса наполнения ЭС знаниями, так и при корректировке базы знаний,

при ее обновлении, пополнении или исключении элементов знаний.

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

Экспертная система работает в двух режимах: в режиме приобретения знаний и в режиме решения задач.

На лекциях изучаются модели представления знаний: семантические сети,

19

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

Модель представления знаний с помощью фактов и правил (продукци-

онная модель) построена на использовании выражений вида

ЕСЛИ (условие) – ТО (действие).

Модель представления знаний с помощью логики предикатов исполь-

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

сания отношения сущностей в виде реляционной формулы, содержащей в себе термы

Семантические сети.

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

ваемыми объектами. Дуги могут быть определены разными методами. Обычно для представления иерархии используются дуги типа IS-A (отношение "являет-

ся") и HAS-PART (отношение "имеет часть"). Они также устанавливают иерар-

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

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

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

Модель универсальна и легко настраивается. Характерная особенность семантической сети – наглядность знаний как системы.

Фреймы.

Фреймовая модель по своей организации во многом похожа на семантиче-

скую сеть. Она является сетью узлов и отношений, организованных иерархиче-

ски: верхние узлы представляют общие понятия, а подчиненные им узлы –

20