НАУКА и ОБРАЗОВАНИЕ

E. P. Пантелеев, канд. техн. наук,

Д. А. Куликов, Ивановский государственный энергетический университет

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

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

Многие задачи проектирования и организационного управления (поиск рациональных вариантов прокладки коммуникаций, планирование транспортных потоков, размещение узлов обслуживания, составление расписаний) по существу сводятся к принятию решений о распределении и синхронизации использования человеческих, финансовых, материальных или информационных ресурсов. Актуальным источником информации о распределяемых ресурсах на этапе порождения альтернатив, предшествующем в классической схеме принятия решений выбору наилучшего варианта, служат реляционные базы данных. Таким образом, проблема порождения альтернативных вариантов распределения ресурсов сводится к построению недетерминированного запроса к базе данных, результатом исполнения которого и будет искомое множество вариантов. Наиболее приемлемым для построения и исполнения таких запросов является вычислительный формализм Пролога, объединяющий декларативную семантику запроса с процедурной семантикой поиска вариантов его согласования. Перспективность CPR-архитектур¹ подтверждается значительным числом реализаций [1]. Однако задача порождения альтернатив на реляционной модели данных имеет специфику, которая в этих реализациях отражения не нашла, а именно:

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

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

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

Архитектура Среды порождения альтернатив показана на рис. 1. Порождающая модель определяет понятие допустимой альтернативы на языке фраз Хорна. Определения строятся на модели данных, сформированной интерфейсом БД, с использованием предикатов API — интерфейса, основное назначение которых состоит в реализации более эффективных, по сравнению с полным перебором, стратегий вычисления. Прологоподобная обрабатывающая структура генерирует на порождающей модели множество альтернатив, элементы которого можно трансформировать интерфейсом базы данных в формат реляционных таблиц.

Рис. 1. Архитектура Среды порождения альтернатив

Графический интерфейс Среды порождения альтернатив с базой данных основан на представлении логической структуры базы в виде диаграммы сущность — связь (ER-модели), т. е. иерархического орграфа Мⁱ (рис. 2), узлы  которого соответствуют объектным Е и связным R модель сущностям, а дуги А определяют отношения между ними:

Рис. 2. ER-модель в задаче составления расписания учебных занятий

Объектные сущности — это множества объектов, составляющие предметное наполнение базы данных. Связные сущности — это отношения, определенные -на смежных по исходящим дугам ER-модели вершинах-множествах. Заданная пользователем ER-модель обеспечивает автоматическое формирование множества однопредикатных SQL-запросов (селекции) для заполнения сопоставленных узлам модели таблиц исходной информацией. В отличие от других средств генерации (таких, например, как MS Query), назначение которых исчерпывается формированием запросов, ER-модель Среды является семантической основой модели порождения альтернативы. Выполняемое ER-моделью связывание базы данных со Средой происходит независимо от процесса порождения альтернатив (статически). Архитектура, "развязывающая" эти два процесса во времени (в предположении, что вся релевантная задаче информация базы данных доступна до начала решения), упрощает интерфейс базы данных и повышает эффективность порождения альтернатив.

Оба типа сущностей ER-модели рассматриваются в Среде порождения альтернатив как множества. Однако для связных сущностей столь же естественна, но более содержательна теоретико-графовая интерпретация, которая реализована в предлагаемом подходе на основе понятия гиперграфа³. Это полезное обобщение понятия графа на случай, когда ребрами могут служить произвольные, а не только двух- и одновершинные подмножества. Использование гиперграфов обеспечивает естественную формализацию отношений типа "многие—к—многим" (рис. 3).

Рис. 3. Теоретико-графовое представление отношения "нагрузка" в задаче составления расписания:

а — фрагмент ER-модели; б — гиперграф связного отношения

На уровне метамодели Среды порождения альтернатив сущности ER-модели определяются как переменные предопределенного множественного типа, а их элементы (объекты) — как структурированные термы:

(Объект): :=объект ((Идентификатор)) (объект ((Идентификатор), (Список_атрибутов)) (Идентификатор): : =(Ключ)| связь ((Ключ), (Ключ)) (Список_атрибутов): : =(Атрибут) | (Атрибут), (Список_атрибутов)

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

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

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

(Атрибут): : =<Имя><Предикат_отношения><Выражение> <Предикат_отношения>: : => ׀ >= ׀ = ׀ <> ׀ <= ׀ <

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

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

                                                            * * * /

Макс Степень Вершины (Гиперграф, Макс Степень, объект (_,Арг=А),А),подграф (Гиперграф, Подграф, объект (связь (Ключ,_)),

Степень Вершины (Гиперграф, Макс Степень, объект (связь (Ключ,_),Арг=В),В)),

* * * /

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

Реализация теоретико-множественных и теоретико-графовых объектов базируется на понятии операционного контекста. Операционный контекст есть последовательность операций О, преобразующая исходное состояние s⁰ объектной или связной сущности в ее текущее состояние s^l. Обусловленная И-недетерминизмом Среды порождения альтернатив возможность параллельного применения к текущему состоянию нескольких операций позволяет говорить о сопоставленном связной сущности дереве контекстов Т = (S, О), корень которого соответствует состоянию s⁰ сущности на момент активизации процесса порождения альтернатив, а путь из корня в каждую из терминальных вершин отождествляется с одним из контекстов (рис. 4). В формировании контекста участвуют определенные на графах и множествах унарные операции добавления/удаления элемента, би­нарные множественные и графовые операции объединения, пересечения, разности, произведения,

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

Например, S₃ = S₁  S₂, где S₁ = {3, 4, 5}, S₂ = {1, 2, 3} эквивалентно суперпозиции примененных к состоянию S₁ операций включить (S₁, S₁₁, объект(4)), включить (S₁₁, S₃, объект (5)). Обратимость унарных операций обеспечивает восстановление прежнего состояния при откате путем применения к текущему состоянию соответствующих обратных операций. Унификация состояний сущностей в нетривиальном случае (связанные переменные, адресующие различные контексты) выделяет минимальное поддерево, содержащее оба соответствующих контекста, затем одно из состояний буферизуется и к нему применяется последовательность операций, которые образуют путь от буферизованного до второго унифицируемого состояния, проходящий через вершину поддерева.

Рис. 4. Дерево контекстов

Если результирующее состояние S₂ = О^m (О^-n (S₁)) совпадает с буферизованным, унификация успешна. Таким образом, понятие контекста органично вписывается в базовые механизмы метода резолюции, абсолютно прозрачно для пользователя, а также решает в рамках простейшей одностековой архитектуры проблему восстановления стека управления при возврате по удаче.

Естественное в логической среде порождение альтернатив полным перебором вариантов практически неэффективно. Теоретико-графовая интерпретация связных сущностей создает предпосылки для формализации задач в терминах полиномиально-эффективных алгоритмов анализа и оптимизации на графах. Рассмотрим в качестве примера предложенный в [3] подход к формализации задачи составления "плотного" расписания равнодлительных учебных занятий. Данный подход использует представление учебной нагрузки в виде гиперграфа Н = (X, Y, R), множество вершин X которого соответствует преподавателям, множество ребер Y — классам, а инцидентор R (x, у) — учебным занятиям преподавателя x в классе у. ER-модель данных для этой задачи и представление нагрузки в виде графа показаны на рис. 2 и 3 соответственно. Идея подхода состоит в разбиении отнесенного гиперграфу нагрузки графа Кенига

,

где , на минимальное число паросочетаний⁴. Каждое паросочетание содержательно соответствует множеству занятий, которые могут проводиться одновременно. Подход реализуется полиномиально-эффективными итерациями, которые выполняются, пока граф K(H) не пуст:

·        построить паросочетание P, которое насыщает все вершины с максимальной степенью в K(H);

·        построить паросочетание P₁, которое насыщает все вершины с максимальной степенью в X;

·        построить паросочетание P₂, которое насыщает все вершины с максимальной степенью в Y;

·        получить Р из P₁ и Р₂;

·        удалить Р из K(H).

Ниже приведены реализующие данный подход определения порождающей модели, семантика которых отражена в названиях предикатов⁵:

Плотное Расписание ({},_,{}).

Плотное Расписание (Нагрузка, График, Расписание):-

Макс Степень Вершины (Нагрузка, Макс Нагрузка Учителя, объект (_,Уроки=А) ,А) , Подграф(Нагрузка, Подграф1, объект (связь (Учитель, )),

Степень (Нагрузка, Макс Нагрузка Учителя, объект (связь (Учитель,_), Уроки=В),В)), Макс Степень Ребра (Нагрузка, Макс Нагрузка Класса, объект (_,Уроки=С) , С) , Подграф (Нагрузка, Подграф2, объект (связь (_, Класс)),

Степень (Нагрузка, Макс Нагрузка Класса, объект (связь (__, Класс) ,Уроки=О) ,D) ) , Макс Паросочетание (Подграф1 , Паросочетание!), Макс Паросочетание (Подграф2, Паросочетание2), Насыщение(Паросочетание1, Паросочетание2), Разность(Нагрузка, Паросочетание, Нагрузка 1), Извлечь(График, График1, объект (Слот)), Плотное Расписание(Нагрузка1, График1, Расписание1) ,

Произведение (Паросочетание, {объект (Слот)), Расписание Урока),

Объединение (Расписание Урока, Расписание1, Расписание).

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

Реализованный в Среде порождения альтернатив механизм поиска с возвратом порождает варианты решения последовательно. Проблема управления выводом заключается в том, что из-за противоречивости составляющих векторной оценки приходится рассматривать множество альтернатив, не доминируемых по заданному бинарному отношению предпочтения. В предлагаемой реализации порождение множества недоминируемых альтернатив выполняет встроенный предикат Найти, реализующий локальный цикл поиска с возвратом для конъюнкции предикатов М (порождающая модель альтернативы), R (отношение доминирования — фильтр альтернатив) и Вывод (запоминание альтернатив, прошедших фильтрацию), указанных в качестве его аргументов:

Найти (М (. . . , X, . . . ), R (X) , Вывод (X) ) ,

Порожденная моделью М альтернатива X представлена одновременно в параметрическом (как отношение) и критериальном (в виде вектора координат, число и тип которых определяется в процессе редактирования соответствующего узла ER-модели) пространствах. Отношение доминирования (необязательный элемент конъюнкции) может быть задано предикатом пользователя, трактующим альтернативу как точку критериального пространства, или встроенным предикатом "!" (отсечение), ограничивающим локальный поиск первым допустимым решением. Отсутствие фильтра означает порождение и сохранение всего множества допустимых альтернатив. Пример реализации пользовательского отношения доминирования:

Парето (X):-Для Каждого (Y,S, Для Каждого(i,X[i] >= Y[i]),

Существует(i,X[i]>Y[i])).

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

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

Плотное Расписание (Нагрузка, График, Расписание), !,

Найти (Вариант Расписания (График, Расписание, Вариант) ,Парето (Вариант) ,Вывод (Вариант) )

определяет множество недоминируемых по Парето альтернатив, каждая из которых удовлетворяет ограничению на отсутствие "окон" у классов и представлена точкой в двумерном критериальном пространстве "неравномерность распределения учебных занятий по дням недели" — "наличие "окон" у преподавателей". Отношение Перестановка порождающей модели определяет удовлетворяющий ограничению вариант расписания в терминах перестановок слотов на множестве ГРАФИК, отношение Критерий формирует значения составляющих вектора оценки варианта, встроенный предикат Создать Запись конструирует представление альтернативы для последующей записи в хранилище ГРАФИК (см. рис. 2):

Таблица 1 Фрагмент реляционного представления учебной нагрузки

Таблица 2 Фрагмент реляционного представления расписания

Вариант Расписания (График, Расписание, Вариант) : -

Номер Слота=1,

Размер Кластера=5, /* Максимальное количество уроков  в день */

Перестановка (График, {}, График1, Расписание, Номер Слота, Размер Кластера), Критерий(График1, Расписание, Неравномерность, Окна),

Создать Запись (Вариант, График1, Неравномерность, Окна).

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

Таблица 3. Фрагмент проекции расписания: Занятость преподавателя Кабанова

В настоящее время β-версия Среды апробируется на задачах распределения ресурсов в области управления учебным процессом ИГЭУ и автоматизации конструкторского проектирования (компоновка модулей). В перспективе программный продукт предназначен для OLE-интеграции в комплексы средств принятия решений различной прикладной ориентации, прежде всего в создаваемый в ИГЭУ комплекс управления качеством образования.

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

1. Чери С, Готлоб Г., Танка Л. Логическое программирование и базы данных: Пер. с англ. М.: Мир, 1992. 352 с.

2. Зыков А. А. Гиперграфы // Успехи математических наук 29:6 (1972). С. 89-154.

3. Свами С, Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. М.: Мир, 1984. 455 с.

Сноски

1 Coupling Prolog to Relational databases — связывание Про­лога с реляционными базами данных.

2 Среда реализации — MS Windows'95, C++ 5,0, драйвер базы данных — MS ODBC 2.0.

3 Согласно [2], гиперграф H есть тройка (X, Y, R), где X — множество вершин, Y — множество произвольных непустых подмножеств X, называемых гиперребрами, R(x, у) — двухместный предикат, задающий отношение инцидентности между элементами множеств Х и Y(инцидентор).

4 Согласно [3], паросочетание  есть подмножество попарно несмежных ребер графа. Паросочетание с наибольшим числом ребер максимально.

5 Подчеркиванием выделены определения пользователя, жирным шрифтом — определения интерфейса API.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 8, 1998

МЕТОДЫ ОПТИМИЗАЦИИ

Ключевые слова: Распределение ограниченных ресурсов, декларативная и процедурная семантика, ПРОЛОГ, операционный контекст, теория расписаний.