Для авторов
Найти
Результаты поиска
Найдено результатов: 9.
-
МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРЕХМЕРНОЙ УПАКОВКИ БОЛЬШОЙ РАЗМЕРНОСТИ
В. В. Курейчик, А. Е. Глущенко2020-07-20Аннотация ▼Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер-
ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных
и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех-
мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра-
ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю-
чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под-
задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор
объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под-
хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на
эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время
получения результата, частично решить проблему предварительной сходимости алгоритмов
и получить наборы квазиотимальных решений за полиномиальное время. Разработан про-
граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной
упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли-
тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен-
ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред-
нем на 5 % превосходит результаты упаковки, полученные с использованием известных
алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности
предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить
теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре-
менная сложность алгоритмов O(n2), в худшем случае – O(n3). -
ИНТЕЛЛЕКТУАЛЬНЫЕ МЕТОДЫ ПАРАМЕТРИЧЕСКОГО ПРОГНОЗИРОВАНИЯ И ОПТИМИЗАЦИИ ТРАЕКТОРИИ ДВИЖЕНИЯ БАС
В.И. Данильченко , В.В. Бова263-2762025-12-30Аннотация ▼Рассматривается задача интеллектуального параметрического прогнозирования и оптимизации траектории движения беспилотной авиационной системы (БАС) с применением эволюционных алгоритмов и методов машинного обучения. Актуальность исследования обусловлена многокритериальностью и высокой сложностью процессов формирования траектории движения БАС, а также необходимостью точной и своевременной оценки её полётных параметров. Это особенно важно для обеспечения надёжности, безопасности и эффективного выполнения полётных задач в условиях эксплуатации БАС, включая сценарии, связанные с функционированием критически значимых объектов инфраструктуры. Цель исследования заключается в повышении точности диагностики траекторных параметров и надёжности параметрического прогнозирования траекторий движения БАС в условиях неопределённости и многокритериальности рассматриваемой задачи. В работе предлагается гибридный подход, включающий генетический алгоритм (ГA), алгоритм роя частиц (PSO) с моделью машинного обучения XGBoost, обеспечивающей адаптивную оценку качества формируемых решений. Реализован вычислительный программный комплекс, включающий механизмы селекции, рекомбинации, мутации и элитного наследования, а также модуль машинного обучения для валидации траектории маршрута и связанных параметров. Проведён вычислительный эксперимент, в рамках которого выполнен сравнительный анализ эффективности GA и PSO при различных сценариях их работы. Тестирование выполнялось на отраслевых наборах данных при различном количестве итераций. В ходе вычислительного эксперимента выявлено преимущество генетического алгоритма, а именно повышение качества проектных решений на 14–17%. Результаты исследования демонстрируют высокую адаптивность и практическую применимость в задачах моделирования, параметрического прогнозирования и маршрутизации, а также указывают на потенциал интеграции с интеллектуальными системами навигации и мониторинга БАС. Материалы статьи представляют практический интерес для специалистов в области разработки и эксплуатации БАС, а также для исследователей, занимающихся задачами многокритериального планирования маршрутов, параметрического прогнозирования и повышения надёжности функционирования БАС.
-
ПОДХОД К КОДИРОВАНИЮ РЕШЕНИЙ В ЭВОЛЮЦИОННЫХ МЕТОДАХ ДЛЯ СОЗДАНИЯ ИНСТРУМЕНТАЛЬНОЙ ПЛАТФОРМЫ ПРОЕКТИРОВАНИЯ
Э. В. Кулиев, А. А. Лежебоков, М. М. Семенова, В.А. Семенов2020-07-20Аннотация ▼Рассмотрены актуальные вопросы и проведен анализ проблемы трехмерной инте-
грации и трехмерного моделирования, возникающей на этапе конструкторского проекти-
рования в ходе решения задачи оптимального планирования компонентов больших и сверх-
больших интегральных схем и корпусных устройств электронной вычислительной аппара-
туры. Представлены и достаточно детально описаны основные преимущества примене-
ния принципов трехмерной интеграции, позволяющие эффективно организовывать произ-
водство персонифицированной электроники, оптимально планировать конфигурацию
больших и сверхбольших интегральных схем с учетом тепловых и энергетических характе-
ристик. В ходе выполнения исследований авторами разработан подход к кодированию ре-
шений на основе интеллектуального механизма, который характеризуется наличием
встроенных средств контроля допустимых решений. Одним из таких средств, экспери-
ментально доказавших свою эффективность, является встроенный механизм «смертель-
ных мутаций», учитывающий статусы генов и заранее заданные ограничения на итоговую
конфигурацию корпуса проектируемого устройства. В работе предложен ряд общих под-
ходов и конкретных алгоритмов решения задачи планирования, основывающихся на ре-
зультатах исследований авторского коллектива и современных подходах к решению
NP-полных задач. Важнейшим практически значимым результатом исследований обозна-
ченной проблемы является разработанная программно-инструментальная платформа
проектирования на современном кроссплатформенном языке программирования Java. Вы-
бранная технология разработки позволяет использовать все основные достоинства со-
временных многоядерных и многопроцессорных архитектур, по использованию программ-
ной многопоточности для реализации параллельных схем решения комбинаторных задач.
Программно-инструментальная платформа обладает дружественным интерфейсом, что
позволяет эффективно управлять процессом решения задачи планирования компонентовбольших и сверхбольших интегральных схем трехмерной интеграции, путем визуализации
ключевых показателей работы алгоритмов на графиках и в блоках текстовой статисти-
ки. Разработанное прикладное программное обеспечение позволило провести серию вычис-
лительных экспериментов, на основе наборов случайных данных также, как и наборах от-
крытых данных бенчмарков для подобного рода задач. Результаты экспериментальных
исследований позволили подтвердить теоретические оценки временной сложности и эф-
фективности предложенных подходов и алгоритмов, в том числе генетического алгорит-
ма, который использует предложенный в работе новый механизм кодирования решений. -
ПЛАНИРОВАНИЕ ПУТИ РОБОТА ДЛЯ НЕСКОЛЬКИХ ЦЕЛЕЙ НА ОСНОВЕ ГИБРИДНОГО АЛГОРИТМА PRM И AGA
Альзубайри Шаймаа М. Джавад Кадим, А.А. Петунин , С.С. Уколов6-182025-11-10Аннотация ▼Задачи планирования оптимального пути мобильных роботов особенно активно исследуются в последнее десятилетие. Цель состоит в том, чтобы найти оптимальный или близкий к оптимальному путь от начального терминала до одного или нескольких терминалов в среде с различными препятствиями. С точки зрения минимизации времени перемещения роботов, пройденного расстояния, энергетических затрат или других оптимизационных критериев. В данной работе предлагается гибридный алгоритм, сочетающий алгоритм вероятностной дорожной карты (PRM) и адаптированный генетический алгоритм (AGA) для решения задачи планирования пути с одной или несколькими независимыми целями. В качестве оптимизационного критерия используется длина пути робота. По сравнению с существующими подходами, используемыми в генетических алгоритмах (GA), предлагаемый подход имеет два основных различия. Первое – это представление среды, которое опирается на обработку изображений и морфологические операции, что оказалось более эффективным методом, чем методы на основе клеточного представления.
В частности, предложенный способ устраняет необходимость поиска компромисса между точностью и скоростью обработки геометрической информации. Второе – это новая тактика создания начальной популяции генетического алгоритма для ускорения сходимости при наличии нескольких целей. за счёт использования возможностей вероятностного алгоритма дорожной карты. Еще одна особенность реализации алгоритма связана с адекватным (для исследуемой предметной области) выбором числовых параметров, определяющих особенности всех этапов эволюционной стратегии, включая временные затраты на выполнение каждого этапа. В частности, это касается, параметров оператора мутации и элитной стратегии. Предложенный алгоритм был протестирован на двух реальных картах с разной степенью сложности. Эффективность алгоритма подтверждена сравнением с результатами планирования пути для тестовых карт, полученными с помощью стандартного генетического алгоритма и алгоритма оптимизации муравьиной колонии. Экспериментальные результаты показывают, что гибридный алгоритм расширяет возможности обычного генетического алгоритма и находит рациональные варианты пути с лучшим значением целевой функции для одной и нескольких целей за гораздо меньшее время, чем другие традиционные реализации GA -
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПЛАНИРОВАНИЯ ТРАЕКТОРИИ ДВИЖЕНИЯ ГРУППЫ МОБИЛЬНЫХ РОБОТОВ ПРИ НАЛИЧИИ СТАЦИОНАРНЫХ И ПОДВИЖНЫХ ПРЕПЯТСТВИЙ
Л. А. Рыбак , Д.И. Малышев , Д. А. Дьяконов , А. А. Мамченкова2025-04-27Аннотация ▼Рассматривается метод планирования траектории движения группы мобильных роботов,
обеспечивающий безопасное перемещение и исключающий возможность столкновений как между
самими роботами, так и с внешними препятствиями, включая движущиеся объекты. Разрабо-
танная математическая модель учитывает три основных сценария возможных столкновений:
пересечение траекторий роботов внутри группы, взаимодействие со стационарными препятст-
виями и вероятность столкновения с подвижными объектами. Каждый из этих сценариев де-
тально анализируется для обеспечения максимальной безопасности движения, а их учет позволя-
ет эффективно адаптировать маршруты роботов к изменяющимся условиям среды. Траектория
движения каждого робота представляется в виде ломаной линии с промежуточными точками,
которые оптимизируются для обеспечения безопасности движения. Особое внимание уделяется
адаптации скорости на различных участках траектории: робот может изменять скорость в
зависимости от текущих условий, чтобы минимизировать риск столкновений. Для оценки рас-
стояний между объектами используется евклидова норма, позволяющая рассчитывать мини-
мальные расстояния между центрами сферических представлений роботов и препятствий. Зада-
ча решается в два этапа. На первом этапе строится траектория для первого робота с учетом
начальных условий и расположения препятствий. На втором этапе формируются траектории
для остальных роботов с учетом уже спланированных маршрутов. Для оптимизации координат
промежуточных точек и скоростей применяется генетический алгоритм, который минимизиру-
ет время перемещения и обеспечивает безопасность движения. Генетический алгоритм использу-
ет операторы скрещивания и мутации для создания разнообразных решений, а также выполняет
проверку на соответствие условиям безопасности. Численное моделирование проведено на языке
Python с использованием библиотеки Matplotlib для визуализации результатов. В ходе эксперимен-
тов было выполнено 50 тестов с различным количеством препятствий (от 5 до 10). Анализ ре-
зультатов показал, что с увеличением числа препятствий возрастает как время расчета, так и
качество сформированных траекторий. Это подтверждает эффективность предложенного
метода для управления группами мобильных роботов в динамически меняющейся среде -
ЭВРИСТИЧЕСКИЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РЕШЕНИЯ ДИОФАНТОВЫХ УРАВНЕНИЙ
Е.Е. Полупанова , П.Е. Усов115-1232022-01-31Аннотация ▼Рассматривается задача решения диофантовых уравнений, которая может приме-
няться в криптографии и криптоанализе. Кратко излагается описание генетического ал-
горитма решения диофантовых уравнений. Определяется правило вычисления значения
целевой функции для хромосомы, описывается система кодирования в генетическом алго-
ритме. Упоминаются генетические операторы, используемые в алгоритме, определяются
условия их выполнения. Описывается критерий останова генетического алгоритма. Анали-
зируется один из недостатков генетического алгоритма – попытки решения любого дио-
фантова уравнения, в том числе и такого, которое заведомо не имеет решений. Предлага-
ется способ, позволяющий устранить этот недостаток в некоторых случаях, и, основан-
ный на теории чисел. Даётся пояснение, в каких случаях этот способ будет работать.
Перед описанием этого способа даётся определение вычета и невычета заданной степени
по заданному модулю. После описания этого способа подробно описывается программная
реализация алгоритма решения диофантовых уравнений и их систем. Затем приводятся
результаты экспериментальных исследований времени и качества работы генетического
алгоритма. Затем представляется результат работы алгоритма для уравнения, которое
заведомо не имеет решений, и для системы уравнений, которая также заведомо не имеет
решений, но в которой общее число неизвестных слишком велико для работы предлагаемо-
го метода. Сравнивается время работы алгоритма при решении уравнения и при решении
системы уравнений. Делается вывод о полезности применения предложенного способа при
решении диофантовых уравнений и систем диофантовых уравнений. -
МЕТОД ПОИСКА ПОСЛЕДОВАТЕЛЬНЫХ ПАТТЕРНОВ ПОВЕДЕНИЯ ПОЛЬЗОВАТЕЛЕЙ В ИНТЕРНЕТ-ПРОСТРАНСТВЕ
В.В. Курейчик, В.В. Бова, Ю.А. Кравченко2020-11-22Аннотация ▼Одной из важных задач интеллектуального анализа данных является выделение зако-
номерностей и обнаружение связанных событий в последовательных данных на основе
анализа последовательных паттернов. В статье исследуются возможность применения
последовательных паттернов для анализа событий поисково-познавательной деятельно-
сти пользователей при взаимодействии с Интернет-ресурсами открытой информационно-
образовательной среды. Поиск последовательных паттернов является сложной вычисли-
тельной задачей, цель которой состоит в извлечении всех частых последовательностей,
отражающих потенциальные связи внутри элементов из транзакционной базы данных
последовательностей событий поисковой активности при заданной минимальной под-
держке. Для ее решения в статье предлагается метод поиска закономерностей в последо-
вательностях событий для обнаружения скрытых закономерностей, указывающих с воз-
можные уровни уязвимости при выполнении задач информационного поиска в Интернет-
пространстве. Описана математическая модель поведения пользователей в поисковой
сессии, основанная на теории последовательных паттернов. Для повышения вычислитель-
ной эффективности метода разработан модифицированный алгоритм генерации последо-
вательных паттернов, на первом этапе которого выполняется AprioriAll, формирующий
частые последовательности-кандидаты всевозможных длин, а на втором - генетический
алгоритм оптимизации входных параметров признакового пространства сгенерированного
множества для поиска максимальных паттернов. Проведены серии вычислительных экс-
периментов на тестовых данных корпуса MSNBC, библиотеки интеллектуального анализа
данных с открытым исходным кодом SPMF. Сравнительной анализ проводился с алгорит-
мами VMSP и GSP. Результаты исследований подтвердили эффективность поиска макси-
мальных последовательных паттернов предложенным алгоритмом с точки зрения времени
выполнения и количества извлеченных паттернов. Результаты проведенных эксперимен-
тальных исследований метода показали, что для увеличения стабильности и точности
работы размер выборки, полученной в результате работы ГА, позволит сократить необ-
ходимое число сканирований базы данных паттернов, обеспечивая приемлемые вычисли-
тельные затраты, сопоставимые с алгоритмом VMSP и превосходящий по времени поиска
последовательных паттернов алгоритм GSP в среднем более чем на 150%. -
МОДИФИЦИРОВАННЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПЛАНИРОВАНИЯ ПРОЕКТОВ, РЕАЛИЗОВАННЫЙ С ИСПОЛЬЗОВАНИЕМ ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ
А. А. Могилев, В. М. Курейчик2020-07-20Аннотация ▼Предложена структура модифицированного генетического алгоритма для решения
задачи построения расписания проекта с учетом ограниченности ресурсов, реализова н-
ного с использованием облачных вычислений, проведен вычислительный эксперимент, в
ходе которого было произведено сравнение результатов работы предложенного алг о-
ритма с лучшими из известных, на данный момент, результатами. Исходя из результа-
тов эксперимента был сделан вывод, о том, что предложенный алгоритм может быт ь
использован для планирования работ реальных проектов, так как с его помощью во з-
можно составлять расписания для проектов с количеством работ n = 90 за приемлемый
промежуток времени. При планировании проектов с количеством работ n = 30, n = 60,
n = 90, 120 время выполнения предложенного алгоритма было меньше, чем время выпо л-
нения стандартного генетического алгоритма в 2.8, в 4, в 5.5 и 6.8 раз соответственно.
В связи с тем, что задача построения расписания проекта с учетом ограниченности
ресурсов является NP-трудной, проблема создания новых и модификации существующих
методов её решения по-прежнему остается актуальной. Для планирования проектов с
большим количеством работ целесообразно использовать облачные вычисления, так как
планирование таких проектов может потребовать много времени и вычислительных
ресурсов. Использование облачных вычислений позволит сократить время выполнения
генетического алгоритма за счет предоставления поставщиком облачного сервиса
больших вычислительных ресурсов. В связи с этим, предложенный в данной работе алго-
ритм отличается от уже имеющихся использованием облачных вычислений для распр е-
деления нагрузки между рабочими станциями, на которых одновременно выполняется
данный алгоритм. Применение в генетическом алгоритме модифицированны х операто-
ров, а также использование облачной инфраструктуры как услуги для реализации ген е-
тического алгоритма при решении задачи планирования проектов определяет научную
новизну исследования. -
КЛАССИФИКАЦИЯ И АНАЛИЗ ЭВОЛЮЦИОННЫХ МЕТОДОВ КОМПОНОВКИ БЛОКОВ ЭВА
Е. В. Данильченко, В.И. Данильченко, В.М. Курейчик2020-07-20Аннотация ▼В настоящее время наблюдается большой рост потребности в проектировании и
разработке радиоэлектронных устройств. Это связано с повышающимися требованиями
к радиоэлектронным системам, а также появлением новых поколений полупроводниковых
приборов. В этой связи возникает необходимость в разработке новых средств автомати-
зированного компоновки блоков ЭВА. Перед компоновкой блоков ЭВА существует ряд про-
блем, которые усложняют реальное представление знаний в САПР и вероятно разрешимы
на нынешнем уровне развития когнитивных наук. Проблема стереотипа и проблема огрубления - взаимосвязаны и нуждаются в создании гибридных моделей представления. В ра-
боте рассмотрена проблема решения задачи компоновки блоков ЭВА при проектировании
радиоэлектронной аппаратуры. Цель данной работы заключается в нахождении путей
оптимизации планирования компоновки блоков ЭВА с применением генетического алго-
ритма. Актуальность работы состоит в том, что генетический алгоритм позволяет
повысить качество планирования компоновки. Рассматриваемые алгоритмы позволяют
повысить качество и скорость планирования компоновки. Научная новизна заключается в
поиске и анализе эффективных методов компоновки блоков ЭВА с помощью генетических
алгоритмов. Принципиальное отличие от известных сравнений в анализе новых перспек-
тивных алгоритмов компоновки блоков ЭВА. Результаты работы. В работе указаны не-
достатки традиционных алгоритмов поиска субоптимального плана ЭВА. Приведены опи-
сания современных моделей эволюционных и других вычислений. Генетические алгоритмы
обладают рядом важных преимуществ – это приспособляемость к изменяющейся окру-
жающей среде, при эволюционном подходе есть возможность анализировать, дополнять и
изменять базу знаний в зависимости от изменяющихся условий, а также быстрое созда-
ние оптимальных решений. Если применять генетические алгоритмы и эвристику предва-
рительной обработки, чтобы обеспечить оптимальные начальные решения, то можно
достичь более продуктивного использования алгоритмов. Известные генетические алго-
ритмы быстро сходящиеся, но при этом они теряют разнообразие популяции, что влияет
на снижение качества решения. Для балансировки данных решение выправляют с помощью
эффективных операторов или устойчивой мутацией.
1 - 9 из 9 результатов
