Подходы к анализу точности мультиагентных моделей динамических систем

Разработанный метод математического и компьютерного моделирования, реализованный в виде ПК STF-ElectronMod, предназначен для расчетов трехмерных температурных полей ЭМ при реальных конструктивных особенностях и условиях монтажа МС на поверхностях МПП. Одними из главных преимуществ STF-ElectronMod по сравнению с существующими системами теплового проектирования являются, во-первых, возможность моделирования многослойности структуры конструкции МПП, которая может насчитывать несколько десятков разнородных по толщине и материалам слоев, во-вторых, способность моделировать конвективный сопряженный теплообмен между МС и ЭРЭ и воздушной средой в электронной системе.

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

Литература

1. Кофанов Ю.Н. Теоретические основы конструирования, технологии и надежности радиоэлектронных средств. М.: Радио и связь, 1991.

2. Дульнев Г.И. Тепломассобмен в радиоэлектронной аппаратуре. М.: Высш. школа, 1984.

3. Билибин К.И., Власов А.И., Журавлева Л.В. [и др.]. Конструкторско-технологическое проектирование электронной аппаратуры. М.: Изд-во МГТУ им. Н.Э. Баумана, 2005.

4. Мадера А.Г. Моделирование теплообмена в технических системах. М.: НФ Первая исслед. лаб. им. акад. В.А. Мельникова, 2005.

5. Мадера А.Г., Кандалов П.И. Моделирование распределений температуры в электронных модулях // Проектирование и технология электронных средств. 2009. № 1. С. 50-53.

6. Kandalov P.I., Madera A.G. Mathematical and computing modeling of temperature fields in electronic modules // 16th Intern. Workshop on thermal investigations of ICs and systems, Barcelona, Spaine, 6-8 October, 2010.

References

1. Kofanov Yu.N., Teoreticheskie osnovy konstruirovaniya, tehnologii i nadezhnosti radioelektronnykh sredstv, Мoscow, Radio i svyaz, 1991.

2. Dulnev G.I., Teplomassoobmen v radioelektronnoy appa-rature, Мoscow, Vysshaya shkola, 1984.

3. Bilibin K.I., Makarchuk V.V., Myslovsky E.V., Parfenov O.D., Pirogova E.V., Shakhnov V.A., Sherstnev V.V., Konstruktor-sko-tekhnologicheskoe proektirovanie elektronnoy apparatury, Мoscow, MGTU, 2005.

4. Madera A.G., Modelirovanie teploobmena v tekhniches-kikh sistemakh, Мoscow, Nauchny Fond «Pervaya Issledovstelskaya lab.»: akad. V.A. Melnikova, 2005.

5. Madera A.G., Kandalov P.I., Proektirovanie i tekhnologiya elektronnykh sredstv, 2009, no. 1, pp. 50-53.

6. Kandalov P.I., Madera A.G., 16th Intern. Workshop on thermal investigations of ICs and systems, Barcelona, Spaine, 6-8 October, 2010.

УДК 519.6

ПОДХОДЫ К АНАЛИЗУ ТОЧНОСТИ МУЛЬТИАГЕНТНЫХ МОДЕЛЕЙ ДИНАМИЧЕСКИХ СИСТЕМ

М.И. Дли, д.т.н., профессор, зам. директора; В.В. Гимаров, к.э.н., доцент; И.В. Иванова, аспирант

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

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

APPROACHES TO ANALYZING THE ACCURACY OF MULTIAGENT MODELS OF DYNAMIC SYSTEMS

Dli MI, Ph.D., Professor, Deputy Director, Gimarov V V. , Ph.D., Associate Professor; Ivanova I. V, Postgraduate (SmolenskBranch National Research Institute «MEI», 1, Energetichesky proezd, Smolensk, 214013, Russia, midli@mail.ru) Аbstract. Currently, modeling is the most frequently used methods of analysis objects and processes. However, keeping in mind the complexity of dynamical systems, the simulation is the most efficient kind of modeling. Its application provides an opportunity to analyze hard-formalizable not previously encountered tasks, which are hardly described by analytic expression. Multi-agent models are the one of the varieties of simulation models that reflect the world as a set of separate subsystems - the agents. This article analyzes the role of multi-agent simulation for solving forecasting dynamic systems in adaptation to unsteady external and internal environment. It's appropriated four types of variation (changes in organizational structure of the model, changes of the agent interaction model, changes of the agent architecture, changes of the internal agent characteristics and parameters), arising during the operation of the multi-agent model. Based on the identified classes of variability it's proposed to use hierarchical multi-agent models that can adapt to the unsteady conditions of external and internal environment. At the same time in case of using this approach to modeling a problem of evaluating the effectiveness of the model is appeared. Hence, the role of the model performance monitoring based on approximation data analyses algorithms is increasing. In this article a method of the model accuracy estimating, which allows to allocate two types of errors, is proposed. The occurrence of the first type errors determines the advisability of the classification model reconstruction, based on a locally-approximation algorithms, including the initial stage of clustering trajectories. The occurrence of the second type errors testifies to the need to redirect implementation of the classification path to the selected class.

Keywords: simulation, multi-agent model, the locally-approximation algorithms, the types of variability models, estimation accuracy of the model, the model of the errors, the modification of the model.

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

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

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

Мультиагентная модель отражает окружающий мир в виде множества обособленных подсис-

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

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

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

MS=

где А - множество агентов системы; Е - множество внешних сред, в которых функционируют агенты, не имеющие отношения к рассматриваемой системе; О - множество взаимодействий между агентами системы; D - множество коммуникативных актов взаимодействия между агентами, которые формируют протокол коммуникации; Gi - цели агентов системы; G0 - цели агентов внешней среды [1].

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

вид: M^S=^A{Aуnр, Апод}, E{Екон, ЕМупр, Еnарт, Епостав,

Еnотреб}, О{Оь О2}, D{DЬ D2, ...}, Gi, Go), где представлены множества агентов: управляющих подразделений Аупр, подразделений, принимающих решения Апод, конкурентов предприятия Екон, муниципальных органов управления ЕМупр, парт-

неров предприятия (банки, маркетинговые агентства) Епарт, поставщиков предприятия Е„остае, потребителей предприятия Епотреб, а также множества отношений подчинения 01, отношения согласования действий 02, актов воздействия на потребителей и поставщиков предприятия с целью заключения новых договоров Б1 и множество актов передачи информации Б2.

Проведенный статистический анализ развития сложных динамических систем показывает, что в реальных ситуациях элементы модели со временем изменяются. То есть можно сказать, что для некоторого момента времени t мультиагентная модель будет иметь следующий вид: MSt={At, Е, 0t, Д, St, G1t, Got). Однако существующие на сегодняшний день подходы не принимают во внимание факт изменчивости при построении такой единой мультиагентной модели на весь период ее функционирования. Поэтому целесообразно использовать мультимодельный подход, предполагающий, что для каждой ситуации (конкретного временного промежутка) необходимо построить обособленную модель, выбор которой определяется значениями заранее заданных показателей. Исходя из логики функционирования сложных систем, можно выделить следующие виды изменчивости: изменения организационной структуры модели (модификация состава агентов модели и изменения более низких уровней), изменение модели взаимодействия агентов (новые виды связей и отношений, изменение архитектуры и характеристик агентов), изменение архитектуры агентов, а также внутренних характеристик и параметров агентов, а именно переопределение целей и задач его функционирования.

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

В работах [2, 3] для выбора модели предлагается использовать классификационный анализ траекторий развития системы, основанный на построении их локально-аппроксимационных моделей. Они представляют собой БД, включающие строки вида (хк-п, хНг,-\), •••, Хы, Хь хк+1>. Таким образом, каждая из классифицируемых траекторий описывается некоторой БД (многомерной матрицей). Для кластеризации объектов на несколько подмножеств (кластеров), в которых траектории более схожи между собой, используется метод нечетких с-средних.

Одновременно при использовании описанного подхода к моделированию возникает вопрос обос-

нованности выбора той или иной модели. В связи с этим возрастает роль мониторинга характеристик моделей, который может реализовываться с использованием алгоритмов аппроксимационного анализа данных [4, 5]. Остановимся на данном алгоритме подробнее.

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

