Содержание к диссертации
Введение
1. Синтез сложных технических систем 9
1.1. Проектирование сложных технических систем 9
1.2. Внешнее и внутреннее проектирование 13
1.3. Аспекты, уровни и этапы проектирования 14
1.4. Функциональное проектирование систем 15
1.5. Автоматизация проектирования сложных технических систем 16
1.6. Задачи анализа и синтеза в процессе проектирования 18
1.7. Структурно-параметрический синтез 21
1.8. Выводы 22
2. Оптимальный многокритериальный выбор в задачах автоматизированного проектирования сложных систем 24
2.1. Задачи принятия решений 24
2.2. Принятие решения – как задача оптимизации 27
2.3. Задача многокритериального выбора 29
2.4. Задача оптимального выбора объектов 31
2.5. Оптимальный выбор в задаче синтеза сложных систем 33
2.6. Выбор совокупности разнородных объектов из общего множества 35
2.7. Выбор совокупности объектов, частично соответствующих поставленным условиям 37
2.8. Многокритериальная оптимизация 39
2.9. Использование однокритериальной оптимизации
2.10. Свертка критериев 41
2.11. Определение относительной важности критериев 42
2.12. Снижение размерности задач многокритериального выбора 43
2.13. Интеллектуальный анализ данных как способ сокращения размерности задачи многокритериального выбора 47
2.14. Многокритериальная классификация 48
2.15. Кластерный анализ 50
2.16. Выводы 52
3. Алгоритм оптимального выбора в проектных процедурах 53
3.1. Задача выбора подмножества объектов по заданным критериям 53
3.2. Выбор подмножества элементов, полностью соответствующих критериям 55
3.3. Выбор подмножества элементов, частично соответствующих критериям 57
3.4. Метрики в задаче структурной оптимизации 58
3.5. Использование транспортной задачи на этапе структурной оптимизации 60
3.6. Использование критериев выбора в виде ограничений и интервалов 62
3.7. Выбор объектов, исходя из минимизации воздействий 64
3.8. Сокращение размерности задачи выбора при выполнении проектных процедур 65
3.9. Алгоритм многокритериального оптимального выбора 67
3.10. Выводы 71
4. Вычислительные эксперименты, оценка точности и эффективности алгоритма многокритериального выбора 72
4.1. Программная реализация алгоритма многокритериальной структурной оптимизации 72
4.2. Тестовая задача 1. Поиск подмножества объектов, полностью соответствующего поставленным требованиям
4.1. Тестовая задача 2. Поиск подмножества объектов, максимально близко соответствующего поставленным требованиям 79
4.2. Применение алгоритма для выбора группы микроконтроллеров 95
Заключение 101
Публикации автора по теме диссертации. 102
Список литературы 104
- Функциональное проектирование систем
- Задача оптимального выбора объектов
- Выбор подмножества элементов, полностью соответствующих критериям
- Тестовая задача 1. Поиск подмножества объектов, полностью соответствующего поставленным требованиям
Функциональное проектирование систем
Проектирование сложной технической системы – задача, разбиваемая на подзадачи, соответствующие разным уровням проектирования. Проектирование таких систем основано на блочном и иерархическом подходе, суть которого состоит в разбиении представления объекта проектирования на несколько частей. Таким образом, происходит замена малого количества задач высокой сложности на большее количество задач допустимой сложности.
Уровни иерархии проектирования различаются степенью детализации представления о системе, каждому уровню соответствует свое определение элементов. Рассматриваемый на некотором уровне элемент системы описывается как система элементов на следующем уровне.
Процесс проектирования разделяется, как правило, на этапы. При этом используются следующие понятия.
Проектное решение – описание объекта или его составной части, достаточное для рассмотрения и принятия заключения об окончании проектирования или путях его продолжения.
Проектная процедура – часть этапа проектирования, заканчивающаяся получением проектного решения. Примерами проектных процедур служат синтез функциональной схемы устройства, оптимизация параметров функционального узла, трассировка межсоединений на печатной плате и т. п.
Проектирование технических систем начинается с выработки технического задания на проектирование, в котором содержатся основные сведения об объекте проектирования, условиях его эксплуатации, требованиях, предъявляемых к проектируемой системе.
Предварительное проектирование заключается в поиске принципиальных возможностей построения системы, исследованием новых принципов, структур, обоснованием общих решений. В ходе эскизного проектирования производится детальная проработка возможности построения системы. На этапе технического проектирования выполняется укрупненное представление конструкторских и технологических решений.
Рабочее проектирование предполагает детальную проработку всех блоков, узлов и деталей системы и соответствующих технологических процессов.
Изготовление и испытание опытного образца завершает процесс проектирования. Внешнее и внутреннее проектирование В общем случае процесс проектирования системы разделяется на внешнее и внутреннее. На этапе внешнего проектирования решаются задачи определения структуры и функций системы в целом, формулируются ее цели и основные характеристики, исследуются принципы внешнего воздействия на систему.
Внешнее проектирование предполагает последовательное формирование следующих положений: задачи, решаемые системой; факторы, действующие на систему и учитываемые при разработке; критерии эффективности системы.
Таким образом, каждый вариант построения системы должен оцениваться в соответствии с заданными критериями эффективности. Для этого строятся соответствующие математические модели. Если построение единой модели невозможно, то проводится декомпозиция системы и построение моделей функционирования подсистем.
После определения наилучшего варианта построения системы переходят к его внутреннему проектированию.
Внутреннее проектирование включает в себя различные технические решения по структуре и параметрам подсистем, узлов и блоков системы на основе результатов внешнего проектирования.
К основным техническим параметрам ИУС, как правило, относят: разрядность и форма представления информации; состав команд, их разрядность и формат; время выполнения отдельных команд; информационный объем запоминающих устройств; число уровней прерывания, система прерываний; организация интерфейсов; скорость передачи информации и протоколы обмена данными по внешним интерфейсам; параметры первичных источников питания.
Аспекты, уровни и этапы проектирования
В ходе проектирования система может рассматриваться на различных уровнях детализации и подробности. В один уровень включают представления, имеющие общую физическую основу и разрабатываемые с помощью единого математического аппарата. Представления о сложных технических системах в процессе их проектирования разделяются на аспекты и иерархические уровни [6]. Такими аспектами чаще всего являются: функциональный аспект, отражающий физические и информационные процессы, протекающие в системе при его функционировании; конструкторский аспект, характеризующий структуру, расположение в пространстве и форму составных частей; технологический аспект, определяющий возможности и методы изготовления системы в заданных условиях. В аспектах проектирования также выделяют отдельные уровни. В функциональном аспекте проектирования обычно используют следующие уровни: структурный или системный уровень; функционально-логический уровень; схемотехнический уровень;9
Задача оптимального выбора объектов
Описанная задача оптимального выбора совокупности объектов рассматривается не только в структурно-параметрическом синтезе сложных технических систем. Подобные задачи встречаются и в других сферах науки, техники и экономики [19, 20, 21, 22, 23]. Они могут формулироваться следующим образом: выбор подходящей техники или оборудования, подбор персонала, выбор оптимального состава многокомпонентных смесей или сплавов, определение победителей в конкурсе со сложной системой оценки, выбор проектов для дальнейшей реализации, выбор компаний на основе экономических показателей для инвестирования, кредитования, сотрудничества, размещения заказов и т.п. выбор группы месторождений полезных ископаемых для добычи, построение подмножества оптимальных по ряду критериев диагностических тестов.
Несмотря на то, что перечисленные задачи относятся к различным достаточно далеким друг от друга областям человеческой деятельности, можно сказать, что речь идет о создании набора элементов, который в целом приобретает свойства, нехарактерные для отдельных элементов или их другой комбинации. То есть можно говорить, что из доступных элементов синтезируется новая система в соответствии с некими сформулированными принципами оценки ее эффективности.
Практический синтез сложной системы не всегда может быть проведен путем перебора всех возможных комбинаций большого множества элементов. Подбор элементов основывается на некоторых теоретических построениях, опыте создания подобных систем.
Таким образом, процесс синтеза предполагает нахождение ответов на следующие вопросы: возможен ли синтез системы из допустимых элементов с заданными свойствами; какой вариант построения системы из допустимых элементов будет наиболее близким к варианту, предложенному в результате теоретических построений.
На определенном уровне упрощения задача оптимального выбора варианта построения системы сводится к следующим начальным условиям: задано исходное множество однородных объектов, характеризуемых рядом числовых свойств; задано описание требуемого множества объектов, которое должно быть выбрано из исходного множества, а если точнее, то критерии, задающие значения свойств отбираемых объектов. Искомый результат решения задачи выбора в такой формулировке -подмножество выбранных объектов, соответствующих поставленным условиям или критериям. Задача достаточно актуальна и рассматривается во многих современных научных работах с разных позиций.
Примером рассмотрения задачи в такой постановке является работа [24]. В ней рассматривается проблема выбора объектов в процессе технической подготовки производства.
Автор использует методы поиска наименьшего покрытия множества для выбора группы объектов, решающих все задачи при их минимальном суммарном весе. Автор также решает задачу нахождения оптимальных наборов изделий, предназначенных для запуска в производство.
Большой интерес представляют собой результаты, полученные на кафедре «Математика и моделирование» Петербургского государственного университета путей сообщения. В рамках научного направления «Системный анализ и управление» образована научная школа «Многокритериальный выбор на конечном множестве альтернатив» [25]. В числе многих других рассматриваются следующие задачи многокритериального выбора:
Выше рассматривалась задачи выбора объектов, полностью соответствующих поставленным критериям. При такой постановке отсутствие в исходном множестве подмножества объектов, обладающих искомыми свойствами, означает отсутствие решения задачи.
Прикладные задачи многокритериального выбора могут быть менее строгими.
При решении практических задач такого рода может быть допустимо использование подмножества объектов, лишь частично соответствующего поставленным условиям. Невозможность получения заданного подмножества может быть обусловлено исходным низким уровнем характеристик рассматриваемых элементов или, наоборот, завышенными к ним требованиями.
Более того, критерии выбора могут описывать идеальный вариант, сформированный на основе предварительных теоретических построений, невозможный или маловероятный в реальных условиях.
В такой постановке задача выбора подмножества должна решаться следующим образом: 1. Проведение поиска подмножества, полностью соответствующего поставленным требованиям.
2. Если первое не достигнуто и допустимо использование подмножества, не полностью соответствующего поставленным требованиям, то проведение поиска подмножества, максимально близкого к поставленным требованиям.
Итак, в этом случае, необходимо определить способы выбора совокупности объектов, которая будет максимально близка к поставленным требованиям. После выбора подмножества, максимально полно отвечающего поставленным требованиям, возможно: констатировать неразрешимость задачи при заданных условиях; провести ослабление требований с целью приведения их в соответствие с имеющимися объектами и оценить возможность использования найденного решения; оценить возможность улучшения параметров выбранных объектов до минимально допустимого уровня некоторыми воздействиями. Ключевой момент в выборе оптимального подмножества, частично соответствующего требованиям, - способ определения степени такого соответствия рассматриваемого объекта.
Одним из подходов к поиску оптимального подмножества объектов является прямое сведение этой задачи к задаче оптимизации. Для этого необходимо задать способ оценки качества рассматриваемого подмножества, основанный на оценках соответствия каждого его элемента той роли, для которой он в данном случае предназначается. Поиск решения заключается в определении подмножества с максимальным значением качества.
Выбор подмножества элементов, полностью соответствующих критериям
Процедуру выбора объектов, параметры которых полностью соответствуют заданным критериям, можно рассматривать как задачу линейного назначения.
Задача в такой постановке отображается с помощью двумерной матрицы сопоставления объектов и критериев Z(1) = %, формируемой на основе информации, хранимой в трехмерной матрице Z.
Если решается задача выбора из множества без ограничений на количество выбранных объектов, то верно обратное: если для любого к существует Q = 1, то задача решена: Укза.к=1 i =ic7j (3.8) Если же возможность выбора объекта ограничена, то задача в таком виде может быть сведена к задаче поиска максимального паросочетания в двудольном графе G = (F = (хг., {уА }),{%}) и решена с помощью алгоритма пополняющего пути или алгоритма Холпкрофта - Карпа [28]. Двудольный граф задается двумя непересекающимися множествами вершин и их отображением друг на друга, представляемым в виде ребер, соединяющих вершины из разных множеств.
Двудольный граф позволяет представить множество объектов X как вершины первой доли, множество Y как вершины второй доли. В качестве их отображения может использоваться матрица смежности двудольного графа (1) . Если количество ребер A в максимальном паросочетании равно K, то задача решена, иначе – решения не существует. Найденное таким образом максимальное паросочетание является решением задачи выбора подмножества объектов, полностью соответствующих критериям.
Задача линейного назначения не является вычислительно сложной и может быть достаточно просто алгоритмизирована. Для использования в проектных процедурах необходимо решить вопрос классификации получаемых решений. Классические алгоритмы позволяют получить одно из множества точных решений задачи, что приводит к неопределенности в случае высокой мощности множества объектов. В качестве возможного подхода к решению этой проблемы предлагается использовать интеллектуальный анализ данных для снижения уменьшения числа объектов. 3.3. Выбор подмножества элементов, частично соответствующих критериям
Как было отмечено выше, задача выбора варианта построения системы на основе предварительных исследований может заключаться в простом подборе элементов, соответствующих поставленным условиям.
Так как это не всегда достижимо, не менее актуальной является задача формирования подмножества элементов, обеспечивающих максимальное значение целевой функции, описывающей систему:
Чтобы избежать использования алгоритмов перебора или возврата к формированию нового набора требований, имеет смысл найти и оценить вариант построения системы (подсистемы), составленный из элементов допустимых, несоответствующих поставленным условиям, но максимально близких к ним.
Решение задачи в такой постановке - выбор оптимального подмножества объектов частично соответствующих критериям - в значительной степени определяется способом вычисления соответствия объекта той или иной роли, для которых он может быть использован.
При такой постановке задачи необходимо ввести понятие расстояния, определяющего степень различия рассматриваемого объекта от заданного требования или набора требований.
Метод вычисления расстояния или метрика, играет важнейшую роль в решении описываемой задачи, так как от правильности алгоритма его определения зависит правильность выбора подмножества объектов.
Способ определения метрики зависит от практического содержания задачи: прежде всего от «стоимости» ресурсов, затрачиваемых на компенсацию несоответствия характеристик объекта требованиям, предъявляемым к нему как к элементу системы, при условии, что такая компенсация возможна. Рассмотрим проблему (3.9) как задачу многокритериальной оптимизации: где f - степень несоответствия рассматриваемого объекта требованиям к нему предъявляемым, в идеальном случае равная 0. В данном случае наиболее универсальным методом оптимизации является свертка критериальных функций, подробно рассмотренная во второй части работы. Использование этого метода достаточно просто математически и, кроме того, делает возможным как выделение более важных критериев, так и их равноправное рассмотрение.
Метрики в задаче структурной оптимизации
Задача выбора подмножества элементов, свойства которых минимально отклоняются от требуемых значений, рассматриваемая как задача многокритериальной оптимизации, может быть сформулирована следующим образом: {ДД-яшп Шє\,..,К (3.11) где Dik - «расстояние» между существующим объектом и требуемым набором свойств, то есть значение, характеризующее степень несоответствия данного объекта данному критерию.
Используем метод свертки критериев и сведем задачу к следующему виду: где F - целевая функция, определяющая оптимальность выбранного решения. Как было сказано выше, способы вычисления расстояний могут быть разные. Применим наиболее простой и универсальный способ - расстояние, определяемое как сумма взвешенных
Коэффициенты важности придают формуле (3.13) достаточную гибкость, обеспечивающую выделение наиболее существенных для данной задачи характеристик. При необходимости задание заведомо большого значения какого-то из коэффициентов позволит исключить из рассмотрения варианты с характеристиками, которые не могут быть компенсированы.
Эвклидово расстояние и расстояние по Хеммингу, как правило, дают сходные результаты. Возможно использование подхода, который позволяет обойтись без суммирования расхождений свойств, а использовать максимальное отклонение параметра от критерия. Для этого можно применить расчет расстояния, основанного на расстоянии Чебышева: В этом варианте степень соответствия объекта определяется не всеми свойствами, а одним - максимально «плохим» параметром. 3.5. Использование транспортной задачи на этапе структурной оптимизации В том случае, что если допустим множественный выбор объекта, то для получения решения необходимо выбрать минимальные элементы в каждом столбце матрицы g2) = )J.
Если множественный выбор не допустим, то в такой постановке задачу можно рассматривать как транспортную и искать решение с помощью известных алгоритмов.
Транспортная задача формулируется как поиск оптимального плана перевозок грузов из пунктов отправления в пункты получения с минимальными затратами. Затраты на перевозку груза характеризуются транспортной таблицей [29].
В нашем случае пунктами отправления и пунктами получения будут соответственно множества {xi} и {yk}.
Таким образом, транспортная таблица представляет собой матрицу Z 2) = Z)J, содержащую «расстояния» между элементами %. и требуемыми значениями свойств у , характеризующие уровень соответствия первого второму и определяемые по формулам (3.13), (3.14) или (3.15). Исходя из этого, требуется найти {VJ - объемы перевозок между пунктами отправления и получения грузов при выполнении следующих условий:
Тестовая задача 1. Поиск подмножества объектов, полностью соответствующего поставленным требованиям
Задача в данной формулировке является несбалансированной, так как 1 К. Для того чтобы превратить задачу в сбалансированную и получить возможность применения алгоритмов, построенных на использовании транспортной таблицы, необходимо ввести фиктивный пункт получения груза с запасом равным I-K и нулевыми затратами на перевозку груза к нему.
Существует несколько подходов к решению транспортной задачи. Применим метод, основанный на использовании теории графов. В данном подходе рассматривается двудольный граф, в котором элементы х. находятся в левой доле, а требования у - в правой. Элементы и критерии попарно соединяются рёбрами с ценой за единицу потока ) и с бесконечной пропускной способностью. К левой доле графа (рис. 3.2) присоединяется исток, к правой - сток. Пропускная способность рёбер из истока к каждому элементу х. равна количеству таких элементов, а рёбер из каждого критерия у к стоку количеству требуемых состояний. Цена за единицу потока у этих рёбер равна 0. Рис. 3.2. Поиск максимального потока минимальной стоимости в качестве способа оптимального выбора объектов
Сформированный подобным образом граф позволяет решать задачу нахождения максимального потока минимальной стоимости. Её решение аналогично нахождению максимального потока в алгоритме Форда-Фалкерсона. Только вместо кратчайшего дополняющего потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширину, а алгоритм Беллмана-Форда. При возврате потока стоимость считается отрицательной [30].
Вычислительная сложность используемых алгоритмов определяется как O(I3) или выше. Использование критериев выбора в виде ограничений и интервалов Выше мы рассмотрели наиболее простой вариант - в качестве критериев выбора, предъявляемых к свойствам объектов (потенциальных элементов системы), были заданы точные значения их характеристик.
На практике такие требования могут формулироваться не только как строгие значения, но и как ограничения, то есть они могут быть заданы как: нижняя (верхняя) граница значений параметра; интервал его допустимых значений.
В первом варианте постановки условий предполагаем, что превышение значения параметра элемента над требуемым значением с точки зрения оптимальности выбора эквивалентно их равенству.
Во втором - считаем эквивалентными между собой любые значения свойств в заданном интервале.
В этом случае, вместо (3.5) требуется выделить подмножество объектов Х Х с набором свойств, отвечающих заданным условиям (в первом случае одному, во втором - двум): Х=Ш \J ckjfp ckj2 (3.24) В описанную выше методику требуется внести ряд изменений, учитывающих возможность задания критериев в виде ограничений и интервалов. В таком случае, например, в качестве элемента матрицы смежности двудольного графа Z(1)=WI, которая используется для поиска максимального паросочетания, нужно использовать: I0 3J zvk=0 (Pk ckj1pk ckj ) Аналогично, при определении «расстояний» между объектом и критерием можно использовать (вместо (3.13)):
После этих (или аналогичных) изменений описанные выше методы на основе поиска максимального паросочетания и решения транспортной задачи также применимы. 3.7. Выбор объектов, исходя из минимизации воздействий
Выше мы рассмотрели варианты задач, в которых оптимальность выбора элементов определялась степенью соответствия выбираемых объектов поставленным условиям.
Этим определяется однозначность оценки качества варианта построения системы: расстояние, определяющее степень близости объекта и критерия не зависит от выбора других объектов, включаемых в подмножество.
Практическое применение подмножества, выбранного таким образом, часто предполагают дальнейшее изменение свойств объектов, которые в него входят. То есть, ведется поиск объектов, приведение свойств которых к заданному уровню потребует минимальных затрат ресурсов - времени, финансов, дополнительного оборудования и т.п.
Если затраты ресурсов на изменение свойств объекта не зависят от состояния других объектов и линейно зависят от «расстояния» между объектом и критерием, то решение задачи поиска оптимального подмножества объектов аналогично описанному решению задачи поиска совокупности объектов, минимально отличающихся от критериев.
Заменив весовые коэффициенты важности свойств на «цену» изменения параметра объекта, получим подмножество объектов, оптимальное с точки зрения минимизации воздействий, приводящих объекты к заданному состоянию. Прикладная задача может оказаться сложнее: размер ресурсов затраченных на изменение свойства объектов может быть величиной непостоянной. Он может зависеть от количества объектов (например, чем больше объектов подвергается изменяющему воздействию, тем дешевле «цена» воздействия), от количества свойств, подвергаемых изменению - чем больше свойств объектов изменяется, тем дороже воздействие.
В подобных случаях использование расстояний, рассчитываемых по (3.12), (3.13) или (3.14), может быть не адекватно задаче. В этом случае расчёт целевой функции усложняется. Учет количества изменяемых свойств можно обеспечить, добавив к коэффициенту важности счетчик изменяемых свойств. Например,
Время решения задачи выбора подмножества из множества объектов с использованием описанных выше методов, зависит от мощности этого множества. Так, например, вычислительная сложность алгоритма решения транспортной задачи, использованного в работе для определения оптимального подмножества, пропорциональна кубу количества рассматриваемых объектов.
Построение современной сложной информационно-управляющей системы может допускать рассмотрение в качестве потенциальных элементов тысячи объектов.
В этом случае практическое использование средств автоматизации невозможно без снижения размерности задачи выбора. Существует достаточно много способов предварительного анализа данных, с помощью которых можно отбросить часть рассматриваемых объектов или их свойств. Они были рассмотрены в главе 2.
Универсального метода сокращения размерности задачи выбора при сохранении точности решения задачи не существует: вывод из сферы рассмотрения части объектов или свойств может привести к негарантированности получения точного решения.
Если ведется поиск подмножества, частично соответствующего критериям и предполагающего изменение свойств выбранных объектов, то, возможно, что снижение точности при определении оптимального подмножества является менее важным, чем сокращение времени решения, которое обеспечивается за счет понижения размерности задачи выбора.
Сократить размерность задачи можно не только путем исключения объектов из рассмотрения. В случае структурно-параметрического синтеза, предлагается объединение объектов в группы по принципу схожести их свойств.
