Разработка моделей и алгоритмов многокритериальной оптимизации компоновки и размещения элементов РЭС

• Автор: Скоробогатов, Михаил Викторович
• Шифр специальности: 05.13.12
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Воронеж
• Количество страниц: 197 с. : ил

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1. ПУТИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ СРЕДСТВ ТОПОЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ В САПР РЭС

1.1. Задачи, критерии и методы оптимальной компоновки и размещения при проектировании топологии современных РЭС.

1.1.1. Методы и алгоритмы компоновки РЭС

1.1.2. Алгоритмы оптимизации размещения элементов РЭС

1.2. Современные средства топологического проектирования и повышение их эффективности на основе многокритериальной оптимизации компоновки и размещения

1.3. Цель и задачи исследования

2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И АЛГОРИТМЫ

ОПТИМАЛЬНОЙ КОМПОНОВКИ РЭС ПО РАЗЛИЧНЫМ

КРИТЕРИЯМ.
2.1. Основные критерии оптимальной компоновки элементов

2.2. Итерационный метод парных перестановок и алгоритм начального распределения
2.2.1. Итерационный метод парных перестановок
2.2.2. Алгоритм начального распределения
2.3. Исследование зависимости эффективности алгоритма парных перестановок от начальных распределений
2.4. Итерационные алгоритмы оптимизации компоновки с использованием различных критериев
2.4.1. Оптимизация компоновки по критерию количества межблочных соединений методом парных перестановок
2.4.2. Повышение эффективности оптимизации компоновки элементов РЭС при наличии сильносвязанных областей
2.4.3. Алгоритм равномерного распределения тепловыделяющих элементов по блокам РЭС

2.4.4. Алгоритм оптимальной компоновки больших массивов тепловыделяющих элементов РЭС с совместным применением тепловых и коммутационных критериев
2.4.5. Алгоритм групповых перестановок при оптимизации компоновки элементов РЭС
2.5. Основные выводы главы
3. МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ
МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ РЭС
3.1. Основные критерии оптимального размещения элементов

3.2. Итерационные алгоритмы оптимизации размещения элементов РЭС
3.2.1. Алгоритм парных перестановок для оптимизации размещения по различным критериям
3.2.1.1. Алгоритм парных перестановок для оптимизации размещения элементов с минимизацией суммарной длины соединений
3.2.1.2. Алгоритм парных перестановок для оптимизации размещения элементов с минимизацией числа пересечений проводников
3.2.2. Исследование статистической зависимости результатов оптимизации алгоритма парных перестановок от исходных начальных размещений
3.2.2.1. Исследование зависимости эффективности алгоритма парных перестановок от исходных начальных размещений при оптимизации размещения по критерию суммарной длины соединений
3.2.2.2. Исследование зависимости эффективности алгоритма парных перестановок от исходных начальных размещений при оптимизации размещения по критерию количества пересечений соединений

3.2.3. Решение задачи размещения с минимизацией суммарной длины соединений и числа пересечений
3.2.4. Минимизация суммарной длины соединений при оптимизации размещения путем перестановок групп, созданных из наиболее связанных элементов
3.2.5. Минимизация числа пересечений трасс при оптимизации размещения путем перестановок групп, созданных из наиболее связанных элементов
3.3. Оптимальное размещение элементов РЭС с совместным использованием коммутационных и тепловых критериев
3.3.1. Оптимизационные модели задачи размещения по тепловым критериям
3.3.2. Алгоритм равномерного начального размещения тепловыделяющих элементов на коммутационном поле
3.3.3. Алгоритмы оптимизации размещения по тепловым критериям методом парных перестановок
3.3.4. Алгоритмы совместного оптимального размещения элементов РЭС по тепловым и коммутационным критериям
3.3.4.1. Равномерное размещение тепловыделяющих элементов РЭС с минимизацией суммарной длины соединений
3.3.4.2. Равномерное распределение тепловыделяющих элементов РЭС с минимизацией числа пересечений соединительных трасс
3.4. Основные выводы главы
4. РЕАЛИЗАЦИЯ ПРОГРАММНО-МЕТОДИЧЕСКОГО КОМПЛЕКСА ОПТИМИЗАЦИИ КОМПОНОВКИ И РАЗМЕЩЕНИЯ ПРИ ТОПОЛОГИЧЕСКОМ ПРОЕКТИРОВАНИИ РЭС
4.1. Структура и состав программного обеспечения
4.2. Применение разработанного программного обеспечения для оптимизации топологии РЭС и анализ эффективности
4.3. Основные выводы главы

памяти ПЭВМ. Поэтому для размещения большого числа конструктивных элементов (п > 100) часто используют эвристические алгоритмы, позволяющие сократить время решения задачи при вполне приемлемом для практики качестве получаемого результата. Кроме того, такие алгоритмы лучше приспособлены для учета конкретных конструкторско-технологических ограничений. К данной группе алгоритмов относятся итерационные, последовательные и смешанные, в которых начальное размещение получают с помощью последовательного закрепления элементов в позициях, а улучшение размещения достигается в результате их парных перестановок [15,19,33,34].
Итерационные алгоритмы имеют структуру, аналогичную итерационным алгоритмам компоновки, рассмотренным в п. 1.1.1. В них для улучшения исходного размещения элементов на плате вводят итерационный процесс перестановки местами пар или групп элементов.
В случае минимизации суммарной взвешенной длины соединений формула для расчета изменения значения целевой функции при перестановке местами элементов ц и г^, закрепленных в позициях ц и имеет вид [ 19]
ДРц(ад = Е (^р-фрХа^-а^р,), (1.17)

где р и й(р) - порядковый номер и позиция закрепления неподвижного элемента Гр. Если ЛРд(£, g) > 0, то осуществляют перестановку ц, и Г], приводящую к уменьшению целевой функции на ЛРр(Е^), после чего производят поиск и перестановку следующей пары элементов и т. д. Процесс заканчивается получением такого варианта размещения, для которого дальнейшее улучшение за счет парных перестановок элементов невозможно.
Использование описанного направленного перебора сокращает общее число анализируемых вариантов размещения (по сравнению с полным перебором), но приводит к потере гарантии нахождения глобального экстремума целевой функции.
Рассмотрим реализацию итерационного алгоритма парных перестановок (рис. 1.7). Строим матрицу длин Х=|^|, каждый элемент которой
определяет расстояние между ПОЗИЦИЯМИ Д( И Zj вычисляемое по одной из формул (1.12) - (1.14) в зависимости от способа выполнения соединений. Ис-