Оптимизация транспортной техники

Размещено на http://www.allbest.ru/

Содержание

Введение.

1. Целевые функции. Выбор критериев.

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

Литература.



Введение

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

С развитием техники, усложнением структуры производства, усложнением и удорожанием проектируемых изделий активно ведутся исследования по алгоритмам оптимизации, и имеется богатый материал по теории линейного и нелинейного программирования.

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

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



1.Целевые функции. Выбор критериев

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

Х1,Х2,Х3,…Хп.

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

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

М = М ( х1,х2,…,хп ).

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

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



Рисунок 2. Двумерная целевая функция.

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

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

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

Рисунок 3. При изменении знака целевой функции на противоположный в задаче на минимум, превращает ее в задачу на максимум.

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

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

С1 (X1, X2, Х3, . . ., Хп) = 0,

С2 (X1, X2, Х3, . . ., Х п) = 0,

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

Сj(X1, X2, Х 3, . . ., Хп) = 0.

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

z1 ?r1(X1, X2, Х3, . . ., Хп) ?Z1

z2 ?r2(X1, X2, Х3, . . ., Хп) ?Z2

………………………………………

zk ?rk(X1, X2, Х3, . . ., Хп) ?Zk

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

Прямые и функциональные ограничения. Прямые ограничения имеют вид

xнi ? xi ? xвi при i ? [1;n],

где xнi , xвi - минимально и максимально допустимые значения i-го управляемого параметра; п - размерность пространства управляемых параметров. Например для многих объектов параметры элементов не могут быть отрицательными: xнi ? 0 (геометрические размеры, электрические сопротивления, массы и т.п.).

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

1) типа равенств

ш (Х) = 0; (2.1)

2) типа неравенств

ц (Х) › 0, (2.2)

где ш (Х) и ц (Х) - вектор-функции.

Прямые и функциональные ограничения формируют допустимую область поиска:

ХД = {Х | ш(Х) = 0, ц (Х)›0, xi › xнi ,

xi ‹ xвi при i ? [1;n]}.

Если ограничения (2.1) и (2.2) совпадают с условиями работоспособности, то допустимую область называют также областью работоспособности ХР.

Любая из точек Х принадлежащая ХД является допустимым решением задачи. Часто параметрический синтез ставится как задача определения любого из допустимых решений. Однако гораздо важнее решить задачу оптимизации - найти оптимальное решение среди допустимых.

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

Рисунок 4. Произвольная целевая функция может иметь несколько локальных оптимумов.

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

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

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

yi < TTi , i О [1, k]; yi > TTj , j О [k+1, l];

yr = TTr ± ?yr; r О [l+1, m].

где yi, yj, yr - множество выходных параметров;

TTi, TTj, TTr - требуемые количественные значения соответствующих выходных параметров по техническому заданию;

?yr - допустимое отклонение r-го выходного параметра от указанного в техническом задании значения TTr.

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

Частные критерии могут применяться в случаях, когда среди выходных параметров можно выделить один основной параметр yi(Х), наиболее полно отражающий эффективность проектируемого объекта. Этот параметр принимают за целевую функцию. Примерами таких параметров являются: для энергетического объекта - мощность, для технологического автомата - производительность, для транспортного средства - грузоподъемность. Для многих технических объектов таким параметром служит стоимость. Условия работоспособности всех остальных выходных параметров объекта относят при этом к функциональным ограничениям. Оптимизация на основе такой постановки называется оптимизацией по частному критерию.

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

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

(2.1)

где aj>0 - весовой коэффициент, определяющий степень важности j-го выходного параметра (обычно aj выбираются проектировщиком и в процессе оптимизации остаются постоянными).

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

(2.2)

определяет среднеквадратичное приближение yj(X) к заданным техническим требованиям TTj.

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

(2.3)

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

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

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

(2.4)

где р -- количество узловых точек щj на оси переменной щ ; aj - весовые коэффициенты, значения которых тем больше, чем меньшее отклонение y(Х, щj) - yTT(Х, щj) нужно получить в j-и точке.

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

Введем количественную оценку степени выполнения j-го условия работоспособности, обозначим ее через zj и будем называть запасом работоспособности параметра yj. Расчет запаса по j-му выходному параметру можно выполнить различными способами, например,

(2.5)

где аj - весовой коэффициент; yjном - номинальное значение j-го выходного параметра; дj - величина, характеризующая разброс j -го выходного параметра.

