Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1


НазваниеУкрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1
страница4/9
Дата публикации06.05.2013
Размер1.03 Mb.
ТипЗакон
userdocs.ru > География > Закон
1   2   3   4   5   6   7   8   9
Рисунок 3.14 – Графическая интерпретация метода Пауэлла


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

Метод наискорейшего спуска – один из методов с переменным шагом (рисунок 3.15). Шаг выбирается с учетом степени изменения функции в направлении поиска:

Hi = h Si Gi,

где i – номер переменной; Hi – шаг поиска; h – относительный шаг поиска; Si – шкальность изменения переменных; Gi – значение антиградиента функции по хi. Шаг Hi остается постоянным до тех пор, пока значение функции убывает (растет).

Рисунок 3.15 – Графическая интерпретация метода наискорейшего спуска


Шкальность определяется зависимостью Si = (xн – xв )i bш , где xн, xв – соответственно принятая нижняя и верхняя граница интервала поиска; bш – коэффициент, определяющий шкальность по переменным.

Имеется ряд методов оптимизации на основе случайного поиска. Ниже приведен алгоритм метода случайного поиска с пересчетом. В алгоритме приняты обозначения: r – псевдослучайные числа в интервале от 0 до 1.0; Si – шкальность изменения xi ; Xт = {xтi} – текущее значение X; Xп = {xпi} – текущее приближение к решению X.


Методы решения задачи одномерной безусловной оптимизации.

Унимодальной называется функция, имеющая один экстремум.

Задача поиска экстремума сводится к нахождению значения хо, соответствующего максимуму или минимуму f(x).

Алгоритм численного метода или метода случайного поиска экстремума может быть рассчитан на нахождение максимума или минимума. Для нахождения противоположного вида экстремума, например, максимума по алгоритму на минимум, необходимо значения оптимизируемой функции f(x) умножить на (-1).

Для аналитического метода, в случае дифференцируемости функции f(x) находим

f'(x) = 0. Решение полученного уравнения дает оптимальное значение хо. Затем вычисляем f''(хо). Если f''(хо) > 0, то имеем минимум; и если f''(хо) < 0, то максимум (рисунок 3.1).




f(x)

1

2


хо x
f '(x)


2

x

1

f ''(x)

2

x
1

Рисунок 3.1 – Графическая интепретация поиска эстремума дифференцируемой функции
Из приведенной графической интерпретации метода следует, что функция (1) имеет максимум и функция (2) – минимум.

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

Метод дихотомии (половинного деления) является одним из методов одномерной безусловной оптимизации унимодальной целевой функции. Алгоритм метода основывается на выборе исходного отрезка поиска решения [a, b] и его последующем делении пополам:

1) xc=(b+a)/2;

2) x1 = xc - /2; x2 = xc + /2;

3) Если при минимизации f(x1) < f(x2), то b = xс, иначе a = xс.

4) При b - a <= , xопт = ( b + a)/2, где  – точность поиска экстремума. Иначе на п. 1.
Ниже приведена графическая интерпретация (рисунок 3.2) и один из алгоритмов метода дихотомии (рисунок 3.3).
f(x)


f(x2)

f(x1)


a x1 xс x2 b х

Рисунок 3.2 – Графическая интепретация метода дихотомии
1

Пуск

2

Ввод a, b,  a и b – текущие значения нижней и верхней

границ интервала поиска экстремума

 – точность поиска

3 4

xс= (a+b)/2 b-a≤ Да 11 Zп – значение

Zп= f(xс) целевой

функции

5 Нет 12 для решения

i = 1, 2 Вывод xc, Zп,

6 13

x1 = xс +(2i-3) /2 Останов


7
Z1= f(x1)

на минимум

8 Да

Z1< Z2

Нет

9 10

a = xc b = xc Рисунок 3.3. Схема алгоритма программы по

методу дихотомии

Метод золотого сечения основан на делении отрезка [a, b] по правилу золотого сечения, когда отношение большего отрезка к меньшему const. Такое отношение определяется выражением (-1)/2=0.62. При этом методе в отличие от метода дихотомии на каждой итерации требуется расчет только одного значения целевой функции. В результате находится решение xп и соответствующее ему значение целевой функции Zп (рисунки 3.4, 3.5).

На минимум:

f(x)

f(x2)

(1-k)(b-a)

f(x1) k( b-a)




a x1 x2 b x
Рисунок 3.4 – Графическая интепретация метода золотого сечения
1

Пуск

2

Ввод a, b,  a и b – текущие значения нижней и верхней

границ интервала поиска экстремума

 – точность поиска

3

k= (-1)/2

4
i = 1

5 13

11 Да 15

x1 = a +(1-k)(b-a) abs(x2-x1)< xп = (x2+x1)/2
6 Нет 16

Z1 = f(x1) на минимум 10

