1.2. Теоретические положения

 

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

 

 

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

В любой момент времени в системе существуют три типа знаний:

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

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

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

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

 

 

  Особенности экспертных систем:

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

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

3. Наиболее подходящая  область применения- решение задач дедуктивным методом. Например, правила или эвристики выражаются в виде пар посылок и заключений типа  “если-то”.

4. Эти системы могут объяснять ход решения задачи понятным пользователю способом. Обычно мы не принимаем ответ эксперта, если на вопрос “Почему?” не можем получить логичный ответ. Точно так же мы должны иметь возможность спросить систему, основанную на знаниях, как было получено конкретное заключение.       

5.  Выходные результаты являются качественными (а не количественными).

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

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

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

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

2) методы представления знаний позволяли описывать лишь статические предметные области.

3) модели представления знаний ориентированы на простые области.

    Представление знаний в экспертных системах второго поколения следующее:

1) используются не поверхностные знания, а более глубинные. Возможно дополнение предметной области.

2) ЭС может решать задачи динамической базы данных предметной области.

Области применения экспертных систем:

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

а) Медицинская диагностика.

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

б) Прогнозирование.    

Прогнозирующие системы предсказывают возможные результаты или события на основе данных о текущем состоянии объекта. Программная система “Завоевание Уолл-стрита” может проанализировать конъюнктуру рынка и с помощью статистических методов алгоритмов разработать для вас план капиталовложений на перспективу. Она не относится к числу систем, основанных на знаниях, поскольку использует процедуры и алгоритмы традиционного программирования. Хотя пока еще отсутствуют ЭС, которые способны за счет своей информации о конъюнктуре рынка помочь вам увеличить капитал, прогнозирующие системы уже сегодня могут предсказывать погоду, урожайность и поток пассажиров. Даже на персональном компьютере, установив простую систему, основанную на знаниях, вы можете получить местный прогноз погоды.

в) Планирование.

Планирующие системы предназначены для достижения конкретных целей при решении задач с большим числом переменных. Дамасская фирма Informat впервые в торговой практике предоставляет в распоряжении покупателей 13 рабочих станций, установленных в холле своего офиса, на которых проводятся бесплатные 15-минутные консультации с целью помочь покупателям выбрать компьютер, в наибольшей степени отвечающий их потребностям и бюджету. Кроме того, компания  Boeing применяет ЭС для проектирования космических станций, а также для выявления причин отказов самолетных двигателей и ремонта вертолетов. Экспертная система  XCON, созданная фирмой DEC, служит для определения или изменения конфигурации компьютерных систем типа VAX и в соответствии с требованиями покупателя. Фирма DEC разрабатывает более мощную систему XSEL, включающую базу знаний системы XCON, с целью оказания помощи покупателям при выборе вычислительных систем с нужной конфигурацией. В отличие от XCON система XSEL является интерактивной.

г) Интерпретация.

Интерпретирующие системы обладают способностью получать определенные заключения на основе результатов наблюдения. Система PROSPECTOR, одна из наиболее известных систем интерпретирующего типа, объединяет знания девяти экспертов. Используя сочетания девяти методов экспертизы, системе удалось обнаружить залежи руды стоимостью в миллион долларов, причем наличие этих залежей не предполагал ни один из девяти экспертов. Другая интерпретирующая система- HASP/SIAP. Она определяет местоположение и типы судов в тихом океане по данным акустических систем слежения.

д) Контроль и управление.

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

е) Диагностика неисправностей в механических и электрических устройствах.

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

ж) Обучение.   

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

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

 Критерий использования ЭС для решения задач:

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

1. Данные и знания надежны и не меняются со временем.

2. Пространство возможных решений относительно невелико.

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

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

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

 

Таблица 1. Критерий применимости ЭС.

 

 

В целом ЭС не рекомендуется применять для решения следующих типов задач:

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

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

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

 

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

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

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

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

3. Навыки системы не возрастают после сеанса экспертизы.

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

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

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

7. В тех областях, где отсутствуют эксперты (например, в астрологии), применение ЭС оказывается невозможным.

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

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

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

 

Преимущества ЭС перед человеком – экспертом:

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

1. У них нет предубеждений.

2. Они не делают поспешных выводов.

3. Эти системы работают систематизировано, рассматривая все детали, часто выбирая наилучшую альтернативу из всех возможных.

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

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

6. Эти системы не заменяют специалиста, а являются инструментом в его руках.

 

 Проблемы, возникающие при создании ЭС. Перспективы разработки:

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

Каталог ЭС и инструментальных  программных средств для их разработки, опубликованный в США в 1987 году, содержит более 1000 систем (сейчас их уже значительно больше). В развитых зарубежных странах сотни фирм занимаются их разработкой и внедрением. Имеются и отечественные разработки ЭС, в том числе - нашедший промышленное применение.

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

