автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Нахождение оптимальных планов параллельного управления в случайной среде в приложении к обработке данных

На правах рукописи

Олейников Андрей Олегович

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Петрозаводск - 2014

005556192

На правах рукожйш

Олейников Андрей Олегович

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

05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Петрозаводск - 2014

Работа выполнена в Новгородском государственном университете им. Ярослава Мудрого.

Научный руководитель: Официальные оппоненты:

Ведущая организация:

Колногоров Александр Валерианович,

доктор физико-математических наук, доцент Печников Андрей Анатольевич,

доктор технических наук, доцент, ведущий научный сотрудник лаборатории телекоммуникационных систем Карельского научного центра РАН

Золотухин Игорь Владимирович,

кандидат физико-математических наук, старший научный сотрудник лаборатории оптики океана и атмосферы Санкт-Петербургского филиала Института океанологии имени П. П. Ширшова РАН

Казанский национальный исследовательский технический университет имени А. Н. Туполева

Защита состоится «17» октября 2014 г. в 14 часов на заседании диссертационного совета Д 212.190.03 при ФГБОУ ВПО «Петрозаводский государственный университет», по адресу: 185910, г. Петрозаводск, пр. Ленина, 33.

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

Автореферат разослан « ^ »__2014 г.

Отзывы и замечания по автореферату в двух экземплярах, заверенные печатью, просьба высылать по вышеуказанному адресу на имя ученого секретаря диссертационного совета.

Ученый секретарь диссертационного совета

Воронов Роман Владимирович

Общая характеристика работы

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

Упрощенно можно описать рассматриваемую модель управления следующим образом: есть несколько шагов, на каждом из которых ЛПР необходимо выбрать одно из двух действий. На выбор каждого из действий ЛПР получает реакцию среды, интерпретируемую как доход. При этом реакция является случайной величиной и зависит только от выбранного на данном шаге действия. Аналогичные модели описываются в задачах о целесообразном поведении в стационарной случайной среде, двуруком бандите и в задаче адаптивного управления.

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

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

Представим, что нам необходимо обработать очень большой объем данных. Для обработки имеется два способа, которые с вероятностями р\ и р2 соответственно приводят к успешной обработке. Разбив данные на группы и применяя ко всем данным в группе один и тот же способ обработки, мы можем использовать количество успешно обработанных данных в качестве дохода. При использовании параллельной обработки мы можем уменьшить необходимое количество этапов, при этом не сильно потеряв в качестве обработки.

Стратегии, получение которых описано в данной диссертации, имеют пороговый характер и для их хранения требуется некоторый объем памяти. Применение такой пороговой стратегии — простая задача, которая может быть реализована даже на устройствах с очень ограниченными ресурсами. Для применения в подобных устройствах полезным может оказаться минимизация объема памяти, требующегося для хранения стратегии.

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

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

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

1. Создание модели параллельной обработки данных с использованием групп различного размера.

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

3. Исследование способов упрощения стратегий и влияния упрощений на полученные доходы.

4. Разработка комплекса программ для исследования параллельной обработки.

Научная новизна. В диссертации описывается два усовершенствования для алгоритма параллельной обработки данных в двухальтернативной среде, а именно: параллельная обработка с различными размерами групп и применение упрощенных стратегий. Описанные усовершенствования и результаты экспериментов по их применению являются новыми результатами.

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

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

Положения, выносимые на защиту. На защиту выносятся следующие положения:

1. Модель двухальтернативной параллельной обработки данных с группами различного размера.

2. Численный метод поиска оптимальных размеров групп для параллельной обработки данных.

3. Численные методы упрощения стратегий параллельной обработки дан-пых.

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

Степень достоверности и апробация результатов. Достоверность результатов подтверждается корректными математическими выкладками и согласованностью результатов расчетов и численного моделирования. Также о достоверности результатов свидетельствует их согласованность с оценками и результатами, полученными другими авторами.

