Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: XLVI Международной научно-практической конференции «Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ» (Россия, г. Новосибирск, 07 июня 2018 г.)

Наука: Информационные технологии

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Фонова А.Э., Трехсвояков Е.В. РАЗРАБОТКА ПРОГРАММНОГО МОДУЛЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ РАЗМЕЩЕНИЯ БЛОКОВ ЭВА БИОИНСПИРИРОВАННЫМИ МЕТОДАМИ // Научное сообщество студентов: МЕЖДИСЦИПЛИНАРНЫЕ ИССЛЕДОВАНИЯ: сб. ст. по мат. XLVI междунар. студ. науч.-практ. конф. № 11(46). URL: https://sibac.info/archive/meghdis/11(46).pdf (дата обращения: 27.02.2024)
Проголосовать за статью
Конференция завершена
Эта статья набрала 40 голосов
Дипломы участников
У данной статьи нет
дипломов

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

Фонова Анна Эдуардовна

студент, кафедра САПР ЮФУ,

РФ, гТаганрог

Трехсвояков Евгений Викторович

студент, кафедра САПР ЮФУ,

РФ, гТаганрог

Щеглов Сергей Николаевич

научный руководитель,

кандидат технических наук, доцент кафедры систем автоматизированного проектирования ЮФУ,

РФ, г. Таганрог

Определим задачу размещения компонентов СБИС таким образом: дается начальное множество элементов, на которых присутствуют выводы. Указаны элементарные цепи, которые соединяют выводы элементов, а также коммутационное поле, на котором будут располагаться элементы. Требуется разместить элементы на коммутационном поле с улучшением определенных критериев качества. [1].

Исходные данные являются описанием элементов, в котором определена форма, размеры, нахождение выводов на элементах, список цепей, который обозначает связи элементов и описание коммутационного поля. Выходные данные включают список х, у - координат на коммутационном поле для всех элементов.

 

Рисунок 1. Пример рабочего поля

 

Задача размещения принадлежит к классу оптимизационных задач. Представим ее в виде кортежа: где     – основной объект оптимизации, то есть граф ; – ограничения: – целое, - расстояние между элементами хi , хj на заданной плоскости, – целое, - число проводников, которые соединяют элементы  и ;  – общее количество цепей схемы; - общее количество посадочных мест.

Каждый элемент заполняет только одно место: .

Q является критерием оптимизации (длина самого длинного соединения),  который определяется целевой функцией:  где

Цель оптимизации: .

Алгоритм серых волков – это новый биоинспирированный алгоритм, предложенный Сейдали Мирджалили в 2013 году. Данный алгоритм имитирует процесс охоты на серых волков в дикой природе. Волки привыкли жить в стае, в которой существуют два главных волка (самец и самка). В каждой стае существует очень сильная иерархия доминирования [2].

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

 

http://www.mdpi.com/energies/energies-11-00163/article_deploy/html/images/energies-11-00163-g001.png

Рисунок 2. Окружение добычи

 

Биоинспирированный алгоритм [3] решения задачи размещения представлен на рисунке 3:

 

Рисунок 3. Биоинспирированный алгоритм решения задачи размещения

 

Программная реализация представлена на рисунке 4:

 

Рисунок 4. Программная реализация

 

Результаты вычислительных экспериментов разработанных алгоритмов. Вычисления производились на различных графах размерностью до 500 вершин. Нахождение наилучших параметров, согласно которым алгоритм выявляет самые эффективные решения является важной целью при применении биоинспирированных алгоритмов. На рисунке 5 находится зависимость времени работы алгоритма АСВ от количества размещаемых блоков. Из графика, полученного на основе экспериментальных данных, видно, что ВСА зависит квадратично от числа элементов.

 

Рисунок 5. Зависимость времени работы АСВ от числа размещаемых элементов на кристалле

 

Проведем сравнительный анализ решений ГА и АСВ для графа из 100 вершин при ограничении в 300 итераций для каждого алгоритма. Размер популяции во всех алгоритмах равен 100. В таблице 1 приведены численные результаты экспериментов.

Таблица 1.

Экспериментальные сравнения

 

Время работы, сек.

Значение ЦФ

Генетический Алгоритм

14,75

1663

Алгоритм Серых Волков

11,156

1216

 

Из таблицы 1 можно заметить, АСВ является самым быстрым и эффективным алгоритмом из исследуемых биоинспирированных алгоритмов.

В заключении отметим, в данной работе рассмотрена задача разработки программного модуля для решения задачи размещения блоков ЭВА. За основу взят алгоритм роевого интеллекта, в частности алгоритм серых волков. Этот алгоритм реализован в программном модуле размещения блоков ЭВА на печатной плате. Вычислительные эксперименты показали, что АСВ работает лучше остальных. Данная работа указывает на то, что роевой интеллект успешно можно применять для определения оптимального решения в размещении ЭВА. Заметим, что есть возможность дальнейшей модернизации данного алгоритма, для улучшения полученных результатов.

 

Список литературы:

  1. Курейчик В.В., Запорожец Д.Ю. Роевый алгоритм в задачах оптимизации. - Таганрог: Изд-во ТРТУ, 2010. – С. 28-32.
  2. Курейчик  В.В., Бушин С.А. Генетический алгоритм размещения разногабаритных элементов. - Таганрог: Изд-во ТРТУ, 2010. – С. 22-27.
  3. Курейчик В.В., Курейчик В.М., Сорокалетов П.В. Биоинспирированные методы в оптимизации. – М.: Физматлит, 2009. – 380 с. 41.
Проголосовать за статью
Конференция завершена
Эта статья набрала 40 голосов
Дипломы участников
У данной статьи нет
дипломов

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.