Первая трудность возникает в связи с постановкой задач. Большинство заказчиков, планируя разработку ЭС, вследствие недостаточной компетентности в вопросах применения методов ИИ, склонна значительно преувеличивать ожидаемые возможности системы. Заказчик желает увидеть в ней самостоятельно мыслящего эксперта в исследуемой области, способного решать широкий круг задач. Отсюда и типичные первоначальные постановки задачи по созданию ЭС: “Разработать ЭС по обработке изображения”; “Создать медицинские ЭС по лечению заболеваний опорно-двигательного аппарата у детей”. Однако, как уже отмечалось, мощность эвристических методов решения задач при увеличении общности их постановки резко уменьшается. Поэтому наиболее целесообразно (особенно при попытке создания ЭС в области, для которой у разработчиков еще нет опыта создания подобных систем) ограничиться для начала не слишком сложной обозримой задачей в рассматриваемой области, для решения которой нет простого алгоритмического способа (то есть неочевидно, как написать программу для решения этой задачи, не используя методы обработки знаний). Кроме того, важно, чтобы уже существовала сложившаяся методика решения этой задачи “вручную” или какими-либо расчетными методами. Для успешной разработки ЭС необходимы не только четкая и конкретная постановка задач, но и разработка подробного (хотя бы словесного) описания “ручного” (или расчетного) метода ее решения. Если это сделать затруднительно, дальнейшая работа по построению ЭС теряет смысл.

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

Таким образом, выясняется, что для разработки ЭС необходимо участие в ней особого рода специалистов, обладающих указанной совокупностью знаний и выполняющих функции “посредников” между экспертами в предметной области и компьютерными (экспертными) системами. Они получили название инженеры знаний (в оригинале - knowledge engineers), а сам процесс разработки ЭС и других интеллектуальных программ, основанных на представлении и обработке знаний - инженерией знаний (knowledge engineering). В развитых зарубежных странах специальность “инженер знаний” введена во многих вузах, в нашей стране основы инженерии знаний изучаются пока в рамках специализаций по системному программированию. Функции эксперта и инженера знаний редко совмещаются в одном лице. Чаще функции инженера знаний выполняет разработчик ЭС. Как показал опыт многих разработок, для первоначального приобретения знаний, в которых участвуют эксперты, инженеры знаний и разработчики ЭС, требуется активная работа всех трех категорий специалистов. Она может длиться от нескольких недель до нескольких месяцев.

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

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

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

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

Рассмотрим факторы, стимулировавшие развитие систем с базами знаний:

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

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

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

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

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

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

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

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

При разработке систем автоматизированного проектирования (САПР) уже нельзя обойтись без ЭС; их использование признано экономически выгодным.

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

    Структура ЭС изображена на схеме:

 

 

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

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

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

 

Подсистема приобретения знаний

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

 

База знаний

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

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

 

(АТРИБУТ  ОБЪЕКТ  ЗНАЧЕНИЕ).

 

Такой факт означает, что заданный объект имеет заданный атрибут   (свойства) с заданным значением. Например, тройка (ТЕМПЕРАТУРА  ПАЦИЕНТ1  37.5) представляет факт «температура    больного, обозначаемого ПАЦИЕНТ1, равна 37.5». В более простых случаях факт выражается неконкретным значением атрибута, а каким либо простым утверждением, которое может быть истинным или ложным, например: «Небо покрыто тучами». В таких случаях факт можно обозначить каким-либо кратким именем (например, ТУЧИ) или использовать для представления факта сам текст соответствующей фразы.

Правила в базе знаний имеют вид:

ЕСЛИ А  ТО  S, где.  А - условие; S- действие. Действие S исполняется, если А истинно. Наиболее часто действие S, так же, как и условие, представляет собой утверждение, которое может быть выведено системой (то есть становится ей известной), если истинно условие правила А.

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

Простой пример правила из повседневной жизни:

        ЕСЛИ небо покрыто тучами

        ТО скоро пойдет дождь.

В качестве условия A может выступать либо факт (как в данном примере), либо несколько фактов A1,...,AN, соединенные логической операцией  и:

        A1 и A2 и ... и AN.

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

       ЕСЛИ

             небо покрыто тучами и барометр падает

       ТО

             скоро пойдет дождь.       (Правило 1).

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

 Если система не может вывести некоторый факт, истинность или ложность которого требуется установить, то система спрашивает о нем пользователя. Например:

      ВЕРНО ЛИ, ЧТО небо покрыто тучами?

При получении положительного ответа от пользователя факт «Небо покрыто тучами» включается в рабочем множество.

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

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

 

Подсистема вывода

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

Цель ЭС - вывести некоторый заданный факт, который называется целевым утверждением (то есть в результате применения правил добиться того, чтобы этот факт был включен в рабочее множество), либо опровергнуть этот факт (то есть убедиться, что его вывести невозможно, следовательно, при данном уровне знаний системы он является ложным). Целевое утверждение может быть либо «заложено» заранее в базу знаний системы, либо извлекается системой из диалога с пользователем.

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

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

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

        ЕСЛИ скоро пойдет дождь

        ТО  нужно взять с собой зонтик.    (правило 2)

Предположим также, что факты «Небо покрыто тучами» и «Барометр падает» имеются в рабочем множестве, а целью системы является ответ на вопрос пользователя:

  «Нужно взять с собой зонтик?»