Основные результаты диссертации докладывались на следующих конференциях:

1. XIX научная конференция преподавателей, аспирантов и студентов НовГУ, 2-7 апреля 2012 г., Великий Новгород.

2. 8-я международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 2-9 нюня 2012 г., Петрозаводск.

3. 55-я научная конференция МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе», 19 - 25 ноября 2012 г., Долгопрудный, Московская обл.

4. XX Всероссийская Школа-коллоквиум по стохастическим методам/Х1У Всероссийский симпозиум по прикладной и промышленной математике, 12 - 18 мая 2013 г., Йошкар-Ола.

5. XIV Всероссийский симпозиум по прикладной и промышленной математике, 29 сентября - 5 октября 2013 г., Великий Новгород.

6. 56-я научная конференция МФТИ «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе», 25 - 30 ноября 2013 г., Долгопрудный, Московская обл.

А также на следующих семинарах:

1. Семинар кафедры прикладной математики и информатики Новгородского государственного университета им. Ярослава Мудрого, 19 ноября 2013 г., Великий Новгород.

Публикации. Материалы диссертации опубликованы в 9 печатных работах, из них 2 статьи в рецензируемых журналах, рекомендованных ВАК [2. 11], 1 статья в сборнике трудов конференций [3], 1 депонированная рукопись [4] и 5 тезисов докладов [5-9]. Получено свидетельство на разработанную программу для ЭВМ [10].

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и списка литературы. Общий объем диссертации — 111 страниц, включая 18 рисунков. Список литературы содержит 69 наименований.

Содержание работы

Во Введении даны общие сведения по исследуемой проблеме, обоснована актуальность диссертационной работы, сформулированы цель и задачи работы, отмечена научная новизна исследований, показана практическая значимость полученных результатов, представлены выносимые на защиту положения.

Задача рассматривается в следующей постановке: пусть n = 1,..., Л^ — управляемый случайный процесс, где рассматриваются в качестве дохода. На каждом этапе управления п (употребляется термин «шаг») ЛПР может выбрать одно из двух возможных действий. Доходы зависят только от выбранного на данном шаге действия и имеют нормальные распределения с математическими ожиданиями т\ и шг соответственно и единичными дисперсиями. Значения т.\ и 7712 не известны ЛПР. Цель управления состоит в максимизации дохода в некотором смысле [12, 13].

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

Среда может быть описана векторным параметром в = (т^шг). Если бы в была известна заранее, то оптимальная стратегия предписывала бы всегда выбирать действие, которому соответствует большее из значений mj, тг- Ожидаемый доход от применения такой стратегии составил бы JVmax(mi, тпг). Если же параметр неизвестен, то функция

характеризует потери вследствие неполноты информации. Здесь Еа# обозначает математическое ожидание по мере, порожденной стратегией а и параметром 9 [12].

Есть несколько подходов к данной задаче. Один из них — это минимаксный подход. При таком подходе находится стратегия управления, приводящая к наименьшим потерям для наихудших возможных параметров среды. Нас будет интересовать множество допустимых параметров среды

(1)

6 = {(этг^тг) : \т\ — ГП21 < 2с},

(2)

где с — некоторая константа (0 < с < с»). В таком случае минимаксный риск будет равен:

/$(©) = Ы5ирЬк{а,д) (3)

£ е

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

Рассмотрим подробнее вторую модель: представим, что нам необходимо обработать большое количество данных. Для каждой новой единицы данных способ обработки может быть выбран только после того, как получены результаты обработки предыдущей. Однако мы можем изменить стратегию следующим образом: разобьем все данные на несколько групп и будем применять одно и то же действие ко всем данным внутри одной группы. Таким образом можно будет ввести их параллельную обработку. Результаты применения действия к группе данных легко могут быть просуммированы, и в силу центральной предельной теоремы распределение таких сумм будет близким к нормальному [12, 13].

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

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

я£(л) = м

Е

