Методы аппроксимации границы Парето в нелинейных задачах многокритериальной оптимизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Березкин, Вадим Евгеньевич

• Березкин, Вадим Евгеньевич
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Березкин, Вадим Евгеньевич

Оглавление.

Введение.

Глава 1. Некоторые проблемы предпроектной стадии проектирования технических систем.

1.1. Предпроектная стадия процесса проектирования.

1.2. Пример проблемы, возникающей на предпроектной стадии.

1.2.1 Краткое описание модели процесса охлаждения стальной полосы.

1.2.2. Функции потерь.

1.2.3 Проектные решения. Параметры процесса охлаждения.

1.3. Аппроксимация оболочки Эджворта-Парето в нелинейном методе достижимых целей.

Глава 2. Изучение методов аппроксимации оболочки Эджворта-Парето.

2.1. Полнота аппроксимации.

2.1.1. Основные обозначения.

2.1.2. Полнота аппроксимации.

2.2. Упрощенный однофазный алгоритм А1.

2.3. Свойства алгоритма А1.

2.3.1. Конечность А1.

2.3.2. Сходимость А1.

2.3.3. Скорость сходимости А1.

2.3.4. Эффективность А1.

2.4. Упрощенный двухфазный алгоритм А2.

2.5. Полнота аппроксимации для А2.

2.6. Свойства алгоритма А2.

2.6.1. Конечность А2.

2.6.2. Сходимость А2.

2.6.3. Скорость сходимости А2.

2.6.4. Эффективность А2.

2.7. Алгоритм А2 в случае Y°=P(Y).

2.7.1. Скорость сходимости.

2.7.2. Эффективность.

2.8. Упрощенный трехфазный алгоритм A3.

2.9. Полное описание методов аппроксимации.

2.9.1. Однофазный алгоритм.

2.9.2. Двухфазные алгоритмы.

2.9.3. Трехфазные алгоритмы.

2.9.4. Генетический метод «оштукатуривания».

Глава 3. Программное обеспечение метода достижимых целей для нелинейных моделей.

3.1. Реализация однофазного метода в MS Excel.

3.2. Реализация однофазных, двух- и трехфазных методов на языке С++.

3.3. Программный комплекс «Метод достижимых целей».

Глава 4. Эксперименты с модельными задачами.

4.1. Методика проведения экспериментов.

4.1.1. Сравнение методов по результатам аппроксимации.

4.1.2. Попарное сравнение аппроксимаций ОЭП.

4.2. Исследование методов на основе использования функции Шекеля.

4.2.1. Исследования методов на двухкритериальных задачах.

4.2.2. Исследования трех- и пятикритериальных задач.

4.2.3. Сравнение однофазного и трехфазного методов.

4.3. Исследования многоэкстремальной задачи.

4.4. Исследование на функции с многочисленными локальными экстремумами.

4.4.1. Модель с параметром а= 1.

4.4.2. Модель с параметром а= 10.

Введение диссертации (часть автореферата) на тему «Методы аппроксимации границы Парето в нелинейных задачах многокритериальной оптимизации»

