Схема выбора эффективной комбинации слотов

Для отыскания -оптимальной стратегии выполнения системы заданий необходимо формирование стратегий, которые являются условно оптимальными по частным критериям и удовлетворяют (3.4.2)-(3.4.4).

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

Тогда для (3.3.1), (3.3.2) справедливо

, ,

, .                               (3.4.7)

Для схемы (3.3.3), (3.3.4)

, ,

, .                               (3.4.8)

Условно оптимальный набор слотов для выполнения -го задания будем обозначать через .

Условно оптимальная комбинация слотов  определяется из уравнения

, ,                (3.4.9)

где значения  получаются из (3.4.7), (3.4.8).

Так, в множество условно оптимальных (при заданном ) входит комбинация слотов (1, 2, 3), полученная при решении задачи в подразделе 3.3.3, когда . Все три комбинации слотов, упомянутые в подразделе 3.3.3, условно оптимальны по критерию  в соответствии с (3.4.9), поскольку они образуют множество альтернатив, являющееся внутренне и внешне устойчивым в соответствующей модели выбора, где бинарное отношение вида (3.4.2) порождается критерием . Условно оптимальными являются комбинации (1, 2, 4) и (2, 2, 4), полученные при решении соответствующей задачи в подразделе 3.4. Они дают суммарное время выполнения пакета заданий, соответственно равное 9 и 7 единицам времени, а затраты составляют 13 и 16 единиц.

При применении схем (3.3.1), (3.3.2) и (3.3.3), (3.3.4) для каждого из критериев эффективности  верны соотношения (3.4.2)-(3.4.4). Действительно, условно оптимальные комбинации слотов согласно (3.4.9) образуют внутренне устойчивое множество комбинаций  в модели выбора . Внешняя устойчивость  следует из того, что . Наборы вида (3.4.9) позволяют построить условно оптимальные стратегии и в конечном итоге найти -оптимальную стратегию и наиболее эффективную комбинацию слотов для выполнения пакета заданий.

Обозначим через  и  стратегии, условно оптимальные по критерию , полученные соответственно по схемам обратной (3.3.1), (3.3.2) и прямой (3.3.3), (3.3.4) прогонки. Заметим, что в общем случае . Пусть  является -оптимальной стратегией в модели выбора , где бинарное отношение  удовлетворяет (3.4.1). Положим, , где  определяется согласно (3.4.2). Тогда  является стратегией, условно оптимальной по критерию , поскольку имеет место (3.4.3), (3.4.4).

Предположим, что

.                              (3.4.10)

Внешняя устойчивость  в модели выбора  исключает существование такой комбинации слотов  и делает невозможным (3.4.10).

Далее, в силу внутренней устойчивости  в

, .                    (3.4.11)

В общем случае . Пусть , . Тогда

, . (3.4.12)

Из-за невозможности выполнения (3.4.10) и справедливости (3.4.11), (3.4.12) следует, что

.                                          (3.4.13)

Таким образом, применение схем (3.3.1), (3.3.2) и (3.3.3), (3.3.4) позволяет сформировать частные стратегии , условно оптимальные по каждому из критериев эффективности , а -оптимальная стратегия согласно (3.4.13) отыскивается на объединении частных стратегий.

В частности, если  является отношением Парето, то речь идет о Парето-оптимальной стратегии. При этом отношение Парето представляет собой асимметричную часть отношения , поскольку справедливо (3.4.1) и при этом .

 

3.4.3. Формирование -оптимальной стратегии планирования при заданных ограничениях

Положим, необходимо сформировать -оптимальную стратегию выполнения пакета заданий, характеристики которых приведены в табл. 3.1. В соответствии с (3.4.13)  строится на объединении стратегий, сформированных с применением частных критериев (подраздел 3.4.2). Пусть  в (3.4.1) формируется критериями (3.2.1), (3.2.2).

В табл. 3.4 приведены стратегии, условно оптимальные по критериям стоимости  и времени  выполнения пакета заданий. Они включают 13 комбинаций слотов (планов), которые сформированы в ходе решения модельных задач, рассмотренных в подразделах 3.3.3 –3.3.6 методом обратной прогонки по (3.3.1), (3.3.2). Варианты 14 - 25 получены методом прямой прогонки в соответствии с (3.3.3), (3.3.4). Планы 1 – 3; 7 – 9; 14 – 16; 20 – 22 являются условно оптимальными по , а планы 4 – 6; 10 – 13; 17 – 19; 23 – 25 – по .

