Курсовая работа: Сравнительный анализ методов оптимизации

2.1.2 Метод золотого сечения

Рассмотрим такое симметричное расположение точек x1 и х2 на отрезке [а; b], при котором одна из них становится пробной точкой и на новом отрезке, полученном после исключения части исходного отрезка. Использование таких точек позволяет на каждой итерации метода исключения отрезков, кроме первой, ограничиться определением только одного значения f (x), так как другое значение уже найдено на одной из предыдущих итераций.

Найдем точки x1 и х2, обладающие указанным свойством.

Рассмотрим сначала отрезок [0; 1] и для определенности предположим, что при его уменьшении исключается правая часть этого отрезка. Пусть х2 = t, тогда симметрично расположенная точка х1 = 1-t (рисунок 6).

Рисунок 6 - Определение пробных точек в методе золотого сечения

Пробная точка х1 отрезка [0; 1] перейдет в пробную точку х2¢ = 1-t нового отрезка [0; t]. Чтобы точки х2 = t, и х2¢ = 1-t делили отрезки [0; 1] и [0; t] в одном и том же отношении, должно выполняться равенство  или , откуда находим положительное значение

…

Таким образом,

х1 = 1-t = , .

Для произвольного отрезка [а; b] выражения для пробных точек примут вид

; . (5)

Замечания:

1. Точки x1 и х2 из (5) обладают следующим свойством: каждая из них делит отрезок [а; b] на две неравные части так, что отношение длины всего отрезка к длине его большей части равно отношению длин большей и меньшей частей отрезка. Точки с таким свойством называются точками золотого сечения отрезка [а; b]. Это и объясняет название рассматриваемого метода.

2. На каждой итерации исключения отрезков с пробными точками (5) одна из них  переходит на следующий отрезок и значение f (x) в этой точке вычислять не следует. Если новым отрезком становится [а; х2], то на него переходит пробная точка  исходного отрезка, становясь его второй пробной точкой (х2’= х1) (рисунок 6). В случае перехода к отрезку [х1; b] пробная точка  исходного отрезка становится первой пробной точкой отрезка [х1; b].

3. Легко проверить, что х1=а+b-х2, и x2=а+b-х1. Поэтому на каждой итерации метода золотого сечения недостающую пробную точку нового отрезка можно найти по перешедшей на него пробной точке с помощью сложения и вычитания, не используя формул (5).

4. В конце вычислений по методу золотого сечения в качестве приближенного значения х* можно взять середину последнего из полученных отрезков

.

Опишем алгоритм метода золотого сечения.

Шаг 1. Найти х1 и х2 по формулам (5). Вычислить f (x1) и f (x2).

Шаг 2. Определить . Проверка на окончание поиска: если en > e, то перейти к шагу 3, иначе - к шагу 4.

Шаг 3. Переход к новому отрезку и новым пробным точкам. Если f (x1) £ f (x2) то положить b=x2, x2=x1, f (x2) £ f (x1), x1=b-t (b-a) и вычислить f (x1), иначе - положить a=x1, x1= x2, f (x1) = f (x2), x2=b+t (b-a) и вычислить f (x2). Перейти к шагу 2.

Шаг 4. Окончание поиска: положить

, .

Сравнение методов исключения отрезков. При сравнении прямых методов минимизации обычно учитывают количество N значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.

Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности e (N) нахождения точки х*, которую они обеспечивают в результате определения N значений f (x). Метод золотого сечения считают более точным, чем метод дихотомии, однако разница в точности в данном случае незначительна.

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

Пусть заданы следующие параметры:

Примем  и . Тогда  (рисунок 7).

Рисунок 7 - Поведение исходной функции на заданном отрезке

Проведем несколько итерации методом дихотомии:

Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:

Так как f (x1) > f (x2), то a: =x1, b оставляем прежним. Тогда на третьем шаге:

Результаты полного решения данной задачи представлены на рисунке 8. Листинг программы представлен в приложении А.

Рисунок 8 - Получение решения методом дихотомии

Для метода золотого сечения:

Так как f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:

Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда на третьем шаге:

И так далее до тех пор, пока не достигнем указанной точности. Полный расчет представлен на рисунке 9. Листинг программы представлен в приложении А.

Рисунок 9 - Получение решения методом золотого сечения

2.2 Методы безусловной минимизации функций многих переменных

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

2.2.1 Метод циклического покоординатного спуска

Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениям x1 и x2.

Рисунок 10 - Циклический покоординатный спуск.

Опишем этот алгоритм.

Шаг 0. Выбрать х Î En, критерий достижения точности e и шаг . Найти f (x1 (0),x2 (0)).

Шаг 1. Принять x1 (1) = x1 (0) +. Определить f (x1 (1),x2 (0)). Сравнить полученное значение с значением начальной функции. Если f (x1 (1),x2 (0)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (1),x2 (0)) > f (x1 (0),x2 (0)), то перейти к шагу 2.

Шаг 2. Принять x1 (1) = x1 (0) - . Определить f (x1 (1),x2 (0)). Сравнить полученное значение с значением начальной функции. Если f (x1 (1),x2 (0)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (1),x2 (0)) > f (x1 (0),x2 (0)), то перейти к шагу 3.

Шаг 3. Принять x2 (1) = x2 (0) +. Определить f (x1 (0),x2 (1)). Сравнить полученное значение с значением начальной функции. Если f (x1 (0),x2 (1)) < f (x1 (0),x2 (0)), то перейти к шагу 5, если же f (x1 (0),x2 (1)) > f (x1 (0),x2 (0)), то перейти к шагу 4.

Шаг 4. Принять x2 (1) = x2 (0) - . Определить f (x1 (0),x2 (1)). Сравнить полученное значение с значением начальной функции. Если f (x1 (0),x2 (1)) < f (x1 (0),x2 (0)), то перейти к шагу 4, если же f (x1 (0),x2 (1)) > f (x1 (0),x2 (0)), то принять исходную точку за минимум.

Шаг 5. Проверить условие достижения точности .

Если в процессе решения с шагом  не получено решения, то принять

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9