2. Порядок выполнения работы

1. Разработать программу поиска минимума функции методом Хука-Дживса с прежними исходными данными. Координаты начальной точки поиска должны быть заданы двумя способами: ввод координат пользователем и случайным образом. Шаг и точность поиска также задается пользователем.

2. Осуществить 3-4 запуска программы из различных точек с разным шагом. Поиск прекращается, когда длина шага будет меньше или равна заданной точности.

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

3. Требования к защите лабораторной работы

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

Контрольные вопросы

1. Характеристика алгоритмов с локальными свойствами.

2. Достоинства и недостатки метода Хука-Дживса.

3. Возможные модификации метода.

Лабораторная работа № 4

МЕТОД ШТРАФНЫХ ФУНКЦИЙ

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

1. Описание метода

Идея метода заключается в образовании составной целевой функции

,

где m – число ограничений;

-штрафная функция, учитывающая ограничения в виде неравенств;

Y(x) – рассматриваемая функция;

f_j(x) – функциональные и параметрические ограничения;

r – принимает значения от 3 до 5.

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

2. Порядок выполнения работы

1. Для метода Хука-Дживса, реализованного в лабораторной работе № 3, разработать программу поиска экстремума с учетом ограничений, т.е. реализовать возможность генерации стартовой точки в недопустимой области решений.

2. Осуществить 3-4 запуска программы из различных точек с разным шагом. Окончание процесса поиска аналогично прекращению поиска в методе Хука-Дживса.

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

3. Требования к защите лабораторной работы

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

Контрольные вопросы

1. Внутренние и внешние штрафные функции.

2. Учет ограничений в методах с локальными свойствами.

Лабораторная работа № 5 случайный поиск с линейной и нелинейной тактикой

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

1. Описание методов

Метод случайного поиска с линейной тактикой

Данный метод строится с помощью двух операторов. Первый оператор случайного шага (), второй - оператор повторения предыдущего шага.

Суть метода: вероятность удачи в ранее удачном шаге больше, чем в случайном, т.е. целесообразно повторять удачные шаги, а при неудаче делать новый случайный шаг. Линейность такого алгоритма заключается в линейном повторении удачного шага (рис. 1).

Метод случайного поиска с нелинейной тактикой

Данный алгоритм моделирует метод проб и ошибок и строится из двух операторов. Первый оператор случайного шага (). Второй оператор – возврат.

Идея алгоритма: используются только те случайные шаги, которые привели к успеху, т.е. к улучшению целевой функции. Неудачные шаги исправляются с помощью оператора возврата. Случайность является поощрением (рис. 2).

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