Содержание к диссертации
Введение
1 Многорежимные системы и задача синтеза 6
1.1. Многорежимные системы 6
1.2. Общая постановка задачи синтеза 11
1.3. Общие подходы к решению задачи синтеза МРС 13
1.4. Одпокаскадные схемы 15
1.5 Дну хкасладные схемы 25
1.6 Многокаскадные системы 37
1.7 Описание программных рсалюации задач синтеза 33
2 Статистическое исследование и программная реализация случайного поиска 42
2.1 Описание метода случайного поиска 43
2.2 Статистическое исследование метода случайное поиска
2.3 Различные модификации случайного поисьа 59
2.4 Описание диалогового программного комплекса глобальной оптимизации "OPTIMUM" 64
3 Многокритериальная оптимизация 80
3.1 Общая постановка задачи и метод решения 81
3.2 Статистические исследование метода решения 87
3.3 Описание диалогового программного комплекса многокритериальной оптимтации "PARETO" 93
Заключение 108
Библиография 109
Приложение 117
- Общие подходы к решению задачи синтеза МРС
- Описание программных рсалюации задач синтеза
- Описание диалогового программного комплекса глобальной оптимизации "OPTIMUM"
- Описание диалогового программного комплекса многокритериальной оптимтации "PARETO"
Введение к работе
В этой работе исследуются, методы глобальной и многокритериальной оптимизации, в основе которых лежат различные модификации ада-птщшого метода случайного поиска, описываются разработанные комплексы программ оптимизации с развитым пользовательским интерфейсом я предлагаются подходы к синтезу некоторых классов систем со структурным управлением, существенно использующие созданные программные комплексы глобальной и многокритериальной оптимизации.
Несомненно, что каждая из перечисленных выше проблем достаточно широка и не может быть решена в рамках одной диссертации. Основная цель этой работы - исследование ъ указанных направлениях ряда частных задач с дальнейшим применением полученных в работе результатов на практике.
Практическое применение МРС находят для синтеза механических коробок перемены передач [22,34. 43, 55, 67], многофункциональных логических модулей [38], структурно перестраиваемых приборов СВЧ [15, 36], радиоэлектронных [15, 36] устройств и др.
В первой главе приводится краткое описание систем со структурным управлением, у которых процесс функционирования зависит от дискретной настройки системы, путем изменения ее структуры на определенный режим работы. Такие системы еще называются многорежимными (МРС), или структурно управляемыми, системами (СУС) [54]. Для их описания используются сетевые модели [39, 54].
Приводится общая постановка задачи синтеза МРС и описываются подходы ее решения. Рассматриваются задачи синтеза мно™режимных систем, состоящих из двухполюсных элементов. При тох\ї используются подходы, позволяющие сократить перебор на множестве дискретных структур-Предлагается модификация одного алгоритма минимизации элементов управления в схемах с максимальным числом режимов при фиксированном количестве функциональных элементов. Описывается разработанное программное обеспечение, реализУЮ11 ее разработанные алгоритмы синтеза на ЭВМ с использованием объектно ориентированного подхода.
Bo-второй главе приводится описание одного способа организаций случайного поиска (СП) и проводится его статистическое исследование, На базе проведенных испытаний предлагаются различные модификации Си, эффективность которых ивдтвервдэтта pm- wtsarai дажна-ми на известных тестовых функциях.
В заключении второй главы описываете основные принципы построенного диалогового программного комплекса глобальной оптимизации "OPTIMUM", из которых можно выделить, прежде всего, применение такого средства программирования как DLL (Dinamic Link Library). Основные цели использования Dl/L: представление задач оптимизации на языке ЭВМ, программное равнение задачи оптимизации на модули целевой функции к ограничений с дальнейшим их независимым друг от друга использованием, решение важной проблемы совместимости программного комплекса с модулями программ пользователя.
Третья глава посвящена многокритериальной оптимизации, В ней предлагается и исследуется метол постро ния множества Парето.
В ее заключении проводится описание специально разработанного диалогового программного комплекса многокритериальной оптимизации "PARTO \ Особое внимание при эт™ уделено использованию в многокритериальной оптимизации принт 1103 динамически подключаемых библиотек DLL.
Проведенные исследования показали вь °кую практической эффек тиішость всех рассмотренных здесь методов оптимизации. Именно поэтому было принято решение о создании технологии ROOT - Red Organization of Optimization Technology, объединяющей все исследованные методы с целью решения различных іадач оптимизации, возникающих на практике.
Для общедоступности к технологии ROOT построен специальный Интернет-сайт, описание которою находится в приложении.
Общие подходы к решению задачи синтеза МРС
В этой работе исследуются, методы глобальной и многокритериальной оптимизации, в основе которых лежат различные модификации ада-птщшого метода случайного поиска, описываются разработанные комплексы программ оптимизации с развитым пользовательским интерфейсом я предлагаются подходы к синтезу некоторых классов систем со структурным управлением, существенно использующие созданные программные комплексы глобальной и многокритериальной оптимизации.
Несомненно, что каждая из перечисленных выше проблем достаточно широка и не может быть решена в рамках одной диссертации. Основная цель этой работы - исследование ъ указанных направлениях ряда частных задач с дальнейшим применением полученных в работе результатов на практике.
Практическое применение МРС находят для синтеза механических коробок перемены передач [22,34. 43, 55, 67], многофункциональных логических модулей [38], структурно перестраиваемых приборов СВЧ [15, 36], радиоэлектронных [15, 36] устройств и др.
В первой главе приводится краткое описание систем со структурным управлением, у которых процесс функционирования зависит от дискретной настройки системы, путем изменения ее структуры на определенный режим работы. Такие системы еще называются многорежимными (МРС), или структурно управляемыми, системами (СУС) [54]. Для их описания используются сетевые модели [39, 54].
Приводится общая постановка задачи синтеза МРС и описываются подходы ее решения. Рассматриваются задачи синтеза мнорежимных систем, состоящих из двухполюсных элементов. При тох\ї используются подходы, позволяющие сократить перебор на множестве дискретных структур-Предлагается модификация одного алгоритма минимизации элементов управления в схемах с максимальным числом режимов при фиксированном количестве функциональных элементов. Описывается разработанное программное обеспечение, реализУЮ11 ее разработанные алгоритмы синтеза на ЭВМ с использованием объектно ориентированного подхода.
Bo-второй главе приводится описание одного способа организаций случайного поиска (СП) и проводится его статистическое исследование, На базе проведенных испытаний предлагаются различные модификации Си, эффективность которых ивдтвервдэтта pm- wtsarai дажна-ми на известных тестовых функциях.
В заключении второй главы описываете основные принципы построенного диалогового программного комплекса глобальной оптимизации "OPTIMUM", из которых можно выделить, прежде всего, применение такого средства программирования как DLL (Dinamic Link Library). Основные цели использования Dl/L: представление задач оптимизации на языке ЭВМ, программное равнение задачи оптимизации на модули целевой функции к ограничений с дальнейшим их независимым друг от друга использованием, решение важной проблемы совместимости программного комплекса с модулями программ пользователя.
Третья глава посвящена многокритериальной оптимизации, В ней предлагается и исследуется метол постро ния множества Парето. В ее заключении проводится описание специально разработанного диалогового программного комплекса многокритериальной оптимизации "PARTO \ Особое внимание при эт уделено использованию в многокритериальной оптимизации принт 1103 динамически подключаемых библиотек DLL. Проведенные исследования показали вь кую практической эффек тиішость всех рассмотренных здесь методов оптимизации. Именно поэтому было принято решение о создании технологии ROOT - Red Organization of Optimization Technology, объединяющей все исследованные методы с целью решения различных іадач оптимизации, возникающих на практике. Для общедоступности к технологии ROOT построен специальный Интернет-сайт, описание которою находится в приложении. Основные обозначения, принятые в работе В этой работе под многорежимной системой (МРС), как и в [30. 56], будет пониматься система с переменной структурой, у которой настройка на определенный режим работы (т.е. на определенную выходную функцию) осуществляется ну гем дискретного изменения связен между функциональными элементами, составляющими систему. Исследуемый здесь класс МРС состоит ЕП двухполюсных функциональных элементов и бинарных элементов управления. В нашем случае для описания таких систем удобнее использовать графовые модели.
Описание программных рсалюации задач синтеза
До сих пор рассматривались алгоритмы, у которых использовался прямой подход к синтезу систем. Однако в ряде случаев, когда для конкретного вида матрицы h[l : гЛ : d\ удается найти простой алгоритм построения функционального графа системы, представляет интерес обратный подход, Итак, пусть р = 3d и матрица А[1 : р. 1 : d\ определяет все возможные режимы, которые можно получить в МРС с d функциональными элементами. И предположим, что мы можем решить задачу по минимизации критерия на множестве значений переменных из Ad и на множестве всех отображений J : (1 : /) —» (1 : р). На практике в нашей работе для этик целей был использован случайный поиск в комбинации с модифицированным методом динамического программирования (методом сдвига [54]) с использованием теоремы 1.3.1.
И теперь стоит задача по выделенным уравнениям множества Р — (1 : I) построить функциональный граф. В общем случае эта задача требует перебора. Поэтому исследуем, какими свойствами должна обладать эта система, чтобы функционачЧЬ-ные графы были заданного класса. Естественно, в этом параграфе нас будут интересовать однокаскадяые функциональные графы. Теорема 1.4.2, Бели матрица А[Р, 1 : d\ определяет однокаскадную схему МРС, то для всякого Є 1 : d все элементы h[P,i] должны быть либо неотрицательными, либо неположительными, Другими словами, любой столбец матрицы не может одновременно содержать и — 1 и +1. Для доказательства предположим противное, что г -ый столбец содержит как —1, так и 4-І. Это означает, что и одном режиме в соответствующей непи от входной вершины к выходной этот элемент расположен в одном направлении, а с лепи другого режима — в обратном, т.е. существует две цепи: от входной вершины и до обеих вершин /1-го ребра функционального графа. Последнее означает, что в функциональном графе имеется цикл. Противоречие. Из этой теоремы следует, что, если существует столбец с отрицательными единицами, то их все можно заменить на положительные. В связи с этим, не теряя общности, будем считать, что ft[s\j] Є {0,Н-1}, Далее приведем алгоритм построения однокаскадной схемы МРС по выделенной матрице h[P, 1 : rf], который даст конструктивные условия существования (или отсутствия) такой схемы. Выделим is матрице h[PA : d\ столбец, содержащий максимальное число единиц. Пусть это будет столбец г-\. Разобьем матрицу А[Р, 1 : d\ на две подматрицы fe[P],l : d] и h\}\.\ : d] такие, что h\jJi] = 1, если j Є Fi, и A[j, i] — 0, если j Є P[f- Удалим из обеих матриц выделенный столбец. Обозначим первую подматрицу Л{1). а вторую - А(0], Повторим ту процедуру для каждой из полученных подматриц, В результате получим уже подматрицы: h[l„ 1), /ь(0т0), - полученные из Л(1) иЛ{0,1}. ft(0,0} - порожденные второй подматрицей Далее выполняем аналогичные действия над каждой из вновь полученных матриц. Если при этом в какой-то из подматриц появляется нулевой столбец, то он из нее удаляется. Назовем такую процедуру разложением матрицы, Понятно, что последовательность получаемых друг из друга подматриц, в которых происходит удаление единичных столбцов порождает цепочку ребер функционального графа, начинающуюся в входной вершине. Предположим i-ът. столбец с единицами удалился в двух различных подматрицах. Это означает, что к і-му ребру в функциональном графе ведут две различные цени от вершины ; = 1, т.е. в графе существует пикл, что невозможно. В этом случае скажем, что матрица неразложима. В противном случае - разложима. Теперь можно сформулировать следующую теорему существования однокаскадной схемы, Теорема 1.4.3. Матрица Ь[Р„1 : d\ порождает однокаскадную схему тогда и только тогда, когда: 1) ее можно привести к матрице, не содержащей отрицательных элементов, и 2) матрица является разложимой. Необходимость следует из теоремы 1.4.2 и из описания процедуры разложения, матрицы. Достаточность следует и1} того, что если маг-трипа разложима, то последов а гель ноет и получаемых подматриц порождают цепи ребер, начинающихся в вершине и = 1, по которым функциональный граф однозначно восстанавливается. Далее матрицу h[P l : d], которую можно привести к матрице, не содержащей отрицательных элементов, будем называть положительно приводимой. Двухкаскадные схемы отличаются от однокаскадных тем, что в каждом каскаде содержится не менее одного ребра: \D\\ 1, \D?\ 1, И для двухкаскадных схем основную роль играют положительно приводимые матрицы, Теорема 1.5,1. Двухкаскадная схема реализует заданную матрицу h[P, 1 : d\ только в том случае, если она положительно приводимая. Действительно, если некоторому ребру (ijj) в матрице /;[Р, 1 : d] соответствует столбец? в котором встречаются элементы — 1 и 4-1, то это означает, что существуют две цепи: от вершины и — 1 до вершин ( и j (если ребро (iyj) Є D\) или от аершин itj к вершине w — г (если ребро (i,j) Є D2). В любом случае получается цикл, что в функциональном графе невозможно, Обратное в общем случае неверно. Приведем пример. Пусть d = 3 и соответствующие ребра обозначим: а,Ь,с. Предположим матрица Ь имеет вид: Покажем, что эту матрицу реализовать в двухкаскаднои схеме невозможно. Эта матрица порождает три цепи, с множествами ребер: 1){а,Ь}; 2){а,с}; 3){6.с}. Путем взаимного переименования ребер любую из этих трех цепей можно перевести в другую. В связи с этим размещение ребер по каскадам можно начать с любого ребра. Пусть ребро а Є D\, Теперь ребро ft можно поместить либо в Х?ь -чибо в Х - Пусть ребро помешается в D[. Таким образом, в D\ получаем цепь ребер из а и Ь. Но тогда невозможно реализовать одну из оставшихся цепей-Аналогичная картина получается, если ребро ft поместить в D- Приведенный факт усложняет использование обратного подхода для решения задачи синтеза д&ухк&скадных схем- С другой стороны применение прямого подхода требует нахождения отображения у? : (1 : /) — {1 : г) на каждом шаге поиска ввиду того, что на множестве вершин {2, 3,... j z — 1} симметрическая группа уже не работает.
Описание диалогового программного комплекса глобальной оптимизации "OPTIMUM"
Далее представим расчеты для второй модификации - СП с ветвлением. Из рисунков 2.3.2 ж 2.3.3 видно, что для некоторых реализаций случайного поиска СП с ветвлением превосходит СП без ветвления.
Задача определения нескольких (или всех) глобальных экстремумов Очень часто ta практике встречаются случаи, когда целевая функция обладает к$ одним, а несколькими глобальными экстремумами, которые с практической точки зрения могут быть отнюдь ке равнозначны между собой. Отсюда, возникает задача нахождения всех или нескольких глобальных экстремумов. Обычно для решения таких задач используются генетические алгоритмы, что объясняется, прежде всего, их особенностями [19]. К сожалению, для генетических алгоритмов нет соответствующих расчетных данных, по которым можно было бы сравнить эффектиБыость методов.
Здесь приводятся расчетные данные, связанные с определением всех глобальных экстремумов многоэкстремальной функции Растриги-на (функция 2). Эта функция имеет в области поиска 96 локальных и 4 глобальных Экстремума. При применении СП с числом ветвлений, равным количеству глобальных экстремумов, получены следующие результаты: всроягГКосГЬ определения всех четырех глобальных экстремумов равна 0,6 а вероятность определения трех из четырех уже -0,95, При этом количество реализаций алгоритма (число вычислений функции цели) выбрано как минимально Необходимое для нахождения одного глобального экстремума с вероятностью, близкой к 1.
В процессе проектирования системы учитывались характерные особенности диалога, возникающего в ходе решения таких задач, из которых можно выделить следующие: - способ представления задач оптимизации в ЭВМ; известно, что различные программные системы, позв лаЮщИе пользователю решать свои задачи оптимизации, предполагают Применение своего (встроен ного) языка программирования, которым еще необходимо овладеть; предлагаемая здесь программная система позволяет применять 1) лю бой кз существующих сегодня языков программирования при использо вании механизма динамически подключаемых библиотек (DLL) и 2) че тыре наиболее распространенных языка Программирования {C/C++, BASIC, PASCAL, FORTRAN) при использовании готовых программ ных блоков; - адаптация используемого метода глобальной оптимизации иод опре делённый класс решаемых задач; - визуализация качественного контроля получаемого решения; Программная реализация "OPTIMUM4 осуществлена при помоши объектно- ориентированного языка nporpa MMpoIiaiiafl C++ в интегрированной среде Borland C++ Bunder 5,0 с использованием библиотеки классов VCL и средств DLL (динамически подключаемых библиотек). Программа функционирует в операционных средах Windows 9х и выше. и OPTIMUM" включает в себя различные средства диалога " человек-машина" , позволяющие пользователю; изменять параметры используемого метода глобальной оптимизации, включаться в ход решения ЭВМ задачи оптимизации на определенных этапах и при необходимости изменять его, С помощью средств визуализации решаемой задачи следить за процессом вычислений, адаптировать параметры метода оптимизации иод конкретные особенности задачи. "Правильное использование всех этих диалоговых средств, в комбинации с. содержащимся в комплексе методом оптимизации, позволяет пользователю более эффективно справляться со своими проблемами оптимизации, нежели в отсутствии диалога, Наряду с этим на начальном этапе знакомства с комплексом существует опасность перегрушгь пользователя информацией об особенностях используемого метода оптимизация и предоставленных к нему средств диалога "человек-машина1 . Возможное следствие всего этого не улучшение, а ухудшение эффективности решения задачи оптимизации, Именно поэтому "OPTIMUM ориентирован также на функционирование с минимальным изменением своих настроек (в частности, исходные параметры случайного поиска выбраны в результате многочисленных статистических расчетов на различных тестовых функциях). Перейдем к краткому обзору основных окон (подсистем) программного комплекса. - Окно ввода параметров случайного поиска. Позволяет ввести (изменить) параметры случайного поиска. В окне располагается график которого - визуализация значений параметров СП с целью адаптации Представлений пользователя о поведений алгоритма оптимизации. Окно контроля скласти оптимизации. Позволяет пользователю визуально контролировать область определения значений аргументов функции цели. Как видно из рис. 2.4.2, изменение левых и правых границ по каждой переменной проводится с помощью графических линеек прокрутки . Каждая линейка содержит текущее оптимальное значение аргументов целевой функции. - Окно рвода целевой функции (рис, 2.4.3). Целевая функния может задаваться двумя способами: 1) путем подключения с помошью средств DLL и 2) путем задания программного кода в окне программы; оба этих способа более подробно будут описаны ниже. - Окно вывода готового решения (рис. 2.4.4]. Кроме найденного оптимального значения заданной целевой функции данное окно содержит еще график, позволяющий пользователю качественно оценить близость найде иного решения к истинному. - Окно локального спуска (рис, 2.4.5). Позволяет пользователю, используя методы локальной оптимизации, уточнить текущее значение целевой функции. В качестве метода локальной оптимизации здесь предлагается использовать метод Хука Дживса [17]. - Окно expert (риє, 2.4.6). Дает возможность пользователю методом статистических расчетов адаптировать параметры случайного поиска под конкретный класс задач, с которыми он имеет дело в своей профессиональной деятельности.
Описание диалогового программного комплекса многокритериальной оптимтации "PARETO"
Существует большое количество различных стохастических методов глобальной оптимизации, и то, насколько эффективен тот или иной метод, зависит не только от него самого, но еще и от выбора его параметров. Для определенного класса функций всегда можно подобрать такие значения параметров поиска, при которых обеспечивается наиболее эффективная работа метода, В связи с этим в комплексе предусмотрена возможность более- гонкой настройки поиска к классу задач, относящихся к профессиональной деятельности пользователя.
Предлагается решать эту проблему предварительного проведения большого количества статистических исследований на классе модельных задач пользователя с последующей выдачей рекомендаций,
Для ее решения была специально создана подсистема "expert", позволяющая пользователю путем проведения статистических расчетов подобрать такие параметры случайного поиска, которые обеспечили бы лучшую сходимость для исследуемого класса задач (рис. 2.4.6), чем в том случае, когда пользователь применяет комплекс со стандартным набором параметров поиска.
В качестве критерия оценки ефективно с ти случайного поиска в подсистеме "expert71 выбрана зависимость вероятности нахождения глобального оптимума от числа обращений к целевой функции. Подсистема "expert" состоит из: 1) полей для ввода параметров, используемых при статистическом исследовании, 2) графика, позволяющего визуально оценить проведенные эксперименты (рис. 2.4.6 А), 3) таблицы с результатами проведенного эксперимента (рис. 2.4.6 В). Поля ввода параметров. Перечислим присутствующие в подсистеме "expert" поля ввода и опишем их назначение. Начальное число шагов - значение числа шагов, с которого начинается построение графика А. Величина шага - значение шага, с которым меняется начальное число шагов. Число реализаций - количество статистических испытаний для оценивания вероятности нахождения решения. Точность - величина, задающая окрестность вокруг точки решения задачи (при попадании в заданную окрестность статистический эксперимент считается удачным). Список argmin - список оптимальных значений аргументов тестовой задачи. График и таблицаполучаемых решений. График используется для визуализации сравнения получаемых в ходе статистических расчетов графиков, при построении которых на оси nstep откладывается число обращений к тестовой задаче алгоритмом оптимизации, а на оси Р -полученная вероятность. Таблица В под графиком хранит набор значений, соответствующих отдельно взятой кривой. Смена значений в таблице осуществляется сШс ом мыши на соответствующей траектории. При этом пользователь может увидеть реальные значения полученных результатов эксперимента. Подсистема "expert" также предоставляет пользователю возможность сохранить полученные результаты экспериментов в файле или распечатать их пля дальнейшего анализа и изучения. Для сохранения (или печати) результатов пользователь должен выполнить click правой кнопкой мыши в области графика Айв появившемся контекстном меню выбрать действие, которое он хочет выполнить. В заключении отметим, что "OPTIMUM" является одним из программных средств технологии ROOT (Red Organization of Optimization Technology) [8]. ознакомиться с которой можно в приложении. Практические ежедневно руководителям различных предприятии, лабораторий, менеджерам и т.п. приходится принимать решения в условиях неопределенности. Последняя может заключаться в оценке вероятности появления события, нахождении его шансов, определении степени профессионализма экспертов и т.п- В этой главе рассматривается такой тип неопределенности, как принятие решений в условиях много-критериальности оценки процесса (системы). Часто считают, что от многокритериальности можно всегда избавиться, построив более глобальную математическую модель процесса. Однако, во-первых, далеко не всегда можно построить и реализовать глобальную модель, а, во-вторых, как показано в [62] , какая бы модель ни была создана в ней всегда останется неопределенность и необходимость получения компромиссного решения. Таким образом, многокритериальное в задачах принятия решения носит принципиальный характер и необходимы эвристические процедуры, облегчающие лицу, принимающему решение (ЯПР), находить компромиссные решения. В этой главе предлагается один из таких подходов, проводится его статистическое исследование и описывается разработанный программный комплекс РАКЕТО, реализующий этот подход в диалоговом режиме с Л ПР.