Ьх{о,в)Щв) (4)

называется байесовским риском, а соответствующая ей стратегия — байесовской [12].

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

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

В разработанном программном комплексе поиском минимаксных стратегии и риска, а также соответствующих потерь занимается программа с1етоШ. Соответствие полученной стратегии и ожидаемых потерь может быть проверено другой программой комплекса — с1ето1йе81.

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

Стратегия, описанная в предыдущей главе, выглядит следующим образом: на первых двух шагах используем первый и второй способ обработки по очереди. Далее выбор способа обработки для следующего шага определяется доходами от предыдущих шагов. После выполнения каждого шага мы получаем реакцию среды и по ней можем определить, какой способ обработки применить на следующем. Разобьем получаемые реакции среды на группы. Размеры групп обозначим как М{, где г € [0, к], к + 2 — количество групп. Ограничения на размеры групп введем следующие: первые две группы должны быть одинакового размера Мо, и сумма размеров всех групп равна первоначальному количеству реакций системы: 2М0 + + М2 Н-----V Мк = N.

Таким образом, от обработки с одинаковыми (возможно единичными) размерами групп мы переходим к обработке с различными размерами групп. При этом стратегия подразумевает применение одинакового способа обработки внутри каждой группы. Поскольку мы не можем менять способ обработки внутри группы, все шаги могут быть обработаны одновременно. При этом общее количество этапов обработки составит к + 1 вместо N.

Положим пх\ = и+у, тп2 = и—у, тогда в = (и+у,и—у), в = {в : |г>| < с}. В новых переменных асимптотически наихудшая плотность распределения имеет вид иа(и,у) = ка(и)р(у), где ка(и) — постоянная плотность при |и| < а; р(у) = р{—у) — симметричная плотность; а —> оо. Соответствующий байесовский риск [И]:

ЬК(а, (и + у, и — и))г/а(и, у)йийу (5)

Дадим рекуррентное уравнение для вычисления байесовского риска, соответствующего стратегии параллельного управления.

Теорема 1. Пусть иа(и,у) = ка(и)р(у), где па(и) постоянная плотность при \и\ < а, плотность р(у) = р(—у) — симметрическая на отрезке \у\< с и а оо. Тогда справедливо рекуррентное уравнение:

= ^(0), (6)

где Я1п1пЛ^) = Яп1пЛ2) = 0 при т+п2 = N.

£1п2(г) = Ма№.„2(г) + п.217+ г)Кгм< (Щ^А ¿г, = Мц$.п,{г) + пг1 тЯп^шАг + Фп2,м< (^г21) &

— ОС

при «1 + п2 = 2Мо Н-----1- М;_ь «1 > Л/о, я2 > М0. Здесь

... 00

= / 2г)дПьП2(2', (-1)«+1г,)р(«)^ £=1,2,

«^(Я, „) = (2™^, + п2))"!/2 ехр (-Вта) ' (8)

= (Йж)1/2 ехр (-да+м)) • При этом байесовский риск вычисляется по формуле

00 оо

(9)

О -ос

Поиск осуществляется для заранее заданных значений Л/,-. Находить риски и стратегии для таких распределений — одна из возможностей программы с1етоТ131ер1, входящей в состав комплекса программ. Также она может находить ожидаемые потери для таких стратегий. Тестирование параллельных стратегий с разными размерами групп при помощи метода Монте-Карло — еще одна функция программы ёетоШев!.

Исследование влияния размеров групп данных на минимаксный риск показало, что различным разбиениям на группы будут соответствовать различные минимаксные стратегии и риски. Возникает закономерная цель — найти такое разбиение, минимаксный риск для которого минимальный. При этом к будем считать фиксированной константой и М; > 0 для 0 < г < к, то есть менять будем только размеры групп данных, но не их количество.

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

Нт Я%{иа{и,у)) = 4М0

ур(у)ёу -

