ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО-КАВКАЗСКИЙ РЕГИОН. 2021; 2: 18-26
http://dx.doi.org/10.17213/1560-3644-2021-2-18-26
ПРИБЛИЖЕННЫЕ МЕТОДЫ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ ЭЛЕКТРИЧЕСКИХ И ЭЛЕКТРОННЫХ ЦЕПЕЙ
Абас Висам Махди Абас – аспирант, кафедра «Прикладная математика», Южно-Российский государственный политех-нический университет (НПИ) имени М.И. Платова, г. Новочеркасск, Россия. E-mail: abas.wisam.82@mail.ru
Аннотация
Рассматривается задача оптимального размещения элементов электрических и электронных цепей. В качестве критерия выбран минимум взвешенной длины соединений. Схема задана матрицей соединений. Рассматривается фиксированный набор позиций элементов и матрица расстояний на основе ортогональной метрики. Данная задача является вариантом общей математической модели, получившей название задачи квадратичного назначения. Геометрическое ограничение задачи – в одной ячейке размещается не более одного элемента. Разработаны и реализованы на ПЭВМ комбинаторные аналоги метода Гаусса–Зейделя, генетического алгоритма и соответствующие гибридные методы для решения задачи квадратичного назначения при оптимальном размещении элементов электронной аппаратуры. Проведена серия вычислительных экспериментов, которые показали удовлетворительные вычислительные качества предложенных вариантов методов.
Предложенный вычислительный метод, являющийся комбинаторным аналогом метода покоординатного спуска и одним из вариантов общего подхода на основе парных перестановок, характеризуется наилучшими вычислительными качествами среди исследованных в статье методов. Согласно известным исследованиям генетический алгоритм сходится заведомо не хуже метода Монте-Карло. Проведенное исследование показывает, что метод штрафных функций в задаче размещения и для случая генетического алгоритма является малоэффективным. Поэтому представляет интерес в качестве особей популяции рассматривать перестановки без повторений. Это обстоятельство учитывается на этапах селекции и мутации: на указанных этапах стандартные вычисления согласно генетическому алгоритму дополняются процедурой парных перестановок генов в хромосоме. Дано подробное описание программы для реализации на ПЭВМ генетического метода.
Ключевые слова: электрическая схема; ограничения размещения; топологические параметры; метрические параметры; коммутационное поле; критерии и методы оптимизации.
Полный текст: [in elibrary.ru]
Ссылки на литературу
1. Алгоритмы размещения элементов [Электронный ресурс]. https://helpiks.org/8-12562.html (дата обращения 03.04.2021).
2. Николов Н.П. Размещение элементов электронных узлов методом многоуровневой декомпозиции и макромоделирования и реализация на его основе ППП для САПР РЭА: дис. … канд. техн. наук 05.13.12. Львов. 1985.
3. Горбачев А.А. Методы и алгоритмы пространственной трассировки печатных плат: дис. ... канд. техн. наук 05.13.12. Калининград. 1999.
4. Селютин В.А. Автоматизированное проектирование топологии БИС. M.: Радио и связь, 1983. 112 с.
5. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983. 278 с.
6. Мартюшев А.В. Метод плетей и границ в квадратичной задаче о назначениях: дис. ... канд. физ.-мат. наук: 01.01.09. СПб.: 2005. 100 с.
7. Палубецкис Г.С. Генератор тестовых задач квадратичного назначения с известным оптимальным решением // Журн. вычисл. математики и математической физики. 1988. Т. 28, № 11. С. 1740 – 1743.
8. Леушкин А.Д., Неймарк Е.А. Квадратичная задача о назначении. Обзор методов, генерация тестовых задач с априорно известным оптимумом // Труды НГТУ им. Р.Е. Алексеева. 2020. № 4 (131). С. 26 – 35.
9. Старостин Н.В., Быкова Н.В. Многоуровневый алгоритм решения задачи архитектурно-зависимой декомпозиции: учеб.-метод. пособие. Н. Новгород: Нижегородский госуниверситет, 2017. 24 с.
10. Рашковский С.А. Решение задач комбинаторной оптимизации методом Монте-Карло: доклады Академии наук. 2016. Т. 471. № 4. С. 403 – 407.
11. Rashkovskiy S.A. Monte-Carlo solution of combinatorial optimization problems // Doklady Mathematics. 2016. Vol. 94. No. 3. Pp. 720 – 724.
12. Дарховский Б.С., Попков А.Ю., Попков Ю.С. Метод пакетных итераций Монте-Карло для решения задач глобальной оптимизации // ИТиВС. 2014. Вып. 3. С. 39 – 52.
13. Кулаков А.А. Разработка и исследование алгоритмов оптимального размещения компонентов СБИС трёхмерной интеграции: дис. … канд. техн. наук 05.13.12. Таганрог, 2016. 164 с.