Нет 12 Zп = f(xп)

Z1 < Z2

7

Нет Да 17

i=1 13 Вывод xп , Zп
8 Да b= x2 : x2 = x1

Z2 = Z1

i = 1 14 18

a= x1 : x1 -= x2 5 Останов

9 Z1-= Z2

x2 = a + k (b-a)
10

Z2 = f(x2) 12

Рисунок 3.5. Схема алгоритма программы по методу

золотого сечения

Метод Фибоначчи основан на делении отрезка [a, b] с использованием чисел Фибоначчи, представляющих ряд, у которого последующее число равно сумме двух предыдущих (1,1,2,3,5,8 и т.д.).
Шаговые методы основаны на том, что текущему приближению к решению xп на каждом новом шаге дается приращение h как xп=xп+h и вычисляется f(xп). Если новое значение целевой функции "лучше" предыдущего, то переменной x дается новое приращение. Если функция "ухудшилась", то поиск в данном направлении завершен.

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

Графическая интепретация и алгоритм поиска экстремума функции на основе поразрядного приближения приведены на рисунках 3.6, 3.7.

f(x)


f(xп+h)

f(xп) На минимум
xп xп+h x

Рисунок 3.6 – Графическая интепретация метода поразрядного приближения
1

Пуск

2

xп, h, a, xп и h – текущие значения соответственно приближения

к решению и шага поиска; a – коэффициент

изменения шага поиска;  – точность поиска решения

3
Z = f(xп)

4

Zп = Z

5
xп = xп + h


6
Z= f(xп)
на минимум

7

Z < Zп Да


Нет
8 Нет 9

abs(h)< h = - a h

Да

10 11 Рисунок 3.7 – Алгоритм поиска

Вывод xп-h, Zп Останов экстремума по методу поразрядного

приближения

Метод квадратичной интерполяции-экстраполяции является одним из методов аппроксимации кривыми и базируется на приближении целевой функции квадратичной параболой по трем точкам – текущее приближение x1= xп и точки, лежащие от нее слева x0 и справа x2 на удалении h и нахождении экстремума аналитически. Процесс проводится до тех пор, пока предыдущее и последующее приближения различаются более, чем на заданную точность поиска. Алгоритм метода следующий (рисунок 3.8 , 3.9):

1. находим x0 = xп - h ; y0 = f(x0); x1 = xп ; y1 = f(x1); x2 = xп + h; y2 = f(x2);

2. находим параметры параболы, проходящей через три выбранных точки

a = (yo- 2y1 + y2) / (2h2) ;

b = (-yo (2x1 + h) + 4y1 x1 - y2 (2x1 - h)) / (2h2);

Тогда очередное приближение x на основе аналитической оптимизации аппроксимирующей функции равно xп = - b/( 2a);

3. проверяем условие : abs(xп - x1) < .

Если выполняется, то оптимум найден. Иначе переходим к 1-му пункту алгоритма.
На минимум:

f(x)







f(x)=ax2+bx+c
f(xп+h)

f(xп-h)

f(xп)





xп-h xп xп+h x

Рисунок 3.8 – Графическая интепретация метода на основе квадратичной аппроксимации
1

Пуск


2

Ввод xп, h,  xп – текущее значение приближения

к решению; h – параметр интервала

9 аппроксимации;  – точность поиска

4 7

a = ...

b = ...
8

5

xi = xп +(i-1) h xп = -b/(2a)


6 9 Нет

abs(x1- xп)< 4

yi= f(xi)

Да

10

Zп= f(xп)
11 Рисунок 3.9 – Алгоритм на основе

Вывод xп, Zп квадратичной аппроксимации


12

Останов


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

Повторение испытаний описывается формулой Бернулли (биноминальным распределением)

, k = 0, 1, 2, ..., n,

где k – число благоприятных случаев;

n – общее число испытаний;

p – вероятность благоприятного исхода при одном испытании;

q – вероятность, противоположная p (q=1-p) .

Вероятность, что событие наступит n раз

;

что не наступит ни разу

;

наступит хотя бы один раз

.
Если абсолютную точность поиска решения на участке (b - a) обозначить через ε, то вероятность решения при одном испытании p = ε/(b - a). При этом вероятности Р1 получения решения в зависимости от числа испытаний n при различных p приведены в таблице 3.1.
Таблица 3.1 – Оценка точности поиска

p

n

p1

0.1

10

20

50

100

0.651

0.878

0.995

0.99999

0.01

100

200

500

1000

0.634

0.866

0.993

0.99996

0.0001

10000

20000

50000

100000

0.632

0.865

0.993

0.99996


