на тему рефераты Информационно-образоательный портал
Рефераты, курсовые, дипломы, научные работы,
на тему рефераты
на тему рефераты
МЕНЮ|
на тему рефераты
поиск
Оптимизация. Методы многомерного поиска

Оптимизация. Методы многомерного поиска

23

Министерство образования Республики Беларусь

Учреждение образования “Гомельский государственный университет им.Ф. Скорины”

Математический факультет

Кафедра ВМ и П

“Оптимизация. Методы многомерного поиска”

Выполнили

студентки группы М - 51, М - 52

Лаптева Е.Н., Кулай Н.В.

Научный руководитель

Орлов В.В.

Гомель 2002

Содержине

  • Введение
    • 1. Основы теории оптимизации
    • 1.1 Проектные параметры
    • 1.2 Целевая функция
    • 1.3 Поиск минимума и максимума
    • 1.4 Пространство проектирования
    • 1.5 Ограничения - равенства
    • 1.6 Ограничения - неравенства
    • 1.7 Локальный оптимум
    • 1.8 Глобальный оптимум
    • 2. Методы многомерного поиска
    • 3. Метод покоординатного подъема
    • 4. Метод исключения областей
    • 5. Метод случайного поиска
    • 6. Градиентные методы
    • 6.1 Ступенчатый наискорейший подъем
    • Литература
Введение

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

1. Основы теории оптимизации

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

Рассматривая некоторую произвольную систему, описываемую т уравнениями с n неизвестными, можно выделить три основных типа задач. Если т=n, задачу называют алгебраической. Такая задача обычно имеет одно решение. Если т>n, то задача переопределена и, как правило, не имеет решения. Наконец, при т<n задача недоопределена и имеет бесконечно много решений. В практике проектирования чаще всего приходится иметь дело с задачами третьего типа. При этом инженеру помогает интуиция, позволяющая сформулировать условия для выбора оптимального варианта. Очевидно, что изделие или технологический процесс, выгодно отличающееся от аналогичных изделий и процессов, будет пользоваться на рынке большим спросом. В этом и состоит смысл поиска оптимальных решений.

Прежде чем приступить к обсуждению вопросов оптимизации, введем ряд определений.

1.1 Проектные параметры

Этим термином обозначают независимые переменные параметры, которые полностью и однозначно определяют решаемую задачу проектирования. Проектные параметры - неизвестные величины, значения которых вычисляются в процессе оптимизации. В качестве проектных параметров могут служить любые основные или производные величины, служащие для количественного описания системы. Так, это могут быть неизвестные значения длины, массы, времени, температуры. Число проектных параметров характеризует степень сложности данной задачи проектирования. Обычно число проектных параметров обозначают через n, а сами проектные параметры через x с соответствующими индексами. Таким образом n проектных параметров данной задачи будем обозначать через x, x, x, … x.

1.2 Целевая функция

Это - выражение, значение которого инженер стремится сделать максимальным или минимальным. Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую (n+1) - мерную поверхность. Ее значение определяется проектными параметрами M=M (x, x, x, … x).

Примерами целевой функции, часто встречающимися в инженерной практике, являются стоимость, вес, прочность, габариты, КПД. Если имеется только один проектный параметр, то целевую функцию можно представить кривой на плоскости (рис.1).

Продолжительность эксплуатации

(проектный параметр)

Рис.1. Одномерная целевая функция

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

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

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

1.3 Поиск минимума и максимума

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

1.4 Пространство проектирования

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

1.5 Ограничения - равенства

Ограничения - равенства - это зависимость между проектными параметрами, которые должны учитываться при отыскании решения. Они отражают законы природы, экономики, права, господствующие вкусы и наличие необходимых материалов. Число ограничений - равенств может быть любым. Они имеют вид C (x, x, … x) =0,C (x, x, … x) =0, C (x, x, … x) =0.

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

1.6 Ограничения - неравенства

Это особый вид ограничений, выражаемых неравенствами. В общем случае их может быть сколь угодно много, причем все они имеют вид

zr (x, x, … x) Z

zr (x, x, … x) Z

…………………………….

zr (x, x, … x) Z

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

1.7 Локальный оптимум

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

1.8 Глобальный оптимум

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

2. Методы многомерного поиска

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

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

Так, если в случае одномерного пространства для достижения /==0,1 требуется вычислить 19 значений целевой функции, то в случае двумерного пространства это число составляет 361, трехмерного-6859, четырехмерного - 130 321, а пятимерного-2476 099! Поскольку при выборе оптимальной конструкции нередко приходится иметь дело с пятью и более переменными, серьезность трудностей, обусловленных многомерностью, становится очевидной.

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

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

3. Метод покоординатного подъема

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

Один из возможных примеров алгоритмов.

f (x) - > min, x Rn

x0-начальное приближение (массив [1: n])

Будем считать, что нам известна функция

minf ( ()), которая вычисляется min: (min) =min ()

Страницы: 1, 2



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