86223 (612688), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Если данное условие не выполнено, возвращаемся к шагу 2.

2.2.3 Практическое применение прямых методов безусловной многомерной оптимизации

Пусть заданы следующие условия:

Тогда по методу циклического покоординатного спуска будет выполнен счет следующего вида:

Т. к. , будем двигаться в противоположную сторону по оси абсцисс с тем же шагом:

,

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

Результаты работы данного алгоритма представлены на рисунке 12. Листинг программы приведен в приложении Б.

Рисунок 12 - Решение поставленной задачи методом спуска

Перейдем к методу Хука-Дживса. Обозначим координаты начального вектора: .

Тогда, соответственно, угол направления движения

.

Найдем значения функции 4-х точек в окрестности начальной:

Минимальное значение функция принимает в точке2, поэтому движемся в заданном направлении 2 пока идет уменьшение функции до достижения указанной точности, в противном случае уменьшаем шаг

( ):

Конечный результат получен на ЭВМ за 36 итераций. Результат представлен на рисунке 13. Листинг программы приведен в приложении Б.

Рисунок 12 - Решение поставленной задачи методом спуска

2.2.4 Минимизация по правильному симплексу

Правильным симплексом в пространстве E_n называется множество из n + 1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.

В пространстве E₂ правильным симплексом является совокупность вершин равностороннего треугольника, в E₃ - правильного тетраэдра.

Если х⁰ - одна из вершин правильного симплекса в E_n то координаты остальных п вершин х¹,. ., хⁿ можно найти, например, по формулам:

(6), где

d₁ , d₂ ,

a- длина ребра. Вершину х⁰ симплекса, построенного по формулам (6), будем называть бaзовой. В алгоритме симплексного метода используется следующее важное свойство правильного симплекса. По известному симплексу можно построить новый симплекс отрaжением какой-либо вершины, например, х^k симметрично относительно центра тяжести х^c остальных вершин симплекса. Новая и старая вершины и х^k связаны соотношением:

, где x^c .

В результате получается новый правильный симплекс с тем же ребром и вершинами =2x^c - х^k, хⁱ, i= 0,. ., n, i k. Таким образом, происходит перемещение симплекса в пространстве Е_n. На рисунке 13 представлена иллюстрация этого свойства симплекса в пространстве Е₂.

Рисунок 13 - Построение нового симплексa в E₂ отрaжением точки х: a - нaчaльный симплекс х⁰, х¹, ; б - новый симплекс х⁰, х¹, ; центр отрaжения - точкa x^c = (х⁰+ х¹) /2

Поиск точки минимума функции f (x) с помощью правильных симплексов производят следующим образом. На каждой итерации сравниваются значения f (х) в вершинах симплекса. Затем проводят описанную выше процедуру отражения для той вершины, в которой f (х) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х⁰ старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.

Шаг 0. Выбрать параметр точности , базовую точку х⁰, ребро и построить начальный симплекс по формулам:

Вычислить f (х1 ^(0),x2 ⁽⁰⁾⁾.

Шаг 1. Вычислить значения f (х) в вершинах симплекса х¹,. ., xⁿ.

Шаг 2. Упорядочить вершины симплекса х⁰,. ., хⁿ так, что бы f (х1 ^(0),x2

⁽⁰⁾⁾ … f (х¹) f (х^n-1) f (хⁿ).

Шаг 3. Найти среднее значение функции:

.

Проверить условие из учета того, что:

(3.38)

Если оно выполнено, то вычисления прекратить, полагая х^* х⁰, f ^* f (x⁰). В противном случае перейти к шагу 4.

Шаг 4. Найти

и выполнить отражение вершины хⁿ. К примеру, для отражения вершины А следует найти точку

.

Тогда отраженная вершина будет иметь вид:

.

Если f (Е) n), то перейти к построению нового симплекса, иначе - перейти к шагу 5.

Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром (редуцирование), считая базовой вершиной х⁰. Остальные n вершин симплекса найти по формуле хⁱ = (хⁱ + х⁰) /2, i=1,. ., n. Перейти к шагу 1.

Геометрическая иллюстрация работы алгоритма в пространстве показана на рисунке 14, где точки х⁰, х¹, х² - вершины начального симплекса, а пунктиром указаны процедуры отражения.

Рисунок 14 - Поиск точки минимума функции с помощью правильных симплексов в пространстве

Замечания:

1. Следует иметь в виду, что если функция f (х) многомодальна, то описанным методом может быть найдена точка локального, а не глобального минимума f (х).

2. Если ограниченность снизу целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова.

2.2.5 Поиск точки минимума по деформируемому симплексу

Алгоритм, описанный в разд.2.2.4, можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. А именно, положение новой вершины вместо вершины хⁿ, соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках;

(7)

Геометрическая иллюстрация этих процедур для пространства E₂ приведена на рисунках 15 и 16.

Рисунок 15 - Пробные точки z¹,z²,z³,z⁴ для перехода к новому симплексу

Рисунок 16 - Новые симлексы, полученные в результате процедур сжатия (а, б); отражения (в); растяжения (г).

Так как величина (0;

1), то выбор точек z¹ и z² соответствует сжатию симплекса; 1, поэтому выбор точки z³ соответствует отражению, а > 1 и выбор точки z⁴ приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве E_n для n 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х⁰ E_n, по формулам

, (8)

где e ⁱ - i-й базисный вектор; - параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров , и для выбора пробных точек zⁱ в формулах (9): = 1/2, = 1 и =2.

Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.

Шаг 0. Выбрать параметр точности , параметры , и , базовую точку х⁰, параметр и построить начальный симплекс. Вычислить f (х⁰).

Шаг 1. Вычислить значения функции в вершинах симплекса х¹,..., xⁿ.

Шаг 2. Упорядочить вершины х⁰,..., xⁿ так, чтобы f (х⁰) … f (хⁿ).

Шаг 3. Проверить достижение заданной точности. Если оно выполняется, то вычисления завершить, полагая х * х⁰, f * f (х⁰). Иначе - перейти к шагу 4.

Шаг 4. Найти и пробные точки z^k, k=1, …, 4 пo формулам (9). Найти f (z^*) = min f (z^k). Если f (z*) < f (zⁿ). то положить xⁿ=z^* и перейти к шагу 2. Иначе - перейти к шагу 5.

Шаг 5. Уменьшить симплекс, полагая хⁱ = (хⁱ + х⁰) /2, i = 1,. ., n и перейти к шагу 1.

Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N шагов алгоритма из точки х⁰ снова строят симплекс, полагая а = ||x⁰-xⁿ||.

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

2.2.6 Практическая реализация симплексных методов

Пусть заданы следующие условия:

Для первой вершины:

Для второй вершины:

Для третьей вершины:

Наибольшее значение функция принимает в точке2, ее и будем отражать. Для этого найдем точку С, лежащую между 1-й и 3-й точками:

Рассмотрим метод симплекса.

Находим координаты отраженной вершины Е и значение в ней функции:

Т. к. , то строим новый симплекс на вершинах Е,1 и 3 и повторяем эту операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса.

Результат рабочей программы представлен на рисунке 17. Листинг приведен в приложении В.

Рисунок 17 - Практическая реализация симплекс-метода

Перейдем к методу деформируемого симплекса.

Введем коэффициенты уменьшения и увеличения: .

Найдем значения функции 4-х точек в окрестности начальной:

Минимальное значение функция принимает в точке1, поэтому строим новый симплекс на вершинах Е,1 и 3 и повторяем выше указанную операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса. Результат рабочей программы представлен на рисунке 18. Листинг приведен в приложении В.

Рисунок 18 - Практическая реализация метода деформируемого симплекса

3. Условная оптимизация

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

Но в реальных задачах обязательно присутствуют ограничения типа равенств или неравенств и ограничения по пределам изменения:

Наличие ограничений приводит к изменению точки минимума, тогда как в задаче без ограничений данная точка может оказаться вне допустимой области.

Рассмотрим 2 метода решения задачи условной оптимизации:

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

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

Например:

где R - параметр штрафа (некое число).

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

В данном курсовом проекте необходимо было максимизировать объемное тело, представленное на рисунке 19.

Рисунок 19 - Объем, который необходимо максимизировать

Указанное тело состоит из цилиндра и стоящего на нем сегмента сферы. Определим изменяемые параметры для данного случая (рисунок 20): r - радиус цилиндра (равен радиусу сферы), h - высота сегмента сферы и h2 - высота цилиндра.

Характеристики

Список файлов курсовой работы