Математические методы, алгоритмы и программные системы для решения прикладных задач качественного характера при логическом представлении нечетких знаний тема диссертации и автореферата по ВАК РФ 05.13.11, доктор технических наук Серов, Владимир Васильевич

• Серов, Владимир Васильевич
• доктор технических наук
• 1997

Оглавление диссертации доктор технических наук Серов, Владимир Васильевич

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЙ

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

с применением ЭВМ

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

1.3. Математические методы и системы для решения прикладных

задач качественного характера

1.4. Описание постановки задач исследований

и последовательности их решения

1.5. Выводы

2. РЕШЕНИЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО СИНТЕЗА И АНАЛИЗА МОЛЕКУЛЯРНЫХ СТРУКТУР МЕТОДАМИ ДИСКРЕТНОЙ МАТЕМАТИКИ

2.1. Постановка задачи и ее практическое значение

2.2. Алгоритм генерации полного набора матриц смежности неизоморфных графов

2.3. Алгоритм анализа матриц смежности по их топологическим особенностям

2.4. Система математического синтеза и анализа молекулярных структур МАИСС

2.5. Примеры применения системы МАИСС

2.6. Выводы

3. РЕШЕНИЕ ЗАДАЧИ ИДЕНТИФИКАЦИИ СТРУКТУР МНОГОАТОМНЫХ МОЛЕКУЛ ПО СПЕКТРОХИМИЧЕСКИМ ДАННЫМ ПРИ ТАБЛИЧНО - ПРОДУКЦИОННОЙ ФОРМЕ ПРЕДСТАВЛЕНИЯ НЕЧЕТКИХ ЗНАНИЙ

3.1. Постановка задачи и ее практическое значение

3.2. Система распознавания структур многоатомных молекул РАСТР

3.3. Представление знаний в системе РАСТР

3.4. Примеры решения задач идентификации структур молекул

3.5. Выводы

4. ПРИКЛАДНОЕ ИСЧИСЛЕНИЕ НЕЧЕТКИХ ПРЕДИКАТОВ

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

4.2. Основные определения и свойства

4.3. Дедуктивные вопросы прикладного исчисления нечетких предикатов

4.4. Формальное представление и классификация прикладных

задач качественного характера

4.5. Выводы

5. ФОРМАЛИЗАЦИЯ ЗНАНИЙ И РЕШЕНИЕ КАЧЕСТВЕННЫХ ЗАДАЧ В ОБЛАСТИ МОЛЕКУЛЯРНОЙ СПЕКТРОСКОПИИ

5.1. Формализация знаний

5.2. Решение качественных задач прогнозирования,

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

5.3. Выводы

6. ПРИМЕНЕНИЕ ИСЧИСЛЕНИЯ НЕЧЕТКИХ ПРЕДИКАТОВ ДЛЯ ФОРМАЛИЗАЦИИ ЗНАНИЙ И РЕШЕНИЯ ЗАДАЧ КАЧЕСТВЕННОГО ХАРАКТЕРА В РАЗЛИЧНЫХ ПРЕДМЕТНЫХ ОБЛАСТЯХ

6.1. Управление производственной и коммерческой

деятельностью предприятия

6.2. Задачи оценочного характера

6.2.1. Оценка качества изделий народного потребления

6.2.2. Контроль сроков выполнения решений

6.3. Разработка естественноязыкового интерфейса

6.4. Выводы

7. СИСТЕМНЫЕ ВОПРОСЫ ПРИКЛАДНОЙ ТЕОРИИ РЕШЕНИЯ ЗАДАЧ КАЧЕСТВЕННОГО ХАРАКТЕРА

7.1. Основные понятия и модели, используемые в процессе

решения качественных задач

7.2. Вопросы общения решающих систем

7.3. Цели решающих систем

7.4. Выводы

8. ВОПРОСЫ ПРОГРАММНОЙ РЕАЛИЗАЦИИ МЕТОДОВ РЕШЕНИЯ КАЧЕСТВЕННЫХ ЗАДАЧ В ИСЧИСЛЕНИИ НЕЧЕТКИХ ПРЕДИКАТОВ

8.1. Примеры программ на ТУРБО-ПРОЛОГе, расширенном для 154 нечеткой логики

8.2. Пример решения задачи структурно-группового

анализа в нечеткой логике

8.3. Выводы 198 ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ 199 СПИСОК ЛИТЕРАТУРЫ

Введение диссертации (часть автореферата) на тему «Математические методы, алгоритмы и программные системы для решения прикладных задач качественного характера при логическом представлении нечетких знаний»

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

2. Разработаны методы, алгоритмы и процедуры решения прикладных качественных задач широко распространенных классов: прогнозирования, интерпретации, идентификации и т.д.

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

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

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

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

Научная новизна диссертации заключается в следующем: -решена задача математического синтеза и анализа молекулярных структур методами дискретной математики и разработан комплекс программ МАИСС;

-решена задача идентификации структур многоатомных молекул по спектрохимическим данным при таблично-продукционной форме представления нечетких знаний и разработана экспертная система РАСТР;

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

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

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

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

-приведены примеры формализации знаний и решения качественных задач на языке ТУРБО-ПРОЛОГ, расширенном для нечеткой логики;

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

Достоверность научных положений, выводов и результатов подтверждается:

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

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

-успешным применением разработанных методов при создании экспертных и информационных систем;

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

Более чем 2 0-летнюю работу в рассматриваемой области автор начинал в неформальном творческом коллективе академика РАЕН, д.ф.-м.н., проф.

Л.А.Грибова под его непосредственным руководством и выражает ему искреннюю признательность. Автор благодарен д.х.н., проф. М.Е.Эляшбергу за долговременное и плодотворное сотрудничество, одним из результатов которого было создание экспертных систем МАИСС и РАСТР. За многолетнее сотрудничество автор признателен В.М.Петрову, особо отмечая его вклад в решение проблем естественноязыкового интерфейса. Академику МАИ, д.т.н., проф. В.З.Букрееву автор благодарен за создание творческой атмосферы на руководимой им кафедре информатики, благодаря чему и стало возможным оформить рассматриваемые работы как диссертацию.

Автор глубоко признателен за внимание к работе, обсуждение полученных результатов, ценные замечания по существу и полезные указания по оформлению работы профессорско-преподавательскому составу и сотрудникам Московской Государственной Академии приборостроения и информатики, Московского Государственного инженерно-физического института, кафедры информатики РосЗИТЛП, Института геохимии и аналитической химии РАН, ВЦ СО РАН, Новосибирского института органической химии СО РАН, кафедры физики ТСХА, п/я А1147, ВНИИ органического синтеза, НИИ спецтехники МВД, НИИ материаловедения, где докладывались отдельные результаты и работа в целом.

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

1.СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЙ

1.1. Общая характеристика вопроса представления знаний и методов решения задач прикладного характера с применением ЭВМ.

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

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

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

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

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

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

