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

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

* г

тинчжо

ИНТЕЛЛЕКТУАЛЬНАЯ ПОДДЕРЖКА ПРОЦЕДУР СИНТЕЗА ИНФОРМАЦИОННО-УПРАВЛЯЮЩИХ СИСТЕМ

Специальность 05.13.01. Системный анализ, управление и обработка информации (в приборостроении)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 О НОЯ 2014

Москва 2014 Я 5 544

005555544

Работа выполнена на кафедре «Вычислительная техника» в Национальном исследовательском университете «МИЭТ».

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

профессор кафедры «Радиоэлектроника» Тульского государственного университета

Аладышев Олег Сергеевич, кандидат технических наук, заведующий отделом МСЦ РАН

Ведущее предприятие - ОАО «НТЦ ЭЛИНС», г. Москва.

Защита состоится "П." декабря 2014 года в 14:30 на заседании диссертационного совета Д212.134.02 в Национальном исследовательском университете «МИЭТ».

124498, Москва, Зеленоград, проезд 4806, МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ и на сайте www.miee.ru.

Автореферат разослан " ^ " ЙйасГр £_2014 года.

_»._ ионного совета

Киселев Денис Викторович.

Официальные оппоненты

Минаков Евгений Иванович, доктор технических наук,

д.т.н., доцент Гуреев А.В.

Общая характеристика работьк

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

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

Современная информационно-управляющая система (ИУС) - это комплекс аппаратных и программных средств, обеспечивающий непрерывную надежную работу различных объектов в реальном масштабе времени.

Как правило, функционирование ИУС при работе с реальными объектами в составе производственных систем связано с решением целого комплекса задач, включая и необходимость обмена информацией с большим числом внешних устройств. Выполняемые задачи характеризуются большой продолжительностью непрерывной работы при поддержании высокой устойчивости к отказам.

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

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

Автоматизированное проведение процедур синтеза ИУС является вычислительно сложной и трудно формализуемой задачей, особенно на начальных этапах.

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

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

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

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

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

Цель работы и задачи исследования. Диссертационная работа посвящена решению задач оптимального многокритериального выбора на основных этапах процесса синтеза сложных систем, а также исследованию методов снижения их вычислительной сложности при высокой размерности. Это соответствует областям исследований, определенных в паспорте специальности 05.13.01 «Системный анализ, управление и обработка информации» (п.4 и п.7).

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

2. Разработка алгоритма оптимального многокритериального выбора варианта построения системы (подсистемы) на основе предварительно сформулированных требований с возможностью снижения размерности задачи с помощью методов интеллектуального анализа данных.

3. Программная реализация разработанного алгоритма.

4. Проведение вычислительных экспериментов, оценка точности и эффективности разработанного алгоритма.

Объект и предмет исследования. Объектом исследования является процесс проектирования сложных информационно-управляющих систем.

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

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

Научная новизна. В диссертации предложен алгоритм оптимального многокритериального выбора варианта построения системы (подсистемы) на основе предварительно сформулированных требований, исследованы методы интеллектуального анализа данных и их применимость для снижения размерности задач оптимального выбора элементов системы.

Положения, выносимые на защиту:

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

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

3. Программная реализация алгоритма.

4. Результаты экспериментальных исследований эффективности алгоритма.

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

Внедрение результатов. Результаты диссертационной работы используются на кафедре вычислительной техники МИЭТ при изучении дисциплины «Интеллектуальные системы».

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

1. Микроэлектроника и информатика - 2010. 17-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ

2. Микроэлектроника и информатика - 2011. 18-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ

3. Актуальные вопросы современной техники и технологии. IV Международная научная заочная конференция. Липецк, 2011.

4. Актуальные проблемы науки. Международная научно-практическая конференция, Тамбов, 2011.

5. Актуальные проблемы информатизации в науке, образовании и экономике. 4-я Всероссийская межвузовская научно-практическая конференция. МИЭТ, 2011.

6. Современные вопросы науки и образования - XXI век, Международная заочная научно-практическая конференция, Тамбов, 2012.

7. Микроэлектроника и информатика - 2013. 20-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. МИЭТ.

8. Актуальные проблемы информатизации в науке, образовании и экономике, б-я Всероссийская межвузовская научно-практическая конференция. МИЭТ, 2013.

