Для авторов
Найти
Результаты поиска
Найдено результатов: 3.
-
ЭВОЛЮЦИОННЫЙ АЛГОРИТМ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ДИСПЕТЧЕРИЗАЦИИ
В.В. Курейчик , А.Э. Саак , Вл.Вл. Курейчик2021-07-18Аннотация ▼Рассмотрена одна из важных задач оптимизации – задача диспетчеризации. Она от-
носится к классу NP- сложных оптимизационных задач. В работе приведена и описана
постановка задачи диспетчеризации. Здесь массив заявок пользователей на компьютерноеобслуживание в Grid- системах моделируется протяжённой линейной полиэдралью коор-
динатных ресурсных прямоугольников. При этом диспетчирование представляется лока-
лизацией линейной полиэдрали в оболочку области вычислительно-временных ресурсов сис-
темы согласно многоцелевому критерию качества применяемого назначения заявок на об-
служивание. В связи со сложностью данной задачи для ее эффективного решения предла-
гаются методы эволюционного моделирования. В статье предложена и описана модифи-
цированная архитектура эволюционного поиска. В качестве модификации введены допол-
нительно три блока. Это блок «внешней среды», блок эволюционной адаптации и блок «не-
перспективных решений». Для ее реализации авторами разработан модифицированный
эволюционный алгоритм, использующий в качестве отбора решений модели эволюций Ч.
Дарвина и Ж. Б. Ламарка. Это позволяет значительно сократить время получения резуль-
тата, частично решить проблему преждевременной сходимости алгоритма и получать
наборы квазиоптимальных решений за полиномиальное время. Разработан программный
модуль на языке C#. Проведен вычислительный эксперимент на тестовых примерах. Про-
веденные экспериментальные исследования, показали, что качество решений, полученных
на основе разработанного эволюционного алгоритма, в среднем на 5 процентов превосхо-
дит результаты решений, полученные с использованием известных алгоритмов последова-
тельного, начально-кольцевого и уровневого при сопоставимом времени, что говорит об
эффективности предложенного подхода. -
ПРОГРАММНАЯ ПОДСИСТЕМА ДЛЯ РЕШЕНИЯ NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ
В.В. Курейчик , Вл. Вл. Курейчик2021-07-18Аннотация ▼Работа посвящена созданию программной подсистемы для решения NP- трудных и
NP-сложных комбинаторно-логических задач на графах. В статье приведено описание
комбинаторно-логических задач на графах. Для эффективного их решения предлагаются
новые многоуровневые архитектуры поиска, такие как простая комбинированная, парал-
лельная комбинированная, двухуровневая, интегрированная и гибридная. Данные архитек-
туры основаны на методах, инспирированных природными системами. Ключевым отличием данных архитектур является разделение поиска на два или три уровня и применение на
них различных алгоритмов эволюционного моделирования и биоинспирированного поиска.
Это позволяет получать наборы квазиоптимальных решений выполнять параллельную
обработку и частично устранять проблему преждевременной сходимости. В статье при-
ведено подробное описание разработанной программной подсистемы и ее модулей. В каче-
стве модулей в подсистеме имеется пять разработанных архитектур и набор разрабо-
танных алгоритмов эволюционного моделирования и биоинспирированного поиска, таких
как эволюционный, генетический, пчелиный, муравьиный, светлячковый и обезьяний. Благо-
даря модульной структуре в подсистеме имеется возможность конструировать более 50
различных вариантов комбинаций поиска. Это позволяет использовать все достоинства
методов биоинспирированной оптимизации для эффективного решения NP-сложных ком-
бинаторно-логических задач на графах. Для подтверждения эффективности разработан-
ной программной подсистемы был проведен вычислительный эксперимент на тестовых
примерах. Проведенные серии тестов и экспериментов показали преимущество использо-
вания программного продукта для решения комбинаторно-логических задач на графах
большой размерности, по сравнению с известными алгоритмами, что говорит о перспек-
тивности применения такого подхода. Временная сложность разработанных алгоритмов
в лучшем случае O(nlogn), в худшем случае – О(n3). -
РАЗРАБОТКА АГЕНТНО-ОРИЕНТИРОВАННОГО АЛГОРИТМА РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ БОЛЬШОЙ РАЗМЕРНОСТИ
Д.А. Береза , Л. А. Гладков , Н. В. Гладкова2025-01-30Аннотация ▼Решение систем линейных алгебраических уравнений (СЛАУ) является одной из важнейших
фундаментальных задач при разработке нового поколения систем проектирования в различных об-
ластях науки и техники. Актуальность данного исследования обусловлена ростом объема данных и
усложнением задач. Традиционные методы решения СЛАУ, такие как метод Гаусса, метод прогон-
ки, итерационные методы (метод Якоби, метод Зейделя и т.д.), хорошо зарекомендовали себя при
работе с относительно небольшими системами. Однако при решении СЛАУ большой размерности
данные методы недостаточно эффективны из-за высоких вычислительных затрат и требований к
памяти. Одним из перспективных подходов к решению задач высокой сложности является использо-
вание агентно-ориентированных систем. Агентно-ориентированные системы предлагают новый
способ организации вычислительных процессов, основанный на взаимодействии независимых аген-
тов, каждый из которых выполняет определенную часть задачи. Такой подход позволяет более гиб-
ко распределять вычислительные ресурсы и эффективно решать сложные задачи в условиях боль-
ших данных. Представлена методика решения уравнений, описывающих математическую модель
схемы, с учетом оптимизации соотношения между точностью расчетов и временем их выполнения.
В данной работе предлагается агентно-ориентированный алгоритм для решения систем линейных
алгебраических уравнений большой размерности. В ходе разработки данного алгоритма был прове-
ден анализ существующих методов и алгоритмов решения СЛАУ, выявлены их преимущества и не-
достатки. Была разработана агентно-ориентированная архитектуру для решения СЛАУ большой
размерности, предложена организация взаимодействия агентов и механизмы распределения задач
между ними. Была выполнена программная реализация разработанного алгоритма. Для оценки эф-
фективности предложенного подхода было проведено его тестирование на ряде тестовых задач.
Также была выполнена оценка производительности и масштабируемости разработанного алго-
ритма, сравнение его с традиционными методами решения СЛАУ.
1 - 3 из 3 результатов
