WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

UОднофазный методU аппроксимации ОЭП состоит в следующем. На каждой итерации осуществляется оценка качества полученной ранее аппроксимации T* на основе N P построения выборочной функции полноты B PB (), получаемой на H основе образов выборки HB B. При автоматической остановке N метода проверяется, например, выполнение требований к радиусу полного покрытия B B

При аппроксимации ОЭП в задачах большой размерности или со сложным поведением вектор-функции f оценки качества аппроксимации, полученные в ходе работы однофазного метода, становятся не действенными, т.е. перестают различать «плохие» и «хорошие» аппроксимации. Поэтому вводится новое отображение : XX, которое ставит в соответствие случайной точке xX некоторую такую «улучшенную» точку xX, что вектор f(x) «более близок» к P(Y), чем f(x). Для суперпозиции функций f и аналогичным образом определим обобщенную,N P выборочную полноту B PB (), равную доле точек xHB B, для H N которых f((x))(T*)B B.

UДвухфазные методыU аппроксимации ОЭП состоят в следующем. На каждой итерации осуществляется оценка качества полученной ранее аппроксимации T* на основе N P построения выборочной функции полноты B PB (), получаемой на H основе улучшенных с помощью отображения : XX образов выборки HB B. В остальном двухфазные методы полностью N аналогичны однофазному.

UТрехфазные методыU отличаются от двухфазных тем, что выборка HB B является объединением двух выборок, одна из N которых генерируется на всем допустимом множестве, а вторая – только в окрестностях точек аппроксимации. При этом первая выборка содержит малое число точек, а вторая – большое число.

Помимо многофазных методов построения аппроксимации ОЭП рассматривается Uгенетический методU (U«оштукатуривание»U), который позволяет улучшить уже ранее построенную аппроксимацию. Метод состоит в следующем. Из прообразов имеющейся базы покрытия T случайно (но с учетом некоторых ограничений) выбираются пары точек («родители»). Между точками каждой такой пары проводится отрезок и на этом отрезке случайным образом выбирается заранее заданное или случайное число q>1 новых точек множества допустимых решений («популяция наследников»). Для всех точекнаследников вычисляются значения f(x). Полученные критериальные точки используются для оценки качества имеющейся аппроксимации и пополнения базы покрытия.

Во второй главе осуществляется теоретическое изучение свойств предложенных методов аппроксимации ОЭП. Анализ методов основан на применении теории аппроксимации многомерных тел, разработанной Г.К. Каменевым (2001) и называемой «Метод глубоких ям». Теоретическое изучение свойств методов осуществляется с помощью упрощенных алгоритмов аппроксимации.

UУпрощенный однофазный алгоритм A1U. Пусть заданы TB B – конечное подмножество из Y, N – объем контрольной выборки и вероятностная мера µB B() на B(X). Рассмотрим k-ую итерацию X алгоритма. Пусть имеется уже построенная база аппроксимации TB B.

k-k P 1) Генерируется выборка HB PB X в соответствии с мерой N k P µB B() и рассчитаются образы f(HB PB ).

X N 2) Ищется точка xk Argmax ( f (x),Tk -1 *) и k xH N k P соответствующее ей максимальное отклонение B B = (f(xP ), TB B*) k k-k P 3) Строится новое множество TB B = P(TB B f(xP )).

k k-UУпрощенный двухфазный алгоритм A2U. Пусть заданы TB B – конечное подмножество из Y, µB B() – вероятностная мера на B(X), X N – объем контрольной выборки. Пусть задано отображение : X P X. Обозначим YP = f((X)). Рассмотрим k-ую итерацию алгоритма. Пусть имеется уже построенная база аппроксимации TB B.

k-k P 1) Генерируется выборка HB PB X в соответствии с мерой N k P µB B() и рассчитываются их образы f((HB PB )).

X N 2) Ищется точка x,k Argmax (f ((x)),Tk -1 *) и k xH N соответствующее ей максимальное отклонение,k P P B PB = (f((xP )), TB B*) k k-,k P 3) Строится новое множество TB B = P (TB B f((xP ))).

k k-UУпрощенный трехфазный алгоритм A3U. Упрощенный трехфазный алгоритм A3 может быть построен на основе усложнения алгоритма A2 модификации метода генерации k P контрольной выборки HB PB. Пусть заданы TB B – конечное N подмножество из Y, µB B() – вероятностная мера на B(X), N – объем X контрольной выборки. Пусть задано отображение : X X.

