Содержание к диссертации
Введение
Глава 1. Некоторые проблемы предпроектной стадии проектирования технических систем 22
1.1. Предпроектная стадия процесса проектирования 22
1.2. Пример проблемы, возникающей на предпроектной стадии 23
1.2.1 Краткое описание модели процесса охлаждения стальной полосы ... 24
1.2.2. Функции потерь 28
1.2.3 Проектные решения. Параметры процесса охлаждения 30
1.3. Аппроксимация оболочки Эджворта-Парето в нелинейном методе
достижимых целей 31
Глава 2. Изучение методов аппроксимации оболочки Эджворта-Парето 43
2.1. Полнота аппроксимации 43
2.1.1. Основные обозначения 43
2.1.2. Полнота аппроксимации 44
2.2. Упрощенный однофазный алгоритм А1 48
2.3. Свойства алгоритма А1 48
2.3.1. Конечность А1 48
2.3.2. Сходимость А1 49
2.3.3. Скорость сходимости А1 50
2.3.4. Эффективность А1 53
2.4. Упрощенный двухфазный алгоритм А2 55
2.5. Полнота аппроксимации для А2 56
2.6. Свойства алгоритма А2 59
2.6.1. Конечность А2 59
2.6.2. Сходимость А2 60
2.6.3. Скорость сходимости А2 60
2.6.4. Эффективность А2 63
2.7. Алгоритм А2 в случае f=P{Y) 64
2.7.1. Скорость сходимости 64
2.7.2. Эффективность 65
2.8. Упрощенный трехфазный алгоритм A3 67
2.9. Полное описание методов аппроксимации 68
2.9.1. Однофазный алгоритм 68
2.9.2. Двухфазные алгоритмы 69
2.9.3. Трехфазные алгоритмы 71
2.9.4. Генетический метод «оштукатуривания» 72
Глава 3. Программное обеспечение метода достижимых целей для нелинейных моделей 76
3.1. Реализация однофазного метода в MS Excel 77
3.2. Реализация однофазных, двух- и трехфазных методов на языке C++ 82
3.3. Программный комплекс «Метод достижимых целей» 89
Глава 4. Эксперименты с модельными задачами 97
4.1. Методика проведения экспериментов 97
4.1.1. Сравнение методов по результатам аппроксимации 97
4.1.2. Попарное сравнение аппроксимаций ОЭП 98
4.2. Исследование методов на основе использования функции Шекеля 100
4.2.1. Исследования методов на двухкритериальных задачах 101
4.2.2. Исследования трех- и пятикритериальных задач 114
4.2.3. Сравнение однофазного и трехфазного методов 124
4.3. Исследования многоэкстремальной задачи 127
4.4. Исследование на функции с многочисленными локальными экстремумами 137
4.4.1. Модель с параметром а=\ 139
4.4.2. Модель с параметром а=10 145
4.5. Заключение 156
Глава 5. Использование метода достижимых целей для анализа проблемы выбора параметров оборудования 158
5.1. Построение аппроксимации однофазным методом 158
5.2. Построение аппроксимации двухфазными и трехфазными методами... 160
5.2.1. Построение предварительной аппроксимации 160
5.2.2. Анализ влияния параметра Q на процесс аппроксимации двухфазным методом 162
5.2.3. Сравнение процесса аппроксимации паретовой границы с использованием двух- и трехфазного методов 165
5.2.4. Изучение комбинаций двухфазных и трехфазных методов 170
5.3. Применение генетического метода 173
Заключение 180
Литература
- Краткое описание модели процесса охлаждения стальной полосы
- Упрощенный однофазный алгоритм А1
- Реализация однофазных, двух- и трехфазных методов на языке C++
- Исследование методов на основе использования функции Шекеля
Введение к работе
Математическое моделирование широко используется для поддержки поиска эффективных решений сложных проблем, в том числе проблем планирования и проектирования. При анализе математических моделей в процессах планирования и проектирования важную роль играют многокритериальные методы, позволяющие учесть противоречивые требования, предъявляемые к рассматриваемым планам, проектным и конструкторским решениям. Среди таких методов важнейшую роль играют методы многокритериальной оптимизации, в которых заранее известно направление улучшения значений отдельных (частных) критериев. В рамках этих методов изучается множество решений, эффективных по Парето, и соответствующая недоминируемая (паретова) граница множества достижимых критериальных векторов [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] был предложен и исследован стохастический адаптивный метод аппроксимации множества всех достижимых критериальных векторов системой шаров. Такой подход, однако, не был предназначен для аппроксимации самой паретовой границы и давал о ней лишь общее представление.
Таким образом, использование МДЦ в нелинейном невыпуклом случае до последнего времени не имело широкого распространения, что, в первую очередь, связано с недостаточной развитостью методов аппроксимации множества достижимых критериальных векторов (или его ОЭП) в нелинейном случае, для которого эти множества обычно являются невыпуклыми. В то же время, потенциально важной областью применения МДЦ является его
использование в процессе проектирования и анализа сложных технических систем, описываемых, как правило, нелинейными математическим моделями, в том числе технических и производственных систем, а также при анализе нелинейных экономических моделей. Этот факт определяет актуальность данной диссертационной работы, посвященной разработке вычислительных методов аппроксимации оболочки Эджворта-Парето множества достижимых критериальных векторов с целью дальнейшей визуализации паретовой границы в нелинейных невыпуклых задачах многокритериальной оптимизации с числом критериев от трех до семи.
Математически задача многокритериальной оптимизации,
рассматриваемая в данной работе, формулируется следующим образом. Пусть заданы и-мерное линейное пространство решений (параметров объекта) R" и т-мерное линейное пространство Rm критериальных векторов. Пусть связь между решениями и значениями критериев выбора устанавливается заданным отображением (вектор-функцией) /: R" -»Rm, заданным, может быть, алгоритмически. Пусть XcR" — заданное множество допустимых решений. Тогда множество достижимых критериальных векторов (также называемое множеством достижимых целей) определяется как Y=J(X). Будем для определенности считать, что в задаче представляет интерес увеличение значения каждого из т критериев при неизменных значениях других (задача многокритериальной максимизации). В этом случае критериальная точка у є R'" доминирует по Парето критериальную точку у є R'", если у'>у, т.е. у', >у„ i=\,...,m, и у1 Фу. Недоминируемая по Парето (в дальнейшем, просто недоминируемая или паретова) граница множества Y=j{X), определяемая как множество недоминируемых точек у є Y, в этом случае имеет вид
P(Y)={y є 7: {у' є Y-.y>y,y'*y} = 0}.
Под множеством Р(Х) парето-эффективных решений понимается подмножество таких решений х є X, что Дх) е P(Y).
Множество P(Y) характеризует совокупность компромиссов, разумных с точки зрения рассматриваемых критериев, и представляет наибольший интерес для пользователя (скажем, конструктора или проектировщика сложной системы). Методы поддержки принятия решения, основанные на концепции многокритериальной оптимизации, представляют пользователю ту или иную
информацию о точках множества P(Y) и дают возможность отбора наиболее предпочтительных точкек этого множества, по которым уже затем находятся предпочтительные решения. В МДЦ в нелинейном случае аппроксимируется оболочка Эджворта-Парето, определяемая в задаче многокритериальной максимизации как
Y* = {yeRm:y
Альтернативное, может быть, более удобное представление ОЭП имеет следующий вид
У=У+(-Л+я)» где R+m— неотрицательный конус пространства R"' (здесь под суммой некоторых множеств А я В подразумевается сумма по Минковскому, т.е. множество {у=а+Ь | аеА, ЬєВ}). Важным свойством множества Y является то, что оно является максимальным (по включению) множеством, таким что P(Y)= P(Y). При этом остальные границы ОЭП имеют достаточно простой вид. Таким образом, задача аппроксимации ОЭП близка по своему содержанию к задаче аппроксимации паретовой границы. Аппроксимация ОЭП, в рамках которой паретова граница аппроксимируется как часть границы ОЭП, а не самой паретовой границы — одно из важных отличий МДЦ от остальных методов, направленных непосредственно на аппроксимацию паретовой границы (хотя в некоторых из них, как будет видно далее, уже строили аппроксимацию ОЭП, не формулируя это явно).
В методах аппроксимации паретовой границы в нелинейных задачах многокритериальной оптимизации можно выделить четыре основных подхода, которые разбиваются на два важных больших класса. Первый из классов включает методы, основанные на использовании постоянных Липшица либо в самих методах, либо при их изучении. В методах второго класса наличие постоянных Липшица не предполагается и не используется.
К первому подходу относятся методы покрытия допустимого множества X шарами, радиусы которых зависят от констант Липшица критериальных функций. Методы такого типа были предложены в [2] на основе обобщения ставшего уже классическим однокритериального метода покрытия, разработанного Ю.Г.Евтушенко в конце 1960х [53, 4]. Метод покрытия требует выполнения условия Липшица для вектор-функции / на всем X с некоторой
константой L. Аппроксимация Р(Х) ищется в виде такого внутренне устойчивого (т.е. не содержащего точек, доминируемых другими точками этого множества) конечного множества A
Ко второму подходу относятся методы, основанные на свертывании критериев в единственный параметрический критерий оптимизации и последующем решении большого числа задач глобальной скалярной оптимизации при различных значениях параметров [8, 13]. Этот подход широко используется в практических задачах. В качестве свертки обычно берется либо расстояние от идеальной точки в метрике Чебышева [13], либо свертка Гермейера [31], либо какие-то их модификации [32]. На основе использования постоянных Липшица можно оценить неточность аппроксимации ([33, 34, 35, 36, 37, 5, 6, 7, 8). Отметим, что, согласно этим оценкам точности аппроксимации, в прикладных задачах для достижения разумной точности требуется решить не реализуемое практически число задач глобальной скалярной оптимизации из-за того, что используемые глобальные оценки постоянных Липшица обычно очень неточны. Кроме того, решение каждой из таких задач глобальной скалярной оптимизации зачастую представляет собой сложную проблему из-за многоэкстремальности оптимизируемых функций. Отметим также примыкающий к этой группе методов теоретический алгоритм второго порядка [38], [39], позволяющий с помощью модифицированной функции Лагранжа учесть сложные функциональные ограничения на множество решений.
К третьему подходу относятся методы случайного поиска — расчет критериальных векторов в случайных (или квазислучайных) точках изХи отбор недоминируемых векторов и соответствующих решений (Parameter Space Investigation, PSI-метод: [10, 11, 12]). Ясно, что при расчете критериальных векторов для достаточно большого числа точек, равномерно распределенных в
X, можно получить аппроксимацию паретовой границы с любой степенью точности. С другой стороны, ясно, что для получения достаточно точной аппроксимации паретовой границы число таких точек в многокритериальных задачах должно быть нереализуемым на практике, если размерность пространства решений велика, а значения вектор-функции fix) подвержены колебаниям. В таких методах случайного поиска оценка качества аппроксимации обычно не осуществляется.
К этим методам примыкают методы типа «имитированного охлаждения (отжига)», в которых на основании аналогии с физическим процессом остывания строится алгоритм случайного поиска решения, причем поиск лучшего решения осуществляется во все более узкой окрестности текущего решения. Этот подход был распространен на задачи многокритериальной оптимизации [28, 29, 30]. Как и во всех методах случайного поиска, в этом подходе анализ сходимости, за исключением тривиальных утверждений, также не производится.
К четвертому подходу относятся эволюционные методы одновременного поиска большого числа точек, близких к паретовой границе. Методы основаны на биологических аналогиях. В настоящее время активно изучаются и развиваются три основные подгруппы эволюционных методов -генетические методы, методы, имитирующие поведение стаи птиц (Particles Swarm Optimization), и методы, имитирующие поведение колонии муравьев (Ant Colony Optimization).
Начало применению генетических алгоритмов для решения задач оптимизации положил Д.Холланд в 1975 г. [40]. Фундаментальный вклад в развитие генетических методов внес Д.Гольдберг [41]. Генетические алгоритмы применялись для решения различных задач оптимизации, в том числе для конструирования технических систем, составления расписаний, маршрутизации транспортных средств, компоновки оборудования, раскроя материалов и др. Идея генетических методов основана на рассмотрении ансамбля хромосом, совершенствующихся в процессе многошаговой процедуры. На каждом шаге происходят случайные изменения (мутации) хромосом, формируются новые хромосомы на основе случайного сочетания пар хромосом, а затем по некоторым правилам отбирается заданное число хромосом, составляющих новое поколение. В последние годы эта идея была использована в задачах
многокритериальной оптимизации [14, 43]. В эволюционных методах обычно используются только сравнительные оценки качества аппроксимации для нескольких аппроксимаций паретовой границы или численно построенная аппроксимация сравнивается с уже известной паретовой границей (см. [14, 43]).
Подчеркнем, что к первому классу методов (с использованием постоянной Липшица) относятся методы первых двух подходов, а ко второму классу (без использования постоянной Липшица) - методы третьего и четвертого подходов. В данной работе предлагаются и изучаются методы аппроксимации ОЭП, относящиеся ко второму классу методов - в них не используются постоянные Липшица критериальных функций. Более того, предполагается, что вектор-функция / может быть задана с помощью вычислительного модуля («черного ящика»), структура которого не известна или не может быть использована при решении задачи многокритериальной оптимизации. Вычислительный модуль может, скажем, осуществлять имитацию динамического процесса или решать краевую задачу математической физики. Так, в данной работе в качестве приложения методов исследуется задача оптимизации параметров оборудования, предназначенного для охлаждения стали в процессе ее непрерывной разливки. В этой задаче требуется найти оптимальные краевые условия в задаче, решение которой (в том числе и значения вектор-функции f) находятся с помощью некоторого имеющегося вычислительного модуля, который по заданным краевым условиям решает краевую задачу в частных производных и рассчитывает значения критериев. В таком случае уже не приходится надеяться на получение информации о величине или даже наличии констант Липшица. Поэтому в методах, разрабатываемых в данной работе, предположения о константах Липшица критериальных функций рассматриваемых моделей в дальнейшем не делаются. Это является важнейшим требованием к разрабатываемым методам, определяющим многие их черты, в частности, использование статистических методов оценки качества аппроксимации.
Разрабатываемые нами методы являются развитием стохастического адаптивного метода аппроксимации неявно заданных невыпуклых множеств, предложенного в [46] и [47], на случай задачи аппроксимации ОЭП (однофазный метод). Для этой задачи, однако, оказалось эффективным использовать комбинирование стохастического метода с локальной
оптимизацией и сжатием области поиска (многофазные подходы), распространенные в задачах невыпуклой однокритериальной оптимизации. Синтез предложенных многофазных стохастических адаптивных методов аппроксимации ОЭП с генетическим подходом позволяет строить гибридные методы аппроксимации ОЭП, также рассматриваемые в настоящей работе.
В методах, разрабатываемых в данной работе, присутствуют основные черты всех четырех подходов к аппроксимации паретовои границы, описанных выше. По аналогии с работой [2], а также с более поздней работой [45] используется идея аппроксимации ОЭП объединением многомерных конусов доминирования с вершинами в точках, близких к паретовои границе. Пусть Т — конечное число точек из множества Y=fiX) (база аппроксимации). Тогда в качестве аппроксимации ОЭП берется множество
г* = и {y + (-R+myyzT},
являющееся объединением конечного числа конусов с вершинами в точках множества Т. Главное отличие разрабатываемых методов от методов [2] состоит в том, что нами не используется информация о значениях или наличии констант Липшица и не осуществляется покрытие множествах.
Важнейшим элементом данной работы является генерирование случайных точек множества допустимых решений X аналогично тому, как это осуществляется в методах третьей группы. Однако, в отличие от методов третьей группы, мы даем статистическую оценку качества аппроксимации ОЭП и формулируем правила остановки процесса аппроксимации, а также дополняем случайный поиск процедурами оптимизации сверток критериев аналогично методам второй группы. В то же время, в отличие от методов второй группы, мы решаем задачи не глобальной, а локальной оптимизации, причем параметры свертки выбираются не из совокупности сверток, сформированной заранее, а на основе требований адаптации свертки к исходной точке процесса локальной оптимизации.
Сочетание стохастических методов поиска оптимального решения с методами локальной однокритериальной оптимизации сверток критериев дополняется адаптивным случайным поиском, развивающим идеи многокритериального «имитированного охлаждения» [28, 29, 30] и состоящем в сжатии области поиска на основе обработки информации о прообразах точек паретовои границы.
Подчеркнем, что использование статистического оценивания качества построенной аппроксимации ОЭП, основанного на генерировании случайных точек множества X, является важной особенностью разработанных методов. Именно применение статистических оценок позволяет отказаться от использования оценки качества аппроксимации паретовой границы на основе постоянных Липшица. Пригодная для использовании на практике оценка качества аппроксимации множества достижимых критериальных векторов в невыпуклых нелинейных задачах многокритериальной оптимизации впервые была предложена в работе [46]. В настоящей работе используются более сильные оценки качества аппроксимации, предложенные в [47]. Для оценки качества аппроксимации ОЭП потребовалась модернизация этой оценки на основе решения задач скалярной оптимизации.
Наконец, в гибридных методах, наряду с другими методами, используется новый генетический метод аппроксимации ОЭП, называемый методом «оштукатуривания». В отличии от обычных многокритериальных генетических методов [14, 43], которые начинают процесс аппроксимации с неэффективных решений и требуют проведения огромного объема вычислительной работы прежде чем будут найдены решения, близкие к парето-оптимальным, метод «оштукатуривания» направлен на улучшение достаточно хорошей аппроксимации, построенной с помощью методов локальной оптимизации и характеризуемой малым числом недоминируемых точек. Одновременно метод «оштукатуривания» придает аппроксимации графически более выразительную форму за счет дополнения исходной аппроксимации большим числом новых промежуточных недоминируемых точек, что делает паретову границу более гладкой.
Последнее свойство метода «оштукатуривания» особенно важно в связи с тем, что центральным шагом метода достижимых целей является визуализация паретовой границы. Насколько нам известно, вопрос о визуализации паретовой границы как целого (а не ее отдельных точек) в невыпуклом случае при более чем двух-трех критериях даже не ставился. В данном исследовании визуализация использует синтез идей, предложенных в [25] для визуализации паретовой границы в выпуклом случае, и идеи об использовании набора конусов для визуализации паретовой границы конечного числа точек [45]. Заранее построенная аппроксимация ОЭП используется для
быстрого расчета и изображения на дисплее всевозможных наборов двумерных сечений этого множества в диалоге с пользователем. При этом наложение сечений дает представление о паретовои границе для трех критериев, а возможность анимации трехкритериальной картины позволяет оценить влияние и других критериев. Пользователь получает представление не только о возможных предельных значениях характеристик объекта, но и о связи величин критериев на паретовои границе (о так называемых критериальных, или эффективных, замещениях).
Синтез различных подходов в одном гибридном методе позволил сделать его достаточно гибким методом аппроксимации ОЭП и создать программное обеспечение персональных компьютеров, позволяющее перенести метод достижимых целей на нелинейные модели с относительно большим числом переменных (до нескольких сотен), заданные вычислительным модулем. Это позволяет использовать такие методы и программное обеспечение в задачах проектирования сложных систем.
Диссертация состоит из введения, пяти глав, заключения и списка литературы.
В первой главе рассматривается проблема поддержки принятия конструкторских решений на предпроектной стадии процесса проектирования и роль многокритериальных методов в этом процессе. Далее приводится пример многокритериальной задачи, которая должна быть решена в процессе проектирования: дается представление о задаче охлаждения стали в процессе разработки и оптимизации установки для ее непрерывной разливки. Эта задача может быть решена на основе использования нелинейной математической модели охлаждения стали, которая была построена ранее в [51]. Ее многокритериальная формулировка была дана в [52], где с помощью сведения к однокритериальной задаче была найдена единственная критериальная точка, близкая, по мнению авторов, к паретовои границе. В гл. 1 показывается, что задача выбора параметров системы охлаждения является нелинейной задачей многокритериальной оптимизации, в которой математическая модель реализована в виде вычислительного модуля, имеющего 325 входных параметров проектируемой системы охлаждения. Выходом вычислительного модуля являются значения пяти показателей, один из которых описывает качество стали при выполненных технологических ограничениях, а четыре
остальных характеризуют нарушения технологических ограничений. Поскольку исследования, проведенные в [52], привели к выводу о том, что одновременное выполнение всех технологических ограничений невозможно, в работе была поставлена задача многокритериальной оптимизации, состоящая в одновременной минимизации четырех критериев, характеризующих отклонения от рассмотренных технологических ограничений. Таким образом, рассматриваемая задача является задачей многокритериальной оптимизации с четырьмя критериями и 325 параметрами решения. В гл. 5 диссертационной работы на основе этой задачи показываются возможности применения гибридных методов аппроксимации оболочки Эджвотра-Парето в процессе проектирования.
Далее в первой главе дается качественное описание стохастических адаптивных методов аппроксимации ОЭП, включающих в себя однофазный, двухфазные, трехфазные и генетический методы аппроксимации. Сочетание различных подходов к решению задач оптимизации в форме так называемых многофазных методов интенсивно применяется в случае однокритериальных задач [53]. В данной работе многофазные методы разрабатываются для задач многокритериальной оптимизации. Далее, осуществляется интеграция построенных многофазных методов с многокритериальным генетическим методом «оштукатуривания», в результате чего формируются гибридные методы аппроксимации ОЭП.
Начало описания методов посвящено способам оценки качества аппроксимации ОЭП и правилам остановки алгоритмов, предлагаемым в работе. Отсутствие информации о постоянной Липшица приводит к тому, что эту задачу невозможно решить достоверно и приходится прибегать к статистическим оценкам. Следует подчеркнуть, что статистические оценки предлагаемого типа до последнего времени практически отсутствовали (см. [14, 43]). Единственный известный подход был предложен в [44]), однако он применим только в двухмерном случае. В данной работе предлагается набор показателей качества аппроксимации, которые хотя и не решают задачу полностью, дают возможность оценить динамику процесса аппроксимации и являются удобными правилами остановки алгоритмов.
Показатели качества аппроксимации, предлагаемые в данной работе, базируются на понятии полноты аппроксимации, которая представляет собой
вероятность того, что образ точки, случайно взятой в X, будет принадлежать построенной аппроксимации ОЭП. Как уже говорилось, эти оценки развивают идею, предложенную в работе [46]. Эмпирический расчет полноты строится на генерировании случайной выборки точек в X и построении доверительного интервала для искомой величины. Введя метрику в пространстве R"', можно определить функцию полноты аппроксимации, равную вероятности того, что образ точки, случайно взятой в X, будет принадлежать заданной е-окрестности (е>0) аппроксимации ОЭП. Эта функция характеризует качество аппроксимации более полно, чем исходная величина полноты. Экспериментально определяется выборочная функция полноты аппроксимации, причем для каждого отдельного є верна упомянутая выше оценка доверительного интервала. Отметим, что выборочная функция полноты является монотонно неубывающей функцией є и может быть легко рассчитана. Она показывает для всех є > О, каких усилий стоит улучшение ^-аппроксимаций ОЭП с помощью генерирования случайных точек. Поэтому рассмотрение графика выборочной функции полноты дает информацию пользователю о том, не следует ли завершить работу алгоритма аппроксимации. Остановку процесса аппроксимации можно и автоматизировать, заменив человеко-машинный анализ графика выборочной функции полноты проверкой значения некоторой ее характеристики. На практике наиболее удобной характеристикой оказался радиус полного покрытия - минимальная величина є, для которой выборочная полнота равна единице (т.е. образы всех сгенерированных точек X принадлежат этой ^-окрестности аппроксимации). Достаточно малое значение радиуса полного покрытия (наряду с выполнением ограничений на другие показатели, определяемые выборочной функцией полноты, скажем, на полноту при некотором конкретном с > 0), может служить правилом остановки процесса аппроксимации.
В однофазном методе на каждой итерации осуществляется улучшение качества полученной ранее аппроксимации Т* на основе генерирования выборки из N случайных равномерно распределенных точек множества допустимых решений X. Для точек выборки рассчитываются соответствующие критериальные точки, а затем рассчитывается доверительный интервал и строится график выборочной функции полноты аппроксимации. Если, например, радиус полного покрытия меньше заданного, то требуемая точность считается достигнутой и процесс прекращается. В противном случае из
совокупности точек исходной базы аппроксимации и вновь полученных точек выделяется недоминируемое множество - новая база аппроксимации, по которой строится новая аппроксимация ОЭП. Далее осуществляется переход к следующей итерации. Достоинством метода является его простота, а также эффективность в случае относительно малой размерности пространства решений.
Далее описываются двухфазные методы, которые отличаются от однофазного метода тем, что в них не только генерируется выборка случайных точек, равномерно распределенных в X, но и проводится приближение образов этих точек к паретовой границе Р(Т). Такое приближение осуществляется с помощью оптимизации выбранных адаптивным образом сверток критериев. Таким образом, здесь осуществляется синтез однофазных методов и концепций второго подхода, особенно работ Краснощекова [7, 8] Оценка качества аппроксимации и проверка правил остановки осуществляется на основе выборочной функции обобщенной полноты, которая имеет смысл вероятности того, что в результате операции приближения случайной точки к паретовой границе полученная критериальная точка будет принадлежать є-аппроксимации ОЭП. В остальном двухфазные методы совпадают с однофазным.
Отметим, что можно сформулировать большое число различных двухфазных методов, отличающихся методами свертки и выбором их параметров. Недостатком методов является необходимость расчета большого числа критериальных точек при оценке значений градиентов критериальных функций. В том случае, когда формулы расчета градиента заданы, описанная проблема теряет свою остроту. Достоинством двухфазных методов является то, что как показано в гл. 4 и 5, многофазные методы эффективны и в случае большой размерности пространства решений (до нескольких сотен переменных).
Трехфазные методы отличаются от двухфазных тем, что при генерировании оптимизируемой выборки случайных точек используется неравномерное распределение точек на множестве X. Это распределение имеет большую плотность вероятности в окрестностях прообразов точек базы аппроксимации, которые строятся с использованием теории экстремальных статистик [54] по методике, предложенной в [47]. В гл. 4 и 5 показано, что эти методы строят более точные аппроксимации в случае большой размерности
пространства решений и сложной структуры экстремумов сверток критериальных функций, чем двухфазные методы. В частности, в некоторых случаях они позволяют значительно уменьшить число решаемых задач локальной оптимизации.
В конце гл. 1 описан генетический метод аппроксимации ОЭП, называемый методом «оштукатуривания». Метод основывается на генерировании случайных точек на отрезках, соединяющих пары прообразов точек базы аппроксимации, удовлетворяющих некоторым ограничениям, расчете критериальных векторов в полученных точках и дальнейшем выборе недоминируемых критериальных векторов.
Во второй главе осуществляется теоретическое изучение свойств предложенных методов аппроксимации ОЭП. Рассматриваются идеализированные алгоритмы реализации однофазного и двухфазных методов, и исследуются их свойства. В частности доказаны конечность числа итераций и сходимость алгоритмов, даны оценки скорости сходимости алгоритмов, а также оценена эффективность работы алгоритмов, то есть проведено сравнение аппроксимаций, построенных с помощью алгоритмов, с любыми другими аппроксимациями при стремлении точности к нулю.
В завершении главы на основе результатов исследования формулируются практические алгоритмы методов аппроксимации ОЭП, изучаемых в диссертации: однофазного, многофазных и генетического метода «оштукатуривания».
В третьей главе описывается программное обеспечение для персональных компьютеров, реализующее метод достижимых целей для нелинейных моделей на основе аппроксимации ОЭП с помощью методов, сформулированных в гл. 2. Рассматриваются три программных системы.
Первая система реализована в среде MS Excel и основана на использовании однофазного метода аппроксимации. Вектор-функция fix) здесь задается либо формулой на листе Excel, либо с помощью макроса на встроенном в MS Excel интерпретаторе Visual Basic. Достоинством системы, являющимся следствием ее реализация в среде MS Excel, является простота ее использования для массового пользователя. Система визуализации позволяет осуществить диалоговую визуализацию паретовой границы и дает возможность указать предпочтительную целевую точку нажатием компьютерной мыши.
Вторая система написана на языке C++ и используется в среде Windows ХР. Система реализует однофазный, двух- и трехфазные методы. Вектор-функция J[x) в системе может быть задана несколькими способами: в виде DLL библиотеки или исполняемого ЕХЕ файла, а также в среде MatLab. Наиболее простая возможность — реализация вектор функции / в среде MatLab 6.5 или выше; достоинство такого подхода в том, что с этой задачей может справиться широкий круг пользователей, знакомых со средой MatLab и умеющий использовать мощный математический пакет среды MatLab. Недостатком такой реализации вектор функции / является невысокая скорость исполнения ее вычислений. Этот недостаток отсутствует, когда вектор-функция Дх) реализована в виде DLL библиотеки или исполняемого ЕХЕ файла. В систему встроен удобный модуль визуализации паретовой границы и спецификации предпочтительной точки на этой границе.
Третья система реализована в рамках проекта по созданию программного комплекса «Метод достижимых целей». Система позволяет пользователю подобрать сочетание методов аппроксимации и их параметров, наиболее пригодное для конкретного типа задач. Говоря иначе, пользователь задает свой многофазный или гибридный метод. В этой системе заданный метод тестируется и, в случае трудоемкости задачи, создается промежуточный файл (скрипт), который передается на кластер или суперкомпьютер, где расчет будет осуществлен с использованием параллельных вычислений. В систему встроен тот же самый модуль визуализации, что и во второй системе.
В четвертой главе описано экспериментальное исследование методов аппроксимации ОЭП в задачах разной размерности. Исследование проводится на основе изучения специально подобранных задач, имеющих различные свойства. В параграфе 4.1 приводится методика проведения экспериментов, в том числе описывается новый метод сравнения двух аппроксимаций паретовой границы, предложенный в данной работе.
В параграфе 4.2 проводится эксперимент с многокритериальными задачами, сформулированными с использованием функции Шекеля, широко применяемой при тестировании методов нелинейной оптимизации:
*(*) = К
(х-а) +с
Эти модели характеризуются простым видом ОЭП, причем с помощью варьирования параметра с можно регулировать высоту и крутизну «пиков» критериальных функций, воздействуя тем самым на форму паретовой границы, что дает возможность сравнивать работу изучаемых методов аппроксимации в различных условиях. Рассматривались задачи разной размерности (от п~2 и т~ 2 до «=12 и т= 5).
В параграфе 4.3 методы аппроксимации ОЭП изучаются на многокритериальной задаче, построенной с использованием экспоненциальной функции
^-,,^) = 3(1-^)^-^-^2 -
-lof-x. -х3 -x\\e-*-xl -Іе-<*+1>2-** +10.
Задача имеет размерность п=2 и т=5, а паретова граница - довольно сложную форму.
В параграфе 4.4 описываются результаты экспериментов на задачах, построенной с использованием функции типа
s(x)= e_at sin—, а>0, х>5, где 8 - малое положительное число. х
Эта функция ведет себя сложным образом в окрестности нуля. Данный
эксперимент показывает, как ведут себя различные методы аппроксимации с
«неудобными» критериальными вектор-функциями.
Из основных результатов, полученных в результате проведения
экспериментов, можно выделить следующие:
Трехфазные методы обычно строят более качественную аппроксимацию, чем двухфазные или однофазный.
Трехфазный метод в большинстве задач оказался менее экономичным по числу расчетов вектор-функции/по сравнению с двухфазным.
Трехфазные методы сами по себе часто имеют медленную сходимость. Причиной этого может оказаться медленное выявление новых точек, в окрестностях которых также следует искать эффективные решения. Комбинирование двух- и трехфазных методов позволяет устранить этот недостаток.
В пятой главе описываются эксперименты с многофазными методами аппроксимации ОЭП в многокритериальной задаче выбора параметров вторичного охлаждения стали в процессе ее непрерывной выплавки. На данной
задаче исследуются многофазные методы как по отдельности, так и в сочетании друг с другом. Предлагается эффективный гибридный метод аппроксимации ОЭП, сочетающий в себе последовательное применение двухфазного, трехфазного и генетического методов. В результате с помощью построенной аппроксимации находятся некоторые приемлемые сочетания критериев, которые сравниваются с достижимой точкой, полученной финскими учеными, также исследовавшими данную задачу. Показывается, что эта точка доминируемой. Приводится обсуждение одного из полученных нами решений. В заключении приведены основные результаты, выдвигаемые на защиту.
Краткое описание модели процесса охлаждения стальной полосы
Вторичное охлаждение играет главную роль в литейном процессе, потому что качество стали зависит от динамики поверхностной температуры и границ затвердения, которые определяются интенсивностью напора водяных струй Из-за недостаточного охлаждения сердцевина полосы (ее максимальная длина обозначена точкой zi) может слишком долго оставаться жидкой, а переохлаждение может повлечь за собой формирование трещин. Кроме того, при перемещении полосы из одной зоны охлаждения в другую должен быть обеспечен плавный переход температуры с минимальными скачками.
Измерение температуры весьма трудоемко, поэтому обычно ее рассчитывают математически. Отметим, однако, что это также непросто, поскольку положение границы затвердения заранее не известно и определяется в результате расчетов. Кроме того, граница затвердения является нечеткой, так как между твердой и жидкой фазами существует так называемая мягкая зона, состояние которой можно определить как «твердо-жидкое».
В работе [51] используется двумерная математическая модель теплообмена. Такое упрощение удается сделать, если пренебречь потоками тепла в направлении движения полосы, которые малы по сравнению с остальными потоками. Это упрощение обосновывается в [51]. Предполагается, что скорость перемещения стальной полосы v остается постоянной. Отсюда «возраст» (продолжительность процесса охлаждения) полосы на расстоянии z от точки начала процесса охлаждения определяется как t = z I v. Таким образом, можно определить моменты tj = Zj/v, /=1,...,5, в которые данная частица полосы проходит соответствующую точку.
В исследовании наибольший интерес представляет зона вторичного охлаждения (zi, zi), в которой расположена распылительная камера, т.е. между поддерживающими роликами расположены водяные форсунки. Здесь имеются несколько различных видов механизма теплообмена: целенаправленное охлаждение водяными струями, проводимость роликов при контакте с поверхностью полосы, излучение, конвективное охлаждение.
На практике трудно разделить конвективный перенос и теплопроводность роликов, поэтому проводимость тепла на границе полосы детально не рассматривается. Вместо этого в зоне вторичного охлаждения используется предположение о том, что тепловой поток пропорционален разности температуры между поверхностью и окружающей средой. Коэффициент пропорциональности в этом соотношении (коэффициент теплообмена и(х, t)) описывает эффект водяного охлаждения. В связи со сказанным модель имеет следующий вид.
Пусть QaR2 — сечение полосы, которое может быть, например, квадратом, прямоугольником (возможно с круглыми углами) или даже кругом. Обозначим через у = у(х, t) неизвестное распределение температуры стали как функцию от xeQ и /є[/і,/4І- В работе [51] на основе использования преобразования Кирхгоффа где к - теплопроводность, вопрос о нахождении температурного распределения у(х, I) сводится при заданном коэффициенте теплообмена и(х, t) к решению краевой задачи dt dv 1 от(/- ) BZ\I УЫО = МО BQ dv W 1 УЄ(УА-УІ) BZ\S„ 8 Щу) = АК(у) BQ, где H(y) — энтальпия, определяемая как #00= f ІР Л)сЮ-р{Ш№№, где р - плотность стали, с — удельная теплоемкость, L — теплота перехода в твердое состояние; функция fs описывает долю твердой фазы в твердожидкой зоне; Q = Q.x(ti, ), 2 = dix(t\, Ц), 21 = 5Qx(fb /2], вектор v определяет внешнюю нормаль к S. В зоне, где осуществляется охлаждение водой, т.е. (t є (t\, ]), тепловой поток на границе полосы описывается двумя составляющими: излучением, пропорциональным четвертой степени температуры (здесь х - константа Стефана-Больцмана, є — коэффициент и yext — внешняя температура); конвекцией, проводимостью роликов и водяным охлаждением, влияние которых приближенно описывается линейным соотношением, в котором У-лаг - температура струй воды, с использованием коэффициента теплообмена и(х, /). Коэффициент теплообмена определяется режимом работы форсунок и является средством воздействия проектировщиков на процесс охлаждения.
В следующих зонах, т.е. (Y є (/2, Ц)), считается, что охлаждение происходит в основном за счет излучения, так что учитывается только соответствующая составляющая. Наконец, предположение о том, что известно распределение температуры у\(х) на выходе из формы первичного охлаждения, дает начальные условия. Задав коэффициент теплообмена и(х, f) во всех точках границы, можно определить решение краевой задачи.
В работе [52] рассматриваемая краевая задача (1.1) дискретизируется путем использования метода конечных элементов по пространству и метода конечных разностей по времени. Пусть Г - триангуляция Q; х„ і-1,... 1, обозначают узлы Г, причем узлы, аппроксимирующие границу, имеют номера \ i P. Временной интервал [1\,Ц] делится на такие подинтервалы ґ\ = 1 ... f4 1 tK4 = ц, что временные события t2 и із находятся среди этих точек. Обозначим Af = / - /" .
Распределение температуры у(х, / ) в момент времени / аппроксимируется конечномерным вектором у — (уі ,...,уи ), где у, — значение аппроксимации в узле сетки (х„ tk). Совокупность величин у(х„ / ), где l i N, К\ к К$, используется как аппроксимация распределения температуры ,у(х, О-Коэффициент теплоотдачи и(х„ і), функция энтальпии Н(у) и преобразование Кирхгоффа аппроксимируются аналогичным образом векторами и , Н(у) и К(ук). Кроме того, значения ywat, yext и у і в узлах сетки представлены векторами ywat, Уехік и уі соответственно, а для аппроксимации производной Н по времени используется неявная схема.
Упрощенный однофазный алгоритм А1
Скорость сходимости алгоритма А1 будем исследовать по методике [47]. Введем следующие обозначения для некоторого множества AczR" [49]. Пусть 9Т (є, А) - минимальное число точек -сети для А, У1(є, А) - минимальное число множеств диаметра не более чем 2є, покрывающих множество А. Множество называется е-различимым, если любые две его различные точки находятся на расстоянии, большем чем є. Обозначим через Ш(є,А) - максимальное число точек -различимого подмножества Л.
Будем считать, что некоторая -сеть для А описывает множество А с точностью є, т.е. для любой точки хєА С помощью точек данной -сети можно указать ее положение с точностью є. Количество бит информации, необходимое для передачи положения точки х с помощью е-сети для А назовем -энтропией А, согласно теории информации оно будет равно log 2 91 ( , 4)+1. Количество бит информации, необходимое для передачи положения точки х с помощью -сети для А, принадлежащей самому множеству А, назовем -емкостью А, согласно теории информации оно будет равно log 2 ffl(e, А)-\.
Отметим некоторые свойства функций 9Т(, А), УІк(є, А), Ш(є, А) [49] как функций ". они являются невозрастающими и непрерывными справа, причем Щ2є, А) т(є, А) т\є, А) Т1(є, А). Обозначим Ж(е,А) := liminf Wl(e-v, А). v-»0+ Оценим число итераций, за которое алгоритм достигнет заранее заданной точности 0. Теорема 4 Пусть 0. Тогда K(s) m(sj) m(pK{m,Y), где величина К(є) определена в теореме 2. Доказательство На каждой итерации алгоритма к К{є) к базе 7 добавляется точка, удаленная от Tk на расстояние pk, не меньшее, чем є. Эта точка будет удалена и от Tk на расстояние не меньшее, чем pk є. Поскольку все добавляемые точки принадлежат Y, то их количество ограничено Ш{е,У), откуда и следует утверждение теоремы. Теперь оценим число итераций, за которое алгоритм сойдется с заданной полнотой. Теорема 5 Пусть отображение / удовлетворяет условию ( ). Тогда для любых є,г], є 0, l rj 0, справедливо где величина K(s,rf) определена в теореме 3. Доказательство Из утверждения леммы 1 следует, что К(є,ф К(є). Поэтому утверждение теоремы следует из теоремы 4.
Таким образом, сходимость алгоритма А1 определяется метрическими свойствами множества Y, его -емкостью. Следствие 1 теоремы 4 Пусть dY (у , у") := тах{ у\ - у" \}, y ,y"eRm и существует шар (куб) радиуса R, который содержит в себе множество Y. Тогда для V 0 справедливо К(є) (2(К+є)/є)т, где величина К(є) определена в теореме 2. Доказательство
Пусть BR - шар радиуса R, содержащий в себе множество Y. Заметим, что единичным шаром в пространстве Rm с такой метрикой является куб, поэтому пространство Rm является разложимым, то есть оно может быть разложено без перекрытий на единичные кубы так, что расстояние между центрами кубов равняется диаметру кубов. В силу этого величина fJJt(e,Y) VR(,BR) не может превышать числа открытых шаров радиуса є/2, содержащихся в BR+, поэтому ffl(,Y) (2(R+e)/e)m. Откуда из теоремы 4 и получаем утверждение следствия. Следствие 1 теоремы 5
Пусть отображение / удовлетворяет условию ( ). Пусть dY (у , у") := тах{ у\ - у" }, y ,y" Rm и существует шар радиуса R, который содержит в себе множество Y. Тогда для любых є,т], s 0, \ т] О, справедливо K(s,TJ) {2{R+s)ls)m, где величина К(є,т]) определена в теореме 3. Доказательство Из утверждения леммы 1 следует, что K(e,rf) K(e). Поэтому утверждение теоремы вытекает из следствия 1 теоремы 4. Для положительных функций J{s) и g(s) обозначим f g, если lim(f/g) = 1. Рассмотрим метрику dY(у ,у") := max{ у\ у"\ },y ,y"eRm. В [49] - 0+ I показано, что в этом случае
Реализация однофазных, двух- и трехфазных методов на языке C++
Программное обеспечение PFA-a, предназначенное для быстрой автоматической аппроксимации ОЭП для нелинейных моделей, реализовано на персональных компьютерах для платформ MS Windows ХР на языке C++. Оно позволяет аппроксимировать оболочку Эджворта-Парето в автоматическом режиме и в дальнейшем визуализировать паретову границу для нелинейных задач в интерактивном режиме. Важно, что входная модель программного обеспечения задается либо в виде исполняемого файла, либо в виде динамически загружаемой библиотеки, либо в виде функции среды MatLab, то есть пользователь получает возможность использовать уже имеющиеся модули, описывающие изучаемую модель в виде черного ящика.
Программное обеспечение автоматической аппроксимации ОЭП состоит из следующих четырех подсистем: 1. подсистема настройки на исходную модель; 2. подсистема задания критериев выбора и параметров расчета; 3. подсистема аппроксимации ОЭП; 4. подсистема визуализации паретовой границы и выбора предпочтительного варианта.
Первая подсистема позволяет настроить PFA-a на расчетный модуль пользователя. С помощью второй подсистемы пользователь определяет критерии, задает параметры окончания работы процесса аппроксимации, а также назначает число генерируемых случайных точек в контрольной выборке. Третья подсистема осуществляет непосредственно сам процесс аппроксимации ОЭП. Четвертая подсистема позволяет задать параметры изображения и визуализировать паретову границу. В рамках этой же подсистемы пользователь может указать предпочтительное достижимое сочетание критериев, принадлежащее покрытию, и получить соответствующую точку базы аппроксимации. Подсистема настройки на исходную модель Подготовка исходной модели состоит из следующих шагов: Подготовки расчетного модуля; Интерфейса расчетного модуля с программным обеспечением PFA-a; Открытия модели; Импорта базы аппроксимации.
До начала работы пользователь должен подготовить вычислительный модуль, который будет осуществлять расчет функции отклика. Такой модуль должен представлять собой экспортируемую функцию динамически подгружаемой библиотеки (DLL), выполняемый программный модуль (ЕХЕ), или функцию среды MatLab 6.1 и выше (m-file).
Следует заметить, что система позволяет определить множество допустимых решений X только в виде параллелепипеда. Если пользователь хочет задать дополнительные ограничения внутри X, то его расчетный модуль должен возвращать число, отличное от нуля, если сочетание значений вектора х удовлетворяет этим ограничениям. В противном случае, модуль должен вернуть ноль. Дополнительные ограничения могут быть также учтены в виде дополнительных критериев.
В первом случае экспортируемая функция должна иметь вид, аналогичный тому, который приведен ниже на языке С: BYTE stdcall MyFunction (const double x, double y);
Входными параметрами являются указатели на массив входных переменных х и на массив для значений выходных переменных у. Результатом работы функции должен быть массив значений, помещенный по адресу у.
Второй вариант задания расчетного модуля состоит в следующем. Пользователь пишет выполняемый ЕХЕ модуль, который из текстового файла принимает входные значения, и результат также выдает в текстовом виде. Если в этом случае потребуется наложить дополнительные ограничения внутри X, то в выходном файле в конце добавляется еще одно число, отличное от нуля, если входные значения удовлетворяют этим ограничениям, или ноль в противном случае.
Третий вариант представляет собой функцию среды MatLab, заданную через соответствующий m-файл. М-файл должен быть доступен из командной строки среды MatLab. Вид функции должен иметь следующий вид: function [res, у] = MyFunction (х); где у — вектор-столбец, содержащий значения аргументов, у — вектор столбец, содержащий значения функции, res — должен быть равен единице, если значения х удовлетворяют дополнительным ограничениям внутри X, и нулю в противном случае.
В любом из трех вариантов задания расчетного модуля нужно указать системе информацию, по которой она сможет к этому модулю обращаться. Для DLL модуля это имя DLL библиотеки и имя экспортируемой из нее вектор-функции; для ЕХЕ модуля - его расположение на диске и файлы входных и выходных значений; для модуля среды MatLab - имя функции, описанной в т-файле.
После того, как расчетный модуль подготовлен, надо настроить интерфейс расчетного модуля с системой PFA-a. Для этого системе следует лишь указать размерность задачи, т.е. величины пит, направления оптимизации по каждому из критериев и ограничения, задающие множество допустимых решений X.
Когда все настройки модели подготовлены, модель можно сохранить под уникальным именем, и в последствии загружать ее для работы. Также можно осуществлять импорт и экспорт базы аппроксимации в текстовый VMT файл.
Исследование методов на основе использования функции Шекеля
Рассмотрим изменение показателей, полученных в процессе аппроксимации. На рис. 4.89 и 4.90 показано изменение точности аппроксимации / на 10 итерациях алгоритма для двухфазных и трехфазных методов.
Наименьшее значение / на 10-й итерации получено двухфазным методом со сверткой Гермейера (0.016), следующим по величине значение / было у трехфазного метода с квадратичной сверткой (0.0057), а самое высокое значение было у двухфазного метода с совместной сверткой (0.0008). В целом же можно видеть, что показатели / на графиках качественно не отличаются друг от друга — имеет место немонотонное постепенное уменьшение величины /.
Здесь для двухфазных методов прослеживается быстрое приближение значений графиков выборочной полноты к единице. Минимальное значение выборочной полноты для двухфазных методов составляет 0.95 для квадратичной свертки, а максимальное - 0.97 для свертки Гермеиера. Для трехфазных методов такого выраженного сближения графиков к единице не наблюдается. В трехфазном методе с квадратичной сверткой к 8-й итерации значение выборочной полноты даже падает до 0.69, после чего к 10-й итерации увеличивается до 0.85. Это означает, что трехфазные методы продолжают находить точки, улучшающие границу.
В целом видно, что значения г в целом убывает с ростом номера итерации, причем для разных методов графики качественно не отличаются .
Графики изменения показателя «Spacing» на 50 итерациях приведены на рис. 4.94 и 4.95 для двухфазных и трехфазных методов соответственно.
Для всех методов видна общая тенденция к снижению этого показателя, т.е. распределение точек базы аппроксимации ОЭП на паретовой границе с увеличением числа итераций становится более равномерным. Наибольшую неравномерность дает свертка Гермейера, как в двухфазном методе, так и в трехфазном методе. Наиболее равномерную аппроксимацию дает квадратичная свертка (и в двухфазном, и в трехфазном методах).
Можно сказать, что число расчетов вектор-функции/в данной задаче зависело больше от вида свертки, нежели чем от типа метода. У трехфазных методов, кроме метода с совместной сверткой, видно увеличение этого числа к 10-й итерации.
Приведем рисунки некоторых полученных аппроксимаций. На рис. 4.98 показана аппроксимация ОЭП, полученная на 50-й итерации трехфазного метода с квадратичной сверткой, а на рис. 4.99 показана ее база аппроксимации. Рис. 4.98. Аппроксимация ОЭП. Рис. 4.99. База аппроксимации. 3-ф. метод, квадратичная с, 3-ф. метод, квадратичная с, итерация 50. итерация 50.
В двухкритериальной задаче более наглядно показывать не аппроксимацию ОЭП, а ее базу аппроксимации. Для визуального сравнения аппроксимаций ОЭП приведем вид их баз аппроксимации на итерации 10 (рис. 4.100). Из рисунка видно более сильное разрежение точек в базах аппроксимации двухфазных методов со свертками Чебышева и Гермейера.
При сравнении этих множеств, полученных на 10-й итерации, выявилось преимущество квадратичной свертки над остальными. На рис. 4.101 и 4.102 показаны графики функций включения для методов со сверткой Гермейера и квадратичной сверткой (двухфазный и трехфазный методы). Для этих рисунков обозначим через А базу аппроксимации, построенную со сверткой Гермейера, через В - квадратичной сверткой. В двухфазном методе наблюдается явное преимущество квадратичной свертки над сверткой Гермейера. Для этого случая vfl(0, ) = ,0.07 vA{0, В ) = 0.33, ЄшЗХА = 0.014, wS = 0.012, GD(B,A ) = 0.001, GD04,B ) = 0.002, «Spacing» для А равен 0.08, для В - 0.047. В трехфазном методе это отличие менее выражено, данные в этом случае такие:
Преимущество свертки Гермейера над сверткой Чебышева проявилось на 10-й итерации в трехфазном методе (рис. 4.103). Отличие аппроксимаций, построенных на свертках Чебышева, Гермейера и совместной свертки двухфазным методом, а также отличие аппроксимаций, построенных на свертках Чебышева и совместной свертки трехфазным методом, были небольшими. Обозначим на рисунке через А базу аппроксимации, построенную со сверткой Чебышева, через
