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

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 Rⁿ

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

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

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

…

r: =f (x⁰); r1: =r+2*; x: =x⁰;

пока abs (r1-r) >=

нц

r1: =r;

Для i от 1 до n

нц

x1: =x;

x [i]: =x [i] +;

(): =f (x);

_min: = minf ( ());

x: =x1;

x [i]: =x [i] + _min;

кц

r: =f (x);

кц

…

x-искомый вектор.

4. Метод исключения областей

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

Одним из методов исключения является метод сеточного поиска, разработанный Мишке и дающий неплохие результаты. В этом случае суженная область неопределенности представляет собой гиперкуб - многомерный аналог квадрата или куба, - размеры которого можно определить заранее. Благодаря этому метод Мишке является одним из немногих методов многомерного поиска, эффективность которого поддается измерению. Чтобы лучше понять сущность этого метода, рассмотрим его для случая пространства проектирования, определяемого двумя переменными. Исходную область неопределенности в зависимости от размерности пространства отобразим на единичный квадрат, куб или гиперкуб. Это позволит вести поиск в нормированной области со стороной, равной единице. В гиперкубе построим сетку, образованную попарно симметричными взаимно ортогональными плоскостями, параллельными координатным направлениям, вдоль которых изменяются проектные параметры. Эти плоскости пересекаются по прямым, которые в свою очередь пересекаются в точках, называемых в дальнейшем узлами. Вычислим значения целевой функции в узлах и в центре куба. В случае М проектных параметров получим 2 значений целевой функции, из которых выберем наибольшее. Примем соответствующий узел за центр гиперкуба меньших размеров и продолжим исследование. Процесс продолжается до тех пор, пока не будет достигнута требуемая степень сужения интервала неопределенности. Если в области допустимых значений обозначить степень сужения вдоль какой-либо оси координат через r, то линейное сужение для b-мерного гиперкуба будет равно f=r, а число вычисленных значений целевой функции N=b (2) +1.

Мишке рекомендует выбирать r в интервале значений 2/3<r<1. Он отмечает также, что в случае трех и более переменных большую эффективность обеспечивают не кубические, а звездообразные области.

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

Выше в этой главе говорилось о громоздкости вычислений в случае многомерного пространства на примере числа значений целевой функции, которые необходимо вычислить, чтобы, пользуясь методом сеток, получить f==0,1, и было показано, что это число растет как степенная функция, показатель степени которой равен размерности пространства. Оригинальный подход, позволяющий обойти эту трудность, предложен Бруксом и основан на случайном поиске. Пусть пространство проектирования представляет собой куб или гиперкуб со стороной, равной единице, и разделено на кубические ячейки путем деления на 10 равных частей каждой стороны куба, соответствующей одному из проектных параметров. При N=2 число ячеек равно 100, при N=3 оно равно 100, в общем случае при N измерений число ячеек равно 10. Вероятность того, что выбранная наугад ячейка войдет в число 10% наиболее перспективных ячеек, равна 0,1, так как при N=1 нас будет интересовать одна ячейка из 10, при N=2 - одна из десяти лучших при общем количестве ячеек 100 и т.д. Вероятность того, что мы пропустим одну из 10% наиболее перспективных ячеек, составит 0,9. Если случайным образом выбрать две ячейки, то вероятность пропуска будет 0,9, т. е 0,81. Вообще вероятность нахождения по крайней мере одной ячейки из наиболее перспективных, доля которых равна f, после N попыток составит Р=1- (1-f) .

В таблице 1 указано, сколько ячеек надо выбрать случайным образом, чтобы обеспечить заданную вероятность при заданной доле наиболее перспективных ячеек. Из нее видно, что при случайной выборке 44 ячеек вероятность достижения f=0,1 составит 99%.

Это очень неплохо, если вспомнить, что для 100% -ного обеспечения целевую функцию в случае пяти переменных пришлось бы вычислить 2 476 099 раз.

Таблица 1.