Математическое моделирование широко используется для поддержки поиска эффективных решений сложных проблем, в том числе проблем планирования и проектирования. При анализе математических моделей в процессах планирования и проектирования важную роль играют многокритериальные методы, позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым планам, проектным и конструкторским решениям. Среди таких методов важнейшую роль играют методы многокритериальной оптимизации, в которых заранее известно направление улучшения значений отдельных (частных) критериев. В рамках этих методов изучается множество решений, эффективных по Парето, и соответствующая недоминируемая (паретова) граница множества достижимых критериальных векторов [1, 7, 31]. Один из главных подходов современной многокритериальной оптимизации представлен методами, направленными на аппроксимацию паретовой границы множества достижимых критериальных векторов и на дальнейшее информирование лица, принимающего решение (ЛПР) о недоминируемых критериальных векторах ([2, 3, 5, 7, 8, 9, 10, 13, 14).

Одним из методов, основанных на аппроксимации паретовой границы, является метод достижимых целей. Этот метод базируется на идее, сформулированной в работах Н.Н. Моисеева [15] и Г.С. Поспелова [16]: для поддержки выбора наиболее перспективных вариантов в задачах проектирования сложных систем предлагалось использовать визуализацию множества реализуемых характеристик объекта проектирования. Компьютерная визуализация этих многомерных множеств должна помочь конструкторам и проектировщикам оценить потенциальные возможности объекта проектирования, выявить связь различных характеристик объекта и найти его перспективные варианты. В методе достижимых целей [25, 26, 27] описанная идея реализуется с использованием интерактивной визуализации и анимации паретовой границы. Такая визуализация оказывается возможной при предварительной аппроксимации множества достижимых критериальных векторов (или другого, более широкого множества — оболочки Эджворта-Парето (ОЭП) множества достижимых критериальных векторов, являющейся максимальным множеством, имеющим ту же паретову границу) с помощью относительно простых фигур (многогранников, конечного числа конусов и т.д.). Интерактивная визуализация и анимация паретовой границы осуществляется путем расчета и изображения двумерных сечений аппроксимации. ЛПР на основе визуального изучения паретовой границы осознанно выбирает предпочтительное достижимое сочетание значений критериев (достижимую цель), а последующий расчет соответствующего парето-эффективного решения осуществляется компьютером автоматически.

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

Надо подчеркнуть, что результаты, полученные в 1980-1990-х годах были основаны на анализе выпуклых, в том числе и линейных моделей; для этого были разработаны адаптивные итеративные методы полиэдральной аппроксимации выпуклых множеств, асимптотически оптимальные по скорости сходимости и сложности описания аппроксимации, в которых аппроксимирующие многогранные множества строятся с помощью расчета значений опорной функции аппроксимируемого множества ([25, 26, 27]).

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

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

Математически задача многокритериальной оптимизации, рассматриваемая в данной работе, формулируется следующим образом. Пусть заданы «-мерное линейное пространство решений (параметров объекта) R11 и т-мерное линейное пространство Rm критериальных векторов. Пусть связь между решениями и значениями критериев выбора устанавливается заданным отображением (вектор-функцией) /: R" —» Rm, заданным, может быть, алгоритмически. Пусть Хс~R" - заданное множество допустимых решений. Тогда множество достижимых критериальных векторов (также называемое множеством достижимых целей) определяется как Y=J(X). Будем для определенности считать, что в задаче представляет интерес увеличение значения каждого из т критериев при неизменных значениях других (задача многокритериальной максимизации). В этом случае критериальная точка/ б R'" доминирует по Парето критериальную точку у е R'", если / >у, т.е. у\ >у„ i=\,.,m, и у'&у. Недоминируемая по Парето (в дальнейшем, просто недоминируемая или паретова) граница множества Y =j{X), определяемая как множество недомииируемых точек у е Y, в этом случае имеет вид

P(Y)={ye Y: {/ б У:У>у,У*у}=0}.

Под множеством Р(Х) парето-эффективных решений понимается подмножество таких решений х е X, что/(х) е P(Y).

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

Y* = {yeRm:y<Ax),xeX}.

Альтернативное, может быть, более удобное представление ОЭП имеет следующий вид

Y*- Y+ (~R+m), где R+m— неотрицательный конус пространства R"1 (здесь под суммой некоторых множеств А и В подразумевается сумма по Минковскому, т.е. множество {у=а+Ь | аеА, ЬеВ}). Важным свойством множества Y* является то, что оно является максимальным (по включению) множеством, таким что P(Y)= P(Y*). При этом остальные границы ОЭП имеют достаточно простой вид. Таким образом, задача аппроксимации ОЭП близка по своему содержанию к задаче аппроксимации паретовой границы. Аппроксимация ОЭП, в рамках которой паретова граница аппроксимируется как часть границы ОЭП, а не самой паретовой границы — одно из важных отличий МДЦ от остальных методов, направленных непосредственно на аппроксимацию паретовой границы (хотя в некоторых из них, как будет видно далее, уже строили аппроксимацию ОЭП, не формулируя это явно).

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

