Оптимизация

     Оптимизация

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

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

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

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

     И структурный, и параметрический синтез объектов может осуществляться при помощи оптимизационных алгоритмов: структурный синтез – при помощи методов дискретного математического программирования; параметрический – непрерывного; структурно-параметрический – при помощи алгоритмов дискретно-непрерывного математического программирования.

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

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

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

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

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

     Литература

1. Батищев Д.И. Методы оптимального проектирования. М. Радио и связь 1984г.
2. Батищев Д.И. Поисковые методы оптимального проектирования. М.: Сов. Радио, 1975.
3. Химмельблау Д. Прикладное нелинейное программирование. Пер. с англ. Мир, М., 1975.
4. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.
5. Сушков Ю.А. Об одном способе организации случайного поиска. Автоматика и вычислительная техника, 1974, № 6, 41-48.
6. Фиакко А., Мак-Кормик Г. Нелинейное прогаммирование. Методы последовательной безусловной минимизации. Пер. с англ. М.: Мир, 1972.
7. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. М.: Наука, 1981.
8. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.

     Математическое  программирование

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

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

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

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

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

     Наиболее  популярными локальными алгоритмами  нулевого порядка (поисковыми алгоритмами) являются Роземброка (вращающихся координат), деформируемого многогранника, Хука-Дживса.

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

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

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

5.1 Постановка задачи  векторной оптимизации

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

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

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

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

Под многокритериальной задачей зачастую понимают не собственно вербальное  описание задачи, а ее модель, а именно: «многокритериальная  задача – математическая модель принятия оптимального решения по нескольким критериям. Эти критерии могут отражать оценки различных качеств объекта или процесса, по поводу которых принимается решение».

Формально многокритериальная задача  как модель задается  в виде:           

где D - множество допустимых решений.  F(x) – векторная функция векторного аргумента x,  которую можно представить как F(x)={f₁(x), f₂(x), … , f_k(x) },      где f₁(x), f₂(x), … , f_k(x) – скалярные функции векторного аргумента x, каждая их которых является математическим выражением одного критерия оптимальности.   Так как в данной модели используется векторная целевая функция, ее зачастую называют задачей векторной оптимизации. Очевидно, что задача (5.1) не принадлежит классу задач математического программирования, т.к.модели      этого класса задач содержат всегда только одну целевую функцию векторного аргумента. 

 
Иначе задачу  (5.1) можно переписать в виде:    

Сущность поставленной задачи состоит в нахождеии такого ее допустимого решения, т.е. }, которое в том или ином смысле максимизирует (минимизирует) значения всех  целевых функций f_i(x), i=1,k.  Существование решения, буквально максимизирующего все целевые функции, является редким исключением. (Если вспомнить пример о поиске одновременно очень качественной и очень дешевой покупки, то становится понятным, что нахождение такого решения – редкая удача, но, гораздо более часто,  это неразрешимая задача).

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

Задача векторной  оптимизации в общем случае не имеет    строго математического математического   решения.  Для получения того или иного ее решения  необходимо использовать дополнительную субъективную информацию специалиста в данной предметной области, которого принято называть лицом принимающим решение (ЛПР), в английском языке - decision maker. Это означает, что при решении задачи разными специалистами с привлечением различных источников информации, скорей всего будут получены различные ответы.