Содержание к диссертации
Введение
Глава 1. Анализ проблем моделирования тепловых полей в системах автоматизированного размещения ЭРЭ 10
1.1. Иерархия конструктивного построения РЭС с позиций анализа тепловых характеристик 10
1.2. Связь тепловых характеристик с основными расчетными процедурами 13
1.3. Постановка задачи теплового моделирования РЭС с позиции системного анализа тепловых характеристик 21
1.4 Функциональный анализ систем автоматизированного проектирования радиоэлектронных систем 24
1.5. Комплексный анализ систем математического моделирования тепловых процессов 30
1.6. Сравнительный анализ систем размещения ЭРЭ на монтажном пространстве 35
1.7. Цель работы и задачи исследования 41
Глава 2. Разработка структуры интегрированной системы моделирования тепловых полей и эволюционного размещения электрорадиоэлементов на монтажном пространстве 42
2.1. Реализация процесса анализа тепловых характеристик РЭС в рамках интегрированных компьютерных технологий 42
2.2. Модульная структура интегрированной системы моделирования и размещения элементов на монтажном пространстве 55
2.3. Основные этапы моделирования и проектирования РЭС с использованием графических библиотек элементов 58
2.4. Постановка задачи поиска оптимальных решений задачи размещения ЭРЭ 65
2.5. Формирование критерия размещения ЭРЭ с учётом тепловых процессов 68
2.6. Формирование исходной информации для математического моделирования тепловых процессов печатных узлов 71
2.7. Анализ использования графических форматов для интеграции графических систем моделирования и проектирования 77
2.8. Конвертация графических форматов файлов для интеграции систем автоматизированного проектирования и моделирования 81
Выводы 84
Глава 3. Математические методы поиска оптимальных решений в задаче размещения электрорадиоэлементов с учётом результатов моделирования тепловых полей 86
3.1. Основные этапы процесса принятия проектных решений по размещению ЭРЭ на монтажном пространстве 86
3.2. Размещение элементов по центрам кластеров с помощью генетического алгоритма 92
3.2.1. Представление допустимых решений задачи размещения в виде бинарных строк 98
3.2.2. Вариабельные признаки особей эволюционного процесса размещения 100
3.2.3. Взаимодействие основных факторов эволюции популяции в течении жизненного цикла 103
3.3. Модификация метода компоновки для размещение элементов в кластере 114
3.4. Модификация метода локальных минимумов для размещения элементов внутри кластера 116
Выводы 120
Глава 4. Программная реализация системы эволюционоого размещения элементов с учётом тепловых полей 121
4.1. Структура интегрированной базы данных радиоэлектронных компонентов 121
4.2. Графический интерфейс «Универсальной справочной системы электронных компонентов» 123
4.3. Программный модуль конвертации графической базы данных из системы P-CAD в AutoCAD 128
4.4. Программный модуль «Система эволюционного размещения электрорадиоэлементов на монтажном пространстве с учётом тепловых полей» 134
4.5. Графический интерфейс и основные принципы работы программы размещения ЭРЭ 138
4.6. Апробация размещения ЭРЭ на монтажном пространстве с учётом результатов моделирования тепловых полей 142
Выводы 151
Заключение 152
Список использованных источников 154
Приложения
- Связь тепловых характеристик с основными расчетными процедурами
- Модульная структура интегрированной системы моделирования и размещения элементов на монтажном пространстве
- Размещение элементов по центрам кластеров с помощью генетического алгоритма
- Графический интерфейс «Универсальной справочной системы электронных компонентов»
Введение к работе
Актуальность темы. В современных условиях интенсивное усовершенствование радиоэлектронных систем (РЭС), направленное на увеличение степени миниатюризации узлов и блоков и повышение требований к надёжности, приводит к необходимости учитывать проблемы анализа тепловых характеристик элементов. Тепловые нагрузки в первую очередь, сказываются на режимах работы электрорадиоэлементов (ЭРЭ), что прямым образом влияет на качество и степень надёжности готового изделия.
Сложность комплексного математического моделирования тепловых режимов и теплового проектирования РЭС заключается в отсутствии у разработчика единой программной среды моделирования и проектирования. Современные пакеты программного обеспечения, предназначенные для размещения ЭРЭ на монтажном пространстве, как правило, не учитывают тепловые режимы работы РЭС и соответственно не проводят их оптимизацию, а предпологают только топологическую оптимизацию для последующей трассировки печатного узла.
Одним из подходов к решению задачи обеспечения оптимального теплового режима функционирования РЭС, является совместное использование методов эволюционного моделирования (генетических алгоритмов) для размещения ЭРЭ на монтажном пространстве и систем математического моделирования тепловых режимов. Такой выбор обусловлен некритичностью генетических алгоритмов к виду оптимизируемой функции, их высокими адаптационными свойствами и быстрой сходимостью при решении оптимизационных задач. Комбинация из методов эволюционного и теплового моделирования позволяет гарантированно получать наборы допустимых проектных решений.
Таким образом, актуальность темы исследования обусловлена необходимостью разработки математических и программных средств, позволяющих получать и оценивать проектные решения размещения ЭРЭ на
5 монтажном пространстве с оперативным учетом результатов моделирования
тепловых режимов функционирования РЭС.
Тематика диссертационной работы соответствует одному из основных научных направлений Воронежского государственного технического университета «Вычислительные системы и программно-аппаратные комплексы».
Цель работы її задачи исследования. Целью диссертационной работы , является разработка специальных математических и программных средств для принятия проектных решений по эволюционному размещению элементов на монтажном пространстве с оперативным учётом результатов математического моделирования тепловых режимов работы радиоэлектронных систем.
Для достижения поставленной цели в работе определены следующие задачи исследования:
провести комплексный анализ проблем моделирования тепловых полей в системах автоматизированного размещения электрорадиоэлементов;
разработать структуру интегрированной системы моделирования тепловых полей и размещения электрорадиоэлементов на монтажно-коммуникационном пространстве;
сформировать унифицированную графическую базу данных моделей ЭРЭ для поддержки и проведения моделирования и размещения элементов;
разработать математические методы поиска оптимальных решений в задаче размещения электрорадиоэлементов с учётом результатов моделирования тепловых полей;
создать специальное программное обеспечение, реализующее эволюционное размещение электрорадиоэлементов с учётом тепловых полей.
Методы исследования. В качестве теоретической и методологической
основы диссертационного исследования использованы методы теории
системного анализа, систем управления базами данных, математического
моделирования, объектно-ориентированного программирования,
математического программирования, компьютерной графики и эволюционных методов оптимизации.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
-предложена модульная структура интегрированной системы моделирования и эволюционного размещения ЭРЭ на монтажном пространстве с оперативным учётом тепловых полей;
-сформирована унифицированная интегрированная графическая база данных моделей ЭРЭ для проведения комплексного моделирования и проектирования РЭС с использованием различных CAD систем;
модифицирован набор математических методов, состоящий из модифицированного генетического алгоритма и алгоритма локальных минимизаций для генерации и оценки результатов принятия проектных решений по размещению ЭРЭ на монтажно-коммутационном пространстве с учётом тепловых процессов;
разработан алгоритм и программное обеспечение конвертации графических форматов файлов для интеграции различных систем моделирования и проектирования с сохранением исходной структуры проекта;
создан набор алгоритмов, реализованных в виде специального программного обеспечения, позволяющего проводить эволюционную оптимизацию размещения в составе интегрированной графической системы моделирования и проектирования сложных радиоэлектронных систем.
Практическая значимость работы. В работе предложен комплекс программных средств, позволяющий проводить моделирование тепловых режимов, анализ и оптимизацию процесса размещения ЭРЭ на монтажном пространстве. В рамках диссертационной работы разработано программное обеспечение «Универсальная справочная система радиоэлектронных компонентов для графических САПР», зарегистрированная в ФАП ВНТИЦ РФ и «Система эволюционного размещения электрорадиоэлементов на монтажном пространстве с учётом тепловых полей».
Реализация и внедрение результатов работы. Основные теоретические и практические результаты работы были апробированы при разработке блока питания системы уличного светодиодного освещения, разрабатываемого в ООО «Рустехресурс» и электронного датчика реле температуры БУТ-Э1, разрабатываемого в 000 «Трейд». Результаты диссертационной работы также используются в учебном процессе ВГТУ в дисциплинах «Конструкторское технологическое обеспечение производства ЭВМ» и «Автоматизированное проектирование вычислительных систем».
Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на Международной открытой научной конференции «Информационные технологии моделирования и управления» (Воронеж, 2004); Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2004); X Международной открытой научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж, 2005); XI Международной открытой научной конференции «Современные проблемы информатизации в моделировании и программировании» (Воронеж, 2006); XII Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2007).
Публикации. По материалам диссертации опубликовано 11 научных работ, в том числе 3-в изданиях, рекомендованных ВАК РФ. В работах опубликованных в соавторстве и приведённых в конце автореферата, лично соискателю принадлежат: [1, 3] - методы реализации процесса размещения электрорадиоэлементов на монтажном пространстве с учётом тепловых процессов; [2] - модель синтеза трёхмерных объектов; [4, 5, 10] - структура интегрированных библиотек для систем моделирования и проектирования РЭС; [6, 11] - структура универсальной справочной системы электронных компонентов для поддержки процесса моделирования и проектирования
8 электронных систем; [7, 8] - методы интеграции различных систем
моделирования и проектирования РЭС.
Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы из 62 наименований. Основная часть работы изложена на 160 страницах, содержит 20 рисунков, 4 таблицы и 4 приложения.
Содержание работы. В первой главе произведена оценка возможности применения широко распространённых систем математического моделирования тепловых режимов работы РЭС и систем автоматизированного проектирования в задачах размещения ЭРЭ. Приведено обоснование необходимости разработки системы размещения ЭРЭ на монтажном пространстве с оперативным учётом результатов моделирования тепловых процессов протекающих в РЭС, сформулированы требования, предъявляемые к данной системе.
Во второй главе на основе проведённого системного анализа разработана модульная структура интегрированной системы моделирования и размещения ЭРЭ на монтажном пространстве с оперативным учётом тепловых процессов. Выявлены основные критерии оптимизации размещения и определенны основные этапы задачи процесса моделирования и поиска оптимальных решений размещения ЭРЭ. Разработаны основные требования для унификации интегрированных графических библиотек для обеспечения возможности сквозного моделирования и проектирования РЭС.
В третьей главе описаны математические методы поиска оптимальных решений в задаче размещения ЭРЭ с учётом результатов моделирования тепловых полей. Произведена модификация генетического алгоритма для размещения элементов по центрам кластеров, модифицирован метод компоновки для размещения элементов и разработан гибридный алгоритм состоящий из генетического алгоритма и алгоритма локальной минимизации.
В четвёртой главе представлена реализация интегрированной системы эволюционного размещения ЭРЭ на монтажном пространстве с учётом результатов моделирования тепловых процессов и оптимизации топологии
9 печатного узла, приведена структура разработанной интегрированной базы
данных ЭРЭ. Также в этой главе рассматривается проблема интеграции
графических баз данных систем моделирования и проектирования, представлен
разработанный алгоритм конвертации графических данных.
В заключении сформулированы основные научные и практические результаты диссертационного исследования.
В приложении приведены таблицы сравнительного анализа систем моделирования тепловых процессов в РЭС между собой, систем размещения ЭРЭ на монтажно-коммутационном пространстве, акты внедрения и примеры апробации работы системы эволюционного размещения ЭРЭ на монтажном пространстве с учётом тепловых процессов.
Связь тепловых характеристик с основными расчетными процедурами
Влияние тепловых характеристик на различные параметры разрабатываемых устройств рассмотрены на связях тепловых процессов с другими процессами и проектными процедурами.
В РЭС, которые подвержены жестким тепловым нагрузкам (диапазон температур от минус 60 до плюс 85 С) и вибрационным воздействиям (диапазон вибрации 1-2500 Гц и амплитуда виброускорений до 25 g), значительные тепловые нагрузки приводят к изменению физико-механических (диссипативных и жесткостных) параметров конструкционных материалов РЭС [8, 19, 59] (рис. 1.2, 1.4).
Таким образом, из вышеизложенного следует, что информация, получаемая на этапах теплового моделирования и проектирования, играет важную роль в процессе синтеза схем и конструкций проектируемых РЭС.
При этом, как видно из табл. 1.1 и рис. 1.2, для качественной проработки проекта с целью учета взаимосвязи физических процессов, позволяющей выработать направления для обеспечения требуемого уровня надежности РЭС, разработчику РЭС необходимо владеть информацией о распределении тепловых полей до уровня отдельных ЭРЭ.
Потребность в данной информации особенно остро стоит на ранних этапах разработки РЭС. Традиционно на этапе эскизного проектирования, руководствуясь требованиями технического задания, осуществляется полный цикл расчетов параметров схемы и конструкции, а также показателей надежности и качества РЭС (рис 1.7).
Результатом данного этапа являются макетные образцы, которые подвергаются испытаниям, и по их результатам вносятся изменения в проект (замена ЭРЭ, корректировка электрической схемы, изменение геометрических и теплофизико-механических параметров конструкции, перекомпоновка конструктивных узлов и т. п., вплоть до корректировки технического задания), после чего продолжают испытания до получения удовлетворительных результатов. Расчётная часть проекта
Далее разработка переходит на этап технического проектирования, где большинство операций по доработке проекта повторяется, включая расчетную часть. Не трудно убедиться, что качество расчетной части в значительной степени определяет количество циклов по доработке проекта. Рассматривая процедуру теплового проектирования на рис. 1.8 видно, что ее связь с другими расчетными процедурами определяет качество их проведения и тем самым, в конечном итоге, влияет на количество доработок проекта.
Учитывая что доработка проекта, основанная на частых испытаниях, является дорогостоящей операцией, необходимо на ранних этапах разработки уделять особое внимание расчетным процедурам и их связям между собой, так как для современных РЭС характерен комплексный характер протекающих в них физических процессов.
Из рисунка видно, что фактически любая модель связана с тепловыми процессами через вектор внешних воздействий, вектор выходных характеристик, а также через некоторое множество общих для нескольких моделей геометрических параметров (размеры корпуса, размеры печатных плат, геометрические параметры каналов, образуемые конструктивными узлами, координаты размещения ЭРЭ на монтажном пространстве и т. п.). Вариация таких параметров в процессе проектирования может в различной степени влиять на множество выходных характеристик, а именно: количественно одни уменьшать, а другие увеличивать. Модели для решения задачи компоновки, размещения и трассировки
Взаимосвязь различных математических моделей при проектировании РЭС с позиций системного подхода: МЭП - модель электрических процессов; МТП -модель тепловых процессов; МАП - модель аэродинамических процессов; МГП - модель гидравлических процессов; МЭмП - модель электромагнитных процессов; ММП -модель механических процессов.
Данное обстоятельство требует также накладывать определенные ограничения на величину изменений параметров в процессе теплового проектирования. В некоторых случаях использование ограничений (1.6) не дает желаемого эффекта, так как связь между процессами может быть ярко выраженной и переходить во взаимосвязь.
Алгоритмы итеративного анализа могут строиться на базе метода простой итерации или на основе квадратичных методов. При этом использование в моделях электрических процессов ЭРЭ температурозависимых параметров (см. выражения (1.1)—(1.5)) позволяет получать функции чувствительности выходных характеристик Гэ проектируемого устройства к изменению локальных температур ЭРЭ [24, 29], что значительно облегчает труд проектировщика в процессе обеспечения соответствия выходных характеристик требованиям ТЗ.
Таким образом, с позиций системного подхода пространственно-временное (в общем случае) распределение температуры в конструкции РЭС Т(х, у, z, т) должно обеспечиваться посредством математического моделирования тепловых процессов, взаимодействующих с внешней средой. При этом под внешней средой понимают как температурные условия эксплуатации РЭС, так и множество математических моделей (см. рис. 1.8), используемых в процессе проектирования анализируемого РЭС.
Системы автоматизированного проектирования печатных узлов можно условно разделить на три категории: 1) «Легкие». Программы из этой категории ориентированы на малые проекты двух- или четырехслойных плат с небольшим числом компонентов. Как правило, здесь присутствует простой редактор схем и программа моделирования на базе стандартного алгоритма SPICE. Редактор плат содержит базовый набор функций ручного размещения компонентов и трассировки проводников. Средства автоматической трассировки или отсутствуют вовсе, или являются крайне неэффективными из-за используемых сеточных алгоритмов. 2) «Средние». Системы из этой категории позволяют упаковывать на платы проекты с гораздо большим числом элементов. Описания таких проектов, как правило, состоят из нескольких листов и могут иметь сложную иерархическую структуру. Программа моделирования также базируется на алгоритме SPICE, но позволяет анализировать достаточно сложные смешанные аналого-цифровые схемы. Редактор печатных плат обеспечивает обработку большого количества слоев и включает средства автоматического размещения и трассировки. Средства верификации печатной платы включают возможность проверки DRC и проведения анализа целостности сигналов. Имеются инструменты ведения библиотек компонентов, а также первичные средства САМ, предназначенные для подготовки проектов к производству. 3) «Тяжелые». Такие системы проектирования печатных плат практически не имеют ограничений по числу слоев и компонентов. Система ввода проектов, как правило, построена таким образом, чтобы обеспечить связь в единое целое отдельных частей, описанных самыми различными методами, причем акцент смещается в сторону текстовых описаний на языках HDL. Управление библиотеками построено таким образом, чтобы обеспечить централизованное ведение библиотечных баз данных с доступом к ним по локальной сети или через сеть Интернет. Средства моделирования позволяют оценить функционирование не только самой схемы (смешанной аналого-цифровой с применением программируемой логики), но и ее топологической реализации. По итогам предтопологического анализа формируются наборы правил и ограничений, которые автоматически передаются в редактор плат и управляют процессом размещения и трассировки. Автотрассировка выполняется с использованием бессеточных алгоритмов, но основная ставка делается на интерактивные инструменты, обеспечивающие полуавтоматическую прокладку наиболее критических проводников (дифференциальных пар, шин). В некоторых случаях при трассировке могут использоваться результаты моделирования "на лету" искажений и наводок сигналов в прокладываемых трассах. Верификация законченной топологии осуществляется с помощью оригинальных методик, позволяющих оценить распространение помех не только в сигнальных слоях, но и в слоях питания и заземления.
Модульная структура интегрированной системы моделирования и размещения элементов на монтажном пространстве
Поиск оптимальных решений по размещению ЭРЭ на монтажном пространстве является одним из трудоёмких и сложных этапов моделирования и разработки РЭС. Так как необходимо учесть большое количество разнообразных параметров(коммуникационные, тепловые и т.п. ). В современных электронных системах применяются микросхемы с очень большой степенью интеграции и работающие на высоких частотах, при этом выделяется большое количество тепла.
Для процесса размещения ЭРЭ на монтажном пространстве с учётом моделирования тепловых полей необходимо решить ряд взаимосвязанных задач: - произвести математическое моделирование тепловых полей излучаемых ЭРЭ; - математически промоделировать электрическую схему устройства для выделения ЭРЭ которые могут оказать паразитное влияние друг на друга; - создать топологическую структуру взаимных связей между элементами; - определить размеры монтажного пространства; - обозначить зоны запретного размещения и технологические вырезы; - определить оптимальные параметры и коэффициенты размещения. Для нахождения оптимального варианта размещения ЭРЭ необходимо учесть следующие параметры: - суммарную длину связей между элементами, которую необходимо минимизировать. Учёт данного параметра позволяет на этапе последующей трассировки печатного узла сформировать оптимальную топологию проводников между элементами; - тепловое излучение выделяемое ЭРЭ. Необходимо обеспечить равномерное распределение теплового излучения по всему печатному узлу для предотвращения локальных перегревов ЭРЭ и печатной платы. Это должно увеличить время наработки на отказ и обеспечить равномерное охлаждение ЭРЭ. Необходимо минимизировать температуры корпусов, температуры печатного узла в месте установки ЭРЭ. Параметры не должны выходить за рамки установленных технических условий. - паразитные явления при работе ЭРЭ. Необходимо минимизировать критерий отклонения выходных параметров работы схемы. Для оценки каждого параметра необходимо сформировать: - математическую модель тепловых полей излучаемых ЭРЭ; - математическую модель паразитных явлений; - математическую оптимизацию топологии.
Предложенная интегрированная система моделирования и проектирования полностью решает весь круг поставленных задач.
Сложность каждой задачи состоит в том, что предъявляются очень большие требования к вычислительным ресурсам и уровню подготовки специалиста, проводящего анализ и размещение ЭРЭ на монтажном пространстве. На основании этого было принято решение о необходимости ухода от прямого математического моделирования тепловых полей при каждом шаге размещения.
Процесс разработки РЭС состоит из большого количества этапов проектирования и моделирования. Целесообразно определить набор этапов разработки, чтобы свести решение задач большой размерности к решению набора задач меньшей размерности. Структуру математического обеспечения процесса моделирования и проектирования РЭС можно разделить на три основные части (Рис. 2.2). 1. Математическое моделирование тепловых полей излучаемые РЭС. 2. Математическое моделирование паразитных явлений в схемах РЭС. 3. Формирование топологических и компоновочных решений. Результаты моделирования должны обезательно учитываются при размещении ЭРЭ.
Программный модуль моделирования тепловых полей излучаемых ЭРС даёт возможность оценить тепловые критерии, получить результаты моделирования стационарных и нестационарных тепловых режимов.
Программный модуль моделирования паразитных явлений в схемах ЭРЭ даёт возможность оценить влияние паразитных индуктивностей, ёмкостей, выявить задержки сигналов в схемах и выявить амплитудно-емкостные помехи.
Программный модуль формирования топологических и компоновочных решений предъявляет коммутационные критерии для размещения, определяет вид компоновки печатного узла (технологические вырезы, зоны запретного размещения, зоны принудительного охлаждения и т.п.). Показатели надёжности дают представления о возможных режимах работы РЭС без отказов. Механические характеристики оценивает функционирование РЭС при вибрационных воздействиях и тепловых нагрузках на материалы РЭС.
Что касается посадочных мест дискретных элементов, монтируемых в отверстия, то они должны разрабатываться в соответствии с ГОСТом 29.137-91 с размерами кратными 2,5 мм, кроме случаев, где межцентровые расстояния определяются конструкцией самого элемента.
При нумеровании контактов полярных элементов первый вывод должен соответствовать минусу (катоду) а второй плюсу (аноду). Посадочные места элементов со штыревыми (радиальными) выводами определяются конструкцией элемента. Посадочные места для микросхем с планарными выводами должны выполняться в соответствии с ГОСТом 29.137-91 и ОСТом 4.010 030-81. Для импортных микросхем и других, не приведенных в указанных стандартах, рекомендуется руководствоваться американским стандартом IPC-SM-782A. Размеры контактных площадок для элементов поверхностного монтажа должны выполняться в соответствии с американским стандартом IPC-SM-782А, и быть кратными 0,1 мм. Также контактные площадки данного типа не должны иметь переходных отверстий и отступов (коротких печатных проводников), соединенных с переходными (или иными) отверстиями. Посадочные места должны содержать графическую информацию (рисунки) разнесённую по слоям. Посадочные места записываются в библиотеки с именами в двух вариантах: - с именами, повторяющими название (тип или марку) элемента и дополнительную информацию о размере корпуса или посадочного места; - с именем, состоящим из названия корпуса элемента или имени типового представителя группы. Обычно так записываются имена для элементов иностранного производства. 5) После создания УГО и посадочного места элемента необходимо произвести так называемую «упаковку» т.е. ввести информацию о соответствии выводов и дополнительную справочную информацию. Следующая информация вводится в описание: имя посадочного места; количество логических частей; буквенный код элемента (например, R для резисторов); символ элемента. Если это неоднородный компонент, то записывается несколько символов; устанавливается вариант нумерации логических частей. В соответствии с требованиями ЕСКД, должна использоваться цифровая нумерация, при этом заполняется таблица соответствия выводов.
Имя, с которым должен записываться элемент в библиотеку зависит от ряда условий. Если элемент не имеет разновидностей по номиналам и другим физическим параметрам, то имя должно повторять имя элемента или его тип. Библиотека также может быть разработана на элемент, имеющий несколько конструктивных исполнений, которые зависят от электрических или эксплуатационных параметров. К таким элементам, в основном, относятся конденсаторы, установочные размеры которых зависят от номинала, рабочего напряжения и т.п..
Размещение элементов по центрам кластеров с помощью генетического алгоритма
Исходной информацией при решении задач размещения являются: данные о конфигурации и размерах коммутационного пространства, определяемые требованиями . установки и крепления данной сборочной единицы в аппаратуре; количество и геометрические размеры конструктивных элементов, подлежащих размещению; схема соединений, а также ряд ограничений на взаимное расположение отдельных элементов, учитывающих особенности разрабатываемой конструкции. Задача сводится к отысканию для каждого размещаемого элемента таких позиций, при которых оптимизируется выбранный показатель качества и обеспечивается наиболее благоприятные условия для последующего электрического монтажа. Особое значение эта задача приобретает при проектировании аппаратуры на печатных платах.
Основная сложность в постановке задач размещения заключается в выборе целевой функции. Связано это с тем, что одной из главных целей размещения является создание наилучших условий для дальнейшей трассировки соединений, что невозможно проверить без проведения самой трассировки, также надо учесть тепловые поля излучаемые элементами. Любые другие способы оценки качества размещения позволяют создать благоприятные для трассировки условия, но не гарантируют получение оптимального результата, поскольку печатные проводники представляют собой криволинейные отрезки конечной ширины, конфигурация которых определяется в процессе их построения и зависит от порядка проведения соединений и также никак не оценивается перегрев элементов. Следовательно, если для оценки качества размещения элементов выбрать критерий, непосредственно связанный с получением оптимального рисунка металлизации печатной платы, то конечный результат может быть найден только при совместном решении задач размещения, выбора очередности проведения соединений и трассировки, что практически невозможно вследствие огромных затрат машинного времени.
Генетические алгоритмы (ГА), представляющие собой алгоритмы поиска в символьном пространстве на основе принципов, заимствованных из эволюционной теории, являются объединением методов направленного и случайного поиска. ГА хорошо работают с целевыми функциями самого общего вида (разрывными, многоэкстремальными и т.п.), так как в них используется универсальный механизм поиска решений, в котором любое пространство поиска представляется в виде множества двоичных строк. Благодаря наличию элементов направленного поиска (оператора кроссинговера и естественного отбора), сочетающихся с элементами случайности (оператора мутации), ГА относятся к классу методов оптимизации, обладающих наилучшими нелокальными свойствами. Для понижения вычислительной сложности задачи размещения необходимо произвести целочисленную аппроксимацию ее компонентов с заменой компонентов размещения, имеющих сложную геометрическую форму, их минимальными ортогональными оболочками.
Исходя из этого предположения, пространство размещения может быть представлено прямоугольным контуром D, заданным своими габаритами (а и b - соответственно длина и ширина контура) и содержащим набор зон запрещенного размещения Z = {zr;r = l,R}, где R - число зон запрещенного размещения.
Генетический алгоритм формирования наборов допустимых решений размещения ЭРЭ - реализована функция контроля возможности применения генетических операторов к выбранному случайным образом гену; - реализована функция оперативной оценки полученных решений при применении ГО к генам, несущим информацию об условно-свободных компонентах; - разработана функциия для формирования первоначальной популяции с учетом зон индивидуального размещения.
Использование модифицированной архитектуры генетического поиска и адаптированных генетических операторов позволяет исключить возникновение недопустимых решений, когда размещаемые компоненты попадают за пределы возможных зон размещения, что значительно сокращает время поиска оптимального размещения. Общая схема работы ГА представлена рисунке 3.2.
В качестве критерия остановки алгоритма может быть использовано выполнение одного из следующих условий: превышение количества заданных поколений; превышение времени эволюции, определенного пользователем; отсутствие улучшения целевой функции на протяжении нескольких поколений, количество которых определяется пользователем.
Последний критерий является наиболее предпочтительным, хотя может свидетельствовать о нахождении всего лишь локального экстремума. Параметры ГА являются встроенными в программный модуль размещения и выбираются в специально отведенном окне программного модуля. Их функция заключается в том, что благодаря им можно настраивать ГА на решение ряда специфических задач связанных с размещением и сэкономить ресурсы вычислительной машины (ОЗУ), т.к. допустимое размещение представляет собой координаты п разногабаритных компонентов, которые закодированы в двоичной системе, а ГА работает с множеством допустимых размещений, поэтому требуется достаточно большой размер памяти для хранения данной информации, а уменьшив размер популяции, вероятность кроссинговера или мутации, при решении конкретной задачи размещения, можно не только сэкономить ОЗУ, но и добиться высокой скорости работы ПМ.
Графический интерфейс «Универсальной справочной системы электронных компонентов»
Согласно хромосомной теории наследственности передача качественных признаков ЄО(РІ), і = 1, n, закодированных в генах, будет осуществляться через хромосомы от «родителей» к «потомкам». Местоположение определенного гена в хромосоме называется локусом, а альтернативные формы одного и того же гена, расположенные в одинаковых локусах хромосомы, называются аллелями (аллелеформами). Хромосома, содержащая в своих локусах конкретные значения аллелей, называется генотипом (генетическим кодом) Е(ак), который содержит всю наследственную генетическую информацию об особи а к, получаемую от «предков» и передаваемую затем «потомкам». При взаимодействии особи а[ с внешней средой ее генотип Е(а к) порождает совокупность внешне наблюдаемых количественных признаков (характеристик (pi ), включающих степень приспособленности \i(a[) особи ак к внешней среде и ее фенотип Ф(а[).
вариант размещения. В этом случае геном является бит Єе(Рі) в бинарной строке Е(х);, который представляет собой координаты (х(, yt) центра установочной кластера отдельного компонента, тем самым описывая принадлежность компонента в пространстве размещения. Линейная же последовательность всех п битов составляет хромосому, в которой каждый ген определяет принадлежность размещаемых компонентов в пространстве размещения.
В качестве ареала - области, в пределах которой только и могут встречаться особи, участвующие в эволюционном процессе, будем рассматривать область поиска D - пространство размещения.
Совокупность особей (aj,..., a v), принадлежащих ареалу, образует популяцию Р1. Число v, характеризующее число особей ak, которые образуют популяцию, будем называть численностью популяции. Для задачи размещения, популяции Р-(а{,...,а у) соответствуют набор из v совокупности допустимых размещений хк є D, к = 1, v.
Будем считать, что популяции Р1 состоят из дискретных, не перекрывающихся между собой поколений - групп особей, одинаково отдаленных в родственном отношении от общих предков, т.е. каждое последующее поколение Pt+1 является совокупностью из v особей, которые отбираются только из особей предыдущего t-ro поколения. Будем отождествлять номер поколения (верхний индекс t в обозначениях особи а к и популяции Р1) с моментом времени t=0,l,...,T, где Т - жизненный ЦИКЛ популяции, определяющий период ее эволюции.
Совокупность из v генотипов всех особей ак, составляющих популяцию Р1, образует хромосомный набор, который полностью содержит в себе генетическую информацию о популяции Р1 в целом. Наличие изменчивости хромосомного набора от поколения к поколению является необходимым условием эволюции популяции Р1 на генетическом уровне.
Будем считать, что популяция Р = (a ,..., a v) представляет собой репродукционную группу - совокупность из v особей, любые две из которых a k, af є Р\ к Ф 1 могут размножаться, выступая в роли "родителей" (ак - «мать»; а - «отец»). Здесь под размножением понимается свойство особей а кєР1 воспроизводить одного или нескольких себе подобных непосредственных «потомков» («детей») Ь, і 1 и обеспечивать у них непрерывность и наследственную преемственность качественных признаков «родителей».
Таким образом, этот фактор эволюционного развития популяции приводит к получению новой генетической информации, содержащей различные комбинации аллельных форм генов «родительских» генотипов. В задаче размещения «воспроизводство себе подобных» можно интерпретировать как возможность построения по заданным допустимым размещениям х1 , 1 eD нового допустимого размещения х eD, а «непрерывность и наследственную преемственность» - как возможность использования аллельных форм в виде бинарных комбинаций координат ee(pj), содержащихся в генотипах «родителей» Е(хк) и Е(х ), для формирования генотипа Е(х ) "потомка", тем самым обеспечивая передачу наследственных признаков (координат) особей от поколения к поколению на уровне обмена генами.
Существуют различные системы скрещивания, такие как панмиксия (случайное скрещивание), аутбридинг и инбридинг, ассортативное, определяющие подбор особей в «родительскую пару». Но большинство из них сводятся к построению распределения вероятности, после чего случайным образом выбираются два «родителя» а к,а}є P ,k 1. Первый подход самый простой и возможно самый распространенный, брачная пара формируется случайным образом («панмексия»), т.е. обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Его универсальность основана на «непредсказуемости» включения особи в брачную пару. Чтобы не допускать преждевременной сходимости алгоритма к «подоптимальным» решениям, т.е. постоянно поддерживать в популяции генетическое разнообразие потенциальных решений, предлагается другой способ выбора родительских особей. Его принцип основан на скрещивании родителей обладающих дальним родством. Под «родством» двух особей здесь будем понимать хэммининговое расстояние между их хромосомными наборами. Такой способ называют «аутбридингом». При такой схеме выбора родителей брачную пару с большей вероятностью будут составлять особи с максимально различными хромосомными наборами. Третий способ - это «инбридинг». Реализация инбридинга напоминает аутбридинг с той лишь разницей, что предпочтение при формировании пар отдается «близкородственным» особям. Инбридинг полезен при формировании локальных групп около нескольких глобальных решений в многоэкстремальных задачах на заключительных этапах поиска.
В данной работе более подробно рассматривается ассортативное скрещивание. Система скрещивания, в которой при образовании «родительской» пары особи выбираются только на основании информации об их количественных признаках (фенотипах или степени приспособленности). В тех случаях, когда при образовании «родительской» пары предпочтение отдается особям со сходными количественными признаками, говорят о положительном ассортативном скрещивании; при отборе в «родительскую» пару особей с количественными признаками, сильно различающимися между собой, говорят об отрицательном ассортативном скрещивании.
Однако, генетическая информация, содержащаяся в хромосомном наборе «родителей» и «потомков», не меняется, т.к. в результате размножения особей путем сигнами и мейоза частоты аллелей остаются постоянными, а меняются только частоты генотипов.
Ранее было отмечено, что генетическая информация, содержащаяся в хромосомном наборе «родителей» и «потомков», не меняется а перераспределяется. Перераспределение генетической информации для задачи размещения представляется как перераспределение между разногабаритными компонентами (особей) координат. Источником же генетической изменчивости особей являются мутации - изменения качественных признаков (координат) особей в результате появления новых аллельных форм в отдельных генах или целиком во всей хромосоме. Тем самым в каждом поколении мутации поставляют в хромосомный набор популяции множество различных генетических вариаций, присущих особям, которые в дальнейшем будем называть мутантами т к,к 1. Процесс изменения содержания генов в хромосоме особей путем мутаций называется мутагенезом. По сути дела, этот фактор эволюции популяции является источником новой генетической информации, не содержащейся ранее в генах генотипов «родителей» и их «потомков». Мутации являются случайными в том смысле, что не зависят ни от генетического кода особи, содержащегося в ее генотипе, ни от количественных значений фенотипа и степени приспособленности особи. Они происходят спонтанно с определенной вероятностью, заменяя в одном или нескольких локусах тех или иных генов аллельные формы последних новыми значениями аллелей, которые принадлежат генофонду и отличаются от аллелей всех «родительских» генотипов в том же самом локусе (гене).