К первому подходу относятся методы покрытия допустимого множества X шарами, радиусы которых зависят от констант Липшица критериальных функций. Методы такого типа были предложены в [2] на основе обобщения ставшего уже классическим однокритериального метода покрытия, разработанного Ю.Г.Евтушенко в конце 1960х [53, 4]. Метод покрытия требует выполнения условия Липшица для вектор-функции / на всем X с некоторой константой L. Аппроксимация Р(Х) ищется в виде такого внутренне устойчивого (т.е. не содержащего точек, доминируемых другими точками этого множества) конечного множества АаК, называемого е-оптимальным решением, что для любой точки х*еР(Х) найдется точка из А, не худшая ее по всем критериям более чем на е. Отметим, что этот подход предназначен для решения задач относительно малых размерностей пространства решений («<10). Отметим, что множество А порождает две аппроксимации паретовой границы: множество {f{A)+(-R+m)} является внутренней аппроксимацией ОЭП, а множество {(Ду1)+£)+ (-R+"')} - его внешней аппроксимацией, где s - вектор с координатами е.

Ко второму подходу относятся методы, основанные на свертывании критериев в единственный параметрический критерий оптимизации и последующем решении большого числа задач глобальной скалярной оптимизации при различных значениях параметров [8, 13]. Этот подход широко используется в практических задачах. В качестве свертки обычно берется либо расстояние от идеальной точки в метрике Чебышева [13], либо свертка Гермейера [31], либо какие-то их модификации [32]. На основе использования постоянных Липшица можно оценить неточность аппроксимации ([33, 34, 35, 36, 37, 5, 6, 7, 8). Отметим, что, согласно этим оценкам точности аппроксимации, в прикладных задачах для достижения разумной точности требуется решить не реализуемое практически число задач глобальной скалярной оптимизации из-за того, что используемые глобальные оценки постоянных Липшица обычно очень неточны. Кроме того, решение каждой из таких задач глобальной скалярной оптимизации зачастую представляет собой сложную проблему из-за многоэкстремальности оптимизируемых функций. Отметим также примыкающий к этой группе методов теоретический алгоритм второго порядка [38], [39], позволяющий с помощью модифицированной функции Лагранжа учесть сложные функциональные ограничения на множество решений.

К третьему подходу относятся методы случайного поиска - расчет критериальных векторов в случайных (или квазислучайных) точках изХи отбор педоминируемых векторов и соответствующих решений (Parameter Space Investigation, PSI-метод: [10, 11, 12]). Ясно, что при расчете критериальных векторов для достаточно большого числа точек, равномерно распределенных в

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

К этим методам примыкают методы типа «имитированного охлаждения (отжига)», в которых на основании аналогии с физическим процессом остывания строится алгоритм случайного поиска решения, причем поиск лучшего решения осуществляется во все более узкой окрестности текущего решения. Этот подход был распространен на задачи многокритериальной оптимизации [28, 29, 30]. Как и во всех методах случайного поиска, в этом подходе анализ сходимости, за исключением тривиальных утверждений, также не производится.

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

Начало применению генетических алгоритмов для решения задач оптимизации положил Д.Холланд в 1975 г. [40]. Фундаментальный вклад в развитие генетических методов внес Д.Гольдберг [41]. Генетические алгоритмы применялись для решения различных задач оптимизации, в том числе для конструирования технических систем, составления расписаний, маршрутизации транспортных средств, компоновки оборудования, раскроя материалов и др. Идея генетических методов основана на рассмотрении ансамбля хромосом, совершенствующихся в процессе многошаговой процедуры. На каждом шаге происходят случайные изменения (мутации) хромосом, формируются новые хромосомы на основе случайного сочетания пар хромосом, а затем по некоторым правилам отбирается заданное число хромосом, составляющих новое поколение. В последние годы эта идея была использована в задачах многокритериальной оптимизации [14, 43]. В эволюционных методах обычно используются только сравнительные оценки качества аппроксимации для нескольких аппроксимаций паретовой границы или численно построенная аппроксимация сравнивается с уже известной паретовой границей (см. [14, 43]).

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

Разрабатываемые нами методы являются развитием стохастического адаптивного метода аппроксимации неявно заданных невыпуклых множеств, предложенного в [46] и [47], на случай задачи аппроксимации ОЭП (однофазный метод). Для этой задачи, однако, оказалось эффективным использовать комбинирование стохастического метода с локальной оптимизацией и сжатием области поиска (многофазные подходы), распространенные в задачах невыпуклой однокритериальной оптимизации. Синтез предложенных многофазных стохастических адаптивных методов аппроксимации ОЭП с генетическим подходом позволяет строить гибридные методы аппроксимации ОЭП, также рассматриваемые в настоящей работе.

В методах, разрабатываемых в данной работе, присутствуют основные черты всех четырех подходов к аппроксимации паретовой границы, описанных выше. По аналогии с работой [2], а также с более поздней работой [45] используется идея аппроксимации ОЭП объединением многомерных конусов доминирования с вершинами в точках, близких к паретовой границе. Пусть Т -конечное число точек из множества Y-J(X) (база аппроксимации). Тогда в качестве аппроксимации ОЭП берется множество r* = U {y + i-R+y-yzT}, являющееся объединением конечного числа конусов с вершинами в точках множества Т. Главное отличие разрабатываемых методов от методов [2] состоит в том, что нами не используется информация о значениях или наличии констант Липшица и не осуществляется покрытие множества X.

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

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

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

Наконец, в гибридных методах, наряду с другими методами, используется новый генетический метод аппроксимации ОЭП, называемый методом «оштукатуривания». В отличии от обычных многокритериальных генетических методов [14, 43], которые начинают процесс аппроксимации с неэффективных решений и требуют проведения огромного объема вычислительной работы прежде чем будут найдены решения, близкие к парето-оптимальным, метод «оштукатуривания» направлен на улучшение достаточно хорошей аппроксимации, построенной с помощью методов локальной оптимизации и характеризуемой малым числом недоминируемых точек. Одновременно метод «оштукатуривания» придает аппроксимации графически более выразительную форму за счет дополнения исходной аппроксимации большим числом новых промежуточных недоминируемых точек, что делает паретову границу более гладкой.

Последнее свойство метода «оштукатуривания» особенно важно в связи с тем, что центральным шагом метода достижимых целей является визуализация паретовой границы. Насколько нам известно, вопрос о визуализации паретовой границы как целого (а не ее отдельных точек) в невыпуклом случае при более чем двух-трех критериях даже не ставился. В данном исследовании визуализация использует синтез идей, предложенных в [25] для визуализации паретовой границы в выпуклом случае, и идеи об использовании набора конусов для визуализации паретовой границы конечного числа точек [45]. Заранее построенная аппроксимация ОЭП используется для быстрого расчета и изображения на дисплее всевозможных наборов двумерных сечений этого множества в диалоге с пользователем. При этом наложение сечений дает представление о паретовой границе для трех критериев, а возможность анимации трехкритериальной картины позволяет оцепить влияние и других критериев. Пользователь получает представление не только о возможных предельных значениях характеристик объекта, но и о связи величин критериев на паретовой границе (о так называемых критериальных, или эффективных, замещениях).

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Березкин, Вадим Евгеньевич

Вывод

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

Заключение. Основные результаты диссертации, выносимые на защиту

1) В диссертации в рамках метода достижимых целей предложен комплекс методов аппроксимации оболочки Эджворта-Парето для нелинейных многокритериальных задач принятия решений с 3-5 критериями, в том числе: а) однофазные и двухфазные методы (совместно с Г.К. Каменевым и А.В. Лотовым); б) трехфазные методы, основанные на неравномерных выборках, определяемых прообразами точек недоминируемой границы и оценками их значимых окрестностей, построенных на основе использования экстремальных статистик; в) генетический метод, отличающийся тем, что он предназначен для улучшения достаточно точной аппроксимации ОЭП; г) гибридные методы, интегрирующие многофазные методы и генетический метод.

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