Прямой перебор в описанном алгоритме возможен для одного параметра благодаря небольшим рассматриваемым значениям N. Начало оптимизации с М0 обусловлено тем, что данное значение сильно влияет на потери (показывает, сколько раз должен быть обязательно применен худший способ обработки). Однако, даже в самом худшем варианте, если не учитывать сложность нахождения минимаксного риска, данный алгоритм имеет линейную сложность от N при фиксированном к. Главная сложность состоит именно в вычислении минимаксного риска для конкретного разбиения (текущий применяемый алгоритм уже имеет сложность 0(N3)). Итоговая сложность предлагаемого алгоритма поиска оптимального разбиения: 0(Лг4).

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

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

В третьей главе описаны идеи получения упрощенных стратегий на основе полученных минимаксных.

Стратегии, найденные при помощи описанных в предыдущих главах рекуррентных формул, имеют пороговый характер и могут быть представлены при помощи треугольной матрицы. Это верно как для стратегий с равными размерами групп, так и для стратегий с различными.

Номер строки и столбца в матрице, описывающей стратегию, будет обозначать количество сделанных шагов, на которых были выбраны первое и второе действие соответственно. Для того, чтобы определить, какое действие необходимо выбрать на данном шаге, используется значение Z = Х\П2 — Х2Щ, где Xi — суммарный доход, полученный за все шаги, на которых было выбрано i-e действие, щ — количество шагов, на которых было выбрано i-e действие. Значение элемента матрицы — это пороговое значение, если оно меньше Z для текущего состояния, стратегия предписывает выбирать первое действие, в противном случае — второе.

Для визуализации данная матрица может быть представлена в виде набора графиков (по одному графику для каждого значения щ +ггг). Для оси абсцисс можно выбрать ^/(щ + 712), для оси ординат: граничное значение Z. Можно нормировать графики по количеству шагов. В таком случае будем использовать t = ti + í2 для именования графиков, ti/t и T(ti,t2) = Z ■ N~3¡2 для координатных осей, здесь í,- = n¿/N. График будет задан набором точек, определяемых пороговыми значениями Z для соответствующей диагонали матрицы.

Лемма 1. Выполняются следующие равенства: Rn}.n2{Z) = R^}.ni{~Z) и Rn¡,n3(Z) = RnlUi(—Z), где R^l,¡2(Z) — потери в случае, если при данных значениях тгь n2, Z будет выбрано сначала 1-е действие, а затем управление

будет вестись оптимально.

Будем использовать представление в виде набора графиков и лемму 1 для получения упрощенных стратегий. Из леммы 1 следует, что каждый график симметричен относительно точки (0,5; 0).

Далее зададим следующее ограничение: будем искать стратегии, которые могут быть табулированы не более чем двумя точками для каждого значения t (таким образом, каждый график будет содержать не более пяти точек). Такое ограничение выбрано из соображений неплохих получающихся результатов для рассматриваемых, небольших значений N. Также причиной выбора именно таких ограничений является форма всех полученных стратегий (из графика видно, что трех точек обычно достаточно, чтобы построить хорошее приближение). Пример графика такой приближенной стратегии показан на рисунке 1 пунктирной линией. Сплошной линей показана часть си.мметричного графика точной стратегии.

Рис. 1. Сравнение точной стратегии и упрощенной методом «На основе суммы квадратов отклонений от графика точной стратегии»

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

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

1. «На основе суммы квадратов отклонений от графика точной стратегии».

2. «На основе потерь от применения стратегии».

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

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

Критерием оптимизации для упрощенной первым с стратегии будет являться сумма квадратов отклонений от точного графика. При этом нас интересует только отклонения в тех точках, где стратегия действительно используется, т. е. для таких х, где х > 0,5; х = ^/(щ + гг2); при этом щ + тг2 для заданного графика является константой.