Исследования в области искусственного интеллекта привели в 70-е годы к идее инженерии знаний а затем и к созданию экспертных систем. Первыми экспертными системами, успешно примененными на практике, были специализированные системы. К ним можно отнести систему DENDRAL [3] (Фейгенбаум, Ледерберг) для установления структур молекул по их масс-спектрам, систему медицинской диагностики MYCIN [4] (Шотлифф). Одновременно была разработана система РАСТР для распознавания структур многоатомных молекул по ИК, ЯМР и некоторым другим спектрам [5,6] (Эляшберг, Серов, Грибов). Относительная успешность практического применения таких экспертных систем привела к резкому росту числа их разработок во всех областях применения ЭВМ.

В специализированных экспертных системах основное внимание уделялось форме представления и конкретному содержанию знаний предметной области. Одновременно и в основном с исследовательскими целями разрабатывались системы общего назначения с акцентом на процедуры поиска решений, которые получили название решателей задач. Это общий решатель задач GPS [7], созданный Ньюэллом, Шоу и Саймоном, вопросно-ответные дедуктивные системы QA3, QA4 [8] Грина, планирующая система STRIPS [9] (Файкс, Нильсон), система программирования ПРИЗ [10] (Тыугу), семиотический решатель СФИНКС [11] (Ефимов) и т.д.

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

Основой для представления знаний очень часто является система продукций на основе правила ЕСЛИ -> ТО (посылка —> следствие, явление -> реакция). Задачи решаются методом автоматического доказательства теорем с использованием принципа резолюций Робинсона [12] или обратного метода С.Ю.Маслова [13].

Широкое распространение получила фреймовая модель М. Минского [14], в которой под фреймом понимается структура данных для представления некоторого концептуального объекта. Информация, относящаяся к фрейму, содержится в его слотах, все фреймы взаимосвязаны

и образуют единую систему, включающую в себя декларативные и процедурные знания. На базе этой концепции созданы языки представления знаний Р11Ь, КЛЬ, БМв, КШИЕ и другие.

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

На определенном этапе работы стало ясно, что необходимы или новые идеи, или новый взгляд на уже известные. Одной из таких хорошо и давно известных идей является теория нечетких множеств Заде [15].

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

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

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

Таблица 1

Методологии для обращения с неопределенностью, неясностью, нечеткостью и неточностью

Класс неясности

Используемая методология

Научные дисциплины, лежащие в основе методологии

А.Неопределенность, случайность:

а) события и(или) состояния среды, обусловленные случайностью;

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

Б. Нечеткость:

а) нечеткость как следствие субъективности или индивидуальности человека

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

1) нечеткое или неточное заключение;

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

а) нечеткость описания или представления;

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

Д. Неясность вследствие структурной сложности и многообразия информации

Теория стохастических процессов и теория принятия решений, мера энтропии

Принцип

неопределенности

Теория нечетких множеств, теория субъективных вероятностей

Теория нечеткого или

приближенного

рассуждения

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

Техника интерпретации образов

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

Теория вероятностей

Квантовая механика

Бесконечно-значная логика Лукасевича

Нечеткая логика (пропозиционное исчисление, исчисление предикатов)

Методы искусственного интеллекта, подкрепленные теорией познания

Техника представления знаний, подкрепленная теорией искусственного интеллекта

Методы нечеткого структурного моделирования

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

Понятие случайности также представляет собой некоторый тип представления неопределённых явлений или часто наблюдаемых событий. Теоретико-вероятностное понятие случайности относится к категории объективных понятий и рассматривается как дополнительное к понятию причинности; такое представление подкрепляется концепцией воспроизводимых экспериментов, которая согласуется с наблюдениями в области естественных наук и в технике. Л.Заде было рассмотрено понятие субъективной вероятности [15], к которой можно относиться как к шкале неоднозначности. Подобно объективной, субъективная вероятность удовлетворяет аксиоме вероятностной меры и оказывается положительной и воспроизводимой.

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

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

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

Обозначим через MB(h,e) меру увеличения доверия к гипотезе h на основе наблюдения исхода е, которая определяется следующим образом: MB(h,e)=(P(h|e)-P(h))/(l-P(h)); меру увеличения неуверенности обозначим MD(h,e), она задается выражением MD(h,e)=(P(h)-P(h|e))/P(h). Тогда фактор определенности, обозначаемый CF(h,e), т.е. степень подтверждения гипотезы

h по наблюдению е определяется выражением CF(h,e)=MB(h,e)-MD(h,e), где P(h/e) - условная вероятность h при известном е; P(h) - субъективная вероятность, т.е. экспертная оценка вероятности, отражающая уверенность эксперта в гипотезе h в некоторый заданный момент времени.

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

MB(h, л h2,e) = min(MB(hbe),MB(h2,e)) MD(h, л h2,e) = max(MD(hbe),MD(h2,e)) MB(hi v h2,e) = max(MB(h],e),MB(h2,e)) MB (hi v h2,e) = min(MD(hbe),MD(h2,e))

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

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

Теория нечетких множеств была предложена JI. Заде в 1965 году. Одной из предпосылок идеи нечетких множеств был принцип несовместимости, который заключается в том, что с увеличением размеров и сложности системы усложняется ее моделирование и создание полностью адекватной модели становится практически невозможным.

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

