Развитие генетических алгоритмов в системах искусственного интеллекта

ЗПЭ-09/51                                                                                       Саковский А. С.

Содержание

 

 

1. Моделирование рассуждений в экспертных системах. 2

1.1. Знания и их представление 3

1.1.1. Логические модели 5

1.1.2. Продукционные модели 6

1.1.3. Сетевые модели 8

1.1.4. Фреймовые модели 9

1.2. Моделирование рассуждений 12

1.2.1. Рассуждения на основе прецедентов 14

1.2.2. Моделирование рассуждений на основе ограничений 17

1.2.3. Немонотонные модели рассуждений 17

1.2.4. Рассуждения о действиях и изменениях 18

1.2.5. Рассуждения с неопределенностью 18

2. Развитие генетических алгоритмов в системах искусственного интеллекта. 20

2.1. История появления эволюционных алгоритмов 20

2.2. Применение генетических и эволюционных алгоритмов оптимизации 23

3. Консалтинг как технология знаний. 25

Литература 27

 

 

1. Моделирование рассуждений в экспертных системах.

 

Введение

 

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

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

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

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

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

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

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

1. Знания и их представление

 

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

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

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

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

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

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

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

 

1.  Логические модели

 

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

Пример. Возьмем утверждение: "Инфляция в  стране превышает прошлогодний уровень  в 2 раза". Это можно записать в  виде логической модели: r(InfNew, InfOld, n), где r(x,y) - отношение вида "x=ny", InfNew - текущая инфляция в стране, InfOld - инфляция в прошлом году. Тогда  можно рассматривать истинные и  ложные предикаты, например, r(InfNew, InfOld, 2)=1, r(InfNew, InfOld, 3)=0 и т.д. Очень полезные операции для логических выводов - операции импликации, эквиваленции.

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

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

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

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

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

 

2.  Продукционные модели

 

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

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

Взаимосвязанный набор продукций образует систему. Основная проблема вывода знания в  системе продукций является выбор  для анализа очередной продукции. Конкурирующие продукции образуют фронт.

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

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

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

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

 

3.  Сетевые модели

 

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

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

 

4.  Фреймовые модели

 

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