Оптимизационные методы минимизации и максимизации
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
ную в результате исследующего поиска точку называют базовой.
Поиск по образцу:
Поиск по образцу в заключается в реализации единственного шага из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка определяется по формуле:
Как только движение по образцу не приводит к уменьшению целевой функции, точка фиксируется в качестве временной базовой точки и выполняется исследующий поиск. При уменьшении значения целевой функции эта точка рассматривается как базовая точка. Если же исследующий поиск не дал результата, необходимо вернуться в предыдущую точку и провести исследующий поиск заново. Если такой поиск не приводит к успеху, то необходимо уменьшить величину шага. Поиск завершается, когда величина шага приращения становится достаточно малой.
Алгоритм метода:
Шаг 1. Задать: 1. Начальную точку ;
. Приращение ,;
. Коэффициент уменьшения шага ;
. Параметр окончания поиска .
Шаг 2. Произвести исследующий поиск.
Шаг 3. Поиск удачный:
Да: перейти к шагу 5;
Нет: продолжить.
Шаг 4. Проверка на окончание поиска: ?
Да: прекратить поиск;
Нет: уменьшить приращение по формуле:
,; Перейти к шагу 2.
Шаг 5. Провести поиск по образцу:
Шаг 6. Провести исследующий поиск, используя в качестве базовой точки: - полученная в результате точка
Шаг 7. Выполняется ли условие ?
Да: продолжить ; ;
перейти к шагу 5; Нет: перейти к шагу 4.
Ход решения: Исходные данные:
- целевая функция;
Шаг 1.
- начальная точка;
- векторная величина приращения;
- масштабный множитель;
Минимизируем значение целевой функции до первого сокращения шага поиска
1.
Шаг 2. Исследующий поиск вокруг базовой точки :
фиксируя , даём приращение переменной :
; ; - поиск удачен;
фиксируя , даём приращение переменной :
; ; - поиск удачен;
Шаг 3.
Так как поиск удачен, то переходим к поиску по образцу (Шаг 5):
Шаг 6. 2. Исследующий поиск вокруг точки (Шаг 2.):
фиксируя , даём приращение переменной :
; ; - поиск удачен;
фиксируя , даём приращение переменной :
; ; - поиск удачен;
Шаг 7.
Шаг 5. Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.):
Шаг 6. 3.Исследующий поиск вокруг точки :
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
фиксируя , даём приращение переменной :
; ; - поиск удачен;
Шаг 7.
Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.):
Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск.
.
Шаг 6. Исследующий поиск вокруг базовой точки :
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
фиксируя , даём приращение переменной :
; ; - поиск удачен;
Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :
Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск (Шаг 6.).
.
Исследующий поиск вокруг базовой точки :
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
В результате исследующего поиска не было достигнуто уменьшение значения целевой функции, то есть значение шага (векторной величины приращения) уменьшить в раз, до величины , затем необходимо произвести исследующий поиск вокруг точки , используя новое значение приращения .
Итерации продолжаются, пока величина шага не укажет на окончание поиска в окрестности точки минимума.
Рис 3. Графическое пояснение метода Хука-Дживса
2.3Метод сопряженных направлений Пауэлла
Описание алгоритма:
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:
приводится к виду сумма полных квадратов
то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде:
вдоль направлений , , называемых -сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнить одномерных поисков.
Алгоритм метода:
Шаг 1. Задать исходные точки , и направление . В частности, направление может совпадать с направлением координатной оси;
Шаг 2. Произвести одномерный поиск из точки в направлении получить точку , являющуюся точкой экстремума на заданном направлении;
Шаг 3. Произвести одномерный поиск из точки в направлении получить точку ;
Шаг 4. Вычислить направление ;
Шаг 5. Провести одномерный поиск из точки (либо ) в направлении с выводом в точку .
Ход решения:
Исходные данные:
<