Метод крутого восхождения (Бокса-Уилсона)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего образования

«Севастопольский государственный университет»

 

МЕТОДИЧЕСКИЕ Указания

 

для изучения раздела «Оценка эффективности СМО на основе экстремального эксперимента»

по дисциплине «Теория систем»

для магистров очной и заочной форм обучения

специальности09.04.01

«Информатика и вычислительная техника»

 

Севастополь

УДК 517.85

Методические указания для изучения раздела «Оценка эффективности СМО на основе экстремального эксперимента» по дисциплине «Теория систем» для магистров очной и заочной форм обучения по специальности 09.04.01 «Информатика и вычислительная техника» / Сост.: И.А. Балакирева. – Севастополь: Изд-во СевГУ, 2016. – 24 с.

 

 

Целью методических указаний является оказание помощи студентам в изучении теории планирования эксперимента при выполнении курсовой работы по дисциплине «Теория систем». Методические указания также будут полезны студентам при выполнении ВКР магистра.

 

Методические указания рассмотрены и утверждены на заседании кафедры ИТиКС (протокол № ___ от ___ ______ 2016 г.)

 

Рецензент: к.т.н., доцент Брюховецкий А.А.

СОДЕРЖАНИЕ

 

 

Введение……………………………………………………………….........
1. Методы покоординатной оптимизации…………………….
2. Градиентные методы………………………………………………..
2.1. Суть градиентных методов………………………………………….
2. 2. Метод крутого восхождения (Бокса-Уилсона)………………………..
2.3. Алгоритм метода Бокса-Уилсона…………………………………...
3. Индивидуальные задания для определения оптимума отклика системы массового обслуживания на основании имитационного эксперимента……………..
4. СОДЕРЖАНИЕ ОТЧЕТА О ВЫПОЛНЕНИИ задания ………………
5. Пример выполнения задания…………………………………….
5.1. Постановка задачи. ………………………………………………….
5.2. Построение линейной регрессионной модели на основе ПФЭ…...
5.3. Реализация процедуры метода крутого восхождения (Бокса-Уилсона)… …………………………………………………………………………
Библиографический список………………………………………...
Приложение 1………………………………………………………………
Приложение 2………………………………………………………………
Приложение 3………………………………………………………………
Приложение 4………………………………………………………………

 

Введение

Во многих случаях инженерной практики перед исследователем возникает задача не только выявления характера связи между откликом объекта исследования и факторами объекта, но и определить такие численные значения этих факторов, при которых отклик (выходной параметр) достигает своего экстремального значения (максимума или минимума). Эксперимент, решающий эту задачу, называется экстремальным. В этом случае задача сводится к оптимизационной процедуре и формулируется следующим обра­зом: требуется определить такие значения факторов X *=(x *₁, x *₂,…, x * _n), при которых y (X *)=extr{ y (X)} для всех , где Φ ⁿ – допустимая область изменения значений факторов.

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

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

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

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

- методы покоординатной оптимизации;

- градиентный метод;

- метод крутого восхождения Бокса-Уилсона;

- симплекс-планирование и т.д.

 

1. Методы покоординатной оптимизации.

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

 

 

Рисунок 1. Процесс приближения к оптимуму отклика объекта исследования на основании покоординатной оптимизации.

 

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

 

2. Градиентные методы.

Суть градиентных методов.

Поиск экстремума поверхности отклика основан на свойствах градиента функции:

- направление градиента поверхности отклика есть направление максимального увеличения значений функции отклика в данной точке факторного пространства;

- в окрестности точки оптимума норма градиента близка к нулю.

В связи с этим при оптимизации процесса движение в факторном пространстве целесообразно совершать в направлении наиболее быстрого возрастания функции откли­ка, т.е. в направлении градиента функции y.

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

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

,

где i, j,…, k – единичные векторы в направлении координатных осей факторного пространства.

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

Рисунок 2. Процесс движения в направлении градиента в факторном пространстве.

 

Координаты точек в направлении градиента рассчитываются по каждому фактору , где xⁱ_j – уровень фактора x_j на i -м шаге, λⁱ_j – величина приращения фактора x_j на i -м шаге, - вычисленное новое значение фактора x_j.

Выбор приращений выполняются сначала для некоторой базовой переменной, создающей максимальное приращение в направлении градиента max{ b_j Δ x_j }= b_б Δ x_б, для этой переменной определяется величина шага h_б.

Размер и знак шагов движения λ_j для всех входных переменных могут быть вычислены по общей формуле

,

где λ_б и Δ x_j считаются всегда положительными, а b_j берется со своим знаком. Процесс приближения к экстремуму поверхности отклика представляет собой последовательность проведения ПФЭ или ДФЭ и построения линейных регрессионных моделей.

Рисунок 3. Процесс приближения к экстремуму функции отклика на основе градиентного метода.

 

В окрестности экстремума коэффициенты линейной регрессионной модели становятся незначимыми. Это может означать следующее:

- задача оптимизации решена, и лучшее значение отклика для текущего плана эксперимента считается точкой экстремума поверхности отклика;

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

 

Метод крутого восхождения (Бокса-Уилсона)

Метод Бокса-Уилсона является модификацией градиентного метода, но при реализации этого метода в направлении градиента выполняется несколько шагов (проводятся «мысленные» опыты) до тех пор, пока значение отклика возрастает (не ухудшается). При решении задачи минимизации функции отклика этот метод называют методом наискорейшего спуска.

Сущность этого метода рассмотрим на примере двухфакторной задачи (рисунок 4). В точке факторного пространства M₀ проводится полный факторный эксперимент, строится линейная регрессионная модель функции отклика и определяется направление градиента.

 

Рисунок 4. Процесс приближения к экстремуму функции отклика на основе метода Бокса-Уилсона.

 

Вдоль выбранного направления с определенным шагом осуществляется движение (точки 1,2,3,4,5) – проводятся «мысленные» опыты. "Мысленный" опыт заключается в по­лучении предсказанных (расчетных) значений функции отклика по ли­нейному уравнению регрессии, что позволяет сократить объем реальных опытов, т.е. увеличить скорость продвижения к экстремуму. При "мыс­ленном" эксперименте" перевод координат в кодированную форму и под­становка их в уравнение модели объекта должна подтвердить действи­тельное возрастание функции отклика. Обычно реальные опыты проводят через 2-4 «мысленных» опыта с целью проверить соответствие значение функции отклика, вычисленное на основании «мысленного» опыта и полученного на практике.

На рисунке 4 точка M ¹ – последняя среди точек на выбранного направления из точки M ⁰, в которых значение функции отклика увеличивается. Точка M ¹ становится центром нового факторного эксперимента, в результате которого строится новая линейная регрессионная модель и определяется новое направление градиента.

Поиск прекращается, когда градиент становится равным нулю, т.е. все коэффициенты b_j будут незначимыми.

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

При эффективном крутом восхождении возможны два исхода: область оптимума достигнута или область оптимума не достигнута.

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

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