При прямом выводе работа системы будет протекать следующим образом:

Шаг 1. Рассматривается правило 1. Его условие истинно, так как оба элемента конъюнкции имеются в рабочем множестве. Применяем правило 1; добавляем к рабочему множеству факт ”Скоро пойдет дождь”.

Шаг 2. Рассматривается правило 2. Его условие истинно, т.к. утверждение из условия имеется в рабочем множестве. Примеряем правило 2; добавляем к рабочему множеству факт “Нужно взять с собой зонтик”. Целевое утверждение выведено.

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

В рассматриваемом примере вывод целевого утверждения “Нужно взять с собой зонтик” обратной цепочкой рассуждений выполняется следующим образом:

Шаг 1. Рассматривается правило 1. Оно не содержит цели в правой части. Переходим к правилу 2.

Шаг 2. Рассматривается правило 2. Оно содержит цель в правой части правила. Переходим к правой части правила и рассматриваем в качестве текущей цели утверждения  “Скоро пойдет дождь”.

Шаг 3. Текущей цели нет в рабочем множестве. Рассмотрим правило 1, которое содержит цель в правой части. Обе компоненты его условия имеются в рабочем множестве, так что условие истинно. Применяем привило 1; в результате выводим утверждение “Скоро пойдет дождь”; которое было нашей предыдущей целью.

Шаг 4. Применяем правило 2, условием которого является данное утверждение. Получаем вывод исходного утверждения.

Заметим, что для упрощения ситуации мы предположили, что в обоих случаях факты “Небо покрыто тучами”  и “Барометр падает” уже известны системе. На самом деле система выясняет истинность или ложность факта, входящего в условие некоторого правила, спрашивая об этом пользователя в тот момент, когда она пытается применить правило.

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

 

 

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

 

 Компонент вывода

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

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

 

Мэри искала ключ.

 

Здесь для слова «ключ» допустимы как минимум два значения «родник» и «ключ от квартиры». В следующих же двух предложениях одно и то же слово имеет совершенно разные значения:

Мы заблудились в чаще.

Нужно чаще ходить в театр.

 

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

 

ЕСЛИ     Белый автомобиль легко заметить ночью

И         Автомобиль Джека белый

ТО       Автомобиль Джека легко заметить ночью

 

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

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

 

Управляющий компонент

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

1. Сопоставление- образец правила сопоставляется с имеющимися фактами;

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

3. Срабатывание - если образец правила при сопоставлении совпал с какими- либо фактами из рабочего множества, то правило срабатывает.

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

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

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

   

 

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

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

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

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

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

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

Участие пользователя выражается в следующем:

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

- общение. Интерфейс пользователя должен соответствовать словарю пользователя и уровню его подготовки;

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

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

 

 Диалог с ЭС. Объяснение

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

Итак, на примере простой ЭС и базы знаний диалог пользователя с системой можно представить себе следующим образом:

Система: Вы хотите узнать, нужно ли взять с собой зонтик?

Пользователь:  Да.

Система:            Верно ли, что небо покрыто тучами?

Пользователь:  Да.

Система:            Верно ли, что барометр падает?

 Пользователь:  Да.

 Система: (после некоторого “размышления”) Нужно взять с собой зонтик.

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

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

Чтобы удостовериться в “разумности” и “компетентности” ЭС, пользователь может обратиться к ее подсистеме объяснения.

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

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

     

 

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

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

Рассмотрим теперь работу подсистемы объяснения. Для получения объяснения в процессе консультации пользователь может “перехватить инициативу” диалога в тот момент, когда система задает очередной вопрос, “переспросив” в ответ систему, почему она его задала. Таким образом, вместо ответа на вопрос системы, пользователь может задать ей встречный вопрос:

 

ПОЧЕМУ?

 

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

Пусть в нашем примере диалога с ЭС пользователь вместо ответа на вопрос системы: “Верно ли, что барометр падает?” задает ей встречный вопрос: ”ПОЧЕМУ?”. ЭС обращается к подсистеме объяснения, которая выдает пользователю следующее сообщение:

 [1.0]  Эта информация необходима, чтобы установить, что скоро пойдет дождь.

   Ранее было установлено, что:

 [1.1]  Небо покрыто тучами.

   Следовательно, если:

 [1.2]  Барометр падает, то скоро пойдет дождь.

    (Правило 1).

Двойные номера в квадратных скобках имеют следующий смысл. Для облегчения работы пользователя подсистема объяснения нумерует свои ответы (номер ответа, в данном случае - 1. является первой цифрой номера), а в каждом ответе - нумерует также утверждения, о которых в нем идет речь. Пользователь может использовать двойные номера для ссылок на утверждения, не выписывая их явно. Например, номер 1.1 обозначает утверждение “Небо покрыто тучами”.

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

ПОЧЕМУ?

(“Почему необходимо установить, что скоро пойдет дождь?”). Второй ответ системы аналогичен первому; в нем указывается, что это необходимо для применения правила 2 с целью установить, что нужно взять с собой зонтик:

[2.0] Эта информация необходима, чтобы установить, что нужно взять с собой зонтик. Если:

[2.1] Скоро пойдет дождь, то нужно взять с собой зонтик.

(Правило 2).

Утверждение [2.0] является исходным целевым утверждением системы. Таким образом, теперь ход рассуждений системы пользователю полностью понятен. Вопрос “ПОЧЕМУ?” позволяет проследить ход рассуждений системы от посылок к заключениям. Однако для более детального осмысления процесса вывода удобно было бы иметь возможность изучать его и в противоположном порядке - от заключений к посылкам. Для этого служит другой вопрос, который также “понимает” подсистема объяснений:

КАК  N?

где N- номер утверждения, выданный подсистемой объяснения на одном из предыдущих шагов диалога. Например, в ответ на вопрос:

КАК   2.0?

“Как получен утверждение 2.0?” подсистема объяснения выдает информацию в правиле, которое было применено для его получения:

[3.1] Используется правило 2, заключением которого является,                             что нужно взять с собой зонтик.

Чтобы получить более подробную информацию о том, как было использовано правило 2, следует повторно задать вопрос “КАК?”:

 КАК  3.1?

“Как было использовано правило 2?”. Ответ системы:

Ранее установлено, что:

[4.1] Скоро пойдет дождь.

Следовательно, нужно взять с собой зонтик.

Выясним теперь, как получено утверждение 4.1:

КАК 4.1?

Ответ системы:

  [5.1] Используется правило 1, заключением которого является, что скоро пойдет дождь. Наконец, выясним, как использовано правило 1:

КАК 5.1?

Ответ системы:

Ранее установлено, что:

[6.1] Небо покрыто тучами.

[6.2] Барометр падает.

Следовательно, скоро пойдет дождь.

Как были получены утверждения 6.1 и 6.2 пользователь помнит, поскольку он отвечал на вопросы системы относительно этих утверждений. Если все же он задаст системе вопрос  КАК 6.1? или  КАК 6.2?, то система напомнит ему об этом.

Описанная модель объяснения используется в системе MYCIN. Достоинством ее является возможность получения объяснения любого шага работы системы, недостатком - жесткая привязка к дереву вывода. Для пользователя- непрограммиста такой способ объяснения может показаться излишне детализованным и слишком формальным, а нужно было бы объяснение на “более высоком уровне”- с точки зрения здравого смысла и без углубления в детали. Подобные модели объяснения только начинают появляться в ЭС и требуют более сложной организации знаний.

 

Разработка стратегии

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

При разработке стратегии управления выводом необходимо ответить на два вопроса:

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

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

 

 Повышение эффективности поиска

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

 а) Сопоставление методов поиска в глубину и ширину.

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

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

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

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

 б)  Альфа-бета алгоритм.     

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

 в)  Разбиение на подзадачи.        

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

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

Рассмотрим, например, задачу о проезде на автомобиле из Пало-Альто (штат Калифорния) в Кембридж (штат Массачусетс). Эта задача может быть сведена, скажем, к следующим подзадачам:

Подзадача 1. Проехать из Пало-Альто в Сан-Франциско.

Подзадача 2.Проехать из Сан-Франциско в Чикаго.

Подзадача 3. Проехать из Чикаго в Олбани.

Подзадача 4. Проехать из Олбани в Кембридж.

Здесь решение всех четырех подзадач обеспечило бы некоторое решение первоначальной задачи.

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

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

г)  Использование формальной логики при решении задач.    

Часто для решения задач либо требуется проведение логического анализа в определенном объеме, либо поиск решения существенно отличается после такого анализа. Иногда такой анализ показывает, что определенные проблемы неразрешимы. В игре в пятнадцать, например, можно доказать, что целевая конфигурация (1) не может быть получена из начальной конфигурации (2).

 

    

 

 

Представление задач в пространстве состояний

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

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

       

Операторы. Состояния и операторы

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

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

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

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

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

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

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

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

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

а) форму описания состояний и, в частности, описание начального состояния;

б) множество операторов и их воздействий  на описания состояний;

в) свойства описания целевого состояния.

Пространство состояний полезно представлять себе в виде направленного графа.

 

Запись в виде графа

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

Последовательность вершин n_i1,n_i2,...,n_ik., в которой каждая вершина n_ij  дочерняя для n_i,j-1, j=2,k, называется путем длины k от вершины n_i1, к вершине n_ik. Если существует путь, ведущий от вершины n_i  к вершине n_j, то вершину n_j  называют достижимой из вершины n_i  или потомком вершины n_i . В этом случае вершина n_i называется также предком для вершины n_j. Видно, что проблема нахождения последовательности операторов, преобразующих одно состояние в другое, эквивалентна задаче поиска пути на графе.

 

Методы поиска в пространстве состояний

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

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

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

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

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

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

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

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

 

