Содержание к диссертации
Введение
1. Однокритериальные задачи наилучшего выбора . 8
1.1. Введение 8
1.2. Задачи с различной априорной информацией об оценках J0
1.3. Ранговые задачи 15
1.4. Выбор при случайном или неизвестном числе вариантов 20
1.5. Пуассоновский процесс появления вариантов . 22
1.6. Другие постановки 24
2. Многокритериальные ранговые задачи 26
2.1. Введение 26
2.2. Задача с конечным числом вариантов 29
2.3. Усеченные функции потерь 36
2.4. Предельная задача оптимальной остановки . 43
2.5. Оптимальное правило остановки и конечность минимальных средних потерь в предельной задаче 53
2.6. Случай симметрической функции потерь . 58
3. Задачи максимизации вероятности остановки на лучшем варианте 64
3.1. Введение 64
3.2. Функции выбора и пороговые правила остановки 66
3.3. Некоторые примеры 75
3.4. Остановка на парето-оптимальном варианте . 80
3.5. Остановка на недоминируемом варианте . 86
Заключение 93
Литература 95
- Выбор при случайном или неизвестном числе вариантов
- Задача с конечным числом вариантов
- Оптимальное правило остановки и конечность минимальных средних потерь в предельной задаче
- Функции выбора и пороговые правила остановки
Введение к работе
Математические модели и методы выбора лучших вариантов находят широкое применение в различных областях анализа сложных систем. Особое значение они приобрели при автоматизации проектирования, в задачах организации и планирования производства. Различным аспектам проблемы выбора: выявлению структуры предпочтений принимающего решение лица, рациональности выбора, теории полезности, алгоритмизации выбора, психологической теории решений, задачам коллективного выбора и другим, посвящены значительные усилия советских и зарубежных исследователей.
За последние двадцать лет в рамках статистической теории решений (более точно - статистического последовательного анализа) сформировался определенный класс моделей, называемый задачами наилучшего выбора. В этих моделях выбор рассматривается как многоэтапный процесс принятия решений, протекающий в условиях вероятностной неопределенности. Предполагается заданным некоторый класс стратегий выбора, определяемый типом информации о качестве обследуемых вариантов и ограничениями на их доступность для выбора. Эффективность выбора, то есть получаемый при использовании какой-либо стратегии выигрыш, считается зависящей от результатов попарного сравнения (ранжирования) вариантов.
Исходной для рассматриваемого круга задач послужила классическая задача наилучшего выбора, формулируемая следующим образом. Предположим, что имеется N вариантов, сравниваемых друг с другом по какому-то критерию, из которых требуется выбрать всего один вариант. Ознакомление с вариантами производится в случайном порядке, а на процесс выбора наложены такие ограничения: в каждый момент может быть выбран только непосред-
ственно наблюдаемый вариант, и ничего не известно о том, каковы последующие варианты. Требуется так остановить процесс выбора, чтобы выбранный вариант с максимальной вероятностью оказался наилучшим среди всех вариантов.
В настоящее время число различных постановок задач наилучшего выбора довольно велико (см. библиографию в конце работы). С большой полнотой изучены задачи максимизации вероятности выбора наилучшего варианта, некоторые классы ранговых задач, игровые модели и другие. Однако почти все известные постановки сохраняют неизменным предположение о возможности ранжирования вариантов по единственному критерию. Это предположение существенно ограничивает область практических приложений моделей выбора, поскольку в большинстве реальных задач оптимизации сложных систем возникает необходимость учета нескольких критериев качества выбираемых вариантов.
Целью настоящей работы является изучение задач оптимальной остановки, моделирующих выбор в ситуациях, когда сравнение вариантов производится по нескольким критериям. Важность развиваемых методов определяется, во-первых, тем, что они позволяют расширить спектр практических применений последовательного анализа, и во-вторых, тем, что эти методы позволяют получить априорные вероятностные оценки результатов выбора, характеризующие соответствие формализованных принципов оптимальности заданным ограничениям.
В принципе любая задача оптимальной остановки с конечным числом шагов может быть решена с помощью одного стандартного приема динамического программирования, называемого методом обратной индукции, который дает алгоритм построения оптимального правила остановки путем решения некоторого рекуррентного
функционального уравнения. В действительности решение этого уравнения лишь в редких случаях может быть найдено аналитически. Более того, в некоторых из рассматриваемых задач применение обратной индукции даже вычислительно невозможно, поскольку для этого требуются экспоненциально растущие (с ростом числа вариантов) объем памяти и число операций. Специальные методы, развиваемые в диссертации, ориентированы на нахождение асимптотически оптимальных или субоптимальных правил остановки.
Коротко изложим содержание работы.
Первая глава носит в основном обзорный характер. В ней приводится классификация известных однокритериальных постановок задач наилучшего выбора. Основное внимание уделяется задачам оптимальной остановки, в которых требуется выбрать всего один вариант. Освещаются задачи с различной априорной информацией о качестве обследуемых вариантов, ранговые задачи, модели выбора при неизвестном числе вариантов и другие. Некоторые результаты являются новыми.
Во второй главе рассматриваются многокритериальные ранговые задачи, постановка которых предложена Стадье [81] . Предполагается, что N обследуемых в случайном порядке вариантов сравниваются по т. независимым критериям. При обследовании очередного варианта становится известным вектор его относительных рангов, который содержит вместе с предыдущими относительными рангами всю информацию о результатах сравнения уже обследованных вариантов. Потери предполагаются заданными монотонной функцией вектора абсолютных рангов выбранного варианта. Требуется минимизировать средние потери по классу правил остановки последовательности наблюдений векторных относительных рангов.
Основные полученные результаты обобщают относящиеся к слу-
чаю одного критерия результаты Муцци [56,5?] , Джианини и Саму-эльса |_41,42 J . При А/—> цена продолжения (решение уравнения обратной индукции) аппроксимируется решением определенного дифференциального уравнения, которое является ценой продолжения в предельной задаче оптимальной остановки с непрерывным временем. Предельная задача естественно интерпретируется как задача наилучшего выбора с бесконечным числом вариантов. Неожиданной оказывается форма предельной задачи, выражающая асимптотический эффект "расслоения" множества вариантов на яг групп вариантов с "конечным" рангом по одному из критериев и "бесконечно большими" рангами по остальным критериям.
В третьей главе изучаются задачи максимизации вероятности остановки на лучшем варианте, которые включают некоторые известные постановки Джилберта и Мостеллера [44] , Гусейна-Заде Гі4J Березовского, Генинсона и Рубчинского [б] , Стадье [80J и автора [l2j Предполагается, что множество лучших вариантов определяется посредством заданной функции выбора, и за критерий эффективности правил остановки принимается вероятность остановки на одном из лучших вариантов. Решается в определенном смысле обратная с точки зрения теории оптимальной остановки задача: задавшись пороговыми правилами остановки вида "пропустить фиксированное число вариантов, и затем остановиться на первом же относительно лучшем варианте", мы находим класс функций выбора, для которых указанные правила оказываются достаточно эффективными. Показано, что в двухкритериальнои задаче остановки на па-рето-оптимальном варианте (изучавшейся ранее в работе [б J ) класс пороговых правил является асимптотически оптимальным, причем предельное значение его эффективности равно единице. Исследуется задача оптимальной остановки на недоминируемом вари-
_ 7 -
анте с полной информацией, когда функция распределения вектора критериальных оценок считается известной.
В заключении приводятся выводы.
Диссертация выполнена в соответствии с плановой работой Института проблем управления (номер государственной регистрации 01828052892). Результаты работы использовались для решения задачи выбора плана технической подготовки производства новой модели автомобиля на Волжском автомобильном заводе.
Результаты автора, составляющие основное содержание диссертации, опубликованы в работах Г6-10,12,13J .
Выбор при случайном или неизвестном числе вариантов
Б работе Джианини-Петтитт j_43j рассматривалась задача минимизации среднего ранга при случайном числе вариантов N Распределение N задавалось условием где 1-1,2. .,. и ol o . Пусть г? (п, J - минимальные (по классу правил остановки, основанных на относительных рангах) средние потери. В [43J доказано, что предел 1У(П, -) при /г бесконечен, если а(. 2. ; равен (I.II), если ( 2 ; конечен, но не меньше (I.II), если U =2 (случай d = 1 отвечает равномерному распределению на ff, ..., /гі ). Расмуссен [64J рассматривал задачу остановки с функцией по терь z(i) общего вида и случайным N . Впрочем, как выяс нилось впоследствии [50J , его утверждение об оптимальности неко торого правила вида (1.6), оказалось ошибочным. Корбин __38 изучал задачу выбора с вероятностными ограничениями на возможность возврата к пропущенным вариантам. В работе I80J термин "конечная память" понимается как воз - 20 можность сравнения очередного варианта только с ґп непосредственно предшествующими ему вариантами. 1.4. Выбор при случайном или неизвестном числе вариантов 1.4Л. Пусть N - случайная величина с заданным распределением рк = Р{М=к} К -1,2,.,. Предположим, что если N - К , то к, упорядоченных по качеству вариантов появляются в случайном порядке так, что все к--престановок равновероятны. Требуется, основываясь на попарном сравнении вариантов, с максимальной вероятностью остановиться на наилучшем из них. Начиная с работы Пресмана и Сонина [24 J , эта задача неоднократно рассматривалась в литературе [50,58,66,84] . Пресман и Сонин показали, что существует некоторое подмножество I С 1}2.} ,lt «оJ-такое, что оптимальное правило остановки имеет вид Максимальное (по включению) подмножество / вида [mirL л-7 или [ /п.} оо_/ называется островом. Задача нахождения Г и цены (оптимальной вероятности удачного выбора) имеет конструктивное решение, когда число островов конечно. Критерием конечности числа островов является неотрицательность последовательности - 21 начиная с некоторого K-d [24j . Как показано в (24j , на каждом острове происходит по крайней мере одна перемена знака с минуса на плюс последовательности оо 4?аРк-Ц-Г ="/j что дает более простое достаточное условие конечности числа островов. В случае, когда Г1 состоит из единственного острова Ы І -/ » оптимальное правило остановки является пороговым, т.е. аналогично (І.І). Например, равномерное на -ft,..., fby , геометрическое и пуассоновское распределения оказываются одноостровными ( ё меняет знак один раз [24J ). 1.4.2. Пусть А/ - семейство случайных величин, имеющих одноостровные распределения /рк j , и v - цена. Если существует слабый предел Р функций распределения то d /А стремится к точке максимума, а V" - к максимальному значению функции о . Например, для семейства равномерных распределений [24,66J : имеем =j&,V , U = еГ2 , Lf(U ) = 2.e . для семей ства пуассоновских распределений 24 J : (к)! J имеем (f(oi)--o( ъ при 0 t 1 , и ot = p(otj- с . Оптимальность Т доказывается в f24J посредством редукции к задаче остановки марковской цепи, последовательные состояния - 22 которой суть моменты появления относительно лучших вариантов. Ирле [50 \ предложил иной метод, модифицирующий известный в динамическом программировании метод Ховарда, который не требует редукции к марковскому случаю. Петручелли f 58J нашел достаточные условия оптимальности некоторого порогового правила.
Задача с конечным числом вариантов
В этой главе рассматривается непосредственное обобщение ранговых однокритериальных задач. Предполагается, что имеется N обследуемых в случайном порядке вариантов, сравниваемых между собой по /п независимым критериям. Под критерием по существу понимается определенный способ сравнения вариантов, а независимость формализуется как вероятностная независимость рангов по различным критериям. При обследовании очередного варианта становится известным вектор его относительных рангов. Считается, что потери при остановке на каком-либо варианте зависят только от его абсолютных рангов, причем потери тем больше, чем больше эти ранги. Требуется указать правило остановки, основанное на относительных рангах, для которого средние потери минимальны.
Решение этой задачи легко получается методом обратной индукции. Оптимальное правило оказывается заданным набором порогов, каждый из которых соответствует одному из значений относительного ранга, и указывает момент, начиная с которого выбрать вариант с таким относительным рангом становится выгоднее, чем пропустить его. Обратная индукция дает алгоритм нахождения порогов и мини малъных средних потерь V , однако найти для них аналитические выражения можно только в исключительных случаях. Более плодотворным оказывается изучение их поведения при N — =
При N—» решение уравнения обратной индукции аппроксимируется решением V- /і:) некоторого дифференциального уравнения, и V — v(o) . Основные трудности в доказательстве этого предельного перехода возникают в случае неограниченной функции потерь, когда v(l ) = x . Обходятся они так: сначала рассматрива - 27 ется случай "усеченных" функций потерь, и затем осуществляется предельный переход по "уровню усечения".
Вероятностный аспект предельных соотношений заключается в том, что v(-b) оказывается ценой продолжения в предельной задаче оптимальной остановки с непрерывным временем.
Таким образом, потери при выборе варианта с абсолютным рангом І є Utf максимальны, а при выборе варианта с абсолютным рангом ( V л зависят только от t , С-/32. . Пусть ci1t...ta варианты, имеющие абсолютные ранги 1,..., М по первому критерию, /,..., в - варианты, имеющие абсолютные ранги ...,/ по второму критерию. Выбор любого из оставшихся вариантов приводит к наибольшим потерям. Когда /V— х t вероятность сущеетвования хотя бы одного варианта с абсолютным рангом і є Жу стремится к нулю, т.е. множества /,..., схму и -li1t...} &п1 пересекаются с бесконечно малой вероятностью, при этом потери при выборе ак или 6К в пределе равны, соответственно у, (к, ft) и CL[ K)
Если считать моменты последовательных наблюдений равными f/rA/i 2/N ... / то момент появления ак или 6 в пределе является равномерно распределенной на единичном интервале случайной величиной, причем все такие моменты асимптотически независимы. Эти факты находят свое выражение в предельной задаче, в которой множество всех вариантов предполагается состоящим из двух бесконечных групп вариантов {ar3Oz ...j и {Sfi г.,---} ; внутри каждой группы варианты имеют конечный абсолютный ранг по одному из критериев и бесконечно большой - по другому, потери же определяются функциями $,(к,М) и (М7к) , /с /,2,..,.
Аналогичное расслоение имеет место и в общем случае, при произвольных числе критериев и функции потерь. При /V—9 для выбора становятся существенными tn групп вариантов с "конечным" рангом по одному из критериев и "бесконечно большими" рангами по остальным критериям.
Общий ход изложения следующий.
В п.2.2 содержится исходная постановка задачи с конечным числом вариантов и описание оптимального правила остановки.
В п.2.3 цена продолжения в исходной задаче аппроксимируется решением дифференциального уравнения в предположении, что функция потерь является усеченной.
В п.2.4 приводится постановка предельной задачи и вывод основного дифференциального уравнения для цены продолжения.
В п.2.5 находится оптимальное правило остановки в предельной задаче, эта задача связывается с исходной и указываются условия конечности минимальных средних потерь.
В п.2.6 рассматривается специальный случай симметрической функции потерь, в котором удается выписать рекуррентные уравнения для порогов в предельной задаче.
2.2. Задача с конечным числом вариантов
2.2.1. Предположим, что имеется вариантов, сравниваемых между собой по т. независимым критериям. Варианты обследуются в случайном порядке с целью выбора одного из них. На каждом шаге можно сравнить очередной вариант с предыдущими и, в зависимости от результатов уже проведенных сравнений, выбрать или пропустить. Потери при выборе какого-либо варианта определяются исключительно его сравнениями со всеми А/ вариантами, причем потери тем больше, чем хуже вариант. Требуется так остановить процесс выбора, чтобы средние потери были минимальны.
Оптимальное правило остановки и конечность минимальных средних потерь в предельной задаче
В предыдущей главе рассматривались задачи наилучшего выбора, в которых потери определялись абсолютным рангом выбранного варианта. В исследовании этих задач решающей оказалась редукция к случаю независимых наблюдений - относительные ранги независимы и потери, ожидаемые на очередном шаге, зависят только от текущего относительного ранга.
Более сложная структура потерь должна была бы учитывать зависимость от абсолютных рангов всех А/ вариантов. Однако введение такой зависимости приводит к значительному усложнению, поскольку ожидаемые потери в этом случае зависят уже от всех наблюденных относительных рангов. В принципе задача выбора может быть сведена к задаче оптимальной остановки некоторой марковской цепи, но число состояний этой цепи экспоненциально растет с увеличением числа вариантов, поэтому нахождение в общем случае оптимального правила остановки связано с большими вычислительными трудностями.
С точки зрения многокритериальной оптимизации, естественно рассмотреть следующий вид зависимости: потери равны нулю, если выбранным оказался парето-оптимальный вариант, и единице - в противном случае. Такая структура потерь отвечает задаче максимизации вероятности остановки на парето-оптимальном варианте. Хотя оптимальное правило остановки, по-видимому, не имеет простого описания, асимптотически оптимальным правилом в двухкрите-риальной задаче оказывается пороговое правило вида "пропустить
CL вариантов и затем остановиться на первом же варианте, па-рето-оптимальном относительно своих предшественников".
Заметим, что и в классической задаче наилучшего выбора оптимально также пороговое правило остановки (см. п.І.2.1). В задаче максимизации вероятности остановки на варианте, наилучшем по одному из критериев (см. П.2.&.3, пример I), класс пороговых правил является асимптотически оптимальным, а в задаче Цусейна-Заде [м] он дает довольно высокую вероятность успеха.
Обобщение перечисленных фактов приводит к постановке задачи наилучшего выбора в более абстрактной форме, безотносительно к ранговой структуре множества вариантов. В настоящей главе за основу берется предположение о том, что множество лучших вариантов определяется посредством некоторой функции выбора, и рассматривается задача остановки на одном из лучших вариантов.
В п.3.2 приводится постановка задачи в терминах, функций выбора и получается нижняя оценка эффективности класса пороговых, правил остановки для функций выбора, обладающих свойствами наследования и отбрасывания.
В п.3.3 эта оценка применяется к некоторым конкретным функциям выбора.
В п.3.4 рассматривается задача остановки на парето-опти-мальном варианте в случае двух критериев. Доказывается асимптотическая оптимальность класса пороговых правил остановки.
В п.3.5 рассматривается случай, когда функция выбора определяется некоторым частичным порядком. Вводится новый класс правил остановки (отличных от пороговых) и оценивается его эффективность.
Функции выбора и пороговые правила остановки
Перечислим основные результаты диссертации.
1. Проведены классификация и обзор известных в литературе однокритериальных постановок задач наилучшего выбора.
2. Найдено аналитическое выражение для оптимальной вероятности выбора наилучшего варианта в задаче остановки с полной информацией, связанной с пуассоновским процессом.
3. Проведено асимптотическое исследование ранговых многокритериальных задач наилучшего выбора: найден непрерывный аналог уравнения обратной индукции, доказана теорема о предельном значении минимальных средних потерь при бесконечно возрастающем числе вариантов и найдены условия конечности этого значения.
4. Изучена задача оптимальной остановки с непрерывным временем - предельная форма ранговых многокритериальных задач, найдено оптимальное правило остановки.
5. В случае симметрической функции потерь приведены рекуррентные уравнения для порогов, задающих оптимальное правило остановки в предельной задаче.
6. В терминах функций выбора сформулирована задача максимизации вероятности остановки на лучшем варианте.
7. Получена нижняя оценка эффективности пороговых правил остановки для функций выбора, обладающих свойствами наследования и отбрасывания.
8. Для случая двух независимых критериев доказана асимптотическая оптимальность пороговых правил в задаче остановки на парето-оптимальном варианте. Приведены асимптотически оптимальные правила остановки и в случае большего числа критериев.
9. В задаче максимизации вероятности остановки на недоминируемом варианте введен-класс правил остановки, который оказывается асимптотически оптимальным для отношения Парето. Получена оценка эффективности этого класса для произвольного частичного порядка.
