Автоматическое построение математических моделей: новое приложение систем автоматического доказательства теорем1

Васильев С.Н., Черкашин Е.А., Бычков И.В.
Институт динамики систем
и теории управления СО РАН,
Черкашин А.К.
Институт географии СО РАН

Аннотация:

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

The problem of automatizing the mathematical model synthesis (MS) by means of artificial intelligence (AI) methods is considered. The logical (first-order) language of positively constructed formulas and corresponding automatical theorem proving software are used as AI engine. A scheme of MS, methods, implementation technics, and usage technology are considered. A structure synthesis example of a model of forest dynamics and control is described.

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

Примечание

... теорем1
Работа выполнена при финансовой поддержке РФФИ, грант N 01-07-90411-в, и ФППВНШ, N 00-15-96037.

Введение

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

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

В Институте динамики систем и теории управления СО РАН разработаны и внедряются в практику новые средства автоматического доказательства теорем и построения логических выводов (АДТ/ЛВ) в исчислениях над логическим языком первого порядка, языком позитивно-образованных формул (по-формул) [3].

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

Общая схема построения математических моделей

Общая схема построения (синтеза) математической модели нами представляется в следующем виде:

1. На первом этапе производится определение типа модели, исходя из описания предметной области задачи моделирования, свойств исходных данных. По своей сути, эта задача -- задача распознавания образа.

2. Для выбранного типа модели определяется метод построения модели, который может быть более или менее формализованным, т.е. это либо конкретный алгоритм, либо система знаний о предметной области представленной в БЗ системы ПМ.

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

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

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

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

Пример: Модель динамики древостоев

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

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

\begin{displaymath} \Biggl\{ \frac{dx_j}{dt}=\sum_{i\in m(j)}a_{ij}x_i- \sum_{i\in k(j)} a_{ji}x_j, \qquad j=\{1,2,\ldots,n\}. \end{displaymath} (1)

Здесь $x_i$ - число (количество, площадь) элементов (участков), находящихся в состоянии $j$ (с преобладанием определенной породы леса определенного класса возраста); $a_{ij}$ - интенсивность перехода элементов (например, интенсивности смены одной породы одного класса возраста другой породой другого класса возраста) из состояния $i$ в состояние $j$, $a_{ij},a_{ji}>0$, $m(i)\cap k(j) = \emptyset$.

Обычно построение модели "Лесные ресурсы" человеком для заданного региона или лесхоза начинается с анализа состояния лесных ресурсов и природных условий моделируемого региона. Исходной информацией служат данные учета лесного фонда, которые представляют собой таблицы распределения площадей и запасов лесов по преобладающим породам и группам возраста. Данные этих таблиц обновляются каждые пять лет лесоустроительными организациями. В настоящее время ведутся и электронные БД. Кроме того, при разработке графа возрастной динамики лесонасаждений с учетом смены пород в масштабе лесхоза требуется принимать во внимание всевозможные направления смены пород и возрастные циклы древостоев на всей территории лесхоза [5]. Основным источником информации здесь являются научные публикации, отражающие закономерности динамики леса в различных регионах, например [2,7]. Эти материалы корректируются в ходе специальных экспедиционных работ, а также по данным таксационных описаний.

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

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

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

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

Целью нашей работы является автоматизация вышеописанного процесса построения математической модели с помощью применения систем АДТ/ЛВ. Это позволит, в частности, строить интеллектные программные системы, настраиваемые на конкретный объект путем указания (уточнения) необходимых свойств данных об этом объекте, не перестраивая алгоритм существующей программы для учета конкретных свойств нового объекта. Кроме того, в процессе ПМ можно учесть и "дополнительные пожелания" пользователя в виде логических ограничений, добавляемых к существующей БЗ в каждом конкретном случае.

БЗ для этапа 1 (определение типа модели) содержит информацию о приложениях каждой математической модели. Приложение характеризуется предметной областью (областью применения и языком описания), целью моделирования, а также другими характеристиками, специфическими для этой предметной области. Например, в приложениях к прогнозированию динамики лесных ресурсов выделяются [4,5] следующие характеристики:

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

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

Для построения модели ДУД конкретного региона необходимо задать множество состояний $S=\{s_1,s_2,\ldots,s_n\}$, $n\in N$, $m(j),k(j)\subseteq S$, начальные условия $x_j(0)$, идентифицировать коэффициенты модели $a_{ij}$. Метод построения модели ДУД -- это система знаний, частично описанная ниже в виде правил, формализованных в языке по-формул. Заметим, что идентификация коэффициентов и задание начальных условий производятся параллельно построению схематического представления модели.

1. "Для описания динамики лесных ресурсов в геосистеме $a$ типа ландшафт на период в несколько десятков лет необходимо использовать модель типа (1)..." (назовем этот тип моделей "лесн_рес") Сначала требуется "... Ввести состояние, соответствующее площади лесных земель данного ландшафта, не покрытых лесом2." Данному естественно-языковому высказыванию сопоставляется следующая формализация:

\begin{displaymath} \begin{array}{ll} \begin{array}[t]{l} \forall a,t_0:\m... ...дь}(\mbox{\it непокр\_лп},t_0)). \end{array} \end{array} \end{displaymath}

