На минимум

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 = ε /(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 определяет отрезок, в пределах которого формируется случайная точка.

Поиск по сайту: