Постановка проблемы

Структура рассмотренной в [8] специализированной оболочки для построения интеллектуальных САПР и АСНИ включает в себя средства для организации интерфейсов со специализированными САПР, ориентированными на различные предметные области. Цели создания таких интерфейсов следующие:

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

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

Общий метод решения проблемы

Для решения данной задачи рассматривалась прямая и обратная постановка задачи. Прямая постановка задачи предполагала конвертацию данных из БД оболочки в Excel-таблицу, а обратная – конвертацию данных из Excel-таблицы в БД оболочки. Решение задачи в обоих постановках требовало решения разнообразных подзадач. Например, для решения задачи в обратной постановке необходимо: сформировать существующую постановку задачи для данной Excel-таблицы, т.е. определить, что имеется на ее входе, а что на ее выходе; сформировать набор таблиц DBF; выяснить у пользователя новую постановку задачи; трансформировать набор таблиц DBF в соответствии с новой постановкой задачи.

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

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

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

Суть концепции недоопределенных вычислительных моделей, предложенной А.С. Нариньяни [1] в развитие работ Э.Х. Тыугу [2], заключается в том, что величинам приписываются недоопределенные значения, определяющие область возможных значений (перечисление, интервал). Значения связываются друг с другом ограничениями, представляющими собой некоторые математические выражения. Интерпретация этих ограничений, выполняемая по потоковому алгоритму, позволяет уточнять связываемые ими недоопределенные значения. Задав набор ограничений – вычислительную модель, можно получить в результате ее интерпретации значения искомых величин, удовлетворяющие наложенным ограничениям, или обнаружить противоречие в этих ограничениях. Вычислительная модель при таком подходе играет роль спецификации задачи, а значения величин являются как входными параметрами задачи, так и ее выходными результатами. Недостатком метода недоопределенных моделей выступает статически задаваемая жесткая связь элементов системы, не позволяющая перестраивать структуру всей системы в целом в процессе работы. Принцип монотонности изменения значений, характерный для недоопределенных моделей, является существенным ограничением, поскольку позволяет лишь уточнять значения величин, но не изменять их, в соответствии с динамикой развития моделируемой системы.

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

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

1. Каждая модель рассматривается независимо от других моделей, т.е. отсутствует уровень функциональной сети.
2. В качестве ограничений принимается только равенство — это означает, что модель описывается системой уравнений, связывающих входные значения с выходными параметрами.
3. На нижнем уровне фактически существует только один объект – таблица моделирующей системы (табличного процессора типа Excel), слотами которого являются ячейки таблицы, содержащие значения-константы или формулы.

Математическая постановка задачи и методы решения

3.1. Математическая постановка задачи

Рассмотрим вычислительную модель. Пусть X = { x_i | i = 1..N } – множество входных параметров, Y = { y_j | j = 1..M } – множество выходов (зависимых переменных), а связи задаются в виде функций:

Y₁ = f₁( X );
Y_k = f_k( X, y₁..y_k-1 ), k = 2..M. (*)

Полученная модель C=(X, Y, F) позволяет по известным входным параметрам рассчитать зависимые переменные за одну итерацию. Если определить Y_k = f_k( X, Y ), k = 1..M, то будет получена рекурсивная модель. Если рассматривать описанную выше модель в терминах объектно-ориентированного подхода [2], то получим локальную модель, в качестве операций ограничений в которой используются отношения равенства (путем замены в формулах (*) присваивания на равенство). Рассмотренная выше модель является статической в том смысле, что наборы входных и выходных переменных, а, следовательно, и порядок вычислений в ней жестко определен и не может быть изменен без перестройки модели. Формально задача выглядит следующим образом. В модели (*) X' параметров сделать выходными путем введения Y' входных параметров, причем X'⊆X и Y'⊆Y. Фактически требуется построить новые функции f', которые бы вычисляли новые выходные параметры по оставшимся старым и введенным новым входным, т.е. пусть:

X"⊆X\X', Y"⊆Y\Y', тогда ∀y_i∈X'∪Y": y_i = f'_i( X" ∪ Y' ∪ X' ∪ Y") (**)

Определение: Функция f несущественно зависит от параметра x_i, если любое изменение параметра x_i не изменяет значения функции f.

Определение: Функция f существенно зависит от параметра x_i, если какое-либо изменение параметра x_i изменяет значение функции f.

3.2. Метод решения для частного случая

Сначала рассмотрим частный случай данной задачи. Дано: (*), (**), причем X'={ x_k }, Y'= { y_j }. Найти: f'_i, такие что: y₁=f'₁( X", y_j); y_i=f'_i( X", y_j, y₁..y_i-1), i=2..M-1, i≠j; x_k=f'_M(X", Y). Решение будем искать следующим образом:

Алгоритм 1.
Исходные данные: C=(X, Y, F) – исходная вычислительная модель; y_j∈Y – новый входной параметр; x_k∈X – новый выходной параметр.
Результат: C'=(X \ {x_k} ∪ {y_j}, Y \ {y_j} ∪ {x_k}, F') – новая вычислительная модель.