9. Микроэлектроника и информатика 21-я Всероссийская межвузовская научно-техническая канференцая студентов и аспирантов. МИЭТ Публикации. По материалам диссертации опубликовано восемь тезисов докладов и шесть статей, в том числе четыре в журналах, входящих в перечень ВАК.

Структура и объём диссертационной работы. Рукопись диссертационной работы, общим объемом 107 страниц, состоит из введения, четырех глав, заключения, списка литературы из 30 источников и приложения.

Содержание работы

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

В первой главе рассматриваются различные аспекты проектирования сложных технических систем на примере информационно-управляющих систем. Очевидно, что информационно-управляющие системы (ИУС) относятся к категории сложных - систем, состоящих из множества взаимодействующих подсистем.

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

Разработка ИУС, как сложного технического объекта, предполагает использование системного подхода: проектируемая система должна рассматриваться как единое целое, состоящее из взаимодействующих частей и обеспечивающее достижение поставленных целей.

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

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

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

Проектирование сложной технической системы - это итерационный процесс: в ходе проектирования задачи анализа и синтеза выполняются многократно.

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

определяют оптимальные параметры элементов системы.

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

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

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

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

Построение моделей и разработка алгоритмов для структурно-параметрического синтеза является сложной и актуальной проблемой.

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

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

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

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

/(х) ~> тах, хеХДсй7 ^ 1)

где:

Ш - пространство решений,

X - множество допустимых решений (подмножество пространства решений, в котором происходит поиск оптимальных решений),

]\х) - критерий оптимизации.

Решением задачи является х е X . если

V. Дх*) >/(*)•

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

»возможности выражения функции в аналитическом виде;

• количества переменных, от которых она зависит;

• ее унимодальности;

•ее дифференцируемое™.

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

