Найти

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

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

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

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

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

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

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

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

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

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

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

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