3) Разработаны три системы программного обеспечения на персональном компьютере реализующие метод достижимых целей для нелинейных многокритериальных задач в среде MS Excel, в среде MS Windows на основе Windows API, а также в рамках многомашинного программного комплекса «Метод достижимых целей».

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

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

4.5. Заключение

На основе проведенных экспериментов на модельных задачах можно сделать следующие выводы:

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

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

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

4. Трехфазный метод в большинстве задач оказался менее экономичным по числу расчетов вектор-функции/по сравнению с двухфазным.

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

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

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

Глава 5. Использование метода достижимых целей для анализа проблемы выбора параметров оборудования

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

5.1. Построение аппроксимации однофазным методом

Итак, рассматривается задача выбора параметров процесса вторичного охлаждения стали в процессе ее непрерывной выплавки. Как было сказано в первой главе, задача имеет пять критериев (J[,.,J5), при этом критерий J\ при поиске параметров не учитывается. Приведем еще раз смысл каждого из критериев:

• J\ - функция отклонения температуры на поверхности стальной полосы от желаемой температуры;

• Ji — ограничение на температуру поверхности стальной полосы;

• J3 - ограничение на скорость охлаждения поверхности полосы;

• J4 — ограничение на длину жидкой сердцевины полосы;

• J5 — ограничение на минимальное значение в точке разгиба стальной полосы.

Задача имеет 325 управлений (параметров), соответствующих величине напора водяных струй, использующихся для охлаждения полосы стали.

Отметим, что ранее над задачей охлаждения стальной полосы работали K.Miettinen, M.Makela и T.Mannikko [52]. Задача решалась с помощью метода NIMBUS (Nondifferentiable Interactive Multiobjective BUndle-based optimization System) ([59, 60, 61]) и в результате было найдено следующее сочетание критериев:

Jr=2.11708, J2=0, J3=0, J4=0, J5=0.20727. (5.1)

В данной работе мы сравним наши результаты с точкой (5.1), которую будем условно называть точкой Миеттннен,

Прежде, чем описывать аппроксимацию ОЭП на основе многофазных и генетических методов, продемонстрируем результаты применения однофазного метода. В процессе аппроксимации было сделано 40 итераций с объемом контрольной выборки N~ 100 000 точек, итого 4 миллиона точек. Выборочная полнота полученной аппроксимации близка к единице. Точность построенного множества на каждой итерации находится в пределах = 0.02-0.05, причем расстояние до идеальной точки практически не уменьшается. Результаты аппроксимации показаны на рис. 5.1 и 5.2. ё

5.

4.

3.

Qz: у4

11585 ю.зеа 9.013 7 724 6.43? 5.15 3.863 2.57J 1.187 0

Рис. 5.1. Аппроксимация ОЭП, построенная однофазным методом, и точка Миеттинен (помечена на рисунке кружочком). Критерии J2 (у2 на рисунке) и J3 (уЗ) изображены на координатных осях, а критерий J4 (у4) - на цветовой шкале

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

-3. О 3. 6, 9.

Рис. 5.2. Аппроксимация ОЭП, построенная однофазным методом, и точка Миеттинен (помечена на рисунке кружочком). Критерии J5 (у5 на рисунке) и J* (у4) изображены на координатных осях, а критерий Уз (уЗ) - на цветовой шкале

5.2. Построение аппроксимации двухфазными и трехфазными методами

5.2.1. Построение предварительной аппроксимации

База исходной аппроксимации Г0 строилась в два этапа. Сначала была сгенерирована выборка из 10 случайных точек множества X. Для каждой из этих точек были решены четыре задачи локальной минимизации частных критериев J2-J $ в отдельности, т.е. всего 40 задач локальной оптимизации. Из найденных критериальных точек были выбраны недоминируемые, из которых была составлена база предварительной аппроксимации 7оо> содержащая 12 критериальных точек. Были также найдены характерные размеры паретовой границы. В процессе решения 40 указанных задач локальной оптимизации потребовалось рассчитать 111 градиентов целевой функции, т.е. в среднем менее трех расчетов на одну задачу. Кроме того, потребовалось дополнительно рассчитать около 2500 значений оптимизируемых функций, т.е. около 60 расчетов на задачу. Найденные характерные размеры паретовой границы имеют следующую величину: 0£Л<10Д 0<Уз<3.3, 0sA<5.4 и OS/sSl 53. В дальнейшем в функциях полноты и принадлежности использовались относительные величины отклонения от паретовой границы, в качестве которых брались величины, полученные делением исходных значений соответствующих координат на эти диапазоны.

Далее, была проведена одна итерация двухфазного метода, в рамках которой были сгенерирована и локально оптимизирована (с использованием квадратичной свертки) случайная выборка, состоящая из 126 точек. При решении этих задач локальной оптимизации было рассчитано 2092 градиентов оптимизируемых функций, т.е. в среднем несколько менее 17 расчетов градиента на одну задачу оптимизации. Кроме того, потребовалось дополнительно рассчитать около 58 тысяч значений оптимизируемых функций, т.е. около 460 расчетов на задачу. Как видно, локальная оптимизация квадратичной свертки является в среднем значительно более трудоемкой задачей, чем оптимизация одного частного критерия.

Обобщенная двухфазная выборочная полнота т]НФ'М(0) множества (Too)* оказалась равной 0.5 (см. рис. 5.3), а максимальное отклонение полученных критериальных точек от (Too)* составило около 1% от размеров паретовой границы. Оно оказалось равным по порядку величине отклонения найденных точек от идеальной точки. Это показывает, множество (Too)* является весьма посредственной аппроксимацией ОЭП. Базу аппроксимации То составили те недоминируемые критериальные точки, которые отклонялись от (Too)* не менее чем на 70% от максимальной величины отклонения. Таких точек оказалось 17.

