Для авторов
Найти
Результаты поиска
Найдено результатов: 3.
-
МНОГОСТАДИЙНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ОДНОМЕРНОЙ УПАКОВКИ НА БАЗЕ ЭФФЕКТИВНЫХ МЕТОДОВ КОДИРОВАНИЯ РЕШЕНИЙ, И ДВУХУРОВНЕВОЙ ЭВОЛЮЦИОННОЙ ПАМЯТИ
М.А. Ганжур , Б.К. Лебедев , О.Б. Лебедев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-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). -
РЕШЕНИЕ ЗАДАЧИ ИНТЕЛЛЕКТУАЛЬНОГО АНАЛИЗА ДАННЫХ НА ОСНОВЕ БИОИНСПИРИРОВАННОГО АЛГОРИТМА
Э.В. Кулиев , Д. Ю. Запорожец, Ю.А. Кравченко , М.М. Семенова2022-01-31Аннотация ▼Рассматривается биоинспирированный алгоритм для решения задач интеллектуаль-
ного анализа. Интеграция биоинспирированных алгоритмов для решения задач интеллек-
туального анализа данных является перспективным направлением исследований. В качест-
ве биоинспирированного алгоритма, рассмотрен алгоритм, основанный на адаптивном
поведении муравьиной колонии. Алгоритм муравьиной колонии позволяет производить ка-
чественный поиск перспективных решений для получения оптимальных и квазиоптималь-
ных решений. Алгоритм обладает способностью выполнять поиск подходящей логических
условий. Алгоритм муравьиной колонии основан на примере поведения живых муравьев в
природе. Муравьи способны находить кратчайшее решение адаптируясь к изменениям
окружающей среды. Авторами предложен модифицированный алгоритм муравьиной коло-
нии для решения задачи интеллектуального анализа данных. В качестве задачи интеллек-
туального анализа данных выбрана задача кластеризации. Кластеризация – объединение в
группы схожих объектов – является одной из фундаментальных задач в области анализа
данных и Data Mining. Список прикладных областей, где она применяется, широк: сегмен-
тация изображений, маркетинг, борьба с мошенничеством, прогнозирование, анализ тек-
стов и многие другие. Решение данной задачи приобретает особую актуальность в услови-
ях постоянно растущего объема генерируемых, передаваемых и обрабатываемых данных.
Классические методы кластеризации оптимизированы путем объединения с предложен-
ным алгоритмом биоинспирированной оптимизации – муравьиным алгоритмом. Предло-
женный метод представляет собой модель, в которой муравьи представлены в виде аген-
тов, которые случайным образом перемещаются в пространстве решений с некоторыми
ограничений (например, препятствия на их пути). Для определения эффективности разра-
ботанного модифицированного муравьиного алгоритма (АСО) с алгоритмом кластериза-
ции, авторами была проведена серия вычислительных экспериментов. Для сравнения были
взять генетический алгоритм, алгоритм обезьян и алгоритм волков. Результаты модели-
рования доказывают, что муравьиный алгоритм на основе кластеризации дает лучшие
результаты, чем другие предлагаемые алгоритмы.
1 - 3 из 3 результатов