Здесь предполагается, что все соотношения сведены к виду yi < TТj. Если yi > TТj , то -yj < -TТj . Следует принимать аj >1 (рекомендуемые значения 5 ? аj ? 20), если желательно достичь выполнения j-го технического требования с заданным допуском, т. е. yj = TТj ± ?yj; aj=l, если необходимо получить максимально возможную оценку zj.

Качество функционирования технической системы характеризуется вектором выходных параметров и, следовательно, вектором Z=(zm,zm,…,zm). Поэтому целевую функцию следует формировать как некоторую функцию ц(Z) вектора оценок. Например, если в качестве целевой функции рассматривается запас только того выходного параметра, который в данной точке X является наихудшим с позиций выполнения требований ТЗ, то

где m - количество запасов работоспособности.

Естественно теперь поставить задачу о выборе такой стратегии поиска X, которая максимизировала бы минимальный из запасов, т. е.

(2.6)

где ХД - допустимая для поиска область.

Критерий оптимизации с целевой функцией (2.6) называют максиминным критерием.

Статистические критерии. Оптимизация при статистических критериях имеет целью получение максимальной вероятности Р выполнение работоспособности. Эту вероятность принимают в качестве целевой функции. Тогда имеем задачу

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

Возможны различные способы нормирования. В качестве примера рассмотрим способ логарифмического нормирования, достоинством которого является переход от абсолютных приращений параметров к относительным. В этом случае i-и управляемый параметр ui преобразуется в безразмерный хi следующим образом:

(2.7)

где оi - коэффициент, численно равный единице параметра ui .

Нормирование выходных параметров можно выполнить с помощью весовых коэффициентов, как в аддитивом критерии, или переходом от уj к запасам работоспособности zj по (2.5).

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

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

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

Надежные и одновременно экономичные методы поиска глобального экстремума в настоящее время неизвестны. Надежным, но крайне неэкономичным методом глобального поиска является метод сканирования. При его применении область определения F(Х) в пространстве управляемых параметров разбивается на k подобластей, в центре каждой из которых вычисляется значение целевой функции. Если функция зависит от п параметров, то необходимо выполнить kn вариантов расчетов. Чтобы получить достоверную картину поведения гиперповерхности отклика целевой функции, необходимо сканировать допустимую область с достаточно малым шагом. Поэтому даже для сравнительно несложных задач потери машинного времени на поиск становятся недопустимо большими. Этот недостаток характерен и для методов случайного поиска глобального экстремума. Однако затраты ресурсов на случайный поиск можно сделать приемлемыми, если не предъявлять высоких требований к надежности определения экстремума.

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

Классы методов безусловной оптимизации

Рис. 1.

В методах нулевого порядка (прямых методах) информация о производных не используется. Для методов первого порядка необходимо вычислять как значение функции качества, так и ее первые частные производные (градиентные методы).

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

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

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

Используются также методы условной оптимизации (методы проекции градиента, допустимых направлений (метод Заутендайка) и др.).

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

Практически все методы оптимизации стремятся построить такую последовательность значений Х0, X1, Х2 и т. д., при которой F(X0 )>F(Х1)>F(Х2)>… . В этом случае метод обеспечивает сходимость и можно надеяться, что минимум функции будет найден.

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

Основные этапы поиска экстремума. Численные методы поиска оптимума позволяют построить последовательность шагов от начальной точки Х0 через некоторые промежуточные точки Хk к локальному экстремуму X*.

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

Рис. 2.

оптимизация функция нормирование ограничение

Очевидно, что Х0 должна принадлежать области определения целевой функции и чем ближе к экстремуму выбрана Х0, тем быстрее и с большей вероятностью экстремум будет найден. Сущность метода оптимизации определяется этапами 2 и 3 алгоритма, на которых выбирается направление дальнейшего поиска и вычисляются координаты очередной точки Xk+1 на траектории поиска. Далее в точке Xk+1 вычисляются значения целевой функции F(Xk+1) и функций-ограничений, т. е. определяется информация, позволяющая судить о достигнутом успехе. Инженер может назначить различные условия прекращения поиска, и в зависимости от степени их выполнения поиск будет продолжен или прекратится.

При анализе различных методов поиска полезны геометрические представления.

Поверхность отклика функции двух переменных F(X)=F(x1, x2) удобно представлять совокупностью линий равных уровней (рис. 3).

Рис. 3.

Эти линии получаются при пересечении поверхности отклика <F(X) плоскостью, параллельной плоскости координат (х1, х2). При наличии ограничений типа равенств или неравенств характер их поведения также удобно изображать на той же плоскости, имея в виду, что каждое из уравнений ограничений определяет в п-мерном пространстве (п--1)-мерную поверхность. На плоскости (х1,х2) ограничение имеет вид некоторой линии. Штриховкой отмечается допустимая область поиска.

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

