Оптимизация многомерной нелинейной функции. Слепой поиск (стр. 1 из 3)

Аннотация

Данный курсовой проект на тему «Оптимизация многомерной нелинейной функции. Слепой поиск». Необходимо было разработать программную модель числового метода поиска экстремума функции двух переменных. Предусмотреть ввод исходных данных и вывод с сохранением. Исследовать ограничения на вводимую функцию, обусловленные методом поиска и средствами моделирования.

Проект содержит 24 листа, включая приложение, листинг программы и таблицу – 1.

Введение

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

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

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

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

Оно включает в себя следующие основные темы.

· Интерполяция

· Аппроксимация

· Решение нелинейных уравнений и их систем

· Решение систем линейных уравнений

· Вычисление интегралов

· Основы решения дифференциальных уравнений

· Метод оптимизации.

1. Постановка задачи

1.1 Теоретическое приложение

Концепция методов

В методах случайного поиска величина шага

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

В данном разделе рассматриваются следующие методы:

· Слепой поиск

· Метод случайных направлений

· Метод поиска с «наказанием случайностью»

· Блуждающий поиск

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

и вдали от оптимума. Поэтому здесь они рассматриваются преимущественно в ознакомительном плане. Методы этой группы позволяют в среднем быстрее выходить в район оптимума. Эффективны рассматриваемые методы и при поиске глобального оптимума.

1.2 Основные методы

1. Метод случайных направлений.

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

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

Поиск заканчивают, когда за заданное число попыток

не удается найти точку с лучшим значением критерия оптимальности, чем имеющаяся текущая.

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

уменьшается коэффициент , что позволяет «уточнить» положение оптимума. В этом случае условием окончания является малость значения шага (то есть ).

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

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

2. Метод поиска с «наказанием случайностью».

Метод является аналогом метода наискорейшего спуска, только направление локального поиска не градиентное, а случайное. Как и в предыдущем методе, из текущей точки делают случайные шаги до тех пор, пока не будет найдена точка с лучшим значением критерия оптимальности. Затем в этом направлении регулярным методом одномерного поиска ищут оптимум. В точке оптимума по направлению опять случайным образом ищут новое направление и т.д.

Условием окончания обычно является невозможность получения лучшей точки из текущей за предварительно заданное число попыток

.

3. Метод с «блуждающим поиском».

Данный метод является статистическим расширением градиентного метода и реализуется в соответствии с алгоритмом

где

– случайный вектор с единичным модулем, и – коэффициенты, характеризующие вклад случайной составляющей и регулярной составляющей ( ) в величину шага.

Чаще в формуле для

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

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

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

Стратегия поиска может предусматривать не постоянное, а периодическое добавление случайного вектора к градиентному шагу. Частота случайных «скачков» должна уменьшаться по мере приближения к оптимуму и увеличиваться вдали от него. Для этого существуют специальные алгоритмы самообучения, например:

,

где

– число шагов регулярным градиентным методом без случайной составляющей, т.е. период добавления случайной составляющей;

– заданное целое число (рекомендуется , при этом в процессе поиска будет изменяться в диапазоне ).