Введение
Распределенная оптимизация ограничений (DCOP или DisCOP) является распределенным аналогом оптимизации ограничений. DCOP – это задача, в которой группа агентов должна совместно выбирать значения для набора переменных таким образом, чтобы минимизировать стоимость набора ограничений, определенных для этих переменных. Распределенное удовлетворение ограничений – это подход к описанию задачи в терминах ограничений, известных и обеспечиваемых различными участниками (агентами). Ограничения определены для некоторых переменных с предопределенными областями значений и требуют, чтобы этим переменным были присвоены согласованные значения разными агентами. Задачи, сформулированные в рамках этого подхода, могут быть решены любыми алгоритмами, разработанными для него. Этот подход использовался под различными названиями еще в 1980-х годах. Первое известное использование современного названия относится к 1990 году.
DCOP
Основными компонентами задачи DCOP являются агенты и переменные. Важно отметить, что каждая переменная принадлежит агенту; это и делает задачу распределенной. Формально, DCOP – это кортеж, где: – множество агентов, – множество переменных, – множество доменов переменных, где каждый является конечным множеством, содержащим возможные значения переменной. Если содержит только два значения (например, 0 или 1), то называется бинарной переменной. – функция стоимости. Это функция, которая отображает каждое возможное частичное назначение в стоимость. Обычно лишь немногие значения не равны нулю, и представляется в виде списка кортежей, которым присвоено ненулевое значение. Каждый такой кортеж называется ограничением. Каждое ограничение в этом наборе – это функция, присваивающая вещественное значение каждому возможному назначению переменных. Некоторые специальные виды ограничений:
Унарные ограничения – ограничения на одну переменную, то есть для некоторого .
Бинарные ограничения – ограничения на две переменные, то есть для некоторого .
– функция владения. Это функция, отображающая каждую переменную в связанного с ней агента. означает, что переменная «принадлежит» агенту . Это подразумевает, что агент несет ответственность за присвоение значения переменной . Обратите внимание, что не обязательно является инъекцией, то есть один агент может владеть более чем одной переменной. Также не обязательно является сюръекцией, то есть некоторые агенты могут не владеть никакими переменными. – целевая функция. Это оператор, который агрегирует все индивидуальные стоимости для всех возможных назначений переменных. Обычно это достигается посредством суммирования:
is the set of agents, is the set of variables, is the set of variable domains, <math>\{D 1, D 2, \dots, D { where each is a finite set containing the possible values of variable If contains only two values (e. g. 0 or 1), then is called a binary variable. is the cost function. It is a function that maps every possible partial assignment to a cost. Usually, only few values of are non zero, and it is represented as a list of the tuples that are assigned a non zero value. Each such tuple is called a constraint. Each constraint in this set is a function assigning a real value to each possible assignment of the variables. Some special kinds of constraints are:
Unary constraints constraints on a single variable, i. e., for some Binary constraints constraints on two variables, i. e, for some is the ownership function. It is a function mapping each variable to its associated agent. means that variable "belongs" to agent This implies that it is agent 's responsibility to assign the value of variable Note that is not necessarily an injection, i. e., one agent may own more than one variables. It is also not necessarily a surjection, i. e., some agents may own no variables. is the objective function. It is an operator that aggregates all of the individual costs for all possible variable assignments. This is usually accomplished through summation:
Цель DCOP состоит в том, чтобы каждый агент присваивал значения своим связанным переменным, чтобы либо минимизировать, либо максимизировать для данного назначения переменных.
Задания
Присвоение значения – это пара (x, v), где v – элемент домена x. Частичное присвоение – это набор присвоений значений, в котором каждый x встречается не более одного раза. Оно также называется контекстом. Это можно представить как функцию, отображающую переменные в DCOP на их текущие значения: обратите внимание, что контекст по сути является частичным решением и не обязан содержать значения для каждой переменной в задаче; следовательно, отсутствие x в контексте означает, что агент еще не присвоил значение переменной x. При таком представлении "домен" (то есть набор входных значений) функции f можно рассматривать как множество всех возможных контекстов для DCOP. Поэтому в остальной части этой статьи мы можем использовать понятие контекста (то есть функцию) в качестве аргумента функции f. Полное присвоение – это присвоение, в котором каждый x встречается ровно один раз, то есть всем переменным присвоены значения. Оно также называется решением DCOP. Оптимальное решение – это полное присвоение, в котором целевая функция оптимизируется (то есть максимизируется или минимизируется, в зависимости от типа задачи).
A partial assignment is a set of value assignments where each appears at most once. It is also called a context. This can be thought of as a function mapping variables in the DCOP to their current values:
Note that a context is essentially a partial solution and need not contain values for every variable in the problem; therefore, implies that the agent has not yet assigned a value to variable Given this representation, the "domain" (that is, the set of input values) of the function f can be thought of as the set of all possible contexts for the DCOP. Therefore, in the remainder of this article we may use the notion of a context (i. e., the function) as an input to the function. A full assignment is an assignment in which each appears exactly once, that is, all variables are assigned. It is also called a solution to the DCOP. An optimal solution is a full assignment in which the objective function is optimized (i. e., maximized or minimized, depending on the type of problem).
Примеры задач
Различные задачи из разных областей могут быть представлены в виде DCOP.
Распределенная окраска графа
Проблема раскраски графа формулируется следующим образом: задан граф и набор цветов, необходимо присвоить каждой вершине *vᵢ* цвет *cᵢ* так, чтобы количество смежных вершин, имеющих одинаковый цвет, было минимальным. В рамках DCOP (Distributed Constraint Optimization) каждому узлу графа соответствует один агент, отвечающий за выбор цвета для этого узла. Каждый агент имеет одну переменную, область значений которой содержит *k* элементов (по одному значению для каждого возможного цвета). Для каждой вершины *vᵢ* существует переменная *xᵢ* с областью значений {1, ..., *k*}. Для каждой пары смежных вершин *vᵢ* и *vⱼ* существует ограничение, определяющее стоимость 1, если обеим соответствующим переменным присвоены одинаковые цвета: *cost(xᵢ, xⱼ) = 1, если xᵢ = xⱼ, и 0 в противном случае*. Цель состоит в минимизации общей стоимости.
Проблема распределенных многочисленных рюкзаков
Распределенная многовариантная постановка задачи о рюкзаке выглядит следующим образом: задан набор предметов различного объема и набор рюкзаков различной вместимости. Необходимо назначить каждый предмет в рюкзак таким образом, чтобы минимизировать объем переполнения. Пусть – множество предметов, – множество рюкзаков, – функция, отображающая предметы в их объем, а – функция, отображающая рюкзаки в их вместимость. Чтобы закодировать эту задачу как DCOP, для каждого создадим одну переменную с соответствующей областью значений . Затем для всех возможных контекстов : где представляет собой общий вес, назначенный контекстом рюкзаку .
Проблема распределения распределенных элементов
Проблема распределения предметов заключается в следующем. Есть несколько предметов, которые необходимо распределить между несколькими агентами. Каждый агент имеет свою собственную оценку для каждого предмета. Цель состоит в оптимизации некоторой глобальной цели, такой как максимизация суммы полезностей или минимизация зависти. Проблему распределения предметов можно сформулировать как DCOP следующим образом. Для каждого агента i и предмета j добавьте бинарную переменную vij. Значение переменной равно "1", если агент получает предмет, и "0" в противном случае. Переменная принадлежит агенту i. Чтобы выразить ограничение, что каждый предмет может быть отдан не более чем одному агенту, добавьте бинарные ограничения для каждой пары различных переменных, связанных с одним и тем же предметом, с бесконечной стоимостью, если обе переменные одновременно равны "1", и нулевой стоимостью в противном случае. Чтобы выразить ограничение, что все предметы должны быть распределены, добавьте n-арное ограничение для каждого предмета (где n – количество агентов), с бесконечной стоимостью, если ни одна переменная, связанная с этим предметом, не равна "1".
Подходы к решению ADCOP
Простой способ решения задачи ADCOP — заменить каждое ограничение на ограничение, равное сумме функций. Однако это решение требует от агентов раскрытия своих функций стоимости. Часто это нежелательно из соображений конфиденциальности. Другой подход называется «Частные события как переменные» (PEAV). В этом подходе каждая переменная, помимо собственных переменных, также владеет «зеркальными переменными» всех переменных, принадлежащих её соседям в сети ограничений. Существуют дополнительные ограничения (со стоимостью, равной бесконечности), гарантирующие, что зеркальные переменные равны исходным переменным. Недостатком этого метода является то, что количество переменных и ограничений значительно больше, чем в исходной задаче, что приводит к увеличению времени выполнения. Третий подход — адаптировать существующие алгоритмы, разработанные для DCOP, к структуре ADCOP. Это было сделано как для алгоритмов полного перебора, так и для локального поиска. Гарантированная личная выгода: агенты соглашаются действовать на общее благо, если их собственная полезность не ниже, чем в условиях отсутствия сотрудничества (то есть конечный результат должен быть улучшением Парето по сравнению с исходным состоянием). Лямбда-сотрудничество: существует параметр λ. Агенты соглашаются действовать на общее благо, если их собственная полезность не ниже, чем λ, умноженная на их полезность в условиях отсутствия сотрудничества. Решение таких задач частичного сотрудничества в ADCOP требует адаптации алгоритмов ADCOP.
Книги и обзоры
Глава в сборнике. См. главы 1 и 2; доступна для бесплатного скачивания онлайн.