Таким образом, каждый рассматриваемый критерий не является единственным полностью отражающим достигаемую цель. Полностью характеризует задачу совокупность критериальных функций (/1>/2'•">//??) ' заданных пА пространстве решений X .

Постановка задачи многокритериального выбора включает:

• множество возможных решений X ;

• векторный критерий / = [// 2>-> / т)

• отношение предпочтения , заданное на множестве возможных решений.

Задача, заключающаяся в выделении одного или несколько лучших вариантов (альтернатив) из множества возможных, является типовой в теории принятия реп!ения. Часто в качестве множества альтернатив выступает некоторый набор объектов, задаваемых определенными характеристиками, в котором требуется выбрать лучший

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

• определение способа интегральной оценки объекта рассматриваемого типа, являющейся функцией его свойств;

• вычисление значений интегральной оценки для всех рассматриваемых объектов;

• выбор лучшего объекта, то есть объекта с экстремальным (максимальным или минимальным) значением интегральной оценки.

Наряду с задачами выбора лучшего объекта на практике часто встречаются родственные задачи, в которых результатом анализа множества объектов должен стать не единственный самый лучший объект, а отбор группы лучших объектов (подмножества множества рассматриваемых объектов).

Задача выбора лучшего объекта из некоторой совокупности потенциальных элементов системы является неотъемлемой частью этапов параметрического и структурно-параметрического синтеза сложной технической системы.

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

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

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

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

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

Оба эти примера предполагают рассмотрение элементов системы в разных задачах оптимального выбора - во всех, в которых они могут быть применимы - с разными принципами оценки оптимальности этого выбора. Кроме этого, надо учитывать, что выбор такого объекта в одной задаче, может исключать его выбор в других.

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

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

Таким образом, процесс синтеза предполагает нахождение ответов на следующие вопросы:

• возможен ли синтез системы из допустимых элементов с заданными свойствами;

• какой вариант построения системы из допустимых элементов будет наиболее близким к варианту, предложенному в результате теоретических построений.

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

задано исходное множество однородных объектов, характеризуемых рядом числовых свойств;

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

Искомый результат решения задачи выбора в такой формулировке -подмножество выбранных объектов, соответствующих поставленным условиям или критериям.

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

При решении практических задач такого рода может быть допустимо использование подмножества объектов, лишь частично соответствующего поставленным условиям. Невозможность получения заданного подмножества может быть обусловлено исходным низким уровнем характеристик рассматриваемых элементов или, наоборот, завышенными к ним требованиями.

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

В такой постановке задача выбора подмножества должна решаться следующим образом:

1. Проведение поиска подмножества, полностью соответствующего поставленным требованиям.

2. Если первое не достигнуто и допустимо использование подмножества, не полностью соответствующего поставленным требованиям, то проведение поиска подмножества, максимально близкого к поставленным требованиям.

Итак, в этом случае, необходимо определить способы выбора совокупности объектов, которая будет максимально близка к поставленным требованиям.

После выбора подмножества, максимально полно отвечающего поставленным требованиям, возможно:

» констатировать неразрешимость задачи при заданных условиях; • провести ослабление требований с целью приведения их в соответствие с имеющимися объектами и оценить возможность использования найденного решения; ® оценить возможность улучшения параметров выбранных объектов до минимально допустимого уровня некоторыми воздействиями.

Ключевой момент в выборе оптимального подмножества, частично соответствующего требованиям, - способ определения степени такого соответствия рассматриваемого объекта.

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

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

{/!(*)./2<»>•••,/¿М) -> пип, х =(х1,х2>—хп) (2-2)

gj(x )<Ь]

При этом качество некоторого решения рассматривается в виде вектора 2>-->/0 > компонентами которого служат оценки варианта решения

по частным критериям.

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

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

Для этого применяют:

• Выбор и рассмотрение единственного основного частного критерия.

• Последовательное раздельное рассмотрение частных критериев.

• Преобразование частных критериев в один комплексный критерий.

Один из вариантов реализации векторной оптимизации - выделение

основного (самого важного) критерия оптимальности, рассмотрение остальных в виде ограничений и проведение однокритериальной оптимизации. Примером такого метода является метод е-ограничений.

Серьезным недостатком такого подхода является возможная неадекватность первоначально поставленной многокритериальной задачи и соответствующей однокритёриальной задачи с дополнительными ограничениями, что делает его малоприменимым на практике.

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

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

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

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

Очевидно, что уменьшение одного или другого снижает вычислительную сложность задачи и время ее решения.

Можно считать, что сложность решения задач многокритериального выбора зависит от:

• размерности пространства, образуемого характеристиками объектов;

• мощности множества объектов, составляющих анализируемую совокупность.

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

• отбора для анализа группы свойств, являющихся наиболее информативными;

• агрегирования однотипных признаков;

' предварительного исключения из рассмотрения объектов, однозначно не являющихся искомыми.

Существует большое количество методов, основанных на математической статистике, которые могут использоваться для анализа параметров и выделения наиболее важных из них. Опираясь на такой анализ, можно сократить размерность пространства свойств анализируемых объектов,

К задаче выбора элементов системы из большого множества объектов,

можно подойти и с другой стороны - уменьшать не количество рассматриваемых свойств, а количество объектов. Например, объединив сходные объекты в группы.

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

Для рассмотрения задачи в такой постановке может быть использован ряд методов интеллектуального анализа данных.

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

Для объединения объектов в группы можно применить к их множеству методы классификации или кластеризации объектов.

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

Задача синтеза системы рассматривается в следующей формулировке.

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

Искомый результат может формулироваться следующим образом:

• как выбор объектов, полностью соответствующих поставленным требованиям,

• как выбор объектов максимально близких к поставленным требованиям.

Возможны два варианта задачи:

• допустим множественный выбор объекта - каждый объект может быть поставлен в соответствие разным наборам требований и выбран многократно;

• множественный выбор не допустим - отнесение объекта к одной из групп исключает возможность его выбора по другому набору требований.

Обозначим рассматриваемую совокупность объектов как множество:

X ={*/}, 1 = 1../, (3.1)

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

(3.2)

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

у ={ук}, к = \,..К, К<1, (3.3)

Ук = {с}д} (3-4)

*

Таким образом, требуется выделить подмножество объектов X с X с набором свойств, равных заданным:

Х* = {хк} | Р)д = с]у (3.5)

Условия задачи полностью описываются матрицами «существующих

и «требуемых параметров» У = с ]д • Соответствие свойств объектов и критериев полностью характеризуется

Щ

параметров» X —

Ру

трехмерной матрицей сравнений «объекты-критерии-свойства» 2 -

где результат сопоставления свойства объекта и его требуемого значения у соответствующего критерия:

1, Р

и

(3.6)

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

Задача в такой постановке легко отображается с помощью двумерной

матрицы сопоставления объектов и критериев г® ~ ЫгкЬ Формируемой

на основе информации, хранимой в трехмерной матрице 2, .

Элементы матрицы определяются следующим образом:

!» У 2ук = ЧРу=С}д)

При этом необходимо учесть, если существует > для которого все

