Материал: Материалы по курсу (часть 2)

11. Управление переходом организма из исходного в конечное состояние методом дп: использование ориентированного графа.

Рассмотрим управляемый процесс, который переводит некоторую систему G из начального состояния S0 в конечное состояние Sm. При наличии промежуточных состояний такой перевод представляется в виде траектории, состоящей из конкретной последовательности промежуточных состояний (рис. 2.1). Если промежуточные состояния могут быть различными, то траектория перевода G из S0 в Sm неоднозначна и зависит от вырабатываемых управляющих воздействий x.

W=W(x) – целевая функция, х – выбранное управление.

Введя какую-либо W=W(x), можно сравнивать (по величине W) траектории друг с другом и искать оптимальную, при которой достигается экстремум W. В зависимости от содержания целевой функции в процессе оптимизации ее стремятся либо максимизировать, либо минимизировать. Далее будет рассматриваться оптимизация, при которой W → min. Таким образом, задача заключается в отыскании оптимального управления x *, при котором целевая функция W достигает своего минимального значения W *, т. е.

Представим себе процесс управления состоящим из конечного числа последовательных шагов. В этом случае траектория перехода G из S0 в Sm будет иметь вид последовательности промежуточных состояний S0, S1, S2, …, Sm, которая является результатом пошагового управления x, также имеющего вид последовательности . Будем считать, что Si обозначает состояние системы G, а xi – управление на i-м шаге для произвольной траектории.

Для конкретной же траектории конкретное управление xi' переводит G в конкретное состояние Si’. Нужно иметь в виду, что управления x1, x2, …, xm в общем случае не числа, а векторы, функции, какие-либо предписания и т. п.

Пусть на каждом отдельном i-м шаге, заключающемся в переходе из S_i-1 в Si, известно значение целевой функции W, которое обозначается w_i. Считая выбранный критерий W аддитивным, т. е. полагая, что задачу оптимизации можно сформулировать следующим образом. Требуется найти такое оптимальное управление (где – оптимальное шаговое управление на i-м шаге), при котором целевая функция W принимает минимальное значение, т.е.

.

Пример:

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

1. Перечислить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения.

2. Для каждого i-го шага определить значение w_i в функции от состояния S_i-1 на (i-1)-м шаге и от шагового управления x_i

3. Определить, как изменяется состояние S_i-1 системы G под влиянием управления x_i на (i-1)-м шаге: оно переходит в новое состояние

4. Пусть W_i(S_i-1) – условный оптимум целевой функции, получаемый на всех последующих шагах, начиная с i-го и до конца. Надо записать основное рекуррентное уравнение динамического программирования, выражающее W_i(S_i-1) через уже известную функцию W_i+1(S_i),

Этому условному оптимуму целевой функции соответствует условное оптимальное управление на i-м шаге x_i(S_i-1), которое совместно с оптимальным управлением на всех последующих шагах обращает целевую функцию на всех оставшихся шагах, начиная с данного, в минимум.

5. Произвести условную оптимизацию последнего, m-го шага, задав множество состояний S_m-1, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого S_m-1 условный оптимум целевой функции по формуле

и находя условное оптимальное управление x_m(S_m-1), для которого этот минимум достигается.

6. произвести условную оптимизацию (m-1)-го,(m-2)-го и т. д. шагов по формуле , полагая в ней i=(m-1),(m-2),… и для каждого шага указать условное оптимальное управление x_i(S_i-1), при котором достигается минимум.

Так как начальное состояние системы S0 одно, и оно известно, то на первом шаге варьировать состояние системы не нужно – оптимальное значение целевой функции для S0 находится непосредственно. Это и есть оптимум функции цели за весь процесс перевода:

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

12. Управление переходом организма из исходного в конечное состояние в условиях неопределенности.

Поведение системы зависит не только от начального состояния S₀ и выбранного управления x, но и от случайности.

Рассмотрим стохастическую модель задачи о кратчайшем пути на ациклической сети. Допустим существование в системе условных вероятностей P(S_i/S_i-1) того, что на i-м шаге управления система перейдет в состояние S_i при условии, что до этого она находилась в S_i‑1 и было применено управление x_i. Это условие представляет собой допущение о марковском свойстве системы, согласно которому вероятность перехода системы в какое-либо состояние S_i зависит только от состояния S_i-1, из которого совершается переход, и от применяемого управления x_i, но никак не зависит от предыстории системы, предшествующей ее переходу в S_i-1.

Пусть S_i^(j) обозначает конкретное состояние системы, в которое она переходит на i-м шаге, w_ik^(j) – временные затраты на перевод организма в состояние S_i^(j) на i-м шаге из состояния S_i-1^(k).

Предположим, что для части сети известно условные минимальные средние временные затраты W̅_i+1(S_i) на достижение конечного состояния из

Через р₁,р₂,…,p_n обозначены условные вероятности перехода p_j=P(S_i^(j)|S_i-1,x_i), причем Если, например, находясь в состоянии S_i-1 применяем управление x_i, то средние затраты времени W̅_i(S_i-1|x_i) на достижение конечного состояния из S_i-1:

Т.к. вариантов управления на i-м шаге может быть несколько, т.е. x_i может принимать разные значения при котором становится минимальным. При этом стохастическое обобщение основного рекуррентного имеет вид:

Развернутая форма:

Т.к. мы применяем условные вероятности, то

Пример 1:

Решается задача управляемого перевода организма из исходного состояния S0 в конечное состояние S₃ (лечение, нормализация состояния оператора). При этом существуют промежуточные состояния , а возможные переходы их состояния в состояние изображены на рис.2.11 в виде ориентированного ациклического графа. На ребрах графа проставлено время, требуемое для перевода организма из одного состояния в другое. В каждом состоянии S_i-1 имеется несколько управляющих воздействий xi, которым соответствуют определенные наборы вероятностей перехода

Сумма чисел в каждой строке = 1

Кроме того, в состоянии всегда применяется управление x₃⁽¹⁾ и , а в состоянии всегда применяется x₃⁽²⁾ и

Требуется каждому состоянию сопоставить одно оптимальное управляющее воздействие, при котором общее среднее время перехода из в будет минимально, а также определить это время.

Времена перехода организма из состояния в состояние равны:

Условную оптимизацию, как и раньше, начинаем с последнего, 3-го шага управления. Из условия задачи видно, что на 3-м шаге управление вынужденное, поэтому

Условную оптимизацию на 2-м шаге проводим с помощью рекуррентного уравнения

min

min

Результат оптимизации

В кружках проставлены значения условных минимумов . Из рисунка видно, что оптимальное управление на 1-м шаге равно x₁⁽²⁾. Оно детерминировано переводит систему в S₁⁽¹⁾, где наилучшее управление заключается в применении x₁⁽³⁾. При этом система переходит в S₂⁽¹⁾ или в S₂⁽¹⁾, с вероятностями, равными 0,6 и 0,4 соответственно. Если переход осуществлен в S₂⁽¹⁾, то дальше надо применять x₃⁽¹⁾, если же в S₂⁽²⁾, то оптимальное шаговое управление здесь x₃⁽²⁾. В обоих случаях система переходит в S₃. Состояния S₁⁽²⁾ и S₁⁽³⁾ остаются незадействованными. Минимальное среднее время перехода из S₀ в S₃ составляет 11,6 единиц времени.

Пример 2:

В течение ближайших 3-х дней больному необходимо сделать срочную операцию. Для уменьшения риска неблагоприятного исхода желательно, чтобы состояние больного непосредственно перед операцией было наилучшим. С помощью медицинских обследований состояние больного оценивают по трехбалльной шкале, причем оценка 1 соответствует наихудшему состоянию S₁, 2 – промежуточному S₂, 3 – наилучшему S₃. Надо рассчитать оптимальную стратегию врача (т.е. в какой из трех дней лучше всего делать операцию), если вероятности наступления состояний S₁, S₂, S₃, и в любой день не зависят от состояния больного в предыдущий день и равны

p1=P(S1) =0,3; p2=P(S2) =0,5; p3=P(S3) =0,2;

Для решения этой задачи составим дерево альтернатив, изображенное на рис.2.13 Пусть z_i - оценка состояния больного, а x_i - принимаемое решение в i-й день. Тогда после измерения состояния больного в 1-й день (Изм1), если z₁=3, то x₁=[On], т.е. принимается решение оперировать; если z₁=1, то x1=[Жд]- ждать следующего дня, а если z₁=2, то возникает неопределенность (может быть принято, как одно, так и другое решение). Аналогичная ситуация возникает и на второй день после процедуры Изм2, если в 1-й день принято решение [Жд]. Таким образом задача заключается в выработке рекомендаций о принятии оптимальных решений, если в 1-й или во 2-й день состояние больного будет оценено как 2.

В качестве критерия оптимальности (целевой функции) будем использовать среднеожидаемую оценку состояния оперируемого больного, которую необходимо максимизировать. Пусть w_i^(j)- значение целевой функции на i-й день при z_i=j. Допустим, больного решили оперировать лишь на 3-й день. В этом случае среднеожидаемая оценка состояния больного перед операцией будет равна (рис. 2.14).

Этот результат показывает, что если на 2-й день мы получили z₂=2, то (так как это больше, чем 1,9) наилучшим будет решение x₂=<On> и для второго дня дерево альтернатив представляется в виде рис. 2.15. Из рисунка видно, что w₂⁽¹⁾ = w̅₃.Рассуждая аналогично, среднеожидаемая оценка состояния больного на 2-й день