Найти

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

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

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

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

• РАЗРАБОТКА БИОЭВРИСТИК ДЛЯ СОЗДАНИЯ ИНТЕЛЛЕКТУАЛЬНОЙ ПОДСИСТЕМЫ ПРИНЯТИЯ ЭФФЕКТИВНЫХ РЕШЕНИЙ NP- ТРУДНЫХ И NP-СЛОЖНЫХ КОМБИНАТОРНО-ЛОГИЧЕСКИХ ЗАДАЧ НА ГРАФАХ

  Д.В. Заруба , Э.В. Кулиев , Д. Ю. Запорожец , М. М. Семенова

  2021-11-14

  Аннотация ▼

  Статья посвящена решению новых актуальных проблем, возникших в условиях со-
  временного развития информационных и нанометровых технологий в области проектиро-
  вания, а также разработке новых инновационных методов, обеспечивающих получение
  эффективных решений за полиномиальное время. В статье рассматривается проблема
  решения NP-сложных задач. Приведено описание процедуры измерения сложности задачи.
  Описаны особенности NP- трудных и NP-сложных комбинаторно-логических задач. При-
  ведены основные различия между задачами, а также проблемы, с которыми приходится
  сталкиваться при решении такого вида задач. Представлена общая схема принятия реше-
  ний, состоящая из формулировки проблемы; принятие решения; сигнала в автоматических
  системах и обратной связи. На втором этапе (формирование и выбор вариантов решений)
  решение основывается на биоинспирированном алгоритме поиска решений задачи комми-
  вояжёра. Для решения поставленной задачи был разработан модифицированный биоинспи-
  рированный алгоритм, основанный на поведении муравьиной колонии. В отличие от других
  методов оптимизации, метаэвристические алгоритмы могут находить глобальные опти-
  мальные решения для задач, где существует много локальных решений из-за их случайного
  характера. Эти причины привели к широкому использованию таких алгоритмов при реше-
  нии различных задач оптимизации. Биоинспирированные алгоритмы становятся новой
  революцией в области решений оптимизационных задач. Представлена постановка задачи
  коммивояжера, а также решение поставленной задачи на основе муравьиного алгоритма.
  Алгоритмы, такие как генетические алгоритмы и PSO могут быть очень полезными, но
  они все еще имеют некоторые недостатки в решении проблем мультимодальной оптими-
  зации. Эти алгоритмы способны находить оптимальные решения независимо от физиче-
  ской природы проблемы. В рамках экспериментальных исследований был произведен анализ
  работы биоинспирированных алгоритмов: алгоритм стаи летучих мышей бактериальный
  алгоритм и муравьиный алгоритм.

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

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

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

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

  Э. В. Кулиев, А. А. Лежебоков, М. М. Семенова, В.А. Семенов

  2020-07-20

  Аннотация ▼

  Рассмотрены актуальные вопросы и проведен анализ проблемы трехмерной инте-
  грации и трехмерного моделирования, возникающей на этапе конструкторского проекти-
  рования в ходе решения задачи оптимального планирования компонентов больших и сверх-
  больших интегральных схем и корпусных устройств электронной вычислительной аппара-
  туры. Представлены и достаточно детально описаны основные преимущества примене-
  ния принципов трехмерной интеграции, позволяющие эффективно организовывать произ-
  водство персонифицированной электроники, оптимально планировать конфигурацию
  больших и сверхбольших интегральных схем с учетом тепловых и энергетических характе-
  ристик. В ходе выполнения исследований авторами разработан подход к кодированию ре-
  шений на основе интеллектуального механизма, который характеризуется наличием
  встроенных средств контроля допустимых решений. Одним из таких средств, экспери-
  ментально доказавших свою эффективность, является встроенный механизм «смертель-
  ных мутаций», учитывающий статусы генов и заранее заданные ограничения на итоговую
  конфигурацию корпуса проектируемого устройства. В работе предложен ряд общих под-
  ходов и конкретных алгоритмов решения задачи планирования, основывающихся на ре-
  зультатах исследований авторского коллектива и современных подходах к решению
  NP-полных задач. Важнейшим практически значимым результатом исследований обозна-
  ченной проблемы является разработанная программно-инструментальная платформа
  проектирования на современном кроссплатформенном языке программирования Java. Вы-
  бранная технология разработки позволяет использовать все основные достоинства со-
  временных многоядерных и многопроцессорных архитектур, по использованию программ-
  ной многопоточности для реализации параллельных схем решения комбинаторных задач.
  Программно-инструментальная платформа обладает дружественным интерфейсом, что
  позволяет эффективно управлять процессом решения задачи планирования компонентовбольших и сверхбольших интегральных схем трехмерной интеграции, путем визуализации
  ключевых показателей работы алгоритмов на графиках и в блоках текстовой статисти-
  ки. Разработанное прикладное программное обеспечение позволило провести серию вычис-
  лительных экспериментов, на основе наборов случайных данных также, как и наборах от-
  крытых данных бенчмарков для подобного рода задач. Результаты экспериментальных
  исследований позволили подтвердить теоретические оценки временной сложности и эф-
  фективности предложенных подходов и алгоритмов, в том числе генетического алгорит-
  ма, который использует предложенный в работе новый механизм кодирования решений.