Применение методов Монте–Карло для решения многокритериальных задач

Введение 4
Связанные работы 6
Глава 1. Теоретическое описание 7
1.1. Описание модели С ММ 7
1.2. Постановка задачи и пошаговый алгоритм решения 8
1.3. Описание алгоритмов и инструментарий 10
1.3.1. Алгоритм Баума-Велша 11
1.3.2. Алгоритм Витерби 14
Глава 2. Тестирование 16
2.1. Тестирование на примере игры “теннис” 16
2.1.1. Вычисление элементов матрицы B 17
2.1.2. Тестирование на данных, представленных в статье 19
2.1.3. Тестирование на данных, найденных нами 21
2.1.4. Сравнение с другими подходами решения поставленной задачи .... 22
2.2. Применение модели к другой игре со схожими характеристиками 24
Заключение 29
Список литературы 30
Приложение А. Реализация алгоритма Баума-Велша из пакета “НММ” . . 31
Приложение Б. Реализация алгоритма Витерби из пакета “НММ” 34

Купить

Многокритериальная задача — это математическая модель принятия оптимального решения одновременно по нескольким критериям. Эти критерии могут отражать оценки различных качеств объекта (или процесса), по поводу которых принимается решение, или оценки одной и той же его характеристики, но с различных точек зрения. В данной работе под многокритериальными задачами мы будем понимать задачи теории игр.
Математическая теория игр — дисциплина, возникшая на стыке 2 наук: математики и экономики. В настоящее время область ее практического применения достаточно широка: политические и дипломатические отношения, биология, информатика и другие. Предметом изучения данной дисциплины являются игры и связанные с ними стратегии (т.е. множества доступных игрокам действий), а целью — выработка методов нахождения оптимальных стратегий. Под игрой, как правило, понимается некоторая конфликтная ситуация, т.е. процесс, в котором принимают участие от двух и более сторон преследующих собственные цели (см., например, [1]).
Игры принято различать по типу. Например, кооперативные и некооперативные игры, с нулевой суммой и ненулевой суммой, параллельные и последовательные, метаигры, игры с полной или неполной информацией [2], [10]. Последние, с одной стороны, наиболее сложны для построения моделей прогнозирования, с другой - представляют значительный практический интерес, т.к., достаточно часто в реальных конфликтных ситуациях, участники не обладают полной информацией о действиях оппонентов [7], [9], [5].
Для дальнейших рассуждений нам понадобится следующее определение: ход игрока — это выбор действия из некоторого множества возможных действий игрока, определяемых правилами игры.
В нашей работе мы будем рассматривать игры, включающие в себя следующие элементы:
1. Чередование ходов, которые могут быть как личными, так и случайными;
2. Недостаточность информации;
3. Функция выигрыша [4].
Как уже было отмечено ранее, во многих реальных конфликтных ситуациях участники не обладают всей информацией об истинных состояниях процесса и могут оценивать результаты действий соперников только по некоторым ограниченным наборам данных. В этих условиях принятие решений может зависеть от нескольких факторов, в том числе — случайных. Один из возможных подходов к нахождению оптимальной стратегии в таких задачах это использование для описания исследуемой ситуации вероятностных моделей.
В данной статье мы будем использовать Скрытые Марковские Модели (СММ) для описания состояний игры в различные моменты времени. СММ зарекомендовали себя как мощное средство обработки данных в самых различных областях, с примерами применения можно ознакомиться в [8]. Преимущества СММ перед другими моделями следующие:
1. СММ обладают простой математический структурой;
2. Структура СММ позволяет моделировать сложную цепочку наблюдений;
3. Параметры модели могут быть автоматически выбраны таким образом, чтобы описать имеющийся набор данных для обучения (под обучением СММ понимается определение оценок параметров модели).
В недавно опубликованной работе [17] был предложен метод нахождения оптимальной стратегии для игры с двумя участниками, основанный на применении СММ. В статье был описан подход к решению стратегических игр, в которых игроки могут менять стратегии в течении игры. Целью было увеличить шансы игрока, т.е. узнать какую стратегию принимает соперник в каждый момент времени. Предложенный подход основан на использовании алгоритма Баума-Велша, решения марковской игры поиска смешанного равновесия Нэша.
В нашей работе мы хотим развить данный подход, предложив альтернативный метод, основанный на применении алгоритма Витерби для получения цепочки скрытых состояний и выбора наиболее вероятного хода вместо решения марковской игры.
Работу нашего алгоритма мы проиллюстрируем на двух демонстрационных примерах: игры в теннис и игры в “Камень, ножницы, бумага”.
Данная работа организована следующим образом: в Главе 1 дано теоретическое описание Скрытых Марковских Моделей, а так же предложена модель решения игры двух лиц с неполной информацией; в Главе 2 тестируется предложенная модель решения по игре, описанной в [17], также алгоритм тестируется по другой игре со схожими характеристиками.
Связанные работы
Основополагающей работой в теории игр является книга Джона фон Неймана и Оскара Моргенштерна “Теория игр и экономическое поведение” в 1944 г. [2] Большая часть данной книги посвящена играм с нулевой суммой. Игры с нулевой суммой — игры, в которых выигрыш одной стороны равен проигрышу другой. Игры с нулевой суммой с участием 2-х игроков называются антагонистическими. К таким играм также можно отнести игры с постоянной суммой, при которых сумма общего выигрыша всех игроков фиксирована, и поэтому увеличение выигрыша одного из них возможно только за счет уменьшения выигрышей других игроков.
В конце 1960-х годов Джон Харшаньи ввел понятие игр с неполной информацией и разработал концепцию байесовских равновесий. Д. Харшаньи рассматривал ситуации, когда у одного игрока нет информации о возможных выигрышах другого игрока, и выигрыши приходится оценивать вероятностно.
На практике часто встречаются ситуации, которые в теории игр принято называть повторной игрой (repeated game) т.е. игрой, которая состоит в некотором числе повторений некоторых игровых стадий (stage game). Впервые повторные игры с неполной информацией были введены Ауманом и Машлером в 1960г. [7] Рассматривались игры, в которых начальное состояние выбиралось с вероятностью р, и только иг рок 1 знает это состояние, в то время как игрок 2 знает все возможные состояния, но не знает фактического состояния. После каждого хода, оба игрока знают исход предыдущего хода и продолжают играть.
В [16] рассматриваются игры с двумя игроками с нулевой суммой, заданные цепью Маркова над конечным множеством состояний и семейством матричных игр. Последовательность состояний подчиняется цепи Маркова. В начале каждого этапа только игроку 1 сообщается о текущем состоянии, затем воспроизводится соответствующая матричная игра, после чего выбранные действия наблюдаются обоими игроками. Такие игры можно охарактеризовать играми с отсутствием информации с одной стороны.
В [17] описана модель скрытой марковской игры (СМИ), при которой второй игрок может наблюдать исходы того или иного хода противника, знает множество возможных скрытых состояний соперника, но не знает скрытых состояний в определенные моменты времени и матрицу переходов из состояния в состояние.
В нашей работе мы рассмотрим альтернативный метод нахождения оптимальной стратегии, разработанный на основе предложенного в статье [17].
Купить