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

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

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

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

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

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

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

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

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

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

Целью диссертационной работы является разработка. методов и алгоритмов поддержки принятия решения для экспертной системы автоматизации подготовки картографических изданий на примере ДАРЯ.

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

1. Анализ теоретических и практических разработок в области экспертных систем (статических и динамических), геоинформационных систем, а также в области интеграции этих систем.

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

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

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

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

6. Проектирование на основе разработанных методов и алгоритмов экспертной системы автоматизации редакционно-издательской и допе-чатной подготовки картографических изданий на примере ДАРЯ.

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

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

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

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

В Главе 4 данной работы проводится оценка временных затрат алгоритма поддержки принятия решения, исследование такта алгоритма поддержки принятия решения. В рамках каждого из исследований и оценок выводятся аналитические зависимости, строятся их графики. Также в данной главе приводится описание основных программных компонент, разработанных в соответствии с предложенными структурами, методами и алгоритмами: компоненты для работы с микрознаниями, компоненты для работы с макрознаниями, геоинформационной компоненты. Рассматриваются вопросы их интеграции в рамках единой автоматизированной системы — ГИЭС. Приведен реальный пример интеграции компонент в области подготовки листов ДАРЯ — ГИЭС «ДИАЛЕКТ». Представлено описание предметной области, а также описание задач, подлежащих автоматизации. Кратко описан процесс проектирования данного примера ГИЭС. Дана краткая характеристика полученных результатов.

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

Основные выводы и результаты работы:

1. В рамках диссертационной работы проведен анализ подходов к проектированию экспертных и геоинформационных систем, приведена их классификация.

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

3. Разработана математическая модель базы знаний ГИЭС.

4. Разработана методика классификации событий, возникающих в процессе выполнения процедуры поддержки принятия решения в ГИЭС.

5. Разработаны методики и алгоритмы поддержки принятия решения в экспертной компоненте ГИЭС: функционирование менеджера пользователей, обработка событий, поддержка принятия решений.

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

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

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

Заключение

.