Geum.ru

Б. Ф. Мельников (Тольяттинский государственный университет, B. Melnikov@tltsu ru, bormel@mail ru) Аннотация Внастоящей статье рассматриваются эвристические методы принятия решений в различных задача

Вид материалаЗадача

Содержание


3. Принятие решений при одновременном применении нескольких разных «жадных» эвристик. Динамические функции риска
Подобный материал:
1   2   3   4   5   6   7

3. Принятие решений при одновременном применении

нескольких разных «жадных» эвристик. Динамические функции риска


Как уже было отмечены выше, кроме эвристики, формулирующей сам МВГ (для ЗКВ, либо для какой-либо другой ЗДО) всегда необходима ещё одна эвристика. А именно – эвристика для выбора элемента, «разделяющего» рассматриваемую задачу на левую и правую подзадачи.16 Однако некоторый эвристический разделяющий алгоритм может быть заменён на какой-либо другой; более того, очень часто при решении некоторой ЗДО с помощью МВГ желательно выбирать один из нескольких разделяющих алгоритмов – в зависимости от того, какая именно подзадача решается. Разные варианты разделяющих алгоритмов могут быть выбраны в зависимости от размерности решаемой задачи, от её границы, а также от многих других характеристик, связанных с конкретными ЗДО.

В рассматривавшемся нами примере описания МВГ для ЗКВ в [4] используется хороший (т.е. дающий хорошие результаты по сравнению с другими) разделяющий алгоритм – но только один. Однако задолго до издания [4] (вышедшей на языке оригинала в 1977 г.) при описании ветвления в МВГ использовались самые различные эвристики – подробнее см., например, [17];17 более современный взгляд на данную проблему см., например, в [18]. Для рассматриваемой нами ЗКВ упомянем, например, такие эвристики:
  • суммарное число нулей;
  • сумму минимумов, взятых по строкам и по столбцам;
  • сумму нескольких разных минимальных значений в каждой строке и столбце с некоторыми «коэффициентами затухания»;
  • количество строк и столбцов, в которых содержится более одного нуля

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

Итак – как же воспользоваться тем фактом, что в разных конкретных ситуациях (в разных конкретных подзадачах одной и той же ЗДО) относительно лучше работают разные эвристики? (Всё это относится и к точным, завершённым алгоритмам, и к неточным, незавершённым.) Нам требуется определённым образом принять решение о выборе конкретного элемента матрицы стоимостей для ветвления. Имеется информация, данная разными экспертами – разными эвристиками, т.н. «предикторами». При этом очень часто эксперты дают противоречивую информацию – и надо её каким-то образом «усреднять».18 Усреднение делается с помощью набора коэффициентов – но, в отличие от всех ранее опубликованных алгоритмов ([6]19 и мн.др.), автор использовал в своих алгоритмах динамически подобранные функции риска.

Поскольку разные эвристики выдают значения, выраженные в разных «единицах измерения», для вычисления окончательного результата их необходимо специальным образом нормировать. Набор специальных коэффициентов нормировки (настраиваемый, например, с помощью генетических алгоритмов, о которых будет сказано ниже) – метод, по-видимому, достаточно хороший, но не он является основным для изложенного в настоящей статье. Автор в разных ЗДО использовал специальную модификацию «метода голосования», где каждая эвристика выдаёт рассматриваемые варианты выбора (например, в случае ЗКВ – нули приведённой матрицы стоимостей, соответствующие некоторым дугам – кандидатам для ветвления). После этого к результатам голосования (т.е. просто к результатам применения разных эвристик-предикторов для разных элементов-кандидатов) применяются динамически подобранные функции риска.20

Итак, основной выбор ребра для ветвления в МВГ осуществлялся путём применения динамически подобранных функций риска (ДФР). Подробнее о взглядах автора на применение подобных функций см. в [7]. Поскольку та статья была посвящена программированию непосредственно недетерминированных игр21, в нашем случае необходима ещё одна эвристика – для выбора «оценки текущей позиции», т.е. конкретной ситуации, возникшей при решении некоторой ЗДО с помощью МВГ. См. ниже обоснование метода выбора стратегии в случае нескольких экспертов и краткое изложение результатов вычислительных экспериментов.22 Однако стоит отметить, что часто на практике алгоритмы, использующие ДФР, удачно работают и в том случае, когда такой эвристики – для выбора аналога оценки текущей позиции в играх – и не существует; см. об этом подробнее в разделе 6.

Итак, пусть имеются несколько различных эвристик для выбора конкретной стратегии решения некоторой ЗДО. При этом каждая из возможных стратегий имеет несколько различных экспертных оценок перспективности (т.е. имеется несколько независимых подпрограмм-экспертов, предикторов). Стратегию можно выбирать просто по максимальному значению среднего значения перспективности. Однако рассмотрим следующий пример ([13]; пример идейно близок к статье [7], поскольку в нём используются 36 предикторов).

Пусть экспертные оценки перспективности изменяются в пределах отрезка [0,1].23 Пусть для 1-й стратегии 1 эксперт дал оценку 1, и 35 экспертов – оценку 0.055. А для 2-й стратегии 2 эксперта дали оценку 0.95, а остальные 34 эксперта – оценку 0. Видимо, на основе этих данных практически любой пользователь (человек) выберет 2-ю стратегию. (Поскольку в 1-й стратегии имеется 1 «очень хороший» результат и 35 «очень плохих», а для 2-й стратегии – соответственно 2 «очень хороших» и 34 «очень плохих»; «средних» же результатов ни в одном из двух случаев нет.) Однако усреднение по простейшему алгоритму (т.е., просто среднее арифметическое экспертных оценок) даёт 0.081 в 1-м случае и 0.053 во 2-м – т.е., надо выбирать 1-ю стратегию?

Проведём вычисления, аналогичные [7] – с теми же самыми алгоритмами построения ДФР. Для 1-й стратегии получаем функцию риска

–0.685  x2 + 1.300  x + 0.386 ,

а для 2-й –

–0.694  x2 + 1.374  x + 0.321 .

Окончательные значения усреднения экспертных оценок с помощью этих функций риска составляют 0.111 в 1-м случае и 0.147 – во 2-м. То есть применение алгоритмов динамического построения функций риска и усреднения экспертных оценок с их помощью даёт «более естественные» результаты.

Справедливости ради стоит отметить, что двукратное применение усреднения (т.е. усреднения с помощью предварительных значений, полученных в результате первого применения динамических функций риска) снова «даёт преимущество» 1-й стратегии. Однако в пределе24 снова получаются «естественные» результаты. Опишем эти результаты в виде следующей таблицы, где обозначения столбцов равны номеру усреднения с помощью динамической функции риска (другими словами – количеству применений алгоритма построения ДФР). При этом столбец 0 – простое усреднение (среднее арифметическое оценок), а столбец  – значения в пределе.
0
1
2
3
4
5
…


1-я стратегия
0.081
0.111
0.104
0.106
0.105
0.105
…
0.105

2-я стратегия
0.053
0.147
0.094
0.118
0.106
0.112
…
0.110

Этот пример вовсе не является искусственным, «оторванным от реальности»: в реальных алгоритмах экспертных оценок, упомянутых выше, случаи разброса экспертных оценок (данных разными предикторами), при которых разница между максимальным и минимальным значением превышает 0.5 (т.е. половину длины отрезка изменения оценки) весьма часты – например, в случайной ЗКВ размерности 75 они, согласно проведённым автором статистическим исследованиям, составляют около 10%.25