Метод случайного поиска имеет два преимущества. Во-первых, он пригоден для любой целевой функции независимо от того, является она унимодальной или нет. Во-вторых, вероятность успеха при попытках не зависит от размерности рассматриваемого пространства. Хотя этот метод не позволяет непосредственно найти оптимальное решение, он создает подходящие предпосылки для применения в дальнейшем других методов поиска. Поэтому его часто применяют в сочетании с одним или несколькими методами других типов. Функция Random -случайное число из [0,1]

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

f (x) - > min, x Rⁿ

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

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

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

r: =f (x⁰); r1: =r+2*; x: =x⁰;

пока abs (r1-r) >=

нц

r1: =r; x1: =x;

Для i от 1 до n

нц

l [i]: = random;

x [i]: =x [i] +*R [i] ;

кц

(): =f (x);

_min: = minf ( ());

x: =x1;

для i от 1до n

нц

x [i]: =x [i] + _min* l [i] _;

кц

r: =f (x);

кц

6. Градиентные методы

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

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

Позднее мы включим их в схему поиска.

Метод оптимизации, в основу которого положена идея движения по самой крутой тропе, называется методом наискорейшего подъема или наискорейшего спуска. Вектор градиента перпендикулярен линии уровня и указывает направление к новой точке в пространстве проектирования.

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

Вектор градиента произвольной целевой функции F (x,x,x,…,x) имеет вид:

(F/x) e+ (F/ x) e+…. + (F/ x) e,

где частные производные вычисляются в рассматриваемой точке. Этот вектор направлен вверх, в направлении подъема; обратный ему вектор указывает направление спуска. Единичный вектор градиента часто представляют в виде ve+ve+ve+…+ve, где

v=.

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

Здесь - небольшое смещение в направлении x. Эту формулу часто называют "приближением секущей". Полученную информацию о направлении градиента можно использовать различным образом для построения алгоритма поиска.

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

f (x) - > min, x Rⁿ

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

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

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

r: =f (x⁰); r1: =r+2*; x: =x⁰;

Пока abs (r-r1) >=

нц

r1: =r;

x1: =x;

Для i от 1 до n

нц

l [i]: = f (x1) / x [i] ;

x [i]: =x [i] +*l [i] ;

кц

(): =f (x);

_min: = minf ( ());

x: =x1;

Для i от 1 до n

x [i]: =x [i] +_min*l [i] ;

кц

r: =f (x);

кц

6.1 Ступенчатый наискорейший подъем

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

Наискорейший подъем с использованием одномерного поиска

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

x=x+Sv,

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

Задача 1

Найти прямую наилучшим образом аппроксимирующую совокупность экспериментальных точек. Уравнение прямой y=m*x+b. Суммарная ошибка в случае точек определяется выражением SUM=

Необходимо найти минимум, SUM, оптимальные значения m,b. Экспериментальные точки заданы.

Задача 2

Емкость бака для жидких отходов должна составитьV л. Изготовляется бак из железобетона толщиной t см. Определить геометрические параметры бака, при которых на его изготовление пойдет минимальное количество бетона.

Задача 3

Емкость бака для жидких отходов должна составитьV л. Изготовляется бак из железобетона толщиной t см. Определить геометрические параметры бака, при которых на его изготовление пойдет минимальное количество бетона, учитывая что бак имеет крышку.

Задача 4

Изготовитель контейнеров проектирует открытый контейнер из листового материала. Заготовка вырезается из листа, сгибается по пунктирным линиям и сваривается четырьмя швами. Каковы должны быть размеры контейнера небольшого объема, если площадь его дна не должна превышать 1 м² и ни один из линейных размеров a,b,c не должны быть больше другого более чем в 3 раза?

Задача 5

Сравнительно простая с математической точки зрения целевая функция Розенброка y=100 (x₂-x) ²+ (1+x₁) ² описывает поверхность с впадиной.

Минимальное значение целевой функции соответствует точке с координатами M (x,y). Если взять начальную точку во втором квадранте, то не всегда удается обеспечить сходимость. Выбрав исходную точку попытаться решить эту задачу оптимизации:

a) методом покоординатного спуска;

b) градиентным методом.

Литература

1. Шуп Т. “Решение инженерных задач на ЭВМ", 1982

2. Брукс С.Ш." О случайных методах поиска максимума ”, 1958