Поведение поверхностей отклика целевых функций



а -- многоэкстремальность; б -- овражный характер; в -- седловая точка

Рис. 4.

Классические методы оптимизации.

Метод прямого перебора. Если известна функциональная связь целевой функции Y и искомой переменной X, то можно последовательно вычислить значения целевой функции для некоторых значений искомой переменной. Вычисления повторяются до тех пор, пока не будет найден min (max) значения целевой функции

Y=f(x1,…, xi,…, xn, u1,…, uj,…, um),

xi= x0i + Дxik (k=0, 1, 2,…,l)

Этот метод может быть использован для решения задач исследования операций, если имеются одна искомая переменная или несколько с небольшим диапазоном изменения искомых переменных:

Особенность и преимущества метода прямого перебора заключаются:

1) в независимости поиска от вида и характера целевой функции;

2) в цикличности поисковой процедуры;

3) в определении глобального экстремума целевой функции;

4) в простоте алгоритма и программы оптимизации;

5) в малом объеме необходимой машинной памяти.

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

Классический метод дифференциального исчисления. Если известна функциональная связь целевой функции с искомыми переменными Y=f(x1,…, xi,…, xn u1,…, uj,…, um), которая обладает непрерывными первыми частными производными, то, определив частные производные по своим искомым переменным, приравняв частные производные от Y по xi нулю и решив совместно систему уравнений

?Y/?х1 = 0,(1.1)

?Y/?xn = 0,

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

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

1) при большом числе оптимизируемых параметров рассматриваемый метод становится весьма сложным в части решения системы уравнений

?Y/?xi = 0 (i=1, 2, ...,n);

2) условие определения экстремума, выраженное системой уравнений (1.1), является необходимым, но не достаточным для решения задачи. Так как выражения (1.1) определяют положение стационарных точек внутри области, среди которых, кроме экстремальных, могут быть особые точки типа “седла”, учет достаточных условий нахождения экстремумов функции многих переменных является сложным как в алгоритмическом, так и в вычислительном плане. Так, достаточное условие существования min функции одной переменной -- это положительная, величина производной четного порядка d2kY/dx>0 (k=1, ..., п). При наличии функции двух переменных достаточным условием существования min функции является положительная определенность матрицы

3) рассматриваемый метод дает возможность найти экстремум только в том случае, если он лежит внутри, а не на границе области возможных значений переменных, следовательно, требуется дополнительный анализ значений функции f(x1,…, xi,…, xn u1,…, uj,…, um), на границах допустимой области изменения параметров (x1,…, xi,…, xn ).

4) оптимизируемая функция f(x1,…, xi,…, xn u1,…, uj,…, um) должна быть непрерывной и иметь первые и вторые производные по оптимизируемым параметрам;

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

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

Пусть имеется целевая функция Y=f(x1,..., хn, u1, ..., um), экстремум которой требуется найти, причем существуют дополнительные условия

цk(x1,…, xi,…, xn u1,…, uj,…, um)=0 (k=1, 2, …,p).

Введя p дополнительных множителей л1, л2, … лp, построим новую функцию

L(x1...,xi,…, хn, uj,..... , um, л1, …,лk, …, лp,) =

f(xk,…, xi,…, xn u1,…, uj,…, um) -

где лk - множитель Лагранжа.

Необходимые условия экстремума состоят в равенстве нулю всех первых частных производных от L по x1...,xi,…, хn, л1, …, лk, …, лp:

dL/dxi = 0 (i = l, 2, ..., n);

dL/ лk =0. (k=1, 2, ..., р).

В результате получается n + р уравнений с n + р неизвестными (x1..., xi,…, хn), (л1, …,лk, …, лp). Решение этих уравнений относительно переменных х, л дает возможность определить положение стационарной точки. Использование вспомогательной функции L(х, л) позволяет заменить задачу с дополнительными условиями задачей без них.

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

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

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

Методы поиска экстремума унимодальных функций. Функция одной переменной, имеющая в интервале исследования один горб (впадину), называется унимодальной, или: функция Y - унимодальная, если x1<xопт (х1>xопт), x2<xопт (х2 >xопт) и x1<х2, то Y(x1)< Y(x2) (Y(x1)>Y(x2)) .

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

Рис. 5. Разновидности унимодальной функции:

а - выпуклая; б - непрерывная; в - произвольная

Если целевая функция унимодальная, то можно сузить интервал исследования функции на оптимум путем определения значений целевой функции в двух точках интервала задания функций Y(x1) и Y(x2) и последующего поинтервального сравнения. При этом возможны три случая (рис. 6):



