Software & Systems

Известно, что построение математической модели решаемой задачи для многих предметных специалистов является достаточно сложной проблемой. Возможно, наиболее экономичным путем ее решения является привлечение компьютерных систем, основанных на знании. В качестве примера можно назвать систему САПФИР-АСС, которая создается в рамках методологии автоматизации моделирования, разрабатываемой в Санкт-Петербургском институте информатики и автоматизации РАН [1,2], и является дальнейшим развитием предшествующего ряда систем САПФИР-КОГНИТРОН [3,4].

В подходе, ориентированном на поддержку принятия решений в областях математической и компьютерной некомпетентности пользователей [5,6], формирование математической модели в системе САПФИР-АСС сводится к следующему.

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

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

Заключительный этап – распознавание математической модели, заданной пользователем. Этот этап – компетенция исключительно системы САПФИР-АСС, и пользователь о нем может даже не догадываться. Далее система самостоятельно либо совместно с пользователем выбирает метод решения и использует его для получения возможных вариантов решения [6].

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

х8=х1+х2+х3,                                                      (1)

х9=х2 – х8*х4,                                                    (2)

х10=х9+х5+х6+х7.                                             (3)

Будем считать, что имена переменных в (1)-(3) полностью соответствуют именам переменных в предметной области. Рассмотрим, как будет происходить создание математической модели задачи в этом случае.

Первый этап. Пользователь формирует множество предметных переменных, определяющих, по его мнению, суть решаемой задачи. Пусть предметные переменные носят имена х8, х1, х2, х3. Пользователь вводит имена в систему. Система проверяет наличие введенных переменных в БФО, находит выражение (1), их содержащее.

Второй этап. Система запрашивает ограничения, которым удовлетворяют значения переменных в решаемой пользователем задаче. Пользователь вводит в систему информацию о том, что значение переменной х1 больше 1, но меньше 3; значение переменной х2 равно 5; значение переменной х3 больше 1, но меньше либо равно 2, а значение переменной х8 равно 9.

Третий этап. Система анализирует полученную информацию и по характеру заданных областей определения переменных приходит к выводу, что математической моделью задачи, которую пользователь только что сформулировал, является уравнение х8=х1+х2+х3 с областью допустимых значений переменных х1Î(1,3), х2Î[5,5], х3Î(1,2], х8Î [9, 9].

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

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

Столь категоричное утверждение для БФО, содержащих знания о предметной области, представленные в языке алгоритмических сетей [2], не всегда оправдано. Определим условия, при которых, несмотря на отсутствие в БФО тех или иных переменных, введенных пользователем, сформулированная им задача будет решена системой.

Согласно определению [1], алгоритмическая модель (АМ) есть алгоритм, структуризация вычислительных процедур которого произведена в соответствии с представлениями разработчика о причинно-следственных или временных связях явлений, характеризующих моделируемый объект. Итак, представление БФО системы в виде выражений (1)-(3) в нашем примере отражает представление разработчиков системы о предметной области, для решения задач которой система и предназначена.

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

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

Сформулируем условие, являющееся необходимым для выполнения нашего предположения.

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

х10 = (х2-(х1+х2+х3)*х4)+х5+х6+х7.                 (4)

Любая модель, описанная в рассматриваемом подмножестве языка алгоритмических сетей, относится к классу рациональных (дробно-рациональных) алгебраических функций [7], и может быть представлена суперпозицией функций x+y, x-y, x*y, x/y.

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

Отсюда необходимым условием возможности решения задачи при отсутствии предметной переменной в БФО системы является выполнение соотношения n < N, где n – степень детализации модели; N – максимальная степень детализации модели.

Вернемся к нашему примеру. Для выражения (4) n=2, N=6. Соотношение n < N выполняется, следовательно, возможно решение поставленной задачи за счет детализации модели, хранящейся в БФО. Ниже приведен пример соответствующей детализации:

х12=х1+х3, х13=х12+х2,

х11=х13*х4, х9=х2 – х11,

х14=х6+х7, х15=х14+х5, х16=х9+х15.

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

х12=х1+х3, х13=х12+х2,

х11=х13*х4, х9=х2 – х11,

х14¢=х5+х7, х15¢=х14¢+х6, х16=х9+х15¢.

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

Рассмотрим еще несколько примеров возможной реструктуризации выражения (4):

х8=х1+х2+х3,                                                      (5)

х11=х8*х4,                                                           (6)

х9=х2 – х11,                                                                (7)

х10=х9+х5+х6+х7.                                             (8)

Как видно из примера, в результате суперпозиции функций (5)-(8) появилась новая, по сравнению с исходным представлением модели, предметная переменная х11.

Другой пример:

х12=х1+х3,                                                           (9)

х13=х12+х2,                                                               (10)

х11=х13*х4,                                                               (11)

х9=х2 – х11,                                                               (12)

х10=х9+х5+х6+х7.                                             (13)

В результате суперпозиции функций (9)-(13) появились три новые переменные х11, х12 и х13, а переменная х8 исчезла.

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

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

1. Система осуществляет проверку степени детализации имеющейся у нее модели предметной области. Если степень детализации БФО не является максимальной, переход к пункту 2. Если степень детализации максимальна, с помощью данной БФО решить поставленную задачу нельзя, пользователю выдается соответствующее диагностическое сообщение. Конец работы процедуры.

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

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

4. Система определяет наличие еще не просмотренных пользователем фрагментов БФО, которые можно детализировать. Если такие фрагменты есть, переход к 2. Иначе пользователю выдается соответствующее сообщение. Конец работы процедуры.

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

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

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

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

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

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

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

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

Список литературы

1.        Иванищев В.В., Марлей В.Е. Введение в теорию алгоритмических сетей. - СПб.: Изд-во СПбГТУ, 2000. - 179 с.

2.        Иванищев В.В., Марлей В.Е., Морозов В.П. Система автоматизации моделирования САПФИР-Искра. Основы построения системы. - Л.,1989.- 63с. - (Препр. /ЛИИАН; №99).

3.        Иванищев В.В., Морозов В.П., Михайлов В.В., Бы- ков Я.А., Костельцев А.В. Система искусственного интеллекта для моделирования. - Проблемы информатизации: теоретич. и науч.-практич. журнал / РАН, Мин. науки и техн. политики РФ. - М., 1996.- Вып.1. - С.51-55.

4.        Морозов В.П. Технология построения моделей и решения задач в системе автоматизации моделирования САПФИР-Искра87 // Вопросы алгоритмического моделирования сложных систем. - Л.:ЛИИАН,1989.- С.32-49.

5.        Морозов В.П. Программные системы, ориентированные на привлечение знаний экспертов в процессе решения задач. // Программные продукты и системы. - №1. - 2001. - С.33-35.

6.        Морозов В.П. Система интегрированного управления проектами САПФИР АСС // VII Междунар. конф.: Региональная информатика-2000 (“РИ-2000”, Санкт-Петербург, 5-8 декабря 2000 г.)/ Тр. конф. - СПб., 2001. - С.283-285.

7.        Морозов В.П. Задачи на вычисление при наличии ограничений. Метод обращения // Алгоритмическое моделирование, инструментальные средства и модели. - СПб.: СПИИРАН,1992. - C.112-137.