Методы перебора

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

 1)  Поместить вершину в список, называемый ОТКРЫТ.

 2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу.

 3) Взять первую вершину из списка ОТКРЫТ и перенести ее в список ЗАКРЫТ; назовем эту вершину n.

 4) Раскрыть вершину n, образовав все вершины, непосредственно следующие за n. Если непосредственно следующих вершин нет, то переходить сразу же к шагу (2). Поместить имеющиеся непосредственно следующие за n вершины в конец списка ОТКРЫТ и построить указатели, ведущие от них назад к вершине n.   

 5) Если какие-нибудь из этих непосредственно следующих за n вершин являются целевыми вершинами, то на выход выдать решение, получающееся просмотром вдоль указателей; в противном случае переходить к шагу (2).

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

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

 

Метод равных цен

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

В методе равных цен для каждой вершины n в дереве перебора нам нужно помнить стоимость пути, построенного от начальной вершины s к вершине n. Пусть g(n)-  стоимость от вершины s к вершине n в дереве перебора. В случае деревьев перебора мы можем быть уверены, что g(n) является к тому же стоимостью того пути, который имеет минимальную стоимость (т.к. этот путь единственный). 

В методе равных цен вершины раскрываются в порядке возрастания стоимости g(n). Этот метод характеризуется такой последовательностью шагов:

1)  Поместить  начальную вершину s в список, называемый ОТКРЫТ. Положить g(s)=0.

 2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае переходить к следующему шагу.

 3) Взять из списка ОТКРЫТ ту вершину, для которой величина g имеет наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине название n. (В случае совпадения значений выбирать вершину с минимальными g произвольно, но всегда отдавая предпочтение целевой вершине.)

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

 5) Раскрыть вершину n, построив все непосредственно следующие за ней вершины. (Если таковых нет переходить к шагу (2).) Для каждой из такой непосредственно следующей (дочерней) вершины n_i вычислить стоимость g(n), положив g(n_i)=g(n)+c(n,n_i). Поместить эти вершины вместе с соответствующими им только что найденными значениями g в список ОТКРЫТ и построить указатели, идущие назад к n.

 6) Перейти к шагу (2).

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

    Алгоритм, работающий по методу равных цен, может быть также использован для поиска путей минимальной длины, если просто положить стоимость каждого ребра равной единице. Если имеется несколько начальных вершин, то алгоритм просто модифицируется: на шаге (1) все начальные вершины помещаются в список ОТКРЫТ. Если состояния, отвечающие поставленной цели, могут быть описаны явно, то процесс перебора можно пустить в обратном направлении, приняв целевые вершины в качестве начальных и используя обращение оператора Г.     

 

 

Метод перебора в глубину

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

1) Глубина корня дерева равна нулю.

2) Глубина любой последующей вершины равна единице плюс глубина вершины, которая непосредственно ей предшествует.

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

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

 Метод перебора в глубину определяется следующей последовательностью шагов:

 1)  Поместить  начальную вершину в список, называемый ОТКРЫТ.

 2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в противном случае перейти к  шагу (3).

 3) Взять первую вершину из списка ОТКРЫТ и перенести в список ЗАКРЫТ. Дать этой вершине название n.

 4) Если глубина вершины n равна граничной глубине, то переходить к (2), в противном случае к (5).   

 5) Раскрыть вершину n, построив все непосредственно следующие за ней вершины. Поместить их (в произвольном порядке) в начало списка ОТКРЫТ и построить указатели, идущие от них к n.

 6) Если одна из этих вершин целевая, то на выход выдать решение, просматривая для этого соответствующие указатели, в противном случае переходить к шагу (2).

   

На рис.8 приведена блок- схема для метода перебора в глубину.

 

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

 

Изменение при переборе на произвольных графах

При переборе на графах, а не на деревьях, нужно внести некоторые естественные изменения в указанные алгоритмы. В простом методе полного перебора не нужно вносить никаких изменений, следует лишь проверять, не находиться ли уже вновь построенная вершина в список ОТКРЫТ или ЗАКРЫТ по той причине, что она уже строилась раньше в результате раскрытия какой- то вершины. Если это так, то ее не нужно вновь помещать в список ОТКРЫТ.

Прежде чем делать какие- либо изменения в алгоритме перебора в глубину, нужно нужно решить, что понимать под глубиной вершины в графе. Согласно обычному определению, глубина вершины равна единице плюс глубина наиболее близкой родительской вершины, причем глубина начальной вершины предполагается равной нулю. Тогда поиск в глубину можно было бы получить, выбирая для раскрытия самую глубокую вершину списка ОТКРЫТ (без превышения граничной глубины). Когда порождаются вершины, уже имеющиеся в списке ОТКРЫТ, либо в списке ЗАКРЫТ, пересчет глубины такой вершины может оказаться необходимым.

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

 

Обсуждение эвристической информации

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

Для многих задач можно сформулировать правила, позволяющие уменьшить объем перебора. Все такие правила, используемые для ускорения поиска, зависят от специфической информации о задаче, представляемой в виде графа. Будем называть такую информацию эвристической информацией  (помогающей найти решение) и называть использующие ее процедуры поиска эвристическими методами поиска. Один из путей уменьшить перебор состоит в выборе более “информированного”  оператора  Г, который не строит много не относящихся к делу вершин. Этот способ применим как в методе полного перебора, так и в методе перебора в глубину. Другой путь состоит в использовании эвристической информации для модификации шага (5) алгоритма перебора в глубину. Вместо того, чтобы размещать вновь построенные вершины в произвольном порядке в начале списка ОТКРЫТ, их можно расположить в нем некоторым определенным образом, зависящим от эвристической информации. Так, при переборе в глубину в первую очередь будет раскрываться та вершина, которая представляется наилучшей.