Обозначим через х\, у[ точки, определяющие график упрощенной стратегии, а через а — искомый угол наклона. Первая точка упрощенной стратегии заранее известна: Хд = 0,5; уд = 0. Более того, нам интересен только угол наклона получившегося графика упрощенной стратегии, поэтому мы можем выбрать, например, х\ = тах(хг- €Е [0,5; 1]). Таким образом, нам необходимо найти только оптимальное значение для у[. Чтобы не усложнять формулы будем искать значение а:

Ег,е[0,5;:1] Уг(х1 хо) а = Г (х-х')1- (10)

Далее можно найти у[ = а{х\ — Хд).

Вторая модификация предложенного метода будет использовать для определения упрощенной стратегии уже три точки. При этом координата х\ может быть выбрана как х[ = (хтах — 0,5)/2, где хтах — максимальное значение абсциссы среди точек точной стратегии. Выберем х\ = тах(г,; £ [0,5; 1]). Будем оптимизировать уже две переменные: а и /3, где /3 — угол наклона графика для участка после х\.

Минимизируя сумму квадратов отклонений упрощенной стратегии от точной, получим следующие значения для а и ¡3:

= Е^е[0,5;х;] У*{хг ~ 4) + Ет^х?;!] ~ ~ Х\)){Х\ ~ до)

Е,,£;«.Г,:,;;(.'', - 4)2 + Е.,^!]«^ - хо)2 - - - хг0)У (1 }

/3 = 5х - а¿2,

(12)

где

52 =

51 =

■г>2 '

(13)

(14)