Рис. 6. Возможные случаи сужения интервала исследования

1) если У1 > У2, то хопт<х2 , т. е. оптимум не может лежать правее, иначе нарушается предположение об унимодальности функции (интервал [х2, х] из дальнейшего рассмотрения исключается);

2) если У1 < У2, то хопт > х1;

3) если У1=У2, то х1<хопт<х2.

Как правило, задачи оптимизации имеют унимодальную целевую функцию.

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

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

Метод дихотомии (половинное деление). В этом методе (рис.7) искомая длина интервала исследования xn, в котором лежит искомый оптимум, уменьшается с каждом шагом N почти в два раза.



Рис. 7. Зависимость длины интервала исследования от числа шагов поиска.

Алгоритм метода состоит из следующих этапов:

1) делят исходный интервал исследования пополам;

2) вблизи точки деления (по разные ее стороны) подсчитывается дважды значение целевой функции Y(x'N+1), y(x" N+1):

x?N+l=xN/2 - Дx/2; x" N+l = xN/2 + Дx/2,

где Дx - наименьший интервал изменения управляющей переменной, при котором становится возможным обнаружить отличие между Y(x'N+1), и y(x" N+1 );

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

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

Интервал, в котором находится оптимум, после N шагов определяется-по формуле



xn= [2-N/2 + (1 - 2-N/2) Дх] х0,

где х0 - первоначальный интервал исследования; N - число шагов. Грубо говоря, xQ/xN ? 2N/2.

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

Рис. 8. Обозначения, используемые в методе золотого сечения.

Сущность этого метода состоит в следующем. Интервал неопределенности делится на две неравные части так, что отношение длины большого отрезка к длине всего интервала равно отношению длины меньшего отрезка к длине большего отрезка рис. 8 показан интервал неопределенности Z, состоящий из отрезков z1 и z2, отношение длин которых определяется правилом золотого сечения



Кроме того, z1 + z2 =Z. Из первого уравнения следует z21=Zz2. Подставляя сюда значение Z из второго уравнения и деля обе части на z21 , получаем

Решая это квадратное уравнение, находим для положительно корня значение

На рис. 9 показано деление интервала неопределенное в этом отношении и нанесены соответствующие значения целевой функции, которые позволяют уменьшить интервал неопределенности в 1/0,618 раза. На этой стадии еще не видны преимущества Метода золотого сечения по сравнению с методом дихотомии, однако, они явно проявляются при дальнейшем делении интервала, так как оказывается, что одно из значений целевой функции, которое требуется вычислить на следующем шаге, уже известно.



Рис. 9. Метод золотого сечения.

Поэтому, чтобы уменьшить неопределенность еще в 1/0,618 раза, требуется дополнительно вычислить только одно значение целевой функции в точке, определяемой правилом золотого сечения

При п>2 эффективность метода золотого сечения выше, чем у метода дихотомии, так как при каждом последующем вычислении целевой функции интервал неопределенности сокращается в 1/0,618 раза. После вычисления N значений целевой функции коэффициент дробления интервала неопределенности составляет

f = 0,618N-1.

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

ZJ-2 = ZJ-1 +ZJ, 1<J<N,



где ZJ - длина интервала неопределенности после вычисления J-го значения целевой функции.

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

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

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

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

Метод покоординатного спуска, подъема (метод Гаусса-Зейделя). Суть его в поочередной оптимизации последовательно по каждому управляющему параметру.

Пусть решению подлежит задача минимизации функции F(X)

где ХП - n-мерное пространство.

В методе покоординатного спуска направление очередного шага выбирается вдоль какой-либо одной координатной оси, например оси параметра x1. Движение в этом направлении производится в сторону, в которой наблюдается уменьшение F(Х), и выполняется до тех пор, пока F(X) уменьшается. Далее движение начинается вдоль новой координатной оси, например параметра x2, и т. д. После цикла спусков вдоль всех п осей производится новый цикл, если экстремум еще не найден. Когда ни по одной из осей невозможно перемещение с уменьшением функции F(Х) с шагом h>hmin, поиск прекращается и полученная точка X признается за принадлежащую малой окрестности экстремальной точки X* (здесь hmin - задаваемое ограничение шага снизу).



Рис. 10. Графическая интерпретация метода поочередного изменения параметров

Сначала оптимизация производится по одному параметру х1 затем переходят ко второму х2 и так далее, пока значения целевой функции не перестанут уменьшаться (возрастать) (рис.10).

Недостатки:

1. обеспечивает получение только локального оптимума или особой точки типа седла;

2. позволяет оптимизировать только непрерывно изменяющиеся параметры;

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

4. эффективность метода существенно снижается при наличии ограничений.

Преимущество метода - простота алгоритма и программы.

Метод градиента. Один из самых распространенных регулярных методов поиска. Процесс оптимизации по методу градиента заключается в определении направления наибольшего изменения целевой функции Y = f(xi, ...,xn, u1, …, um) и некотором перемещении по этому направлению. Направление наибольшего изменения функции определяется направлением градиента оптимизируемой функции.

Для нахождения составляющих градиента необходимо: вычислить частные производные целевой функции по оптимизируемым параметрам ?f/?xi (i = 1, 2, ..., n). Градиент функции grad f(x) = (?f/?x1, …, ?f/?xn), вычисленный в точке N(x1(N), ..., х), характеризует направление быстрейшего возрастания функции, а антиградиент--направление быстрейшего убывания. Градиент всегда перпендикулярен к поверхности равных значений целевой функции.

Для определения оптимума необходимо при минимизации целевой функции для каждой точки поиска N определить градиент и сделать шаг по направлению антиградиента (т. е. в направлении, обратном градиентному) xi(N+1) = xi(N) - а?f/?xi (i = l, 2, ..., n), где a>0 - длина рабочего шага, значение которого может определяться двояко:

1) если a = const, то модуль рабочего шага для метода градиента оказывается пропорциональным модулю градиента:

,

т. е. не является постоянным;

2) если же a = b|grаd f(x)(N)|-1, то модуль рабочего шага оказывается постоянным, так как

