Том 15, № 5 (2014)

Рассматривается p-медианная задача оптимального размещения на графе (сети), являющаяся популярной моделью как в логистических задачах (оптимальное размещение транспортной, телекоммуникационной и иной инфраструктуры), так и опосредованно в задачах кластерного анализа, распознавания образов, в теории оценивания. Цель p-медианной задачи на графе (сети) заключается в нахождении определенного числа вершин (узлов) таких, чтобы суммарное расстояние от всех узлов сети до ближайшей из выбранных вершин (узлов) было минимальным. Для приближенного решения рассматриваемой неразрешимой (в общем случае) за полиномиальное время задачи предложен эвристический алгоритм, основанный на идеях метода изменяющихся вероятностей, являющегося методом случайного поиска с адаптацией. Идея алгоритма заключается в случайном выборе вершин в соответствии с заданными вероятностями выбора каждой из вершин и изменении этих вероятностей для каждой из выбранных вершин и вершин в некоторой ее окрестности в зависимости от достигнутого значения целевой функции (т. е. в зависимости от суммарного расстояния от каждой из вершин графа до ближайшей из выбранных вершин). При создании алгоритма для p-медианных задач с большой размерностью и вычислительной сложностью ставится задача оптимального использования вычислительных мощностей. Эффективность алгоритма подтверждена экспериментальной проверкой на тестовых примерах из библиотеки ORLIB. Также приведены результаты работы комбинированного алгоритма - комбинации предложенного алгоритма с процедурой локального поиска для решения данной задачи. Экспериментально показано, что результаты такой комбинации превосходят результаты оригинального многократных запусков алгоритма, реализующего локальный поиск из случайным образом выбранных вершин. Кроме того, в работе экспериментально показано, что для небольших задач алгоритм способен получить точное решение задачи.

Рассматриваются проблемы идентификации и управления стохастическими объектами с дискретнонепрерывным характером технологического процесса. Исследуется более общий класс динамических объектов, в дальнейшем - объекты с памятью. Характерной отличительной особенностью рассматриваемых процессов является тот факт, что при описании не используются разностные аналоги дифференциальных уравнений, принятые в классической теории идентификации и управления. Подобные процессы часто имеют место в различных контурах управления аэрокосмической техники, например, при виброиспытаниях космических аппаратов, в процессе их производства. В этом случае локальный канал «вибратор - космический аппарат (КА)», определяемый вибросигналом и соответствующим сигналом датчика, установленным на КА, может описываться разностными уравнениями. При этом естественно отсутствие аналогии между уравнением в непрерывном времени и разностным. Данная особенность является главным отличием объектов с памятью от традиционных динамических процессов. Это накладывает свой отпечаток при моделировании и управлении подобными объектами и обусловливает актуальность рассматриваемой задачи. Рассматриваются теорити- ческие сведения о непараметрических алгоритмах идентификации и управления. Непараметрические модели для объектов с памятью рассматриваются в двух вариантах. Один из них тесно связан с описанием объекта в виде интеграла Дюамеля. Второй путь состоит в частичной параметризации объекта, т. е. соответствует условиям как параметрической, так и непараметрической неопределенности. В основу построения непараметрических алгоритмов дуального управления положены принципы построения стохастических оптимальных систем А. А. Фельдбаума в их байесовской постановке. Состоят они в том, что управляющие устройство должно выполнять две функции: изучение и управление в процессе активного накопления информации. Рассматривается ситуация, когда на входе объекта «включается» управляющие устройство, соответствующие его обратной модели. Очевидно, что описание объекта не может быть по ряду причин точным, и обратный оператор может только приближенно описывать процесс в направлении «выход-вход». На этой основе выстраиваются как непараметрические модели объектов с памятью, так и непараметрические алгоритмы дуального управления. Тщательно анализируется процесс обучения системы дуального управления с активным накоплением информации. Подробно приводятся результаты численного исследования непараметрических моделей для многомерных процессов с памятью, а также результаты вычислительного эксперимента применения алгоритма непараметрического адаптивного дуального управления.

Рассматривается процесс разработки и применения мультиагентной системы для реконструкции текстуры фонового пространства изображения при удалении объектов. Рассматривается общая проблематика процедуры фото- и видеореконструкции, а также области ее применения. Проводится анализ существующих методов восстановления пропусков в больших массивах данных. Предлагается решение на основе одного из распространенных методов кластерного анализа - особой самоорганизующейся нейронной сети. Приводится поэтапный алгоритм обучения карт Кохонена: инициализация карты, выбор механизма отбора узлов, смещение смежных узлов в зависимости от функции соседства, определение меры обучения и переобучения сети, шаги грубой и тонкой подстройки. Разработан адаптированный алгоритм обучения и восстановления данных изображения на основе карт Кохонена. Введены механизм инициализации карты, структура обучающих векторов, методика выбора нейрона-победителя, функции соседства. Рассматривается принцип мультикартирования и применение кооперативного решения задачи на основе мультиагентного подхода. Расширен алгоритм мультиагентного решения на основе предварительной сегментации для определения смежных областей. Разработана архитектура мультиагентной системы, определено поведение отдельных агентов, спроектированы коммуникационные каналы для взаимодействия агентов. Реализована мультиагентная система восстановления текстуры на изображения. Представлены результаты экспериментов. Эксперименты были проведены на базе эталонных изображений для поиска объектов интереса (CBIR database). Приведены оценки эффективности выбранных параметров мультикартирования. Оценка оптимального количества карт при мультикартировании проведена на основе процента покрытия палитры исходного изображения. Представлены показатели точности и быстродействия агентного механизма для подсистем обучения и реконструкции, на основании которых можно сделать выводы об эффективности предлагаемой методики. Оценка точности проведена при помощи метрик SSIM, MSE, PSNR, а также при помощи методики попиксельного сравнения. Оценка быстродействия проведена для различных конфигураций мультиагентной системы с целью определения самой эффективной из них.

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

