Найти

Результаты поиска

• МНОГОСТАДИЙНЫЙ МУРАВЬИНЫЙ АЛГОРИТМ ОДНОМЕРНОЙ УПАКОВКИ НА БАЗЕ ЭФФЕКТИВНЫХ МЕТОДОВ КОДИРОВАНИЯ РЕШЕНИЙ, И ДВУХУРОВНЕВОЙ ЭВОЛЮЦИОННОЙ ПАМЯТИ

  М.А. Ганжур , Б.К. Лебедев , О.Б. Лебедев

  21-37

  2025-10-01

  Аннотация ▼

  Целью работы является разработка и исследование методов биоинспирированного поиска для решения задач одномерной упаковки в одинаковые контейнеры на базе эффективных алгоритмов кодирования и декодирования решений, композитного критерия и двухуровневой структуры эволюционной памяти. В работе предложена структура упорядоченного кода упаковки одномерных элементов в одинаковые контейнеры главное достоинство которого заключается в том, что одному решению упаковки соответствует один код и наоборот. Поисковая процедура базируется на модифицированной метаэвристике муравьиного алгоритма. На каждой итерации алгоритм одномерной упаковки имеет многостадийную структуру. Стадии выполняются последовательно одна за другой, начиная с первой. Каждая стадия С_k включает процедуры, выполняемые агентом z_k. Число стадий равно числу агентов в популяции плюс заключительная стадия итерации. Основная задача, решаемая конструктивным алгоритмом на стадии С_k, заключается в построении кода R_k упаковки множества элементов X в одинаковые контейнеры. Стадия делится на периоды по числу формируемых агентом z_k  списков X_jк. Период делится на этапы. На каждом периоде последовательно по этапам решаются следующие задачи: агент z_k конструктивным алгоритмом формирует набор R_k упорядоченных списков X_jк одномерной упаковки в одинаковые контейнеры; рассчитываются оценки f_jk упаковки каждого контейнера O_j элементами списка <X_jк>; рассчитывается количество λ_jk феромона, пропорциональное оценке f_jk; рассчитывается оценка W_k=∑_i(f_jk) одномерной упаковки множества элементов X в H одинаковых контейнеров; производится отложение феромона на ребрах графа G, соответствующих списку X_jк в ячейки накопительной матрицы памяти E второго уровня. После формирования всеми агентами z_k популяции Z упорядоченных списков R_k, накопленный феромон добавляется в основную матрицу памяти Φ первого уровня. Для каждого R_k рассчитывается общий показатель F_k качества упаковки множества элементов X. Заключительная операция на итерации ‒ испарение феромона на ребрах графа G и фиксация z_k c лучшим F_k. Проведены экспериментальные исследования заключающиеся в выяснении качества работы метода на тестовых наборах большой размерности. Для сравнения разработанного алгоритма с известными методами и с приближенными алгоритмами авторами было выбрано несколько групп бенчмарок из различных источников

• ПОИСКОВЫЙ ПОПУЛЯЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СБИС

  Б. К. Лебедев , О.Б. Лебедев , В. Б. Лебедев

  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).