аЦ{ = 0 , то задача решения не имеет.

Если решается задача выбора из множества без ограничений на

а ¡к

(3.7)

количество выбранных объектов, то верно обратное: если для любого £

существует аЦс = 1, то задача решена:

Если же возможность выбора объекта ограничена, то задача в таком виде может быть сведена к задаче поиска максимального паросочетания в

двудольном графе £ = (р" = ({х/}> (у^]) {а//с}] н Решена с помощью алгоритма пополняющего пути или алгоритма Холпкрофта - Карпа.

Если количество ребер А в максимальном паросочетании равно К, то задача решена, иначе - решения не существует.

Найденное таким образом максимальное паросочетание является решением задачи выбора подмножества объектов, полностью соответствующих критериям.

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

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

*

X ={хк)

*

^ (X ) -» шах (3.9)

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

Решение задач]! в такой постановке — выбор оптимального подмножества объектов частично соответствующих критериям - в значительной степени определяется способом вычисления соответствия объекта той или иной роли, для которых он может быть использован.

При такой постановке задачи необходимо ввести понятие расстояния, определяющего степень различия рассматриваемого объекта от заданного требования или набора требований.

Метод вычисления расстояния или метрика, играет важнейшую роль в решении описываемой задаче, так как от правильности алгоритма его определения зависит правильность выбора подмножества объектов.

Способ определения метрики зависит от практического содержания задачи: прежде всего от «стоимости» ресурсов, затрачиваемых на компенсацию несоответствия характеристик объекта требованиям, предъявляемым к нему как к элементу системы, при условии, что такая компенсация возможна.

Рассмотрим проблему (3.9) как задачу многокритериальной оптимизации:

{/¿}4тт, (ЗЛО)

где f ^ - степень несоответствия рассматриваемого объекта требованиям к

нему предъявляемым, в идеальном случае равная 0.

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

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

[Dik) -> min Vk е l,..,K (3 п)

где Dik ' «расстояние» между существующим объектом и требуемым

набором свойств, то есть значение, характеризующее степень несоответствия данного объекта данному критерию. Вопрос определения «расстояния» подробно рассмотрен в диссертации.

В том случае, что если допустим множественный выбор объекта, то для получения решения необходимо выбрать минимальные элементы в каждом

столбце матрицы

(3.12)

Если множественный выбор не допустим, то в такой постановке задачу можно рассматривать как транспортную и искать решение с помощью известных алгоритмов.

Транспортная таблица представляет собой матрицу ~

содержащую «расстояния» между элементами х{ и требуемыми значениями свойств у ^ , характеризующие уровень соответствия первого второму

Выше мы рассмотрели наиболее простой вариант - в качестве критериев выбора, предъявляемых к свойствам объектов (потенциальных элементов системы), были заданы точные значения их характеристик.

На практике такие требования могут формулироваться не только как строгие значения, но и как ограничения, то есть они могут быть заданы как:

• нижняя (верхняя) граница значений параметра;

• интервал его допустимых значений.

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

Во втором - считаем эквивалентными между собой любые значения свойств в заданном интервале.

В этом случае, вместо (3.5) требуется выделить подмножество объектов

*

X ^ X с набором свойств, отвечающих заданным условиям (в первом случае одному, во втором - двум):

X : = {хк)

С1а<Р1г,-<С]Н^ (3.13)

счк = 1

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

В таком случае, например, в качестве элемента матрицы смежности двудольного графа — ||ог'&||» которая используется для поиска

максимального паросочетания, нужно использовать:

X У/ = 1 (с]д- <Р]-<С1д )

(3.14)

3/ = 0 (Р1д<С1д-гР}д->С}д-2)

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

В соответствии с этим''различием, разработаны два варианта алгоритма, приведенные ниже.

Вариант 1 (допустим множественный выбор объектов):

1. Формирование матрицы соответствия объектов предъявляемым

требованиям 2,

(1) = Ца/^Ц по формуле (3.7).

2. Определение возможности получения точного решения. Необходимым условием является наличие в каждом столбце не менее одного элемента а^ — 1, ^к ■

3. Если условие (п.2) выполняется, то задача решена. Завершение работы алгоритма.

4. В противном случае, формируется матрица расстояний между

объектами и требованиями = •

5. Поиск приближенного решения. В каждом столбце выбираются

элементы с минимальным значением а-ц^ g—;—>min,

