Для авторов
Найти
Результаты поиска
Найдено результатов: 16.
-
ИСПОЛЬЗОВАНИЕ ИНВАРИАНТОВ НЕЧЕТКОГО ГРАФА ДЛЯ АНАЛИЗА УСТОЙЧИВОСТИ СЛОЖНЫХ ТРАНСПОРТНЫХ СИСТЕМ
И.Н. Розенберг , И.А. Дубчак136-1452025-12-30Аннотация ▼Рассматриваются вопросы оценки устойчивости транспортно-логистических систем (ТЛС) в условиях неопределенности, которые играют ключевую роль в обеспечении эффективного функционирования цепей поставок. Устойчивость систем анализируется в контексте их способности адаптироваться к внешним и внутренним воздействиям, таким как экономические колебания, изменение спроса, стихийные бедствия и технологические сбои. В данной статье предлагается использовать инварианты нечетких множеств, а именно нечеткое доминирующее множество, для оценки и анализа устойчивости транспортно-логистических систем в условиях неопределенности. Показано, что нечеткое доминирующее множество позволяет решать задачу размещения распределительных узлов в транспортно-логистической системе. Приведены примеры нахождения нечетких доминирующих множеств для нечетких и нечетких темпоральных графов как моделей транспортно-логистической системы. Нечеткие темпоральные графы также позволяют проводить более адекватное моделирование и анализ систем в случаях, когда параметр времени является одним из важных факторов. Практическая значимость исследования заключается в возможности проектирования более надежных и адаптивных ТЛС, способных эффективно функционировать в условиях неопределенности. Результаты могут быть использованы для оптимизации логистических процессов, снижения затрат и повышения устойчивости цепочек поставок. Полученные выводы также открывают перспективы для дальнейших исследований в области интеграции методов искусственного интеллекта и анализа больших данных в управлении транспортными системами. Дальнейшие исследования предлагается направить на интеграцию методов оптимизации потоков с учетом временных факторов и разработку цифровых двойников ТЛС
-
РАСПОЗНАВАНИЕ И АДАПТИВНАЯ ГЕНЕРАЦИЯ ПСЕВДОСЛУЧАЙНЫХ ТЕСТОВ ПОСЛЕДОВАТЕЛЬНОСТНЫХ ЦИФРОВЫХ УСТРОЙСТВ
Ю.Е. Зинченко , Т. А. Зинченко189-2042025-11-10Аннотация ▼Целью статьи является повышение эффективности псевдослучайного тестирования цифровых устройств по сравнению с общепринятым традиционным подходом. Для достижения поставленной цели в работе решаются следующие основные задачи: анализ эффективности традиционных подходов тестирования; разработка нового подхода тестирования на базе распознавания и адаптивного псевдослучайного тестирования цифровых устройств; разработка системы тестирования на базе разработанных подходов и экспериментальные исследования на ее основе.
В качестве объекта диагностики в данной работе выступают последовательностные (с элементами памяти) цифровые устройства, выполненные в виде типовых элементов замены на микросхемах средней и малой степени интеграции. В качестве моделей неисправностей при синтезе и анализе тестов используются константные неисправности. Предметом исследований выступают последовательностные цифровые устройства как объекты диагностики и подходы их псевдослучайного тестирования. В работе представляется подход распознавания и тестирования последовательностных цифровых устройств, который базируется на сочетании традиционного псевдослучайного тестирования на первом этапе с «распознаванием объекта диагностики» и построении «альтернативного графа объекта» на втором этапе с последующим «блужданием» по этому графу с целью повышения эффективности тестирования. На базе предложенного подхода разработана система тестирования цифровых устройств AGAT. Тестирование в системе может выполняться как для одного, так и группы объектов диагностики на одном либо группе персональных компьютеров в локальной компьютерной сети, при этом учитывается «многопоточность» на основе многоядерных процессоров персональных компьютеров сети. Выполняются экспериментальные исследования предложенного подхода и системы AGAT на двух типах объектов диагностики: международном наборе экспериментальных схем ISCAS’89 и наборе типовых элементов замены специализированной радиотехнической системы -
О ВЫЧИСЛЕНИИ СРЕДНЕГО ВРЕМЕНИ ИНФИЦИРОВАНИЯ В РАМКАХ ДИСКРЕТНОЙ МАРКОВСКОЙ ЭПИДЕМИОЛОГИЧЕСКОЙ МОДЕЛИ В ОТСУТСТВИИ ЛЕЧЕНИЯ
А.А. Магазев , А. Ю. Никифорова53-632025-11-10Аннотация ▼Моделирование распространения вирусов является актуальной областью исследований. Существует множество «непрерывных» эпидемических моделей, основанных на использовании систем дифференциальных уравнений. Недостатком таких моделей является то, что они имеют погрешность при описании начальной стадии распространения вируса и не учитывают особенности связей между индивидуумами. «Дискретные» модели, в которых время и количество инфицированных и восприимчивых узлов являются дискретными величинами, дают более точную картину эпидемического процесса. В этой работе мы изучаем некоторую дискретную марковскую модель в случае, когда лечение отсутствует. Это важный случай, поскольку его можно рассматривать либо как приближение к начальной фазе эпидемии, либо как модель эпидемий вирусов, которые трудно поддаются лечению. В первом разделе мы подробно описываем свойства исследуемой марковской модели. Во втором разделе, используя марковский подход, мы определяем среднее время заражения, то есть количество временных шагов, затраченных на заражение всех особей в популяции. Однако расчет среднего времени заражения в популяциях с большим количеством особей (или в сетях с большим количеством узлов) является сложной вычислительной задачей, поэтому в третьем разделе мы предлагаем соответствующую приближенную формулу для этого параметра при условии, что связность сети и вероятность распространения вируса малы. В четвертом разделе мы используем метод имитационного моделирования для расчета среднего времени заражения, а затем сравниваем результаты, полученные различными методами. Для проведения вычислительного эксперимента нами было разработано консольное приложение, написанное на языке программирования C++. Анализ значений среднего времени инфицирования, определенных тремя методами: методом точного вычисления фундаментальной матрицы M, вычислением с применением приближенной формулы и методом имитационного моделирования, показал, что методы хорошо согласуются между собой при заданных нами условиях. Полученная приближенная формула для среднего времени заражения является более простым в использовании вариантом расчета данного параметра.
-
РЕШЕНИЕ ОБРАТНОЙ ЗАДАЧИ СПЕКТРАЛЬНОЙ ТЕОРИИ ГРАФОВ ПРИ ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ
А.Н. Целых , В. С. Васильев , Л.А. Целых , С.А. Барковский163-1732025-10-01Аннотация ▼Статья посвящена решению основной обратной задачи спектральной теории графов – определении основных параметров графа по спектру его собственных значений. В данной работе нас интересуют когнитивные причинные графовые модели сложных систем, динамика переменных которых недоступна. Мы рассматриваем нестохастические графовые модели, которые имеют нечисловые значения узлов и связей, а также плохо определенные системные факторы. При отсутствии исходных данных решение обратной задачи для направленного взвешенного знакового графа становится значительно более сложным. Когда графы имеют одинаковую топологию, но разные веса на дугах, то их спектры образуют в пространстве решений некоторое множество нечетких коллинеарных векторов. Линии этих векторов расходятся в пространстве векторов из-за их направленности к разным вершинам. В данной работе предлагается использовать алгоритм, позволяющий точно восстановить веса когнитивного графа, когда известен условный главный собственный вектор и топологический шаблон матрицы смежности. Данный алгоритм учитывает важную особенность матрицы смежности графа – направление главного собственного вектора к целевой вершине, что позволяет найти правильное решение из набора нечетких коллинеарных векторов в пространстве решений. Для того, чтобы добиться полного восстановления весов графа с приемлемой точностью предлагается объединить спектр графа и модель эффективную управления с задачей комбинаторной оптимизации. Восстанавливая веса матрицы смежности с использованием нашего подхода, мы сравниваем их с заданным графом. При сравнении учитываются такие параметры графа, как спектр графа, коэффициенты подобия для реконструированной матрицы, векторы отклика и управления
-
УПРАВЛЕНИЕ В АВТОНОМНЫХ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМАХ С ПОМОЩЬЮ ОНТОЛОГИИ НАМЕРЕНИЙ
Н.А. Жукова , И. А. Куликов2025-01-30Аннотация ▼Статья посвящена описанию возможностей управления в автономных телекоммуникацион-
ных системах при помощи онтологий намерений. В современных телекоммуникационных сетях
наметились тенденции к децентрализации систем и наделению их компонентов возможностью
автономной работы, при этом на уровне системы определяется бизнес-логика их работы, кото-
рая во многих случаях требует взаимодействия между несколькими или многими компонентами
систем, выступающими в роли поставщиков или потребителей услуг. В статье рассматривают-
ся автономные сети, управляемые с использованием модели TMN (от англ. Telecommunication
Management Network – телекоммуникационная сеть управления), которая является многоуровне-
вой моделью, включающей уровни управления бизнесом, услугами, телекоммуникационной сетью и
ее компонентами. Для управления сетями в парадигме поставщиков и потребителей услуг между-
народной ассоциацией, объединяющей поставщиков сервисов и их потребителей в сфере телеком-
муникаций TMForum разработана концепция, основанная на использовании онтологий намерений
(Intent in Autonomous Networks), позволяющих формулировать задачи управления в автономных
сетях за счет определения критериев управления сетями и их элементами с точки зрения намере-
ний участников взаимодействия по получению и предоставлению сервисов. Ввиду того, что онто-
логия намерений описана в формате OWL, представляющим ее как семантическую сеть связанных
между собой классов, в статье предложено для управления телекоммуникационными сетями ис-
пользовать модель телекоммуникационной сети в форме графа знаний, который связан как с до-
менной онтологией телекоммуникационных сетей, так и с онтологией намерений, что позволяет
обеспечить автономность компонентов сети за счет управление при помощи намерений, а ис-
пользование доменной онтологии в области телекоммуникационных сетей облегчает интеграцию
со сторонними поставщиками и потребителями сервисов оператора. Предложенный подход со-
вместного использования онтологии намерений, политик и модели сети в форме графа знаний для
управления телекоммуникационными сетями на бизнес-уровне является новым и его примени-
мость показана в статье на примере реализации процесса регистрации и выполнения заявки на
подключение телекоммуникационного сервиса. Рассмотренный пример показывает возможность
совместного использования модели телекоммуникационной сети в форме графа знаний, построен-
ной на основе доменной онтологии и онтологии намерений при выполнении верхнеуровневых биз-
нес-процессов управления автономной телекоммуникационной сетью. -
БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ ИНВАРИАНТНЫХ ГРАФОВЫХ ЗАДАЧ
О.Б. Лебедев , А.А. Жиглатый2022-11-01Аннотация ▼Предлагается биоинспирированный метод решения набора инвариантных комбина-
торно-логических задач на графах: формирования паросочетания графа, выделения внут-
ренне-устойчивого множества вершин, выделения клики графа. Описывается модифициро-
ванная парадигма муравьиной колонии использующая, в отличие от канонического метода,
механизмы формирования решений на модели пространства поиска в виде звездного графа.
Задача формирования в графе внутренне-устойчивого множества вершин может быть
сформулирована, как задача разбиения. На начальном этапе на всех ребрах звездного графа
H откладывается одинаковое (небольшое) количество феромона ξ/m, где m=|E|. Процесс
поиска решений итерационный. Каждая итерация l включает три этапа. Агенты облада-
ют памятью. На каждом шаге t в памяти агента ak имеется количество феромона фj(t),
отложенного на каждом ребре графа H. На первом этапе каждый агент ak популяции
конструктивным алгоритмом находит решение Ur
0k, рассчитывает оценку решения
ξk(Ur
0k) и значение степени пригодности полученного агентом решения φk (количество фе-
ромона, соответствующее оценке). На втором этапе, после полного формирования всеми
агентами решений на текущей итерации, феромон ωj, накопленный в j-ой ячейке в буфер-
ном массиве КЭПб, добавляется в каждую j-ю ячейку основного массива Q2={qj|j=1,2,…,m}
коллективной эволюционной памяти КЭПo. На третьем этапе происходит общее испаре-
ние феромона на множестве ребер E звездного графа H. Временная сложность алгоритма,
полученная экспериментальным путем, совпадает с теоретическими исследованиями и для
рассмотренных тестовых задач составляет О(n2). -
МЕТОД И АЛГОРИТМ ПЛАНИРОВАНИЯ ОПЕРАЦИЙ НА ОСНОВЕ МОДЕЛИ НЕЧЕТКОГО КОНЕЧНОГО АВТОМАТА
М. В. Князева , А. В. Боженюк , И. Н. Розенберг2022-05-26Аннотация ▼Рассматривается задача планирования, как важная оптимизационная задача, стоя-
щая перед многими транспортными и роботизированными приложениями. Для решения
задач планирования подходы основаны на методах оптимизации, методах выборки и дис-
кретизации (sampling-based methods), и обычно такого рода задачи являются NP-
трудными и многомерными. В данной статье разработан метод планирования и состав-
ления расписаний на основе нечеткой модели конечного автомата. Дано нечеткое графо-
вое представление задачи составления расписания и планирования операций. В работе при-
ведены два подхода к формальной постановке задачи планирования с ограниченными ресур-
сами и временными переменными: ориентированный на состояния (с переходами между
состояниями), ориентированный на темпоральное упорядочивание (на временной шкале).
Темпоральное моделирование для задач планирования подразумевает качественный подход
к управлению распределением операций или топологическим упорядочением, а также коли-
чественный подход к обработке неточных длительностей, взаимосвязей между операция-
ми по многочисленным параметрам. Введены понятия нечетких интервалов и нечетких
отношений для планирования операций на графе. Разработан алгоритм планирования, ос-
нованный на основе теории автоматов и темпоральном моделировании в условиях неопре-
деленности. Используя формализм теории автоматов, проблема планирования и нахожде-
ния оптимальных путей решается путем последовательного изменения и анализа состоя-
ний планируемой системы с использованием различных операций, пока не будет найдено
решение. В работе обсуждается идея упорядоченного во времени частичного расписания,
связанного с каждым состоянием планируемой системы. Предложена модель конечного
автомата для системы планирования в условиях неопределенности. Разработан метод и
алгоритм планирования операций на основе недетерминированного конечного автомата и
схемы перечислений. Недетерминированные вычисления для задачи планирования пред-
ставляют собой дерево решения, корень которого соответствует началу процесса плани-
рования, а каждая точка ветвления в дереве соответствует точке вычисления, в которой
у машины есть несколько вариантов выбора. -
ПРЕОБРАЗОВАНИЕ ПОСЛЕДОВАТЕЛЬНОГО ИНФОРМАЦИОННОГО ГРАФА МЕТОДА ПРОГОНКИ В ПАРАЛЛЕЛЬНУЮ ФОРМУ
Д. В. Михайлов177-1882021-10-05Аннотация ▼Множество вычислительных задач может быть представлено в виде последова-тельного информационного графа. В общем случае такой информационный граф не может быть приведён к параллельному виду с целью ускорения выполнения его операций. Но в слу-чае если вершины этого графа обладают свойствами ассоциативности, дистрибутивно-сти и т.д., такой граф можно преобразовать в параллельно-конвейерную форму. Эти пре-образования могут быть произведены не только над графами, содержащими элементар-ные операции – сложение, умножение, логическое И и т.д. – но и над графами, содержа-щими макрооперации. Одним из примеров таких графов является информационный граф решения СЛАУ методом прогонки (методом Томаса). В статье рассмотрено решение для трёхдиагональных СЛАУ. Информационный граф метода прогонки состоит из двух час-тей: прямого хода, в котором выполняется переход от трёхдиагональной формы к двух-диагональной, и обратного хода, в котором непосредственно вычисляются значения неиз-вестных. Несмотря на то, что операции, составляющие базовую макрооперацию метода прогонки, обладают свойством ассоциативности, простое преобразование графа к пира-мидальному виду не даст необходимого результата. Необходимо преобразовать базовые макрооперации особым образом и изменить то, какие данные на них поступают. После этого возможно будет привести граф к пирамидальному виду. Для обратного хода приме-няется аналогичное преобразование графа и составляющих его базовых подграфов. По-скольку для того, чтобы начать вычисления в обратном ходе, нам необходимо полное за-вершение вычислений прямого хода, следует перейти от двух специализированных типов вычислительных блоков к одному универсальному, и построить на его основе универсаль-ную вычислительную структуру.
-
АЛГОРИТМ РЕКОНСТРУКЦИИ МАТРИЦЫ СМЕЖНОСТИ ПРИЧИННЫХ ГРАФОВЫХ МОДЕЛЕЙ В ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ
А. Н. Целых, В.С. Васильев , Л. А. Целых2021-11-14Аннотация ▼Рассматривается проблема моделирования сложных систем при отсутствии на-
блюдаемых переменных. Для решения этой проблемы предлагается использовать причин-
ные графовые модели. Класс причинных моделей, который мы здесь рассматриваем, опре-
деляется как нестохастические причинные модели с ненаблюдаемыми переменными. Эти
модели представляются в виде направленного графа, создаваемого на основе человеческих
ментальных репрезентациях. При этом на дугах причинность выражена в виде некоторых
меток, которые имеют знак, определяющий направление изменений состояния системы.
Рассматриваемые причинные модели включают неоднородные, сложные и качественныетипы переменных, иллюстрирующие нечисловую природу узлов и связей, а, следовательно,
отсутствие и невозможность получения временных рядов данных. В условиях отсутствия
наблюдаемых переменных и невозможности проведения экспериментов, проблема рекон-
струкции матрицы смежности графовой причинной модели становится гораздо более
сложной. Требуется получить модель с определенным спектральным разложением, которое
реализует основную функцию моделируемой системы. На основе этой концепции предлагает-
ся новый метод реконструкции матрицы смежности, реализованный на соответствующей
матрице причинного распространения или передаточной матрице. Идея состоит в том,
чтобы использовать комбинаторную оптимизацию на основе спектральной теории графов
для генерации данных из качественной нестохастической причинной модели и реконструиро-
вать матрицу смежности, используя эти данные. В этом случае собственные векторы
идентифицируются как ключевые цели процесса реконструкции матрицы, что постулирует
фундаментальный подход, основанный на спектральных свойствах графа. Результаты вы-
числительных экспериментов решения задачи реконструкции матрицы смежности для при-
чинных графовых моделей в отсутствии наблюдаемых переменных с использованием разра-
ботанного алгоритма показали, что алгоритм эффективно реконструирует матрицы в за-
данных параметрах с допустимыми показателями схожести. Доказана сходимость при-
ближения к решению алгоритма реконструкции матриц не медленнее, чем со скоростью
геометрической прогрессии. С технической точки зрения, преимуществом алгоритма явля-
ется реализация инструмента автоматической настройки параметра регуляризации, при-
годного для пользователей без предварительных математических знаний. -
АЛГОРИТМ ЭФФЕКТИВНЫХ УПРАВЛЕНИЙ В НЕСТОХАСТИЧЕСКИХ ПРИЧИННЫХ МОДЕЛЯХ В ОТСУТСТВИИ НАБЛЮДАЕМЫХ ПЕРЕМЕННЫХ ДЛЯ СИСТЕМ ПРИНЯТИЯ УПРАВЛЕНЧЕСКИХ РЕШЕНИЙ
А. Н. Целых , В. С. Васильев , Л.А. Целых2021-11-14Аннотация ▼Рассматривается проблема репликации процесса принятия человеком управленческих
решений в условиях неопределенности и неполноты исходных данных. Лицо, принимающее
решение, опирается на свою систему взглядов, в которую входит общее видение системы,
относительно которой принимается решение. Система представлена в виде причинной
модели, созданной на основе ментальных представлений человека. Эти модели представ-
ляют собой направленные графы, на дугах которых причинность выражена в виде меток,
которые имеют знак, определяющий направление изменений состояния системы. Вершины
этого направленного графа представляют собой концепты высокого уровня абстракции.
Такой граф моелирует функционирование реальной системы. Таким образом, мы исследуем
проблему предсказания и управления действиями человека на основе нестохастических
причинных моделей в отсутствие наблюдаемых переменных для использования в системах
поддержки принятия решений и экспертных системах. Принятие решений рассматрива-
ется с точки зрения выбора объектов приложения управленческих воздействий – факторов
модели. В настоящем исследовании мы показываем, что применение предложенного алго-
ритма может облегчить принятие решений относительно выбора управляющих воздейст-
вий, которые поддерживают достижение тактических и стратегических целей лица, при-
нимающего решения. Следует отметить, что алгоритм реализует автоматизированный
подбор параметра регуляризации, что делает доступным разработку и применение предложенного алгоритма для пользователей, не имеющих достаточной математической под-
готовки. Сходимость последовательности множителя Лагранжа алгоритма эффектив-
ных управлений доказана. Доказана теорема о резонансе в нестохастической причинной
модели, представленной направленным графом, который определяется областью допус-
тимых значений коэффициента демпфирования в модели управления. Ожидается, что
внедрение этого инструмента в системы поддержки принятия решений повысит надеж-
ность решений, принимаемых в отношении работы системы в целом. Выбор управляющих
воздействий с использованием предложенного алгоритма имеет высокую эффективность
и производительность. Таким образом, результаты, представленные в исследовании, мо-
гут быть полезны для разработки приложений в интеллектуальных системах -
ИССЛЕДОВАНИЕ СТРУКТУРНЫХ ХАРАКТЕРИСТИК РАСПРЕДЕЛЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ ГРАФОВ С МНОЖЕСТВЕННЫМИ РАЗНОТИПНЫМИ СВЯЗЯМИ
Е.Р. Мунтян , Э.В. Мельник2021-08-11Аннотация ▼В статье рассмотрены вопросы построения отказоустойчивых вычислительных
систем, в части структуры и резервирования. При проектировании распределенных вычис-
лительных систем (ВС) возникает необходимость учета большого количества факторов,
влияющих на производительность, надежность и отказоустойчивость. Для распределен-
ных ВС к таким факторам относятся, в том числе структурные характеристики. В ра-
боте представлены графики зависимости вероятности безотказной работы ПУ распреде-
ленной вычислительной системы от характеристик ее структуры. Применение перспек-
тивных способов резервирования, таких как резервирование производительности, сущест-
венно повышает сложность задачи проектирования структуры. При резервировании про-
изводительности взамен ввода в систему специальных резервных узлов предполагается
использование избыточных вычислительных ресурсов внутри задействованных процессор-
ных узлов (ПУ). В случае отказа узла его задачи перераспределяются на свободный резерв
работоспособных узлов. Для реализации такого способа резервирования системы требует-
ся организация многопрограммного режима работы, когда на каждом узле могут одно-
временно выполняться несколько задач. Необходимость обеспечения мультипрограммного
режима работы приводит к увеличению количества конфигураций системы, подлежащих
анализу на этапе проектирования и в случае реконфигурации при отказе. Для снижения
трудоемкости анализа отдельно взятой конфигурации предложен подход на основе графов
с множественными и разнотипными связями. Использование моделей на основе таких гра-
фов позволяет представить структуру вычислительной системы с учетом мультипро-
граммной обработки информации и при этом существенно сократить время вычисления
базовых характеристик за счет применения связей в виде вектора, позволяющих объеди-
нить несколько разнотипных связей. -
МЕТОД РЕШЕНИЯ ГРАФОВЫХ NP-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ ПРИНЦИПА РАСПАРАЛЛЕЛИВАНИЯ ПО ИТЕРАЦИЯМ
А. В. Касаркин2021-02-25Аннотация ▼При решении графовых NP-полных задач на многопроцессорных системах рост обо-
рудования не приводит к пропорциональному росту производительности системы, поэто-
му не всегда удается решить задачу за приемлемое время. Целью работы, описанной в
статье, является минимизация времени решения задачи поиска максимальных клик графа с
использованием реконфигурируемых вычислительных систем (РВС). При решении задачи
на РВС методом распараллеливания по слоям рост производительности также замедля-
ется, несмотря на лучшую степень масштабируемости по сравнению с многопроцессор-
ными реализациями. В статье предложен метод создания параллельно-конвейерных про-
грамм для реконфигурируемых вычислительных систем на основе распараллеливания по
итерациям для решения графовых NP-полных задач. Рассмотрено, что использовать би-
товый способ представления множеств (как в методе распараллеливания по слоям) для
метода распараллеливания по итерациям не является эффективным. Новый метод отли-
чается организацией вычислений, а именно – обработкой неупорядоченных множеств,
доступ к элементам которых осуществляется не по адресам (как в массивах), а по значе-
ниям (именам вершин и именам дуг графа). Показано, что новый метод на основе распа-
раллеливания по итерациям, несмотря на более низкую удельную производительность, свя-
занную с тем, что вычислительным подструктурам из-за символьного представления
множеств необходимо обработать большее число промежуточных данных, обеспечивает
практически линейный рост реальной производительности РВС при значительно большем
количестве вычислительного ресурса по сравнению с методом распараллеливания по слоям. -
СЕМАНТИКО-СТАТИСТИЧЕСКИЙ АЛГОРИТМ ОПРЕДЕЛЕНИЯ КАТЕГОРИЙ АСПЕКТОВ В ЗАДАЧАХ СЕНТИМЕНТ-АНАЛИЗА
А.О. Корней, Е.Н. Крючкова2021-02-13Аннотация ▼В современном мире одним из ключевых каналов коммуникации является Интернет.
Через электронные площадки осуществляется торговля, продвижение услуг. Социальные
сети и мессенджеры становятся важнейшим каналом общения и мощным инструментом
воздействия на общественное мнение. Весомую долю во всем публикуемом контенте зани-
мают тексты, написанные на естественном языке. Поэтому проблемы обработки и по-
нимания естественных языков (ЕЯ) на сегодняшний день являются одними из ключевых.
Под влиянием коммерческих интересов активно развивается область автоматического
анализа тональности на основе аспектов. Данная задача существенно зависит от кон-
кретных предметных областей, и поэтому вопрос быстрой и эффективной адаптации
существующих моделей к новым доменам стоит весьма остро. В работе предлагается
гибридный метод аспектно-ориентированного анализа тональности текстов, основанный
на данных, извлеченных как из общеупотребительных словарей, так и из домен-
ориентированных текстов. Предложен метод построения конденсированного семантиче-
ского графа на основе неструктурированных домен-зависимых текстов. Введены числен-
ные метрики, позволяющие оценивать значимость отдельных терминов в пределе всего
домена. Предложен алгоритм категоризации текстов, основанный на выделении семанти-
ческих кластеров в пределах конденсированного домен-специфического графа. Предложен
метод оценки тональности домен-ориентированных текстов, основанный на статисти-
ческих данных, включая совместное использования тонального словаря и сконденсирован-
ного домен-специализированного графа. Приведены результаты экспериментов, позволяю-
щие оценить качество работы алгоритмов. -
ПРИМЕНЕНИЕ ЗАПРЕЩЕННЫХ ФИГУР В ЗАДАЧЕ РАСКРАСКИ ГРАФА ПРИ ПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ
В. И. Потапов2021-01-19Аннотация ▼Проектирование конструкции печатных плат в виде плоских структур без перемы-
чек является одной из самых сложных задач на этапе схемотехнического проектирования.
Задача в такой постановке особенно актуальна микросборок и для электронных модулей
контрольно-проверочной, бортовой аппаратуры, выполненных по технологии поверхност-
ного монтажа, где, например, по причине металлического теплоотвода или керамического
основания, структура соединений возможна только в одном слое. В работе рассматрива-
ется задача проектирования печатных плат в виде синтеза плоских структур электрон-
ных схем. Целью является расположение соединений на печатной плате без пересечений,
что облегчает условия проведения трасс любому трассировщику современных программ
проектировании. Для её решения предложено большое число различных алгоритмов, основ-
ным недостатком которых является заложенный в них принцип последовательного и
фрагментарного просмотра коммутационного пространства. Сложность алгоритмов
синтеза подобных структур обусловлена также необходимостью учета большого числа
различных требований, связанных со спецификой их изготовления и особенностями разра-
батываемого конструктивно-технологического решения. В настоящей работе предлага-
ется выполнить проектирование печатной платы с высокой эффективностью трассиров-
ки соединений за счет решения задачи расслоения исходного графа-схемы и построения
плоского графа-схемы как на стороне установки ЭРЭ, так и на обратной стороне платы -
стороне пайки, исключая запрещенные фигуры по теореме Потрягина-Куратовского.
Критерием является минимизация переходных отверстий, а также минимизация провод-
ников (ребер) на одной стороне печатной платы. Задача расслоения представляет собой
задачу раскраски графа в два цвета с использованием принципов характеризационного
управления, решение которой базируется на теореме Кенига, определяющей запрещенную
фигуру в виде циклов нечетной длины. Для проектирования печатных плат разработаны
алгоритм и методика построения планарных графов и расслоения графа на две стороны
печатной платы с уменьшением количества неразведенных ребер. Точное решение прини-
мает вид полиномиальной зависимости не выше 5-й степени, позволяет получить резуль-
тат за приемлемое время и повысить эффективность трассировки на 5–15 %. -
ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗБИЕНИЯ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ
Б.К. Лебедев, О. Б. Лебедев, Е. О. Лебедева2020-07-20Аннотация ▼Работа алгоритма разбиения базируется на использовании коллективной эволюцион-
ной памяти, под которой подразумевается информация, отражающая историю поиска
решения и хранится независимо от индивидуумов. Алгоритм, связанный с эволюционной
памятью, стремится к запоминанию и многократному использованию способов достиже-
ния лучших результатов. Коллективная эволюционная память алгоритма разбиения со-
стоит из некоторого количества статистических индикаторов, отображающих для ка-
ждого выполненного варианта число θ его вхождений в состав лучших решений на выпол-
ненных генерациях алгоритма и число, δ определяющее насколько полезна реализованная
альтернатива при формировании результатов на прошлых генерациях алгоритма. Коллек-
тив не имеет централизованного управления, и в связи с этим используется непрямой об-
мен информацией. Непрямой обмен состоит в выполнении неких действий, в различное
время, при которых происходит изменение некоторых частей эволюционной памяти одним
агентом. В дальнейшем происходит использование этой измененной информации другими
агентами, в этих частях. Вначале на каждой итерации конструктивным алгоритмом
формируется nk решений Qk,. Каждое решение Qk является отображением Fk=V→X, пред-
ставляется в виде двудольного подграфа Dk и формируется путем последовательного на-
значения элементов в узлы. Формирование каждого решения Qk выполняется множеством
агентов A, посредством вероятностного выбора каждым агентом ai узла vj. Процесс на-
значения элемента в узел включает две стадии. На первой стадии выбирается агент ai, а
на второй стадии − узел vj. При этом должно выполняться ограничение: каждому агенту
множества A соответствует один единственный узел множества V. Рассчитывается
оценка ξk решения Qk и оценка полезности δk множества альтернатив, реализованных
агентами в решении Qk. На втором этапе агенты увеличивают в интегральной россыпи
альтернатив R* интегральную полезность множества альтернатив на величину δk..
На третьем этапе осуществляется снижение оценок полезности δk интегральной россыпи
альтернатив на величину μ. В работе используется циклический метод формирования ре-
шений. В этом случае наращивание оценок интегральной полезности δk множества пози-
ций P выполняется после полного формирования множества решений Q на итерации l.
Экспериментальные исследования проводились на основе сформированных тестовых при-
меров с полученным ранее оптимальным решением. Полученные результаты сравнивались
с результатами полученными другими известными алгоритмами разбиения схем на части.
Для сравнения был сформирован набор стандартных бенчмарок. Проанализировав получен-
ные результаты, можно сделать вывод, что предложенный метод позволяет получать на
4–5 % решения качественнее, чем его аналоги. -
ПРОБЛЕМА ВЫБОРА ДЕМПИНГ-ФАКТОРА В МОДЕЛИ ЭФФЕКТИВНЫХ УПРАВЛЕНИЙ ДЛЯ НАПРАВЛЕННЫХ ВЗВЕШЕННЫХ ЗНАКОВЫХ ГРАФОВ
А.Н. Целых, В. С. Васильев, Л. А. Целых2020-07-20Аннотация ▼Рассматривается проблема выбора демпинг-фактора в модели эффективных управ-
лений на основе максимизации передачи влияний для нечетких когнитивных моделей, пред-
ставленных направленными взвешенными знаковыми графами. Для передачи влияния ис-
пользуется модель управления, реализующая развитие системы. Алгоритм эффективных
управлений основан на решении оптимизационной задачи отыскания вектора внешних воз-
действий, максимизирующего накопленный рост приращений показателей вершин. Опти-
мальным управляющим воздействием признаётся управление, доставляющее максимум
отношению квадрата нормы вектора отклика системы к квадрату нормы вектора управ-
ления. Демпинг-фактор такой модели управляет сравнительным масштабом прямого и
косвенного влияния всех внутрифакторных связей системы в целом. Целью исследования
является определение таких областей допустимых значений для получаемых решений, при
которых (i) соблюдается условие непротиворечивости результата; (ii) изменение рангов
вершин носит медленный характер. Под непротиворечивостью результата мы понимаем
удовлетворение правилами работы системы в целом. Эти правила могут выражаться в
наложении ограничений на статус вершин, на знак воздействий и откликов. В работе ус-
танавливается значение демпинг-фактора, называемое резонансным, при котором проис-
ходит резонансный всплеск значения целевой функции задачи максимизации влияния, когдасонаправленность между резонансным откликом и вызывающим его воздействием отсут-
ствует. Выбор демпинг-фактора влияет на значение целевой функции задачи максимиза-
ции влияния и на вектор эффективного управления, на котором это решение достигается.
Значение резонансного демпинг-фактора можно интерпретировать как предел возможной
управляемости системы, т.е. предел потенциальной возможности воздействия на систе-
му без причинения ей вреда. Оценка предложенного решения производится по степени ус-
тойчивости ранга узлов модели в зависимости от влияния изменений демпинг-фактора,
алгоритмизации определения области его допустимых значений и форме проявления резо-
нанса в границах значений демпинг-фактора.
1 - 16 из 16 результатов
