Найти

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

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

  Б.К. Лебедев, О. Б. Лебедев, Е. О. Лебедева

  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 % решения качественнее, чем его аналоги.

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

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

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

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

  А.И. Савельев , В.В. Лебедева , И.В. Лебедев , К.В. Камынин , Л.Д. Кузнецов , А.Л. Ронжин

  2022-04-21

  Аннотация ▼

  В работе обоснована актуальность разработки алгоритмов управления группой БпЛА
  при возникновении кризисных ситуаций, влияющих на выполнение поставленной задачи по
  доставке грузов в труднодоступные места. Описан алгоритм автономного коллективного
  (децентрализованного) управления группой БпЛА при выполнении целевой задачи транспор-
  тировки грузов, а также комбинированного управления при возникновении кризисных ситуа-
  ций, когда режим автономного управления невозможно реализовать в полном объеме. Под-
  робно описан алгоритм отработки кризисной ситуации при нехватке энергетического ресур-
  са на борту БпЛА и возврате агентов группы на стартовую позицию. Представлены резуль-
  таты моделирование движения группы БпЛА мультироторного и самолетного типов и от-
  работки кризисной ситуации по управлению группой БпЛА на основе информации о запасах
  энергетических или топливных ресурсов. В ходе проведения экспериментов итеративно вы-
  полнялся расчет остатка топлива при движении БпЛА в точку посадки, а также количест-
  ва топлива, доступного БпЛА в данный момент времени. В результате экспериментов было
  выявлено, что время расчета остатка энергетического ресурса не превышает 6,792 мс.
  В случае, если топливо заканчивается у лидера, миссия транспортировки груза завершается
  досрочно, поскольку не может быть выполнена без участия лидера. При выходе из строя
  нескольких ведомых миссия может быть продолжена в том случае, если их количество не
  превышает заданного значения, критичного для продолжения миссии доставки груза. Приве-
  дены результаты экспериментальных исследований моделированию полета БпЛА с грузом, в
  ходе которых выполнялось построение полетной маршрута, имитирующего криволинейную
  траекторию движения в городских условиях от точки старта до конечной точки, где проис-
  ходит посадка БпЛА и передача груза. В экспериментах использовался разработанные БпЛА
  и бортовая система крепления термоконтейнера. При проведении летных испытаний сред-
  няя скорость горизонтального движения БпЛА была задана 10 м/с. Протяженность полета
  составляла 5350 м. Время, затраченное на полет, составило 13 мин. 51 с.

• ЭВОЛЮЦИОННЫЙ ПОПУЛЯЦИОННЫЙ МЕТОД РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

  Б.К. Лебедев , О.Б. Лебедев , Е.О. Лебедева

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