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

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

В последнее время все большее внимание привлекают динамические задачи многокритериальной оптимизации, в которых требуется найти эффективные решения задач проектирования динамических систем. Методы анализа таких задач могут быть основаны на использовании методов оптимизации динамических систем, основы которых были заложены J1.C. Понтрягиным и его школой. Близость методов оптимизации динамических систем и многокритериальной оптимизации особенно ясно проявляется при сопоставлении методов аппроксимации множеств достижимости динамических систем, развиваемых в нашей стране наряду со школой JI.C. Понтрягина школами А. Б. Куржанского и Ф. Л. Черноусько, и методов аппроксимации паретовой (недоминируемой) границы в задачах многокритериальной оптимизации, разрабатываемых школой П. С. Краснощекова. Оба упомянутых класса методов основаны на аппроксимации многомерных множеств, так что результаты работ в одной области могут быть применены в другой. Этот факт использован в исследованиях группы А. В. Лотова, проводящихся в ВЦ РАН и ВМиК МГУ и направленных на аппроксимацию и визуализацию выпуклых множеств. Методы аппроксимации множеств достижимости для линейных управляемых систем, разработанные в 70-е годы прошлого века, были затем использованы в многокритериальном методе достижимых целей (МДЦ), в рамках которого аппроксимируется либо множество достижимых критериальных векторов, либо его оболочка Эджворта-Парето (ОЭП), т. е. максимальное множество, имеющее ту же паретову границу. В свою очередь, оптимальные методы полиэдральной аппроксимации ОЭП были в дальнейшем использованы для аппроксимации выпуклых множеств достижимости динамических систем.

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

Применение МДЦ для поиска парето-эффективных решений экономических задач началось еще в семидесятых годах ([26]), а с середины восьмидесятых годов МДЦ используется для поиска парето-эффективных стратегий улучшения состояния окружающей среды ([29], [30]). Другой важной областью применения МДЦ является изучение возможных вариантов технических систем на предпроектной стадии процесса проектирования. Дальнейшее развитие МДЦ связано с его применением в сети Интернет, где метод может быть использован в системах электронной торговли, выбора экологических решений и т. д. ([58]).

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

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

Математическая задача многокритериальной оптимизации выглядит следующим образом. Пусть задано некоторое пространство решений W и пусть критериальное пространство является^{-мерным} линейным пространством Пусть задано X a W — множество возможных допустимых) решений. Пусть связь между решениями и значениями критериев выбора решения устанавливается отображением /: W -> Rd. Будем считать, что лицо, принимающее решение, (ЛПР) заинтересовано в уменьшении значений каждого из d критериев. В таком случае критериальная точка У <= Rd доминирует (по Парето) другую критериальную точку у е Rd, если у'^у, т. е. у.

