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

Z < Z_п Да

 

 

Нет

 

8 Нет 9

abs(h)<e h = - a h

 

 

Да

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

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

приближения

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

1. находим x₀ = x_п - h; y₀ = f(x₀); x₁ = x_п; y₁ = f(x₁); x₂ = x_п + h; y₂ = f(x₂);

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

a = (y_o- 2y₁ + y₂) / (2h²);

b = (-y_o (2x₁ + h) + 4y₁ x₁ - y₂ (2x₁ - h)) / (2h²);

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

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

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

 

На минимум:

f(x)

 

 

f(x)=ax²+bx+c

 

f(x_п+h)

f(x_п-h)

f(x_п)

 

 

 

x_п-h x_п x_п+h x

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

 

1

Пуск

 

 

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

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

 

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

4 7

a =...

b =...

 

x_i = x_п +(i-1) h x_п = -b/(2a)

 

 

6 9 Нет

abs(x₁- x_п)<e 4

y_i= f(x_i)

Да

 

Z_п= f(x_п)

 

11 Рисунок 3.9 – Алгоритм на основе

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

 

Останов

 

 

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

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

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

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

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

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

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

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

;

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

;

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

.

 

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

 

Таблица 3.1 – Оценка точности поиска

p	n	p1
0.1		0.651 0.878 0.995 0.99999
0.01		0.634 0.866 0.993 0.99996
0.0001		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) /ε испытаний для надежного решения (Р₁> 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 определяет отрезок, в пределах которого формируется случайная точка.

 

76.Оптимизация при наличии ограничений случайным поиском

Метод прямого учета ограничений успешно может быть применен при реализации методов случайного поиска (рисунок 3.17). Для прямого учета ограничений достаточно в подпрограмме расчета целевой функции присваивать, если хотя бы одно из ограничений нарушено, бесконечно большое (при минимизации) или бесконечно малое (при максимизации) значение. При этом данное испытание при случайном поиске не должно учитываться счетчиком неудачных проб. Если ни одно из ограничений не нарушено, то вычисляется реальное значение целевой функции.

Например, на Бейсике подпрограмма без учета ограничений и с учетом ограничений будет при оптимизации на минимум следующей:

m1: ' п/п вычисления Z без учета ограничений Z= … Return

m1: ' п/п вычисления Z с учетом ограничений if (ограничение 1 нарушено) then m2 if (ограничение 2 нарушено) then m2 ……….. if (ограничение n нарушено) then m2 Z= …:goto m3 m2: Z= 1E20 m3: return

Пуск

 

Ввод m, e m – число оптимизируемых переменных;

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

 

Ввод x_нi,x_вi, x_нi и x_вi – соответственно нижняя и верхняя

начальные границы поиска оптимума

 

Ввод h, a_ш ,b_ш, l h –относительный шаг поиска; l – предельное

число неудачных попыток по каждой переменной;

5 a_ш и b_ш – соответственно коэффициент уменьшения

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

L = l ^m

 

 

 

s_i = (x_вi - x_нi)/ b_ш

 

 

8 на минимум

 

x_тi = (x_вi + x_нi)/2 15 16

x_пi= x_тi Z_п > Z Да x_пi = x_тi,

Z_п= Z

 

Нет

9 17 11

Z = f(X_т) k = k + 1

 

 

18 Да

_· Z_п = Z k <= L 12

 

Нет

11 19

k = 0 16,21 h = h a_ш

 

 

12 18 20 Да 21

i = 1, m h >= e a_ш Вывод x_пi,

Z_п, h

Нет

13 22

x_тi = x_пi + s_i h (2 r -1) Вывод Z_п,x_пi, 11

 

 

14 Останов

Z = f(X_т)

Рисунок 3.17 – Алгоритм многомерной оптимизации

случайным поиском с пересчетом

 

 

77.Одномерная безусловная оптимизация по методу дихотомии

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

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

2) x₁ = x_c - e/2; x₂ = x_c + e/2;

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

4) При b - a <= e, x_опт = (b + a)/2, где e – точность поиска экстремума. Иначе на п. 1.

Ниже приведена графическая интерпретация (рисунок 3.2) и один из алгоритмов метода дихотомии (рисунок 3.3).

 

f(x)

 

f(x₂)

f(x₁)

 

e

 

a x₁ x_с x₂ b х

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

 

1

Пуск

 

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

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

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

3 4

x_с= (a+b)/2 b-a≤e Да 11 Z_п – значение

Z_п= f(x_с) целевой

 

 

функции

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

 

i = 1, 2 Вывод x_c, Z_п,e

 

 

6 13

x₁ = x_с +(2i-3) e/2 Останов

 

 

 

Z₁= f(x₁)