Содержание к диссертации
Введение
ЗАДАЧИ Планирования регрессионных жспериментов и оптимизации по неточным моделям .
1.1. Общие задачи оптимизации с неточными моделями . II
1.1.1. Принцип неразличимости для скалярных задач 13
I.I.2. Векторные задачи оптимизации с неточными моделями. 19
1.2. Регрессионные задачи планирования эксперимента и оптимизации.. 22
1.2.1. Некоторые допущения 23
1.2.2. Скалярная оптимизация по регрессионной модели на основе принципа неразличимости 26
1.2.3. Планирование регрессионных экспериментов 29
1.2.3.1. Понятия и критерии оптимальности планов 30
1.2.3.2. Разрешающая способность регрессионной модели и R -критерии оптимальности
планов 35
1.3. Формулировка цели исследований 38
2. Отношения првдочтения и неразличимости в задачах векторной оптимизации с неточными моделями . 40
2.1. Отношение неразличимости в векторных задачах оптимизации
2.2. Отношение предпочтения в векторных задачах в условиях неразличимости.«... 42
2.3.Проверка векторных задач на определенность 47
2.4. Об области оптимума и ее выделение* 50
Выводы по второй главе... 55
3. Векторная оптимизация по регрессионным моделям 57
3.1. Отношения неразличимости и предпочтения в векторной задаче с регрессионными моделями
3.2. Анализ векторной задачи на определенность Исследование свойств и способов выделения области оптимума. 59
3.2.1. Анализ задачи на определенность... 59
3.2.2. Свойства и способы выделения области оптимума 61
3.3. Примеры. 66
Выводы по третьей главе... 72
4. Алгоритмы вццеления области оптимума в векторных задачах оптимизации с неточными моделями 74
4.1. Алгоритмы выделения области оптимума для скалярных задач оптимизации ... 76
4.1.1. Модификация метода градиента 78
4.1.2. Модификация метода сеток... 78
4.1.3. Модификация метода Монте-Карло... 79
4.2. Алгоритмы выделения области оптимума для векторных задач. 82
4.3. Сопоставление алгоритмов (по количеству попарных сравнений)... 84
4.3.1. Конечное множество решений 84
4.3.2. Континуальное множество решений... 34
Выводы по четвертой главе... 88
5. R -оптимальные планы в задачах скалярной и векторной оптимизации с регрессионными моделями 89
5.1. Критерии /^-оптимальности планов в векторных регрессионных задачах оптимизации 5.2. Аналитический синтез R -оптимальных планов для одномерной регрессии.. 97
5.2.1. R& -оптимальные планы для чебышевской системы базисных функций 98
5.2.2. Исследование свойств "равномерного" плана для тригонометрической регрессии на (0,2:0
5*3. Синтез RQ -оптимальных планов для многофакторной полиномиальной регрессии... ЮЗ
5.3.1. Синтез /(# -оптимальных планов для полиномиальной регрессии 2-го порядка общего вида ЮЗ
5.3.2. Синтез А,2 -оптимальных планов для некоторых полиномиальных моделей до 3-го
порядка. 104
Выводы по пятой главе.
6. Шыт применения принципа неразличимости к решению некоторых других задач
6.1. Общая постановка задачи..
6.2. К решению задач оптимального управления с неточными функционалами качества 6.3. Задача синтеза оптимального плана при ошибках измерения.» П7
6.4. Задачи интервального оценивания регрессион ных параметров. ^24
6.4.1. Метод наименьших квадратов (МНК) 1;^
6,4.2. Метод наименьших модулей(МШ)... 130
6.5. Комплекс прикладных программ выделения области оптимума в скалярных задачах оптимизации 133
6.6, К решению задачи оптимизации пропускной способности ремонтных депо локомотивов.. 134
6.6.1. Некоторые сведения 134
6.6.2. Построение регрессионных моделей 137
6.6.3. Постановка и решение задачи оптимизации по регрессионным моделям. 145
Выводы по шестой главе , 149
Заключение 151
Литература 153
Список обозначений 164
Приложения
- Общие задачи оптимизации с неточными моделями
- Отношение неразличимости в векторных задачах оптимизации
- Отношения неразличимости и предпочтения в векторной задаче с регрессионными моделями
- Алгоритмы выделения области оптимума для скалярных задач оптимизации
Введение к работе
Данная диссертационная работа посвящена решению актуальной научной проблеме - разработке методов решения задач векторной оптимизации с неточными моделями. Основной упор в работе делается на задачи с регрессионными моделями, построенными на основе экспериментально-статистических данных, которые в настоящее время получили широкое применение в практике оптимизации технологических объектов и систем.
Процесс проектирования и оптимизации технологических объектов включает этапы выбора оптимального плана эксперимента, построения математических моделей объекта, постановки задачи оптимизации и ее решения по построенным математическим моделям.
В последние годы для указанных этапов разработаны достаточно эффективные теоретические методы и прикладные программы, предназначенные для решения широкого плана практических задач проектирования и оптимизации. Вместе с тем, из анализа литературных источников можно заметить, что до настоящего момента довольно слабо исследованы методы решения задач оптимизации, в особенности - методы решения задач многокритериальной оптимизации, по неточным моделям с учетом информации об ошибках моделей.
В данной диссертации упомянутый подход [IIобобщен на случай векторных задач оптимизации по неточным моделям, а также исследована возможность его применения к некоторым другим типам задач принятия решений в условиях неточной или неполной информации.
Работа содержит 44-? страниц основного текста, -/5 рисунков, -/в таблиц и состоит из введения, шести глав, заключения, списка литературы из 4ІІ названий и приложения.
Основные теоретические результаты работы изложены в последних пяти главах. Для всех шести глав принята единая по композиции и структуре форма изложения материала: глава разбита на параграфы и последние - на подпараграфы.
В первой главе представлены основные понятия и предпосылки из теории оптимального эксперимента и оптимизации, а также исходные результаты решения задач планирования эксперимента и оптимизации с неточными моделями. На основе анализа существующих подходов к решению упомянутых задач были сформулированы цели исследований работы.
Во второй главе подход к решению скалярных задач оптимизации по неточным моделям с использованием принципа неразличимости обобщен на векторные задачи оптимизации, исследованы свойства отношений неразличимости и предпочтения, области оптимума и условия пригодности моделей для векторных задач в общем случае.»
В третьей главе изложены результаты исследований задачи векторной оптимизации по регрессионным моделям с применением принципа неразличимости.
В четвертой главе модифицированы известные и предложены некоторые новые алгоритмы выделения области оптимзша для векторных задач.
В пятой главе исследованы возможные критерии оптимальности планов для векторных регрессионных задач и синтезированы Я - оптимальные планы для скалярных задач оптимизации.
В шестой главе исследована возможность применения принципа неразличимости к задачам оптимального управления по неточным функционалам, интервального оценивания регрессионных коэффициентов, и синтеза оптимальных планов эксперимента при ошибках в независимых переменных. Здесь же описан комплекс прикладных программ NERA выделения области оптимума для скалярной задачи оптимизации по неточным моделям, результаты решения задач оптимизации пропускной способности ремонтного депо для локомотивов
В приложении представлены доказательства некоторых теорем и утверждений, а также листинг комплекса программ NERA на язшеГО/?ГЯАЛ/-1У, ЕС ЭВМ.
По результатам исследований в диссертационной работе было опубликовано 5 печатных работ. Основные положения работы докладывались и обсуждались на
ІУ Всесоюзной конференции по планированию эксперимента и автоматизации научных исследований, г.Москва, 1980г.;
I Всесоюзной конференции "Опыт и перспективы внедрения статистических методов в АСУ ТП",г.Смоленск, 1981;
Всесоюзном НТС "Создания и внедрения автоматических и автоматизированных систем управления непрерывными и непрерыв - но-дискретными технологическими процессами", г.Алма-Ата,1983; Общегородском семинаре "Дцентификация и оптимизация промышленных объектов", г.Москва, 1984.
Общие задачи оптимизации с неточными моделями
В последнее время возрастает количество научных публикаций, посвященных проблеме принятия решений в условиях неопределенности, и в частности, в условиях неточности моделей. Это обусловлено тем, что на практике с каждым днем все более часто приходится решать задачи проектирования или оптимизации объектов или систем при частичном отсутствии информации или неточном знании об исследуемых объектах. Предложены различные подходы к выделению неулучшаемых (недоминируемых) решений, зависящие от особенностей возникновения ситуации неопределенности (неточности).
В частности, в теории выбора [41-43,49,65,73J исследуются ситуации, когда неточность связана с субъективным характером выделения предпочтительных решений лицом, принимающим решение; в теории нечетких множеств [44,82,83,71,72] неточность связана с размытостью исходных данных задачи, а в задачах векторной оптимизации L 43,46,66-70,90-102 2 с наличием многих противоречивых критериев. Кроме того, в условиях неполной информации об объекте, обусловленной, например, его стохастической природой, неточностью в измерении исходных данных и т.п., возникает ситуация неопределенности, когда из двух альтернатив 2 и Хл , принадлежащих некоторому допустимому множеству X , нельзя выбрать предпочтительной, и следовательно, они становятся неразличимыми. В частности, такая ситуация имеет место в задаче скалярной оптимизации когда вместо истинного скалярного критерия - известна лишь его оценка -ф , или в задаче векторной оптимизации когда вместо компонент -gc вектора F Є /Z известны толь-ко их оценки j с= S,w и т.д. В практике оптимизации технологических объектов и экономических систем эти ситуации довольно часто имеют место, так как модели - cfaJ неизвестных критериев /, v=: Ьт обычно приходится строить на основе экспериментально-статистических данных. В связи с этим решение задач (ІЛЛ) и (I.I.2) в указанных постановках важно и актуально.
В дальнейшем, если нет специальных оговорок, условимся, что множество X - выпуклая область, а у L- l= j i - выпуклые функции от х . В общем случае в качестве JC может быть выступать число, вектор, функция, матрица и т.п. Условимся в общем случае называть JC - решением задачи, а функцию -- критерием задачи.
Нетрудно видеть, что в случае точной модели / $ср= $х)) задача (1,1.1) может быть выражена математической моделью вида X; 0С)± (I.I.3) и решена известными методами математического программирования. и Если модель неточная, т.е. - fa) $&) , но прене-брегают ошибками в модели -g-fa) , то задача оптимизации описывается моделью Ш Х, & (ІЛ.4) При сравнении решений х f р Хл Є X по модели ц?(х) необходимо считать, что Хі лучше Л (xiyxJL) , когда имеет место соотношение ХІ УХХ _ - #зс ) &xxJ (1Л.5) Вместе с тем, из-за ошибок в модели (Xj возможны ситуации, при которых gfr ) fax) , ХОТЯ #Х0 JfctJ (I.I.6) и следовательно, худшее из двух решений объявляется ошибочно предпочтительным.
Чтобы избежать подобных неверных выводов, в Ш предлагается подход, основанный на введении отношения неразличимости решений с использованием информации об ошибке модели. При этом вводится отношение неразличимости JCf а х , порожден-ное неточностью модели критерия % . Запись х4 а. х. означает, что jr/ неразличимо с х± , т.е. неточность модели не позволяет выбрать из них предпочтительное.
Отношение неразличимости в векторных задачах оптимизации
Условимся сначала, что в общем случае для обозначения отношений неразличимости и предпочтения сохраним символы и - использованные в задачах скалярной оптимизации. В отдельных случаях при необходимости употребим и другие их обозначения, которые в дальнейшем будут оговорены специально. Например, отношения неразличимости вида (I.I.I0) и пороговой неразличимости вида (1.1,9) в векторных задачах обозначим как 9? и ?рл , а соответствую-шие им отношения предпочтения - как / и /Jj , соответственно.
Учитывая специфику векторных задач, для которых выбор лучшего решения производится по многим критериям, и опираясь на введенное отношение неразличимости для скалярных задач, можно предложить два следующих правила неразличимости решений в задачах векторной оптимизации:
1-е правило: В векторных задачах оптимизации решения Х и ЭСХ неразличимы (обозначим как х± VLx± ), если они неразличимы, хотя бы по одному критерию, или каждое из них не лучше другого по отношению Р , т.е.
Так как ( ; ) - полная система отношений, согласно утвер-ждению 2.1 имеем, что отношение Р влечет за собой отношение Р .
Используя введенное отношение строгого предпочтения, область оптимума Х0 можно определить выражением (I.I.I6).
В дальнейшем при синтезе алгоритмов выделения области опти-мума Х0 важным свойством является транзитивность отношения предпочтения - .
Рассмотрим этот вопрос несколько подробнее. "Теорема 2.1. Для того, чтобы отношение предпочтения Р было транзитивным, достаточно, чтобы для всех функций Р;Сх .,хх) выполнялись отношения
Утверждение 2.5. Отношение предпочтения Р транзитивно.
Доказательство утверждения 2.5. основано на том, что для всех пар х(,хлеХ функции ftCXbXjj постоянны, то есть p Cx sc = Лі Cents хі,ххє X
Аотя отношение предпочтения - , как показано выше, в общем случае не является порядком, ему присуще следующее важное свойство.
Утверждение 2.6. Отношение предпочтения - в задаче векторной оптимизации антирефлексивно и ациклично.
Доказательство. Антирефлексивность отношения - немедленно следует из антирефлексивности отношения Р и (2.2.1). Нам остается доказать, что - - ациклично.
Предположим от противного что Зхі,... JC«, GX, %ъ - » чт0 xt -.. -... -; , - х,. Из Хх х± - ... /,, и транзитивности отношения Р р , согласно (2.2.1) имеем . PJT/t. С другой стороны, из Хп. - х аналогично, имеем xnPXi,
Противоречение между х± Р Z , и Хп Р ocj. доказывает утверждение 2.6. В соответствии с теоремой [65,73,74 3 известно, что если множество решений конечно, то модель XNj sz, У (2.2.10) для задачи векторной оптимизации в условиях неразличимости можно заменить моделью вида где иезе} _ всегда существующая на Х# и определяемая заданным отношением неразличимости д: функция полезности. Последнее означает, что при ацикличном и антирефлексивном отношении - , можно построить функцию UCx} t т.е. свести задачу (2.2.10) к задаче со скалярным критерием. При этом выделение области оптимума не представляет труда, так как могут быть использованы известные методы математического программирования на дискретном множестве решений.
Заметим, что формально отношение - может быть всегда определено, если введено отношение неразличимости решений. Вместе с тем имеют место ситуации, когда неточность моделей так высока, что на X не существует ни одной пары решений, которые находятся в отношении - , и в качестве "оптимального" можно с равным успехом взять любое решение из X. Очевидно, что в этом случае модели непригодны для принятия решений, т.е. задача является неопределенной.
Отношения неразличимости и предпочтения в векторной задаче с регрессионными моделями
Для регрессионных моделей условия проверки задачи векторной оптимизации на определенность удается сформулировать сравнительно просто, используя утверждения 2.7 и 2.8.
Так, при отношении неразличимости V , согласно ут верждению 2.7, задача векторной оптимизации не определена, если не определена хотя бы одна калярная задача оптимизации по какому-либо из критериев ф fa) j 1 - 4 ъ% а при отношении неразличимости 10 х , если каждая скалярная задача оптимизации с критерием ifa)/ ї-4» не определена. Следовательно, достаточно исследовать условия непригодности модели в скалярных задачах.
Для отношения Фзм такое условие определяется в соответствии с (1.2.14).
Для отношения 2 можно видеть, что если максимальное значение разности &з)- fe+J не больше минимального значения функции j Огу, хх) , -Vх,, х±у х , х?. X то любые два решения между собой неразличимы. Следовательно, достаточное условие неопределенности задачи в этом случае определяется соотношением
Если знак величины отрицательный, то мо дель непригодна для решения задачи.
В табл. 3.1 представлены условия проверки задачи оптимизации на определенность для всех рассмотренных выше отношений неразличимости. Из таблицы видно, что приведенные условия сравнительно простн, и их легко проверить на практике, не решая саму задачу оптимизации.
Если установлено, что задача определена, необходимо выделить область оптимума. 3.2.2. Свойства и способы выделения области оптимума Также как в общем случае, рассмотренном во второй главе для векторных задач с регрессионными моделями области оптиму-ма Хо присущи следующие общие свойства 1) Хо -эквивалентность 2) Хо содержится в области неразличимости любого не-улучшаемого решения. 3) Для любого типа функций fa fa, X&J , і =? 4 области оптимума Хо и Хо при отношениях неразличимое-ти W и 2г вложены друг в друга, т.е. Ха Х0 (Утверждение 2.9) 4) Область Парето Хо представляет собой часть области оптимума X, , т.е. Х0 Х0 (Теорема 2.3). С другой стороны, область оптимума для регрессионных векторных задач обладает и некоторыми специфическими свойствами.
Из соотношения 2 ?j% 9fJf/ Утверждение 3.1) и на основе Теоремы 2.2 нетрудно доказать следующую теорему. Теорема 3.1. Для отношений неразличимости V, , еА и % » соответствующие области оптимума вложены друг в друга, т.е.
В большинстве случаев для рассмотренных выше отношений неразличимости, согласно Утверждениям 2.3., 2.5 и 3.2, отно шения предпочтения — транзитивны, поэтому из Теоремы 2.4 и Утверждения 2.1 следует справедливость следующей теоремы, полезной при синтезе алгоритма выделения области оптимума.
Теорема 3.2. Для векторных задач с отношениями неразличимости 7е , 7 fJ Tpfbj у % ? и ф область оптимума Х0 совпадает со множеством неулучшаемых решений на множествах L (x. tj , и X =г О L С /), и равна пересечению Г) L fx&) всех множеств неразличимости каждого оп тимального решения Хл
Алгоритмы выделения области оптимума для скалярных задач оптимизации
Данная модификация осуществляет следующую процедуру 1) В текущей точке Х{ вычислить- V #fr) градиент функции $х)\ 2) Продвигаться по направлению \7 .fxJ с рабочим шагом ft+t =&-«)/ , o o ci. Если CCc+jd: X э то продвижение из точки 3Ci осуществляется го одной из осей координат s у = п , соответст-вующей наибольшей убыли значения функции fxj 3) Процесс повторяется до тех пор, пока значения гради ента V faj не станет меньше заданного числа 8 ; или когда на следующем шаге при продвижении по V-frfec) имеем Хі-/ч$X » а продвижение по осям координат -Є в допустимой области X не приводит к уменьшению значения tL x ) . 4) Вычислить матрицу В(х ) и ее собственный вектор уЧ/nt tv о 5) Продвигаться по /Ґ/Й с мелким шагом до точки Хґ, где выполняется равенство (4.1.6). Вычислить Р0 = //эс зс //, 6) Построить сетку Lfx J в гиперкубе (4.1.8) или гипершаре (4.1.7). 7) На L (х ) с помощью алгоритма AI выделить оценку Хс области оптимума Х0 .
Если размерность области X не велика, а критерий имеет сложный вид (например, недифференцируемый, многоэкстремальный, и т.п.), то целесообразно использовать метод сеток. 4.1.2. Модификация метода сеток В предположении, что допустимая область X ас) гиперкуб , алгоритм может быть описан следующим I) Область X накрывается грубой сеткой С± , узлах кото-рой вычисляются значения {хг) , Хс є С 2)Среди точек Хс Є СІ определяется xi }= jr /ntn pfrjj 3) Определяется множество Mi точек неразличимых с х/ на сетке Qj 4) Каждая точка ХСЄ М± задает центр более мелких сеток СІ t в узлах которых вычисляются значения &cxj \ 5) На объединении сеток У С± вычисляется х = rg mt t$x)\i\ определяется множество неразличимых с х/л)точек, 6) Далее - как в пп. 4-7 модификации метода градиента. Основным недостатком метода сеток является его большой объем вычислений, причем последнее очень чувствительно к размерности задачи. Поэтому если размерность задачи велика, то для случая выпуклого критерия fffxj целесообразно использовать другие методы - например, метод случайного поиска. Ниже описан один из таких алгоритмов.
Пусть на і -ой итерации известна точка лу , вектор -L , компоненты которого задают область изменения переменных, и число S Є foj ) I) Генерируется п. равномерно распределенных случайных чисел %j в интервале f -0,5; 0.5 J и вычисляется критерий $Х) В ТОЧКаХ X; х Xi + dtA f /j ..v Ъ# ) Z tJj 2) СреДИ ТОЧеК X ti Определяется Xt+, = АГ и) Алгоритм аппроксимации любой выпуклой области X гиперкубом описан в работе [57 J . л тік yfrj ; 3) Выделяется с использованием генератора случайных век торов МНОЖеСТВО М{+й = I X/ Є Х- X/ Я Х{+ } решений неразличимых с ХІ+± и находится его центр тяжести Хс+ Вычисляется I fi-Zjl 1 j 4) Процесс повторяется. Останов происходит, когда число итераций больше заданного /V , или значение критерия больше не уменьшается) 5) Определяется Р0 аналогично тому, как это сделано в пп. 4-5 модификации метода Градиента, и генерируется в гипершаре (4.1.7) большой набор случайных точек, среди которых выделя-ется оценка L(x J множества неразличимости LCx J \ 6) На L(x J с помощью алгоритма AI найти оценку Х0 множества Х0 л Процесс образования множества LOcV в п.5 может быть осуществлен следующим образом.
Пусть в гипершаре t% радиуса Ri с центром в точке ос определено множество Mi случайных точек, неразличимых с х Увеличивая радиус / на величину A %i , в кольце A S- нового гипершара St\ = Si UuSi радиуса /Єе +Х = /ЄІ +Д Q генерируют случайные точки и определяют среди них множество АМ случайных неразличимых с X точек. При этом МІ+Л = М UAMi» Процесс продолжается до тех пор, пока до некоторого шага X все новые точки не станут различимыми с х . Тогда L(x )= Мх