Некоторые из планов, полученных при формировании стратегий с применением различных критериев и схем прогонки, совпадают. В табл. 3.4 это, например, планы 4, 7; 5, 8; 6, 9; 1, 10; 2, 12; 3, 13; 11, 15; 14, 17 и т.д. Оставим лишь первый план из пары совпадающих и сведем их в табл. 3.5.

 

Таблица 3.4

План	Комбинация	Критерий
	слотов
1	(1,2,3)	15	10
2	(2,2,2)	20	10
3	(3,1,2)	20	10
4	(1,2,4)	13	9
5	(2,2,4)	16	7
6	(3,2,4)	15	5
7	(1,2,4)	13	9
8	(2,2,4)	16	7
9	(3,2,4)	15	5
10	(1,2,3)	15	10
11	(2,1,3)	19	10
12	(2,2,2)	20	10
13	(3,1,2)	20	10
14	(3,2,1)	16	9
15	(2,1,3)	19	10
16	(2,1,4)	17	9
17	(3,2,1)	16	9
18	(3,2,2)	19	8
19	(3,2,3)	17	6
20	(3,2,1)	16	9
21	(3,2,2)	19	8
22	(1,2,3)	15	10
23	(3,2,1)	16	9
24	(2,1,4)	17	9
25	(1,2,4)	13	9

 

В ней представлены относительные (нормированные) в соответствии с (3.4.6) значения критериев ,  для планов, обозначенных как .

В пространстве критериев  и , имеющих одинаковую важность, альтернативы  и  доминируют над всеми остальными и образуют подмножество Парето (рис. 3.2).

 

Таблица 3.5

План	Комбинация слотов	Нормированный критерий		Функция полезности
	(1,2,3)	0,29	1	0,65
	(2,2,2)	1	1	1
	(3,1,2)	1	1	1
	(1,2,4)	0	0,80	0,40
	(2,2,4)	0,43	0,40	0,42
	(3,2,4)	0,29	0	0,15*
	(2,1,3)	0,86	1	0,93
	(3,2,1)	0,43	0,80	0,62
	(2,1,4)	0,57	0,80	0,69
	(3,2,2)	0,86	0,60	0,73
	(3,2,3)	0,57	0,20	0,39

 

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

Положим, веса нормированных в соответствии с (3.4.6) критериев ,  равны. Тогда наилучшим компромиссным решением является план  с минимальным значением 0,15 функции полезности . Именно этот план и должен быть оформлен ресурсными запросами к локальным вычислительным узлам в виде резервирования соответствующих слотов.

 

Рис. 3.2. Пример стратегии планирования в пространстве

двух критериев

Выводы

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

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

4. МНОГОАГЕНТНОЕ ВЗАИМОДЕЙСТВИЕ и элементы теории игр

4.1. Введение и основные понятия теории игр

Введение

 

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

Для того чтобы приблизиться к пониманию и решению этих проблем мы предлагаем использовать теоретико-игровой подход и далее представим некоторые элементы теории игр, наиболее существенные для анализа и решения поставленных задач. Так, в разделе 4.2 рассматривается проблема выбора стратегий поведения рациональными соперниками, раздел 4.3 содержит и примера механизма, обладающего необходимыми и предсказуемыми экономическими свойствами, а в разделе 4.4 на примере сетевых моделей продемонстрирован итеративный алгоритм распределения сетевых ресурсов.

 

4.1.2. Основные определения теории игр

Теория игр имеет уже довольно богатую историю. Первый научный труд Теория игр и экономическое поведение (Theory of games and Economic Behavior), посвященный этой дисциплине, был издан в 1944 году Джоном фон Нейманом и Оскаром Моргенштерном. Однако, как и во многих других областях науки, отдельными проблемами, ныне относящимися к теории игр, занимались задолго до издания данной книги. Так, многие задачи теории игр были поставлены и решены такими известными учеными, как А.Курно и Ж. Бертран (работы 19го века). Некоторые из этих работ имеют ярко выраженное отношение к экономике, другие направлены на изучение взаимодействия игроков в различных ситуациях, например, в теории шахматной игры. Методы и модели теории игр нашли применение не только в экономике, но и в социологии, биологии, политологии, технике, кибернетике и т.д.

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

Можно выделить и другие определения.

Теория игр - это математическая теория принятия оптимальных решений в условиях конфликтов (Н.Н. Воробьев).

Теория игр - это теория рационального поведения людей с несовпадающими интересами (Роберт Ауманн).

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

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

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

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