Рис. 5.3. График обобщенной выборочной полноты т]нФ'и(е) множества (7оо)*

5.2.2. Анализ влияния параметра Q на процесс аппроксимации двухфазным методом

Параметр Q характеризует условие включения получаемых критериальных точек в новую базу аппроксимации по их отдаленности от аппроксимации ОЭП, полученной на предыдущей итерации. При Q=0 в базу включаются все найденные недоминируемые точки, а при Q=S, где 0<<5<1, в базу включаются только те из найденных точек, которые не ближе к аппроксимации ОЭП, чем брг где р - максимальная величина отклонения выборочных точек от аппроксимации ОЭП (радиус полного покрытия). Были рассмотрены два значения параметра Q, а именно, Q=0 и 6=0.7. За исходную была взята база аппроксимации 7о. Для Q=0 было проведено четыре итерации с выборкой в 149 точек. На рис. 5.4 приведены графики обобщенной двухфазной выборочной полноты TjH^^ie) для построенных множеств (Т\)*, (7г)* и (7з)*. Как видно, выборочная полнота г}нФ'М(0) с каждой итерацией монотонно растет от 0.947 до 0.968, причем для £=0.001 (т.е. £=0.1% от размеров паретовой границы) наблюдается рост величины г}нФ'м(е) от 0.97 до 1. При этом радиус полного покрытия падает от 0.009 на первой итерации (т.е. для множества (Го)*) до 0.001 к четвертой итерации (т.е. для множества (7з)*). Достижение величины е=0.001 было выбрано как условие завершения процесса в связи с тем, что эта величина достаточно мала: она составляла около 20% расстояния до идеальной точки от построенных паретовых границ. Таким образом, аппроксимация (7з)* была признана вполне пригодной для завершения расчета. База аппроксимации 7з состояла из 37 точек, а полученная в процессе оценки аппроксимации (7з)* еще более точная база Г4 - из 41 точки.

