автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Декомпозиция и многокритериальный выбор в проектировании систем

и

0 ^ У

ЧЕРНОВИЦКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. ). ФЕДЬКОВИЧА

на правах рукописи

Шафранский- Сергея Викторович

ДЕКОМПОЗИЦИЯ И МНОГОКРИТЕРИАЛЬНЫЙ ВЫБОР В ПРОЕКТИРОВАНИИ СИСТЕМ

03.13.16 - применение вычислительной техники,-иатаиатическо кодеямровакня а стоматических ыотодов в научных исследованиях.

Автореферат диссертации на соискание ученой степени кандидата §кзико-иатеиатичёских лаук

Черновцы - 1931

Работа выполнена в Киевском о? .на Ленина и ордена Октябрьской Ре~олгчии государствен^ у -верситете им. Т. Г. Шевче....о.

Научный руководитель: доктор физико-математических наук,

профессор Белов Ю. А.

Официальные оппоненты: доктор физико-математических наук, профессор Федоров В. В.

доктор теигкчесхих наук, профессор Гарь, .икс Ф. Г.

Ведущая организация: Москоьский государственный университет им. М. В. Ломоносова, факу у^т вычислительной математик и кибернетики. .

Защита состоится "«//'" /¿/¿Усх. 1991 г. в часов на заседании специализированного ученого советь К. 068.16.05 в Чериовицкон государственном университете ' С 274 012 .г.Черновцы, госуниверситет, ул. М. Коцюбинского, 2, аул. .£. 5. - '

С диссертацией можно ознакомиться в научной библиотеке Черновицкого государственного универсг"ота.

Автореферат разослан " . 1931 г.

Садовяк А.И.

Ученый секретарь специализированного совета К. 053.16.05

'■■ТДЭЛ ft :сертаций |j

I

0Б12АЯ ХАРАКТЕРИСТИКА Р,Г0ТЫ.

Актуальность проблемы. Создание современных сложных технических скотом представляет собой длительный процесс, включающий "несколько тесно взаимосвязанных зтаков, среди koto^jx вазжейашм является этап ispT актирования. Проектирование ионы: рассматриваться как процесс принятия решений, т.е. постановки я реализации эадачз: .ьгбора соответствии с некоторой моделью.

В технических областях исторически сложились проверенные опытом практической деятельности правила оценки проектных разработок. Будучи формализованы в некоторые "разумные" правила выделения оптимальных в том или ином смысле вариантов иэ всего множества реализуемых технг зки альтерг тие они легли в осг -ву обаеЗ теории- выбора. Данные "классические" процедуры выбора достаточно глубока изучены как в теоретическом, так и в практическом плане при рыдании разнообразных задач. " пес -еднее время в теории зыбора наметились тенденции перехода к исследовании нетрадиционных процедур, что позволяет расширить функциональные возможности моделей, повысить их практическую значимость. • Помимо этого, обьеякь-.кк различных эвристических методов на единой методологической основе должно способствовать и пи.внесе-ние в теоркэ- выбора идей "нечеткости" Заде Это объясняется те: , что в реальных зздачах принятий решения цели, ограничения, • критерии зиборг. ъ большей части субъ< тивны и четко не. определены. Поэтому при построении теоретических моделей возникает необходимость использования нечетких множеств, отнесений,- приво-дяаих к понятия нэчеткого выбора.

Однако попытки применения ¿¿иных теоретических моделей в-проектировании схожих мкогокошгонектнщ систем часто. от -».зыва-ются неудачными. Складывается ситуация, когда на практике специалисты предпочитают использовать проверенныэ спитом собственные эвристические и интуитивные процедуры анализа, не гарантируйвие математической: отгималькостн. Невозможность учета всего многообразия свойств, присудил сложной технической системе, приводит к необходимости примеиенкя декожюзнцискиых методов анализа, 'С инаэнорной' точки зрения наиболее встестззншл* представляется подход, кслользувдяй идее агрегирования.- перехода к иовому, качественно отличкону уровни описаний, который соответствует более целостному взгляду аа проектируемую техническую систему.

■ Теоретичесче чсследования в последнем направлении могут служить методологической .основой для разработки конкретных процедур декомпозиции применительно к разлив ж областям техники. Н?~?о"тельно требуется i ст .¿атиэация предлагаемых д« лшози — онньпг процедур, в частности, на основf разработок теорий функций выбора и принятия решений.

Большая груп- .известных декомпозиционных схем включает в процедуры выбора на каздом из уровней агрегирования.решение оптимизационных задач с несколькими критериями. Это обусловлено прин-ципи-льной многокритериальностью любой ело юй технической системы. Имея в виду, что многокритериальный выбор часто является первым этапом более общей и ле всегда математически точно формализуемой процедуры, достаточно важными представляются pas. ¿ботки м°~одов, поз» лляющих исследовать все множество решений многокритериальной задачи чмножество Парето). При численном решении многокритериальных задач возникает проблема учета погрешностей, присутствующие при реал-з<^ии выбранного метода.

Цель работы состоит в разработке обобщенных декомпозиционных процедур решения задачи выбора и их систематизации на основе единого подхода, с учетом свойств применяемых механизмов выбора и методов агрегирования; '

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

Научная новизна полученных в раб<-~е результатов заключается в следующем:

1) В терминах функций выбора разработан- ряд новых формали-. зованных процедур'решения задачи выбора, основанных на многоуровневом агрегировании структур описаний проектных вариантов.

2) Сформулирована задача выбора в нечеткой постановке, введены и исследованы свойства v ераторов нечеткого выбора, понятие ■ варьируемого выбора. Разработаны декомпозиционные процедуры решения задач нечеткого выбора.

3) Декомпозиционный подход к кретазироват' на е../чай "хлассическц-рационального выбора, в том чь^ле ь-оора по вертким отношениям предпочтен т. . *

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

Методика исследований, проведенных в диссертационной заботе, основана на методах теории функций выбора, нечетких лнож' -.тв и отношений, многокритериальной оптимизации, исследования операций и вычислитель' ого эк<*~еримента.

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

Апробация и публикации. По результатам делались сообщения и"доклады на

- научно-исследовательском очминаре кзфетры исследований оперший факультета ВМиК МГУ; ;

- научно-проблемном семинаре в Институте,проблеи кибернетики,' г. Москва;

- специализированных семинарах НПО "Квант", г. Киеь;

- научно-исследовательских и проблемных семинарах кафедр численных методов математической физики, моделирования словных систем, теории программирования ""У.

- республиканском семинара Черновицкого университета.

По результатом диссертационной работьт опубликованы 4 рабо-и.

На защиту выносятся следусцие результаты:

- обобщенные декомпозиционные процедуры решения задачи выбора при проектировании Сдля выбора обаего вида, классически-рационального и нечеткого выбора); •

- обоснование применения специального семейства сверток для решения задач многокритериального ьыбора в виде:

неулучааемых оценок параметра семейства, гарантируввих заданный уровень погрешности; '

алгоритмов генерации весовых коэффициентов, определявших . последовательность вычислений;

оценок относительной точности аппроксимации множества Парето при наличии реальных вычислительных погрешностей;

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

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

СОДЕРЖАНИЕ ?АР'"Ы.

Рассыотрени задач в работе проводится по схеме от общего к частному: решение общей задач-* выбора (глава 1), классически-рациональный выбор Сглава 2), многокритериальный выбор Сглава 3). В .лаве 4 рассматриваются приложения т ории к проектированию антенных систем.

• В главе 1."Декомпозиция задачи выбора при проектировании сложных систем" рассмотрены вопросы разработки , декоыюэ"",ионных пр цедур реализации выбора оптимальных проектных решений при проектирования слогных систем. Выбор описывается • как; 'результат применения функции С к множеству проектных альтернатив ,Х.

В ' 1 приводеьы краткие сведент* из теории выбора-, сформулированы основные характеристические условия для функции выбора г Ссумыаторности 3, константности В> наследования ¡Ь* независимости от отвергнутых вариантов Ф, согмасм С и ДР.). Дано понятие агрегирования структ^ описаний элементов м-охества X, приводящего к построению иерархии описаний.сложное, системы, с целью упрощения решения задачи вибора. Одноуровневый процесс агрегирования описывается уравне..лем

X « Г С X V. 113 •

где Г - оператор агрегирования, для которого существует обратный оператор Г X -новое бази-чое множество . проектов. Пусть С - функция выбора агрегированного уровня .

Выделим условия согласования фун: ий выбора исходного и агрегированного уровней и оператора агрегирования, которые определяют степень эффективности выбранного способа агрегирования. • ' '

Определение 1.1. Для ф. .:кций выбора С,. С и оператора агрегирования Г имеет место первое условие согласования, если выполняется:

Г СССХЭЭ С ССГ 4X3)5 имеет место второе условие согласования, если выполняется

г "* сссх: а ссг -чх)}. ■ . • ' сзз

Обозначим С' <• Г СССК>Э, ССХ'.Х ) « ССХ) л X' .

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

Теорема 1.1.

1. Пусть для функций выбора С, С и оператора агрегирования Р выполняются условия согласования С2), (3), тогда ССХ) а С'.

2» При выполнении условия согласования С2Э справедливы следующие декомпозиционные соотношения

С п СССх», если .С € 3 ;

* Х\С'

С и ССХЧС'Э,

С СХЭ ■ если С е К и включение С2) - строгое,

С' и ССХЧС'; С' и ССХЧС'Э),

если С 6 И п О; С и ССХ X }, в противном случае.

3. При выполнении условия согласования СЗ) справедливы , следующие декомпозиционные соотношения

ССС), если СО;

С СХЭ «

. ССС ; X 3, в противном случае.

. Исследован тахюз случай неполного выбора агрегированного уровня и случай, когда оператор агрегирования не является взаимно-однозначным.

В последующих.параграфах развиваемый подход обобщается на задачи нечетко определенного выбора.

• В I 3 собраны основные сведения, связанные а нечетким выбором. В этом случае вся информация о предпочтительности содержится в нечетком множестве

ФСХ) * < Сх, (л хСх5), х « X, р к ! X »> 10; 11 >

где § - оператор нечеткого выбора, X' 5 X Ф СХ') а ^ 'Значение характеристической функции ц ^Сх) мозно интерпретировать как степень принадлежности элемента множеству, являющим-'

ся решением задачи выбора.

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

С „.ХЭ " < х 6 v | (j хСх) > v У

уровня v из некоторого интервала варьирования [ а 5 ß 3, заданного априори.

Определение' 1.2. Числовые функции р. Т) : X -> 10; 11 называются t а ; " 3 - эквивалентными на Х'£ X , если выполняется: -

V х е X' 7} СхЗ 5 а, если р СхЗ £ а ;

Т) СхЗ в juCxJ , если а < ^ СхЭ < /Э ; . 7) Сх) Z ß , если ц СхЗ 2: ß . В i 4 С о-ое делен: 1.4) введены следующие обобщенные характеристические условия для оператороь «четкого выбора: сумматорности, Ф. е S (0 ß} , если v X' с X

и р х, t а ; (3 Э -эквивалентны на X' ; константности, Ф € К ta ^ ,'. если у X' с X из у , . Э > с*

следует 1а; ninC уСХ'З; /?3 3 -эквивалентность р х и М • и из у СХ'З < /3 ■> ух,СхЭ < в?хС es; уСХЗ ) V * е X'; независимости от отвергнутых ва^лантов, Ф е О to , эсли

V Х'с X, уСХ'З > уСХ\Х'Э, КХ'З > а, уСХЧХ'Э </3.=> InaxC а; уСХ\Х')3; ninC уСХ'З; ß33 ^эквивалентность ^ ж .

' sup р „СхЭ, X' 0 , х С X'

Здесь уСХ'З , ' •

О, X' »'0

В работе определена взаимосвязь обобщенных характеристических условий для операторов нечеткого выбора с характеристическими условиями для функций выбо!-- (теорема 1.43. . ..

Доказан ряд лемм,, устанавливавших конкретный видподмножеств. 1а; /33 - варьируемый выбор на которых эквивалентен вр"ару ни всем множестве X.

В S 5 рассмотрены вопросы, касавилеся решэкая зада нечеткого выбора.. Вв ,ено следувиеа общее условие.

Определение 1.5. Для операторов нечеткого выбора Ф > Ф и оператора агрегирования Г выполнено условие ограниченного рассогласования , если для любого х € X, х € Г"' СхЭ справедливо:

гсахС 0; Д СхЗ - 51 3 < м „СхЗ < и1пС 1; Д _СхЗ + <5? 3. х * х

Здесь Ф - оператор выбора агрегированного уровня, процесс

агрегирования описывается уравнением С13, р ^ = Ф СХ), Г -

взаимно-однозначный оператор. Обозначим С^ ■ Г ССуСХЗЗ.

Основным результатом является следующая

Теорема 1.5. При выполнении условия ОР^ числовая функция пх , 1а , ¡3 3 - эквивалентная исходной

функции ^ х = Ф СХ), определяется следующим образок :

!а , если х е ХЧС^; 1 , если х е С И уСх)' ""

где

если х € С^, ч

Сх>, если Ф е $[Д

Сх; у), где у € -произвольный вариант, если ;

, ЭСШ * € О |а#/3> >

X , в- противном случае.- |

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

Основные понятия классически-рационального (к. -р. 3 выбора изложены в § 1. Здесь т .же приведены утверждения, устанавливающие взаимосвязь топологических свойств бинарных отношений, . заданных на базисном множестве, с характеристическими свойствами реализуемых ими функций выбора. В § 2 предложенный ранее з главе 1 декомпозиционный подход развит применительно к-случаю к. -р. механизмов выбора. • Введены условия согласования • отношений смежных уровней иерархии и оператора агрегирования, ' отражаюияв некоторые основные случаи "трансформации" парных

предпочтений:

условие сохранения строгой доминируемости : V х,у с X, Су,х) е I, х е Т " СхЗ »>

3 у € Г Су) Су,х) € Р ; условие необрацения строгого доминирования :

V х, у еХ, С? х) е Р, х е Р"' Сх), у е Р Су) »>

Су, хЗ ей; условие сохранения эквивалентности:

V х,у е X, Су,х) € I, х е Р "Чх?, у е ? "Су) »> Су,х) е I,

где Р ■ Яч Л"', I * Я п К"1; И» £ - рефлексивные отношения предпочтения соответственно исходного и агрегированного уровней. Установлена связь данных условий с введенными ранее услови- . яки С2) и (3). Приведены.декомпозиционны© процедуры, соответствуете "каждому из рассмотренных условий согласования. Некоторые важные для практики частные случаи организации агрегирования и соответствующие им эмпирические процедуры собраны в 3.

Введение в рассмотрение нечетких бинарных отношений поз- -волило обобщить а § 4. 5 данные результаты для решения задач нечеткого к. -р. выбора.

Дальнейший сужением множества рассматриваемых задач является класс многокритериальных задач выбора, изучению -'которых посвааена глава 3 "Численные методы решения задач многокритериального выбора".

■£ 1 данной главы дает основные сведения из теории многокритериального выбора. Рассматривается задача аппроксимации по векторному функционалу множества Парето СрШ реионий многокритериальной задачи Кх) » С Г Сх), ... „СхЗЗ «> н1п, х € )., ' У » ГСХЭ с Е в , с поиоаьп реализации конечного чгсла опти-

•Шзационных задач с Функцией-сверткой частных критериев - вида

в

Г V < .а 1 1/о

Рас X, ГСх) ) в 142 С ^ ^Сх 33 ,1 , а £ 1,

ы (4)

X € ЛСа,ЬЗ » С X € Е " I 0 < а,< X. 5 Ь. , У X. =1 >,

1 1 1 15*1

Данное семейство сверток, зависящих от векторного параметра X, является обобщением известное линейной свертки Карлика Сслучай а = 13 и минимаксной свертки Гермейера Св пределе при а ->°° 3 В отличии от последнего семейства свертки ,С43 сохраняют

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

В § 2 (определение 3.1) введено понятие регулярности множества оптимальных оценок: СрШ равномерно регулярно с параметром ц, если для у у° е CpCY) существует ц > 0 такое, что выполняется

