Найти

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

• БИОИНСПИРИРОВАННЫЙ ПОИСК В ПОЛНОМ ГРАФЕ СОВЕРШЕННОГО ПАРОСОЧЕТАНИЯ МАКСИМАЛЬНОЙ МОЩНОСТИ

  Б. К. Лебедев , О.Б. Лебедев , М. А. Ганжур , М. И. Бесхмельнов

  2025-01-30

  Аннотация ▼

  Разработана реконфигурируемая архитектура гибридной многоагентной системы поиска
  решений, базирующиеся на парадигмах роевых алгоритмов. Реконфигурируемая архитектура пу-
  тем настройки позволяет реализовать следующие методы гибридизации: высокоуровневую и низ-
  коуровневую гибридизацию вложением, типа препроцессор/постпроцессор, ко-алгоритмическую
  на базе одного или нескольких типов алгоритмов. Предложена методология синтеза совершенного
  паросочетания минимального веса в полном графе, основанная на базовых принципах гибридизации
  поисковых. эволюционных процедур. В работе агентами роя являются трансформирующиеся хро-
  мосомы, являющиеся генотипами решения. В качестве кода решения используется упорядоченный
  список множества вершин графа. Разработана структура упорядоченного кода паросочетания
  главное достоинство которого заключается в том, что одному решению (паросочетанию) соот-
  ветствует один код и наоборот. Определены свойства упорядоченного кода и разработаны алго-
  ритмы кодирования и декодирования. Работа гибридной системы начинается с генерации роем
  пчел случайным образом произвольного множества отличающихся друг от друга решений в виде
  исходного множества хромосом. Ключевой операцией пчелиного алгоритма является исследование
  перспективных решений и их окрестностей в пространстве поиска. Разработан метод формиро-
  вания окрестностей решений с регулируемой степенью подобия и близости между ними. На по-
  следующих этапах работы многоагентной системы выполняется поиск решений процедурами,
  построенными на основе гибридизации роевого и муравьиного алгоритмов. Отличительной осо-
  бенностью гибридизации является сохранение автономии гибридизируемых алгоритмов. Отме-
  тим, что для представления решений в алгоритмах используется единая структура данных, что
  упрощает стыковку разработанных процедур. Предлагается подход к построению модифициро-
  ванной парадигмы роя трансформирующихся хромосом. Поиск решений выполняющая в аффинном
  пространстве. В процессе поиска осуществляется перманентные трансформации (переход) хро-
  мосом в состояния с лучшим значением целевой функции решения (градиентная стратегия). Про-
  цесс поиска решений итерационный. На каждой итерации осуществляется трансформация (пере-
  ход) хромосом в состояния с лучшими значениями целевой функции решения. Целью трансформа-
  ции хромосомы, тяготеющей к лучшей хромосоме, в новое состояние является минимизация сте-
  пени различия, путем изменения взаимного расположения элементов в упорядоченном списке, что
  соответствует увеличению веса аффинной связи. Обновленные после трансформации хромосомы
  являются, в свою очередь, базовыми точками в последующих трансформациях. В результате экс-
  периментов было установлено, что показатели качества разработанных алгоритмов имеют бо-
  лее высокие значения чем в работах, представленных в литературе

• РАЗРАБОТКА МОДИФИЦИРАВАННЫХ МЕТОДОВ И МОДЕЛЕЙ ПОИСКОВОЙ АДАПТАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ СБИС

  О.Б. Лебедев , А.А. Жиглатый , Е.О. Лебедева

  2021-12-24

  Аннотация ▼

  В работе для решения задачи планирования СБИС разработан поисковый алгоритм
  на основе модифицированного метода муравьиной колонии. Задача формирования плана
  СБИС сводится к задаче формирования соответствующего польского выражения. Разра-
  ботанный метод синтеза польского выражения включает построение дерева разрезов,
  выбор типов разрезов (H или V), идентификацию и ориентацию модулей. Эволюционирую-
  щая популяция разбита на пары агентов. Каждый член популяции – пара агентов, рабо-
  тающих совместно. При этом конструктивные алгоритмы A1 и A2, используемые аген-
  тами пары различаются. Задача, решаемая алгоритмом А1, формулируется как задача
  поиска взаимно однозначного отображения Fk=M*→P множества модулей M c выбранны-
  ми ориентациями, |M*|=|M| в множество P позиций шаблона Sh. Фактически решение за-
  ключается в выборе на графе G1 подмножества ребер E*1E1, входящих в соответствующее отображение Fk. В алгоритме A2 в качестве модели пространства поиска реше-
  ний для выбора типа, последовательности и места расположения разрезов в шаблоне Sh
  разработан граф G2=(X, E2). X={(x1i,x2i)|i=1,2,…,n} множество вершин графа G2, соот-
  ветствует множеству P потенциальных позиций шаблона Sh для возможного размещения
  в них имен символов разрезов. Каждая потенциальная позиция piP шаблона 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).

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

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

  2020-11-22

  Аннотация ▼

  В ряде случаев возникает необходимость установления соответствия между заяв-
  ленным и фактическим значением категориальной переменной на основе совокупности
  признаков объекта. В этом случае возникает потребность в классификаторе с оптималь-
  ной последовательностью рассматриваемых атрибутов с заданным значением целевой
  функции. Значением целевой переменной может быть: да, нет, номер сорта, номер класса
  и т.д. В работе решается задача построения классификационной модели в виде оптималь-
  ной последовательность рассматриваемых атрибутов и их значений, входящих в состав
  маршрута от корневой вершины к концевой вершине с заданным значением целевой пере-
  менной. Если требуется классификатор, включающий возможность альтернативных от-
  ветов, то вначале строятся независимо друг от друга оптимальные маршруты для каж-
  дого значения целевой переменной, а затем эти маршруты объединяются («склеиваются»)
  в единое бинарное дерево решений. В алгоритме построения классификатора на основе
  метода кристаллизации россыпи альтернатив, каждое решение Qk интерпретируется в
  виде в ориентированного маршрута Mk на бинарном дереве решений. Назовем порядковый
  номер элемента в ориентированном маршруте Mk позицией siS={si|i=1,2,…,nA}. Элемен-
  том маршрута Mk является пара (xi,ui-), где xi соответствует Ai. ui- в маршруте Mk явля-
  ется ребром, выходящим из xi и соответствует выбранному вместе с Ai значению Ai. Вто-
  рой индекс элемента ui- определится после выбора Ai, помещенного в соседнюю с sj позицию
  sj+1. Работа алгоритма построения дерева решений базируется на использовании коллек-
  тивной эволюционной памяти, под которой подразумевается информация, отражающая
  историю поиска решения. Алгоритм учитывает тенденции к использованию альтернатив
  из наилучших найденных решений. Особенностями являются наличие непрямого обмена
  информацией – стигмержи. Совокупность данных об альтернативах и их оценках состав-
  ляет россыпь альтернатив. Рассмотрены ключевые моменты анализа альтернатив в про-
  цессе эволюционной коллективной адаптации. Экспериментальные исследования показали,
  что разработанный алгоритм находит решения, не уступающие по качеству, а иногда и
  превосходящие своих аналогов в среднем на 3–4 %. Временная сложность алгоритма, полу-
  ченная экспериментальным путем, лежит в пределах О(n2)-О(n3).