Вычислительные затраты были следующими. На одну итерацию, т.е. на оптимизацию 149 точек требовалось в среднем около 2500 расчетов градиента, т.е. в среднем около 17 расчетов градиента на одну задачу локальной оптимизации. Кроме того, потребовалось дополнительно рассчитать около 35 тысяч значений оптимизируемых функций, т.е. около 240 расчетов на задачу. Как видно, локальная оптимизация квадратичной свертки оказалась в среднем столь же трудоемка, что и при построении исходной базы аппроксимации Tq. О

X /

4 000<-004 8 OOOt 004

Рис. 5.4. Графики выборочной полноты т]нФ^(е) для множеств (Ti)*, (7г)* и (7з)* при Q=0

Для Q^O.7 было проведено пять итерации с выборкой в 149 точек. На рис. 5.5 приведены графики обобщенной выборочной полноты т]пФ^(е) для множеств (Г/)*, (Г?)*, (Тз)* и (Т4)*. Как видно, выборочная полнота т]цф'М(0) медленно увеличивается от итерации к итерации с 0.74 до 0.8, причем для £=0.001 выборочная полнота растет от 0.88 до 0.93. При этом радиус полного покрытия падал от 0.09 на первой итерации (т.е. для множества (То)*) до 0.005 к пятой итерации (т.е. для множества (Т4)*). Дальнейшая аппроксимация с 6=0.7 была признана бесперспективной и расчет завершен. База аппроксимации Т4 состояла из 23 точек. Вычислительные затраты оказались приближенно такими же, как и в случае с Q=0. у

Г

J г а. f

О 0 001 0 002 0 003 О ОСИ 0 005 0 006 0.007 0 00$ 0.009 0 02

Рис. 5.5. Графики выборочной полноты 7]/ф'Ы(е) для (Г1)*, (7г)*, (7з)* и (Г4)* при 6=0.7

Проведем теперь непосредственное сравнение аппроксимаций ОЭП, полученных после проведения четырех итераций, т.е. множеств (Г4)*, построенных при 0=0 и <2=0.7. Рассмотрим функции включения, описывающие долю точек одной из аппроксимаций, принадлежащие е-окрестности другой аппроксимации. На рис. 5.6 верхний график описывает функцию включения множества (74)*, построенного при <2=0.7, в £-окрестность множества (/4)*, построенного при Q=0. Нижний график — наоборот, функцию включения множества (Т4)* , построенного при Q=0, в е-окрестность множества (74)*, построенного при Q=0.7.

Г г*

J

1

0 0 002 0 004 0 006 0.008

Рис 5.6. Функции включения для множеств (Г4)* , построенных при Q=0.7 и

Q=0.

Как видно из верхнего графика, множество (/4)*, построенное при Q=0, уже при е, близком к нулю, содержит около 80% точек базы аппроксимации Тц, построенной при Q=0.7, а при £=0.0045 целиком содержит множество (Г4)*, построенное при Q—0.7. В то же время, из нижнего графика следует, что множество (/4)*, построенное при <2=0.7, при £=0 содержит только около 35% точек базы аппроксимации Г4, построенной при <2=0, а целиком содержит множество (Г4)*, построенное при Q=0, только при е=0.0076. Этот анализ также подтверждает, что аппроксимация, построенная при <2=0, значительно превосходит аппроксимацию, построенная при <2=0.7.

Список литературы диссертационного исследования кандидат физико-математических наук Березкин, Вадим Евгеньевич, 2008 год

1. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. Москва: Наука. 1982.

2. Евтушенко Ю.Г., Потапов М.А. Методы численного решения многокритериальных задач // Доклады АН, 1986, том 291 №1. С. 25-29.

3. Евтушенко Ю. Г., Потапов М. А. Численные методы решения многокритериальных задач // Кибернетика и вычислит, техника. 1987. Вып. 3. М.: Наука, С. 209 - 218.

