Для авторов
Найти
Результаты поиска
Найдено результатов: 5.
-
МНОГОСТАДИЙНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ОДНОМЕРНОЙ УПАКОВКИ НА БАЗЕ ЭФФЕКТИВНЫХ МЕТОДОВ КОДИРОВАНИЯ РЕШЕНИЙ, И ДВУХУРОВНЕВОЙ ЭВОЛЮЦИОННОЙ ПАМЯТИ
М.А. Ганжур , Б.К. Лебедев , О.Б. Лебедев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. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников
-
БИОИНСПИРИРОВАННЫЙ ПОИСК В ПОЛНОМ ГРАФЕ СОВЕРШЕННОГО ПАРОСОЧЕТАНИЯ МАКСИМАЛЬНОЙ МОЩНОСТИ
Б. К. Лебедев , О.Б. Лебедев , М. А. Ганжур , М. И. Бесхмельнов2025-01-30Аннотация ▼Разработана реконфигурируемая архитектура гибридной многоагентной системы поиска
решений, базирующиеся на парадигмах роевых алгоритмов. Реконфигурируемая архитектура пу-
тем настройки позволяет реализовать следующие методы гибридизации: высокоуровневую и низ-
коуровневую гибридизацию вложением, типа препроцессор/постпроцессор, ко-алгоритмическую
на базе одного или нескольких типов алгоритмов. Предложена методология синтеза совершенного
паросочетания минимального веса в полном графе, основанная на базовых принципах гибридизации
поисковых. эволюционных процедур. В работе агентами роя являются трансформирующиеся хро-
мосомы, являющиеся генотипами решения. В качестве кода решения используется упорядоченный
список множества вершин графа. Разработана структура упорядоченного кода паросочетания
главное достоинство которого заключается в том, что одному решению (паросочетанию) соот-
ветствует один код и наоборот. Определены свойства упорядоченного кода и разработаны алго-
ритмы кодирования и декодирования. Работа гибридной системы начинается с генерации роем
пчел случайным образом произвольного множества отличающихся друг от друга решений в виде
исходного множества хромосом. Ключевой операцией пчелиного алгоритма является исследование
перспективных решений и их окрестностей в пространстве поиска. Разработан метод формиро-
вания окрестностей решений с регулируемой степенью подобия и близости между ними. На по-
следующих этапах работы многоагентной системы выполняется поиск решений процедурами,
построенными на основе гибридизации роевого и муравьиного алгоритмов. Отличительной осо-
бенностью гибридизации является сохранение автономии гибридизируемых алгоритмов. Отме-
тим, что для представления решений в алгоритмах используется единая структура данных, что
упрощает стыковку разработанных процедур. Предлагается подход к построению модифициро-
ванной парадигмы роя трансформирующихся хромосом. Поиск решений выполняющая в аффинном
пространстве. В процессе поиска осуществляется перманентные трансформации (переход) хро-
мосом в состояния с лучшим значением целевой функции решения (градиентная стратегия). Про-
цесс поиска решений итерационный. На каждой итерации осуществляется трансформация (пере-
ход) хромосом в состояния с лучшими значениями целевой функции решения. Целью трансформа-
ции хромосомы, тяготеющей к лучшей хромосоме, в новое состояние является минимизация сте-
пени различия, путем изменения взаимного расположения элементов в упорядоченном списке, что
соответствует увеличению веса аффинной связи. Обновленные после трансформации хромосомы
являются, в свою очередь, базовыми точками в последующих трансформациях. В результате экс-
периментов было установлено, что показатели качества разработанных алгоритмов имеют бо-
лее высокие значения чем в работах, представленных в литературе -
БИОИНСПИРИРОВАННЫЙ АЛГОРИТМ ПЛОТНОЙ УПАКОВКИ ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РАСКРОЯ ПОЛУОГРАНИЧЕННОЙ ПОЛОСЫ
Б. К. Лебедев , О.Б. Лебедев , М.А. Ганжур2024-10-08Аннотация ▼Предлагается архитектура и методология раскроя-упаковки полуограниченной полосы на
основе методов биоинспирированного поиска. В основе подхода к декомпозиции обшей задачи упа-
ковки и методологии формированию карт раскроя лежат эвристики уровневого подхода к упаков-
ке полосы. Архитектура сформирована на основе декомпозиции общей задачи и включает 5 основ-
ных секций: управление процессом поиска; формирования блоков; формирование контейнеров;
компакция контейнеров; заполнения полосы контейнерами. Упаковка ориентирована на двухуров-
невый раскрой полосы. На первом уровне путем гильотинного разреза выполняется раскрой на
контейнеры. На втором уровне два варианта раскроя: путем гильотинного или путем не гильо-
тинного разреза выполняется раскрой контейнеров на детали (элементы прямоугольной формы).
Упаковка выполняется путем последовательного заполнения уровней полосы контейнерами.
В основу методологии раскроя-упаковки полуограниченной полосы положен иерархический подход
снизу вверх. Задача, решаемая на первом уровне иерархии, заключается в формировании множе-
ства блоков B одинаковой ширины на базе исходного набора A прямоугольников, включаемых в
блоки. Для решения поставленной задачи авторами разработан биоинспирированный алгоритм
одномерной упаковки элементов в одинаковые блоки. На втором уровне иерархии решается задача
распределения блоков по контейнерам. Все контейнеры и блоки имеют одинаковую ширину D,
равную ширине полосы. В каждом контейнере помещаются два блока. Задача распределения бло-
ков по контейнерам сведена к задаче нахождения максимального паросочетания минимальной
стоимости. В отличие от канонической метаэвристики муравьиного алгоритма в работе аген-
том на графе поиска решений строится максимальная клика, которая является интерпретацией
решения. На третьем уровне иерархии решается задача компакции контейнеров. Процесс распре-
деления блоков по контейнерам сопровождается процедурой сжатия каждой пары блоков, назна-
чаемых в один контейнер. Целью компакции является минимизация общей площади контейнера
путем плотного размещении блоков. Компакцию последовательно проводят во всех контейнерах.
На четвертом уровне иерархии решается задача заполнения полосы контейнерами. В качестве
модели для представления решения на графе поиска решений служит клика. Разработана база
данных коллективной эволюционной памяти. Разработана методика формирования феромоновых
точек и структур данных коллективной эволюционной памяти. Для проведения объективных экс-
периментов были использованы известные тестовые задачи, представленные в литературе и
сети Интернет. По сравнению с существующими алгоритмами достигнуто улучшение результа-
тов на 3-5%. Временная сложность алгоритма, полученная экспериментальным путем, практи-
чески совпадает с теоретическими исследованиями и для рассмотренных тестовых задач со-
ставляет (ВСА ≈ О(n2)). -
УПАКОВКА В ПОЛУБЕСКОНЕЧНУЮ ПОЛОСУ НА ОСНОВЕ ДЕКОМПОЗИЦИИ И ГИБРИДИЗАЦИИ БИОИСПИРИРОВАННЫХ МЕТОДОВ
Б. К. Лебедев , О. Б. Лебедев , М. А. Ганжур2023-10-23Аннотация ▼Объектом исследования является задача прямоугольной упаковки в полубесконечную
полосу. Задан набор прямоугольников. Дан один большой объект (называемый полосой), чья
ширина D задана, а HP высота – искомое значение переменной. Цель состоит в том, что-
бы минимизировать высоту HP полосы, содержащей прямоугольники, помещенные в поло-
су без их взаимного перекрытия. Для решения задачи упаковки предложен новый гибридный
подход на основе декомпозиции общей задачи упаковки и гибридизации биоиспирированных
методов, а также новый гибридный подход к декомпозиции общей задачи упаковки. Разра-
ботаны новые архитектура и методы решения задачи упаковки, построенные на основе
декомпозиции и гибридизации разработанных авторами роевых методов, использующие
различные стратегии поиска, функционирующие параллельно-последовательно и реали-
зующие более широкий обзор пространства решений, что позволяет обеспечить более
высокую вероятность локализации глобального экстремума за приемлемое время. Разра-
ботана методология нового направления поиска решений задач ортогональной упаковки на
основе моделей адаптивного поведения биологических систем. Разработан высокоэффек-
тивный гибридный биоинспирированный метод решения задач одномерной и прямоугольной
упаковки, основанный на декомпозиции задачи на множество подзадач и интеграции ме-
тодов поисковой оптимизации. Предложены новые механизмы решения задачи упаковки,
использующие математические методы, в которых заложены принципы природных меха-
низмов принятия решений. В отличие от канонической парадигмы муравьиного алгоритма
агентом на графе поиска решений в качестве решения формируется разбиение множества
прямоугольных элементов A на подмножества Ak
i, где Ak
j ‒ подмножество элементов, на-
значенных агентом в блок. Разработаны поисковые методы для решения задач гильотин-
ного и не гильотинного прямоугольного раскроя. Для проведения объективных эксперимен-
тов были использованы известные тестовые задачи, представленные в литературе и Ин-
тернет. Получены лучшие результаты по сравнению с тестируемыми методами. Пред-
ложенные в работе теоретические положения для решения задач упаковки и раскроя про-
мышленных объектов в условиях единичного производства реализованы в виде методик,
алгоритмов и прикладного программного обеспечения. По сравнению с существующими
алгоритмами достигнуто улучшение результатов на 3–5%. Временная сложность алго-
ритма, полученная экспериментальным путем, практически совпадает с теоретическими
исследованиями и для рассмотренных тестовых задач составляет О(n2). -
ОПТИМИЗАЦИЯ НА ОСНОВЕ ОБЪЕДИНЕНИЯ МОДЕЛЕЙ АДАПТИВНОГО ПОВЕДЕНИЯ РОЯ АГЕНТОВ
Б.К. Лебедев , О. Б. Лебедев , М. А. Ганжур2023-06-07Аннотация ▼Разработана архитектура бионического поиска для решения задачи размещения элемен-
тов СБИС на основе гибридизации алгоритмов пчелиной колонии и роя хромосом, что позволя-
ет выходить из «локальных ям» и увеличивает сходимость алгоритма размещения. Начальные
итерации реализует пчелиный алгоритм, чтобы обеспечить широкий обзор области поиска, а
завершающие – алгоритм роя хромосом, обеспечивающий точную локализацию экстремума,
найденного пчелиным алгоритмом. Агенты представляются в виде популяции хромосом, яв-
ляющихся генотипами решения задачи размещения. В работе описывается модифицированная
парадигма роя хромосом, обеспечивающая, в отличие от канонического метода, возможность
поиска решений в аффинном пространстве позиций с целочисленными значениями параметров.
В поисковом популяционном методе оптимизации роем хромосом агентами популяция являют-
ся хромосомы. Хромосома является генотипом объекта оптимизации. Суть поисковой проце-
дуры заключается в последовательной смене оператором направленной мутации состояний
объекта оптимизации (хромосомы) и поиске оптимального состояния. Предложена аффинно-
релаксационная модель (АРМ) роя хромосом – это граф вершины которого соответствуют
хромосомам, а дуги соответствуют аффинным связям между ними. Переход хромосомы в
новое состояние осуществляется с помощью релаксационной процедуры. В работе в качестве
средства изменения решения выступает оператор направленной мутации (ОНМ), суть кото-
рого заключается в изменения целочисленных значений генов в хромосоме. Целью перехода явля-
ется сокращении веса аффинной связи между хромосомами. Описаны механизмы ОНМ. Пред-
ложена модифицированная структура алгоритма пчел. Для каждой базовой хромосомы реали-
зуется вероятностный выбор набора хромосом, расположенных в окрестности базовой хромо-
сомы. Улучшить качество работы разработанного алгоритма можно при помощи настройки
значений управляющих параметров. Временная сложность алгоритма при фиксированных зна-
чениях размера популяции и количества генераций составляет О(n). В общем зависимость вре-
мени работы гибридного алгоритма составляет О(n2) – О(n3).
1 - 5 из 5 результатов
