Мультиэвристический подход к задачам дискретной оптимизации1



Скачать 475.48 Kb.
страница3/9
Дата17.01.2013
Размер475.48 Kb.
ТипДокументы
1   2   3   4   5   6   7   8   9

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

1   2   3   4   5   6   7   8   9

Похожие:

Мультиэвристический подход к задачам дискретной оптимизации1 iconСитуационный подход к задачам поиска текстовой информации
Здесь тоже присутствуют идеи такого рода: будет использоваться некий набор экстралингвистических отношений, и эти экстралингвистические...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЭлементы дискретной математики
П. А. Корнилов, Н. И. Никулина, Семенова О. Г. Элементы дискретной математики. Учебное пособие. Ярославль: Изд-во ягпу им. К. Д....
Мультиэвристический подход к задачам дискретной оптимизации1 iconУрок по геометрии в 7-м классе на тему "Некоторые свойства прямоугольных треугольников"
Раздаточный материал: карточки с тестом, листы с чертежами к задачам самостоятельной работы, листы для ответов к задачам самостоятельной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛингвистические противоречия в терминологической системе дискретной математики
Именно таким путем язык может разрешить определяющее противоречие говорящего и слушающего, которое в терминологической системе дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconСборник упражнений для студентов математического факультета пединститута
В сборник включены упражнения по дискретной математике. Основная цель упражнений – отработка основных понятий дискретной математики,...
Мультиэвристический подход к задачам дискретной оптимизации1 icon"Построение конечно-разностных формул на границе дискретной области счёта"
При численном решении уравнений математической физики важным становится вопрос замены непрерывной области изменения аргумента дискретной...
Мультиэвристический подход к задачам дискретной оптимизации1 iconВ. П. Голубятников известный специалист в области геометрии, топологии и их приложений к задачам математического моделирования и к обратным задачам. Он опубликовал 160 научных работ, в том числе монографию Uniqueness q
«Uniqueness questions in reconstruction of multidimensional objects from tomography-type projection data», изданную в Голландии,...
Мультиэвристический подход к задачам дискретной оптимизации1 iconПрограмма курса Дополнительные главы дискретной математики для групп 318, 319 кафедры математической кибернетики
«Дополнительные главы дискретной математики» (для студентов 3-го курса 2-го потока). В нее включены разделы, относящиеся к конечнозначным...
Мультиэвристический подход к задачам дискретной оптимизации1 iconЛичностно-ориентированный подход к обучению иностранному языку
Личностный подход к обучающимся при организации учебно– воспитательного процесса
Мультиэвристический подход к задачам дискретной оптимизации1 iconМеждународный опыт в области инклюзивного образования: Норвегия
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org