4. Ю. Г. Евтушенко. Численный метод поиска глобального экстремума (перебор на неравномерной сетке). Журнал вычислительной математики и математической физики, Т. 11, N 6, С. 1390-1403.

5. Краснощёкое П. С., Фёдоров В. В., Флёров Ю. А. Элементы математической теории принятия проектных решений // Автоматизация проектирования, 1997, № 1. С. 15-23.

6. Краснощекое П.С., Петров А.А. Принципы построения моделей. Москва: МГУ. 1983.

7. Краснощекое П.С., Петров А.А., Федоров В.В. Информатика и проектирование. Москва: Знание. 1986.

8. Краснощекое П.С., Морозов В.В., Федоров В.В. Декомпозиция в задачах проектирования // Известия АН. Серия Техн. Киб., 1979. № 2. С. 7-17.

9. Соболь И.М., Статников Р.Б. Выбор оптимальных параметров в задачах со многими критериями. Москва: Наука. 1981.

10. Соболь И.М., Статников Р.Б. Наилучшие решения где их искать // Математика и кибернетика, 1/82.

11. Statnikov R. В., Matusov J. Multicriteria Optimization and Engineering. -New Jersey: Chapman and Hall, 1995.

12. Соболь KM. О распределении точек в кубе и сетках интегрирования. // Успехи матем. наук, 1966, 21, №5, С. 271-272.

13. Штойер Р. Многокритериальная оптимизация. М.: Радио и связь, 1992.

14. Deb К. Multi-objective optimization using evolutionary algorithms. -Chichester: Wiley, 2001.

15. Моисеев H.H. Математические задачи системного анализа. Москва: Наука. 1981.

16. Поспелов Г.С., Ириков В.А. Программно-целевое планирование и управление. Москва: Советское радио. 1976.

17. Лотов А.В. Исследование экономических систем с помощью множеств достижимости // Труды международной конференции «Моделирование экономических процессов» (Ереван, апрель 1974). Москва: ВЦ АН СССР. 1975.

18. Лотов А.В. О понятии обобщенных множеств достижимости и их построении для линейных управляемых систем // Доклады АН СССР, 250(5). 1980.

19. Лотов А.В. Анализ потенциальных возможностей экономических систем // экономика и матем. методы, 17(2). 1981.

20. Лотов А.В. Согласование математических моделей с использованием множеств достижимости // Математические методы анализа взаимодействия отраслевых и региональных систем. Москва: Наука. 1983.

21. Лотов А.В. Введение в экономико-математическое моделирование. Москва: Наука. 1984.

22. Лотов А.В. Методы анализа математических моделей управляемых систем на основе построения множества достижимых значений показателей качества управления. Дис. на соискан. учен. степ. докт. физ.-мат. наук. Москва: ВЦ АН СССР. 1986.

23. Lotov A.V., Chernykh O.L., Hellman О. Multiple Objective Analysis of Long-Term Development Strategies for a National Economy // European Journal of Operational Research. 1992. V.56. No.2.

24. Lotov A., Bushenkov V., Chernykh O. Multi-criteria DSS for River Water Quality Planning // Microcomputers in Civil Engineering. 1996.

25. Лотов A.B., Бушенков B.A., Каменев Г.К., Черных О.Л. Компьютер и поиск компромисса. Метод достижимых целей. М.: Наука, 1997.

26. Лотов А.В., Бушенков В.А., Каменев Г.К. Метод достижимых целей. -Lewiston, NY: Mellen Press, 1999.

27. Lotov A. V., Bushenkov V. A., Kamenev G. K. Interactive Decision Maps. Approximation and Visualization of Pareto Frontier. Boston: Kluwer Academic Publishers, 2004.2829,3033,34,353839,40,

28. Chipperfield A. J., Whideborn J. F., Fleming P. J. Evolutionary algorithms and Simulated Annealing for MCDM // Multieriteria Decision Making: Advances in MCDM Models, Algorithms, Theory, and Applications. -Boston: Kluwer Academic Publishers, 1999.

29. Suppaptnarm A., Steffen К .A., Parks G. 71, and Clarkson P. J. Simulated Annealing: An alternative approach to true multiobjective optimization // Engineering Optimization. 2000. V. 33(1). P. 59 85.

30. Kubotani H., Yoshimura K. Performance evaluation of acceptance probability functions for multiobjective simulated annealing // Computers and Operations Research. 2003. V. 30, P. 427 442.

31. Гермейер Ю.Б. Исследование операций. M.: Наука, 1970.

32. Wierzbicki А. (1981) A mathematical basis for satisficing decision making //

33. Organizations: Multiple Agents with Multiple Criteria, ed. by J. Morse. Berlin:1. Springer.