Когда мы нашли оптимальные значения для а и ¡3, мы можем найти необходимые координаты у[ и

У первого метода есть также третья модификация, в которой появляется третья переменная для оптимизации: х[. При помощи формул (11) и (12) мы можем найти оптимальные а и (5 для любого фиксированного х\. Само же значение х\ принадлежит промежутку (0,5; хг2) и может быть оптимизировано при помощи какого-либо численного метода одноппараметрической оптимизации.

Следует также обратить внимание на то, что, при использовании описанного выше метода, стратегия для каждого шага (значения п1 + будет упрощаться независимо. Это позволяет очень сильно упростить задачу по упрощению стратегии, но также потенциально ухудшает ее результат.

Метод «На основе потерь от применения стратегии» отличается тем, что он использует точную стратегию только как отправную точку для поиска упрощенной стратегии. Метод заключается в численной оптимизации параметров а, ¡3, х\ каким-либо методом многопараметрической оптимизации. При этом для данного метода в качестве критерия оптимизации используется значение потерь, вычисленное при помощи рекурсивных формул аналогичных (6) - (9) по упрощенной стратегии. Этот метод требует больше вычислений из-за увеличения размерности задачи оптимизации (3 • {Ы — 2) переменных). Такой метод интересен также в том смысле, что позволяет проверить существование стратегии, отвечающей заданным ограничениям и имеющей меньшее значение минимаксного риска, чем у найденной при помощи предложенных в предыдущих главах методов минимаксной стратегии.

Поиск упрощенных стратегий — задача программы demoRoughStrategy. В данной программе реализованы описанные методы поиска упрощенных стратегий, при этом для метода «На основе потерь от применения стратегии» реализован поиск упрощенной стратегии методом покоординатного спуска и градиентным методом. Применение полученных стратегий можно смоделировать при помощи программы с1етоШез1.

Для N = 15 получены следующие результаты: для того, чтобы табулировать точную стратегию, потребуется хранить 42 точки (с учетом симметричности стратегий). Для того, чтобы табулировать упрощенную стратегию, потребуется 26 точек (или 13 точек в случае простого аналитического метода). Разница между потерями для точной и упрощенных стратегий при моделировании методом Монте-Карло не превышала 0,8%.

Для N = 30 получены следующие результаты: для того, чтобы табулировать точную стратегию, потребуется хранить 197 точек (с учетом симметричности стратегий). Для того, чтобы табулировать упрощенную стратегию, потребуется 56 точек (или 28 точек в случае простого аналитического метода). Разница между потерями для точной и упрощенных стратегий не превышала при моделировании 0,9%.

В Заключении представлены результаты исследования параллельной обработки данных.

Заключение

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

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

Основная часть работы посвящена параллельной обработке с различными размерами одновременно обрабатываемых групп. Исследована проблема формирования оптимальных размеров групп данных для минимизации минимаксного риска. Разработан алгоритм для нахождения оптимальных размеров групп. Произведено численное моделирование полученных стратегий, представлены результаты этого моделирования.

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

Разработан комплекс программ, в который входят программы, позволяющие:

1. Находить минимаксные стратегии и риски для обработки с одинаковыми размерами групп.

2. Находить минимаксные стратегии и риски для обработки с различными размерами групп.

3. Получать упрощенные стратегии на основе минимаксных.

4. Проводить численное моделирование применения всех получаемых видов стратегий.

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

Список публикаций в изданиях, рекомендованных ВАК РФ

1. Колногоров А. В., Олейников А. О. Оптимизация параллельной многоэтапной обработки в случайной среде // Вестник НовГУ. 2012. № 68. С. 67-69.

2. Олейников А. О. Численная оптимизация параллельной обработки в стационарной случайной среде // Труды КарНЦ РАН. 2013. Т. 1. С. 73-78.

Список публикаций в других изданиях

3. Олейников А. О. О робастном управлении в случайной среде // Материалы докладов аспирантов, соискателей, студентов: XIX научная конференция преподавателей, аспирантов и студентов НовГУ 2-7 апреля 2012 года. Часть 2. 2012. С. 78-80.

4. Колногоров А. В., Олейников А. О. О робастном управлении в случайной среде. Деп. в ВИНИТИ № 317-В2011 от 01.07.2011. С. 17.

5. Олейников А. О. Получение упрощенных стратегий для параллельной обработки в случайной среде численными методами // Обозрение прикладной и промышленной математики. 2013. Т. 20, вып. 4. С. 565.

6. Олейников А. О. Способы получения упрощенных стратегий для параллельной обработки в случайной среде // Обозрение прикладной и промышленной математики. 2013. Т. 20, вып. 2. С. 149.

7. Олейников А. О., Колногоров А. В. Численная оптимизация групп данных для параллельной обработки в стационарной случайной среде // Труды 55-й научной конференции МФТИ. Управление и прикладная математика. 2012. Т. 1. С. 92-93.

8. Колногоров А. В., Олейников А. О. Оптимизация параллельной многоэтапной обработки в случайной среде // Обозрение прикладной и промышленной математики. 2012. Т. 19, вып. 2. С. 210-211.

9. Олейников А. О., Колногоров А. В. Получение упрощенных стратегий для параллельной обработки в случайной среде с различными размерами групп //

Труды 56-й научной конференции МФТИ. Управление и прикладная математика. 2013. Т. 1. С. 84-85.

10. Программа поиска оптимальных размеров групп данных для параллельной обработки // Свидетельство о государственной регистрации программы для ЭВМ. № 2013614359 от 29.04.2013.

11. Колногоров А. В., Олейников А. О. Оптимизация параллельной многоэтапной обработки в случайной среде // Вестник НовГУ. 2012. № 68. С. 67-69.

Цитированная литература

12. Колногоров А. В. Нахождение минимаксных стратегии и риска в случайной среде (задаче о двуруком бандите) // Автоматика и телемеханика. 2011. Т. 5. С. 127-138.

13. Колногоров А. В. Робастное параллельное управление в случайной среде (задаче о двуруком бандите) // Автоматика и телемеханика. 2012. Т. 4. С. 114-130.

Подписано в печать 27.06.2014. Печать офсетная. Усл.печ.л.1. Тираж 100 экз. Заказ № 450. Типография ООО «Литера», ИНН 5321015720 173003 Великий Новгород, ул. Большая Санкт-Петербургская,39