|Дx(N+1)| = b |grаd f(x)(N)|-1 |grаd f(x)(N)| = b = const .

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

Недостатки:

1) необходимо перед каждым рабочим шагом производить довольно сложный предварительный анализ;

2) при наличии ограничений применение метода затрудняется;

3) необходимо определять частные производные целевой функции по оптимизируемым параметрам;

4) невысокая скорость достижения оптимума;

5) трудности в достижении конечной точки (оптимума);

6) большая чувствительность к масштабным преобразованиям.

Графическая интерпретация метода градиентов

Рис. 11.

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

Метод наискорейшего спуска (подъма). Это разновидность метода градиента, обеспечивающая наименьшее число шагов в определении оптимума. Суть его сводится к следующему. После определения градиента функции Y=f(x) делается шаг в направлении, обратном градиенту. Если значение целевой функции при этом уменьшилось по сравнению с исходным, то делается очередной рабочий шаг в том же направлении, а не определяется заново градиент, как при методе градиента. Если же после очередного рабочего шага значение целевой функции увеличилось по сравнению с предыдущим значением, то движение прекращается, заново определяется направление градиента и т. д. Повышенная скорость сходимости является существенным преимуществом этого метода.

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

Р = 1 - (1 - f)N.

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

Таблица 1.

f	Вероятность
	0,80	0,90	0,95	0,99
0,1	16	22	29	44
0,05	32	25	59	90
0,01	161	230	299	459
0,005	322	460	598	919

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

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

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

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

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

4. Проанализировать особенности алгоритма. Анализ структуры алгоритма часто позволяет решить вопрос о его пригодности для решения той или иной конкретной задачи. Не рекомендуется использовать методы, требующие нахождения частных производных в аналитическом виде, так как для многих целевых функций это невозможно сделать (примером могут служить зависимости, полученные экспериментально). Кроме того, если структура производных, полученных аналитически, очень сложна, то само дифференцирование может резко увеличить стоимость подготовки задачи и вероятность ошибок со стороны программиста. Методы, включающие изменение масштабов, как правило, обладают большей эффективностью и гибкостью. Отметим, что более гибкие программы для ЭВМ обычно не отличаются большими, размерами или временем счета. Так как всегда желательно испробовать для решения данной задачи несколько разных алгоритмов, то заслуживает внимания “пакетный” подход, позволяющий переходить с одного алгоритма на другой путем замены в основной программе обращения к подпрограмме. Тем самым исключается необходимость составления новой программы, экономится время и сокращаются затраты труда.



Литература

1. Сухарев А.Г., Тимохов А.В., В.В. Курс методов оптимизации М.:Наука, 1986.- 328 с.

2. Батищев Д.И. Методы оптимального проектирования М.: Радио и связь, 1984.-248 с.

3. Дегтярев Ю.И. Методы оптимизации: Учеб. пособие для вузов. - М.: Сов. радио, 1980. - 272 с.

Размещено на Allbest.ru