ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Сжатие, использующее точку С

123 4

Если значения функции в точках R и W одинаковы, следует проверить другую точку. Возможно, значение функции меньше в точке М, но нельзя заменять вершину W точкой М, так как три точки должны составлять треугольник. Рассмотрим две средние точки С₁ и С₂, которые лежат на отрезках WM и MR соответственно (рис. 4.3).

Рис. 4.3. Сжатие точки С₁ или С₂ для метода Нелдера-Мида

Точку, в которой функция принимает наименьшее значение, обозначаем через С и получаем новый треугольник BGC.

Сокращение по направлению к В

Если значение функции в точке С не меньше, чем значение в W, точки G и W следует "стянуть" к точке В (рис. 4.4).

Рис. 4.4. Сокращение треугольника к точке В

Точку G заменяем точкой M, a W – точкой S, которая является средней точкой на отрезке, соединяющем точки В и W.

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

Алгоритм Нелдера-Мида

1. Задать начальный симплекс, вычислить значения ЦФ в вершинах симплекса, выбрать вершины B, W, G.

2. Если выполнены условия окончания поиска, то объявить точку B минимумом и перейти на 500

3. Выполнить операцию отражения для получения вершины R.

4. Если f(R) < f(G), то перейти на 5 (отражение, либо растяжение)

Иначе перейти на 6 (сжатие либо растягивание)

5. Если f(B) < f(R) то заменить W на R,

иначе вычислить Е и f(E),

Если f(E) < f(B) то замена W на Е

иначе замена W на R.

Перейти на 2

6. Если f(R) < f(W) то

замена W на R

Вычислить С = (М+ R)/2 или С = (М+ R)/2 и f(С)

Если f(С) < f(W) то замена W на С

иначе вычислить S и f(S)

замена W на S, замена G на M

Перейти на 2.

7. Конец алгоритма

Поиск минимума ЦФ завершается, когда размеры симплекса или разность между значениями в вершинах симплекса становятся достаточно малыми. Часто используют дисперсия

где – значения ЦФ в вершинах симплекса, – среднее значение ЦФ в вершинах симплекса

Выполнение условий окончания поиска соответствует либо малому ребру симплекса, либо попаданию стационарной точки внутрь симплекса, либо одновременному выполнению обоих условий.

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

Метод Хука-Дживса

Данный метод один из наиболее простых прямых методов поиска (1960 г). Метод использует попеременно исследующий (зондирующий) поиск и поиск по образцу (модельный ход).

1. Исследующий поиск позволяет из текущей точки пространства выбрать направление, движение в котором обеспечивает минимизацию целевой функции.

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

Алгоритм Хука-Дживса

1. Ввести начальные значения: - начальная базисная точка; – шаг изменения переменной; - минимальное значение шага; < 1 – константа изменения длины шага

2. Вычислить значение ЦФ в базисной точке

3. Выполнить исследующий поиск в точке , получить новую базисную точку и значение ЦФ в этой точке, .

4. Если (значение ЦФ уменьшилось), перейти на => 8

5. Выполнить поиск по образцу, используя новую базисную точку ,

6. Выполнить исследующий поиск в т. , получить точку и значение ЦФ .

7. Если , определить новую базисную точку: присвоить ; ; , перейти на => 5.

8. Если , то уменьшить длину шага, , перейти на => 3.

9. Закончить поиск, печатать результаты.

Окончание поиска происходит при условии, что длина шагов (минимального заданного значения)

Исследующий поиск метода Хука-Дживсасодержит такие шаги:

1. Вход: базисная точка , значение ЦФ ;

Задать начальное значение счетчика итераций k = 1 и начальное значение шага переменой h.

2. Увеличить координату на шаг :

(для k =1 будет )

Вычислить значение функции

3. Если , перейти на => 7

4. Уменьшить координату на шаг :

(для k = 1 )

5. Если , перейти на => 7

6. Если не достигнуто уменьшения ЦФ, оставить без изменений, и перейти на => 8.

7. Запомнить новые значения и .

8. Если не все переменные использованы, т.е. , то перейти к следующей переменной, , и перейти на => 2, иначе закончить поиск, перейти на => 9

9. Конец исследующего поиска. Получена новая базисная точка и значение ЦФ .

Достоинства алгоритма Хука-Дживса:

- используются простые операции, не приводящие к запрещенным арифметическим действиям (типа деления на 0);

- не высокие требования к памяти компьютера

Недостатки алгоритма:

- исследующий поиск выполняется только в направлении осей координат, что может привести к прекращению поиска без достижения минимума, если направление «оврага» не параллельно осям координат;

- большое количество вычислений целевой функции.

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

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

123 4