Для авторов
Найти
Результаты поиска
Найдено результатов: 18.
-
ПОПУЛЯЦИОННЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ДЕРЕВА РЕШЕНИЙ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ
Б. K. Лебедев , О. Б. Лебедев , В.Б. Лебедев2020-11-22Аннотация ▼В ряде случаев возникает необходимость установления соответствия между заяв-
ленным и фактическим значением категориальной переменной на основе совокупности
признаков объекта. В этом случае возникает потребность в классификаторе с оптималь-
ной последовательностью рассматриваемых атрибутов с заданным значением целевой
функции. Значением целевой переменной может быть: да, нет, номер сорта, номер класса
и т.д. В работе решается задача построения классификационной модели в виде оптималь-
ной последовательность рассматриваемых атрибутов и их значений, входящих в состав
маршрута от корневой вершины к концевой вершине с заданным значением целевой пере-
менной. Если требуется классификатор, включающий возможность альтернативных от-
ветов, то вначале строятся независимо друг от друга оптимальные маршруты для каж-
дого значения целевой переменной, а затем эти маршруты объединяются («склеиваются»)
в единое бинарное дерево решений. В алгоритме построения классификатора на основе
метода кристаллизации россыпи альтернатив, каждое решение Qk интерпретируется в
виде в ориентированного маршрута Mk на бинарном дереве решений. Назовем порядковый
номер элемента в ориентированном маршруте Mk позицией siS={si|i=1,2,…,nA}. Элемен-
том маршрута Mk является пара (xi,ui-), где xi соответствует Ai. ui- в маршруте Mk явля-
ется ребром, выходящим из xi и соответствует выбранному вместе с Ai значению Ai. Вто-
рой индекс элемента ui- определится после выбора Ai, помещенного в соседнюю с sj позицию
sj+1. Работа алгоритма построения дерева решений базируется на использовании коллек-
тивной эволюционной памяти, под которой подразумевается информация, отражающая
историю поиска решения. Алгоритм учитывает тенденции к использованию альтернатив
из наилучших найденных решений. Особенностями являются наличие непрямого обмена
информацией – стигмержи. Совокупность данных об альтернативах и их оценках состав-
ляет россыпь альтернатив. Рассмотрены ключевые моменты анализа альтернатив в про-
цессе эволюционной коллективной адаптации. Экспериментальные исследования показали,
что разработанный алгоритм находит решения, не уступающие по качеству, а иногда и
превосходящие своих аналогов в среднем на 3–4 %. Временная сложность алгоритма, полу-
ченная экспериментальным путем, лежит в пределах О(n2)-О(n3). -
ПОИСКОВЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС
Б. К. Лебедев , О.Б. Лебедев , В. Б. Лебедев2020-11-22Аннотация ▼В работе рассматривается поисковый популяционный алгоритм размещения компо-
нентов СБИС. По аналогии с процессом возникновения и формирования кристаллов из ве-
щества, процесс порождения решения путем последовательного проявления и конкретиза-
ции решения на базе интегральной россыпи альтернатив назван методом кристаллизации
россыпи альтернатив. Решение Qk задачи размещения представляется в виде биективного
отображения Fk=A→P, каждому элементу множества A соответствует один единст-
венный элемент множества P и наоборот. Лежащая в основе алгоритма метаэвристика
кристаллизации россыпи альтернатив выполняет поиск решений с учетом коллективной
эволюционной памяти, под которой подразумевается информация, отражающая историю
поиска решения и памяти поисковой процедуры. Отличительной особенностью используе-
мой метаэвристики является учет тенденции к использованию альтернатив из наилучших
найденных решений. Предложены компактные структуры данных для хранения интерпре-
таций решений и памяти. Алгоритм, связанный с эволюционной памятью, стремится к
запоминанию и многократному использованию способов достижения лучших результатов.
Разработанный алгоритм относится к классу популяционных алгоритмов. Итерационный
процесс поиска решений включает три этапа. На первом этапе каждой итерации конст-
руктивным алгоритмом формируется nq решений Qk. Работа конструктивного алгоритма
базируется на базе показателей основной интегральной россыпи альтернатив – матрицы
R, в которой хранятся интегральные показатели решений, полученных на предыдущих
итерациях. Процесс назначения элемента в позицию включает две стадии. На первой ста-
дии выбирается элемент, а на второй стадии – позиция pj. При этом должно выполняться
ограничение: каждому элементу соответствует одна позиция pj. Рассчитывается оценка
ξk решения Qk и оценка полезности δk множества позиций Pk выбранных агентами. В рабо-
те используется циклический метод формирования решений. В этом случае наращивание
оценок интегральной полезности δk в основной интегральной россыпи альтернатив B вы-
полняется после полного формирования множества решений Q. На втором этапе итера-
ции производится наращивание оценок интегральной полезности δk в основной интеграль-
ной россыпи альтернатив – матрице R. На третьем этапе итерации осуществляетсяснижение оценок полезности δk интегральной россыпи альтернатив R на априори заданную величину δ*. Работа алгоритма завершается после выполнения заданного числа итера-
ций. Сравнительный анализ с другими алгоритмами решения производился на стандартных
тестовых примерах (бенчмарках) корпорации IBМ, при этом решения, синтезируемые ал-
горитмом CAF, превосходят по эффективности решения известных методов в среднем на
6%. Временная сложность алгоритма – О(n2)-О(n3). -
ЭВОЛЮЦИОННЫЙ ПОПУЛЯЦИОННЫЙ МЕТОД РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
Б.К. Лебедев , О.Б. Лебедев , Е.О. Лебедева2022-11-01Аннотация ▼Рассматривается эволюционный популяционный метод решения транспортной за-
дачи на основе метаэвристики кристаллизации россыпи альтернатив. Исследуется за-
крытая (или сбалансированная) модель транспортной задачи: сумма груза у поставщиков
равно общей сумме потребностей в пунктах назначения. Цель оптимизации – минимизация
стоимости (достижение минимума затрат на перевозку) или расстояний и критерий вре-
мени (затрачивается минимум времени на перевозку). В основу метаэвристики кристалли-
зации россыпи альтернатив положена стратегия, основанная на запоминании и повторе-
нии прошлых успехов. Стратегия делает упор на «коллективную память», под которой
подразумевается любой вид информации, которая отражает прошлую историю развития
и хранится независимо от индивидуумов. В качестве кода решения транспортной задачи
рассматривается упорядоченная последовательность Dk маршрутов. Объектами являют-
ся маршруты, альтернативами – множество позиций P в списке, где np – число позиций в
списке Dк. Множество объектов Dк соответствует множеству всех маршрутов. Множе-
ство альтернативных состояний P объекта соответствует множеству альтернативных
вариантов размещения объекта списке Dк. Работа популяционного эволюционного алго-
ритма кристаллизации россыпи альтернатив опирается на коллективную эволюционную
память, называемую россыпью альтернатив. Под россыпью альтернатив решения в рабо-
те называется структура данных, используемая в качестве коллективной эволюционной
памяти, несущая информацию о решении, включающую сведения о реализованных альтер-
нативах агентов в данном решении и о полезности решения. Разработан конструктивный
алгоритм формирования опорного плана путем декодирования списка Dк. На каждом шаге
t решается задача выбора очередного в последовательности Dк маршрута и определения
количества груза, перевозимого из пункта отправления Ai в пункт назначения Bj по этому
маршруту. Разработанный алгоритм является популяционным, реализующим стратегию
случайного направленного поиска. Каждый агент является кодом некоторого решения
транспортной задачи. На первом этапе каждой итерации l конструктивным алгоритмом
на базе интегральной россыпи альтернатив формируется nk кодов решений
Dk.Формирование каждого кода решения Dk выполняется последовательно по шагам путем
последовательного выбора объекта и позиции. Для построенного кода решения Dk рассчи-
тывается оценка решения ξk и оценка полезности δk. Формируется индивидуальная рос-
сыпь альтернатив Rk и переход к построению следующего кода решения.
На втором этапе итерации производится суммирования интегральной россыпи альтерна-
тив, сформированной на предыдущих итерациях от l до (l-1), cо всеми индивидуальными
россыпями альтернатив, сформированных на итерации l. На третьем этапе итерации l
производится снижение всех интегральных оценок полезности r*αβ интегральной россыпи
альтернатив R*(l) на величину δ*. Алгоритм решения транспортной задачи был реализован
на языке С++ в среде Windows. Сравнение значений критерия, на тестовых примерах, сизвестным оптимумом показало, что у 90% примеров полученное решение было оптималь-
ным, у 2% примеров решения были на 5% хуже, а у 8% примеров решения отличались ме-
нее, чем на 2%. Временная сложность алгоритма, полученная экспериментальным путем,
лежит в пределах О(n2). -
ОПТИМИЗАЦИЯ НА ОСНОВЕ ОБЪЕДИНЕНИЯ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ РОЯ АГЕНТОВ
Б.К. Лебедев , О. Б. Лебедев , М. А. Ганжур2023-06-07Аннотация ▼Разработана архитектура бионического поиска для решения задачи размещения элемен-
тов СБИС на основе гибридизации алгоритмов пчелиной колонии и роя хромосом, что позволя-
ет выходить из «локальных ям» и увеличивает сходимость алгоритма размещения. Начальные
итерации реализует пчелиный алгоритм, чтобы обеспечить широкий обзор области поиска, а
завершающие – алгоритм роя хромосом, обеспечивающий точную локализацию экстремума,
найденного пчелиным алгоритмом. Агенты представляются в виде популяции хромосом, яв-
ляющихся генотипами решения задачи размещения. В работе описывается модифицированная
парадигма роя хромосом, обеспечивающая, в отличие от канонического метода, возможность
поиска решений в аффинном пространстве позиций с целочисленными значениями параметров.
В поисковом популяционном методе оптимизации роем хромосом агентами популяция являют-
ся хромосомы. Хромосома является генотипом объекта оптимизации. Суть поисковой проце-
дуры заключается в последовательной смене оператором направленной мутации состояний
объекта оптимизации (хромосомы) и поиске оптимального состояния. Предложена аффинно-
релаксационная модель (АРМ) роя хромосом – это граф вершины которого соответствуют
хромосомам, а дуги соответствуют аффинным связям между ними. Переход хромосомы в
новое состояние осуществляется с помощью релаксационной процедуры. В работе в качестве
средства изменения решения выступает оператор направленной мутации (ОНМ), суть кото-
рого заключается в изменения целочисленных значений генов в хромосоме. Целью перехода явля-
ется сокращении веса аффинной связи между хромосомами. Описаны механизмы ОНМ. Пред-
ложена модифицированная структура алгоритма пчел. Для каждой базовой хромосомы реали-
зуется вероятностный выбор набора хромосом, расположенных в окрестности базовой хромо-
сомы. Улучшить качество работы разработанного алгоритма можно при помощи настройки
значений управляющих параметров. Временная сложность алгоритма при фиксированных зна-
чениях размера популяции и количества генераций составляет О(n). В общем зависимость вре-
мени работы гибридного алгоритма составляет О(n2) – О(n3). -
ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗБИЕНИЯ МЕТОДОМ КРИСТАЛЛИЗАЦИИ РОССЫПИ АЛЬТЕРНАТИВ
Б.К. Лебедев, О. Б. Лебедев, Е. О. Лебедева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 % решения качественнее, чем его аналоги. -
БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ПЛОТНОЙ УПАКОВКИ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАСКРОЯ ПОЛУОГРАНИЧЕННОЙ ПОЛОСЫ
Б. К. Лебедев , О.Б. Лебедев , М.А. Ганжур2024-10-08Аннотация ▼Предлагается архитектура и методология раскроя-упаковки полуограниченной полосы на
основе методов биоинспирированного поиска. В основе подхода к декомпозиции обшей задачи упа-
ковки и методологии формированию карт раскроя лежат эвристики уровневого подхода к упаков-
ке полосы. Архитектура сформирована на основе декомпозиции общей задачи и включает 5 основ-
ных секций: управление процессом поиска; формирования блоков; формирование контейнеров;
компакция контейнеров; заполнения полосы контейнерами. Упаковка ориентирована на двухуров-
невый раскрой полосы. На первом уровне путем гильотинного разреза выполняется раскрой на
контейнеры. На втором уровне два варианта раскроя: путем гильотинного или путем не гильо-
тинного разреза выполняется раскрой контейнеров на детали (элементы прямоугольной формы).
Упаковка выполняется путем последовательного заполнения уровней полосы контейнерами.
В основу методологии раскроя-упаковки полуограниченной полосы положен иерархический подход
снизу вверх. Задача, решаемая на первом уровне иерархии, заключается в формировании множе-
ства блоков B одинаковой ширины на базе исходного набора A прямоугольников, включаемых в
блоки. Для решения поставленной задачи авторами разработан биоинспирированный алгоритм
одномерной упаковки элементов в одинаковые блоки. На втором уровне иерархии решается задача
распределения блоков по контейнерам. Все контейнеры и блоки имеют одинаковую ширину D,
равную ширине полосы. В каждом контейнере помещаются два блока. Задача распределения бло-
ков по контейнерам сведена к задаче нахождения максимального паросочетания минимальной
стоимости. В отличие от канонической метаэвристики муравьиного алгоритма в работе аген-
том на графе поиска решений строится максимальная клика, которая является интерпретацией
решения. На третьем уровне иерархии решается задача компакции контейнеров. Процесс распре-
деления блоков по контейнерам сопровождается процедурой сжатия каждой пары блоков, назна-
чаемых в один контейнер. Целью компакции является минимизация общей площади контейнера
путем плотного размещении блоков. Компакцию последовательно проводят во всех контейнерах.
На четвертом уровне иерархии решается задача заполнения полосы контейнерами. В качестве
модели для представления решения на графе поиска решений служит клика. Разработана база
данных коллективной эволюционной памяти. Разработана методика формирования феромоновых
точек и структур данных коллективной эволюционной памяти. Для проведения объективных экс-
периментов были использованы известные тестовые задачи, представленные в литературе и
сети Интернет. По сравнению с существующими алгоритмами достигнуто улучшение результа-
тов на 3-5%. Временная сложность алгоритма, полученная экспериментальным путем, практи-
чески совпадает с теоретическими исследованиями и для рассмотренных тестовых задач со-
ставляет (ВСА ≈ О(n2)). -
ДЕЦЕНТРАЛИЗОВАННОЕ УПРАВЛЕНИЕ ГРУППОЙ АВТОНОМНЫХ ПОДВИЖНЫХ ОБЪЕКТОВ ПРИ ФОРМИРОВАНИИ ТРАЕКТОРИИ ДВИЖЕНИЯ
Б.К. Лебедев , О.Б. Лебедев , М. И. Бесхмельнов2025-01-14Аннотация ▼В статье рассматриваются алгоритмы формирования траекторий движения беспилотных
летательных аппаратов (БПЛА) при проведении поисково-спасательных и ликвидационных опера-
ций. Описаны методы и алгоритмы управления движением группы БПЛА в строю, при разверты-
вании в линию, при развертывании в шеренгу, при поворотах, в колонне. Управление осуществля-
ется с помощью альтернативных алгоритмов коллективной адаптации, основанных на идеях кол-
лективного поведения. Рассмотрены принципы функционирования одного автомата адаптации.
Целью управления ведомыми роботами является минимизация отклонений. Для реализации меха-
низма адаптации параметрам вектора сопоставляются автоматы адаптации, моделирующие
поведение объектов адаптации в среде. Разработана структура процесса альтернативной кол-
лективной адаптации параметров, под контролем которых осуществляется движение группы
БПЛА в строю. Разработаны оригинальные правила управления параметрами, обладающие рядом
преимуществ по сравнению с другими методами: полная децентрализация управления в сочетании
с динамической коррекцией параметров роботов, задающих положение и ориентация робота в
абсолютной системе координат, и линейную скорость робота соответственно. Предложена
структура маневра, выполняемого роботом для коррекции отклонений параметров. Управление
осуществляется с помощью алгоритма альтернативной коллективной адаптации, основанного на
идеях коллективного поведения объектов адаптации, что позволяет эффективно обрабатывать
внештатные ситуации, такие как выход агентов из строя, изменения числа агентов вследствие
выхода из строя или внезапного приобретения связи с очередным агентом, а также в условиях
наличия ошибок измерений и шумов, удовлетворяющих определённым ограничениям. -
БИОИНСПИРИРОВАННЫЙ ПОИСК В ПОЛНОМ ГРАФЕ СОВЕРШЕННОГО ПАРОСОЧЕТАНИЯ МАКСИМАЛЬНОЙ МОЩНОСТИ
Б. К. Лебедев , О.Б. Лебедев , М. А. Ганжур , М. И. Бесхмельнов2025-01-30Аннотация ▼Разработана реконфигурируемая архитектура гибридной многоагентной системы поиска
решений, базирующиеся на парадигмах роевых алгоритмов. Реконфигурируемая архитектура пу-
тем настройки позволяет реализовать следующие методы гибридизации: высокоуровневую и низ-
коуровневую гибридизацию вложением, типа препроцессор/постпроцессор, ко-алгоритмическую
на базе одного или нескольких типов алгоритмов. Предложена методология синтеза совершенного
паросочетания минимального веса в полном графе, основанная на базовых принципах гибридизации
поисковых. эволюционных процедур. В работе агентами роя являются трансформирующиеся хро-
мосомы, являющиеся генотипами решения. В качестве кода решения используется упорядоченный
список множества вершин графа. Разработана структура упорядоченного кода паросочетания
главное достоинство которого заключается в том, что одному решению (паросочетанию) соот-
ветствует один код и наоборот. Определены свойства упорядоченного кода и разработаны алго-
ритмы кодирования и декодирования. Работа гибридной системы начинается с генерации роем
пчел случайным образом произвольного множества отличающихся друг от друга решений в виде
исходного множества хромосом. Ключевой операцией пчелиного алгоритма является исследование
перспективных решений и их окрестностей в пространстве поиска. Разработан метод формиро-
вания окрестностей решений с регулируемой степенью подобия и близости между ними. На по-
следующих этапах работы многоагентной системы выполняется поиск решений процедурами,
построенными на основе гибридизации роевого и муравьиного алгоритмов. Отличительной осо-
бенностью гибридизации является сохранение автономии гибридизируемых алгоритмов. Отме-
тим, что для представления решений в алгоритмах используется единая структура данных, что
упрощает стыковку разработанных процедур. Предлагается подход к построению модифициро-
ванной парадигмы роя трансформирующихся хромосом. Поиск решений выполняющая в аффинном
пространстве. В процессе поиска осуществляется перманентные трансформации (переход) хро-
мосом в состояния с лучшим значением целевой функции решения (градиентная стратегия). Про-
цесс поиска решений итерационный. На каждой итерации осуществляется трансформация (пере-
ход) хромосом в состояния с лучшими значениями целевой функции решения. Целью трансформа-
ции хромосомы, тяготеющей к лучшей хромосоме, в новое состояние является минимизация сте-
пени различия, путем изменения взаимного расположения элементов в упорядоченном списке, что
соответствует увеличению веса аффинной связи. Обновленные после трансформации хромосомы
являются, в свою очередь, базовыми точками в последующих трансформациях. В результате экс-
периментов было установлено, что показатели качества разработанных алгоритмов имеют бо-
лее высокие значения чем в работах, представленных в литературе -
ГИБРИДНЫЙ МЕТОД ПЛАНИРОВАНИЯ КОНФИГУРАЦИИ МАРШРУТА НА КАРТЕ МЕСТНОСТИ В УСЛОВИЯХ ЧАСТИЧНОЙ НЕОПРЕДЕЛЕННОСТИ
М. И. Бесхмельнов , Б.К. Лебедев , О. Б. Лебедев2025-04-27Аннотация ▼Описывается гибридный алгоритм ситуационного планирования траектории в условиях
частичной неопределенности для двухмерного пространства, основанный на интеграции волново-
го и муравьиного алгоритмов, позволяющий строить в реальном масштабе времени траектории
минимальной длины с одновременной оптимизацией ряда других критериев качества построенного пути. Процессы формирования участка траектории и перемещения по нему объекта череду-
ются на каждом шаге. Формирования траектории осуществляется последовательно (пошагово)
на двух уровнях каждого шага. Формирование и ориентация локальной зоны видимости и покры-
ваемого ею региона на карте местности выполняется относительно текущего опорного вектора.
Процедурами первого уровня на карте местности последовательно по шагам формируется цепоч-
ка попарно смежных регионов с локализованными препятствиями. Процедурами второго уровня
на шаге формируется множество траекторий прохода подвижного объекта через регион.
При слиянии цепочки регионов образуется область местности, через которую прокладывается
траектория. Вся траектория является совокупностью отдельных траекторий прохода подвиж-
ного объекта через регионы, связывающих его исходную позицию с целевой позицией. Поиск реше-
ния осуществляется популяцией агентов на графе поиска решений. Вершины множества соот-
ветствуют ячейкам области. Две вершины связаны ребром, если соответствующие им ячейки на
модели местности в виде дискретного рабочего поля смежны и возможен переход соединения из
одной ячейки в другую. Синтез траектории и передвижение подвижного объекта в условиях неоп-
ределенности – это сложная задача, требующая интеграции различных сенсорных систем, алго-
ритмов обработки данных, алгоритмов планирования пути и систем управления движением. По-
стоянное развитие технологий в областях искусственного интеллекта, машинного зрения и ро-
бототехники позволяет создавать всё более совершенные системы автономной навигации. Одна-
ко, полная автономность и гарантированная безопасность подвижного объекта в любых условиях
пока остаются сложными задачами для исследования. -
МНОГОСТАДИЙНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ОДНОМЕРНОЙ УПАКОВКИ НА БАЗЕ ЭФФЕКТИВНЫХ МЕТОДОВ КОДИРОВАНИЯ РЕШЕНИЙ, И ДВУХУРОВНЕВОЙ ЭВОЛЮЦИОННОЙ ПАМЯТИ
М.А. Ганжур , Б.К. Лебедев , О.Б. Лебедев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. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников
-
УПАКОВКА В ПОЛУБЕСКОНЕЧНУЮ ПОЛОСУ НА ОСНОВЕ ДЕКОМПОЗИЦИИ И ГИБРИДИЗАЦИИ БИОИСПИРИРОВАННЫХ МЕТОДОВ
Б. К. Лебедев , О. Б. Лебедев , М. А. Ганжур2023-10-23Аннотация ▼Объектом исследования является задача прямоугольной упаковки в полубесконечную
полосу. Задан набор прямоугольников. Дан один большой объект (называемый полосой), чья
ширина D задана, а HP высота – искомое значение переменной. Цель состоит в том, что-
бы минимизировать высоту HP полосы, содержащей прямоугольники, помещенные в поло-
су без их взаимного перекрытия. Для решения задачи упаковки предложен новый гибридный
подход на основе декомпозиции общей задачи упаковки и гибридизации биоиспирированных
методов, а также новый гибридный подход к декомпозиции общей задачи упаковки. Разра-
ботаны новые архитектура и методы решения задачи упаковки, построенные на основе
декомпозиции и гибридизации разработанных авторами роевых методов, использующие
различные стратегии поиска, функционирующие параллельно-последовательно и реали-
зующие более широкий обзор пространства решений, что позволяет обеспечить более
высокую вероятность локализации глобального экстремума за приемлемое время. Разра-
ботана методология нового направления поиска решений задач ортогональной упаковки на
основе моделей адаптивного поведения биологических систем. Разработан высокоэффек-
тивный гибридный биоинспирированный метод решения задач одномерной и прямоугольной
упаковки, основанный на декомпозиции задачи на множество подзадач и интеграции ме-
тодов поисковой оптимизации. Предложены новые механизмы решения задачи упаковки,
использующие математические методы, в которых заложены принципы природных меха-
низмов принятия решений. В отличие от канонической парадигмы муравьиного алгоритма
агентом на графе поиска решений в качестве решения формируется разбиение множества
прямоугольных элементов A на подмножества Ak
i, где Ak
j ‒ подмножество элементов, на-
значенных агентом в блок. Разработаны поисковые методы для решения задач гильотин-
ного и не гильотинного прямоугольного раскроя. Для проведения объективных эксперимен-
тов были использованы известные тестовые задачи, представленные в литературе и Ин-
тернет. Получены лучшие результаты по сравнению с тестируемыми методами. Пред-
ложенные в работе теоретические положения для решения задач упаковки и раскроя про-
мышленных объектов в условиях единичного производства реализованы в виде методик,
алгоритмов и прикладного программного обеспечения. По сравнению с существующими
алгоритмами достигнуто улучшение результатов на 3–5%. Временная сложность алго-
ритма, полученная экспериментальным путем, практически совпадает с теоретическими
исследованиями и для рассмотренных тестовых задач составляет О(n2). -
ПРИМЕНЕНИЕ ТЕХНОЛОГИЙ КОМПЬЮТЕРНОГО ЗРЕНИЯ В СИСТЕМАХ ОБРАБОТКИ ВИЗУАЛЬНОЙ ИНФОРМАЦИИ
О.Б. Лебедев , Р.И. Черкасов254-2762025-11-10Аннотация ▼Рассмотрено применение технологий искусственного интеллекта, в частности компьютерного зрения в системах обработки визуальной информации. Проведен комплексный анализ нейросетевых подходов к решению задач компьютерного зрения, включая систематизацию ключевых типов задач: классификацию изображений, детектирование объектов и семантическую сегментацию. Детально исследованы архитектурные принципы сверточных нейронных сетей с акцентом на механизмы извлечения пространственных признаков через сверточные слои, оптимизацию представления данных посредством операций пулинга и преобразование признаков в полносвязных слоях. Особое внимание уделено эволюции методов обнаружения объектов, где задача выбора модели рассмотрена как расширение классификации за счет интеграции регрессии пространственных координат, а также проведена оценка эффективности детекторов на основе метрик IoU, Precision, Recall и F1-score, демонстрирующих фундаментальный компромисс между точностью локализации и скоростью обработки. В качестве оптимального решения для систем реального времени представлен алгоритм YOLOv7, архитектура которого основана на разбиении входного изображения на сетку S×S ячеек с прямым предсказанием параметров ограничивающих рамок (координаты центра, ширина, высота) и вероятностей классов для каждой ячейки, а также использовании специализированных слоёв (SPP, PANet) для мультимасштабной агрегации признаков. Структура нейронной сети подтверждает эффективность используемого подхода, обеспечивающего высокое быстродействие без критического снижения точности в стратегически важных приложениях видеонаблюдения, автономных систем и дополненной реальности. Проведено сравнительное исследование одноэтапных и двухэтапных детекторов с оценкой их производительности по ключевым метрикам. Особое внимание уделено практическим аспектам применения технологий компьютерного зрения в реальных системах обработки визуальной информации
-
РАЗРАБОТКА МОДИФИЦИРАВАННЫХ МЕТОДОВ И МОДЕЛЕЙ ПОИСКОВОЙ АДАПТАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ СБИС
О.Б. Лебедев , А.А. Жиглатый , Е.О. Лебедева2021-12-24Аннотация ▼В работе для решения задачи планирования СБИС разработан поисковый алгоритм
на основе модифицированного метода муравьиной колонии. Задача формирования плана
СБИС сводится к задаче формирования соответствующего польского выражения. Разра-
ботанный метод синтеза польского выражения включает построение дерева разрезов,
выбор типов разрезов (H или V), идентификацию и ориентацию модулей. Эволюционирую-
щая популяция разбита на пары агентов. Каждый член популяции – пара агентов, рабо-
тающих совместно. При этом конструктивные алгоритмы A1 и A2, используемые аген-
тами пары различаются. Задача, решаемая алгоритмом А1, формулируется как задача
поиска взаимно однозначного отображения Fk=M*→P множества модулей M c выбранны-
ми ориентациями, |M*|=|M| в множество P позиций шаблона Sh. Фактически решение за-
ключается в выборе на графе G1 подмножества ребер E*1E1, входящих в соответствующее отображение Fk. В алгоритме A2 в качестве модели пространства поиска реше-
ний для выбора типа, последовательности и места расположения разрезов в шаблоне Sh
разработан граф G2=(X, E2). X={(x1i,x2i)|i=1,2,…,n} множество вершин графа G2, соот-
ветствует множеству P потенциальных позиций шаблона Sh для возможного размещения
в них имен символов разрезов. Каждая потенциальная позиция piP шаблона Sh моделиру-
ется двумя альтернативными вершинами (x1i,x2i). Выбор при размещении разрезов верши-
ны x1i указывает на то, что в позицию pi помещен разрез типа V, выбор вершины x2i – ука-
зывает на то, что в позицию pi помещен разрез типа H. Каждая итерация l общего алго-
ритма включает начальный и три основных этапа. Начальный этап заключается в сле-
дующем. Обнуляются матрицы ко-эволюционной памяти КЭП*1 и КЭП*2. На первом этапе
каждая пара агентов dk=(a1k, a2k): – конструктивными алгоритмами A1 и A2 синтезирует
свое решение Wk=(E1k
*,Sk); – формируется польское выражение Shk, соответствующее
решению Wk; – на базе Shk формируется дерево разрезов Tk; – на базе Tk формируется план
Rk и рассчитывается оценка решения Fk; – агенты откладывают (добавляют) феромон в
ячейки матриц коллективной эволюционной памяти КЭП*1 и КЭП*2, соответствующие
ребрам решения Wk=(E1k
*,Sk) в графах поиска решений G1 и G2 в количестве пропорциональном оценке решения Fk. На втором этапе феромон, накопленный в КЭП*1 и КЭП*2
агентами популяции на итерации l, добавляется в КЭП1 и КЭП2. На третьем этапе осу-
ществляется испарение феромона на ребрах графов G1 и G2. Тестовые испытания под-
твердили эффективность предложенного метода. Временная сложность алгоритма, по-
лученная экспериментальным путем, совпадает с теоретическими исследованиями и для
рассмотренных тестовых задач составляет О(n2). -
УПРАВЛЕНИЕ ГРУППОЙ БПЛА ПРИ ОТРАБОТКЕ КРИЗИСНЫХ ПОЛЕТНЫХ СИТУАЦИЙ В РЕШЕНИИ ТРАНСПОРТНЫХ ЗАДАЧ
А.И. Савельев , В.В. Лебедева , И.В. Лебедев , К.В. Камынин , Л.Д. Кузнецов , А.Л. Ронжин2022-04-21Аннотация ▼В работе обоснована актуальность разработки алгоритмов управления группой БпЛА
при возникновении кризисных ситуаций, влияющих на выполнение поставленной задачи по
доставке грузов в труднодоступные места. Описан алгоритм автономного коллективного
(децентрализованного) управления группой БпЛА при выполнении целевой задачи транспор-
тировки грузов, а также комбинированного управления при возникновении кризисных ситуа-
ций, когда режим автономного управления невозможно реализовать в полном объеме. Под-
робно описан алгоритм отработки кризисной ситуации при нехватке энергетического ресур-
са на борту БпЛА и возврате агентов группы на стартовую позицию. Представлены резуль-
таты моделирование движения группы БпЛА мультироторного и самолетного типов и от-
работки кризисной ситуации по управлению группой БпЛА на основе информации о запасах
энергетических или топливных ресурсов. В ходе проведения экспериментов итеративно вы-
полнялся расчет остатка топлива при движении БпЛА в точку посадки, а также количест-
ва топлива, доступного БпЛА в данный момент времени. В результате экспериментов было
выявлено, что время расчета остатка энергетического ресурса не превышает 6,792 мс.
В случае, если топливо заканчивается у лидера, миссия транспортировки груза завершается
досрочно, поскольку не может быть выполнена без участия лидера. При выходе из строя
нескольких ведомых миссия может быть продолжена в том случае, если их количество не
превышает заданного значения, критичного для продолжения миссии доставки груза. Приве-
дены результаты экспериментальных исследований моделированию полета БпЛА с грузом, в
ходе которых выполнялось построение полетной маршрута, имитирующего криволинейную
траекторию движения в городских условиях от точки старта до конечной точки, где проис-
ходит посадка БпЛА и передача груза. В экспериментах использовался разработанные БпЛА
и бортовая система крепления термоконтейнера. При проведении летных испытаний сред-
няя скорость горизонтального движения БпЛА была задана 10 м/с. Протяженность полета
составляла 5350 м. Время, затраченное на полет, составило 13 мин. 51 с. -
БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ РЕШЕНИЯ ИНВАРИАНТНЫХ ГРАФОВЫХ ЗАДАЧ
О.Б. Лебедев , А.А. Жиглатый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). -
КО-ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ НА ОСНОВЕ ВЗАИМОДЕЙСТВИЯ СУБПОПУЛЯЦИЙ, ОТЛИЧАЮЩИХСЯ СТРАТЕГИЯМИ ПОИСКА
О. Б. Лебедев, А.А. Жиглатый2023-02-17Аннотация ▼Разработана новая методология и метод размещения элементов СБИС, отличающиеся
тем, что решение задачи размещения основывается на использовании фиксированного порядка
выбора позиций, ориентированного на эффективное решение задачи размещения, и эвристиче-
ской процедуры распределения элементов по позициям, позволяющие снизить общую трудоем-
кость, и повысить качество решения. Процесс формирования списка позиций на коммутацион-
ном поле осуществляется с использованием механизмов волнового алгоритма. В основу выбора
окончательного списка положен принцип построения маршрута с минимальной оценкой сум-
марной линейной длины расстояний между позициями маршрута. Для решения задачи разме-
щения разработан поисковый алгоритм на основе модифицированного метода муравьиной ко-
лонии. Для исключения преждевременной сходимости и локализации глобального экстремума
задачи разработка алгоритма производилась на основе ко-эволюционного подхода. Архитекту-
ра ко-эволюционного алгоритма размещения разработана на основе парадигмы муравьиного
алгоритма. В пространстве поиска субпопуляции параллельно реализуют четыре стратегии
оптимизации. В работе процесс ко-эволюции реализован на основе взаимодействия субпопуля-
ций, отличающихся стратегиями поиска. Отличительной особенностью используемого ко-
эволюционного подхода является то, что субпопуляции решений фактически являются вирту-
альными. Процесс ко-эволюции реализуется одной популяцией агентов Z путем последователь-
ного формирования и слияния, виртуальных субпопуляций решений в одну популяцию. В работе
решение задачи размещения направлено на повышение трассируемости посредством минимизации ресурсов, требуемых для реализации соединений. Существенный вклад в минимизацию
пространственной и временной сложности поисковой процедуры внесли: использование вирту-
альными субпопуляциями общей эволюционной памяти, общего графа поиска решений, форми-
рование единой интерпретации решения в виде маршрута на полном ориентированном графе с
бинарными ориентированными ребрами. Тестирование производилось на бенчмарках
19s, PrimGA1, PrimGA2. Результаты по сравнению с существующими алгоритмами улучшены
на 7-8%. Вероятность получения глобального оптимума составила 0.96. В среднем решения
отличаются от оптимального менее, чем на 1.5%. Временная сложность алгоритма при фик-
сированных значениях размера популяции и количества генераций составляет О(n). Общая вре-
менная сложность гибридного алгоритма составляет О(n2)–О(n3). -
ОПРЕДЕЛЕНИЕ ТРЕБУЕМЫХ ХАРАКТЕРИСТИК ПРИВОДА РАБОЧЕГО ОБОРУДОВАНИЯ РОБОТОТЕХНИЧЕСКОГО СРЕДСТВА ДЛЯ ГУМАНИТАРНОГО РАЗМИНИРОВАНИЯ
С. С. Носков , А.Ю. Баранник , А.А. Лебедев , A.В. Лагутина2024-08-12Аннотация ▼Целью исследования является разработка методики, позволяющей рассчитать основные па-
раметры, характеризующие способность робототехнического средства, оснащенного бойковым
минным тралом выполнять операции по гумманитарному разминированию. Для этого в рамках
данной работы были решены задачи как расчет крутящего момента на валу бойкового трала,
определение мощности приводящего бойковый трал мотора, а расчетной оценки мощности сило-
вой установки робототехнического средства. В ходе проведения исследований был проанализиро-
ван опыт создания и основные параметры зарубежных средств разминирования с бойковыми
минными тралами – экипажной машины разминирования Hydrema 910 MCV, робототехнического
средства разминирования MV-4, дистанционно-управляемой машины разминирования ДУМ-Р
«Уран-6», дистанционно-управляемого минного трала МТ-2. Также были проанализированы ос-
новные особенности рабочего органа рассматриваемых машин, а именно бойкового минного тра-
ла. В основу разработанной методики положена методика расчета силы сопротивления разруше-
ния грунта и взрывоопасного предмета ВОП при воздействии байком, опирающуюся на теорию
взаимодействия рабочих органов землеройных машин, разработанную академиком Н.Г. Домбров-
ским. Также при разработке данной методики были использованы результаты работ по расчету
конструкции бойкового трала выполненные хорватскими специалистами Винковича Н., Стойко-
вича В. и Микулича Д. При этом расчёты были проведены для различных грунтов, которые в зави-
симости от удельного сопротивления резанью поделены на 4 категории: песчаная глина, гравий;
плотная глина, уголь; твердая глина с гравием; средний сланец, мел, мягкий гипсовый камень. По-
лученные данные стали фактически массивом исходной информации, которая вместе с известными физическими зависимости позволили сформировать массив расчётных формул, которые
позволяют рассчитать крутящий моментн на валу бойкового трала, мощность приводящего бой-
ковый трал мотора, а также мощность силовой установки робототехнического средства, и тем
самым решить научную проблему, поставленную в начале исследования. -
УПРАВЛЕНИЕ ПЕРЕДВИЖЕНИЕМ ГРУППЫ БПЛА С СОБЛЮДЕНИЕМ ГЕОМЕТРИЧЕСКОЙ СТРУКТУРЫ СТРОЯ НА ОСНОВЕ АЛЬТЕРНАТИВНОЙ КОЛЛЕКТИВНОЙ АДАПТАЦИИ
Д.В. Котов , О.Б. Лебедев2024-04-15Аннотация ▼Основным способом решения задач планирования и управления движением является ис-
пользование интеллектуальных технологий. При этом интеллектуальные технологии применя-
ются для решения задач постановки и корректировки целей управления и программы действий
по реализации этих целей, а также для формирования алгоритма управления в условиях неопре-
деленности, обусловленной различными факторами, в исполнительных элементах, подсистеме
управления движением, подсистеме планирования и поведения. Данная работа посвящена акту-
альной проблеме математического моделирования и теории управления: задаче децентрализо-
ванного управления мультиагентной системой, состоящей из агентов, моделирующих поведе-
ние автономных роботов, с целью обеспечения движения группы роботов, развернутых в линию
и в строю типа «конвой». В работе рассматриваются результаты исследований в сфере
управления группой беспилотных летательных аппаратов, определены типы задач, которые
могут выполняться группой воздушных роботов, выделены основные стратегии управления и
их особенности. Сформированы общие позиции, необходимые для разработки детализирован-
ного алгоритма группового управления. Каждый робот должен ориентироваться в простран-
стве автономно без GPS по сигналам с собственной камеры или лидара (активного дальномера)
определять помехи, выстраивать оптимальные пути движения и принимать решения, направ-
ленные на достижения цели и выполнения задачи. Управление осуществляется с помощью алго-
ритма альтернативной коллективной адаптации, основанного на идеях коллективного поведе-
ния объектов адаптации. Для реализации механизма адаптации параметрам вектора сопос-
тавляются автоматы адаптации, моделирующие поведение объектов адаптации в среде. Раз-
работана структура процесса альтернативной коллективной адаптации, под управлением
которой осуществляется передвижение группы роботов в строю
1 - 18 из 18 результатов
