Аннотация
Данный курсовой проект на тему «Оптимизация многомерной нелинейной функции. Слепой поиск». Необходимо было разработать программную модель числового метода поиска экстремума функции двух переменных. Предусмотреть ввод исходных данных и вывод с сохранением. Исследовать ограничения на вводимую функцию, обусловленные методом поиска и средствами моделирования.
Проект содержит 24 листа, включая приложение, листинг программы и таблицу – 1.
Введение
Прикладные науки развиваются своим путем, используя существующий математический аппарат для решения возникающих проблем, и даже своими потребностями стимулируют в развитие некоторых разделов математики. Но в них нередко царят своя терминология, свои частные приемы решения задач, свои исходные предпосылки и цели. Имеют место ситуации, когда некорректно примененные прикладниками методы, тем не менее, позволяют получать полезные практические результаты. Дисциплина «Математическое моделирование» давно сформировалась, как прикладная наука и включена в подготовку специалистов почти по всем экономическим техническим направлениям.
Математическое моделирование как инструмент познания завоевывает все новые и новые позиции в различных областях деятельности человека. Эта наука широко проникла в различные области науки: экономические, социальные, биологические и многие другие, на первый взгляд, далекие от математики.
Основная задача моделирования различного рода процессов и систем с целью исследования объектов, прогнозирования их поведения или поиска наилучших условий функционирования сводится к расчету анализируемых показателей по математической модели при тех или иных значениях (функциях) входных величин. Важное значение при этом приобретают вычислительные алгоритмы, с помощью которых можно получить при моделировании решение конкретной математической задачи.
Знакомству с идеями и алгоритмами решения наиболее распространенных задач вычислительной математики, применяющихся при математическом моделировании, получению практических навыков их применения.
Оно включает в себя следующие основные темы.
· Интерполяция
· Аппроксимация
· Решение нелинейных уравнений и их систем
· Решение систем линейных уравнений
· Вычисление интегралов
· Основы решения дифференциальных уравнений
· Метод оптимизации.
Постановка задачи
Теоретическое приложение
Концепция методов
В методах случайного поиска величина шага при построении улучшающей последовательности
формируется случайным образом. Поэтому в одной и той же ситуации шаг
может быть различен в отличие от регулярных методов. «Методы случайного поиска являются прямым развитием известного метода проб и ошибок, когда решение ищется случайно, и при удаче принимается, а при неудаче отвергается, с тем чтобы немедленно снова обратиться к случайности как к источнику возможностей. Такое случайное поведение разумно опирается на уверенность, что случайность содержит в себе все возможности, в том числе и искомое решение во всех его вариантах».
В данном разделе рассматриваются следующие методы:
· Слепой поиск
· Метод случайных направлений
· Метод поиска с «наказанием случайностью»
· Блуждающий поиск
В целом случайные методы поиска предпочтительнее регулярных в задачах высокой размерности и вдали от оптимума. Поэтому здесь они рассматриваются преимущественно в ознакомительном плане. Методы этой группы позволяют в среднем быстрее выходить в район оптимума. Эффективны рассматриваемые методы и при поиске глобального оптимума.
Основные методы
1. Метод случайных направлений.
Из текущей (или заданной начальной) точки делается шаг в случайном направлении , где
– случайный вектор с модулем, равным единице (случайно только его направление);
– коэффициент пропорциональности шага. Если
(при поиске минимума критерия оптимальности), то новая точка принимается за текущую, и из нее делаются шаги в надежде найти лучшую точку. Если
, то делают новую попытку, то есть новый шаг
.
Поиск заканчивают, когда за заданное число попыток не удается найти точку с лучшим значением критерия оптимальности, чем имеющаяся текущая.
Существуют модификации метода, в одной из которых после серии неудачных попыток уменьшается коэффициент
, что позволяет «уточнить» положение оптимума. В этом случае условием окончания является малость значения шага (то есть
).
Существует также модификация метода с обратным шагом. Отличительной ее особенностью является то, что при неудачном шаге из точки
сразу производится шаг в обратном направлении
. При достаточном удалении от оптимума такая стратегия поиска может оказаться весьма эффективной. Если обратный шаг оказался неудачным, то можно сделать новый шаг из текущей точки или перейти к поиску с уменьшенным шагом. В последнем случае существует опасность замедления поиска вдали от оптимума, особенно в овраге.
2. Метод поиска с «наказанием случайностью».
Метод является аналогом метода наискорейшего спуска, только направление локального поиска не градиентное, а случайное. Как и в предыдущем методе, из текущей точки делают случайные шаги до тех пор, пока не будет найдена точка с лучшим значением критерия оптимальности. Затем в этом направлении регулярным методом одномерного поиска ищут оптимум. В точке оптимума по направлению опять случайным образом ищут новое направление и т.д.
Условием окончания обычно является невозможность получения лучшей точки из текущей за предварительно заданное число попыток .
3. Метод с «блуждающим поиском».
Данный метод является статистическим расширением градиентного метода и реализуется в соответствии с алгоритмом
где – случайный вектор с единичным модулем,
и
– коэффициенты, характеризующие вклад случайной составляющей
и регулярной составляющей (
) в величину шага.
Чаще в формуле для используется не градиент
, а составляющие направляющие косинусы градиента, что позволяет выдерживать заданное соотношение между регулярной и случайной составляющими шага.
Теоретически доказывается, что данный алгоритм наиболее вероятно приведет к глобальному экстремуму. В алгоритме могут использоваться алгоритмы коррекции шага , свойственные градиентному методу, который включается после
неудачных попыток. Условием окончания является малость значения шага
.
Стратегия поиска может предусматривать не постоянное, а периодическое добавление случайного вектора к градиентному шагу. Частота случайных «скачков» должна уменьшаться по мере приближения к оптимуму и увеличиваться вдали от него. Для этого существуют специальные алгоритмы самообучения, например:
,
где – число шагов регулярным градиентным методом без случайной составляющей, т.е. период добавления случайной составляющей;
– заданное целое число (рекомендуется
, при этом в процессе поиска
будет изменяться в диапазоне
).
Обратно пропорционально частоте «скачков» меняется и доля случайной составляющей в шаге, т.е. . Условием окончания поиска будет, как и в регулярном градиентном методе, близость градиента к нулю.
Математическое описание
Метод слепого поиска
Идея метода очень проста и наглядна. Случайным образом в допустимой области берется точка, и сравнивается значение критерия в ней с текущим наилучшим. Если новая случайно взятая точка хуже хранящейся в качестве текущей лучшей, то берут другую точку. Если же нашли точку, в которой критерий лучше, то ее запоминают в качестве текущей лучшей. Гарантируется, что при неограниченном возрастании числа попыток мы будем приближаться к глобальному оптимуму, т.е. найденное текущее наилучшее значение будет столь угодно близко к точному решению.
На практике поиск прекращают, когда число неуспешных попыток превышает наперед заданное число .
Данный поиск можно применять для поиска начального приближения, задав сравнительно небольшое число попыток. Метод прост в алгоритмическом плане и не требует примера с конкретными значениями.
Для получения случайных чисел , принадлежащих открытому интервалу (
) используют функцию преобразования
,
если нужны целые числа, используют
.
Блок – схема алгоритма моделирования
![]() | |||
![]() | |||
Описание ввода – вывода
1 – вводим выбранную нами функцию;
2 – ввод выбранного нами интервала.
3 – вводим число итераций;
4 – основной цикл для вычислений;
5 – реализация случайной величины для получения значений координат точки;
6 – вычисляем значение функции;
7 – первая итерация;
8 – первое вычисляемое значение оптимально;
9 – выбираем следующее более оптимальное значение;
11 – текущее значение является оптимальным;
12 – выводим X1, X2, Y оптимальные, т.е. выводим минимум функции