Здесь атом Состояние($m$, $s_0$, непокр_лп, площадь(непокр_лп, $t_0$)) обозначает, что "Состояние $s_0$ соответствует не покрытым лесом землям", причем площадь этого участка определяется с помощью запроса к БД, который представляется как результат выполнения функции площадь. Аргументы функции (тип участка непокр_лп. и момент времени $t_0$3) -- параметры этого запроса, характеризующие свойства результата.

2. "Если в геосистеме $a$ существуют участки леса с преобладающей породой -- сосна_обыкновенная, то добавить в создаваемую модель 6 новых состояний роста этой породы4...". Необходимо найти также площади этих участков. Кроме того, "...Переход сосны обыкновенной в следующий класс возраста происходит, в среднем, через 20 лет. При проведении лесохозяйственных мероприятий (посадка леса) срок зарастания не покрытых лесом площадей сокращается вдвое." Следующая формула формализует это высказывание:

\begin{displaymath} \begin{array}{lll} \begin{array}[t]{l} \forall m,a,s_0... ...).\\ \end{array} \end{array} & \Psi, \end{array} \end{displaymath}

где $\Psi$ содержит правила идентификации скорости зарастания не покрытых лесом участков леса:

\begin{displaymath} \left\{ \begin{array}{ll} \forall\;\; \mbox{\sl Имее... ...реход \hspace{0.3ex}}(m,s_0,s_1,0.05) \end{array} \right. \end{displaymath}

Здесь Переход ($m$, $s_3$, $s_4$, $0.05$) обозначает переход (рост) приспевающих насаждений в спелые леса; интенсивность изменений ($1/20=0.05$) обратно пропорциональна времени, необходимому для перехода из одного состояния в другое (определяется из эмпирических данных). Заметим, что приведенное правило достаточно специфично, его можно обобщить на случай любой породы, данные о которой найдены в таблицах распределения участков леса моделируемого региона. Кроме того, зарастание непокрытых лесом площадей и последовательности смены пород деревьев определяется свойствами исследуемой природной геосистемы, которые можно выявить с помощью формализованных знаний, полученных от эксперта-географа.

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

\begin{displaymath} \begin{array}{lll} \begin{array}[t]{l} \forall m,a,s,f... ...ox{\sl Переход \hspace{0.3ex}}(m,s,s_0,intens). \end{array} \end{displaymath}

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

4. "Рубка лесов производится по достижении им "спелого" класса возраста, характерного для конкретной породы":

\begin{displaymath} \begin{array}{lll} \begin{array}[t]{l} \forall m,a,s,s... ...ox{\sl Переход \hspace{0.3ex}}(m,s,s_0,intens). \end{array} \end{displaymath}

Атом Проблема($a$, моделир_рубки, intens, forest) определяет необходимость моделировать рубки в системе $a$ породы деревьев forest; интенсивность рубки задается значением, получаемым переменной intens. Вырубка ассоциируется с переходом леса из состояния, соответствующего спелым деревьям, в не покрытые лесами площади.

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

Примечание

... лесом2
Гари, вырубки, погибшие от вредителей лесонасаждения, обозначаемые константой непокр_лп.
...$t_0$3
Начальный момент времени.
... породы4
Каждое состояние соответствует площади лесных земель, занимаемых той или иной породой леса определенного класса возраста: "молодняки I-го класса" (молI), "молодняки II-го класса" (молII), "средневозрастные" (ср_возр), "приспевающие" (присп), "спелые" (спел), "перестойные" (перест).

Методика использования и вопросы реализации САПМ

В основе системы принятия решений лежит модуль АДТ/ЛВ КВАНТ [1,6]. Название программы отражает специфику реализованного метода АДТ, базирующегося на типово-кванторных формализмах (не уничтожать кванторы).

Процесс поиска доказательства представляет собой вопросно-ответную процедуру применения единственного правила вывода к базовым подформулам, управляемого набором так называемых модификаторов основной стратегии [1]. Процесс АДТ/ЛВ может быть распараллелен, а также им возможно управлять так называемыми внешними модификаторами основной стратегии поиска АДТ/ЛВ. Основная стратегия задается модификатором "по умолчанию" и является полной стратегией.

Предлагаемая методика использования рассматриваемой технологии базируется на предположении, что модуль КВАНТ присоединяется к основной (интеллектуализируемой) программной системе (ПС) через специальный интерфейсный модуль. Задачей этого модуля является сопряжение по данным и запросам блоков ПС и КВАНТ. Интерфейсный модуль программируется разработчиком ПС с помощью библиотек функций интерфейса прикладного программирования системы КВАНТ. В направлении ПС$\to$КВАНТ этот модуль должен обеспечивать передачу внутренних данных через преобразование в по-представление, которое подразумевает использование атомарных высказываний (атомов) для простых элементов/структур данных (термов), а более сложных формул для представления ограничений. В обратном направлении осуществляется преобразование результатов АДТ/ЛВ, представленных в виде новых фактов, термов, а также частей по-формул, в представление, принятое в ПС. Запросы, поступающие из модуля КВАНТ в процессе построения АДТ/ЛВ, например, вычисления значения некоторого терма, который, в свою очередь, может интерпретироваться как запрос к БД, также передаются через этот модуль.

В настоящее время авторами разрабатываются методики, инструментальные средства и программные модули для реализации интерфейса для модуля КВАНТ. В их основе лежит использование так называемых языков расширения (Lua, Python, Perl, Visual Basic For Applications, и т.д.). С помощью этих языков обеспечивается взаимодействие основного ПО и КВАНТ на уровне объектов этих языков, где, например, некоторая константа, используемая в по-формуле, ассоциируется с определенным объектом используемого языка расширения. Запуск процесса решения некоторой задачи СММ со стороны языка расширения выглядит как запуск некоторой процедуры языка или метода объекта. Программирование стратегий и модификаторов осуществляется средствами этих же языков расширения. При этом "программа" стратегии представляет собой процедуру или функцию языка расширения, манипулирующую структурой по-формулы, представленной в виде объектов этого языка.

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

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

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

Заключение

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

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

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

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

Литература

1
Cherkashin E.A., Vassilyev S.N., Zherlov A.K. Modifiers of Logical Calculi and Their Application to Intelligent Control of Dynamic Systems // In: Proc. of "The First International Conference on Mechatronics and Robotics", 1, Saint-Petersburg, 2000, 21-27.

2
Баранов В. И., Смирнов М. Н. Пихтовая тайга на предгорьях Алтая. Пермь, 1931.

3
Васильев С. Н., Жерлов А. К. Об исчислении типово-кванторных формул // Докл. Акад. Наук, 343, 5, 1995, 583-585.

4
Раздьяконова Т. С., Черкашин А. К., Шепотько И. О. Планирование лесозаготовок с учетом пространственно-временной динамики лесных ресурсов (на примере лесов зоны БАМа) // Планирование и прогнозирование природно-экономических систем, Новосибирск: Наука, 1984.

5
Черкашин А. К. Модели естественной и антропогенной динамики лесных ресурсов.// Планирование и прогнозирование природно-экономических систем, Под. ред. Гурман В. И., Константинов Г. Н., Новосибирск, Наука, 1984, 46-94.

6
Черкашин Е. А. Программная система КВАНТ/1 для автоматического доказательства теорем. Канд. дисс...к.т.н., ИДСТУ СО РАН, Иркутск, 1999.

7
Фуряев В. В., Киреев Д. М. Изучение послепожаровой динамики лесов на ладшафтной основе. Новосибирск, Наука, 1979.
Ваши комментарии
[SBRAS]
[Головная страница]
[Конференции]
[СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации Friday, 07-Sep-2001 14:29:08 NOVST