34. Нефедов B.H. Методы регуляризации многокритериальных задач оптимизации // М. МАИ, 1984.

35. Нефедов В. Н. Об аппроксимации множества Парето // ЖВМиМФ. 1984. Т. 24(7). С. 993- 1007.

36. Нефедов В. Н. Об аппроксимации множества оптимальных по Парето решений //ЖВМиМФ. 1986. Т. 26(2). С. 163 176.

37. Жадан В.Г. Метод параметризации целевых функций в условной многокритериальной оптимизации // Ж. вычисл. матем. и матем. физ. 1986, Т.26, №2, 177-189.

38. Жадан В.Г. Метод модифицированной функции Лагранжа для задач многокритериальной оптимизации // Ж. вычисл. матем. и матем. физ. 1988, Т.28, №11, С. 1603-1618.

39. Holland J. "Adaptation in Natural and Artificial Systems", Univ. of Michigan Press, 1975.

40. Goldberg, D. E. "Genetic Algorithms in Search, Optimization, and Machine Learning", Addison-Welsey, 1989.

41. Schott J. "Fault tolerant design using single and multi-criteria genetic algorithm optimization." Master's thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology. 1995.

42. Zitzler, E., L. Thiele, M. Laumanns, С. M. Fonseca, and V. Grunert da Fonseca (2003). Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation 7 (2), 117-132.

43. Бушепков B.A., Гусев Д.И., Каменев Г.К., Лотов А.В., Черных O.JI. Визуализация множества Парето в многомерной задаче выбора // Доклады Академии наук. 1994. Т.335. N 5. С. 567-569.

44. Каменев Г.К., Кондратьев Д.Л. Об одном методе исследования незамкнутых нелинейных моделей // Математическое моделирование, 1992, №3, 105-118.

45. Каменев Г. К. Аппроксимация вполне ограниченных множеств методом глубоких ям // Ж. вычисл. матем. и матем. физ. 2001. Т. 41. № 11. С. 1751-1760.

46. А.Н. Ширяев Вероятность. М. «Наука». 1980.

47. Колмогоров А.Н., Тихомиров В.М. ^-энтропия и ^-емкость множеств в функциональных пространствах // Успехи мат. наук. 1959, Т. 14, No. 2, С. 3-86.

48. А.Н.Колмогоров, С.В.Фомин Элементы теории функций и функционального анализа. М.: Наука, 1976.

49. Е. Laitinen and P. Neittaanmaki. "On Numerical Solution of the Problem Connected with the Control of the Secondary Cooling in the Continuous Casting Process", Control Theory and Adv. Tech., vol. 4, pp. 285-305, 1988.

50. К. Miettininen., M.M. Makela, and T. Mannikko. "Optimal Control of Continuous Casting by Nondifferentiable Multiobjective Optimization", Computational Optimization and Applications, vol. 11, pp. 177-194, 1988.

51. Horst, R., and Pardalos, P.M. Handbook on Global Optimization. Dordrecht, NL: Kluwer, 1995.

52. Жиглявский А. А., Жилинскас А.Г. Методы поиска глобального экстремума. М.: Наука, 1991.

53. Хохлов М.А. «Информационная технология и инструментальная система математического моделирования экономики "Экомод"», диссертация на соискание ученой степени кандидата физико-математических наук, М.: ВЦ РАН, 2007.

54. Ю.Н. Павловский, Н.В. Белотелое, Ю.И. Бродский Имитационное моделирование. Москва. Издательский центр «Академия». 2008.

55. Лотов А.В., Каменев Г.К, Березкин В.Е. Аппроксимация и визуализация паретовой границы для невыпуклых многокритериальных задач. // ДАН. Т. 386. №6. с.с. 1-4. 2002.

56. Zitzler, Е., L. Thiele, М. Laumanns, С. М. Foneseca, andV. Grunert da Fonseca (2003). Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation 7 (2), 117-132.

57. K.Miettinen and M.M.Makela "Interactive Bundle-Based Method for Nondifferentiable Multiobjective Optimization: NIMBUS", Optimization, vol. 34, pp. 231-246, 1995.

58. K.Miettinen and M.M. Makela "Interactive Method NIMBUS for Nondifferentiable Multiobjective Optimization Problems", in Multicriteria Analysis, J.Climaco (Ed.), Springer-Verlag: Berlin-Heidelberg, pp. 310-319, 1997.

59. K.Miettinen, M.M.Makela and R.A.E. Makinen "Interactive Multiobjective Optimization System NIMBUS applied to Nonsmooth Structural Design Problems", in System Modelling and Optimization, J. Dolezal, J.Fidler (Eds.), pp. 397-385, 1996.