Содержание к диссертации
Введение
1 Байесовская модель задачи наилучшего выбора с разладкой 18
1.1 Постановка задачи 18
1.2 Байесовская модель наилучшего выбора с дисконтированием выигрыша 18
1.3 Байесовская модель наилучшего выбора с платой за наблюдения 30
1.4 Приложения 33
1.5 Результаты 36
2 Максимизация ожидаемого выигрыша в задачах наилучшего выбора с разладкой 37
2.1 Многопороговая задача наилучшего выбора с полной информа цией с разладкой 37
2.1.1 Случай Ъ < 1 38
2.1.2 Случай Ъ > 1 41
2.2 Игровая задача наилучшего выбора с разладкой 44
2.2.1 Неконкурентная постановка 44
2.2.2 Конкурентная постановка 57
2.3 Результаты 65
3 Максимизация вероятности выигрыша в задачах наилучшего выбора с разладкой 67
3.1 Задача наилучшего выбора с полной информацией с разладкой 67
3.1.1 Случай конечного числа наблюдений 68
3.1.2 Случай бесконечного числа наблюдений 78
3.1.3 Приложения 82
3.2 Игровая задача оптимальной остановки 84
3.2.1 Равномерное распределение на отрезке [0,1] 85
3.2.2 Равномерное распределение на отрезке [0,6], b > 1 87
3.2.3 Комбинированный вариант 89
3.2.4 Вариант задачи с разладкой 91
3.3 Заключение 92
Заключение 94
Литература 96
- Байесовская модель наилучшего выбора с платой за наблюдения
- Игровая задача наилучшего выбора с разладкой
- Случай бесконечного числа наблюдений
- Комбинированный вариант
Введение к работе
Актуальность темы. При построении моделей в области биологии, менеджмента, социологии и других наук часто возникают задачи наилучшего выбора. Эти задачи отражают важные особенности реальных процессов принятия решений в условиях неопределенности. Поэтому актуальным является как рассмотрение новых постановок задач, так и разработка прикладных моделей на их основе. На практике также нередки ситуации, когда в процессе наблюдения вероятностный закон распределения характеристик случайного процесса изменяется, что влечет дополнительные трудности при принятии решений.
Задача наилучшего выбора. Важным направлением в теории вероятностей являются задачи оптимального управления случайными процессами. Наряду с традиционными вероятностно-статистическими задачами в середине XX века началось систематическое исследование задач, которые теперь относят к вероятностной теории оптимального управлегоія. Одним из разделов этой теории является теория оптимальных правил остановки в задачах наилучшего выбора.
Проблемы наилучшего выбора впервые были представлены в 40-х годах в работах известного американского статистика А. Вальда в связи с задачами последовательного различения гипотез [3]. Основная особенность этих
задач состоит в том, что наблюдатель последовательно обозревает независимые одинаково распределенные случайные величины с неизвестным законом распределения, и целью является определение типа распределения этих наблюдений. В отличие от классических методов математической статистики, в которых число производимых наблюдений фиксируется заранее, методы последовательного анализа характеризуются тем, что момент прекращения наблюден и и (момент остановки) является случайным и определяется наблюдателем в зависимости от значений наблюдаемых случайных величин. Преимущество последовательных методов было продемонстрировано А. Вальдом на задаче различения двух простых гипотез по результатам независимых наблюдений. При этом было установлено, что подобные методы требуют в среднем меньшего числа наблюдений по сравнению с любым другим способом различения с фиксированным объемом выборки при тех же вероятностях ошибочных решений. Более того, А. Вальд указал и тот последовательный метод (названный крптерием последовательных отношений вероятностей), который является оптимальным в классе всех последовательных методов [28].
Однако больший интерес использование последовательных методов представляет при изучении класса задач наилучшего выбора. Начиная с момента опубликования первой задачи этого класса ("задачи о секретаре"), было рассмотрено большое количество различных постановок. Однако можно выделить общие свойства, присущие задачам наилучшего выбора [1, 45):
выбор осуществляется в несколько этапов, то есть растянут во времени;
на процесс выбора наложены стратегические и информационные огра-
ничения, связанные с полной или частичной недоступностью для выбора пропущенных вариантов и статистической неопределенностью качества будущих объектов;
эффект выбора (выигрыш) тем выше, чем лучше выбранные варианты.
Классической постановкой задачи наилучшего выбора является следующая "задача о секретаре" (также называемая "задачей выбора невесты") [1, 45, 50]:
в компании имеется одно вакантное место секретаря, на которое претендует п соискателей, проранжированных по качеству - лучший претендент имеет (абсолютный) ранг 1, худший - ранг п. С претендентами последовательно в случайном порядке проводятся собеседования (равновероятны все последовательности, в которой будут приглашаться на собеседование претенденты). Решение о принятии претендента или отказе в занятии вакансии основывается на относительном ранге - оценке качества текущего претендента относительно качеств предыдущих претендентов. Решение должно быть объявлено соискателю сразу же по окончании собеседования с ним, причем нельзя принять соискателя, которому ранее было отказано в занятии вакансии. Требуется с наибольшей вероятностью принять лучшего из всех претендентов (если принятый претендент лучший из всех, то выигрыш равен 1, в противном случае выигрыш равен 0).
Описанная задача была решена в 1961 г. независимо друг от друга Е. Б. Дынкиным (основываясь на теории марковских процессов [7]) и Д. Линдли (с помощью метода динамического программирования [61]). Оба решения приводят к неожиданному и красивому результату. Оказывается, необходимо пропустить (запоминая относительные ранги) примерно треть всех претендентов (п/е), а затем из оставшихся принять соискателя, который окажется лучше всех просмотренных ранее. При этом вероятность удачного выбора при п —* оо равна 1/е.
В последующие годы было изучено большое число новых постановок задачи наилучшего выбора (см. например, работы, содержащие исторические обзоры [35, 45, 47]). При этом было выделено два подкласса задач относительно информированности наблюдателя: задачи с полной и с отсутствием информации. Задачей с отсутствием информации называют вариант задачи наилучшего выбора, в котором распределение случайных величин неизвестно, а качество наблюдений может быть оценено лишь сравнением с предыдущими наблюдениями. В частности, к задачам с отсутствием информации относится и "задача о секретаре" (а также задачи, рассмотренные, например, в работах [21, 29, 38, 49, 87, 88}).
В задачах с полной информацией лицу, принимающему решение, известен закон распределения наблюдаемых случайных величин. Классическая постановка задачи с полной информацией ("задача о продаже недвижимости") выглядит следующим образом:
наблюдателю последовательно одна за другой поступают на рассмотрение п независимых одинаково распределенных случайных величин с известным непрерывным законом распределения. При получении каждого из наблюдений необходимо решить: принять или отвергнуть случайную величину. К отвергнутому наблюдению нельзя вернуться позднее. Цель наблюдателя - максимизировать вероятность принятия максимального значения из последовательности случайных величин.
Эвристическое решение этой задачи было впервые представлено в работе [50], а в статье [34] дано строгое доказательство полученного результата. Оптимальным правилом остановки является многопороговая стратегия - на каждом шаге і (1 < г < п) наблюдатель устанавливает порог ( и принимает первое наблюдение Xf. Хі > qi (уравнение для вычисления значений
оптимальных порогов можно найти, например, в [50]). Вероятность успешного выбора при большом числе наблюдений равна примерно 0.58. Различные постановки задач наилучшего выбора с полной информацией были рассмотрены авторами работ [36, 51, 52, 58, 68, 73, 74, 75] и другими.
Основное отличие задач "о секретаре" и '"о продаже недвижимости" заключается в доступной информации о наблюдениях, что приводит к изменению как оптимального правила выбора (в задаче с полной информацией уже не нужно пропускать наблюдения для "набора статистики", вместо этого используется многопороговая стратегия), так и вероятности удачного выбора.
Помимо четко разграниченных подклассов задач с полной и с отсутствием информации, рассматривают также задачи с различными ограничениями на доступную информацию о наблюдениях - задачи с частичной информацией, в которых, например, известен закон распределения, но неизвестны его параметры, либо неизвестны точные значения наблюдаемых случайных величин и т.д. (см., например, [70, 71, 72]).
Для каждого из подклассов было рассмотрено большое количество различных постановок задач наилучшего выбора. Интерес к этим задачам обусловлен следующими причинами. Во-первых, задачи наилучшего выбора отражают существенные особенности реальных процессов выбора в условиях неопределенности; во-вторых, они всегда имеют содержательную постановку и легко интерпретируемые решения в экологии, информационных технологиях, Экономикс и других науках (см. [13, 15, 77]).
Задача обнаружения разладки. В теории обнаружения и стати-
стическом контроле часто приходится сталкиваться с задачами, в которых вероятностные характеристики наблюдаемых величин могут измениться в случайный момент времени (момент появления "разладки"). При этом возникает проблема скорейшего обнаружения момента изменения вероятностных характеристик последовательности случайных величин. Эта проблема описана в монографии А. Н. Ширяева (так называемая задача "о разладке" [28]), в которой, в частности, приводятся решения задачи о разладке винеровско-го процесса и задачи в байесовской постановке. Задача "о разладке", послужившая отправной точкой представленного диссертационного исследования, состоит в следующем:
пусть 0 - случайная величина, принимающая значения 0,1,..., а наблюдения Xi,X2,... таковы, что при условии в = п величины X\,X2,...,Xn-i независимы и одинаково распределены и имеют функцию распределения Fo(x), a XnjXn+i,... — также независимы и одинаково распределены, но имеют функцию распределения F\(x) ф Fq(x). То есть в момент в происходит изменение вероятностных характеристик у наблюдаемого процесса. Возникает задача, как, последовательно наблюдая величины Х\,Х2, ... решить вопрос о том, в какой момент следует сделать вывод о произошедшей "разладке" — изменении вероятностных характеристик, но так, чтобы с одной стороны избежать ошибки классификации (объявления о "разладке" в тот момент, когда она еще в действительности не произошла), а с другой стороны — минимизировать время между возникновением "разладки" и ее фактическим обнаружением.
Задача о "разладке" была решена А.Н. Ширяевым в 1971 году. Различным вариантам этой задачи было посвящено также большое количество работ других авторов (см., например, [24, 30, 54]).
Модели, связанные с обнаружением разладки, применяются, например, при статистическом анализе историчесЕ<их текстов и установлении автор-
ства [2], контроле качества технологических операций [26] и т.д.
Задача наилучшего выбора с разладкой. В данной диссертационной работе проводится исследование проблем, принадлежащих классу задач наилучшего выбора с разладкой. Этот класс составляют задачи, в которых необходимо осуществить наилучший выбор в условиях ожидаемого изменения характеристик базового случайного процесса.
В общем виде задачи наилучшего выбора с разладкой описываются следующим образом (в дальнейшем на эту базовую постановку мы будем ссылаться как на модель (А)):
рассмотрим производящую систему, генерирующую последовательность из п независимых случайных величин Xi,X2, ...,Xq-i,Xo, Xq+i, ..., Хп. В случайный момент 9 происходит разладка и закон распределения случайных величин изменяется. Так, величины Хь Х2, ...,Хв-г описываются абсолютно непрерывной функцией распределения Fi(x), а величины Xo,Xg+i,...,Xn - абсолютно непрерывной функцией распределения F2{x). Будем считать, что до разладки система находится в состоянии Si, а после — в состоянии SV
Момент разладки в имеет геометрическое распределение с параметром а (0 < а < 1). То есть изначально система находится в состоянии Si, а перед генерацией каждой новой случайной величины состояние сие темы изменяется согласно следующей матрице переходов:
Наблюдателю известны функции распределения случайных величин в состояниях Si и *%, а также вероятность разладки 1-а, но истинное состояние системы остается неизвестным. После получения каждого из значений случайных величин наблюдателю требуется решить: принять значение случайной величины (и закончить процесс наблюдений) или отклонить. При этом нельзя ни отвергнуть все наблюдения, ни вернуться к наблюдению, которое было отвергнуто ранее. Задача наблюдателя заключается в
том, чтобы принять максимальное значение из последовательности случайных величин.
В случае нескольких наблюдателей задачу необходимо исследовать теоретико-игровыми методами. Такую теоретико-игровую модель наилучшего выбора будет называть моделью (В).
Особенностью (и дополнительной сложностью) задач наилучшего выбора с разладкой является то, что на неопределенность, связанную со значениями будущих наблюдений, накладывается неопределенность, связанная с текущим состоянием системы (произошла разладка или нет). На основе моделей (А) и (В) в представленном диссертационном исследовании рассмотрен ряд постановок задач, отличающихся целями наблюдателей (максимизация либо вероятности выбора максимального значения, либо ожидаемого значения принятой случайной величины), наличием конкурентов при выборе (игровые постановки), возможностями варьирования порогов в процессе наблюдения (значения порогов могут быть зафиксированы до начала наблюдений или наоборот, наблюдатель может иметь возможность изменять значения порогов, учитывая оценку вероятности нахождения системы в определенном состоянии) и т.д.
В диссертационном исследовании рассматриваются два класса стратегий наблюдателя: однопороговые и многопороговые стратегии. Многопороговая стратегия — это такая стратегия, при которой наблюдатель на каждом гааге і (і — 1,...,п) устанавливает порог qi и принимает случайную величину Xj в случае, если xt > qi, отвергая ее в противном случае. Однопорого-вая стратегия — это такая многопороговая стратегия, при которой qi = q,
; = і,...,??.
Впервые вариант задачи наилучшего выбора с разладкой был рассмотрен в работе [78], где в условиях людели (А) необходимо максимизировать ожидаемое принятое значение из последовательности случайных величин. При этом наблюдатель оценивает вероятность нахождения системы в одном из состоянии, на основе чего модифицирует значения порогов.
Представленная диссертационная работа посвящена исследованию задач наилучшего выбора с разладкой, комбинирующих в себе основные особенности и классических проблем наилучшего выбора, и задач обнаружения разладки. Актуальность диссертационной работы подтверждает большое внимание, которое уделяется этим задачам при проведении как теоретических изысканий, так и внедрении математических моделей в технологические процессы.
Цель диссертационной работы заключается в построении решений задач наилучшего выбора с разладкой методами теории оптимальной остановки и некооперативной теории игр.
В работе исследуются следующие основные задачи:
Байесовская модель наилучшего выбора с платой за наблюдения
Используя те же рассуждения, что и в случае дисконтирования выигрыша, можно построить байесовскую стратегию для случая платы за наблюдения. Обозначим с - значение, которое наблюдатель платит за каждое новое полученное наблюдение. Цель наблюдателя - максимизировать ожидаемый выигрыш с учетом платы за наблюдения. Выигрыш наблюдателя находим следующим образом: Обозначим выражение в квадратных скобках через Vi(7r, q). Тогда за г шагов до окончания наблюдений оптимальный порог д?: будет определяться решением оптимизационной задачи = a,Tgmax.Vi(ir,q). я Повторяя рассуждения, используемые при доказательстве теоремы 1, можно показать, что в классе стационарных стратегий выражение для V (7r, q) имеет аналогичный вид: где Gi{q) и Ti(q) удовлетворяют следующим рекуррентным соотношениям: При этом при к — со компоненты Gk{q) и ТЦд) функции выигрыша сходятся соответственно к G(q) и T(q) вида Как и в случае дисконтирования выигрыша, рассмотрим пример нормальных функций распределения случайных величин с дисперсией а2 = 1, математическими ожиданиями /i\ = 10 и /i2 = 9 функций Fi{x) и і ( ) соответственно. Стратегии с постоянными порогами определяются формулой В таблице 1.6 представлены основные характеристики стратегий принятия решения. Так же, как и в модели с дисконтированием выигрыша, использование -В-стратегии дает больший выигрыш (10.178), чем применение стратегий с постоянным порогом (выигрыш 9.027 и 10.17 для стратегий Лі и А2 соответственно) . Далее рассмотрим пример экспоненциальных функций распределения F\{x) и F ix) с параметрами Лі = 0.5 и \ч = 1 соответственно. Две пороговые стратегии А\ и Ач определяются формулой В таблице 1.7 представлены значения порогов принятия наблюдений в зависимости от величины платы за наблюдения, в таблице 1.8 - дополнительные характеристики стратегии выбора.
Задача планирования и распределения вычислительных ресурсов является одной из наиболее актуальных для развития информационных систем. С развитием высокопроизводительных технологий — кластерных и GRID-вычислений — особую важность приобретают проблемы управления задача,-ми и ресурсами. Проблеме управления заданиями посвящены многочисленные работы как в России, так и за рубежом (см., например, [11, 60, 53]). Важную роль играет также управление заданиями с точки зрения клиента вычислительной системы. В работе рассматривается задача определения оптимального объема запрашиваемых для обработки вычислительной заявки ресурсов в условиях ожидаемого изменения загруженности сервера. Рассмотрим некоторую информационную систему, предоставляющую клиентским компьютерам вычислительные ресурсы. Объем свободных вычислительных ресурсов в каждый момент времени неизвестен. Однако известно, что в случайный момент времени сервер перейдет в более загруженное состояние, и объем ресурсов, предоставляемый для заявок, уменьшится (произойдет "разладка"). Известно, что изначально вычислительная система слабо нагружена. Механизм обслуживания заявки следующий. На каждом шаге клиент указывает минимальный объем ресурсов, необходимый заявке. Если система имеет больший объем свободных ресурсов, чем указано в заяв ке, то заявка принимается на обслуживание и ей выделяются все свободные ресурсы.
В противном случае заявка отвергается, и клиент получает возможность подать свою заявку (с новой величиной требуемого объема ресурсов) на следующем шаге. Задача клиента — получить как можно больший объем ресурсов для обслуживания своей заявки, учитывая при этом, что предпочтительно более раннее обслуживание заявки. Обозначим Si состояние слабой загрузки вычислительной системы. Соответственно, »% — это состояние высокой загрузки системы. В каждый момент времени 1,.., О,.., п система предоставляет вычислительные ресурсы клиентским компьютерам. Объем свободных ресурсов характеризуется случайными величинами Xi,..,Xg-i с известным законом распределения Fi(x). В случайный момент времени в происходит "разладка", и система переходит в состояние 2 — распределение случайных величии Хд,..,Хп меняется на F2(x). Большая загруженность системы означает, что распределение Fi(x) стохастически доминирует распределение (.т). Будем считать, что случайная величина в имеет геометрическое распределение, т.е. в каждый момент времени "разладка" может произойти с вероятностью 1-а. На каждом шаге г клиент указывает минимальный требуемый объем ресурсов q{. Заявка принимается сервером, если qi xL (клиент получает ресурсы объемом ХІ), и отвергается в противном случае. На каждом шаге выигрыш дисконтируется коэффициентом Л (что задает предпочтение более раннего обслуживания заявки). Если заявка не была принята за п шагов, то клиент получает выигрыш, равный 0.
Игровая задача наилучшего выбора с разладкой
Рассмотрим следующую задачу: пусть в условиях модели (В) каждый из двух наблюдателей (игрок I и игрок II) стремится максимизировать ожидаемое значение принятой случайной величины, получаемое им в качестве выигрыша. Известно, что в состоянии S\ система генерирует случайные величины, равномерно распределенные на отрезке [0,1], в состоянии , — равномерно распределенные на отрезке [0,6]. На каждом шаге г (г — 1, ..,п) случайная величина Х{ передается одному из игроков согласно заданным приоритетам: с вероятностью р наблюдение получает игрок I, с вероятностью 1 — р — игрок II.
Таким образом, каждый из игроков получает лишь часть случайной последовательности Xi,X2...,Xn. Если один из игроков на некотором шаге к (1 к п) принял наблюдение Х , то другому игроку каждое новое наблюдение из оставшейся случайной последовательности X +i, ---,- все также предоставляется с вероятностью, соответствующей его приоритету (это условие задачи и подразумевается под "неконкурентностыо"). Если игрок за п шагов не принял наблюдения, то он получает выигрыш, равный нулю. Решение ищется в классе однопороговых стратегий (пороги q\ и qo для игроков I и II соответственно), значения порогов устанавливаются перед началом наблюдений и не могут быть изменены в дальнейшем. Функции выигрыша Пусть игрок II имеет больший приоритет выбора наблюдений (то есть р \)\ если это не так, то перенумеруем игроков таким образом, чтобы это условие выполнялось. Очевидно, что в таком случае ожидаемый выигрыш (а значит и значение оптимального порога игрока I) также будет меньше значения оптимального порога игрока П. Воспользуемся методом динамического программирования, чтобы получить рекуррентный вид функций выигрыша игроков. За к шагов до окончания наблюдений при условии, что система находится в состоянии S\ и уста-новлены пороги q\ и q2, выигрыш Hkx{qi, () каждого из игроков определяется как максимум между значением наблюдения Xf,. и ожидаемым выигрышем Hk{qi-,Q2)i который будет получен при продолжении: rSi H iqi o) = max{xk,Hk-i(qi,q2)) = тах:{хк, aH _1(qliq2)) + (1- а) Ьф_ ъ q2)), l k n. При этом Н01 = Н02 = 0 — если игрок не остановился на последнем шаге, то он получает нулевой выигрыш.
Оптимальные значения порогов q\ и q\ будут определяться решением следующей оптимизационной задачи если система находится в состоянии Si или Функции Hkx{qi,l) и Hk2(qi: b) определяют ожидаемый выигрыш игрока I за А; шагов до окончания наблюдений, если другой игрок остановился на одном из предыдущих наблюдений. В случае, если система находится в состоянии Si: Если игрок за п шагов не принял наблюдения, его выигрыш равен нулю: Подставляя в формулу (2.3) значения функций Hk (qi,q2), Hk2{qi,b) и Hkl(qi, 1) получаем итоговую нерекуррентную формулу для функции выигрыша игрока I: Аналогично вычисляется ожидаемый выигрыш игрока II за к шагов до окончания наблюдений при установленных порогах qi и q2 для случаев, когда разладка еще не произошла: n когда система уже перешла в состояние S2 Ожидаемый выигрыш игрока II в случае, когда другой наблюдатель за предыдущие п — к шагов выбрал налюдение, а система находится в состоянии TS2 Формулы выигрыша игроков I и II, хотя и не содержат рекуррентных зависимостей, имеют сложный вид и с увеличением количества шагов сложность их вычисления растет полиномиально. Кроме того, нахождение оптимальных порогов qi и q2 требует решения системы из уравнений (2.4) и (2.6). В таблицах 2.3 и 2.4 по результатам численного моделирования представлены значения оптимальных порогов и ожидаемых выигрышей игроков I и II для случая 20 наблюдений и приоритета р = 0.333.
Случай бесконечного числа наблюдений
Рассмотрим предельные значения функций выигрыша (3.1) и (3.2) при увеличении числа наблюдений. Для функции выигрыша (3.1) при q Ь получим: Рій, a, b) = lim Ргіп, q, а, 6) = (1 - а) ( " gQ - 1 " Q)) . (3.3) п-+оо \ 1 — qa 1 — qa J Найдем значение q{ : q\ 6, при котором вероятность правильного выбора будет наибольшей: дР\ aln(l-ga)-o:ln(l—а)-д п. dq (1-qa)2 откуда q = І. Следовательно, q\ = max(&, —-— ). Замечание 3.1 При предельном переходе в формуле (3.3) отброшено сла гаемое а 2 1 можно показаны , что в этом случае погрешность /=о при вычислении вероятности удачного выбора при п = 100 не превышает 0.001 для а 0.94, а при п = 1000 — для а 0.994. Однако, ка,к следствие, нарушается "совместіімость" с задачей без разладки — теперь к ней нельзя перейти, положив а = 1. Аналогично для Рчіп, q, a, b): P2(q, a, b) = lim P2{n, q, a, b) = n- oo 1-а i;m V (g/b)J(l-(g/b)n-j) . /1 _ лЛ Л"(1-Ь«) _ Мі-оЛ 77—1 В работе [50] показано, что при п — оо значение max 2_, _ —i 0.517, причем д — 1. Следовательно, Рг( , а, 6) возрастает по , значит, q\ = arg max P2{q: a,b) = b и 9Є(0,6] P2(n, a, 6) = - „ , (1-М 0.517 + ln J 1 — a Лемма 3.1 Для любых значений параметров а и Ь: 0 а,Ь 1 выполняется следующее неравенство: Доказательство. Прежде всего отметим, что при q = b верно P2(b,a,b) Рі(Ь, а, 6), следовательно неравенство выполняется для всех тех а и 6, при 7 l-e(l-a) которых О -. Теперь покажем, что неравенство верно для q\ = ————. Заметим, что 1-е(1 а) Ь = ±= е. Тогда Что и требовалось доказать. Из Леммы 1.1 следует, что оптимальный порог принятия наблюдений в задаче наилучшего выбора с разладкой равен 6, а P(q , a, b) = P2{q , ct, b). Представленные выше выкладки обобщаются в следующей теореме. Теорема 3.1 5 задаче наилучшего выбора с разладкой с полной информацией при бесконечном числе наблюдений максимальная вероятность выбора наибольшего наблюдения, достигается, при пороге при этом вероятность удачного выбора (1-М Результаты моделирования В таблице 3.4 представлены значения вероятности удачного выбора P(q , a, Ъ) при различных значениях параметров а и Ь. Как видно из таблицы, вероятность удачного выбора может быть в зависимости от значений параметров — больше или меньше, чем в задаче без разладки. На рисунке 3.2 представлен график функции вероятности удачного выбора в зависимости от вероятности разладки. a вероятность выигрыша 0.7 - J 0.617 Из рисунка видно, что с ростом а вероятность удачного выбора повышается и достигает значения 0.617 в точке а = 0.554, однако при дальнейшем понижении вероятности разладки вероятность удачного выбора понижается, так как неопределенность текущего состояния системы оказывает сильное влияние. Далее представлена модель распределения вычислительных ресурсов GRID-системы для задач, объем вычислений для которых зависит от требуемой точности. В основу модели положена описанная выше задача наилучшего выбора с полной информацией с разладкой.
При моделировании поведения сложных объектов, природных и технологических процессов зачастую возникает необходимость в проведении ресурсоемких вычислений. Для этих целей зачастую используются вычислительные системы на основе различных GRID-технологий (см., например [44]). Как правило, объем свободных ресурсов GRID в каждый момент времени является случайным и определяется доступностью неоднородной вычислительной и коммуникационной инфраструктуры. Поэтому возникает проблема выбора моментов обслуживания периодически решаемых задач, объем вычислений для которых зависит от требуемой точности (например, прогноз погоды может быть сделан с погрешностью в 1 градус, но допускается погрешность до 3 градусов). Для таких задач фактическая точность вычислений может определяться исходя из объема доступных в конкретный момент времени ресурсов. Рассмотрим следующую задачу распределения вычислительных ресурсов. Высокопроизводительный сервер (кластер, сервер распределения ресур сов GRID) в дискретные моменты времени предоставляет вычислительные ресурсы по запросу клиентских приложений. Правило выделения ресурсов следующее: клиентское приложение указывает минимальный объем ресурсов, требуемый для выполнения заявки. Приложению выделяется только один "вычислительный квант" — заявка, поставленная на выполнение в некоторый момент к, должна освободить ресурсы в момент к +1. Если объем доступных ресурсов сервера превышает порог, указанный клиентом, то заявка принимается на обслуживание и получает все свободные ресурсы. В противном случае заявка отвергается. Клиентскому приложению требуется указывать такие пороги, чтобы заявка была поставлена на обслуживание в течение п шагов и получила при этом как можно больший объем ресурсов. Дополнительно предположим, что распределение случайной величины, описывающей объем доступных ресурсов вычислительной системы, в случайный момент времени может измениться (например, в результате добавления/удаления удаленного вычислительного узла). Пусть S\ — это исходное состояние вычислительной системы, а 5г -новое состояние (с новой функцией распределения случайных величии, описывающих объем свободных ресурсов). Будем считать, что величина свободных ресурсов сервера в каждый момент времени характеризуется случайной величиной с известным законом распределения Fi(x) и F2(x) для состояний Si и 6 соответственно, а переход из первого состояния во второе может произойти на каждом шаге с вероятностью 1-а. На каждом шаге к (1 к п) клиент указывает значение q - порог
Комбинированный вариант
Теперь рассмотрим вариант задачи, в котором случайная величина Л і имеет равномерное распределение на отрезке [0,1], а Хо — равномерное распределение на отрезке [0,6], где b 1. Тогда функции выигрыша игрока т, установившего порог д, при условии, что остальные игроки используют пороговую стратегию t q, имеют следующий вид: и H\q,t) = ± b-(qb+tq)m (t\ 1 (Ь іЦ)т-(ІГ _L (і) »-1- )2-1 mbm-1(b+t) " \b) Следовательно, значение оптимального порога определяется как решение следующего уравнения. -1) [qb + q"-q]m = l ?n(6+q) На рисунке 3.4 представлен график функции оптимального порога q(b) в зависимости от значения параметра b для варианта задачи с двумя игрока ми. Рассмотрим обобщение игры, описанной в модели В, на случай разладки. Пусть изначально распределение наблюдений является равномерным на отрезке [0,1]. В случайный момент времени (перед первым пли перед вторым наблюдением) может произойти разладка, и распределение случайных величин изменится на равномерное на отрезке [0.6], где 6 1. Момент разладки — это случайная величина, имеющая геометрическое распределение с параметром а. Разладка происходит для всех наблюдателей одновременно. Решение этой игры можно представить как комбинацию решений трех рассмотренных ранее игр: ,777 В таблице 3.6 представлены результаты численного моделирования значений оптимальных порогов при различном количестве игроков. В данной главе рассмотрена задача наилучшего выбора с разладкой, в которой наблюдатель стремится максимизировать вероятность удачного выбора значения из последовательности случайных величин, используя однопо-роговую стратегию.
В результате, получен аналитический вид формулы для вычисления значений оптимальных порогов принятия наблюдения для произвольных значений параметров задачи (вероятности разладки, числа наблюдении и параметра распределения случайных величин после возникновения разладки). На основе представленных результатов численного моделирования проводится сравнение полученных результатов с решением задачи наилучшего выбора без разладки и отмечены характерные особенности, связанные со значениями оптимальных порогов и соответствующих вероятностей выигрыша. Во второй части главы для случая большого числа наблюдений найдены предельные значения оптимального порога выбора наблюдений и соответствующей вероятности выигрыша, зависящие от значений параметров задачи (вероятности разладки и параметра распределения случайных величин после возникновения разладки). Рассмотрена игровая задача оптимальной остановки для т игроков. Для данной задачи рассмотрены три варианта с различными параметрами равномерного распределения. Представлено обобщение задачи на случай разладки. Для описанных постановок задачи приведены результаты численного моделирования и найдены оптимальные пороги. Результаты данной главы были представлены на международной конференции "Optimal Stopping and Stochastic Control" (22-26 августа 2005 г., Петрозаводск), Российско-финской летней школе "Dynamic Games and Multicriteria Optimization" (2-7 сентября 2006 г., Петрозаводск), V Московской международной конференции по исследованию операций (10-11 апреля 2007 г., Москва), международной конференции "Теория игр и менеджмент" (28- 29 июня 2007 г., Санкт-Петербург), II летней школе Российского журнала менеджмента (9-20 июля 2007 г., Санкт-Петербург) и международном семинаре "Graduate School Seminar: Citations as impacts of research — who reads our papers?" (5-7 декабря 2007 г., Финляндия-Швеция), а также опубликованы в статьях и тезисах [17, 64, 65]. Заключение В работе представлены результаты исследования задач наилучшего выбора с полной информацией с разладкой. Рассмотрена задача максимизации вероятности выбора наилучшего значения из последовательности случайных величин в условиях ожидаемой разладки.
Получен аналитический вид формулы, определяющей оптимальное значение порога в зависимости от значений параметров задачи. Представлены результаты численного моделирования, которые демонстрируют характерные особенности задачи, связанные с выбором наблюдения до или после разладки. Рассмотрен случай большого числа наблюдений. Исследована теоретико-игровая задача оптимальной остановки для т лиц. Рассмотрены три постановки задачи, отличающиеся параметром равномерного распределения наблюдаемых случайных величин. С помощью метода динамического программирования получены оптимальные пороги. Представлено обобщение модели на случай разладки. Проведено численное моделирование значений оптимальных порогов принятия наблюдений. Рассмотрена многопороговая задача наилучшего выбора с полной информацией с разладкой; целью наблюдателя является максимизация ожидаемого значения принятой случайной величины с помощью многопороговой стратегии. Исследованы два варианта изменения в результате разладки параметра равномерного распределения наблюдаемых случайных величин. Представлены результаты численного моделирования значений оптимальных порогов. Рассмотрены две игровые постановки задачи наилучшего выбора с разладкой, в которых целью наблюдателей является максимизация ожидаемого значения принятой случайной величины. Для каждой из постановок построены функции выигрыша и найдены оптимальные однопороговые стратегии; рассмотрен частный случай абсолютного приоритета одного из игроков и вариант большого числа наблюдений. Рассмотрена байесовская модель задачи наилучшего выбора с разладкой, в которой наблюдатель имеет неполную информацию о наблюдаемых случайных величинах. Исследованы модели с дисконтированием и платой за наблюдения. Предложена байесовская стратегия порогового вида, в которой на каждом шаге учитывается апостериорная оценка вероятности разладки системы. Представлены результаты численного моделирования, на основании которых можно сделать вывод, что указанная стратегия дает больший выигрыш, чем использование однопороговых стратегий, не учитывающих поступающую информацию. На основе байесовской модели задачи наилучшего выбора с разладкой описана модель распределения вычислительных ресурсов в высокопроизводительных системах.