P (Y) = {у eY :{y'eY:/< у, у’Ф у} = 0}.

Множество P (Y) часто называют паретовой границей, оно характеризует совокупность компромиссов, разумных с точки зрения рассматриваемых критериев, и представляет наибольший интерес для ЛПР, заинтересованных в поиске эффективных решений проблемы. Оболочка Эджворта-Парето множества критериальных векторов имеет вид Y* = Y + Rf, где R* неотрицательный ортант пространства Rd. Поскольку паретова граница ОЭП совпадает с паретовой границей множества Y = / (X), в многокритериальных методах ОЭП можно использовать вместо Y.

Методы поддержки принятия решения, основанные на многокритериальной оптимизации, тем или иным образом дают возможность отбора наиболее предпочтительной точки множества P (Y). Особенностью МДЦ является предварительная аппроксимация множества Y * и дальнейшая визуализация его паретовой границы P (Y) с использованием двумерных сечений аппроксимации Y *.

В диссертации в качестве множеств возможных решений рассматриваются множества достижимости линейной динамической системы х = Ах + u (t), 0.

Как обычно, под множеством достижимости X (t*) системы (0.1)-(0.3) в некоторый момент времени /*е[0,Г] понимается множество концов x (t*) всех траекторий x (t), 0.

Таким образом, возникает следующая задача: пусть заранее по каким-то причинам выбрана последовательность моментов времени 0<.

Хх, Х2,., Хм, аппроксимирующих в заданные моменты времени множества достижимости X{tx), X (t2),., X™, мы можем далее с помощью методов полиэдральной аппроксимации построить аппроксимацию их ОЭП и визуализировать паретовы границы соответствующих множеств. Тем самым можно продемонстрировать зависимость паретовой границы от времени.

К настоящему времени были разработаны различные подходы к аппроксимации множеств достижимости, наиболее известными из которых являются эллипсоидальная аппроксимация и полиэдральная аппроксимация. Методы эллипсоидальной аппроксимации, основанные на аппроксимации отдельным эллипсоидом [40] или пересечением и объединением эллипсоидов, построенных на основе решения систем обыкновенных дифференциальных уравнений [57], [32] дают возможность дать оценку расположения множества достижимости. В отличие от методов эллипсоидальной аппроксимации, методы полиэдральной аппроксимации, предложенные J1.C. Понтрягиным в его предисловии к книге [34], позволяют осуществить аппроксимацию множества достижимости с любой степенью точности. Методы, основанные на идее JI.C. Понтрягина, используют измерение опорной функции множества достижимости. Несмотря на то, что было разработано несколько альтернативных подходов к построению полиэдральной аппроксимации множеств достижимости линейных динамических систем (см., например, [25], [27], [21], [56]), основным практическим средством полиэдральной аппроксимации остаются методы, использующие расчет опорной функции для направлений, выбираемых оптимальным образом.

Поскольку в МДЦ требуется аппроксимировать ОЭП с любой заранее заданной точностью на основе построенной аппроксимации множества достижимости, в данной работе используются методы полиэдральной аппроксимации множеств достижимости, основанные на расчете опорной функции. В книге [34] для расчета опорной функции множеств достижимости предложено использовать принцип максимума для терминальных задач оптимизации со свободным концом. Точность численного расчета опорной функции множеств достижимости линейных динамических систем на основе использования принципа максимума изучалась в работах [37], [13], в которых была доказана сходимость получаемой оценки к точному значению опорной функции. В данной диссертации дается гарантированная оценка погрешности расчета опорной функции. Как и следовало ожидать из работ [63], [45], погрешность расчета опорной функции стремится к нулю с квадратичной скоростью по шагу дискретизации по времени. Важно, что в данной диссертации рассчитывается не только скорость, но и константа сходимости, в формулу расчета которой входит число переключений функции оптимального управления, оцененное в работах [34], [55], [38]. Гарантированная оценка погрешности расчета опорной функции позволяет при использовании методов полиэдральной аппроксимации выпуклых компактных тел [29], [30], [58] конструктивно получить гарантированные внешние и внутренние оценки множеств достижимости линейной динамической системы с любой заданной степенью точности.

Как уже говорилось, методы, использующие расчет опорной функции, обычно направлены на аппроксимацию единственного множества достижимости в некоторый (обычно, конечный) момент времени. В многокритериальных проблемах, рассматриваемых в данной диссертации, требуется построение множеств достижимости в промежуточные моменты времени. В [28] был предложен метод укрупненных шагов, в котором множества достижимости в выбранные моменты времени строятся последовательно, последующее на основе предыдущего. В книге [30] было предложено использовать для этого расчет опорной функции, который для каждого следующего множества X (tk) основан на использовании аппроксимации предыдущего множества X{tk"x) (метод крупных шагов). До настоящего времени метод крупных шагов не был реализован в связи с тем, что не была решена проблема построения оценки погрешности, привносимой из-за такого расчета опорной функции. Эта проблема была подчеркнута, например, в [58].

Гарантированные внешние и внутренние оценки множеств достижимости линейной динамической системы с любой заданной степенью точности, полученные в данной работе, позволили реализовать на практике метод крупных шагов. При этом осуществляется как апостериорное оценивание погрешности в процессе аппроксимации, так и априорное оценивание, позволяющее разумным образом выбрать параметры алгоритмов. Решение этой проблемы особенно важно в связи с возможностью использования последовательности множеств достижимости для анализа паретовой границы в динамических задачах многокритериальной оптимизации, имеющих важное прикладное значение. Кроме того, разработанная техника применима не только для систем типа (0.1)-(0.3), но и для непрерывно-дискретных систем, в которых в моменты времени tx,., tM происходит импульсное воздействие или изменение закона движения. Этим определяется актуальность данной диссертационной работы.

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

Цели диссертационной работы:

1) Разработать методы пошагового построения аппроксимации последовательности множеств достижимости для линейной динамической системы с вычислением погрешности аппроксимации, в том числе с автоматическим выбором шага аппроксимации по времени и точности полиэдральной аппроксимации. В рамках этой задачи потребовалось:

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

• разработать методы аппроксимации терминального множества достижимости с априорной и апостериорной оценками погрешности;

• построить апостериорную оценку погрешности при пошаговой аппроксимации множеств достижимости;

• разработать метод априорного расчета значений параметров аппроксимации для достижения заданной точности аппроксимации.

2) Построить оценки скорости сходимости многогранников наилучшей аппроксимации для тел с частично гладкой границей.

3) Применить метод крупных шагов с оценками погрешности аппроксимации в задаче пошаговой аппроксимации множеств достижимости непрерывно-дискретных систем.

4) Разработать метод визуализации динамической границы Парето для задач многокритериальной оптимизации в случае линейных автономных управляемых систем.

5) Реализовать программное обеспечение для персональных компьютеров, основанное на разработанных методах и провести экспериментальные расчеты.

Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения.

Заключение

.

Результаты диссертационной работы, выносимые на защиту, состоят в следующем.

1) Разработаны методы пошагового построения аппроксимации последовательности множеств достижимости для линейной динамической системы с вычислением погрешности аппроксимации, в том числе с автоматическим выбором шага аппроксимации по времени и точности полиэдральной аппроксимации. В рамках этой задачи:

• доказана гарантированная оценка погрешности для расчета значения опорной функции множества достижимости линейной управляемой системы;

• разработаны методы аппроксимации терминального множества достижимости с априорной и апостериорной оценками погрешности;

• построена апостериорная оценка погрешности при пошаговой аппроксимации множеств достижимости;

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

2) Построены оценки скорости сходимости многогранников наилучшей аппроксимации для тел с частично гладкой границей (совместно с Г. К. Каменевым).

3) Построена модификация метода крупных шагов с оценками погрешности аппроксимации в задаче пошаговой аппроксимации множеств достижимости непрерывно-дискретных систем.

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

5) Реализовано программное обеспечение для персональных компьютеров, основанное на разработанных методах и проведены экспериментальные расчеты.