Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. В минимуме светопоглощения
  2. Важность цены открытия для минимума или максимума дня
  3. Дивергенции "быков" класса В: цены опускаются к новому минимуму, а индикатор дает такой же глубокий минимум, что и предыдущий. Это самый слабый сигнал к покупке.
  4. Каждый треугольник образован двумя сближающимися линиями. Верхняя линия соединяет два или более максимумов, а нижняя два или более минимумов.
  5. Как выбрать сухой корм с минимумом углеводов.
  6. Классификация и необходимый минимум узлов, которые должен знать и уметь вязать (применять на практике) участник горного похода первой категории сложности
  7. Лексический минимум. Существительные второго склонения.

Z < Zп Да

 

 

Нет

 

8 Нет 9

abs(h)<e 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) < e.

Если выполняется, то оптимум найден. Иначе переходим к 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

Пуск

 

 

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

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

 

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

4 7

a =...

b =...

 

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

 

 

6 9 Нет

abs(x1- xп)<e 4

yi= f(xi)

Да

 

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). При этом вероятности Р1 получения решения в зависимости от числа испытаний 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) /ε испытаний для надежного решения (Р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 определяет отрезок, в пределах которого формируется случайная точка.

 

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

 

 

 

si = (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 + si h (2 r -1) Вывод Zп,xпi, 11

 

 

14 Останов

Z = f(Xт)

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

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

 

 

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

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

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

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

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

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

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

 

f(x)

 

f(x2)

f(x1)

 

e

 

a x1 xс x2 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 Вывод xc, Zп,e

 

 

6 13

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

 

 

 

Z1= f(x1)

 

 


Дата добавления: 2015-10-16; просмотров: 165 | Нарушение авторских прав


Читайте в этой же книге: Закон распределения Релея | Многоканальная разомкнутая система массового обслуживания | Многоканальная замкнутая система массового обслуживания | Транспортная задача линейного программирования | На минимум 1 страница | На минимум 2 страница | На минимум 3 страница | На минимум 4 страница | Задача о назначениях | РОЗДІЛ 1. ТЕОРЕТИЧНІ ОСНОВИ ФОРМУВАННЯ ПРАВИЛЬНОЇ ПОСТАВИ В МОЛОДШИХ ШКОЛЯРІВ |
<== предыдущая страница | следующая страница ==>
На минимум| На минимум

mybiblioteka.su - 2015-2024 год. (0.021 сек.)