Субъективный способ нормирования параметров

При проектировании любой системы требуется достижение некоторых качеств (в противном случае речь не может идти о проектировании, а тогда что и зачем сравнивать), совокупность данных требуемых качеств и определяет идеальный вектор, то есть параметры q_nmax и q_nmin - формируются субъективно разработчиком, исходя из условий задач. Действительно, как выбирать, как назначать какие-либо весовые коэффициенты, пока не определился с тем, что необходимо получить в результате. Исходя из этого посыла, предполагаем, что задать подобные значения q_nmax и q_nmin возможно всегда. А теперь очень важный момент, следующий из представленной выше интерпретации. Задав q_nmax и q_nmin , мы тем самым задаем идеальный вектор, причем не только его величину, но и расположение в пространстве. Напомним, что, следуя интерпретации, расположение вектора в пространстве задается назначением весовых коэффициентов. В данном случае, задав q_nmax и q_nmin , мы тем самым задаем и весовые коэффициенты – относительную важность параметров. Т.е. при таком подходе к решению задачи снимаются все неопределенности – выбирается вариант, наиболее подходящий сформулированным требованиям.

Замечание:

В случае если у варианта значение какого-либо параметра превосходит требуемое, то при выборе учитывается требуемое качество, а не значение какого-либо параметра варианта (так как в подобном завышении локального качества нет необходимости). Учеет же завышенного значения параметра приведет к изменению расположения идеального вектора в пространстве, т.е. к изменению «весов», задаваемых по умолчанию.

Для решения задачи используется аддитивная свертка:

_N

Yn = ∑q_nm

ⁿ⁼¹

а нормированные значения параметров вариантов определяются соответствующим образом:

q_nm = q_nm / q_nmax , если лучшее значение качества определяется, как max (например, производительность)

q_nm = q_nmin / q_nm, если лучшее значение качества определяется, как min (например, стоимость)

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

Достоинства:

· Однозначно интерпретируем идеальный вектор качества, задающий то совокупное качество, которое следует обеспечить проектируемой системой (а не неким гипотетически идеальным набором значений параметров, достижение которых может быть недостижимым в совокупности).

· На идеальный вектор (величину и расположения) никак не сказывается выбор сравниваемых между собою вариантов.

· Не требуется как-либо дополнительно учитывать относительную важность параметров, так как она подсознательно задается разработчиком при формировании требуемого качества системы при проектировании.

Игровые системы

Элементы теории игр

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

Наибольший интерес вызывают антагонистические игры – где выигрыш одного игрока означает проигрыш другого. Игра описывается платежной матрицей.

B A			……
			……
..	……

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

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

Для этого используются максиминный (максимальный из минимальных выигрышей) и минимаксный (минимальный из максимальных проигрышей) критерии:

Игра с седловой точкой задается условием (равенство максиминного и мимимаксного критериев).

Пример платежной матрицы игры с седловой точкой:

3 8 6 5 3

10 9 8 7 7

6 5 2 4 2

15 9 8 3 9

Рассмотрим платежную матрицу. Стратегии игрока А определяются строками, игрока В – столбцами.. Максимальный из минимальных выигрышей для игрока А образует значение «7» во второй строке. Действительно, какую бы стратегию не выбрал игрок В, если игрок А выбрал вторую стратегию, то его выигрыш не будет менее 7. При любой иной стратегии все зависит от действий игрока В и выигрыш игрока А может быть ниже. Например, игрок А решил «рискнуть» и выбрал четвертую стратегию. В предположении, что игрок В будет придерживаться первой стратегии, игрок А может получить максимальный выигрыш «15». Но игрок В сразу перейдет к третьей стратегии, и в этом случае выигрыш игрока А составит всего лишь «3».

Теперь рассмотрим поведение игрока В. Максимальный из минимальных проигрышей для него составит значение «7» в четвертом столбце. Если он будет придерживаться четвертой стратегии, то больше «7» он не проиграет. Если он рискнет, например, выберет третью стратегию, где его проигрыш может составить всего «2», то игрок А может выбрать вторую или четвертую стратегии, и проигрыш игрока В увеличится.

Таким образом, исходя из пессимистической оценки, обоим игрокам лучше не рисковать, тогда они обречены на выигрыш/проигрыш «7».

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

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

-вероятность попадания в вершину

-цена игры в l-ой вершине графа.

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

Таким образом, данный математический аппарат позволяет обосновать и выбрать действия противников, стратегии их поведения, предусмотреть возможный выигрыш/проигрыш игроков для достаточно широкого приложения задач, сводящихся к теории игр.

ПОДВЕДЕМ ИТОГИ

1. В данном курсе нами рассмотрены наиболее часто применяемые на практике в области вычислительной техники методы оптимизации, используемые при проектировании детерминированных систем: методы синтеза оптимального плана, расписания, маршрута. Вместе с тем, нами не рассмотрен важнейший раздел теории исследования расписаний, связанный с оптимизацией вероятностных систем (стохастические методы). Этот раздел будет вами рассмотрен в курсе лекций, посвященном теории массового обслуживания профессора Т.И. Алиева.

Весьма кратко мы коснулись игровых систем, которым посвящен целый раздел исследования операций – теория игр, а также способов учета эвристических знаний при решении оптимизационных задач. Эвристика находит широкое использование в экспертных системах, с вопросами построения и использования которых вы познакомитесь в курсе лекций доцента И.А. Бессмертного.

3. Что очень важно, и на что хочется обратить ваше внимание:

Основной целью лекционного курса является не ознакомление вас с неким ограниченным набором методов оптимизации, что, отчасти, бессмысленно за весьма ограниченное время, ввиду их большого разнообразия; не привитие вам неких навыков применения данных методов. Основа курса – это рассмотрение подходов к проектированию, к обоснованию эффективности полученных решений на предметной области «методы оптимизации». В конечном счете, не так важно, что вы будете проектировать, какую-либо сложную техническую систему или собственно метод оптимизации. И в том, и в другом случае, вам необходимо четко сформулировать цель решаемой задачи, четко обосновать (неким образом интерпретировать) предлагаемый подход к решению, суметь обосновать эффективность полученного решения. В данной же части курса мы пытались научиться проектировать методы оптимизации для различных практических приложений, обосновывать их эффективность для различных способов использования;

Как изучать материал и как готовиться к тестированию и к экзамену. Для этого необходимо понять цель данного курса – это рассмотрение подходов к проектированию, к обоснованию эффективности полученных решений. Большинство контрольных вопросов будут посвящены именно этому. Вам не требуется ничего зазубривать – Вам требуется лишь хорошо разобраться в изложенном материале.