Имитационное моделирование в задачах конфигурирования дискретных объектов с заданным поведением
На правах рукописи
Петросов Давид Арегович ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ В ЗАДАЧАХ КОНФИГУРИРОВАНИЯ ДИСКРЕТНЫХ ОБЪЕКТОВ С ЗАДАННЫМ ПОВЕДЕНИЕМ Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Белгород – 2010
Работа выполнена в Белгородском государственном технологическом университете им. В.Г. Шухова кандидат технических наук, доцент
Научный консультант:
Иванов Игорь Владимирович доктор технических наук, профессор
Официальные оппоненты:
Магергут Валерий Залманович кандидат технических наук, доцент Штифанов Андрей Иванович Саратовский государственный технический
Ведущая организация:
университет
Защита диссертации состоится «30» сентября 2010 в 12:30 часов на заседании диссертационного совета Д212.014.06 при Белгородском государственном технологическом университете им. В.Г. Шухова, по адресу: 308012, г. Белгород, ул.
Костюкова, 46.
С диссертацией можно ознакомиться в библиотеке Белгородского государственного технологического университета им. В.Г. Шухова.
Автореферат разослан «_» 2010г.
Ученый секретарь диссертационного совета Ю.А. Бондаренко
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. Дискретное модельное описание является характерным не только для технических, но и для технологических, организационных, экономических, биологических и других типов объектов, что делает целесообразным изучение общих подходов и методов разработки и исследования моделей для такого рода «дискретных» объектов (ДО). Свойством дискретности может обладать структура, поведение и время функционирования объектов.
Один из основных этапов создания ДО – этап конфигурирования, то есть определение состава элементов и межэлементных связей.
Критериями эффективности решения задачи конфигурирования являются качество полученного решения и затраты связанные с получением этого решения.
Принятие решения при формировании конфигураций ДО осуществляется на основе генерации возможных структурных и функциональных моделей объекта, оценки этих моделей и выборе среди них лучшей альтернативы – такого варианта возможной модели ДО, которая функционирует должным образом, т.е. способна преобразовывать заданный входной сигнал в требуемый выходной сигнал.
В настоящее время имеются методы, позволяющие формализовать процедуру параметрического синтеза объекта, однако, отсутствуют эффективные методики, обеспечивающие структурное конфигурирование объекта с заданным поведением. Во многом это связано со сложностью моделей, учитывающих динамическое изменение связей в процессе функционирования объекта.
В основу работы положены три актуальных научных направления: имитационное моделирование, эволюционные методы и сети Петри.
Имитационное моделирование – один из мощных инструментов решения задач синтеза, который целесообразно использовать при конфигурировании объектов. Он дает возможность специалисту экспериментировать с проектируемыми и существующими объектами в случаях, когда делать это с реальным объектом невозможно или нецелесообразно. Разработке теоретических основ имитационного моделирования и применению этой методологии посвящены работы Н.Н. Моисеева, А.А. Самарского, В.П. Строгалева, Ю.И. Рыжикова, Р. Шеннона и др.
Эволюционные методы представляют собой современный математический аппарат нахождения эвристических решений сложных задач, основанный на понятии эволюции, что обуславливает их применение при конфигурировании ДО.
Теоретические и прикладные вопросы применения эволюционных методов рассматривались в работах А.Г. Ивахненко, Н.И. Корсунова, В.М. Курейчика, Д. Э.
Попова, Дж. Холанда, В. Ф. Хорошевского и др.
Сети Петри, как математический аппарат моделирования динамических дискретных систем, являются удобным формальным и графическим языком для моделирования систем с параллелизмом. Этот язык представляет собой обобщение теории автоматов, в котором может быть выражена концепция одновременно происходящих событий, что позволяет применять данный математический аппарат при создании сложных дискретных объектов. Описанию и применению данного математического аппарата посвящены работы В.Е. Котова, С.А. Юдицкого, В.З.
Магергута, И.А. Ломазовой, Дж. Питерсона, и др.
Актуальность темы диссертационного исследования связана с необходимостью совершенствования методов разработки и исследования математических моделей сложных распределенных процессов функционирования дискретных технических и организационных систем.
Целью диссертационной работы является разработка и исследование имитационных моделей дискретных объектов с заданным поведением.
Поставленная цель определила следующие основные задачи исследования:
1. Выполнить анализ существующих математических моделей конфигурирования ДО;
2. Разработать имитационную модель формирования конфигурации ДО со статической структурой;
3. Разработать имитационную модель формирования конфигурации ДО с динамической структурой;
4. Выполнить программную реализацию конфигурирования ДО на основе разработанных математических моделей.
Методы исследований. Для решения поставленных задач использовались методы системного анализа, эволюционных вычислений, теории сетей Петри (СП) и дискретной математики.
Научная новизна диссертационной работы состоит в следующем:
1. Разработана имитационная модель конфигурирования дискретных объектов, учитывающая возможность динамической перестройки структуры, на основе математического аппарата вложенных сетей Петри и генетических алгоритмов;
2. Предложено представление моделей дискретных объектов в виде сетей Петри для кодирования генотипа в рамках генетических алгоритмов при решении задач конфигурирования;
3. Предложен подход к формированию критериев качества конфигурирования объектов, используемый в рамках генетического алгоритма для построения функции приспособленности.
Практическая значимость. На основе полученных моделей и алгоритмов разработана информационная система формирования конфигурации ДО с заданным поведением для решения задач обработки информации в произвольной предметной области. Практическая значимость подтверждается актами о внедрении отдельных результатов диссертационных исследований на ООО «Завод моющих средств» (г.
Шебекино) и в Белгородском государственном технологическом университете им.В.Г.Шухова.
Положения, выносимые на защиту:
1. Способ построения конфигураций ДО с использованием генетических алгоритмов, описанных вложенными сетями Петри;
2. Метод поиска конфигурации дискретного объекта с фиксированными межкомпонентными связями;
3. Метод поиска конфигурации дискретного объекта с перестраиваемыми межкомпонентными связями;
4. Архитектура системы имитационного моделирования дискретных объектов на основе разработанных методов;
5. Комплекс проблемно-ориентированных программ имитационного моделирования дискретных объектов с заданным поведением.
Достоверность и обоснованность результатов исследований определяются использованием современных методов исследований, корректностью математических выводов и компьютерного моделирования, а так же результатами вычислительных экспериментов.
Личный вклад соискателя Все разделы диссертационной работы выполнены лично автором. Все изложенные в диссертационной работе результаты исследований получены либо соискателем лично, либо при его непосредственном участии.
В работах, опубликованных в соавторстве, лично автором выполнена адаптация и формализация генетических алгоритмов на основе инструментария вложенных сетей Петри [4, 7, 8], разработана концепция построения структур ДО с фиксированными и перестраиваемыми межкомпонентными связями [5, 6, 9, 12], разработан вычислительный алгоритм и модуль поиска конфигурации [13, 14].
Апробация результатов диссертации. Основные научные и практические результаты докладывались и обсуждались на 7 Международном форуме «Радиоэлектроника и молодежь в XXI веке» (Харьков, 2003), 8 Международном форуме «Радиоэлектроника и молодежь в XXI веке» (Харьков, 2004), Международной научно-практической конференции «Информационные технологии в науку и образование» (Харьков 2005), Международной научно-технической конференции молодых учёных БГТУ им. В.Г. Шухова (г. Белгород, 2009), Международной научной конференции «Проблемы управления, передачи и обработки информации (АТМ-ТКИ 50)» (г. Саратов, 2009), XIV Международной научно-производственной конференции "Проблемы сельскохозяйственного производства на современном этапе и пути их решения" (г. Белгород, 2010), на ежегодных научно-технических семинарах кафедры «Информационные технологии» БГТУ им. В.Г.Шухова (2008-2010 г.г.).
Публикации. Основные положения работы изложены в 12 печатных работах, из которых 3 в изданиях, рекомендованных ВАК РФ по научной специальности диссертационной работы. Получено 2 свидетельства о государственной регистрации программ для ЭВМ.
Диссертационная работа состоит из введения, четырех глав, заключения и списка литературных источников из 139 наименований. Содержание работы изложено на 153 листах машинописного текста.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, сформулирована цель и поставлены задачи, необходимые для ее достижения. Кратко изложены основные результаты, определяющие новизну и практическую ценность работы. Перечислены места реализации и апробации результатов работы.
Глава 1 «Обзор современного состояния проблемы» является вводно постановочной, в ней поведен обзор современного состояния проблемной области, дано определение ДО, рассмотрены формальные и интеллектуальные методы конфигурирования ДО.
Рассмотрены объекты различной физической природы, как то: организационные, механические, электротехнические, технологические и объекты вычислительной техники. Показана общность этих объектов с точки зрения возможности их описания дискретными моделями с заданным поведением. Установлено существование класса задач конфигурирования дискретных объектов, часть из которых может быть решена путем использования имитационных моделей с фиксированными межэлементными связями, а часть потребует применения динамически перестраиваемых структур моделей.
Также проведен анализ используемых инструментариев и на основе этого анализа предложено использовать генетические алгоритмы как формальный метод поиска наилучшей конфигурации и сети Петри, как математический инструмент для построения имитационной модели компонентов ДО, а также как средство реализации самого генетического алгоритма. Проведен анализ существующих программных средств, способных решать поставленную задачу.
Глава 2 «Имитационная модель формирования конфигурации дискретного объекта со статической структурой» посвящена созданию имитационной математической модели процесса формирования конфигурации ДО с заданным поведением, имеющего фиксированный набор связей.
Для этого описывается объект О O=S,C, (1) где O – объект, который необходимо сконфигурировать, S – фиксированная структура объекта, С– состав объекта.
C = (C1,…, Ci, …,CR), (2) где Ci – i-й компонент объекта, R – количество компонентов объекта.
{} Ci = Cij M1 i j=, (3) где Cij – j-й экземпляр i-го компонента, Mi – количество экземпляров i-го компонента.
P = { Pk } L= k, (4) где P – множество свойств, которыми может обладать конфигурируемый объект, Pk – k-е свойство множества P, L – количество свойств множества P.
Требуется для заданного свойства Pk 0, которым должен обладать объект О, подобрать по одному экземпляру Cij (k ) каждого компонента Ci так, чтобы объект ( ) O = S, C1 j(k 0 ),K, C Rj(k 0 ), (5) обладал свойством Pk 0.
Для описания объекта O (1) в виде сети Петри (СП), необходимо определять его структуру S и состав C также на языке СП.
Согласно (2) и (3) состав C полностью определяется компонентами, поэтому каждый компонент Ci должен быть описан в виде СП, а это в свою очередь означает, что каждый экземпляр компонента Cij необходимо определять на языке СП.
Каждый Cij экземпляр обозначим через СП, моделирующую его,- PNij (Petri Nets)ij.
Выделяем у каждого экземпляра входы и выходы, которые моделируются позициями сети PNij. Множество входных и выходных позиций обозначаются через INij и OUTij.
Между элементами множеств INij и INi, а также OUTij и OUTi должны существовать взаимно однозначные соответствия FijIN:INijINi и FijOUT:OUTijOUTi.
На рис. 1 (а) показано соответствие между компонентами и экземплярами.
СП, моделирующая компонент Ci, обозначается через PNi (Petri Nets)i. Если компонент Ci, представлен экземпляром Cijo, то PN i = PN ij. o Структура S объекта O полностью определяется взаимосвязями между компонентами, которые можно моделировать переходами СП. Обозначим множество таких переходов через T.
Каждый переход tqT соединяет выходные позиции некоторых компонентов Ci1, C i2, …, Ci с входными позициями некоторых других компонентов Ci A+1, Ci A+ 2, …, A Ci A+ B, что наглядно иллюстрируется рис.1 (б).
PN ij C ij IN ij OUTij tq Ci A + Ci ij ij FIN FOUT Ci Ci A + B Ci A IN i OUTi а) б) Рисунок 1. Соответствие (а) и связи (б) между компонентом и экземпляром R Соответствие F : T U(INi UOUT) полностью определяет структуру S объекта O.
i i = СП, моделирующая объект O, описывается в виде кодовой строки PN=PN1,…,PNi,…,PNR,T,F, (6) где PNi – модель компонента Ci, а множество переходов T и соответствие F определяют структуру S объекта O.
Для выбора необходимой модели объекта O определим поведение объекта как способность преобразовывать заданный входной сигнал в необходимый выходной.
Поведение объекта описывается парой неотрицательных целочисленных векторов ) ( ) ( ZOUT = z1, K, zOUT OUT ZIN = z1, K, z IN IN W V 0, и IN где zv – число меток, поступивших в v-ю входную позицию перед запуском сети PN, zwout – число меток, появившихся в w-й выходной позиции после остановки сети PN, V0 и W0 – число элементов множеств IN и OUT соответственно.
Таким образом, поставленная задача сводится к следующей. Среди всех гипотетически возможных моделей PN объекта O найти такую, которая обладает свойством Zk.
Для того чтобы проверить, обладает ли модель PN свойством Zk, необходимо сформировать эту модель, на ее вход IN подать вектор ZkIN, запустить сеть PN и после ее остановки сравнить метки на выходе OUT с вектором ZkOUT.
Меру близости будем определять, привлекая понятие метрического пространства и рассматривая полученный вектор ZOUT и эталонный вектор ZkOUT как элементы W евклидова пространства 0 – множества упорядоченных наборов из W ( ) действительных чисел x = x1, K, xW0 с расстоянием W 1 (x, y ) = x w y w w =1 (7) ( ) где y = y1, K, yW0.
Чем меньше 1(ZOUT,ZkOUT), тем ближе модель PN к свойству Zk. Если 1(ZOUT,ZkOUT)=0, то модель PN обладает свойством Zk. Естественно рассматривать расстояние 1 как целевую функцию.
Для поиска конфигурации используется генетический алгоритм (ГА). Операторы ГА будут моделироваться переходами вложенных сетей Петри (ВСП), а генотипы – макрометками ВСП.
Множество генотипов, непосредственно обрабатываемое ГА, называется популяцией. Начальная популяция может формироваться либо автоматически (например, случайным выбором экземпляров компонентов), либо задаваться непосредственно разработчиками ДО. Обозначим начальную популяцию через G0=(PN1,…,PN2n), где PNi – i-ая модель объекта проектирования в виде СП, 2n – фиксированный размер популяции. Здесь для простоты дальнейшего описания предполагается, что размер популяции является четным числом.
Каждую модель PNi разместим в соответствующей позиции Ai в качестве макрометки ВСП.
Оператор отбора моделируется переходом SEL, который будет копировать PNi из позиции Ai и размещать эти копии в позициях B1, B2, …,B2i-1, B2i, …, B2n-1, B2n в качестве макрометок ВСП. Обозначим макрометки, размещенные в позициях B2n-1 и B2i, через PN j и PN j. Макрометки размещаются в позициях B1, …, B2n в 2 i 1 2i соответствии со значением целевой функции (7) по правилу: чем меньше значение функции (7), тем меньше номер позиции, в которой размещается макрометка. Таким образом, в позиции B1 размещается самая лучшая макрометка, в позиции B2 – чуть худшая макрометка и т.д. до позиции B2n, в которой будет находиться самая плохая макрометка.
Оператор скрещивания моделируется переходом CROSSi, который будет забирать макрометки PN j и PN j из позиций B2i-1 и B2i, скрещивать их и размещать новые 2 i 1 2i макрометки PN j2 i 1 и PN j2 i в позициях D2i-1 и D2i соответственно. Макрометки скрещиваются по следующему правилу:
1. Случайным образом из множества {1,2,…,R} выбирается некоторое число, которое мы обозначим через r.
2. В генотипах PN j2i 1 и PN j2 i выделяем модель r-го компонента j j j PN j2i = PN 12i,..., PN r2i,..., PN R i, T, F j j j PN j2i 1 = PN12i 1,..., PN r2i 1,..., PN R i 1, T, F и 3. Меняем местами выделенные модели и получаем новые макрометки j j j j j j j j PN 2i 1 = PN 12i 1,..., PN r2i,..., PN R i 1, T, F 2 PN 2i = PN 12i,..., PN r 2i 1,..., PN R i, T, F и Оператор мутации моделируется переходом MUT2i, который будет забирать макрометку PN j из позиции D2i, осуществлять ее мутацию и размещать новую 2i макрометку PN j в позиции E2i Макрометка подвергается мутации по следующему 2i правилу:
1. Случайным образом из множества {1,2,…,R} выбирается некоторое число, которое мы обозначим через r.
PN j2 i 2. В генотипе выделяем модель r -го компонента j j j j PN 2i = PN 12i,..., PN r2i,..., PN R i, T, F 3. Из множества {PNrj}Mj=1 моделей экземпляров r -го компонента случайным j2 i образом выбираем новую модель, которую мы обозначим через PN rnew, заменяем ею j j j j PN 2i = PN12i,..., PN r2i,..., PN R i, T, F j2 i new модель PN и получаем новую макрометку r Оператор мутации макрометки в позиции D2i-1 моделируется аналогично.
Оператор редукции моделируется переходом RED, который будет забирать макрометки из позиций E1,…,E2n и из позиций A1,…,A2n, удалять худшие макрометки, а оставшиеся размещать в позициях A1,…,A2n. Макрометки удаляются по следующему правилу:
1. Для каждой макрометки вычисляется целевая функция (7).
2. В позиции A1 размещается самая лучшая макрометка, в позиции A2 – чуть худшая макрометка и т.д. до позиции A2n, в которой будет находиться самая плохая макрометка. Обозначим макрометку, размещенную в позиции Ai, через PN i.
3. Все остальные макрометки удаляются. Заметим, что будет удалено ровно 2n макрометок.
Структура вложенной СП с обозначением всех макрометок показана на рис. 2.
Рисунок 2. Формализация генетического алгоритма с помощью ВСП Глава 3 «Имитационная модель формирования конфигурации дискретного объекта с динамической структурой» посвящена созданию имитационной математической модели конфигурирования ДО с переменными межкомпонентными связями.
Рассматривается класс задач формирования конфигурации ДО, который можно представить кортежем:
K A B O = In, Out,{Sk }k =1,{ f a }a =1,{Fb }b=1, (8) где O – объект, который необходимо сконфигурировать;
In – множество входных данных объекта O;
Out – множество выходных данных объекта O;
Sk – k-я подсистема объекта O;
a – функция, определяющая, какие выходные данные соответствуют входным данным: a : InOut;
Fb – бинарное отношение на множестве {Sk}Kk=1 : Fb {Sk}Kk=1 {Sk}Kk=1.
Требуется для заданной функции f a подобрать бинарное отношение Fb такое, 0 чтобы множество подсистем {Sk}Kk=1 обеспечивало обработку объектом O входных данных в выходные данные в соответствии с функцией f a. Входы объекта O будут моделироваться множеством позиций Pin={pmin}Mm=1, где M – количество входов объекта, а ее выходы – множеством позиций Pout={pnout}Nn=1, где N – количество выходов объекта (рис. 3).
in M ( k ) Входы подсистемы Sk – это множество Pkin = {pk,m }m =1, где M(k) – количество N (k ) входов подсистемы Sk, а ее выходы – множество Pkout = {pkout }n=1, где N(k) – количество,n выходов подсистемы Sk.
p1in p1out … … O in out pm pn … … out in pN pM Рисунок 3. Контекстная модель ДО в задаче конфигурирования Входы и выходы подсистем объекта O моделируются множеством позиций.
Подсистемы {Sk}Kk=1 могут быть связаны как между собой, так и с входами и выходами объекта O. Эти связи будут моделироваться множеством переходов T={tq}Qq=1, где Q – количество переходов. Каждый переход tq характеризуется своими входными и выходными позициями. Входами перехода tq могут быть как любые входы объекта O, так и любые выходы подсистем {Sk}Kk=1. Выходами перехода tq могут быть как любые выходы объекта O, так и любые входы подсистем {Sk}Kk=1.
Обозначим входы перехода tq через Inq, а выходы – через Outq. Тогда, исходя из вышесказанного, In q Pin U U Pkout и Out P U U P.
K K in q out k k =1 k =1 Для каждого входа объекта O должен существовать переход tq, соединенный с этим входом, а для каждого выхода каждой подсистемы Sk должен существовать переход tq, соединенный с этим выходом. Формально эти требования можно записать в виде равенства U In q = Pin U U Pkout. Соответственно, для каждого выхода объекта O Q K k =1 q = должен существовать переход tq, соединенный с этим выходом, и для каждого входа каждой подсистемы Sk должен существовать переход tq, соединенный с этим входом.
Формально эти требования запишем в виде равенства U Outq = Pout U U Pkin.
Q K k =1 q = Разные переходы могут иметь некоторые общие входные и выходные позиции, но полностью совпадающих переходов быть не должно. Это требование формализуется следующим образом: Inq1= Inq2Outq1 Outq2 (при q1 q2)и Outq1= Outq2 Inq1 Inq (при q1 q2).
Множество подсистем {Sk}Kk=1 вместе с подмножеством множества переходов T={tq}Qq=1 полностью определяют текущую структуру объекта O. Не обязательно все подсистемы {Sk}Kk=1 должны быть задействованы в текущей структуре. При этом перестройка структуры объекта O определяется изменением подмножества задействованных в данный момент переходов.
Перестройка функций происходит в подсистемах {Sk}Kk=1. В общем случае каждой подсистеме Sk можно сопоставить множество сетей Петри, которые будут моделями программ обработки данных. Это множество можно представить как PNk и определить его следующим образом: PN k = {PN k,r }rR=(1k ), где PNk,r – r-й алгоритм обработки данных подсистемой Sk, представленный в виде СП.
Формально необходимо для каждой СП PNk,r описать ее позиции, переходы и дуги. В общем случае сеть PNk,r моделирует некоторое действие по преобразованию входных данных в выходные данные. Поэтому в качестве моделей алгоритмов будут рассматриваются не СП PNk,r, а переходы («вырожденные» сети Петри). Таким образом, множество PNk будет выглядеть так PN k = {t k,r }rR=(1k ). Входами Ink,r каждого перехода tk,r могут любые входы подсистемы Sk: Ink,rPkin, а выходами Outk,r каждого перехода tk,r могут любые выходы подсистемы Sk: Outk,rPkout.
Модель объекта O в виде СП может выглядеть так, как показано на рис. 4. В этой модели выделен путь, по которому входные данные, поступив на верхние два входа объекта O (на рисунке в виде двух меток), проходят через ее подсистемы и появляются на нижнем выходе объекта O. Пунктиром выделены незадействованные переходы и дуги.
O t1 t • S • S t S t t2 t Рисунок 4. Пример имитационной модели ДО на основе сети Петри Формализуем генотип G, он должен определять:
какие переходы из множества T={tq}Qq=1 будут представлены в модели объекта O;
какие переходы из множества PN k = {tk,r }rR=(1k ) будут представлены в модели каждой подсистемы Sk.
Таким образом, генотип G будет иметь следующий вид:
G=(g1,…,gq,…,gQ,h1,…,hk,…,hK), где gq{0,1} и hk{0,1,…,r,…,R(k)}.
Если gq = 0, то переход tq отсутствует в модели объекта O, иначе (gq = 1) переход tq присутствует в модели объекта O. Если hk=0, то в модели подсистемы Sk отсутствует алгоритм обработки данных. Если hk=r (r{1,…,R(k)}), то в модели подсистемы Sk представлен переход tk,r.
Среди всех гипотетически возможных моделей объекта O необходимо найти такую, которая решает поставленную задачу: из имеющегося множества подсистем {Sk}Kk=1 и системы переходов T={tq}Qq=1 построить такой объект O, который на входной вектор реагировал бы требуемым выходным вектором.
Для оценки этой близости вводим обозначение для требуемого вектора: V=(v1,…, vn,…,vN), где vn – количество меток, которые должны находиться в позиции pnout объекта O. Вектор, который получился в результате работы объекта O, обозначим через W=(w1,…,wn,…,wN), где wn – количество меток, которые реально находятся в позиции pnout объекта O. Разницу (расстояние) между требуемым и реальным N вектором можно оценивать по формуле (V,W ) = vn wn.
n = Выбор целевой функции влияет на эффективность работы генетического алгоритма. Поэтому на практике можно использовать и формулу, задающую N классическое евклидово расстояние (V, W ) = (vn wn )2, и редко используемую n = формулу (V, W ) = max vn wn. При программной реализации генетического алгоритма 1n N необходимо заложить в систему возможность работы с формулой 1/ p N p (V,W ) = vn wn, которая при p=1, p=2 и p представляет собой n =1 рассмотренные выше формулы. Чем меньше, тем ближе модель объекта O к требуемой конфигурации. При =0 модель полностью соответствует заданному требованию. После выбора целевой функции можно описать операторы генетического алгоритма.
Оператор скрещивания можно описать следующим образом. Рассмотрим два генотипа: G1 = (g11, K, g 1, g 1 +1, K gQ, h11,K, hk1, hk1+1,K, hK ), G2 = (g12,K, g q2, g q2+1,K gQ, h12,K, hk2, hk2+1,K, hK ).
1 1 2 q q Случайным образом выбираем два числа: q из диапазона (множества) {1,2,…,Q} и k из диапазона {1,2,…,K}, а затем меняем соответствующие участки генотипов. Таким образом, из родителей G1 и G2 получаются потомки G3 и G4, наследующие свойства родителей: G3 = (g11,K, g1, gq+1,KgQ, h11,K, hk1, hk2+1,K, hK ), G4 = (g12,K, g q2, g 1+1,K gQ, h12,K, hk2, hk1+1,K, hK ).
2 2 2 1 q q Можно ограничиться и выбором какого-то одного числа (q или k). Сколько чисел будет выбрано (одно или два) и, если одно, то какое именно, можно также определять случайным образом. Можно также выбрать для каждого диапазона ({1,2,…,Q} и {1,2,…,K}) по две точки и меняться «серединками».
Оператор мутации описывается следующим образом. Рассмотрим один генотип G=(g1,…,gq,…,gQ,h1,…,hk,…,hK). Случайно выбираем два числа: q из диапазона {1,2,…,Q} и k из диапазона {1,2,…,K}. А затем меняем значения gq и hk следующим образом. Если было gq =0, меняем его на единицу: gq =1. И наоборот: если было gq =1, то станет gq =0. Если было hk=r, то меняем его на любое другое из диапазона {0,1,…,r 1,r+1,…,R(k)}. Естественно, при r=0 это будет диапазон {1,…,R(k)}, а при r=R(k) это будет диапазон {0,1,…,R(k)-1}.
Оператор редукции удаляет слабые генотипы. Для этого после скрещивания определяются качества всех потомков. После чего потомки и родители объединяются в одно множество генотипов, что позволяет упорядочить их по качеству. В соответствии с настройками ГА происходит отсеивание конфигураций.
В частном случае перестройка структуры объекта O может происходить с использованием межкомпонентной шины.
Вся система элементов ДО и шин обрабатывается последовательно от входа системы к ее выходу. Сначала первый слой элементов получает и обрабатывает входные сигналы. Затем по первой шине сигналы передаются на второй слой. После обработки сигналы по второй шине поступают на третий слой и т.д. Процесс заканчивается после обработки сигналов последним слоем элементов, и выходной вектор сравнивается с искомым.
Формально, для каждой шины задано множество входных позиций In = {Inm} и множество выходных позиций Out = {Outm} (m = 1, 2, …, M). Входные позиции – это выходы предыдущего блока элементов ДО, а выходные позиции – входы последующего блока элементов (рис. 5).
In1 Out Шина In2 Out Inm Outm InM OutM Рисунок 5. Обобщение межкомпонентных связей в слой «Шина» Для моделирования межкомпонентной шины целесообразно использовать: связи («вырожденные сети Петри»), элементы ДО и логические элементы. Каждой выходной позиции Outm сопоставляются (генерируются случайным образом):
– блок ИЛИ с указанием множества входных позиций;
– блок ИЛИ-НЕ с указанием множества входных позиций;
– количество блоков И;
– количество блоков И-НЕ;
– множество входных позиций для каждого блока И (И-НЕ).
Выходной позиции могут быть сопоставлены один блок ИЛИ, один блок ИЛИ-НЕ, несколько блоков И, несколько блоков И-НЕ.
Шина работает следующим образом. Выходные позиции обрабатываются по порядку от Out1 до Outm согласно алгоритму. Первым проверяется блок ИЛИ, затем ИЛИ-НЕ. Потом проверяются блоки И, а в самом конце – И-НЕ. Для ускорения процесса сначала проверяются блоки И с меньшим количеством входных позиций.
Проверка останавливается, когда найден блок, который можно будет запустить.
Таким образом, шина полностью характеризуется набором блоков, сопоставленных каждой выходной позиции. Поэтому скрещивание шин – это обмен выходными позициями.
Родители: X-шина: xOut1, …, xOutm, xOutm+1, …, xOutM Y-шина: yOut1, …, yOutm, yOutm+1, …, yOutM Потомки: X-шина: xOut1, …, xOutm, yOutm+1, …, yOutM Y-шина: yOut1, …, yOutm, xOutm+1, …, xOutM Мутация шины – изменение для какой-либо выходной позиции:
– множества входных позиций блока ИЛИ;
– количества блоков И;
– множества входных позиций для каждого блока И.
В главе 4 «Разработка системы имитационного моделирования конфигурирования дискретного объекта» для анализа эффективности и проверки адекватности полученных математических моделей процесса формирования конфигураций ДО создана информационная система (ИС), архитектура которой представлена на рис. 6.
Архитектура включает 5 основных элементов: элементная база, база знаний, генетический алгоритм на основе вложенных сетей Петри, модуль поиска и модуль анализа моделей. ИС выполняет функцию поиска конфигурации ДО, на основе моделей ДО хранящихся в элементной базе формализованных сетями Петри. Так же ИС помогает анализировать полученные конфигурации ДО, соответствующих критериям поиска, используя базу знаний (БЗ). Модуль эмуляции и редактирования, входящий в состав блока анализа, позволяет оценить и отредактировать модели приближенные к критериям поиска, и принять решение о вводе новых элементов ДО в элементную базу.
Функции модельера разделены между двумя интерфейсными модулями интерфейсом «Пользователя» и интерфейсом «Эксперта». Интерфейс «Пользователя» предназначен для специалиста в предметной области, в которой происходит моделирование. Интерфейс позволяет управлять системой с помощью параметров поиска, элементной базы и работой с модулем анализа. Интерфейс «Эксперта» предназначен для работы с настройками генетического алгоритма, базы знаний и элементной базы. Тем самым пользователь ИС должен быть специалистом лишь в своей предметной области, а настройки конфигурирования ДО проводятся экспертом.
На основе функциональной модели ИС была осуществлена ее программная реализация. Комплекс проблемно-ориентированных программ разработан на языке программирования Object Pascal (в среде Delphi) и зарегистрирован в ФГУ ФИПС. Из списка функциональных задач были решены следующие:
Генерация генотипов по заданным настройкам;
Эмуляция генотипов;
Подбор структуры сети по заданному входу и выходу;
Модуль для тестирования для проведения экспериментов;
Менеджер генотипов.
Интерфейс эксперта «Выходной» интерфейс Создание и Элементная База (ЭБ) редактирование Модели моделей Интерфейс Пользователя объектов на Настройки СП Правила База Знаний (БЗ) Настройки Модель Генетический Правила алгоритм на основе ЭБ сетей Петри (СП) Модель Параметры Анализ Поиск Модели Отказ конфигурации поиска Корректировка Проблемно-ориентированное ПО Рисунок 6. Архитектура информационной системы моделирования ДО Входными документами в системах являются файлы типовых устройств описанных в виде сетей Петри. Для стандартизации предусмотрено описание сетей Петри при помощи языка PNML (Petri Net Markup Language).
На основе предложенного метода имитационного моделирования ДО и разработанной архитектуры ИС реализован и зарегистрирован комплекс программ.
Показана его работа в процессе решения задачи формирования конфигурации вычислительных систем с заданным поведением, задачи распределения ресурсов на примере формирования расписания занятий в вузе и построена система массового обслуживания операционного зала банка. Среди иных задач использования предложенного метода можно назвать, например, задачу нахождения ветви, характеризующую правильную СП, на дереве достижимых маркировок, нахождение нужных конфигураций при создании технического комплекса АСУ ТП и ряд других.
Для решения задачи поиска конфигурации триггерного устройства построены математические модели триггеров и их конфигурации на основе сетей Петри;
формирования конфигурации проводится на основе адаптированного генетических алгоритмов.
Модель конфигурации триггерного устройства с «квадратной» структурой показана на рис. 7.
Если подсистема S1,1 моделируется RS-триггером, подсистема S1,2 – Т-триггером, S2,1 – D-триггером, а подсистема S2,2 – Т-триггером, и все триггеры находятся в единичном состоянии, то конфигурация O=(RS, T, D, T) будет иметь такой вид, как показано на рисунке 8 в соответствии с (6).
pin1 tin1 pin1,1 pout1,1 t1,1 pin1,2 pout1,2 tout1 pout S1,1 S1, pin2 tin2 pin2,1 pout2,1 t2,1 pin2,2 pout2,2 tout2 pout pin3 tin3 pin3,1 pout3,1 t3,1 pin3,2 pout3,2 tout3 pout S2,1 S2, pin4 tin4 pin4,1 pout4,1 t4,1 pin4,2 pout4,2 tout4 pout Рисунок 7. Модель конфигурации ДО размерностью Конфигурация O=(RS, T, D, T) работает по следующему алгоритму:
– на вход подаются данные, моделируемые метками;
– запускаются «входные» переходы tin1 – tin4;
– запускаются триггеры «первой очереди» RS1,1 и D2,1;
– запускаются переходы «первой очереди» t1,1 – t4,1;
– запускаются триггеры «второй очереди» T1,2 и T2,2;
– запускаются «выходные» переходы tout1 – tout4;
– в результате получается выходной вектор.
p in 1 t in 1 p in 1,1 p out1,1 p in 1,2 p out1,2 t out1 p out t 1, S Q • • Q T RS 1,1 T 1, C Q R Q p in 2 t in 2 p in 2,1 p out2,1 p in 2,2 p out2,2 t out2 p out t 2, p in 3 t in 3 p in 3,1 p out3,1 p in 3,2 p out3,2 t out3 p out t 3, D Q • • Q T D 2,1 T 2, C Q C Q p in 4 t in 4 p in 4,1 p out4,1 p in 4,2 p out4,2 t out4 p out t 4, Рисунок 8. Пример конфигурация триггерного устройства с начальным состоянием (1, 1, 1, 1) Например, если на вход конфигурации подать вектор (0, 1, 0, 1), то на выходе получится вектор (1, 0, 1, 0).
Задача составления расписания занятий представлена в виде ситуации распределения ресурсов, где ресурсами являются студенческие группы, а средствами обработки аудиторные помещения.
Для решения задачи распределения ресурсов, поступающих во входные позиции IN (8) дискретного объекта структура генотипа представлена с использованием топологии «звезда» в следующем виде (рис. 9).
OUT IN tout, 1 S Pout, 1 Cn, j C1, j C2, j P P1 P. Pin,. tin,.
t1 t t t1 t2 t1 t t Pin, t tin, tout, Pout, Cn, j P...
Pin, tin, t1 PB.
C2, j Pout, P tout, 3..
..
t.
tin, n Pin, n..
P C1, j C1, j C2, j.. t t1 Cn, j t1 t...
..
Pout, n tout, n..
.
S P1 P1 P Sn Рисунок 9. Структура генотипа в задаче распределения ресурсов Объект O состоит из множества подсистем O=(S1,…,Sn), которые в свою очередь состоят из компонентов C=(C1,…,Ci) и экземпляров Ci={Cij}mj=1.
Позиция PB – является источником, в который поступают ресурсы для обработки.
Количество переходов в модели Cij должно соответствовать количеству ресурсов, которое экземпляр обрабатывает за одну итерацию.
Метка во втором уровне вложенной сети Петри является ресурсом и представлена следующим образом K=G,D,M, где M=(M1,…,Mn) – маркер обработки ресурса;
G=(G1,…,Gn) – маркер принадлежности к типу ресурсов;
D=(D1,…,Dn) – маркер принадлежности к совместному использованию.
В задаче составления расписания маркер принадлежности к совместному использованию D – индикатор потока для проведения лекционных занятий (лекционное занятие может проводиться более чем с одной группой).
Маркер принадлежности к типу ресурсов G – индикатор специальности (ввиду того, что предметы на разных специальностях не всегда совпадают по своему наполнению материалом).
Маркер обработки ресурса M – состоит из количества и типа аудиторных занятий на учебный день.
Количество циклов обработки ресурсов в предложенной модели оценивается:
max max M r,i + r, где M r,i – мощность i-го ресурса в INr.
r =1, R i =1, N ( r ) Модель системы массового обслуживания операционного зала банка описана в диссертационной работе.
Оценка эффективности работы ГА на ВСП осуществлялась экспериментально, на примере конфигурирования ДО различной размерности со статической и динамической структурой, с помощью разработанного и зарегистрированного комплекса проблемно–ориентированных программ в сравнении с методом прямого перебора и методами направленного перебора (ветвей и границ, золотое сечение).
Полученные результаты приведены в диссертационной работе.
В таблице 1 представлено среднее время работы адаптированного генетического алгоритма при нахождении первой соответствующей параметрам конфигурации статического (способного преобразовывать один входной вектор в требуемый выходной) и динамического (способного преобразовывать несколько входных векторов в требуемые выходные вектора) триггерного устройства в сравнении с прямым перебором. Для случая динамической структуры задавались два входных и выходных вектора, обработка осуществляется с использованием слоя межкомпонентных связей «Шина».
Таблица Из приведенных данных видно, что преимущество предложенного ГА на ВСП над методом прямого перебора начинается с конфигурирования ДО размерностью 3Х3 в случае динамической структуры объекта и 4Х4 при статической структуре.
В процессе исследования метода была выполнена проверка влияния мощности начальной популяции на время поиска решения.
На рисунке 10 отображен график зависимости времени, требуемого для нахождения конфигурации триггерного устройства, от начальной популяции, конфигурация имела прямоугольный вид размерностью 3Х4 с перестраиваемой структурой, с использованием межкомпонентной шины в виде «вырожденных» сетей Петри с входным вектором 101010 и выходным вектором 011010.
2 с игурации, м Врем поиска конф 1 1 я 9 06 438 4 4 5 6 7 8 9 10 20 30 40 100 150 200 300 400 Количество генотипов в начальной популяции Рисунок 10. Среднее время поиска конфигурации в зависимости от размера начальной популяции, мс Качественный показатель представленного графика в зависимости от размерности ДО не изменялся.
Основные результаты и выводы При выполнении диссертационной работы были получены следующие результаты:
1. На основе проведенного анализа существующих математических моделей конфигурирования дискретных объектов был сделан вывод о необходимости создания имитационных моделей, учитывающих динамическое изменение связей в процессе функционирования объекта с заданным поведением на основе генетических алгоритмов и сетей Петри;
2. Реализована адаптация и формализация генетического алгоритма, с помощью вложенных сетей Петри для решения задачи конфигурирования ДО с заданным поведением;
3. Предложена математическая модель для формирования конфигурации ДО с фиксированной и перестраиваемой структурой;
4. Разработана архитектура информационной системы, основанной на полученных математических моделях;
5. Проведена оценка эффективности разработанных моделей на примере конкретных практических задач конфигурирования вычислительной техники с заданным поведением и формирования расписания занятий вуза на основе реализованных программных средств.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в научных изданиях, входящих в перечень рекомендованных ВАК 1. Петросов, Д.А. Адаптация генетического алгоритма при моделировании вычислительной техники с изменяющейся структурой и набором компонентов на основе Сетей Петри [Текст]/ Д.А. Петросов // Вопросы современной науки и практики. – Тамбов: Изд-во ТГТУ, 2009. – №6(20). – С. 54–63.
2. Петросов, Д.А. Математическое моделирование формирования конфигураций вычислительной техники с заданным поведением [Текст]/ Д.А. Петросов // Вопросы современной науки и практики. – Тамбов: Изд-во ТГТУ, 2009. – №7(21). – С. 113–121.
3. Петросов, Д.А. Математическая модель формирования конфигурации вычислительной техники на основе триггеров [Текст]/ Д.А. Петросов // Вестник ИжГТУ. – Ижевск: Изд-во ИжГТУ, 2009. – №3(43). – С. 139–143.
Статьи в научных журналах и сборниках трудов 4. Ельчанинов, Д.Б. Применение генетических алгоритмов при проектировании компьютерной техники [Текст]/ Д.Б Ельчанинов, Механа Сами, Д.А. Петросов // Вестник Херсонского государственного университета. – Херсон: Изд-во ХГУ, 2003. – № 2(18). – С. 146–148.
5. Лобода, В.Г. Концепция построения структур функционально ориентированных вычислительных устройств [Текст]/ В.Г. Лобода. Д.А. Петросов // АСУ и приборы автоматики. – Харьков: Изд-во ХНУРЭ, 2003. – №122. – С. 61–71.
6. Белова, Н.В. Концепция буферизации в вычислительных устройствах и системах. [Текст]/Н.В. Белова, Механа Сами Саади, Д.А Петросов // Радиоэлектроника и молодежь в XXI веке: сб. научных трудов 6 – го Международного молодежного форума. – Харьков: Изд-во ХНУРЭ, 2002. – Ч.2. – С.36–37.
Статьи в материалах и сборниках трудов научных конференций 7. Ельчанинов, Д.Б. Представление генетических алгоритмов сетями Петри в задачах проектирования компьютерной техники [Текст]/ Д.Б. Ельчанинов, В.Г.
Лобода, Д.А. Петросов // Информационные технологии – в науку и образование: сб.
материалов научно-практической конференции. – Харьков: Изд-во ХНУРЭ, 2005. – С.
48–51.
8. Белова, Н.В. Модель перепрограммируемого процессора с гибкой архитектурой [Текст]/ Н.В. Белова, Т.Г. Долженкова, Д.А. Петросов // Радиоэлектроника и молодежь в XXI веке: сб. материалов 8-го Международного молодежного форума. – Харьков: Изд-во ХНУРЭ, 2004. – Ч.2. – С. 277.
9. Белова, Н.В., Минимальное замкнутое покрытие двух классов цифровых автоматов [Текст]/ Н.В. Белова, Т.Г. Долженкова, Д.А. Петросов // Радиоэлектроника и молодежь XXI веке: сб. материалов 7-го Международного молодежного форума. – Харьков: Изд-во ХНУРЭ, 2003. – С. 468.
10. Петросов, Д.А. Интеллектуальная система поддержки принятия решений при формировании вычислительной техники с использованием генетических алгоритмом и L-сетей Петри [Электронный ресурс]/ Д.А. Петросов// сб. материалов Международной научно-практической конференции студентов, аспирантов и молодых ученных БГТУ им. В.Г. Шухова. – Белгород, 2009. 1 электрон. опт. диск (CD-ROM).
11. Петросов, Д.А. Математическая модель процесса формирования конфигурации вычислительной техники на основе триггеров с использованием генетических алгоритмов и сетей Петри [Текст]/ Д.А. Петросов// Проблемы управления, передачи и обработки информации (АТМ-ТКИ 50): сб. тр. Междунар. науч. конф. – Саратов: Изд во СГТУ, 2009. – С.344–347.
12. Иванов, И.В. Концепция работы межкомпонентной шины при конфигурировании дискретных объектов с заданным поведением [Текст]/ И.В.
Иванов, Д.А. Петросов // Проблемы сельскохозяйственного производства на современном этапе и пути их решения: сб. материалов XIV международной научно производственной конференции. – Белгород: Изд-во БелГСХА, 2010. – Ч.2. – С.23.
Официальная регистрация программ 13. Басавин, Д.А. Программа поиска конфигурации вычислительной техника/ Д.А.
Басавин, Д.А. Петросов// Свидетельство о государственной регистрации программы для ЭВМ 2009616324 ФГУ ФИПС – 2009.
14. Карамышев, Е.П. Программа составления расписания учебного процесса ВУЗа/ Е.П. Карамышев, Д.А. Петросов// Свидетельство о государственной регистрации программы для ЭВМ № 2010612452 ФГУ ФИПС – 2010.
Подписано в печать 02.07.10. Формат 60х84/ Усл. печ. л. 1,00 Тираж 100 экз. Заказ № Отпечатано в Белгородском государственном университете им. В.Г. Шухова 308012, г. Белгород, ул. Костюкова,