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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1.

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

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

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

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

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