Ух / у^ 5 1 + t -> У4 / у° 2 1 - t/*

V t 2 0, у fi ср CY).

Доказана

Лемма 3.1. Если множество С pCY) равномерно регулярно

о константой р >т-1, то выполняется:

С С Y Э « U Arg Hin F, С Л, у ).

Р X € Л<о,1 > у € Y 1

Использование линейного семейства сверток позволяет выделить лишь некоторое узкое подмножество в CpCY), для расширения которого следует использовать в С4) значение степенного параметра а > 1. Однако при увеличении значения а растут и вычислительные затраты на оптимизацию. В работе получена неулучшаемая нижняя оценка величины степенного параметра, гарантирующая заданный уровень погрешности определения точек

г -»-»■

СР CY). Введем обозначение q.Cy) «I у, У 1/у,

1 Je» 3 '

Теорема 3.1. Пусть у° € Ср CY), '« q. v./), сг > 0, у' е Arg nin F„ С у

. у И • _

Тог*а условие yt' /у° < 1 + er, 1 ■ 1,в , будет выполнено при

а > о' i. 1, а' ■ In в / In С1 + оЭ. Если CpCY) регулярно в точке у0 с константой ц, а < ц £ а-1, то требуемое значение а' определяется как решение уравнения:

С 1 + а )а + Са-1) С 1 - o/\i )а » в.

В i 3 исследована погрешность численной реализации метода сверток. • Зависимость относительной точности аппроксимации элементов множества оптимальных оценок от погрешностей задания исходной информации и вычислений получена в виде некоторого неявного уравнения, решение которого единственно и легко опрэдо-

ляется численными' расчетами.

В { 4 приведены алгоритмы генерации значений векторного параметра семейства сверток, использование которых позволяет оптимизировать процесс вычислений по количеству итераций.

£ 5 посвяаен обсуменив области применимости методов различных типов к -эшенив многокритерильных задач. Предлагается ряд "гибридных" алгоритмов, объединявших полезные свойства различных методов.

Глава 4 "Проектирование антенных систем" демонстрирует применение теоретических результатов работы к проектирование дискретных антенных систем.

В §•1 кратко обоснован выбор для рассмотрения антенных решеток, дано описание особенностей предметной областа.

§ 2 посвяаен применений методов сверток многокритериальной оптимизации в задачах синтеза параметров антенных систем. Рассмотрены три постановки задач синтеза линейных антенных решеток при наличия нескольких критериев эффективности. В § 3 данные оптимизационные методы использозаны в рамках декомпозиционных процедур, призванных упростить задачу синтеза. Две предложенные здеоь "гибридные", декомпозиционные процедуры объединяет."сверточные" градиентные оптимизационные методы, ' рассмотренные в главе 3, и известные сеточные методы решения -' задач выбора.- Данные процедуры полностьв вкладывается в формализованные декомпозиционные схемы, изученные в предыдущих главах работы. •

Конкретно решены задачи синтеза диаграмм направленности антен- ' ной системы, входящей в состав ИВК, работаваего в условиях и:-.-.яичия активно действуваих помех в области видимых углов, в пределах некоторых угловых секторов. Ставится.задача распределения ресурса модности по. элементарным излучателям с цельо формирования провалов в ДН в данных угловых секторах. В качестве критериев рассматривались среднее значение модности излучения в секторе помех) ширина диаграммы направленности, уровень бокового излучения, коэффициент направленного действия антенной решетки. Приведенные в тексте результаты проектирования вклвчавт числовые данные синтеза и графические представления диаграмм направленности синтезируемых антенных систем.

•Расчеты проведены с помоаьв разработанного комплекса программ решения многокритериальных задач, вклвчавьих группу

"сверточных" градиентных методов оптимизации, ряд известных сеточных методов выделения множества отимальных решений, а также вспомогательные модули расчета точностных оценок, диалогового взаимодействия, выдачи результатов в графическом виде и т.п. Программы реализованы на языке Си (версия 2.0 Typdo-Си) в среде операционной системы MS-DOS для IBM PC - совместимых компьютеров.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ.

Основными положениями диссертационной работы являются:

- разработка декомпозиционных процедур решения задачи выбора (з том числе классически-рационального и нечеткого выбора )

при проектировании, их систематизация на основе единого дхода, с учетом свойств применяемых механизмов выбора я методов агрегирования;

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

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

По результатам диссертационной работа опубликованы работы:

1. Белов D. А., Гальперин В. А., Шафранский C.B. Автоматизация проектирования сложных систем на основе эвристического поиска и имитационного моделирования. 2-ой североморавский симпозиум социалистических- стран "Имитация систем", июнь 1089. Тезисы доклада. - Острава,. 1989.

2. Белов Ю. А., Шафранский С. В, ¿^композиция задачи выбора при проектировании сложных систем //Изв. АН СССР. Техни-

ческак кибернетика, N 2, 1990, С. 173-177.

3. Бэлой С. А., Шафранский С. Б. Декоыпозвдкоаикд процедуры в задачах выбора оптимальных проектов //Доклады АН УССР, N с, 1931, С 47 - 31.

4, Белов Ю.А., Шафрансхий С.В. Применение дифференцируемого секайстг сверток в задачах юшгокритериальной оптимизации //Доклады АН УССР, И 3, 1991, С. 63 - 6Г.