Выбираются ближайшие к значениям х^-1) и хф (в смысле расстояния) последовательно стоящие значения х]_1, х] из каждой траектории того класса, к которому был отнесен ряд х(0. Определяются х(+1 при помощи выражения вида

Xt+1 ~ С0 + С1Х-1 + С2 X •

Если точка t совпадает с какой-либо точкой ti из имеющихся в БД траекторий класса, то матрица и (матрица точек траектории) модифицируется заменой х, на (х,+х)/2.

Полученное итоговое значение хм сравнивается с реальным xt+1. Если разность меньше заранее заданного значения 5, точность признается удовлетворительной, а опыт удачным.

Рассмотрим правило останова представленной процедуры определения точности мультиагентной модели, то есть обоснование числа Ы0 следующих подряд удачных опытов [4].

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

бы ни были цзад>0 и ¿>0, вероятность события Рг(ц < цзад) больше, чем (1-8), если N удовлетворяет неравенству

N0 - К > 1п

где К - среднее арифметическое количество коррекций БД при построении локально-аппроксима-ционных моделей траекторий классов.

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

ошибок первого рода можно задать цзад=0,3 и 51=0,4. Принимая значение К равным, например, 8, получаем А0>14.

Для ошибок второго рода цзад=0Д и 51=0,05. Тогда при данных значениях число подряд проведенных успешных опытов будет составлять А0-К>51. Учитывая значение К, получаем А0>59.

Таким образом, подставляя указанные значения в (2), можно определить Лг01 и А02, которые позволят при реализации процедуры мониторинга характеристик построенной модели выделить ошибки первого и второго видов и, соответственно, принять своевременное решение о выборе одной из модификаций мультиагентной модели.

Литература

1. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. М.: ЭдиториалУРСС, 2002.

2. Гимаров В.А., Гимаров В.В., Иванова И.В. Построение динамической мультиагентной модели с использованием классификации трендов // Программные продукты и системы. 2011. № 3. С. 162-166.

3. Гимаров В.А., Гимаров В.В., Иванова И.В. Нестационарная мультиагентная модель регионального рынка интернет-услуг // Прикладная информатика. 2011. № 6. С. 7-14.

4. Дли М.И., Круглов В.В., Осокин М.В. Локально-аппроксимационные модели социально-экономических систем и процессов. М.: Наука. Физматлит, 2000.

5. Дли М.И. Обобщенная локально-аппроксимационная модель динамического объекта // Программные продукты и системы. 1999. № 3. С. 15-21.

References

1. Tarasov V.B., Ot mnogoagentnykh sistem k intellektual-nym organizatsiyam: filosofiya, psikhologiya, informatika [From multi-agent systems to intellectual organizations: philosophy, psychology, computer science], Moscow, EditorialURSS, 2002.

2. Gimarov V.A., Gimarov V.V., Ivanova I.V., Programm-nye produkty i sistemy, 2011, no. 3, pp. 162-166.

3. Gimarov V.A., Gimarov V.V., Ivanova I.V., Prikladnaya informatika, 2011, no. 6, pp. 7-14.

4. Dli M.I., Kruglov V.V., Osokin M.V., Lokalno-approksi-matsionnye modeli sotsialno-ekonomicheskikh system i protsessov [Localy-approximation model of socio-economic systems and processes], Moscow, Nauka. Fizmatlit, 2000.

5. Dli M.I., Programmnye produkty i sistemy, 1999, no. 3, pp. 15-21.

УДК 519.688

ИНТЕРАКТИВНОЕ БАЙЕСОВСКОЕ МАТИРОВАНИЕ ИЗОБРАЖЕНИЙ

М.С. Синдеев, аспирант (Институт прикладной математики им. М.В. Келдыша РАН, Миусская пл., 4, г. Москва, 125047, Россия, msindeev@graphics.cs.msu.ru);

В. С. Конушин, программист

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

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

INTERACTIVE BAYESIAN IMAGE MATTING Sindeev M.S., Postgraduate (Keldysh Institute of Applied Mathematics of RAS, 4, Miusskaya Sq., Moscow, 125047, Russia, msindeev@graphics.cs.msu.ru);

Konushin V.S., Programmer

Аbstract. Digital matting is a process of extracting foreground object from an arbitrary natural image. The obtained object layer can be used for photomontage or for retouching the source image. Unlike the image segmentation problem, for fuzzy object edges (hair, feathers etc.) it is required to compute a valid opacity channel. The main disadvantages of existing methods are low accuracy and serious difficulties that occur to the user trying to improve the result, because many algorithms lack interactivity and require a full recomputation of the result. This article describes an interactive image matting algorithm