которые и формируют решение задачи. Завершение работы алгоритма.

Вариант 2 (множественный выбор объектов не допустим):

1. Формирование матрицы соответствия объектов предъявляемым

требованиям ZÖ) = ||а/&|| по формуле (3.7).

2. Нахождение максимального паросочетания.

3. Если найденное максимальное паросочетание полное, т.е. дефицит двудольного графа равен 0 и выполнено условие

А = К , то найдено точное решение задачи. Завершение работы алгоритма.

4. В противном случае, формируется матрица расстояний между объектами и требованиями

Dikl

5. Если мощность множества объектов велика и значительно превосходит мощность множества требований {{х/}и {ст}> т0 объединенное множество объектов

и наборов требований разбивается на группы с помощью кластерного анализа.

6. Оптимальная структура ищется в виде {vj^} с помощью

алгоритма решения транспортной задачи:

a. Внутри всего множества, если кластеризация не проводилась.

b. Внутри кластеров, если кластеризация проводилась.

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

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

Программная реализация содержит следующие модули:

• Формирование матрицы

= II ajfc I соответствия объектов

наборам требований.

• Формирование матрицы

Dik\ расстояний между

объектами и наборами требований.

• Поиска максимального паросочетания А в двудольном графе

G = [V

• Кластеризации объединенного множества объектов и наборов требований {{х/}и{^}}=> {Ст}.

• Поиска оптимального решения транспортной задачи (максимального

потока минимальной стоимости) {у/1}.

Работоспособность алгоритма тестировалась на задаче выбора подмножества из множества объектов по заданным наборам требований. Исходные данные приведены в диссертации. Решалась задача выбора 10 из 50 объектов:

• полностью соответствующих заданным требованиям; » максимально близким к заданным требованиям. Рассматривался наиболее сложный вариант задачи, при котором

множественный выбор объектов не допускается.

В таблице приведены точные решения задачи:_

У: (1)Х| (2)* (3) X;

У1 X, Хю Х2з

У 2 Хб х26 х29

Уз х)3 Х29 х26

У4 х18 XI8 Х)8

У5 х,6 Х16 Х16

Уб х21 х21 х21

У7 Х4 Х4 Х4

У8 Х7 Х8 Х7

У9 х14 Х7 Х,4

Ую Х2 Х2 X?

Во втором эксперименте требования были ужесточены таким образом, чтобы точное решение отсутствовало. Задача решалась без использования кластеризации и с разделением множества на 5 и 10 кластеров. Были

Решение без применения кластеризации Решение с разделением на 5 кластеров Решение с разделением на 10 кластеров

Л X; У< Х| Дк У1 йк

Уг Х]0 0 У) Хю 0 У1 Хю 0

Уг Х6 5 У: Хб 5 У2 Хб 5

Уз Хп 0 У) х26 8 Уз х.з 0

У4 XI8 4 У< Х|8 4 У4 Х|8 4

У5 Х16 9 У5 Х16 9 У5 Х43 59

У6 Х21 0 Уб Хл 0 Уб Х21 0

У7 Х4 7 У7 Х4 7 У7 Х38 31

У8 Х7 0 У8 Х7 0 У» Х32 20

У' Х|4 0 У» Хм 0 У9 х7 0

Ую Х2 5 Ую XI 5 Ую Х2 5

30 38 124

В качестве задачи, приближенной к реальным условиям, возникающим

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

№ п/п Название Р1аБЬ, КБайт ЛАМ, Кбайт 1\0, шт иАЯТ, шт

1 А08Р-ВР538Р 8192 148 54 3

2 АОиС7033 96 6 9 1

3 АОиС7019 62 8 14 1

4 АБиС7021 62 8 13 1

5 АОиСМЗбО 128 8 19 1

6 АБиС7024 62 8 30 1

7 АБиС7060 32 4 14 1

8 АБиС7032-8Ь 96 б 9 1

9 АВБР-ВР539Р 8192 148 54

10 АБиС7061 32 4 14 1

11 АБиС7028 62 8 40 1

12 АБиС7062 32 4 14 1

13 АБиС7129 126 8 8

14 АВиС7025 62. 8 30 1

15 АБиСМЗб! 128 8 19 1

Далее представлено решение задачи выбора объектов с помощью

Набор требований Объект

В1 А7 (АБиС70б0)

В2 А13 (АБиС7129)

ВЗ А5 (АБиСМЗбО)

