Студопедия

КАТЕГОРИИ:



Мы поможем в написании ваших работ!

Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Мы поможем в написании ваших работ!

Итерационный алгоритм поиска решения МЦП


Автор: Вилисов Валерий Яковлевич, профессор кафедры Математики Технологического университета (г. Королев, Моск. обл.)

Есть два варианта алгоритма:

· полный перебор стратегий ;

· сокращенный перебор (алгоритм Р. Ховарда) с постепенным улучшением элементов вектора стратегий .

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

 

Рассмотрим, как можно построить целевую функцию.

Конкурирующие стратегии сравниваются между собой по величине среднего платежа за один шаг при большом количестве шагов ().

Определим средний платеж для -ой стратегии за один шаг в установившемся режиме, где , - полное количество возможных стратегий.

Для -ой стратегии из множества матриц можно составить одну рабочую и аналогично из матриц составить одну рабочую матрицу платежей .

Технология составления и состоит в том, что стратегия является ключом, для отбора строк из матриц и . Так первая строка в переносится из первой строки матрицы , вторая - из второй строки матрицы и т.д.

Аналогично конструируется и матрица . Таким образом, задача с K матрицами и K матрицами свелась к задаче с единственной матрицей и единственной матрицей , которые уже не зависят от решения k.

Средний платеж за один шаг при условии, что процесс находился в i-ом состоянии определится обычным усреднением:

.

Для вычисления безусловного среднего платежа необходимо определить вектор вероятностей состояний в установившемся режиме (). Тогда средний платеж за один шаг для фиксированной стационарной стратегии s в установившемся режиме определится так:

. (6)

Здесь можно принять в качестве целевой функции при выборе стратегии.

Тогда задача выбора оптимальной стратегии примет вид:

. (7)

Здесь неизвестным остается вектор . Из теории марковских процессов известно, что в установившемся режиме справедливо следующее матричное уравнение:

, (8)

где должно выполняться условие нормировки:

. (9)

Решение системы уравнений (8) и (9) позволяет получить значения координат вектора . Тогда в задаче (7) все элементы известны за исключением искомого аргумента s.



Пример. Рассмотрим, как можно построить матрицы и для типового примера.

Для и множество стратегий . Тогда, например, для стратегии

;

.

?

Метод полного перебора стратегий состоит из следующих этапов:

1. Сформировать множество стратегий .

2. Для очередной стратегии s сформировать матрицы и .

3. Вычислить вектор вероятностей состояний в установившемся режиме , решив систему уравнений (8) и (9).

4. Вычислить средний платеж за один шаг по формуле (6).

5. Выбрать оптимальную стратегию по формуле (7), сравнив значения для всех стратегий.

 

Метод итерационного перебора стратегий (метод Р. Ховарда).

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

Итерационный процесс прекращается, как только ни по одному элементу вектора стратегий нет улучшения.

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

Для любой стратегии из множества матриц и формируется одна матрица и одна . При этом МЦП с матрицей переходных вероятностей ведёт себя как обычная стационарная ЦМ.

В основе итерационного метода лежит уравнение Беллмана:

(10)

где, ось времени «развернута в обратную сторону», т.е. t означает число шагов, оставшихся до общей продолжительности процесса N.

В (10) от стратегии зависят лишь и , а не зависят. Здесь имеют смысл имеют смысл платежа при условии, что процесс находится в состоянии . В итерационном алгоритме их называют весовыми коэффициентами (ВК).

Схематически, метод состоит из двух чередующихся этапов:

· на 1-ом этапе - вычисляются ВК для стратегии ;

· на 2-ом этапе - улучшается стратегия варьированием решений для каждого состояния , в результате чего получается улучшенная стратегия .

Затем вновь повторяется 1-й этап и т.д. до тех пор, пока улучшенные стратегии на двух соседних шагах не будут отличаться.

Итерации можно начинать с любого из этапов.

На 1-ом этапе используются свойства уравнения (10) в установившемся режиме (при ), когда уже не будет зависеть от времени, а значит . С учетом этого (10) можно представить в таком виде:

, (11)

где и известны и однозначно определяются текущей стратегией , а не известны.

Следует решить систему уравнений (11) относительно неизвестных .

1-й этап называется этапом определения весовых коэффициентов (ВК).

На 2-ом этапе следует воспользоваться уравнением (10) для улучшения стратегии варьированием решений для каждого состояния , где и известны, а вычислены на 1-ом этапе. В (10) номер шага является номером итерации и - это ВК, вычисленные на предыдущей итерации. Т.е. в правой части (10) известны все элементы для фиксированной стратегии . Тогда, если изменять решения в , то значение левой части уравнения (10), имеющее смысл платежа для состояния , может служить показателем улучшения или ухудшения стратегии при варьировании элемента .

Таким образом, на данном (2-ом) этапе путем варьирования элементов текущей стратегии выбирается новая (улучшенная) стратегия, которая хотя бы по одному элементу вектора стратегий может оказаться лучше текущей. Новая стратегия становится текущей, и итерационный процесс переходит к 1-му этапу.

2-й этап называется этапом улучшения стратегии.

Этапы 1 и 2 повторяются до тех пор, пока процесс улучшения стратегий не прекратится, т.е. пока стратегии на двух соседних этапах не станут одинаковыми.

Приведенные алгоритмы поиска оптимальных стратегий МЦП успешно работают при условии, что характеристики процесса (и ) известны. Однако обычно платежи многокритериальны и часто неизвестны. Для МЦП также возможно решение обратных задач, т.е. восстановление обобщенной матрицы и матрицы по наблюдениям.



<== предыдущая лекция | следующая лекция ==>
Рекуррентный алгоритм поиска решения МЦП | Модели частоты рекламных воздействий

Дата добавления: 2014-01-04; Просмотров: 1010; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2021) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.009 сек.