Рассмотрена задача идентификации нелинейных динамических систем класса Винера в условиях неполной информации. В настоящее время широко известны параметрические методы идентификации подобных систем, которые часто имеют дискретно-непрерывный характер. Обычно при параметрической постановке задачи идентификации класс уравнений, описывающий динамический процесс, известен с точностью до вектора параметров. Следующий этап - это оценка параметров по наблюдениям входных-выходных переменных процесса. При этом важно отметить, что выбор параметрической структуры модели исследуемого объекта оказывается чрезвычайно важным. Неточности модели, возникающие при некоторых погрешностях на стадии ее параметрического выбора или определения, не удается устранить при оценке параметров. А значит, модель будет в том или ином смысле, достаточно грубой. В настоящей статье линейный элемент модели Винера не известен с точностью до параметров, что соответствует уровню непараметрической неопределенности. В качестве нелинейного элемента модели принимается та или иная параметрическая структура. Конкретно рассматривается случай, когда параметрический блок представлен в виде квадратора и звена с насыщением. Таким образом, задача идентификации стохастических объектов класса Винера рассматривается в условиях частичной непараметрической неопределенности. На первом этапе строится модель линейного динамического блока. Для построения непараметрической модели последнего необходимо на вход объекта подать функцию Хевисайда, в этом случае выход объекта с точностью до коэффициента является его переходной функцией. Восстановление весовой функции осуществляется по наблюдениям переходной методами непараметрической статистики. Для оценки параметров нелинейного звена необходимо проведение соответствующих экспериментов. Следует обратить особое внимание на то, что при идентификации нелинейной динамической системы класса Винера контролю подлежат только входные и выходные переменные. Подобная ситуация типична при изготовлении не только космических аппаратов, но и многих их блоков и элементов. Кроме того, рассматриваемые модели оказываются полезными при создании компьютерных систем технической диагностики при виброиспытании космических аппаратов (КА) по каналу: «вибросигнал - сигнал датчика, установленный на КА». Проведено численное исследование предложенных алгоритмов, рассматривались модели систем класса Винера в различных условиях (при различном уровне помех в каналах измерения, различном объеме выборки и видах входных воздействий). Результаты компьютерных исследований показывают работоспособность предложенных алгоритмов.

Рассматриваются вопросы, связанные с построением и обучением деревьев принятия решения. Разбираются проблемы переобучения деревьев принятия решения и их способности к обобщению. Обсуждаются проблемы локальных поисковых процедур для настройки деревьев принятия решения. Предлагается эволюционный подход к автоматизированному формированию деревьев принятия решения на основе гибридизации алгоритма генетического программирования и генетического алгоритма. Алгоритм генетического программирования решает задачу структурного поиска в пространстве деревьев принятия решения. Объектом поиска для генетического программирования служит взаимное расположение функциональных узлов в дереве принятия решения (структура). Структура дерева выстраивается из элементов терминального и функционального множеств. В качестве элементов функционального множества выбираются возможные условия, которые ограничивают одну из входных переменных и разбивают исходную совокупность на группы. В качестве элементов терминального множества выбираются возможные решения, которые принимаются в рамках рассматриваемой задачи. Генетический алгоритм решает задачу параметрической оптимизации. Каждое условие в дереве имеет один или несколько числовых параметров. Эти параметры кодируются в бинарную строку и осуществляется поиск в направлении уменьшения ошибки дерева принятия решения на обучающей выборке. Приводится совместная схема работы генетического программирования и генетического алгоритма. Рассматриваются основные эволюционные операторы. Предложенный подход был реализован в виде программной системы, позволяющей получать бинарные деревья принятия решения с узлами, содержащими не более одного параметра. Приводятся рабочие окна программы. С помощью программной системы решена задача о диагностике степени тяжести повреждений органов брюшной полости при перитоните. Показано, что эволюционный алгоритм, построенный на основе гибридизации алгоритма генетического программирования и генетического алгоритма, позволяет получать деревья принятия решения с высоким свойством обобщения, использующие в 4 раза меньше информации в сравнении с теми данными, которые фиксируются при анамнезе пациента.

Изучение бесконечных групп с различными условиями конечности - актуальная задача в теории групп. Одним из таких условий является условие насыщенности группы заданным множеством групп. Группа G насыщена группами из множества M, если любая конечная подгруппа из G содержится в подгруппе, изоморфной некоторой группе из M. Известно, что произвольная периодическая группа, насыщенная группами из множества групп {(p n)}, где p и n не фиксируются, изоморфна L 2(Q), где Q - локальноконечное поле. Кроме того, этот результат удалось обобщить на случай, когда группа насыщена группами из множества групп j

Показать

Скрыть