Более гибкий (и более дорогой) путь использования эвристической информации состоит в том, чтобы, согласно некоторому критерию, на каждом шаге переупорядочивать вершины списка ОТКРЫТ. В этом случае перебор мог бы идти дальше в тех участках границы, которые представляются наиболее перспективными. Для того, чтобы применить процедуру упорядочения, нам необходима мера, которая позволяла бы оценивать “перспективность” вершин. Такие меры называют оценочными функциями.

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

 

 Использование оценочных функций

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

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

Условимся располагать вершины, предназначенные для раскрытия, в порядке возрастания их значений функции f. Тогда можно использовать некоторый алгоритм (подобный алгоритму равных цен), в котором для очередного раскрытия выбирается та вершина списка ОТКРЫТ, для которой значение f оказывается наименьшим. Будем называть такую процедуру алгоритм упорядоченного перебора.

Чтобы этот алгоритм упорядоченного перебора был применен для перебора на произвольных графах (а не только на деревьях), необходимо предусмотреть в нем возможность работы в случае построения вершин, которые уже имеются либо в списке ОТКРЫТ, либо в списке ЗАКРЫТ. При использовании некоторой произвольной функции f нужно учесть, что величина f для некоторой вершины из списка ЗАКРЫТ может понизиться, если к ней найден новый путь (f(n) может зависеть от пути из s к n даже для вершин из списка ЗАКРЫТ). Следовательно, мы должны тогда перенести такие вершины назад в список  ОТКРЫТ и позаботиться об изменении направлений  соответствующих указателей.       

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

1) Поместить начальную вершину s в список, называемый ОТКРЫТ, и вычислить f(s).

2) Если список  ОТКРЫТ пуст, то на выход дается сигнал о неудаче; в противном случае переходи к следующему этапу.

3) Взять из списка ОТКРЫТ ту вершину, для которой f имеет наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине название n. (В случае совпадения значений выбирать вершину с минимальными f произвольно, но всегда отдавая предпочтение целевой вершине.)

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

 5) Раскрыть вершину n, построив все непосредственно следующие за ней вершины. (Если таковых нет переходить к шагу (2).) Для такой дочерней вершины n_i вычислить значение f(n_i).

6) Связать с теми из вершин n_i , которых еще нет в списках ОТКРЫТ или ЗАКРЫТ, только что прочитанные значения f(n_i). Поместить эти вершины в список ОТКРЫТ и провести от них к вершине n указатели.

7) Связать с теми  из непосредственно следующих за n вершинами. которые уже были в списке  ОТКРЫТ или ЗАКРЫТ, меньшие из прежних или только что вычисленных значений f. Поместить в список ОТКРЫТ  те из непосредственно следующих за n вершин, для которых новое значение f оказалось ниже, и изменить направление указателей от всех вершин, для которых значение f уменьшилось, направив их к n..

8) Перейти к (2).

Общая структура алгоритма идентична структуре алгоритма равных цен (см. рис. 7), поэтому мы не приводим для него блок-схему. Отметим, что множество вершин и указателей, порождаемых этим алгоритмом, образует дерево (дерево перебора), причем на концах этого дерева расположены вершины из списка ОТКРЫТ.

 

Перебор этапами

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

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

 

Ограничение числа дочерних вершин

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

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

 

 Поочередное построение дочерних вершин

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

Причины, приведшие СИИ к коммерческому успеху, следующие.

Интегрированность. Разработаны инструментальные средства искусственного интеллекта (ИС ИИ), легко интегрирующиеся с другими информационными технологиями и средствами (с CASE, СУБД, контроллерами, концентраторами данных и т.п.).

Открытость и переносимость. ИС ИИ разрабатываются с соблюдением стандартов, обеспечивающих открытость и переносимость [14].

Использование языков традиционного программирования и рабочих станций. Переход от ИС ИИ, реализованных на языках ИИ (Lisp, Prolog и т.п.), к ИС ИИ, реализованным на языках традиционного программирования (С, C++ и т.п.), упростил обеспечение интегрированности, снизил требования приложений ИИ к быстродействию ЭВМ и объемам оперативной памяти. Использование рабочих станций (вместо ПК) резко увеличило круг приложений, которые могут быть выполнены на ЭВМ с использованием ИС ИИ.

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

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

Структура экспертных систем

Типичная статическая ЭС состоит из следующих основных компонентов (рис. 1.):

·                    решателя (интерпретатора);

·                    рабочей памяти (РП), называемой также базой данных (БД);

·                    базы знаний (БЗ);

·                    компонентов приобретения знаний;

·                    объяснительного компонента;