Рассмотрим k-ую итерацию алгоритма A3. Пусть имеется уже построенная база аппроксимации TB B.

k-k k k k P 1) Генерируется выборка HB PB = H H, где выборка H N N1 N2 Nимеет объем NB B точек и генерируется на всем множестве X в k соответствии с мерой µB B(). Выборка H имеет объем NB B и X Nгенерируется каким-либо определенным образом на k P подмножествах X. Считаются их образы f((HB PB )).

N 2) Ищется точка x,k Argmax (f ((x)),Tk -1 *) и k xH N соответствующее ей максимальное отклонение,k P P B PB = (f((xP )), TB B*) k k-,k P 3) Строится новое множество TB B = P (TB B f((xP ))).

k k-При исследовании свойств алгоритмов на отображения f и накладываются следующие условия:

UУсловие (*).U Отображение f удовлетворяет условию (*), если для любого конечного множества T из Y и для любого >-P справедливо f P ((T*)B BY)B(X).

UУсловие (**).U Отображения f и удовлетворяют условию P (**), если для любого конечного множества T из YP и для любого ->0 справедливо -1[f ((T*) Y )]B(X).

Доказаны следующие свойства алгоритмов. Пусть {TB B} – k последовательность баз аппроксимации, порождаемая соответствующим алгоритмом.

Конечность.

UТеорема 2U (для A1). Для любого >0 существует минимальный номер K() такой, что B B<.

K()+UТеорема 9U (для A2 и A3). Для любого >0 существует PB минимальный номер K() такой, что P B<.

K()+Сходимость.

UТеорема 3U (для A1). Пусть f удовлетворяет (*). Тогда для любых >0, 0<<1 существует минимальный номер K(,) такой, что надежность выборочной оценки полноты в виде TK (,N ) ( ) > не меньше *(,N).

UТеорема 10U (для A2 и A3). Пусть f и удовлетворяют (**).

Тогда для любых >0, 0<<1 существует минимальный номер K(,) такой, что надежность выборочной оценки полноты в виде TK (,N ) ( ) > не меньше *(,N).

Скорость сходимости. Пусть A – произвольное множество.

R P NP (, A) – минимальное число точек метрической -сети для множества A. N(, A) – минимальное число множеств диаметра не более чем 2, покрывающих множество A. M(, A) – максимальное число точек -различимого множества A (т.е.

такого множества, точки которого удалены друг от друга не менее, чем на ) (А.Н.Колмогоров и В.М.Тихомиров, 1959). Пусть ~ M(, A) := liminf M( - v, A).

v0+ UТеорема 4U (для A1). Пусть >0, тогда ~ K() M(,Y ) M(B B, Y), где K() определена в теореме 2.

K()+UСледствие 2 теоремы 4U (для A1). Пусть dY (y, y ) := max{ | yi - yi | } и объем Vol(Y)>0, тогда i m lim sup K ( ) Vol(Y )2m, где K() определена в теореме 2.

+UТеорема 5U (для A1). Пусть f удовлетворяет условию (*), тогда ~ для >0, 0<<1 K(,) M(,Y ) M(B B, Y), где K(,) K(,)+определена в теореме 3.

UСледствие 2 теоремы 5U (для A1). Пусть dY (y, y ) := max{ | yi - yi | } и объем Vol(Y)>0, тогда i m lim sup K(,) Vol(Y )2m, где K(,) определена в теореме 3.

+UТеорема 11U (для A2 и A3). Пусть >0, тогда ~ K() M(,Y ) M(K ( )+1,Y ), где K() определена в теореме 9.

UСледствие 2 теоремы 11U (для A2 и A3). Пусть P dY (y, y ) := max{ | yi - yi | } и объем Vol(YP )>0, тогда i m m limsup K( ) Vol(Y )2, где K() определена в теореме 9.

+UТеорема 12U (для A2 и A3). Пусть f и удовлетворяют условию (**), тогда для >0, 0<<~ K(,) M(, Y ) M(K (, )+1,Y ), где K(,) определена в 10.