1. Если y_j несущественно зависит от x_k, то решения нет.
2. В первоначальной формуле y_j=f_j(X, y₁..y_j-1) вместо всех y_m, которые существенно зависят от x_k, подставим их функции f_m. (Обозначим множество y_m, m=1..j-1, несущественно зависящих от x_k как Z). Получим y_j=g_j(X", Z, x_k).
3. Результат шага 1 приведем к виду g_j(X", Z, x_k) - y_j = 0. Найдем аналитическое решение уравнения шага 2: x_k = f'_M( X", Z, y_j). Получаем решение данного частного случая: y₁=f₁( X", y_j); y_i=f_i( X", y_j, y₁..y_i-1), i = 2..M-1, i ≠ j; x_k=f'_M(X", Y).

3.3. Метод решения общей задачи

Общая задача сводится к частной. Рассмотрим V = X'×Y'. Для каждого элемента (x_i, y_j) этого множества можно выполнить алгоритм 1 решения частного случая, причем X' для алгоритма 1 будет содержать только первый элемент пары из множества V, а Y' – только второй. Если алгоритм 1 неуспешен для этой пары – пара изымается из множества V. Если множество пусто (V = ∅) то вернуться на шаг назад. Если алгоритм 1 успешен для пары, то переход к следующему шагу: из множества V удаляются все элементы, содержащие в качестве первой компоненты x_i, из множества X' удаляется x_i, из Y' – y_j. Если множество X' пусто – конец алгоритма.

Алгоритм 2.
Исходные данные: C=(X, Y, F) – исходная вычислительная модель; X'∈X – множество новых результатов (выходных параметров); Y'∈Y – множество новых исходных данных (входных параметров).
Результат: C'=(X" ∪ Y', Y" ∪ X', F') – новая вычислительная модель.

1. Если X' = ∅ , то C' = C. Алгоритм успешно завершен. Все.
2. Определим V = X' × Y'.
3. Пока V ≠ ∅ : Берем (x, y) ∈ V.
4. Если алгоритм 1 с параметрами (C, x, y) успешен (результат сохраняется в С'), то вызвать алгоритм 2 с параметрами (C', X' \ {x}, Y'). Результат последнего вызова, а также его успешность являются результатами работы алгоритма. Все.
5. Если вызов алгоритма 1 с параметрами (C, x, y) неуспешен, то V = V \ { (x, y) }, повторить шаг 2.
6. Если V = ∅ , то алгоритм потерпел неудачу. Все.

3.4. Метод поиска аналитического решения уравнения

Задача преобразования модели сводится к задаче нахождения аналитического решения уравнения (см. п. 2 алгоритма 1). Последняя задача по своей сложности является алгоритмически неразрешимой для всего класса функций, имеющих вектор аргументов и значение-скаляр. (Простейший тому пример – уравнение x⁵ + ax⁴ + bx³ + cx² + dx + e = 0). Однако, большой класс задач характеризуется примитивными функциями, для которых найти решение относительно одного из аргументов не сложно, или же функциями, для которых явно определены обратные. К такому классу задач относятся, в частности, и многие экономические задачи [7]. Решение уравнения будем проводить рекурсивно в 2 этапа: построение шаблона функции и поиск шаблона в базе знаний.

Определение: Выражение – это: число; переменная из списка допустимых; функтор, за которым в скобках перечислены выражения.

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

Определение: Константной частью называется: число; переменная из множества X"+Y'; функция, аргументы которой – константные части.

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

Определение: Шаблон функции – функция, построенная на основе искомой, все константные части которой заменены символом CONST. Шаблон некоторой функции f будем обозначать Ш( f ).

Определение: Функция f эквивалентна функции g, если Ш(f)=Ш(g). Обозначение: f ≡ g.

Шаблон функции строится следующим образом:

Алгоритм 3
Исходные данные: f – функция. Результат: Ш( f ) – шаблон функции.

1. Все константные части заменяются на CONST. Если такие части не найдены, то переход на шаг 3, иначе на шаг 2.
2. Осуществляются алгебраические преобразования, такие как: раскрытие скобок, приведение к общему знаменателю, сортировка аргументов для коммутативных операций в таком порядке, чтобы все аргументы – CONST оказались в конце списка аргументов, приведение подобных, замена производных операций (вычитание, деление) прямыми (соответственно сложение, умножение) с обращением всех аргументов кроме первого посредством обратных функций (соответственно унарный минус, 1/x). Если такие операции выполнены, то переход на шаг 1, иначе на шаг 3.
3. Все.

База знаний представляет собой множество кортежей вида (Шаблон для сравнения – Ш_с, Результат решения – Р_р). Если Ш( f ) = Ш_с, значит решение f (x_k) относительно x_k эквивалентно Р_р. Решение строится следующим образом. На этапе сравнения Ш( f ) с Ш_с всем CONST Ш_с ставятся в соответствие CONST из Ш( f ). В Р_р все CONST заменяются связанными функциями из соответствующих CONST функции f. Полученная форма есть результат решения уравнения f(x_k) = 0 относительно x_k. Если ни один шаблон базы знаний не совпадает с построенным шаблоном функции, то построенный шаблон усложняется (например, вместо x + CONST ставится CONST * x + CONST), после чего выполняется новый цикл поиска по базе знаний. Процесс усложнения идет следующим образом: сначала к переменной без константного множителя добавляется множитель CONST, при этом отмечается, что этот CONST соответствует единице, если в выражении с операцией сложения нет CONST, туда добавляется CONST тоже. Если поиск во всех случаях неудачен, алгоритм поиска решения терпит неудачу. В дальнейшем пользователь может пополнить базу знаний шаблоном для указанного уравнения. В конечном итоге, класс решаемых уравнений зависит от наполненности базы знаний.

В качестве языка реализации был выбран Object Pascal (компилятор Borland Delphi) [5]. Данный выбор объясняется простой и вместе с тем мощной реализацией в данном языке концепции объектов [4], универсальностью языка программирования, удобством написания и отлаживания программ в среде Borland Delphi IDE.

Заключение

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