Содержание к диссертации
Введение
1 Математические модели задач последовательного выбора 26
1.1 Последовательный выбор в задачах экологии поведения 27
1.2 Выбор объектов в экономических задачах 32
1.3 Нахождение объектов выборочной совокупности . 36
1.4 Математическая модель многократного выбора . 38
2 Теория задач наилучшего выбора 41
2.1 Выбор лучшего объекта 41
2.2 Многократный выбор 43
2.3 Последовательный выбор нескольких объектов с заданными рангами 49
2.4 Задача Гусейн-Заде 57
2.5 Конечная память в задаче многократного наилучшего выбора 63
2.6 Задача наилучшего выбора в случае неравновероятпых перестановок 65
3 Численные методы 71
3.1 Индукция назад 71
3.2 Метод последовательной минимизации расстояния Кульбака-Лейблера 72
3.3 Выбор к объектов с заданными рангами 81
3.4 Выбор двух объектов из трех лучших по качеству . 85
3.5 Задача наилучшего выбора с конечной памятью . 88
Заключение 94
Список литературы 95
Приложение 105
- Выбор объектов в экономических задачах
- Нахождение объектов выборочной совокупности
- Последовательный выбор нескольких объектов с заданными рангами
- Метод последовательной минимизации расстояния Кульбака-Лейблера
Введение к работе
Актуальность темы
При изучении явлений окружающего мира или при принятии решений приходится сталкиваться с процессами, течение которых по времени предсказать заранее в точности невозможно. Эта неопределенность вызвана наличием случайных факторов, воздействующих на ход процесса. Подобные процессы могут быть описаны стохастическими моделями, основанными на теории случайных процессов. Стохастические модели находят применение в самых различных областях знания и сферах человеческой деятельности, включая экономику, финансы, биологию и экологию.
При построении математических моделей данных процессов существенной является роль среды, которая определяет структуру информации и от которой зависит тип принятия решения: немедленный выбор между альтернативами или последовательный выбор. Рассмотрим ряд задач, возникающих в экологии поведения и в экономике, связанных с проблемами выбора.
Так, например, животное, двигаясь в ареале обитания, последовательно выбирает наилучшее место питания или партнера для воспроизводства. Покупатель ищет продукт, наиболее соответствующий его запросам, последовательно рассматривая различные предложения, или работодатель проводит собеседование для отыскания наилучшего кандидата на вакантную должность.
Для всех этих задач общей является следующая особенность — выбор осуществляется в несколько этапов, то есть происходит во времени. На процесс выбора наложены стратегические и информационные ограничения, связанные с недоступностью для выбора пропущенных вариантов и статистической неопределенностью качества будущих вариантов. Последовательный выбор в условиях неполной информации приводит к классу задач наилучшего выбора. Именно описываемая таким образом модель отражает существенные особенности реальных процессов выбора.
Наши построения будут существенно опираться на задачу наилучшего выбора, которая относится к теории оптимальной остановки.
Сформулируем задачу однократного наилучшего выбора. Пусть имеется N объектов, упорядоченных по качеству. Занумеруем объекты в таком порядке, как мы знакомимся с ними. Все объекты поступают в случайном порядке, то есть все N\ перестановок равновероятны. В некоторый момент t известны сравнительные качества объектов а\, с&2,..., &г, но ничего неизвестно о качестве остальных N — t объектов. После ознакомления с очередным объектом at можно его либо принять (в этом случае выбор объекта сделан), либо отвергнуть и продолжить наблюдения (при этом вернуться к отвергнутому объекту невозможно). Необходимо найти оптимальную стратегию, обеспечивающую наибольшую вероятность выбора
лучшего объекта.
Оптимальная стратегия имеет вид: нужно пропустить k*N — 1 вариантов, а затем остановиться на первом же объекте, который окажется лучше всех предыдущих.
Подробные обзоры истории развития задачи наилучшего выбора и ее обобщений приводятся в работах Фергисона1, Самуельса2. Различные методологические подходы к решению классической задачи наилучшего выбора можно найти в книгах Роббинса, Сигмунда и Чао3, Березовского и Гнедина4, Ширяева5.
Дальнейшие исследования развивались в нескольких направлениях. Одно из них - выбор нескольких объектов. Николаев6 отказался от необходимости выбирать единственный объект и рассмотрел обобщение классической задачи — задачу многократного наилучшего выбора. При этом необходимо найти стратегию, максимизирующую вероятность выбора к,к > 2 лучших объектов. Продолженные Николаевым7 исследования задачи о многократной оптимальной остановке привели к решению более широкой задачи — задачи об оптимальной остановке случайной последовательности. Многократный выбор рассматривался в работах Ано8, Преатера9, Тамаки10, Вилсона11. Софронов и Полушина рассмотрели задачу наилучшего многократного выбора с заданным распределением для перестановок. Николаев, Софронов, Полушина рассмотрели другое обобщение задачи многократного наилучшего выбора — задачу многократного наилучшего выбора с заданными рангами. В данной постановке требуется выбрать несколько объектов с заранее заданными рангами г i, г2-, , Г&.
Другое обобщение задачи наилучшего выбора — выбор одного объекта из нескольких лучших, так как на практике может быть достаточно обладать вторым по качеству объектом, третьим по качеству и так далее. Гусейн-Заде12 решил задачу, в которой успехом считался выбор любого из / лучших
Ferguson T.S. Who solved the secretary problem? // Stat.Sci. 1989. V.4. N 3. P. 282-289.
2Samuels M. Who solved the secretary problem? comment: Who will solve the secretary problem? // Stat.Sci. 1989. V. 4. N 3. P. 289-291.
3Роббинс Г., Сигмунд Д., Чао И. Теория оптимальных правил остановки. М.: Наука, 1977.
4Березовский Б.А., Гнедин А.В. Задача наилучшего выбора. М.: Наука, 1984.
5Ширяев А.Н. Статистический последовательный анализ. М.: Наука, 1976.
8Николаев М.Л. Об одном обобщении задачи наилучшего выбора // Теор. вер. и ее прим. 1977. Т. 22. В. 1. С. 191-194.
7Николаев М.Л. Оптимальные правила многократной остановки // Обоз, прикл. и пром. матем. 1998. Т. 5. В. 2. С. 309-348.
8Апо К. Multiple selection problem and ola stopping rule // Sci. Math.Jap. 2001. V. 53. N 2. P. 335-346.
9Preater J. On multiple choice secretary problems // Math.of Oper.Research. 1994. V. 19. N 3. P. 597-602. 10Tamaki M. A generalized problem of the optimal selection and assignment // Oper.Reseach. 1986. V. 34. N 3. P. 486-493.
nWilson J. Optimal choice and assignmentof the best m of n randomly arriving items // Stoch.Proc.and Appl. 1991. V. 39. P. 325-343.
12Гусейн-Заде СМ. Задача выбора и оптимальное правило остановки последовательности независимых испытаний // Теор. вер. и ее прим. 1966. Т. 11. В. 3. С. 534-537.
объектов. В дальнейшем изучение этой постановки продолжали Кавай и Тамаки13, Порошински14, Сушвалко и Шайовски15.
В классической задаче наилучшего выбора предполагается, что объекты поступают один за другим в случайном порядке. Таким образом, все N\ возможных порядков появления объектов равновероятны. Этот случай принято называть случаем отсутствия информации. Если поступающие объекты обладают какой-то количественной характеристикой их качества (например, ценой), то рассматриваются поступающие случайные величины. Это задача об остановке случайной последовательности. В простейшем случае естественно считать, что поступающие объекты являются независимыми случайными величинами с равномерным распределением. В той ситуации, когда априорно или в результате некоторых предварительных исследований, стало известно, какому семейству распределений принадлежит распределение, поступающих объектов, но неизвестны параметры, задача называется задачей с частичной информацией. Когда наблюдателю точно известно распределение, в этом случае задача называется задачей с полной информацией. Бойдецки16 рассмотрел задачу оптимальной остановки последовательности случайных величин, имеющих пуассоновское распределение. К задачам с частичной информацией относятся работы Петручелли17. Случай полной информации рассматривается в статьях Неймана, Порошински и Шайовски18, Николаева и Софронова19. Софронов и Полушина рассматривали задачу наилучшего выбора с неравновероятными перестановками. Позднее авторы обобщили эту задачу на случай многократного выбора.
Можно рассмотреть еще одно обобщение классической задачи. Пусть наблюдатель получает возможность возвращаться к просмотренным ранее объектам, но каждый пропущенный объект с некоторой вероятностью может быть уже недоступен. Такие задачи с памятью рассматривались в статьях Роуза20, Сайто21.
13Kawai М., Tamaki М. Choosing either the best or the second best when the number of applicants is random II Сотр. and Math, with Appl. 2003. V. 46. P. 1065-107.
14Porosinski Z. On optimal choosing of one of the k best objects // Stat, and Prob. Letters. 2003. V. 65. P.419-432.
15Suchwalko A., Szajowski K. Non standard, no information secretary problems // Sci. Math. Jap. 2002. V. 56. P. 443-456.
18Bojdecki T. On optimal stopping of a sequence of independent random variables - probability maximizing approach // Stoch. An. Int. J.of Prob. and Stoch.Proc. 1979. V. 3. N 1. P. 61 - 71.
17Petruccelli J. On a best choice problem with partial information // The Ann.of Stat. 1980. V. 8. N 5. P. 1171-1174.
18Neumann P., Porosinski Z., Szajowski K. On two person full-information best choice problem with imperfect observation I) Game Theory and Appl. 1996. V. 2. P. 21-25.
19Николаев М.Л., Софронов Г.Ю. Многократные оптимальные правила остановки для суммы независимых случайных величин // Дискретная математика. 2007. Т. 19. В. 4. С. 42-51.
20Rose J. Optimal sequential based on relative ranks with renewable call options // J.of the Am.Stat.Ass. 1984. V. 79. N 386. P. 430-435.
21Saito T. Optimal stopping problem with controlled recall // Prob. Eng. and Inf. Sci. 1998. V. 12. N 11. P. 91-108.
Кроме того, существуют и другие различные обобщения задачи наилучшего выбора: случайное число наблюдаемых объектов (Пресман и Сонин22), несколько наблюдателей (Гликман23), плата за наблюдения (Лоренсен24), задача, в которой максимизируется время обладания относительно лучшим объектом (Тамаки, Пирс, Шайовски25), задача о минимизации ожидаемого ранга (Чао, Моригути, Роббинс и Самуэльс26) и суммарного ожидаемого ранга (Николаев).
В настоящей работе исследуются обобщения задачи многократного наилучшего выбора — важного класса задач теории оптимальных правил многократной остановки. Для некоторых из исследуемых обобщений оптимальные правила получены в явном виде. Проблема состоит в том, что в отдельных случаях структура остановочных множеств существенным образом зависит от конкретной задачи (например, определенного набора рангов гі,...,г&). В этой ситуации необходимо прибегнуть к прямым вычислениям. Непосредственные рекурсивные вычисления методом индукции назад приводят к значительным временным затратам. Для задач, в которых N велико, их применение крайне затруднительно. В то же время метод Монте-Карло не дает достаточной точности и устойчивости результатов. Для отыскания наборов, характеризующих структуру остановочных множеств, и цены игры в программном комплексе реализуется метод последовательной минимизации расстояния Кульбака-Лейблера. Используемый алгоритм позволяет оценить оптимальное правило и цену игры даже при незначительных объемах выборок.
Решение поставленных обобщенных задач многократного наилучшего выбора является значимым для теории оптимальных правил многократной остановки. Каждый результат в области принятия решений является вкладом в теорию и практику. Именно поэтому, проблематика диссертации является актуальной как с точки зрения развития теории, так и с точки зрения практических применений.
Цель работы
Целью настоящей диссертации является построение математической модели, основанной на оптимальных последовательных процедурах в случае многократного выбора, получение оптимальных правил для некоторых обобщений задачи многократного наилучшего выбора и оценивание оптимальных правил методами математического моделирования.
22Пресман Э.Л., Сонин И.М. Задача наилучшего выбора при случайном числе объектов // Теор. вер. и ее прим. 1972. Т. 17. В. 4. С. 695-706.
23Glickman Н. A best-choice problem with multiple selectors // J.Appl.Prob. 2000. V. 37. P. 718-735.
24Lorenzen T. Optimal stopping with sampling cost: the secretary problem // The Ann. of Prob. 1981. V. 9. N 1. P. 167-172.
25Tamaki M., Pearce C, Szajowski K. Multiple choice problems related to the duration of the secretary problem II RIMS Kokyuroku. 1998. V. 1068. P. 75-86.
28Chow Y.S., Moriguti S., Robbins H., Samuels S. Optimal selection based on relative rank // Israel J.Math. 1964. V. 2. P. 81-90.
Методика исследований
При решении перечисленных задач применялись результаты и методы математического моделирования, математического программирования, теории случайных процессов и теории вероятностей.
Для реализации программного комплекса основным алгоритмическим языком был выбран объектно-ориентированный язык C++.
Научная новизна
Основные результаты диссертации являются новыми и состоят в следующем:
1. Впервые предложена математическая модель, описывающая процедуру
многократного последовательного выбора в прикладных задачах.
Найдены оптимальные правила многократной остановки в задачах многократного наилучшего выбора с заданными рангами, Гусейн-Заде и в задаче с конечной памятью.
Получены расчетные формулы для нахождения цены игры методом последовательной минимизации расстояния Кульбака-Лейблера. Решение каждой из приведенных постановок связано с рассмотрением отдельной задачи оптимизации и требует специального подхода.
4. Разработан программный комплекс, позволяющий методами
математического моделирования оценивать оптимальные правила для
указанных задач.
Теоретическая и практическая значимость
Предлагаемые математические подходы позволяют изучать методами математического моделирования многие экономические и биологические процессы. Полученные в диссертации теоретические результаты являются дальнейшим развитием теории оптимальных правил многократной остановки. Разработанный программный комплекс дает возможность оценивать правила оптимальной остановки для рассматриваемого круга обобщений задачи многократного наилучшего выбора.
Достоверность результатов работы подтверждается
математическими доказательствами, результатами моделирования и обработки данных;
апробацией этих результатов на международных, всероссийских конференциях и научных семинарах.
Апробация работы
Основные результаты диссертации докладывались на международных, всероссийских и региональных научных конференциях и форумах:
Студенческой конференции МарГУ (г. Йошкар-Ола, 2005 г.);
Девятых Вавиловских чтениях (г. Йошкар-Ола, 2005 г.);
(3) Международной конференции "Оптимальная остановка
и стохастическое управление" (г. Петрозаводск, 2005 г.);
(4) Всероссийской школе-коллоквиуме по стохастическим методам
(г. Йошкар-Ола, 2006 г.);
(5) Шестой молодежной школе-конференции "Лобачевские чтения —
2007" (г. Казань, 2007 г.);
(6) Пятнадцатой международной конференции "Математика. Компьютер.
Образование" (г. Дубна, 2008 г.);
Седьмой молодежной школе-конференции "Лобачевские чтения — 2008" (г. Казань, 2008 г.);
кафедральном семинаре "Теория оптимальных правил многократной остановки" при кафедре математического анализа и теории функций (рук. — проф. Николаев М.Л., доц. Софронов Г.Ю.).
Ряд исследований, приводимых в диссертационной работе, выполнялись в рамках проекта, поддержанного грантом Министерства образования и науки Российской Федерации "Развитие научного потенциала высшей школы" (проект 34173). Автор награжден именной стипендией Президента Республики Марий Эл.
Публикации По теме диссертации опубликовано 13 печатных работ. Из них — 5 статей в российских реферируемых журналах, входящих в список ВАК, 2 — в тезисах докладов всероссийских симпозиумов и конференций.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы (94 наименования), приложения. Каждая глава разбита на параграфы. Работа проиллюстрирована 26 рисунками и изложена на 108 страницах.
Выбор объектов в экономических задачах
Люди также сталкиваются с проблемой принятия решения в условиях неполной информации. Неправильное решение в животном мире может привести к потере места питания, партнера для воспроизводства или к переходу в неблагоприятную среду. Психологи и экономисты изучают механизмы отбора, которые применяют люди в условиях последовательного выбора и их последствия.
Рассмотрим типичную экономическую задачу - выбор некоторого определенного продукта. Стандартный подход к решению этой задачи предполагает, что для всех возможных продуктов данного типа производится сбор информации, взвешивается значимості, полученной информации согласно некоторой функции полезности, комбинируя полученные веса, получается финальная ценность для каждого продукта данного типа, затем по этим данным выбирается наилучший продукт. Однако в этой ситуации не учитываются возможные ограничения по времени, издержкам, затратам усилий или знаний. К тому же, возможно, что полная информация может быть недоступна [38].
Подобная задача может решаться при выборе места для парковки или дома. Наблюдателю следует сделать выбор до того, как все возможные варианты рассмотрены. Это связано с тем, что вероятность вернуться к просмотренным объектам либо крайне мала, либо такая возможность вообще отсутствует.
Экспериментально исследуя поведение людей, экономисты [48, 94] и психологи [31, 32, 79, 82] показали, что в большинстве случаев люди склонны прекращать наблюдения слишком рано. В действительности это связано с тем, что человек не ищет достаточно долго, потому что сталкивается с трудностями в ходе поиска. Например, при поиске заправочной станции с наиболее дешевым бензином покупатель склонен чаще всего заправиться в наиболее удобном для пего месте, чем продолжать поиски.
Задачи последовательного поиска продукта с наименьшей ценой рассматривались в ряде экспериментальных работ (например, [54]). Полагалось, что время дискретно, и покупатель наблюдает цены, являющиеся случайными величинами, последовательно. Покупатель может приобрести продукт по текущей цене и остановить поиск, или продолжить поиск более низкой цены. При этом, если покупатель решает вернуться к пропущенным ранее вариантам, вероятность того, что отвергнутый объект остался доступным для выбора, довольно низка. Также следует отметить, что в случае, когда лицо, принимающее решение, знает о существовании возможности вернуться, то поиск продолжается слишком долго.
Отметим, что искомый продукт, помимо количественных характеристик (цены), может обладать качественными характеристиками (например, в случае квартиры — состояние, этаж, район и др.). В этом случае рассматриваемые объекты, оцениваемые по многочисленным разнообразным шкалам, могут быть прорапжировапы лишь в отношении "лучше" или "хуже". Так, были проведены эксперименты, в которых участникам исследования необходимо было выбрать квартиру. С помощью объявлений подбирались N объектов, удовлетворяющих заданным условиям отбора [94]. Из данных объектов следовало выбрать наилучший вариант. В ходе исследований были обнаружены три фактора, влияющие на процесс принятия решения: момент, в который появился относительно лучший объект, число пропущенных ранее относительно лучших и сколько времени прошло с момента появления последнего относительно лучшего объекта. Хотя с точки зрения оптимального правила значимым является только первое условие, лицо, принимающее решение, как правило учитывает и последние два фактора.
Подобная картина наблюдается, если рассматривать задачу о поиске претендента на вакансию. В опытах лицо, принимающее решение, получает выигрыш тг(а) за выбор претендента с абсолютным качеством а, где 7г(1) . .. 7г(п). Рассматривались случаи, когда 7г(1) = 1, 7г(?) = 0 для і 1 и 7г(1) 0,7г(2) 0,7г(3) 0, TT(J) = 0 для г 3. В экспериментах участвовали студенты, обучающиеся в университете Аризоны. В исследуемых группах было по тридцать участников. Участники получали некий выигрыш за выбор не только самого лучшего претендента, но и нескольких первых лучших по качеству. При таком изменении требований участники эксперимента все равно принимали решение об остановке слишком рано, однако, средний выигрыш увеличивался. Исследователи объясняют это тем, что порой требование "выбор самого лучшего по качеству" является слишком жестким. Гораздо понятнее и реалистичнее являются требования выбрать одного из нескольких самых лучших. Следует отметить, что условие 7г(1) — 1, 7г(г) = 0 для г 1 соответствует классическому случаю задачи наилучшего выбора.
Принятие решения в условиях неполной информации приводит к задаче об оптимальной остановке. Так в [8] рассматривается применение оптимальных стратегий в рекламных кампаниях.
Или же наблюдаемую случайную величину уп можно интерпретировать как относительное качество имущества (например, дома) в момент п. Тогда рассматривается задача продажи объекта с конечным горизонтом N, с одним предложением цены за текущий момент. Пусть есть возможность вернуться к предложениям рассмотренным не позднее, чем М шагов назад. Рассматриваемая задача сводится к задаче наилучшего выбора с конечной памятью [80, 92].
Нахождение объектов выборочной совокупности
Всякое исследование начинается со сбора фактов, наблюдения. При выборе объектов наблюдения следует предъявлять некоторые требования.
Объектом статистического наблюдения называем ту совокупность, в которой должны быть собраны необходимые сведения. Сплошное наблюдение — учет всех объектов в пределах данной совокупности. Сплошное наблюдение не всегда целесообразно, а иногда и невозможно. Поэтому следует проводить не сплошное (частичное) наблюдение —- рассматривать только некоторую часть объектов, по которой составляют представление о характерных особенностях исследуемого явления в целом. Не сплошное наблюдение имеет ряд преимуществ по сравнению со сплошным наблюдением: затрачивается значительно меньше затрат труда, средств и времени в связи с уменьшением числа обследуемых единиц.
Главное требование к несплошному наблюдению состоит в том, что оно должно быть представительным. Обследуемые единицы отбираются так, чтобы, опираясь на полученные по этим единицам данные, получить верное представление о явлении в целом. Поэтому одной из существенных особенностей не сплошного наблюдения является организация отбора единиц обследуемой совокупности.
Так, способ основного массива предполагает отбор единиц совокупности, преобладающих по изучаемому признаку. Данный способ не обеспечивает отбора единиц, которые представляли бы все части совокупности.
Монографическое наблюдение — детальное описание некоторого небольшого числа единиц совокупности. Монография, как один из способов изучения особенностей единиц совокупности, предусматривает отбор из состава всей совокупности качественно однородных единиц одного типа. Собираются подробные сведения по 1-3 единицам с индивидуальными значениями признака, близкими к типичным значениям признака в группе.
Выборочное наблюдение является таким видом статистического наблюдения, при котором обследованию подвергается некоторая часть единиц изучаемой совокупности, отобранная в определенном порядке, с целью последующей характеристики всей совокупности.
В случае последовательного наблюдения объектов необходимо решить, какие объекты должны попасть в выборку. Так, для случая монографического наблюдения естественное требование состоит в том, чтобы изучаемый объект являлся бы "средним" по исследуемым свойствам. В случае выборочного наблюдения в итоговую выборку необходимо включить, как лучшие объекты, так и худшие объекты. Именно рассмотрение некоторых крайних возможных состояний позволит точно изучить свойства исследуемой совокупности. Для способа основного массива следует отбирать группу лучших или худших объектов из совокупности, упорядоченной по некоторому признаку.
Поскольку выбор объектов проходит в условиях неполной информации, то с математической точки зрения это приводит к задаче наилучшего выбора с заданным рангом. В данной постановке необходимо выбрать не обязательно лучший объект. Цель состоит в отыскании объекта с заданным абсолютным рангом г [72, 85].
Все вышеприведенные модели рассматривали случай выбора одного объекта. Тем не менее, известно, что существуют виды животных 42, 63], среди которых самки в течение одного сезона последовательно отбирают несколько партнеров для спаривания. Это относится к некоторым видам ятцериц, рыб и птиц. Помимо этого, представляется вполне естественным, что животное может последовательно выбирать более одного места питания.
Женские особи гладких тритонов (Tritunis v. vulgaris; Amphibia; Salamandridae) "обучаются" последовательному выбору. Самцы этого вида развивают большие спинные гребни в период спаривания. В течение одного брачного периода женские особи могут спариваться с несколькими различными мужскими особями (до семи) [46]. Отбор основывается на феиотипических признаках. Мужские особи с высокими спинными гребнями являются наиболее ценными с точки зрения генетической ценности.
Эксперименты проводились в феврале-марте 1994. Группе женских (п = 28) особей тритонов в течение некоторого периода демонстрировались потенциальные партнеры для спаривания. В первом спаривании группе представляли самцов с высоким спинным гребнем (8.5 - 10 мм). Через 20 дней во время второго спаривания группе представили самцов с низкими спинными гребнями (4.0 - 6.5 мм). В третьем финальном спаривании женским особям представили самцов с очень высокими спинными гребнями (10.0 - 13.0 мм). В таблице 1.1 представлены численные данные проведенного эксперимента.
Последовательный выбор нескольких объектов с заданными рангами
Неформально данную теорему можно объяснить следующим образом. После того, как наблюдатель просмотрел первый объект, он может остановиться на первом шаге и получить выигрыш Х\. Необходимо выяснить, остановить ли выбор после первого наблюдения или продолжать его. Ответ на этот вопрос зависит от информации, полученной после второго наблюдения. Что в свою очередь приводит к вопросу, прекращать ли наблюдения на втором шаге, получив выиграш Х-2, или продолжать процесс, делая третье наблюдение. Повторяя рассуждения, приходим к следующему вопросу: если сделаны N — 1 наблюдение, то следует ли завершить процесс выбора или же следует сделать финальное наблюдение? Как правило, ответить на этот последний вопрос нетрудно. В случае когда происходит последнее наблюдение, то в силу ограничений наблюдатель в любом случае прекращает процесс выбора. Значит, если выбор не был сделан ранее, то в N — 1 момент лицо, принимающее решения, должно решить, остановиться сейчас или сделать еще одно наблюдение. Оптимальное решение в такой ситуации зависит от увиденных ранее значений. Рассуждая подобным образом далее, заметим, что при известных наблюдениях до N — 2 шага, наблюдатель может принять решение проводить ли ему наблюдение iV—1 значения, чтобы получить выиграш .XJV_I, или остановиться сейчас. Поскольку для каждого возможного значения XN-I наблюдатель знает оптимальную процедуру, то он может сравнить риск от принятия решения без продолжения наблюдения с риском, отвечающим проведению N — 1 наблюдения. Двигаясь назад до первого шага, для каждого возможного Х\ можно определить оптимальную линию проведения наблюдений на следующих шагах. Из такого сравнения па первом и последующих шагах может быть получена оптимальная процедура последовательного решения.
К классу задач теории оптимальной остановки относится класс задач наилучшего выбора. Классическая задача однократного наилучшего выбора может быть сформулирована следующим образом [44]. Пусть имеется N объектов, упорядоченных по качеству, то есть, можно указать, какой из них самый лучший, какой второй по качеству и так далее. Занумеруем объекты в том порядке, как мы знакомимся с ними. Все объекты поступают в случайном порядке. Таким образом, все ЛП перестановок равновероятны. В текущий момент t известны сравнительные качества объектов cii,ci2,.. . ,at, но ничего неизвестно о качестве остальных N — t объектов. После ознакомления с очередным объектом at можно его либо принять (в этом случае выбор объекта сделан), либо отвергнуть и продолжить наблюдения (тогда вернуться к отвергнутому объекту невозможно). Необходимо найти оптимальную стратегию, обеспечивающую наибольшую вероятность выбора лучигего объекта. Основным характерным свойством этой задачи является то, что единственной информацией, получаемой наблюдателем о каждом предмете, является его относительный ранг среди уже просмотренных объектов.
Оптимальная стратегия имееет вид: существует номер k N такой, что первые (к\- — 1) объектов следует пропустить, а затем остановиться на первом объекте, который лучше всех предыдущих.
Метод последовательной минимизации расстояния Кульбака-Лейблера
Поскольку отыскать набор ir = (71 , . . . , 7г), определяющий структуру стратегии оптимального выбора, и значение v описанными выше методами достаточно трудно, мы отыщем их, решая одну комбинаторную задачу оптимизации. Если N ДОСТаТОЧНО ВеЛИКО, МОЖНО ОЦеНИТЬ ПОРОГИ 71 ,...,71 , И V моделированием. Итак, рассматривается следующая задача максимизации Заметим, что расстояние Кульбака-Лейблера несимметрично. Из определения расстояния Кульбака-Лейблера видно, что J д(х) In g(x)dx из (3.2) не зависит от /г. Таким образом, минимизация расстояния Кульбака-Лейблера сводится к рассмотрению задачи максимизации J д(х) In h(x)dx. Первоначальной идеей при использовании данного метода является связать задачу оценки параметра с некоторой задачей оптимизации. Для этого определим последовательность индикаторных функций {I{s(x) -/}} иа X Аля различных у Є -Пусть {f{-,u)} — семейство функций распределения на X с действительным параметром и. Для некоторого и задача оптимизации (3.1) связана с задачей оценки параметра где Pw — вероятностная мера, 7 известный или неизвестный параметр. Обычно оценка I представляет собой сложную задачу [75]. Рассматриваемый метод позволяет решать ее достаточно эффективно. В ходе его работы производится постоянный пересчет и адаптивное изменение функций плотности, которое базируется на уменьшении расстояния Кульбака-Лейблера. Создается последовательность функций /(-, ), f(-,ui), f(-,u2),...,f{-,u ), сходящихся к оптимальному решению. Фактически метод последовательной минимизации расстояния Кульбака-Лейблера создает последовательность дуплетов {{jt,ut)}, которая быстро сходится к оптимальному (7 ,w ). Метод состоит из двух шагов: 1. Обновление 7І- Для фиксированного Ui-i. пусть 7 — это (1 — уо)-квантиль S(X) при Щ-i. Оценкой % Для It является где для случайной выборки Xi,... ,Х]\-2 с функцией плотности f(-;ut-\) S является г-ой порядковой статистикой представления S(X\),..., S(XJV2). 2.
Обновление uL. Для фиксированных jt и Щ-і, щ есть решение задачи минимизации расстояния Кульбака-Лейблера, Если математическое ожидание заменить на его состоятельную оценку, то из формулы (3.3) получим: для фиксированных 7t и щ \. получаем щ из следующей задачи Чтобы завершить описание алгоритма, следует определить значения для А 2 и р, начальные параметры и0 и критерий остановки. Вместо вектора v будем использовать его сглаженный вариант где а — параметр сглаживания, 0.7 а 1. При о; = 1 приходим к первоначальному правилу. Определим критерий остановки [76]. Будем рассматривать следующий процесс скользящего среднего: где iif фиксировано, Далее обозначим соответственно, где R фиксировано. Определим момент остановки следующим образом: где К и Я фиксированы, є — параметр, є 0.01. Рассмотрим следующую схему моделирования наборов х = (xi,...,xk) [25]. Пусть вектор параметров и = {ui}, где fy = (ЬЦ, ... ,bik), 1 ЪЦ bik N, a L — число всех возможных сочетаний без возвращений. Теперь дискретный случайный вектор х имеет функцию плотности распределения вероятностей Используя (3.34) [76], получаем выражение для щ = {щ }: где l\ такое, что Xn = 6/n X7? = (Хмі, , пк) является дискретным случайным вектором из f(x; ut-i). Тогда формула (3.4) преобразуется в (3.7). Рассмотрим численный пример, иллюстрирующий работу схемы (пример 1 параграф 2.3). Пусть N = 15 и к = 2. Используя метод Монте-Карло, отыщем оценки для цены игры v для всех возможных наборов (7Гі,7Г2). На рисунках 3 и 4 изображено среднее значение цены игры v после 5 повторений, объем выборки N\ = 5000. Приведем результаты моделирования для классической задачи многократного наилучшего выбора.
Параметры моделирования N2 = ЮО, Nx = 200, Nlnst = 5000, р = 0.1, а = 0.7, є = 0.01, К = 6 R = 3. Рисунок 5 был построен на основе 100 повторений метода для данных N и к. Этот рисунок иллюстрирует то, что рассматриваемый метод находит пороговые множества (тгі, ) такие, что позволяют получить максимальную цены игры. Остановимся подробнее на алгоритме отыскания пороговых значений при заданных параметрах моделирования. В таблице 3.3 представлены значения щ для различных итераций. В первоначальный момент полагаем, что все возможные пороговые множества равновероятны. Однако уже на 25 итерации видно, что оптимальным является один из трех наборов (5, 9), (5, 10) или (6, 9). Алгоритм будет выполняться до тех пор, пока не выполнится условие остановки (3.5): є — 0.01. На рисунках 0 11 приведено распределение вероятностей между пороговыми множествами для первой, десятой, двадцатой, тридцатой, сороковой и пятьдесят пятой итерации соответственно. Также с помощью метода последовательной минимизации расстояния Кульбака-Лейблера были получены пороги и цена игры для различных N. На основе 10 повторений получена таблица 3.4. Параметры моделирования: Л = 100, N± = 500, Niast = 10000, р = 0.1, а = 0.7, є = 0.01. К = 6,R = 3. На рисунках 12 и 13 представлены цена игры v и пороги Из сравнения методов, представленных в параграфах 3.1 и 3.2, видно, что метод последовательной минимизации расстояния Кульбака-Лейблера быстрее сходится, является устойчивым и позволяет находить оптимальные решения. В следующих параграфах этот метод будет применяться для различных обобщений задачи многократного наилучшего выбора.
Алгоритм вычислений приведен в приложении. Кроме того, отметим, что описанный алгоритм также эффективно применяется в других задачах. В частности, для отыскания оптимального правила в задаче многократного наилучшего выбора с минимизацией ожидаемого суммарного ранга [22, 65]. В работе рассматривается применение метода последовательной минимизации Кульбака-Лейблера и модифицированного генетического алгоритма для указанной задачи. Показано, что первый метод требует незначительных вычислительных затрат и отыскивает решения с меньшей погрешностью.