UСледствие 2 теоремы 12U (для A2 и A3). Пусть P dY (y, y ) := max{ | yi - yi | } и объем Vol(YP )>0, тогда i m lim sup K(,) Vol(Y )2m, где K(,) определена в +теореме 10.

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

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

PB UТеорема 17U (для A2). Пусть S – произвольная P B-сеть для K()+P(Y), где K() – минимальный номер итерации такой, что PB P B<. Тогда K()+ NR(K ( )+1, P(Y )).

card S card TK ( ) M(K ( )+1, P(Y )) m P UСледствие 1 теоремы 17U (для A2). Пусть Vol(P(Y))>0 в RP, m m m-m P P P PB RP = RP RP. Пусть S – произвольная P B-сеть для P(Y), где K()+ PB K() – минимальный номер итерации такой, что P B<. Тогда K()+ m card S liminf.

+card TK ( ) В завершении главы на основе результатов исследования формулируются практические алгоритмы методов аппроксимации ОЭП, изучаемых в диссертации: однофазного, многофазных и генетического метода «оштукатуривания».

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

Первая система реализована в среде MS Excel и основана на использовании однофазного метода аппроксимации. Векторфункция f(x) здесь задается либо формулой на листе Excel, либо с помощью макроса на встроенном в MS Excel интерпретаторе Visual Basic. Достоинством системы, являющимся следствием ее реализация в среде MS Excel, является простота ее использования для массового пользователя. Система визуализации позволяет осуществить диалоговую визуализацию паретовой границы и дает возможность указать предпочтительную целевую точку нажатием компьютерной мыши.

Вторая система написана на языке C++ и используется в среде Windows XP. Система реализует однофазный, двух- и трехфазные методы. Вектор-функция f(x) в системе может быть задана несколькими способами: в виде DLL библиотеки или исполняемого EXE файла, а также в среде MatLab. Наиболее простая возможность – реализация вектор функции f в среде MatLab 6.5 или выше; достоинство такого подхода в том, что с этой задачей может справиться широкий круг пользователей, знакомых со средой MatLab и умеющий использовать мощный математический пакет среды MatLab. Недостатком такой реализации вектор функции f является невысокая скорость исполнения ее вычислений. Этот недостаток отсутствует, когда вектор-функция f(x) реализована в виде DLL библиотеки или исполняемого EXE файла. В систему встроен удобный модуль визуализации паретовой границы и спецификации предпочтительной точки на этой границе.

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

В четвертой главе описано экспериментальное исследование методов аппроксимации ОЭП в задачах разной размерности.

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

Первый класс задач сформулирован с использованием функции Шекеля, широко применяемой при тестировании P методов нелинейной оптимизации: s(x)=1/{(x-a)P +c}. Эти модели характеризуются простым видом ОЭП, причем с помощью варьирования параметра c можно регулировать высоту и крутизну «пиков» критериальных функций, воздействуя тем самым на форму паретовой границы, что дает возможность сравнивать работу изучаемых методов аппроксимации в различных условиях. Рассматривались задачи разной размерности (от n=2 и m= 2 до n=12 и m= 5). Далее методы аппроксимации ОЭП изучаются на многокритериальной задаче, построенной с использованием экспоненциальной функции 2 - x1 -( x2 +1)s( x1, x2 ) = 3(1 - x1 ) e - 2 2 1 3 -10 x1 - x1 - x2 e-x1 -x2 - e-( x1+1)2-x2 + 10.

4 Задача имеет размерность n=2 и m=5, а паретова граница – довольно сложную форму. Последние эксперименты проводятся на задачах, построенной с использованием функции типа s(x)= e-ax sin, a>0, x, где – малое положительное число. Эта x функция ведет себя сложным образом в окрестности нуля.

Данный эксперимент показывает, как ведут себя различные методы аппроксимации с «неудобными» критериальными векторфункциями.

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

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

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

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

В пятой главе описываются эксперименты с многофазными методами аппроксимации ОЭП в многокритериальной задаче выбора параметров вторичного охлаждения стали в процессе ее непрерывной выплавки. Как было уже сказано, задача имеет управлений и 5 критериев (JB B–JB B), первый из которых (JB B) не 1 5 учитывается при решении задачи.

Исследовались следующие проблемы:

• Сравнение аппроксимации паретовой границы с использованием двух- и трехфазных методов.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»