·                    диалогового компонента.

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

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

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

Компонент приобретения знаний автоматизирует процесс наполнения ЭС знаниями, осуществляемый пользователем-экспертом.

Объяснительный компонент объясняет, как система получила решение задачи (или почему она не получила решение) и какие знания она при этом использовала, что облегчает эксперту тестирование системы и повышает доверие пользователя к полученному результату.

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

В разработке ЭС участвуют представители следующих специальностей:

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

 

 

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

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

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

Программист разрабатывает ИС (если ИС разрабатывается заново), содержащее в пределе все основные компоненты ЭС, и осуществляет его сопряжение с той средой, в которой оно будет использовано.

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

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

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

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

"Почему система задает тот или иной вопрос?", "как ответ, собираемый системой, получен?".

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

 

На рис. 1.2 показано, что в архитектуру динамической ЭС по сравнению со статической ЭС вводятся два компонента: подсистема моделирования внешнего мира и подсистема связи с внешним окружением. Последняя осуществляет связи с внешним миром через систему датчиков и контроллеров. Кроме того, традиционные компоненты статической ЭС (база знаний и машина вывода) претерпевают существенные изменения, чтобы отразить временную логику происходящих в реальном мире событий.

Подчеркнем, что структура ЭС, представленная на рис. 1.1 и 1.2, отражает только компоненты (функции), и многое остается "за кадром". На рис. 1.3 приведена обобщенная структура современного ИС для создания динамических ЭС, содержащая кроме основных компонентов те возможности, которые позволяют создавать интегрированные приложение в соответствии с современной технологией программирования.

 

Этапы разработки экспертных систем

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

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

1) существуют эксперты в данной области, которые решают задачу значительно лучше, чем начинающие специалисты;

2) эксперты сходятся в оценке предлагаемого решения, иначе нельзя будет оценить качество разработанной ЭС;

3) эксперты способны вербализовать (выразить на естественном языке) и объяснить используемые ими методы, в противном случае трудно рассчитывать на то, что знания экспертов будут "извлечены" и вложены в ЭС;

4) решение задачи требует только рассуждений, а не действий;

5) задача не должна быть слишком трудной (т.е. ее решение должно занимать у эксперта несколько часов или дней, а не недель);

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

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

Использование ЭС в данном приложении может быть возможно, но не оправдано. Применение ЭС может быть оправдано одним из следующих факторов:

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

Приложение соответствует методам ЭС, если решаемая задача обладает совокупностью следующих характеристик:

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

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

3) задача должна быть достаточно сложна, чтобы оправдать затраты на разработку ЭС. Однако она не должна быть чрезмерно сложной (решение занимает у эксперта часы, а не недели), чтобы ЭС могла ее решать;

4) задача должна быть достаточно узкой, чтобы решаться методами ЭС, и практически значимой.

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

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

В ходе работ по созданию ЭС сложилась определенная технология их разработки, включающая шесть следующих этапов (рис. 1.4):

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

 

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

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

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

 

 

 

Интерфейс с конечным пользователем

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

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

Интерфейс с пользователем TDC Expert ограничен возможностями системы TDC 3000, т.е. взаимодействие с конечным пользователем ограничивается текстовым режимом работы.

 

Представление знаний в экспертных системах

Первый и основной вопрос, который надо решить при представлении знаний, - это вопрос определения состава знаний, т.е. определение того, "ЧТО ПРЕДСТАВЛЯТЬ" в экспертной системе. Второй вопрос касается того, "КАК ПРЕДСТАВЛЯТЬ" знания. Необходимо отметить, что эти две проблемы не являются независимыми. Действительно, выбранный способ представления может оказаться непригодным в принципе либо неэффективным для выражения некоторых знаний.

По нашему мнению, вопрос "КАК ПРЕДСТАВЛЯТЬ" можно разделить на две в значительной степени независимые задачи: как организовать (структурировать) знания и как представить знания в выбранном формализме.

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

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

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

В соответствии с общей схемой статической экспертной системы (см. рис. 1.1) для ее функционирования требуются следующие знания:

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

Для динамической ЭС, кроме того, необходимы следующие знания:

1) знания о методах взаимодействия с внешним окружением;

2) знания о модели внешнего мира.

Зависимость состава знаний от требований пользователя проявляется в следующем:

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

Состав знаний о языке общения зависит как от языка общения, так и от требуемого уровня понимания.

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

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

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

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

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

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

2) метазнания используются для обоснования целесообразности применения правил из области экспертизы;

3) метаправила используются для обнаружения синтаксических и семантических ошибок в предметных правилах;

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

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

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

• организация знаний по уровням представления и по уровням детальности;
• организация знаний в рабочей памяти;
• организация знаний в базе знаний.

 

Уровни представления и уровни детальности

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

Число уровней представления может быть больше двух. Второй Уровень представления содержит сведения о знаниях первого уровня, т.е. знания о представлении базовых понятий первого уровня. Разделение знаний по уровням представления обеспечивает расширение области применимости системы.

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

 

Организация знаний в рабочей системе

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

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

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

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

 

Организация знаний в базе данных

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

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

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

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

