Для авторов
Найти
Результаты поиска
Найдено результатов: 6.
-
РАЗРАБОТКА БИОЭВРИСТИК ДЛЯ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНОЙ ПОДСИСТЕМЫ ПРИНЯТИЯ ЭФФЕКТИВНЫХ РЕШЕНИЙ NP- ТРУДНЫХ И NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ
Д.В. Заруба , Э.В. Кулиев , Д. Ю. Запорожец , М. М. Семенова2021-11-14Аннотация ▼Статья посвящена решению новых актуальных проблем, возникших в условиях со-
временного развития информационных и нанометровых технологий в области проектиро-
вания, а также разработке новых инновационных методов, обеспечивающих получение
эффективных решений за полиномиальное время. В статье рассматривается проблема
решения NP-сложных задач. Приведено описание процедуры измерения сложности задачи.
Описаны особенности NP- трудных и NP-сложных комбинаторно-логических задач. При-
ведены основные различия между задачами, а также проблемы, с которыми приходится
сталкиваться при решении такого вида задач. Представлена общая схема принятия реше-
ний, состоящая из формулировки проблемы; принятие решения; сигнала в автоматических
системах и обратной связи. На втором этапе (формирование и выбор вариантов решений)
решение основывается на биоинспирированном алгоритме поиска решений задачи комми-
вояжёра. Для решения поставленной задачи был разработан модифицированный биоинспи-
рированный алгоритм, основанный на поведении муравьиной колонии. В отличие от других
методов оптимизации, метаэвристические алгоритмы могут находить глобальные опти-
мальные решения для задач, где существует много локальных решений из-за их случайного
характера. Эти причины привели к широкому использованию таких алгоритмов при реше-
нии различных задач оптимизации. Биоинспирированные алгоритмы становятся новой
революцией в области решений оптимизационных задач. Представлена постановка задачи
коммивояжера, а также решение поставленной задачи на основе муравьиного алгоритма.
Алгоритмы, такие как генетические алгоритмы и PSO могут быть очень полезными, но
они все еще имеют некоторые недостатки в решении проблем мультимодальной оптими-
зации. Эти алгоритмы способны находить оптимальные решения независимо от физиче-
ской природы проблемы. В рамках экспериментальных исследований был произведен анализ
работы биоинспирированных алгоритмов: алгоритм стаи летучих мышей бактериальный
алгоритм и муравьиный алгоритм. -
ПОДХОД К КОДИРОВАНИЮ РЕШЕНИЙ В ЭВОЛЮЦИОННЫХ МЕТОДАХ ДЛЯ СОЗДАНИЯ ИНСТРУМЕНТАЛЬНОЙ ПЛАТФОРМЫ ПРОЕКТИРОВАНИЯ
Э. В. Кулиев, А. А. Лежебоков, М. М. Семенова, В.А. Семенов2020-07-20Аннотация ▼Рассмотрены актуальные вопросы и проведен анализ проблемы трехмерной инте-
грации и трехмерного моделирования, возникающей на этапе конструкторского проекти-
рования в ходе решения задачи оптимального планирования компонентов больших и сверх-
больших интегральных схем и корпусных устройств электронной вычислительной аппара-
туры. Представлены и достаточно детально описаны основные преимущества примене-
ния принципов трехмерной интеграции, позволяющие эффективно организовывать произ-
водство персонифицированной электроники, оптимально планировать конфигурацию
больших и сверхбольших интегральных схем с учетом тепловых и энергетических характе-
ристик. В ходе выполнения исследований авторами разработан подход к кодированию ре-
шений на основе интеллектуального механизма, который характеризуется наличием
встроенных средств контроля допустимых решений. Одним из таких средств, экспери-
ментально доказавших свою эффективность, является встроенный механизм «смертель-
ных мутаций», учитывающий статусы генов и заранее заданные ограничения на итоговую
конфигурацию корпуса проектируемого устройства. В работе предложен ряд общих под-
ходов и конкретных алгоритмов решения задачи планирования, основывающихся на ре-
зультатах исследований авторского коллектива и современных подходах к решению
NP-полных задач. Важнейшим практически значимым результатом исследований обозна-
ченной проблемы является разработанная программно-инструментальная платформа
проектирования на современном кроссплатформенном языке программирования Java. Вы-
бранная технология разработки позволяет использовать все основные достоинства со-
временных многоядерных и многопроцессорных архитектур, по использованию программ-
ной многопоточности для реализации параллельных схем решения комбинаторных задач.
Программно-инструментальная платформа обладает дружественным интерфейсом, что
позволяет эффективно управлять процессом решения задачи планирования компонентовбольших и сверхбольших интегральных схем трехмерной интеграции, путем визуализации
ключевых показателей работы алгоритмов на графиках и в блоках текстовой статисти-
ки. Разработанное прикладное программное обеспечение позволило провести серию вычис-
лительных экспериментов, на основе наборов случайных данных также, как и наборах от-
крытых данных бенчмарков для подобного рода задач. Результаты экспериментальных
исследований позволили подтвердить теоретические оценки временной сложности и эф-
фективности предложенных подходов и алгоритмов, в том числе генетического алгорит-
ма, который использует предложенный в работе новый механизм кодирования решений. -
МНОГОСТАДИЙНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ОДНОМЕРНОЙ УПАКОВКИ НА БАЗЕ ЭФФЕКТИВНЫХ МЕТОДОВ КОДИРОВАНИЯ РЕШЕНИЙ, И ДВУХУРОВНЕВОЙ ЭВОЛЮЦИОННОЙ ПАМЯТИ
М.А. Ганжур , Б.К. Лебедев , О.Б. Лебедев21-372025-10-01Аннотация ▼Целью работы является разработка и исследование методов биоинспирированного поиска для решения задач одномерной упаковки в одинаковые контейнеры на базе эффективных алгоритмов кодирования и декодирования решений, композитного критерия и двухуровневой структуры эволюционной памяти. В работе предложена структура упорядоченного кода упаковки одномерных элементов в одинаковые контейнеры главное достоинство которого заключается в том, что одному решению упаковки соответствует один код и наоборот. Поисковая процедура базируется на модифицированной метаэвристике муравьиного алгоритма. На каждой итерации алгоритм одномерной упаковки имеет многостадийную структуру. Стадии выполняются последовательно одна за другой, начиная с первой. Каждая стадия Сk включает процедуры, выполняемые агентом zk. Число стадий равно числу агентов в популяции плюс заключительная стадия итерации. Основная задача, решаемая конструктивным алгоритмом на стадии Сk, заключается в построении кода Rk упаковки множества элементов X в одинаковые контейнеры. Стадия делится на периоды по числу формируемых агентом zk списков Xjк. Период делится на этапы. На каждом периоде последовательно по этапам решаются следующие задачи: агент zk конструктивным алгоритмом формирует набор Rk упорядоченных списков Xjк одномерной упаковки в одинаковые контейнеры; рассчитываются оценки fjk упаковки каждого контейнера Oj элементами списка <Xjк>; рассчитывается количество λjk феромона, пропорциональное оценке fjk; рассчитывается оценка Wk=∑i(fjk) одномерной упаковки множества элементов X в H одинаковых контейнеров; производится отложение феромона на ребрах графа G, соответствующих списку Xjк в ячейки накопительной матрицы памяти E второго уровня. После формирования всеми агентами zk популяции Z упорядоченных списков Rk, накопленный феромон добавляется в основную матрицу памяти Φ первого уровня. Для каждого Rk рассчитывается общий показатель Fk качества упаковки множества элементов X. Заключительная операция на итерации ‒ испарение феромона на ребрах графа G и фиксация zk c лучшим Fk. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников
-
ИССЛЕДОВАНИЕ МЕТОДОВ ПЛАНИРОВАНИЯ ДВИЖЕНИЯ В ДВУМЕРНЫХ КАРТОГРАФИРОВАННЫХ СРЕДАХ
М. Ю. Медведев , В.Х. Пшихопов , Д.О. Бросалин , Б. В. Гуренко , М.А. Васильева , Хамдан Низар2022-08-09Аннотация ▼Исследуются задача планирования движения в двумерных картографированных сре-
дах. Проводится обзор и анализ известных алгоритмов планирования, базирующихся на
диаграммах Вороного, вероятностной дорожной карте, быстро растущих случайных де-
ревьев, алгоритмах Дейкстры, А*, D* и их модификациях, искусственных потенциальных
полях и интеллектуальных эвристиках. На основе проведенного анализа делается вывод о
том, что классические методы в динамических средах требуют значительных затрат по
времени расчетов и объему используемой памяти. Делается вывод об актуальности разра-
ботки алгоритмов, повышающих эффективность известных методов планирования.
В этой связи данная статья посвящена разработке модифицированного алгоритма быст-
ро растущих случайных деревьев и исследованию его эффективности по сравнению с из-
вестными методами. В статье представлен модифицированный алгоритм быстро рас-
тущих случайных деревьев, отличающийся тем, что при проверке наличия пути в новый
потенциальный узел графа проверяется путь в некоторую область возле указанного узла.
Это позволяет снизить количество узлов в строящемся дереве. Разработанный алгоритм
вначале сравнивается с традиционным алгоритмом быстрорастущих случайных деревьев.
Сравнение производится по времени расчета траектории, объему требуемой памяти, дли-
не пути и проценту ситуаций, в которых успешно найдена траектория в целевую точку.
Далее осуществляется сравнение разработанного алгоритма с алгоритмами планирования
других классов. При исследовании используются репрезентативные выборки численных
экспериментов и различные среды, отличающиеся плотностью расположения препятст-
вий и наличием лабиринтов. Также проводится исследование алгоритмов планирования с
использованием результатов экспериментов на наземном колесном роботе. По результа-
там численных и реальных экспериментов делаются выводы о преимуществах и недос-
татках разработанного алгоритма планирования движения и о целесообразности его при-
менения в различных средах. -
СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ВОССТАНОВЛЕНИЯ ПРОПУЩЕННЫХ ДАННЫХ
А. А. Сорокин , А. В. Дагаев , И. М. Бородянский2020-11-22Аннотация ▼В последние десятилетия качественно развиваются методы системного анализа,
что связано с увеличением скорости технического развития, уплотнением временных про-
цессов, быстрым ростом накапливаемой информации и новыми возможностями вычисли-
тельной техники. К этим методам относятся методы анализа большого объема данных,
методы добычи данных, методы аналитического моделирования, методы параллельной
обработки данных, нейросетевые методы, методы прогнозирования и другие. Представ-
ленные методы позволяют быстро и качественно обрабатывать разнородные кластеры
информации, аккумулировать и синтезировать данные, обобщать и классифицировать
информацию. К последним из представленных методов относятся методы интерполяции и
экстраполяции потерянной, поврежденной или неполученной информации. Данные методы
позволяют структурировать, восстанавливать и моделировать информацию на основе
статистических данных, математических и алгоритмических методов. Таким образом в
статье рассматривается проблема восстановления пропущенных данных в графических и
сложных объектах. Приводятся литературные источники по рассматриваемым задачам.
В них приводится обширная информация по рассматриваемой тематике: представлены
генетические алгоритмы используемые для пространственной интерполяции; рассмотре-
но решение задач неоднородности интерполяции сейсмических данных; описано использование сплайн-аппроксимации для расчета характеристик нелинейных электронных компо-
нентов; разобран метод построения модели трехмерных параметрических рациональных
тел с помощью обобщенной интерполяции Безье, что позволяет моделировать форму тела
и анизотропное пространство; описаны методы применяющие нечеткие линейные уравне-
ния, которые широко распространены в компьютерном зрении; исследован метод адап-
тивной интерполяции на основе градиента учитывающий локальный градиент исходного
изображения. В статье выполняется сравнение нескольких распространенных методов
интерполяции и реставрации данных, таких как: билинейная интерполяция, поверхность
Безье. Кратко описывается каждый метод и особенности его применения в рамках прове-
денного эксперимента. Приводится результат серии экспериментов с представленными
методами с различным количеством испытаний. В заключении делаются выводы о рацио-
нальности выбора одного из предложенных методов без применения длительного натурно-
го эксперимента в каждом случае -
МНОГОУРОВНЕВЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ ТРЕХМЕРНОЙ УПАКОВКИ БОЛЬШОЙ РАЗМЕРНОСТИ
В. В. Курейчик, А. Е. Глущенко2020-07-20Аннотация ▼Рассмотрена одна из важных комбинаторных задач оптимизации – задача трехмер-
ной упаковки разногабаритных элементов в объеме. Она относится к классу NP- сложных
и трудных оптимизационных задач. В работе приведена и описана постановка задачи трех-
мерной упаковки в объеме, введена комбинированная целевая функция учитывающая все огра-
ничения. В связи со сложностью данной задачи предлагается многоуровневый подход заклю-
чающийся в разделение задачи трехмерной упаковки на 3-и подзадачи и решения каждой под-
задачи в строгом порядке. При этом для каждой из подзадач определен уникальный набор
объектов, не повторяющихся в остальных подзадачах. Для реализации многоуровневого под-
хода авторами разработан комбинированный биоинспирированный алгоритм, основанный на
эволюционном и генетическом поиске. Такой подход позволяет значительно сократить время
получения результата, частично решить проблему предварительной сходимости алгоритмов
и получить наборы квазиотимальных решений за полиномиальное время. Разработан про-
граммный комплекс и реализованы на ЭВМ алгоритмы автоматизированной трехмерной
упаковки на основе комбинированного биоинспирированного поиска. Проведен вычисли-
тельный эксперимент на тестовых примерах (бенчмарках). Качество упаковки, получен-
ное, на основе разработанного комбинированного биоинспирированного алгоритма, в сред-
нем на 5 % превосходит результаты упаковки, полученные с использованием известных
алгоритмов, а время решения меньше от 5 % до 20 %, что говорит об эффективности
предложенного подхода. Проведенные серии тестов и экспериментов позволили уточнить
теоретические оценки временной сложности алгоритмов упаковки. В лучшем случае вре-
менная сложность алгоритмов O(n2), в худшем случае – O(n3).
1 - 6 из 6 результатов