Например, если p = ε /(b - a)=0.01, то вероятность получения решения с точностью ε при числе испытаний n = 100 равна 0.634; при n =200 – 0.866; при n = 500 – 0.993; при n = 1000 – 0.99996, т.е. требуется 10 (b - a) /ε испытаний для надежного решения (Р1> 0.9999) с заданной точностью ε. Аналогичная зависимость, как видно из таблицы, имеет место и при других точностях решения.

Имеется большое множество методов оптимизации на основе случайного поиска и их разновидностей. Ниже приведена иллюстрация простейшего метода поиска, состоящая в последовательном формировании на отрезке от a до b случайным образом расчетной точки xт, расчете в ней целевой функции f(xт), сравнении значения функции f(xт) и ранее найденного "лучшего" значения функции f(xп), присвоении xп =xт и f(xп) =f(xт), если текущая точка "лучше". Формирование случайной точки производится по выражению xт = a + r (b-a), где r – случайное число, равномерно распределенное в интервале от 0 до 1.0.
f(x)


f(xт)
f(xп)
a xп xт b x

Рисунок 3.10 – Графическая интепретация метода случайного поиска (на минимум)

Более эффективным является метод случайного поиска с пересчетом, алгоритм которого приведен на рисунке 3.11. Принимаемые значения показателей aш, bш, h и L должны находится в определенном соотношении, например начальные значения могут быть приняты bш = 2 ; h= bш /5 ; aш = 0.25 ; L=10. Формирование случайной расчетной точки xт (блок 9) производится относительно текущего приближения xп на основе использования случайных чисел r, равномерно распределенных в интервале от 0 до 1.0. Произведение sh определяет отрезок, в пределах которого формируется случайная точка.


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

Пуск

2

Ввод a, b,  a и b – начальные значения нижней и верхней

границ интервала поиска экстремума;

 – относительная точность поиска

3

h, L, aш ,bш h –относительный шаг поиска; L – граничное число

неудачных попыток; aш и bш – соответственно

коэффициенты уменьшения шага поиска и

определения шкалы поиска

4
s = (b - a)/ bш

5

xт = (a+ b)/ 2 xт – текущая расчетная точка

xп= xт xп – текущее (начальное) приближение к решению

6

Z = f(xт)


7 на минимум

11 15

Zп = Z Zп > Z Да xп = xт : Zп= Z
15,18

8

k = 0 12 8

k = k + 1

9

xт = xп+ s h (2 r -1) 13

Да 13

k <= L

10 9

Z = f(xт) 14 Нет

h = h aш
18 Да

17

8 xп , Zп, h h >=  aш


Нет

19
Вывод xп , Zп
20

Останов
Рисунок 3.11 – Алгоритм одномерного случайного поиска с пересчетом

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

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

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

функция Розенброка



Хп = (1;1);
функция Пауэлла



Хп = (0;0;0;0);
двумерная экспоненциальная функция :

,

при k = 1 Хп = (1;10).

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

Метод наискорейшего спуска – один из методов с переменным шагом (рисунок 3.15). Шаг выбирается с учетом степени изменения функции в направлении поиска:

Hi = h Si Gi,

где i – номер переменной; Hi – шаг поиска; h – относительный шаг поиска; Si – шкальность изменения переменных; Gi – значение антиградиента функции по хi. Шаг Hi остается постоянным до тех пор, пока значение функции убывает (растет).

1   2   3   4   5   6   7   8   9

Похожие:

Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКурс «Статистические методы управления качеством» специальность 200503...
Особенности эмпирических данных. Случайные величины. Распределения случайных величин. Статистические гипотезы
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКоллоквиум 2 тв и мс
Числовые характеристики случайных величин: математическое ожидание (понятие, свойства)
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон больших чисел
Корреляционная матрица случайного вектора. Коэффициент корреляции двух случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconАвтокорреляция случайного возмущения. Причины. Последствия
Алгоритм теста Голдфелда-Квандта на наличие (отсутствие) гетероскедастичности случайных возмущений
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон распределения Пуассона и его характеристики
Локальная предельная теорема Муавра-Лапласа. Теорема Пуассона Понятие случайной величины. Виды случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗачет Казаринова Ирина Николаевна Старовойтова Ольга Рафаэльевна...
Методология, методика, программа, метод, алгоритм исследования, парадигма, научная традиция
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 icon2: Элементы векторной алгебры
Различают понятия величин, которые характеризуются од -ним числом скалярные величины (например: масса, объём, длина, площадь и т...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconНа рисунке 1 приведен график зависимости скорости движения тела от...
Чему равно отношение силы гравитационного взаимодействия, действующей со стороны Луны на Землю, к силе гравитационного взаимодействия,...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЧто такое метрология?
Размерность качественная характеристика физических величин. Правила определения размерности производных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconПрограмма учебного курса «Физическая география России»
В конце программы приведен перечень экзаменационных вопросов за все три семестра: два на 4 курсе и 1 на пятом курсе см!!!
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница