Найти

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

• МЕТАЭВРИСТИКА НА ОСНОВЕ ПОВЕДЕНИЯ КОЛОНИИ БЕЛЫХ КРОТОВ

  Е.В. Данильченко , В. И. Данильченко , В. М. Курейчик

  132-140

  2021-08-12

  Аннотация ▼

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

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

  Е. В. Данильченко , В.И. Данильченко , В.М. Курейчик

  2021-07-18

  Аннотация ▼

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

• ПРИМЕНЕНИЕ ЗАПРЕЩЕННЫХ ФИГУР В ЗАДАЧЕ РАСКРАСКИ ГРАФА ПРИ ПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ

  В. И. Потапов

  2021-01-19

  Аннотация ▼

  Проектирование конструкции печатных плат в виде плоских структур без перемы-
  чек является одной из самых сложных задач на этапе схемотехнического проектирования.
  Задача в такой постановке особенно актуальна микросборок и для электронных модулей
  контрольно-проверочной, бортовой аппаратуры, выполненных по технологии поверхност-
  ного монтажа, где, например, по причине металлического теплоотвода или керамического
  основания, структура соединений возможна только в одном слое. В работе рассматрива-
  ется задача проектирования печатных плат в виде синтеза плоских структур электрон-
  ных схем. Целью является расположение соединений на печатной плате без пересечений,
  что облегчает условия проведения трасс любому трассировщику современных программ
  проектировании. Для её решения предложено большое число различных алгоритмов, основ-
  ным недостатком которых является заложенный в них принцип последовательного и
  фрагментарного просмотра коммутационного пространства. Сложность алгоритмов
  синтеза подобных структур обусловлена также необходимостью учета большого числа
  различных требований, связанных со спецификой их изготовления и особенностями разра-
  батываемого конструктивно-технологического решения. В настоящей работе предлага-
  ется выполнить проектирование печатной платы с высокой эффективностью трассиров-
  ки соединений за счет решения задачи расслоения исходного графа-схемы и построения
  плоского графа-схемы как на стороне установки ЭРЭ, так и на обратной стороне платы -
  стороне пайки, исключая запрещенные фигуры по теореме Потрягина-Куратовского.
  Критерием является минимизация переходных отверстий, а также минимизация провод-
  ников (ребер) на одной стороне печатной платы. Задача расслоения представляет собой
  задачу раскраски графа в два цвета с использованием принципов характеризационного
  управления, решение которой базируется на теореме Кенига, определяющей запрещенную
  фигуру в виде циклов нечетной длины. Для проектирования печатных плат разработаны
  алгоритм и методика построения планарных графов и расслоения графа на две стороны
  печатной платы с уменьшением количества неразведенных ребер. Точное решение прини-
  мает вид полиномиальной зависимости не выше 5-й степени, позволяет получить резуль-
  тат за приемлемое время и повысить эффективность трассировки на 5–15 %.