В4 А1 (АБ8Р-ВР538Р)

В5 АЗ (АБиС7019)

В заключении приведены основные результаты работы.

Основные результаты работы

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

оптимального выбора, позволяющая использовать для ее решения аппарат теории графов.

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

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

4. Разработанный алгоритм был .программно реализован, что позволило провести вычислительные эксперименты, которые доказали его практическую эффективность и подтвердили обоснованность теоретических предположений. Использование предварительной кластеризации позволяет в 2-3 раза снизить размерность задачи выбора без существенных изменений точности решения. В тестовых задачах такое снижение составило менее 7%, что является приемлемым при инженерных расчетах.

Публикации автора по теме диссертации:

1. Тин Чжо. Кластерный анализ при решении задачи многокритериальной оптимизации. // «Микроэлектроника и информатика» 18-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов. - М., МИЭТ, 2011. - С.164.

2. Тин Чжо. Использование методов интеллектуального анализа данных для решения задач многокритериальной оптимизации. // Международная научная заочная конференция «Актуальные вопросы современной техники и технологии» Российская Федерация, г. Липецк, 29 января 2011г., - С. 64-65.

3. Тин Чжо. Использование кластерного анализа при решении задач многокритериальной оптимизации. // Международная научно-практическая конференция «Актуальные проблемы науки» Российская Федерация, г. Тамбов, 27 сентября 2011 г., - С. 122-123.

4. Тин Чжо. Использование кластерного анализа при решении задач оптимизации. // «Актуальные проблемы информатизации в науке, образовании и экономике 2011» 4-я Всероссийская межвузовская научно-

техническая конференция студентов и аспирантов. Тезису докладов. -М., МИЭТ, 2011.-С. 169.

5. Тин Чжо, Хтет Мин Пью. Выбор подмножества объектов с помощью алгоритмов линейного программирования. // Международная заочная научно-практическая конференция «Современные вопросы науки и образования - XXI век» Российская Федерация, г. Тамбов, 29 января 2012г, -С. 137-138.

6. Тин Чжо, Хтет Мин Пью. Использование графовых баз данных в системах управления процессами. // «Микроэлектроника и информатика» 20-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов. - М., МИЭТ, 2013. - С.172.

7. Тин Чжо. Особенности структурно-параметрического синтеза сложных систем. // «Актуальные проблемы информатизации в науке, образовании и экономике 2013» 6-я Всероссийская межвузовская научно-практическая конференция. Тезисы докладов. - М., МИЭТ, 2013. - С.147.

8. Тин Чжо, Хтет Мин Пью. Оптимизационный подход к задаче выбора подмножества объектов. // «Микроэлектроника и информатика» 20-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов. - М., МИЭТ, 2013. - С.221.

9. Тин Чжо. Решение задач многокритериального выбора при проектировании информационно-управляющих систем. //«Микроэлектроника и информатика» 21-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов. - М., МИЭТ, 2014. -С. 172.

10. Тин Чжо, Чжо Зо Е, Хтет Мин Пью. К вопросу повышения производительности систем распределенной обработки данных. // «Естественные и технические науки» № 4, 2012. С. 277-278. (перечень ВАК).

П.Киселев Д.В., Киселева Т.П., Тин Чжо, Хтет Мин Пью. Оптимизация выбора элементов технической системы с помощью интеллектуального анализа данных // «Фундаментальные и прикладные проблемы техники и технологии», Госуниверситет-УНПК, № 6 (296), 2012, -С. 277-278. (перечень ВАК)

12. Тин Чжо, Таит Зин Пью, Пья Сон Ко Ко, Пэйе Тэйн Наинг. Методика системы распознавания образов с помощью самоорганизующихся карт Кохонена нейронных сетей на основе Ма11аЬ. // Интернет Журнал «Науковедение», № 5 (18), 2013 (перечень ВАК)

13. Киселев Д.В., Тин Чжо, Пущин М.Н., Мьо Мин Све. Задачи многокритериального выбора при синтезе технических систем. // Интернет Журнал «Науковедение», № 4 (23), 2014 (перечень ВАК)

Подписано в печать:

Формат 60x84 1/16. Уч.-изд.л. /, (

Тираж $0 экз. Заказ №

Отпечатано в типографии ИПК МИЭТ.

124498, г. Москва, г. Зеленоград, проезд 4806, д. 5, МИЭТ