Операция сопоставления может использоваться не только как средство выбора нужного объекта из множества кандидатов; она может быть использована для классификации, подтверждения, декомпозиции и коррекции. Для идентификации неизвестного объекта он может быть сопоставлен с некоторыми известными образцами. Это позволит классифицировать неизвестный объект как такой известный образец, при сопоставлении с которым были получены лучшие результаты. При поиске сопоставление используется для подтверждения некоторых кандидатов из множества возможных. Если осуществлять сопоставление некоторого известного объекта с неизвестным описанием, то в случае успешного сопоставления будет осуществлена частичная декомпозиция описания.

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

 

Методы поиска решений в экспертных системах

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

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

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

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

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

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

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

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

 

Инструментальный Комплекс Для Создания Статических Экспертных Систем (На Примере Интегрированного Комплекса Эко)

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

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

На основе комплекса ЭКО было разработано более 100 прикладных экспертных систем. Среди них отметим следующие:

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

 

Средства представления знаний и стратегии управления

Комплекс ЭКО включает три компонента.

Ядром комплекса является интегрированная оболочка экспертных систем ЭКО, которая обеспечивает быстрое создание эффективных приложений для решения задач анализа в статических проблемных средах типа 1 и 2.

При разработке средств представления знаний оболочки преследовались две основные цели: эффективное решение достаточно широкого и практически значимого класса задач средствами персональных компьютеров; гибкие возможности по описанию пользовательского интерфейса и проведению консультации в конкретных приложениях. При представлении знаний в оболочке используются специализированные (частные) - утверждения типа "атрибут - значение" и частные правила, что позволяет исключить ресурсоемкую операцию сопоставления по образцу и добиться эффективности разрабатываемых приложений. Выразительные возможности оболочки удалось существенно расширить за счет интегрированности, обеспечиваемой путем вызова внешних программ через сценарий консультации и стыковки с базами данных (ПИРС и dBase IV) и внешними программами. В оболочке ЭКО обеспечивается слабая структуризация БЗ за счет ее разделения на отдельные компоненты - для решения отдельных подзадач в проблемной среде - модели (понятию "модель" ЭКО соответствует понятие "модуль" базы знаний системы G2).

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

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

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

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

 

Инструментальный комплекс для создания экспертных систем реального времени (на примере интегрированной среды g2-gensym corp., США)

История развития ИС для создания ЭС реального времени началась в 1985 г., когда фирма Lisp Machine Inc. выпустила систему Picon для символьных ЭВМ Symbolics. Успех этого ИС привел к тому, что группа ведущих разработчиков Picon в 1986 г. образовала частную фирму Gensym, которая, значительно развив идеи, заложенные в Picon, в 1988 г. вышла на рынок с ИС под названием G2, версия 1.0. В настоящее время функционирует версия 4.2 и готовится к выпуску версия 5.0.

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

С отставанием от Gensym на 2 - 3 года другие фирмы начали создавать свои ИС для ЭС РВ. С точки зрения независимых экспертов NASA, проводивших комплексное исследование характеристик и возможностей некоторых из перечисленных систем, в настоящее время наиболее продвинутым ИС, безусловно, остается G2 (Gensym, США); следующие места со значительным отставанием (реализовано менее 50% возможностей G2) занимают RTWorks - фирма Talarian (США), COMDALE/C (Comdale Techn. - Канада), COGSYS (SC - США), ILOG Rules (ILOG - Франция).

Классы задач, для которых предназначена G2 и подобные ей системы:

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

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

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

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

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

• интеллектуальное управление производством - G2, G2 Diagnostic Assistant (GDA), NeurOn-Line (NOL), Statistical Process Control (SPC), BatchDesign_Kit;
• оперативное планирование - G2, G2 Scheduling Toolkit (GST), Dynamic Scheduling Packadge (DSP);
• разработка и моделирование производственных процессов - G2, ReThink, BatchDesign_Kit;
• управление операциями и корпоративными сетями - G2, Fault Expert.

Несмотря на то, что первая версия системы G2 появилась не так давно - в 1988 г., ее даже в богатой Америке никто не назовет дешевой. G2 можно назвать бестселлером на рынке программных продуктов - на начало 1996 г. в мире было установлено более 5000 ее копий. Фирма Gensym обслуживает более 30 отраслей - от аэрокосмических исследований до производства пищевых продуктов. Список пользователей G2 выглядит как справочник Who-Is-Who в мировой промышленности. 25 самых крупных индустриальных мировых корпораций используют G2. На базе G2 написано более 500 действующих приложений.

Чем же объясняется успех инструментального комплекса G2? Прежде всего, G2 - динамическая система в полном смысле этого слова. G2 - это объектно-ориентированная интегрированная среда для разработки и сопровождения приложений реального времени, использующих базы знаний. G2 функционирует на большинстве существующих платформ (табл.9.1). База знаний G2 сохраняется в обычном ASCII-файле, который однозначно интерпретируется на любой из поддерживаемых платформ.

 

Таблица 9.1 Платформы, на которых функционирует G2

 

 

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