Пусть М- множество, х- элемент М, тогда нечеткое подмножество А множества М определяется как множество упорядоченных пар {(х,ц,/1(х)}, VxeM, где ¡^(х) - характеристическая функция принадлежности, принимающая свои значения во вполне упорядоченном множестве Е, которая указывает степень или уровень принадлежности элемента х подмножеству А. Множество Е называется множеством принадлежности.

Если Е = {0,1}, то нечеткое подмножество А рассматривается как обычное подмножество.

В 1972г. Л.Заде предложил теоретико-множественную интерпретацию лингвистических переменных, которая отражала лингвистические аспекты отношения принадлежности в нечётких множествах [18]. Например, если высказывание о некотором факте несёт оттенок неуверенности, то его можно характеризовать лингвистически как, истинное, неистинное, очень истинное, более-менее истинное и т.п., определяя каждым таким истиннозначным представлением нечёткого объекта смысл лингвистического ограничения.

Несколько позже Л.Заде предложил ввести в рассмотрение нечёткую логику с лингвистическими, а не числовыми значениями истинности [19,20]. Приближённое рассуждение может рассматриваться как обобщение правил модус поненс и модус толенс, соответствующих хорошо известным правилам вывода модус поненс и модус толенс в исчислении высказываний.

Далее Л.Заде исследовал метаязык PRÜF (абревиатура Possibilistic Relational Universal Fuzzy) [23], чтобы отразить смысловое представление естественных языков. Язык PRÜF опирается на логику с лингвистическими значениями истинности, в которой неточность или неясность, присущая естественным языкам, описывается в терминах распределения возможностей.

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

К настоящему времени в литературе описано множество примеров практического применения теории нечетких множеств [1,2,24,25].

Теория нечетких множеств обнаруживает прежде всего тесную связь с экспертными системами. Применение теории началось в области нечеткого управления во второй половине 70-х годов. Л.Заде был предложен метод описания алгоритмов в форме "если...то" [21,22]. Идея заключалась в том, чтобы раскрыть сущность экспертных систем путем описания алгоритмов словами, т.е. нечетко. Соответственно, получаемые при этом выводы также нечетки. Существует немало примеров успешной автоматизации технологических процессов с помощью нечеткого управления цементной обжиговой печью, холодной прокаткой, водяными насосами и т.д. [25].

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

Разрабатываются нечеткие чипы и нечеткие компьютеры на их основе [24], нечеткое программное обеспечение на ПРОЛОГе и ЛИСПе.

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

Существует много формальных и неформальных определений понятия задача, но до сих пор не выработано общепринятого. В главах 4 и 7 автором будет предложено к обсуждению два опубликованных им в работах [26,27] подхода к определению, систематизации и классификации задач качественного характера с точки зрения формальной логики и с точки зрения инженерии знаний.

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

Пойа [29] определяет задачу следующим образом: "Задача предполагает необходимость сознательного поиска соответствующего средства для достижения непосредственно недоступной цели". Согласно Пойа существует два весьма общих типа задач: задачи на нахождение и задачи на доказательство.

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

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

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

В работе [11] Е.И.Ефимов предложил следующую классификацию типов задач:

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

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

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

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

В работе [31] (М.Д.Месарович) проблемы решения задач в теоретико-множественных представлениях формулируется в самом общем виде следующим образом. Пусть любая система описывается тройкой <\¥,У,№> ,

где Wc X х Z - область определения отображения Т ciWxY, X - множество входных сигналов, Z - множество состояний и Y - множество выходных сигналов системы. Тогда проблема заключается в том, чтобы по заданным множествам W и Y найти требуемые отображения Т.

Примером конкретизации такой модели может служить система доказательства теорем, в которой W - множество правильных формул исчисления высказываний, Y - множество выводимых формул, weH -множество аксиом, используемых в доказательстве, yeY, F0 - множество схем базовых правил вывода, примером которых может служить схема modus ponens, и F - множества конкретных доказательств, представляемых в виде упорядоченной совокупности базовых правил вывода (схема правила превращается в конкретное правило при подстановке в схему конкретных формул). Эта система служит для поиска доказательств j е F.

Если принять, что W - множество правильно описанных ситуаций, и Р= WxW представлят расширенное множество задач, Fo = М0 и F = V -множество программ в мире М0 , то рассмотренная модель может быть представлена как N=<M0,P,V>. Таким образом, необходимыми компонентами решателя являются: объективный мир операций М0, задачи ре Р, играющие роль входных сигналов, и решения veV, играющие роль выходных сигналов.

Отдельный класс практически важных систем составляют системы, характеризуемые большим числом ситуации seS и сравнительно небольшим числом схем решений ЬеВ. Основное внимание в этих системах уделялось эффективному описанию ситуаций в декларативной форме - ситуационное моделирование ( Д.А. Поспелов [32,33], Ю.И. Клыков [34]). Специфика ситуационных систем - значительное преобладание числа ситуаций над числом схем решений - позволяет сводить задачу управления объектов к задаче распознавания класса ситуаций, априори соотнесенного с известной схемой решения.

В попытках автоматизировать процессы решения задач часто использовались одноранговые модели типа N=<MbQ,P,V>, в которых основное внимание обращалось на построение эффективных стратегий поиска решений Q в простых средах Mj. Моделями указанного типа обладают такие известные решатели задач, как GPS, STRIPS, QA3, ПРИЗ, ППР и другие.

Общий решатель задач GPS (GENERAL PROBLEM-SOLVER) базируется на процедуральном описании объектов, операторных схем, таблиц связей. Для нахождения решений применяется обратный поиск с

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

Вопросно-ответная дедуктивная система QA3 (Грин [8]) - это попытка более эффективного представления знаний и использование успехов в области автоматических доказательств теорем. Она рассчитана на произвольную предметную область и произвольные вопросы, ее действие основано на автоматическом доказательстве теорем с использованием принципа резолюции Робинсона [12 ].

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

Планирующая система STRIPS (Файкс, Харт, Нильсон [9]) использует декларативно-процедуральное представление знаний в сочетании с эвристическим поиском.

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

Система ABSTRIPS (Е.Д.Сакердоти [35]) представляет собой модификацию решателя STRIPS, использующую иерархию описаний мира задач.

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

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

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

Из отечественных решателей следует выделить систему программирования ПРИЗ (пакет прикладных инженерных задач) Э.Х.Тыугу [10].

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

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

Д.А.Поспелов предложил определение семиотической модели в виде семерки: W=<T,H,vF,0,X,S,Q>, в которой подсистема А^ТДЧ',©) является формальной системой, а подсистема B=(X,E,Q) представляет индуктивную компоненту модели W, предназначенную для изменения указанной формальной системы в режимах обучения и адаптации применительно к конкретной области. Таким образом, система А выражает синтаксический аспект модели W, а система В - ее семантический и прагматический аспекты.

Примером семиотического решателя является СФИНКС - система формального интеллекта комплексных стратегий (Е.И. Ефимов [11]).

Решатель СФИНКС представляет собой концептуальную систему эвристического поиска в иерархическом пространстве с элементами индуктивно-дедуктивного вывода и процедуральным представлением знаний в формализме системы ДИЛОС. Система создавалась в исследовательских

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

В настоящее время продолжает успешно развиваться концепция, получившая название логического программирования [37,38,39]. Важным практическим шагом в указанном направлении было создание языка ПРОЛОГ [40,41] (РК^гаттн^ т ЬООю). Основная идея этого языка состояла в том, что нужно на логическом языке описать условие задачи, а решение ее получается тогда как результат некоего рутинного процесса, который исполняется на ЭВМ. Условие задачи представляет собой множество формул специального вида в языке логики предикатов первого порядка, одна из формул выделена и называется целью, остальные -посылками. Тогда упомянутый процесс состоит в построении доказательства цели из посылок в исчислении, единственным правилом вывода которого является правило резолюции.

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

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

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

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

Если пересмотреть принцип резолюций с точки зрения нечеткой логики [26,42,43], то появляется возможность построить нечеткий ПРОЛОГ с многозначной оценкой истинности решений [45,46]. Такой вариант языка является весьма удобным и эффективным средством решения качественных задач при нечетком представлении знаний.

1.4. Описание постановки задач исследований и последовательности их решения

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

В начале 70-х годов начали активно проводиться работы по формализации знаний и автоматизации решения задач в области молекулярной спектроскопии, квантовой и структурной химии и областях, смежных с ними. Одной из нерешенных задач, существенно тормозивших процесс создания компьютерных систем в данной области, была задача построения полного набора структурных изомеров, соответствующих заданному атомному составу молекулы. Как это ни удивительно, через более чем столетие после создания теории химического строения не было предложено методов, правил, алгоритмов решения этой задачи. Например, было неизвестно, сколько и каких изомеров у всем известного бензола состава Сб Н6 (их оказалось 217 [47]). Причина, по-видимому, состоит в "неудобстве" задачи для человеческого мышления, которое с позиции современной теории представления знаний следует классифицировать как "нечеткость или неясность в процессах мышления или умозаключения" (см. табл.1). Задача была решена без использования логических методов в формализме теории графов [47-58]. В результате была разработана система

математического синтеза и анализа молекулярных структур МАИСС [58] на языке ФОРТРАН, описанная в главе 2. Аналогичная задача решалась в системе ДЕНДРАЛ эвристическими методами наращивания структуры от ценрального атома, затем была создана соответствующая программа на ЛИСПе.

Ранее М.Е.Эляшберг и Л.А.Грибов [59] предложили использовать исчисление высказываний для логического анализа спектро-структурной информации. В результате была формально решена задача структурно-группового анализа для ИК-спектроскопии, позволяющая устанавливать состав и возможные комбинации фрагментов, объясняющие характеристические признаки спектра. В сочетании с системой МАИСС это дало возможность постановки вопроса о формальном решении задачи установления структур многоатомных молекул по спектрохимическим данным. Разработкой необходимых для ее решения методов, алгоритмов и программ автор занимался в последующее время. В результате была создана экспертная система РАСТР [5,6,58], которая описана в главе 3. РАСТР можно рассматривать как систему, базирующуюся на знаниях в форме продукций в исчислении высказываний, представленных библиотеками спектро-структурных корреляций. Нечеткость, неопределенность знаний учитывается указанием интервальных значений характеристических признаков спектров. Механизм оценки истинности вариантов возможных структурных формул базируется на сопоставлении их гипотетических (прогнозируемых) спектров и системы продукций в исчислении высказываний, описывающих спектро-структурные корреляции, однако ранжирование вариантов ответов не производится.

Дальнейшие исследования показали необходимость более детального и углубленного представления знаний (многоатомные молекулы являются чрезвычайно сложными объектами) и совершенствования методов решения задач. Автором было разработано и опубликовано в применении к решению качественных задач молекулярной спектроскопии [26,42] прикладное исчисление нечетких предикатов, объединяющее возможности исчисления предикатов первого порядка и теории нечетких множеств. В это же время исследования возможности построения нечеткой логики в рамках исчисления высказываний были проводились М.Мукаидоно [43,44].

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

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

Решение задач для микрознаний производится методом доказательства теорем с использованием принципа резолюций, расширенного для нечеткой логики, что дает возможность оценки истинности результатов. В качестве решателя задач на уровне макрознаний используется ТУРБО-ПРОЛОГ [41], расширенный автором до нечеткого. При этом если в расширении, описанном в работе [45 ], нечеткость описывается константами, то здесь -кусочно-линейными аппроксимациями функций принадлежности.

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

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

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

Описанные методы опробованы и использованы при разработке экспериментальной экспертной системы СПРИНТ.

1.5. Выводы

1. Рассмотрены общие вопросы представления знаний и методов решения задач прикладного характера с применением ЭВМ.

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

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

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

2. РЕШЕНИЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО СИНТЕЗА И АНАЛИЗА МОЛЕКУЛЯРНЫХ СТРУКТУР МЕТОДАМИ ДИСКРЕТНОЙ МАТЕМАТИКИ

2.1. Постановка задачи и ее практическое значение

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

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

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

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

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

В системе ДЕНДРАЛ [3], которая разрабатывалась в одно время с рассматриваемыми в данной работе системами МАИСС и РАСТР, использовался алгоритм, который синтезирует структурные формулы методом наращивания структуры от центрального атома, служащего центром графа, при этом в ответ включаются только те формулы, которые удовлетворяют спискам запрещенных и разрешенных фрагментов, что приводит к резкому сокращению числа возможных вариантов. Система ДЕНДРАЛ нашла применение при распознавании структур молекул, относящихся к определенным классам, по их масс-спектрам.

Работы по совершенствованию алгоритмов и программ синтеза и анализа молекулярных структур продолжались и после завершения разработки системы МАИСС [101], что подтверждает их актуальность и практическое значение.

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

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

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

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

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

Программы системы МАИСС разработаны на алгоритмическом языке ФОРТРАН.

Разумная граница размерности решаемых задач равна 8 ДЕС, так как уже при 6 ДЕС число структур может приближаться к тысяче. Максимально допустимая размерность задач равна 10 ДЕС. Рассмотрим далее основные алгоритмы системы МАИСС.

2.2. Алгоритм генерации полного набора матриц смежности неизоморфных графов

Каждую структуру можно представить в виде конечного связного мультиграфа (рис. 2.1а). Для определенной г-й нумерации вершин графа можно построить одну матрицу смежности Вг размерности пх п, где п - число вершин (рис. 2.16). Каждый элемент матрицы Вг отражает отношение между вершинами графа: если вершина 1 соединена ребром кратности ш с вершиной], то элемент Ьу принимает значение т (ш=0,1,2,3). Правый дополнительный столбец матрицы Вг служит для указания количества присоединенных к вершинам атомов водорода: значение элемента Ь^-н дополнительного столбца определяет число атомов водорода для вершины с номером {.

4 II С Н

\

С

с

2 5 6

С - С Н 2- С Н з

//

а

1 2 3 4 5 6 7

1 1 1 2

2 1 2 1

3 1 2 1

4 2 1 1

5 1 1 2

6 1 3

б

1 1 2

2 1

1

1

кг=112002010100001 в

3 1

3 1

1 1 2

2 2

2 2

2 2

кгт=31 ООО 1000200202

г

3 1

3 \ 1

1 1 2

2 2

2 1 . 1

1 3

кг=310001000200201

д

3 1

3 1

1 1 2

2 2

2 2

4

кг=310001000200200

е

3 1

3 1

1 1 2

2 1 1

1 3

1 3

2 1 1

2 1 1

1 1 2

1 2 1

1 1 2

1 3

2 1 1

2 1

1 1 2

1 2

кг=310001000200113

Ж 3 и

Рис. 2.1. Синтез структурных формул

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

Назовем "большей" ту матрицу Вг, которой соответствует большее число

Кг.

Основная идея процесса генерации всех возможных структур состоит в следующем. Сначала строится "максимальная" для данной брутто-формулы матрица Вгт (число атомов водорода при этом игнорируется). Очевидно, этой матрице соответствует максимальное число Кгт. Затем производится последовательное "вычитание" из Вгт минимально возможных чисел (фактически арифметическое вычитание из К^) до тех пор, пока Кгт не станет равно нулю. Для получения Вгт последовательно слева направо и сверху вниз просматриваются строки Вг, начиная с элемента Ьу+Ь т.е. все строки Аг. Каждый элемент, а также симметричный ему, заполняются максимально возможным по правилам валентности числом, пока сумма всех элементов строки не сравняется с валентностью ДЕС, представляющей строку, или строка не закончится (в последнем случае оставшиеся единицы валентности составляют элемент добавочного столбца, т.е. количество присоединенных атомов водорода). Использование правила валентности при заполнении матрицы заключается в следующем: значение каждого очередного элемента вычисляется таким образом, чтобы сумма всех элементов строки была не больше валентности соответствующей ДЕС. Матрица В,™ и число Кгт для брутто-формулы СбНб в качестве примера показаны на рис. 2.1г.

Процесс "вычитания" из Вт минимально возможных чисел производится следующим образом. Все элементы Аг построчно просматриваются справа налево и снизу вверх до тех пор, пока не встретится первый ненулевой элемент Ьу. Это значит, что число Кг просматривается начиная с младших разрядов справа налево, пока не встретится ненулевой разряд. Значение Ьу и симметричного элемента матрицы уменьшается на 1, что равносильно вычитанию единицы из первого справа ненулевого разряда Кг. Затем, начиная с элемента Ьу+Ь строится "максимальная" матрица по описанному выше алгоритму. Результаты трех последовательных применений операции "вычитания" к Вт и соответствующие числа Кг изображены на рис. 2.1д - ж.

Из рис. 2.1д'- ж видно, что матрицы образуются при последовательном вычитании единицы из первого ненулевого справа разряда Кт. Для получения матрицы, представленной на рис. 3.1 ж, необходимо вычесть единицу из младшего ненулевого разряда числа 310001000200200, что равносильно вычитанию из Кг числа 100 (в данном случае 100 есть минимально возможное вычитаемое). Тогда Ь4;5=Ь5;4=1, после этого строим "максимальную" матрицу (рис. 3.1ж), при этом получим Ь4>б=Ьб,дополучаемые в процессе перебора матрицы смежности Вг должны проходить ряд дополнительных проверок. Первой из них является проверка на

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

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

Известно, что каждому графу соответствует множество матриц смежности, элементы которого можно получить перенумерацией вершин. Это свойство называется изоморфизмом графов. Если в скелете молекулы содержится П[ ДЕС первого типа, п2 - второго,... пк - к-го типа, то число возможных перенумераций равно п^*^!*... *пк!. Например, если для молекулы состава С4Н8К203 в матрице смежности первые четыре строки зафиксированы за атомами С, следующие две - за N и последние три - за О, то возможное число матриц смежности для каждого графа равно 4!*2!*3!=288. Из этого множества необходимо выделить только одну матрицу, назовем ее канонической. Для этого следует упорядочить множество всех матриц и выбрать одну в соответствии с принципом упорядочения.

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

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

Был разработан, опробован и включен в МАИС С следующий эвристический критерий: если при перенумерации строк [ и 1+1Д+2,..,П1 матрицы Вг (г=1,2,.., пг 1), относящихся к типу ДЕС 1, и аналогичных перенумерациях для ДЕС типа 2,...,к не удается получить КР>КГ, то матрица канонична. Этот критерий дает 10-30% повторений графов, что допустимо практически для всех задач, в которых МАИСС не используется как счетчик

изомеров, объем же вычислительной работы относительно невелик и соответствует числу перенумераций, вычисляемому по формуле К=Хп;(п|-1)/2, где 1=1,...к. Пример связной и каноничной матрицы смежности приведен на рис. 2.1з.

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

2.3. Алгоритм анализа матриц смежности по их топологическим особенностям

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

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

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

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

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

Полученную таким образом матрицу обозначим Вги,. На рис. 2.1 и показана матрица В™ для матрицы Вг, изображенной на рис. 2.1з. Цикл является простым, если все его вершины входят только в один цикл. Для матрицы Вто это означает, что в каждой ненулевой строке находится по два не равных нулю элемента. Матрица приведенная в качестве примера на рис. 2.1 и, как видим, содержит несколько циклов. Для того чтобы в матрице выделить все простые циклы, необходимо из множества всех ребер графа, соответствующего ВП¥ (число их равно у/), последовательно исключить все сочетания по 0,1,2,...^ ребра, причем q = \¥-3, так как минимально возможный цикл - трехчленный. Тогда общее количество исключаемых сочетаний равно 0= Е\у!/(\у-1)!Л!, где

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

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

Пусть исходный набор, определяющий матрицу смежности А графа А, состоит из N дискретных единиц структуры и N=1! пк, где к=1,2,..Т, и Г - число типов ДЕС (ТьТ2,...,Тк,...Л>), пк - число ДЕС к-го типа. Например, для Сэ-НцЫзОг имеем СеТь МеТ2, ОбТ3, ^3; П1=5, п2=3, п3=2. Предположим, что необходимо установить наличие или отсутствие в графе А подграфа В, содержащего в вершинах Р дискретных единиц структуры, причем Р=Е рк , где рк - число ДЕС типа к в подграфе В, к = 1,2,.../.

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

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

3 7 СНг-О 6 1 | 21 5 ОН—С — СБ—ЫН2

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Серов, Владимир Васильевич

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ

1. Предложена теория и методы формализации нечетких знаний прикладного характера на основе объединения возможностей логики предикатов первого порядка и теории нечетких множеств - прикладное исчисление нечетких предикатов.

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

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

4. Проведена систематизация и формальное описание широко распространенных классов прикладных качественных задач: прогнозирования, интерпретации, идентификации.

5. Приведены примеры знаний решения качественных задач в описанном формализме на языке ТУРБО-ПРОЛОГ.

6. Показана возможность использования нечеткой логики в естественноязыковых приложениях.

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

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

-система математического синтеза и анализа молекулярных структур МАИСС, результаты расчетов системой МАИСС точного числа изомеров различного атомного состава и их построение получены и описаны впервые;

-экспертная система распознавания структур многоатомных молекул РАСТР, неоднократно модифицированный вариант системы РАСТР эксплуатируется более 20 лет;

-экспериментальная экспертная система СПРИНТ, система используется для отработки предлагаемых методов и имеет в своем составе ряд универсальных компонентов, применимых в других системах подобного рода;

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

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

-система контроля сроков выполнения решений.

Список литературы диссертационного исследования доктор технических наук Серов, Владимир Васильевич, 1997 год

СПИСОК ЛИТЕРАТУРЫ

1. Нечеткие множества и теория возможностей. Последние достижения. Матер, науч. конф. Под ред. P.P. Ягера. Пер. с англ. В.Б. Кузьмина. М.:Радио и связь, 1986, 391с.

2. ТэраноТ. Введение в нечеткие системы. Сб. Прикладные нечеткие системы. Под ред. Тэрано Т., Асаи К., Сугэно М. Пер. с япон. Ю.Н. Чернышева. М.:Мир, 1993, 363 с.

3. Feigenbaum Е.А., Buchanan В.J., Lederberg J. Machine intellegence. Edinburg, 1971,6, p.165.

4. Shortliffe E.H. Computer - Based Medical Compation: MYCIN. American Elsevier, New York, 1976.

5. Серов B.B., Грибов JI.A., Эляшберг M.E. Алгоритм и программа идентификации многоатомных молекул по оптическим спектрам. Доклады АН СССР. Т. 232, № 3, М.,1977.

6. Gribov L.A., Elyashberg М.Е., Serov V.V. Computer system for structure recognition of polyatomic molecules by I.R., N.M.R., U.V. and M.S. methods. Analytica Chimica Acta, 95, Amsterdam, 1977, p. 75-96.

7. Ньюэлл A., LLIoy Дж., Саймон Г. (Newell A., Shaw J., Simon H.) Empirical explotations of the logic theory machine. Proc. Western Joint Computer Conf., 1957. Рус. пер.: Эмпирические исследования машины "логик-теоретик". В кн.: Вычислительные машины и мышление. М.: Мир, 1967.

8. Green С.С., Raphael В. The use of theorem-proving techniques in question-answering systems. Proc. 23rd ACM Nat. Conf., 1968.

9. Нильсон H. (Nilson N.) Problem solving methods in artificial intelligence. New York: Mc Graw-Hill Book Company, 1971. Рус. пер.: Искусственный интеллект. М. Мир, 1973.

11. Ефимов Е.И. Решатели интеллектуальных задач. М.: Наука, 1982, 313с.

12. Робинсон Дж. (Robinson G.) A machine-oriented logic based on the resolution principle. - J. ACM, 1965, v. 12, №1, p. 23-41. Рус. пер.: Машинно-ориентированный логический базис в принципе резолюций. Кибернетический сб., Новая сер., №7, М.: Мир, 1970.

13. Мае лов С.Ю. Обратный метод установления выводимости в классическом исчислении предикатов. ДАН СССР, т. 159, N1, 1964, с. 17-20.

14. Minsky M.L. A framework for representing knowledge. Cambridge: Massachusetts Institute of technology, 1974. Рус. пер.: Фреймы для представления знаний. М.: Энергия, 1979.

15. Zadeh L.A. Fuzzy set. Information and control. N 8, 1965, p. 338

16. Танака К. Итоги рассмотрения факторов неопределенности и неясности в инженерном искусстве. Нечеткие множества и теория возможностей. Последние достижения. Матер, науч. конф. Под ред. P.P. Ягера. Пер. с англ. В.Б. Кузьмина. М.: Радио и связь, 1986, 391с.

17. Представление и использование знаний. Под ред. X. Уэно, М.Исидзуки. М.: Мир, 1989.

18. Zadeh L.A. A fuzzy-set-theoretic interpritation of linguistic hedges. J.Cybern, 2, 4-34, 1972.

19. Zadeh L.A.The concept of a linguistic variable and its application to approximate reasoning. Part 1, 2, 3. Information Sciences. 1975, N8, p. 199-249; N8, p. 301-357; N9, p. 43-80.

20. Zadeh L.A.Outline of new approach to the analysis of complex systems and decision process. IEEE Trans, on SMC. 1973.Vol. 3, N1, p. 28-44.

22. Zadeh L.A. Out line of a new approach to ehe analysis of complex systems and decision process. IEEE Trans, on SMC.Vol. 3, N1, 1973.

23. Zadeh L.A. PRUF - A meaningful representation language for natural language. Int. Journal of Man-Machine Studies. N10, 1978.

24. Мумано M., Мукодоно M., Ямагава P. Нечеткие компьютеры и программное обеспечение. Сб. Прикладные нечеткие системы. Под ред. Тэрано Т., Асаи К., Сугэно М. Пер. с япон. Ю.Н. Чернышова.М.:Мир, 1993, 363 с.

25. Иван С., Сути М. и др. Экспертные системы. Сб. Прикладные нечеткие системы. Под ред. Тэрано Т., Асаи К., Сугэно М. Пер. с япон. Ю.Н. Чернышова. М.:Мир, 1993, 363 с.

26. Serov V.V., Gribov L.A., Elyashberg М.Е. Elements of the applied theory of solving gualitative problems of molecylar spectroscopy. Journal of Molecular Structure 129, Amsterdam, 1985. p. 183-214.

27. Serov V.Y., Elyashberg M.E., Gribov L.A. System-related matters in the theory of solving qualitative problems. Journal of Molecular Structure, 178, Amsterdam, 1988. pp. 1-21.

28. Власов В.В. Общая теория решения задач (радиология). М.: ВЗПИ, 1990.

29. Пойя (Polya G.). Mathematics and plausidle reasoning (2 vols). Princeton, 1954. Рус. пер.: Математика и правдоподобные рассуждения. М.: Наука, 1975.

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

31. Mesarovic M.D. Foundations for general system theory. In: Views on Gen. Syst. Theory. New York; London; Sydney: Wiley, 1964. Рус.пер.: Обоснование общей теории систем. В кн.: Общая теория систем. М.: Мир, 1966.

33. Поспелов Д.А. Ситуационное управление: теория и практика. М.: Наука,

1986.

34. Клыков Ю.И. Ситуационное управление большими системами. М.: Энергия, 1974.

35. Sacerdoti E.D. Planning in a hierachy of abstraction space. Artificial Intelligens, v. 5, pp. 115-135.

36. Брябрин B.M. Диалоговая информационно-логическая система. Труды Межд. конф. по Искусственному Интеллекту. Ленинград - Репино, 1977.

37. Robinson J.A. Logic Programming - Past, Present and Future. New Generation Computing, 1983, vol. l,pp. 133-146.

38. Kowalski R. Logic Programming. In: Proceeding of the IFIP-83, Horth Holland, 1983, pp. 133-146.

39. Kowalski R. Algorithm = Logic + Control. Communication of ACM, 1979, vol. 22, N7, pp. 424-435.

40. Клоксин У., Меллиш К. Программирование на языке Пролог. М.: Мир,

1987.

41. Ин Ц., Соломон Д. Использование Турбо - Пролога. Пер. с англ. Д.Ю. Буланже, О.Л.Кондратьева. М.: Мир, 1993, 598с.

42. Серов В.В. Решение качественных задач методом доказательства теорем в прикладном логическом исчислении. Тезисы докладов. Межвузовский научн.-технич. семинар "Системный анализ, техническая и экономическая кибернетика". М., 1984.

43. Мукаидоно М. Нечеткий вывод резоляционного типа. Нечеткие множества и теория возможностей. Последние достижения. Матер, науч. конф. под ред. P.P. Ягера. Пер. с англ. В.Б. Кузьмина. М.: Радио и связь, 1986, 391с.

44. Мукаидоно M., Масудзава M. Свойство резолюций в нечеткой логике. Дэнси цусин гаккай ромбусин.Т. J66-D, N7, 1983.

45. Мукаидоно М. Что такое нечеткий Пролог? Computer today. N25, 1988, р.4^16.

46. Серов В.В., Эляшберг М.Е., Петров В.М. Разработка системы искусственного интеллекта для молекулярной спектроскопии РАСТР-4. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин в химических исследованиях и спектроскопии молекул". Рига, 1986.

47. Серов В.В., Эляшберг М.Е.,Грибов JI.A. Математический "синтез" всех топологических изомеров бензола. Известия ТСХА . Вып. 1, М., 1977, с. 215.

48. Серов В.В., Эляшберг М.Е., Грибов JI.A. Система математического "синтеза" и анализа всех структурных формул органических соединений, соответствующих заданной брутто-формуле. Доклады АН СССР. т. 224, №1, М., 1975. .

49. Serov V.V., Elyashberg М.Е., Gribov L.A. Mathematical synthesis and analysis of molecular structures. Jornal of Molecular Structure, 31, pp.381-397, Amsterdam, 1976.

50. Эляшберг M.E., Серов B.B. Грибов JI.A. Применение ЭВМ для построения структурных формул по данным молекулярного спектрального анализа. Тезисы докладов. Третий семинар "Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1975.

51. Серов В.В.,Эляшберг М.Е., Грибов JI.A. Система математического "синтеза" и анализа молекулярных структур и ее применение в химии. 11-ый Менделеевский съезд по общей и прикладной химии. Физическая химия. Химическая физика и катализ. Электрохимия. М.: Наука, 1975.

52. Серов В.В., Эляшберг М.Е. Математический "синтез" и анализ молекулярных структур с применением ЭВМ и его использование. Тезисы докладов 6-ой Межотраслевой конф. молодых специалистов. М.: ГИРЕДМЕТ, 1976.

53. Серов В.В., Эляшберг М.Е., Грибов Л.А. Комплекс алгоритмов и программ математического "синтеза" и анализа структурных формул химических соединений. Депонент ВИНИТИ .№1464-76, М.,1976.

54. Серов В.В., Эляшберг М.Е., Грибов Л.А. Алгоритм и программа проверки наличия или отсутствия заданных фрагментов в структурных формулах химических соединений, представляемых графами. Журн. структурной химии. Т. 17, № 6, Новосибирск, 1976.

55. Туренко Ф.П., Эляшберг М.Е., Серов В.В. Выборка методом аддитивных функций изомерных структур из множества синтезированных химических графов. Тезисы докладов. 4-ая Всесоюзная конф. "Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1977.

56. Серов В.В., Эляшберг М.Е. Система программ математического "синтеза" и анализа структурных формул всех изомеров, отвечающих заданной брутто-формуле. Сб. аннотаций программ для молекулярной спектроскопии. Новосибирск, 1977.

57. Эляшберг М.Е., Серов В.В., Грибов Л.А. Распознавание химических соединений по их молекулярным спектрам с применением программы построения структурных формул из атомов и фрагментов. Журн. прикладной спектроскопии. Т.26, Вып. 2, Минск, 1977.

58. Эляшберг М.Е., Грибов Л.А., Серов В.В. Молекулярный спектральный анализ и ЭВМ. М.: Наука, 1980, 301с.

59. Эляшберг М.Е., Грибов Л.А. Журн. прикладной спектроскопии, 1968, 8, с. 296.

60. Серов В.В.4 Эляшберг М.Е., Грибов Л.А. Система распознавания структуры сложных молекул по характеристическим признакам в ИК-, КР-, ЯМР-, УФ- и масс-спектрах. Тезисы докладов. 4-ая Всесоюзная конф. "Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1977.

"Использование вычислительных машин в спектроскопии молекул". Новосибирск, 1977.

62. Серов В.В., Эляшберг М.Е., Грибов JI.A. Структурная интерпретация молекулярных спектров. Системный подход. Сб. "Теоретическая спектроскопия ".М., 1977.

63. Серов В.В., Эляшберг М.Е., Грибов JI.A. Система программ автоматического распознавания структуры многоатомных молекул по колебательным спектрам. Сб. аннотаций программ для молекулярной спектроскопии. Новосибирск , 1977.

64. Мешалкин В.П. Экспертные системы в химической технологии. М.: Химия, 1995,368с.

65. Грибов JI.A., Эляшберг М.Е., Серов В.В. и др. Спектры и ЭВМ-инструменты определения пространственных структур молекул. Тезисы докладов 9-ой Межд. конф. по применению ЭВМ в химии и химическом образовании. Новосибирск, 1978.

66. Серов В.В., Грибов JI.A., Эляшберг М.Е. Система программ идентификации химических соединений по молекулярным спектрам. Депонент ВИНИТИ № 2912-78. М., 1978.

67. Gribov L.A., Elyashberg М.Е., Serov V.V. On the solution of one classical problem in vibrational spectroscopy. Journal of Molecular Structure, 50, pp. 371387, Amsterdam, 1978.

68. Серов B.B., Грибов JI.A. Общесистемные вопросы использования прикладных программ по молекулярной спектроскопии. Тезисы докладов. 6-ая Всесоюзная' конф. "Использование вычислительных машин в спектроскопии молекул и химических исследованиях". Новосибирск, 1983.

69. Серов В.В., Грибов JI.A., Эляшберг М.Е. Прикладное логическое исчисление для решения качественных исследовательских задач по молекулярной спектроскопии. Тезисы докладов. 6-ая Всесоюзная конф. "Использование вычислительных машин в спектроскопии молекул и химических исследованиях". Новосибирск, 1983.

70. Серов В.В., Эляшберг М.Е. Формализация решения качественных спектроскопических задач. Тезисы докладов 5-ой Всесоюзной конф. по аналитической химии органических соединений .М., 1984.

71. Серов В.В., Эляшберг М.Е. Формализация решения качественных задач молекулярной спектроскопии. Журн. структурной химии. Т.27, №2, Новосибирск, 1986.

72. Эляшберг М.Е., Серов В.В. Теоретические вопросы построения системы искусственного интеллекта для молекулярной спектроскопии. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин в химических исследованиях и спектроскопии молекул". Рига, 1986.

73. Серов В.В.,Эляшберг М.Е. Основные концепции построения системы искусственного интеллекта для молекулярной спектроскопии. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин в химических исследованиях и спектроскопии молекул". Рига, 1986.

74. Эляшберг М.Е., Серов В.В., Никитин Г.Н. Система распознавания структур молекул РАСТР-3. Тезисы докладов. 7-ая Всесоюзная конф. "Использование вычислительных машин в химических исследованиях и спектроскопии молекул". Рига, 1986.

75. Эляшберг М.Е., Серов В.В., Петров В.М. и др. Система искусственного интеллекта для молекулярной спектроскопии. Тезисы докладов. Всесоюзная конф. "Математические методы и ЭВМ в аналитической химии". М., 1986.

76. Elyashberg M.E.,Serov V.Y., Gribov L.A. Artificial intelligence systems for molecular spectral analysis". Talanta, Vol.34, No.l, Great Britain, 1986. pp.21-30.

77. Петров В.М.,' Серов В.В. Интегрированная модель предметной области в системе, основанной на знаниях. Межвузовский сб. научных трудов "Системный анализ, информатизация и прикладные задачи." М.: РЗИТЛП, 1994.

79. Петров В.М., Серов B.B. Модель понимания связного на уровне абзаца научно-технич. текста. Матер, конф. "Автоматизация проектирования и производства в легкой промышленности." М.: РЗИТЛП, 1995.

80. Петров В.М., Серов В.В. Методы и формальный аппарат, обеспечивающие анализ неграмматичных выражений ограниченного естественного языка. Матер, конф. "Автоматизация проектирования и производства в легкой промышленности." М.: РЗИТЛП, 1995.

81. Серов В.В. Основные понятия прикладного исчисления нечетких предикатов для формализации знаний и решения задач качественного характера. Тезисы докладов. Межвузовская науч. конф. "Современные проблемы текстильной и легкой промышленности". М.: РЗИТЛП, 1996.

82. Serov V.V. Elements of the appliend theory of solving qualitative problems. Multiple criteria and game problems under uncertainti. The Fourth International Workshop. Moscow, 1996.

83. Виноград T. Understanding natural language. New York: Acad. Press, 1972. Рус. пер.: Программа, понимающая естественный язык. М.: Мир, 1976.

84. Эрбран (Herbrand J.) 1930 Reschedeshes sur la theorie de la demonstration. -Trav. Soc. Sei. Lettres varsovie, Classe III Sei. Math. Phys., No. 33, 1930.

85. Прикладная информатика: Сб. ст. Под ред. В.М. Савинкова.М.: Финансы и статистика, 1986, 188с.

86. Алешина H.A., Анисов A.M., Быстров П.И. и др. Логика и компьютер. Моделирование рассуждений и проверка правильности программ. Сер. Кибернетика. М.: Наука, 1990.

87. Любарский Ю.Я. Интеллектуальные информационные системы. М.: Наука, 1990.

88. Попов Э.В. Общение с ЭВМ на естественном языке. М.: Наука, 1982.

90. Carbonell J.G., Hayes P.G. Robust parsing using multiple construction-specific strategies. - In: Bole, L. (ed.). Natural Language Parsing Systems. New York: Springer Verlag, 1984.

91. Hayes P.J., Mouradian G,V. Flexible parsing. AJCL1, vol. 7(4), 1981, p.232-241.

92. Hendrix G.G. Human engineering for apllied natural language processing. "Proceedings 5-th IJCAI, MIT", 1977, p. 183-191.

93. Kwansy S.C., Sondheimer N.K. Relaxation techniques for parsing grammatically ill-formet, input in natural language understanding systems. AJCL, vol. 7(2), 1981, p. 99-108.

94. Schang R. et al. An integrated ubderstander. AJCL, vol. 6(1).

95. Woods W.A., et al. Speech Understanding Systems. Final Technical Report. 3438, Bolt, Beranek and Newman, Inc. Cambridge, Ma, 1976.

96. Поспелов Д.А. Ситуационное управление: теория и практика. М.: Наука, 1986.

97. Амосов М.И. Алгоритмы разума. Киев.: Наукова думка , 1979.

98. Осуги С., Саэки Ю. Приобретение знаний. Пер. с япон. М.: Мир, 1990.

99. Уэно X., Исидзука М. Представление и использование знаний. Пер. с япон. М.: Мир, 1989.

100. Разников В.В., Тальрозе B.JI. Журн. структурной химии, 1970, И, с. 357.

101. Молодцов С.Г., Пиоттух-Пелецкий В.И. У1 Всесоюзная конф. "Использование ЭВМ в спектроскопии молекул и химических исследованиях". Тезисы докладов. Новосибирск, 1982, с. 174-175.

103. Наканиси К. Инфракрасные спектры и строение органических соединений. М.: Мир, 1965, 216с.

104. Эмсли Дж., Финей Дж., Сатклиф JI. Спектроскопия ЯМР высокого разрешения. М.: Мир, 1969, 468с.

105. McLafferty F.W. Mass spectral correlation. Wahington D. C.: Amer. Chem. Soc., 1963, 117p.

106. Гордон А., Форд P. Спутник химика. Физико-химические свойства, методики, библиография. М.: Мир, 1976, 541с.

107. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем: Пер. с англ. под ред. С.Ю. Маслова. М.: Наука, 1983.

108. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982.

109. Серов В.В. Элементы прикладной теории исчисления нечетких предикатов и ее применение для представления знаний и решения качественных задач. Сб. научных трудов Международной академии информатизации. Системный анализ, информатика и оптимизация. М., 1997. с. 138-155.

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

111. Техническое задание на создание автоматизированной системы экспертных оценок на художественно-технических советах, демонстрациях мод и тематических просмотрах изделий легкой промышленности, проводимых на базе ВИАлегпрома. М.: ВНИГИАСУлегпром, 1977.

112. Букреев В.З., Серов В.В., Завилевич М.Л. Комплекс программ подсистемы "Выставки" автоматизированной системы экспертных оценок. Тезисы докладов. Научно-технич. семинар "Системный анализ и оптимизация управления". M., 1982.

113. Букреев В.З., Жуковский В.И., Серов В.В. и др. Вопросы совершенствования методов оценки уровня качества образцов изделий на художественно-технических советах МИНлегпрома. Тезисы докладов. Научно-технич. семинар "Системный анализ и оптимизация управления". М.,

1983.

114. Серов В.В., Орлов А.Г. Программное обеспечение подсистемы "Художественно-технический совет" автоматизированной системы экспертных оценок. Тезисы докладов. Межвузовский научно-технич. семинар "Системный анализ, техническая и экономическая кибернетика". М.,

1984.

115. Букреев В.З., Орлов А.Г., Серов В.В. Подсистема "Художественно-технический совет" автоматизированной системы экспертных оценок. Журн. " Текстильная промышленность ", №9, М., 1984.

116. Букреев В.З., Самородов В.В., Серов В.В. Автоматизированная система экспертных оценок для оценки качества промышленной продукции и изучения потребительского спроса. Сб. научных трудов "Совершенствование организации и автоматизация в торговле города". НПО АСУ " Москва", М., 1986.

ПРЙЛиЖЁНаЁ I

УТВЕРЖДАЮ:

Генеральный директор ОАО ВНИИОС академик РИА профессор С.П.Черных

-/'71 X

»

декабря 1997 г.

СПРАВКА ОБ ИСПОЛЬЗОВАНИИ

Многие результаты, полученные в докторской диссертации В.В.Серова "Математические методы, алгоритмы и

программные системы для решения прикладных задач качественного характера при логическом представлении нечетких знаний", нашли практическое применение в научной практике Лаборатории молекулярной спектроскопии Всероссийского научно-исследовательского института

органического синтеза, г. Москва.

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

Принципы построения баз знаний по молекулярной спектроскопии и особенно методы использования прикладного логического исчисления, развитого В.В.Серовым, нашли применение при разработке новой системы спектроскопической идентификации ЭКСПЕРТ. Использование этих разработок позволило получать результаты анализа с оценкой их достоверности.

Зав. Лабораторией молекулярной спектроскопии ВНИИОС, профессор, д.х.н., к.ф.-м.н. М.Е.Эляшберг

СПРАВКА

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

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

Заместитель начальника НИИСТ МВД России

В.П.Мартынов

АКТ

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

Разработанные методы представления знаний были внедрены для разработки системы программ управления производственной и коммерческой деятельностью в фирме КЕВЛАР с использованием базы данных FOXPRO.

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

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

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

Директор фирмы КЕВЛАР