автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Автоматизация размещения тепловыделяющих элементов в электронных модулях трехмерной компоновки на основе генетического алгоритма

003484315

На правах рукописи

Новиков Илья Сергеевич

АВТОМАТИЗАЦИЯ РАЗМЕЩЕНИЯ ТЕПЛОВЫДЕЛЯЮЩИХ ЭЛЕМЕНТОВ В ЭЛЕКТРОННЫХ МОДУЛЯХ ТРЕХМЕРНОЙ КОМПОНОВКИ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

Специальность 05.13.12 - Системы автоматизации проектирования

2 6 НОЯ 2009

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 2009

003484315

Работа выполнена в Московском государственном техническом университете

им. Н.Э. Баумана.

Научный руководитель: Член-корреспондент РАН,

доктор технических наук, профессор Шахнов Вадим Анатольевич

Официальные оппоненты: д.т.н., профессор

Назаров Александр Викторович

д.т.н., доцент

Филиппова Анна Сергеевна

Ведущее предприятие: Общество с ограниченной ответственностью

«Центральное проектно-конструкторское бюро Ш1М»

Защита состоится 17 декабря 2009 г. в на заседании

диссертационного совета Д 212.141.10 в Московском государственном техническом университете им. Н.Э. Баумана по адресу 105005, г. Москва, 2-я Бауманская ул., д.5

Отзыв на автореферат, заверенный печатью организации, просим присылать по адресу 105005, г. Москва, 2-я Бауманская ул., д. 5.

С диссертацией можно ознакомиться в библиотеке МГТУ им. Н.Э. Баумана.

Автореферат разослан «!2 » 2009 г.

Ученый секретарь Диссертационного совета

к.т.н., доцент Иванов С.Р.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Трехмерная компоновка основана на размещении бескорпусных элементов и соединений между ними не на плоскости печатной платы, а в трехмерном пространстве многослойного электронного модуля (далее - электронные модули трехмерной компоновки, ЭМТК). На сегодняшний день проявляется большой интерес к трехмерной компоновке, а ее освоение требует новых исследований. Большое количество разработок в этой сфере уже ведется за рубежом (компании Amkor Technology, 3D Plus, Irvine Sensors Corporation, VCI, Tezzaron Semiconductor и др.). Существуют и отечественные запатентованные разработки. Работы по применению трехмерной компоновки начаты в НИИ Аргон, НИИСИ РАН, МНПО Спектр и др. Наиболее востребованы ЭМТК в области транспортируемой ЭА, особенно в классах бортовой авиационной и космической аппаратуры, а также автомобильной электроники.

В настоящее время разработка всей ЭА не обходится без применения САПР. Автоматизация конструкторского проектирования достигла высокой степени формализации применительно к таким хорошо освоенным конструктивам электроники, как печатные платы, микросборки (МСб), интегральные и гибридные микросхемы (ИМС). Иначе обстоит дело с трехмерной компоновкой. В большей мере, это следствие того, что ЭМТК появились на рынке относительно недавно, и их разработка и производство еще не вышло на массовый уровень. И, как следствие, еще отсутствует хорошо проработанная теоретико-математическая база, на которой бы основывались САПР ЭМТК. Это делает актуальной разработку методов и алгоритмов автоматизации конструкторского проектирования ЭМТК.

Одним из важнейших этапов конструкторского проектирования является размещение элементов внутри устройства. На этом этапе целесообразно определять такое расположение дискретных источников тепла (электронных элементов), которое обеспечивает нормальный тепловой режим работы ЭМТК. Такую задачу для краткости будем называть задачей «теплового» размещения или размещением по тепловому критерию. Она состоит в поиске такого взаимного расположения элементов, при котором снижение надежности ЭМТК, вызванное перегревом этих элементов, будет минимально возможным. Иными словами, решается задача минимизации суммарной интенсивности отказов ЭМТК в условиях воздействия только тепловых факторов.

Существует множество алгоритмов для решения задачи размещения. Но в большинстве эти алгоритмы ориентированы на проектирование ЭА двумерной компоновки (печатные платы, МСб, ИМС). Для учета особенностей трехмерной компоновки требуется разработка новых алгоритмов. Автоматизация «теплового» размещения в ЭМТК может быть реализована с помощью генетических алгоритмов (ГА). Данный класс алгоритмов основан на имитации биологической эволюции и реализует случайно-направленный поиск на множестве решений.

Генетические алгоритмы были предложены в 60-х годах прошлого столетия Джоном Холландом. В дальнейшем идеи Холланда были развиты в трудах Д. Годдберга, К. Де Йонга и др. Значительный вклад в решение задач эволюционного моделирования внесли Батищев Д.И., Букатова И.Л., Курейчик В.В, Курейчик В.М., Мухачева Э.А, Норенков И.П, Филиппова A.C. и др.

ГА зарекомендовали себя во многих задачах структурного синтеза, которые подразумевают поиск оптимального решения. К таким задачам относятся компоновка элементов по блокам, двумерное размещение элементов на печатных платах и БИС, раскрой и упаковка и др. Для перечисленных задач на достаточном уровне достигнута формализация и проведено множество исследований, широко освещенных в публикациях. При этом задача «теплового» размещения разногабаритных элементов в ЭМТК является новой и мало исследованной.

Отсюда становится очевидной актуальность разработки новых методик и алгоритмов для автоматизации конструкторского проектирования ЭМТК. Потребность в исследовании вопроса «теплового» размещения элементов в ЭМТК определила цель данной диссертационной работы.

Целью работы является разработка методики решения задачи «теплового» размещения в ЭМТК для реализации их автоматизированного проектирования и повышения показателей надежности ЭМТК на этапе проектирования.

Для достижения поставленной цели в работе решались следующие задачи:

1. Разработка математической модели теплового распределения в ЭМТК на основе анализа их конструктивных особенностей.

2. Определение способа получения оценки формируемых решений на основе выбранного критерия оптимизации.

3. Разработка проблемно-ориентированных компонентов генетического поиска, к которым относятся структура особи, способ ее кодирования, модифицированные генетические операторы.

4. Разработка модификации генетического алгоритма, позволяющей наиболее эффективно решать задачу размещения элементов в ЭМТК.

5. Экспериментальная оценка эффективности разработанного генетического алгоритма.

Методы исследования. В работе используются основные положения математической физики (теория тепломассообмена), численные методы для

расчета теплового распределения в конструкции ЭМТК; элементы теории множеств; методы генетического поиска; объектно-ориентированное программирование для разработки программного приложения, реализующего ГА. Для анализа эффективности разработанных алгоритмов применяется численный эксперимент.

Научная новизна работы заключается в следующем:

1. Разработана методика автоматизированного размещения элементов в электронных модулях трехмерной компоновки на основе теплового критерия.

2. Генетический алгоритм впервые применяется для решения такой новой и малоисследованной прикладной задачи, как «тепловое» размещение разногабаритных элементов в ЭМТК.

3. Предложен способ кодирования решения задачи в многохромосомную структуру, где в общем случае отдельные хромосомы гетероморфны (отличаются размерами) и содержат двойной набор аллелей.

4. Предложена новая модификация генетического алгоритма, основанная на разделении множества потенциальных решений задачи на отдельные виды. Показана эффективность предложенной модификации.

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

Реализация и внедрение результатов работы. Результаты диссертационной работы использованы в проектной деятельности ОАО Владимирское конструкторское бюро радиосвязи, ОАО Автогаз ассоциации Спектр-Групп и в учебном процессе кафедры проектирования и технологии производства электронной аппаратуры МГТУ им. Н.Э. Баумана.

Апробация работы и публикации. Основные положения и результаты работы были доложены на 9, 10 и 11-й Молодежных международных научно-технических конференциях Наукоемкие технологии и интеллектуальные системы (Москва, 2007, 2008, 2009), 15-й Международной научно-технической конференции студентов и аспирантов Радиоэлектроника, электротехника и энергетика (Москва, 2009). По теме диссертации опубликовано 8 работ, из них 4 в журналах, рекомендованных ВАК, в том числе получено 1 свидетельство о государственной регистрации программы для ЭВМ.

Структура и объем работы. Диссертация состоит из введения, четырех глав с выводами, заключения с общими выводами по работе, списка литературы и приложения. Работа изложена на 132 страницах машинописного текста, и содержит 50 рисунков. Библиографический список включает 101 наименование.

СОДЕРЖАНИЕ РАБОТЫ

Во введении показана актуальность темы диссертационной работы, поставлена цель работы, сформулированы задачи исследования, отражена научная новизна, дано общее описание выполненной работы.

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

Теоретически наибольшая плотность компоновки и самые короткие межсоединения могут быть достигнуты с помощью конструкторско-технологического метода трехмерной компоновки. Большинство существующих сегодня вариантов трехмерной компоновки используют схожие конструктивы -набор микроплат, собирающихся параллельно друг другу в пакет (рис. 1). На микроплатах или внутри них размещены бескорпусные элементы. Проводники наносятся как на лицевые поверхности микроплат, так и на торцы пакета из микроплат. Сборка из микроплат помещается в корпус.

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

Для расчета температур элементов требуется проведения теплового анализа ЭМТК. В зависимости от особенностей объектов теплового анализа применяются различные математические модели - модели с сосредоточенными параметрами, одномерные и многомерные модели. Поскольку в ЭМТК элементы распределены в объеме модуля, то наиболее целесообразным является использование многомерной (трехмерной) модели теплового распределения.

- Корпус : Микроплаты Проводники

. Электронный элемент Внешние выводы

Рис.1. Электронный модуль трехмерной компоновки

Всю совокупность алгоритмов размещения можно разделить на следующие основные группы: алгоритмы, основанные на точных математических моделях задачи размещения; конструктивные алгоритмы начального размещения; итерационные алгоритмы; алгоритмы, реализующие физические или биологические модели. В настоящее время большое внимание уделяется разработке методов, относящихся к последней группе. К одному из ; таких методов относят генетические алгоритмы (ГА).

ГА, являясь случайно-направленными методами поиска на множестве решений, эффективно используются для решения ЫР-полных задач САПР. Гибкость структуры генетического алгоритма, отсутствие жесткой детерминированности позволяют организовать такую процедуру поиска, которая обеспечивает во многих случаях получение лучшего результата по сравнению с другими методами. Кроме того ГА дают возможность осуществлять поиск в неметризуемом пространстве параметров, содержат элементы адаптации и распараллеливания процессов в ходе своего выполнения.

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

Во второй главе определен набор исходных данных, необходимых для выполнения размещения по «тепловому» критерию; предложена структура и способ кодирования/декодирования особи; разработана математическая модель теплового распределения в ЭМТК; определен вид функции пригодности особи и способ ее расчета; разработаны генетические операторы, соответствующие структуре особи.

Для реализации генетического поиска наилучшего варианта «теплового» размещения требуется следующий набор исходных данных: множество электронных элементов, сгруппированных по микроплатам ЭМТК; габаритные размеры микроплат и элементов, некоторые метрические параметры конструкции ЭМТК; величины мощностей, рассеиваемых элементами в виде тепла; величины теплопроводностей материалов микроплат и элементов; тепловые граничные условия на торцах ЭМТК; параметры элементов, используемые для расчета интенсивностей отказов.

Специфика решаемой задачи накладывает отпечаток на структуру особи, вид функции пригодности и генетические операторы.

При разработке способа кодирования потенциального решения (особи) определяется необходимый состав управляемых параметров. Варьирование значениями этих параметров и составляет суть генетического поиска. Учитывая особенности типовой конструкции ЭМТК, можно сказать, что к управляемым

параметрам следует отнести данные о взаимном расположении группы элементов в пределах одной микроплаты (координаты элементов), а также данные о порядке следования микроплат в пакете при сборке электронного модуля. Тогда каждая особь должна содержать:

• п наборов генов, где п - количество микроплат с элементами, а каждый из этих наборов определяет состав элементов и их взаимное расположение в пределах своей микроплаты;

• один набор генов, определяющий последовательность расположения микроплат в пакете.

Будем называть каждый из набора генов, определяющих расположение элементов, Е-хромосомой, а набор генов, отвечающий за порядок микроплат -М-хромосомой. Таким образом, каждая особь состоит из одной М-хромосомы и из п Е-хромосом.

Задачу размещения элементов в объеме ЭМТК можно разделить на несколько подзадач двумерного размещения групп элементов внутри каждой микроплаты. Для: реализации двумерного размещения предлагается использовать метод размещения «левый нижний утол». Он относится к безуровневым стратегиям формирования упаковок прямоугольных блоков в задаче раскроя-упаковки (Packing Problem) и не является собственно методом поиска оптимального размещения. Вместе с этим он позволяет эффективно размещать разногабаритные элементы без привязки к фиксированным позициям на микроплате, что характерно для ЭМТК. Особенностью данного метода является то, что каждый размещенный элемент не может быть сдвинут влево и вниз. Для формирования корректных вариантов размещения с помощью данного метода вводятся геометрические ограничения в виде условий ортогонального размещения прямоугольников, описывающих контуры элементов, и отсутствия пересечения э тих прямоугольников.

В методе размещения «левый нижний угол» элементы размещаются последовательно, друг за другом. Поэтому в хромосоме достаточно хранить информацию о последовательности размещения элементов. На рис. 2 представлен пример топологии, полученной в результате размещения последовательности элементов A, D, С, F, В, Е, среди которых А, В, F, Е должны иметь горизонгальную (относительно длинной стороны элемента), а элементы D и С вертикальную ориентацию. В качестве стратегии выбора вакантного места использовано размещение в точку, которая имеет наименьшую Y-координату среди всех прочих вакантных мест.

Пусть каждому гену в Е-хромосоме

Рис. 2. Принцип размещения «левый нижний угол»

соответствует один элемент из группы. Тогда аллелем данного гена является имя этого элемента, а локус этого гена зависит от порядка размещения элемента. Для учета ориентации элемента введем дополнительный аллель для каждого гена -аллель ориентации. Значение аллеля ориентации равно «О», если элемент ориентирован вертикально, и равно «1», если элемент ориентирован горизонтально. На рис. 3 показана Е-хромосома для приведенного выше примера.

В структуре М-хромосомы используются только один тип аллелей - аллели имен микроплат. Порядок генов М-хромосомы определяет порядок микроплат в ЭМТК. На рис. 4 представлен пример М-хромосомы для ЭМТК, состоящего из 6-ти микроплат.

Аллели имен . Аллели ориентации

А D С F В £

1 0 0 1 1 1

2 4 1 3 б 5

Рис. 3. Е-хромосома Рис. 4. М-хромосома

Учитывая особенность конструкции ЭМТК, важно отметить, что хромосомы, составляющие особь будут иметь, как правило, относительно невысокую длину (не более 30-40 генов), что объясняется распределением всего множества элементов по отдельным микроплатам.

Процесс декодирования применяется для «расшифровки» имеющихся особей и заключается в размещении элементов на микроплатах. В результате декодирования определяются значения управляемых параметров - координат (X,Y,Z) левых нижних углов «лицевой» части элементов. Данные о размещении элементов в объеме ЭМТК используются для оценки качества особи согласно функции пригодности (fitness function).

Решение задачи «теплового» размещения заключается в минимизации значения функции пригодности (ФП) особи. Очевидно, что использование «теплового» критерия подразумевает расчет распределения температурного поля внутри ЭМТК на основе известных геометрических и физических параметров микроштат и элементов, выделяемых мощностей элементов и заданных, граничных условий. Расчет температурного распределения базируется на трехмерном стационарном линейном механизме переноса тепла в твердых телах (уравнение теплопроводности).

Поскольку математический расчет модели, которая наиболее полно и точно описывает температурное распределение внутри ЭМТК, требует больших затрат машинного времени, был принят ряд допущений, упрощающих в определенной степени математическую модель. К ним относятся изотропность матералов микроплат и элементов, идеальный тепловой контакт между соприкасающимися частями ЭМТК и др. Тепловая модель ЭМТК представляет собой параллелепипед, габариты которого совпадают с габаритами пакета микроплат. Между микроплатами присутствуют слои электроизоляционного материала. В параллелепипед пакета микроплат «вкраплены» параллелепипеды меньшего

размера - электронные элементы, обладающие теплопроводностью и являющиеся объемными источниками тепла (рис. 5). Математическая модель теплового распределения включает в себя систему уравнений теплопроводности для всех точек пространства внутри ЭМТК, условий непрерывности тепловых потоков и равенства температур на границе двух тел и набора граничных условий на торцах ЭМТК. Разработанная модель является применимой к большинству конструктивных вариантов реализации ЭМТК.

tfi

~ ¡1

Д.

Электронные элементы

Микроплаты

Рис. 5. Тепловая модель ЭМТК. Срез в плоскости ЧЪ

Расчет модели осуществляется с помощью метода конечных разностей (МКР). Выбор именно этого метода, по сравнению, например, с методом конечных элементов, объясняется следующими причинами. Во-первых, МКР является более простым в реализации и требует меньших временных затрат. Во-вторых, объект (ЭМТК), «разбиваемый» на элементарные объемы, имеет прямолинейные границы внешних и внутренних областей, и поэтому аппроксимации с помощью МКР оказывается достаточно.

По результатам расчета температурного распределения в ЭМТК находятся максимальные значения температуры каждого элемента. Далее на основе этих значений, а также ряда других исходных данных, для каждого элемента рассчитывается значение интенсивности отказов л,. В общем случае дня всех электронных элементов (транзисторы, диоды, кристаллы микросхем, резисторы, конденсаторы) интенсивность отказов имеет экспоненциальную зависимость от температуры. Суммарное значение всех интенсивностей отказов, помноженное на ряд коэффициентов, составляет общую интенсивность отказов ЭМТК и принимается за значение ФП конкретной особи:

L/=i

•( 1+0.2 Кву)-КФ-Кк-К{

ОБ,

где Key - коэффициент, учитывающий область применения модуля, Кф — коэффициент, учитывающий функциональность модуля, Кк - коэффициент

качества модуля, Коб - коэффициент обучения (освоенности производства). Таким образом, решаемая задача поиска наилучшего теплового размещения элементов состоит в поиске наименьшего значения функционала Я2 и является задачей однокритериальной оптимизации.

Отметим, что принятая структура особи и предложенный способ оценки решения подходит для большинства существующих вариантов реализации ЭМТК. Этим обеспечивается определенная универсальность разрабатываемой методики «теплового» размещения элементов.

К основным и наиболее используемым генетическим операторам относят кроссовер, мутацию и селекцию. Принятая структура особи во многом влияет на реализацию кроссовера и мутации как операторов, модифицирующих генную информацию особи. В связи с особенностями структуры особи были разработаны модифицированные операторы, использующие механизмы обычных операторов кроссовера и мутации, но отличающиеся своим применением к различным частям особи.

Кроссовер М-хромосомы (М-кроссовер) представляет собой оператор кроссовера, применяющийся к М-хромосомам двух родительских особей и формирующий две особи-потомка. В зависимости от количества точек разрыва М-кроссовер может быть одноточечным, двухточечным, многоточечным и однородным (универсальным). Так в случае одноточечного М-кроссовера первый потомок получает набор генов слева от точки разрыва первого родителя, и набор генов справа от точки разрыва второго родителя.

В результате рекомбинации генов некоторые аллели потомков могут повторяться, а некоторые в этом случае будут наоборот отсутствовать. В этом случае производится процедура коррекции генов методом РМХ (Partially Matched Crossover). После коррекции генов все аллели в пределах одной хромосомы становятся уникальными.

Особенность М-кроссовера заключается в том, что у потомков наследуются не только гены М-хромосом, но и происходит наследование соответствующих Е-хромосом. Например, при одноточечном кроссовере у первого потомка в М-хромосоме слева от точки разрыва будут идти номера Е-хромосом (микроплат) первого родителя, а справа от точки разрыва - номера Е-хромосом второго родителя.

Кроссовер Е-хромосомы (Е-кроссовер) представляет собой кроссовер, применяющийся к паре одноименных Е-хромосом двух родительских особей. Формирование потомков происходит аналогично М-кроссоверу. Но при наследовании генов наследуются как аллели имени, так и аллели ориентации. При необходимости выполняется коррекция генов методом РМХ.

Кроссовер особей (F-кроссовер) представляет собой сочетание одного М-кроссовера для М-хромосом родительских особей и набора Е-кроссоверов для всех соответствующих Е-хромосом родительских особей. Результатом F-кроссовера являются два потомка, которые далее подвергаются мутациям.

Мутация М-хромосомы (М-мутация) представляет собой вариант мутации, когда два случайно выбранных гена в М-хромосоме с вероятностью Рт меняются местами. Мутация имен Е-хромосомы (ЕЭД-мутация) аналогична М-мутации, но применяется с вероятностью Рт к конкретной Е-хромосоме особи и производит обмен как аллелей имен, так и аллелей ориентации. Мутация ориентаций Е-хромосомы (ЕО-мутация) с вероятностью Рт изменяет ориентацию одного случайно выбранного элемента в Е-хромосоме. Если элемент имел вертикальную ориентацию в микроплате, его ориентация меняется на горизонтальную, и наоборот.

Необходимость использования описанных выше генетических операторов объясняется следующим. Во-первых, элементами популяции являются не одиночные хромосомы, а многохромосомные особи. Классические операторы кроссовера и мутации применяются к одиночным хромосомам, тогда как в нашем случае рассматривается скрещивание и мутация целых особей. Это требует описания правил, по которым происходит изменение хромосом как составных частей особи. Такие правила и реализуются в виде предложенных генетических операторов. Во-вторых, значение гена М-хромосомы определяется одним аллелем, а для гена Е-хромосомы - двумя. Такие различия в структуре генов делают необходимым разделение генетических операторов на Е-операторы и М-операторы. Очевидно, что в этом случае реализация Е-операторов будет несколько отличаться от реализации М-операторов, тогда как использование классических операторов кроссовера и мутации не позволит в полной мере реализовать необходимые механизмы модификации особи.

Помимо предложенных операторов кроссовера и мутации для реализации ГА применялись известные виды оператора селекции («колесо рулетки», турнирная селекция, элитная селекция, равновероятностный выбор). Оператор редукции использовался для поддержания постоянного размера популяции за счет удаления необходимого количество особей с наихудшими значениями ФП. Популяция, полученная после редукции, представляла собой очередное поколение особей.

На основе разработанных модификаций генетических операторов возможно построить любую из описанных в главе 1 разновидностей ГА для решети задачи «теплового» размещения элементов в ЭМТК.

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

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

Эффективность каждой конкретной реализации генетического алгоритма зависит от ряда составляющих - от вида применяемых генетических операторов,

от параметров генетических операторов, от размера популяции особей, от длины хромосом.

Для исследования влияния вероятности мутации на эффективность генетического поиска было принято, что вероятности М-, ЕО- и ЕК-мутаций равны между собой. Исследование показало, что существует такой диапазон вероятностей мутации, при котором генетический алгоритм обеспечивает наилучшее приближение к известному глобальному экстремуму по сравнению с другими вероятностями мутации. Исследование проводилось для разных исходных данных и с рассмотрением различных размеров популяций. Для всех рассмотренных условий этот диапазон приблизительно совпадал и составлял {0,05-0,2}.

Для оценки влияния оператора кроссовера рассматривались одноточечный (РС1), двухточечный (РС2), многоточечный (РС1чГ) и равномерный (РСЦ) Б-кроссоверы. В результате экспериментов выявлено, что на эффективность кроссовера влияют такие параметры, как длина хромосомы, размер популяции и вероятность мутации. При длинах хромосом более 15-20 генов, размере популяции не менее 10 особей и вероятности мутации 0.1 наилучшую эффективность показывает многоточечный кроссовер, а наихудшую одноточечный (рис. б). Уменьшение длины хромосом приводит к «выравниванию» эффекгивностей рассмотренных видов кроссовера. Увеличение интенсивности мутации (до 0,4-0,5) с сокращением размера популяции (менее 10) делает одноточечный кроссовер более эффективным по сравнению с другими кроссоверами.

Количество обращений к ФП

Рис. 6. Результаты генетического поиска при сравнении операторов

кроссовера

Экспериментальные исследования операторов селекции показали, что главным образом на эффективность того или иного вида селекции влияет численность популяции. В эксперименте сравнивались равновероятностная селекция (RND), селекция «колесо рулетки» (R.W), турнирная селекция (TRN) и элитная селекция (ELT). При размере популяции более 10 особей элитная и турнирная селекция обладают примерно равной эффективностью и обеспечивают лучшее приближение к известному глобальному минимуму, чем «колесо рулетки» и равновероятностная селекция (рис. 7). Уменьшение размера популяции до 8 особей Приводит к заметному выравниванию эффективностей рассматриваемых видов селекции.

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

Время, сек

Рис. 7. Результаты генетического поиска при сравнении операторов селекции

В четвертой главе предложена модификация генетического алгоритма, основанная на выделении отдельных видов особей из общей популяции; приводятся результаты экспериментального сравнения эффективности предложенной модификации с рядом других видов генетических алгоритмов применительно к задаче «теплового» размещения в ЭМТК.

Принятая структура особи позволяет предложить архитектуру ГА, несколько отличающуюся от рассмотренных в первой главе модификаций ГА. Основная идея нового предлагаемого подхода заключается в разделении всех возможных

особей на отдельные виды. Отсюда происходит и название новой предлагаемой модификации ГА - видовой генетический алгоритм (ВГА).

Под видом, в зависимости от смыслового контекста, понимается:

1)либо область решений задачи, в которой все возможные особи имеют одинаковые М-хромосомы,

2) либо некоторая подпопуляция особей с одинаковыми М-хромосомами.

Начальная популяция состоит из К видов, каждый из которых содержит N

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

По истечении Т поколений на основе значений ФГ1 особей текущей популяции конкретного вида делается заключение о приближении этого вида к состоянию стагнации (вырождения), что соответствует попаданию в локальный экстремум. Если признано, что виду «угрожает» стагнация, то производится вмешательство в естественный процесс эволюционирования этого вида - вид модифицируется. Модификация вида состоит в изменении М-хромосомы для всех «ныне живущих» особей данного вида.

После завершения одного контрольного периода начинается очередной контрольный период. Если вид не был модифицирован после предыдущего контрольного периода, то в новом контрольном периоде он продолжает свою эволюцию без изменений.

Для реализации ВГА применяются варианты генетических операторов, описанных выше. Так внутривидовая эволюция представляет собой обычный ГА с элементами локального поиска. Для реализации внутривидового ГА используется Е-кроссовер, а локальный поиск реализован в виде повторений EN-и ЕО-мутаций, проводимых для потомков кроссовера, пока эти потомки не улучшат свои ФП. Механизм модификации видов может быть реализован с помощью М-мутации, а также с помощью М-кроссовера, если использовать два «выродившихся» вида.

При решении задач синтеза экстремальное значение, как правило, неизвестно. Поэтому оценка эффективности разрабатываемой модификации генетического алгоритма может быть дана только в сравнении с результатами решения задачи альтернативными ГА. Для сравнительной оценки предложенного видового генетического алгоритма (KGA) были использованы простой ГА (CGA), параллельный ГА (PGA), метагенетический алгоритм (MGA) и смешанный эволюционный метод (ММЕМ).

В результате серии экспериментов с различными исходным данными выявлено, что наилучшее приближение к известному глобшхьному оптимуму за меньшее время достигается с помощью видового ГА (рис. 8). Из графика также

видно, что параллельный ГА быстро сходится на первой половине эволюции, но затем проявляет признаки попадания в локальный оптимум и проходит близко с кривой простого ГА. Эффективность ММЕМ заметно зависит длины хромосом в особях. При длине хромосом более 30 генов ММЕМ превосходит параллельный и простой ГА. Метагенетический алгоритм показал медленную сходимость вследствие особенностей своей архитектуры (большие временные затраты на оценку конфигурационной популяции), однако по степени приближения к известному глобальному оптимуму в итоге превзошел CGA, PGA и ММЕМ.

На основе экспериментальных данных также произведена оценка эффективности процесса «теплового» размещения как способа повышения надежности ЭМТК. Так при использовании ВГА удается снизить интенсивность отказов ЭМТК в среднем на 10-15% по сравнению с вариантом размещения, полученным случайным образом.

В завершении главы в общем виде сформулирована методика решения задачи автоматизированного «теплового» размещение элементов в ЭМТК на основе генетического алгоритма.

В заключении сделаны общие выводы по проделанной работе и полученных результатах, приведены соответствующие рекомендации.

В приложении приводятся основные данные по разработанной программе для ЭВМ: блок-схема алгоритма работы, среда разработки, количество операторов, требуемый объем памяти, описание выходных данных и др.

Время, сек

Рис. 8. Результаты генетического поиска при сравнении различных ГА

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Главным научным результатом работы является разработка методики автоматизации размещения по тепловому критерию в электронных модулях трехмерной компоновки на базе генетического алгоритма. Данная методика позволяет производить поиск варианта размещения, который обеспечивает минимальную интенсивность отказов ЭМТК за счет уменьшения перегревов элементов.

Основные научные теоретические и практические результаты работы состоят в следующем:

1. Разработана математическая модель теплового распределения в ЭМТК, учитывающая конструктивные особенности ЭМТК. Для расчета температур элементов в ЭМТК целесообразно использовать метод конечных разностей.

2. Разработаны компоненты генетического алгоритма для задачи размещения. Кодированное решение задачи (особь) представляет собой многохромосомную структуру, где в общем случае отдельные хромосомы гетероморфны (отличаются размерами) и содержат двойной набор аллелей. Предложенные модификации генетических операторов кроссовера и мутации позволяют работать с многохромосомной структурой особи.

3. Разработана новая модификация генетического алгоритма - видовой генетический алгоритм. Экспериментальная оценка эффективности ВГА применительно к задаче теплового размещения показала, что он по сравнению с рядом других рассмотренных генетических алгоритмов обеспечивает лучшую степень приближения к глобальному экстремуму за меньшее время работы. Отсюда следует, что ВГА целесообразно использовать для теплового размещения в ЭМТК.

4. Ожидаемое снижение интенсивности отказов ЭМТК за счет применения ВГА составляет около 10-15% по отношению к варианту размещения элементов, полученному случайным образом.

5. Экспериментальное исследование ряда генетических алгоритмов для решения задачи теплового размещения в ЭМТК показало что:

• Наибольшая эффективность генетического поиска обеспечивается при значениях вероятности мутации в диапазоне {0,05-0,2}.

• При размере популяции более 10 особей наиболее эффективными среди рассмотренных видов селекции являются турнирная и элитная.

• Количество точек разрыва мало влияет на эффективность кроссовера при малой длине хромосомы, следовательно, применение смешанного эволюционного метода обосновано при длинах хросомосом более 30-40 генов.

• Применение метагенетического алгоритма обосновано для случаев, когда время оценки ФП одной особи является достаточно малым, либо когда нет жестких ограничений на время работы алгоритма.

• Выбор большого размера популяции (более 30-40 особей) обоснован в случае отсутствия требований к времени работы алгоритма, а также в случае

необходимости получения решения, обладающего высокой степенью приближения к глобальному оптимуму.

РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Новиков И.С. Автоматическое размещение разногабаритных электронных элементов посредством генетического поиска с миграцией // Проектирование и технология электронных средств. - 2007. - №1. - С. 33-38.

2. Новиков И.С, Шахнов В.А. Оптимизация конструкции электронных модулей трехмерной компоновки по тепловому критерию // Проектирование и технология электронных средств. - 2007. - №3. - С. 31-37.

3. Новиков И.С, Шахнов В.А. Теоретические аспекты оптимизации теплового режима трехмерных электронных модулей посредством генетического алгоритма // Вестник МГТУ им. Н.Э. Баумана. Приборостроение. - 2009. - №1. — С. 112-123.

4. Новиков И.С, Шахнов В.А. Практическая реализация оптимизации теплового режима трехмерных электронных модулей посредством генетического алгоритма // Вестник МГТУ им. Н.Э. Баумана. Приборостроение. - 2009. - №2. -С. 62-71.

5. Новиков И.С. Программное решение по автоматизации проектирования электронной аппаратуры трехмерной компоновки // Наукоемкие технологии и интеллектуальные системы 2006: Сб. науч. трудов 8-й Молодежи, научно-техн. конф. -М., 2006. - С. 74-77.

6. Новиков И.О. Формирование конструкций электронных модулей трехмерной компоновки, оптимальных по тепловому критерию с помощью генетического алгоритма // Радиоэлектроника, электротехника и энергетика: Тез. докл. 15-й Междунар. научно-техн. конф. студентов и аспирантов; в 3-х т. -М., 2009.-Т1.-С. 303-304.

7. Новиков И.С. Генетический метод синтеза размещения элементов в трехмерных электронных модулях // Наукоемкие технологии и интеллектуальные системы 2009: Сб. науч. трудов 11-й Молодежи, международн. научно-техн. конф. - М., 2009. - С. 170-176.

8. Автоматизация теплового размещения элементов в электронных модулях трехмерной компоновки: свидетельство о гос. регистрации программы для ЭВМ №2009612607 / И.С. Новиков - заяв. №2009611544 от 08.04.09; зарег. 22.05.09.

Подписано к печати 9.11.09. Заказ №682 Объем 1,0 псч.л. Тираж 100 экз. Типография МГТУ им. Н.Э. Баумана 105005, Москва, 2-я Бауманская ул., д.5 (499) 263-62-01

ВВЕДЕНИЕ.

ГЛАВА 1. КОНСТРУКТОРСКО-ТЕХНОЛОГИЧЕСКАЯ БАЗА И АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ ЭЛЕКТРОННОЙ АППАРАТУРЫ.

1.1. Конструкторско-технологические методы компоновки электронных узлов.

1.2. Модели теплового режима приборов и методы их расчета.

1.3. Алгоритмы решения задачи размещения.

1.4. Генетические алгоритмы и их разновидности.

1.5. Выводы.

ГЛАВА 2. ГЕНЕТИЧЕСКИЙ АЛГОРИТМ РАЗМЕЩЕНИЯ ТЕПЛОВЫДЕЛЯЮЩИХ ЭЛЕМЕНТОВ.

2.1. Варианты автоматизированного размещения тепловыделяющих элементов.

2.2. Исходные данные генетического алгоритма.

2.3. Разработка структуры и способа декодирования особи.

2.4. Вычисление функции пригодности.

2.4.1. Математическая модель теплового распределения.

2.4.2. Метод расчета математической модели теплового распределения

2.4.3. Расчет значения функции пригодности.

2.5. Разработка модификаций генетических операторов.

2.5.1. Операторы кроссовера.

2.5.2. Операторы мутации.

2.6. Простой генетический алгоритм размещения.

2.7. Выводы.

ГЛАВА 3. ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗМЕЩЕНИЯ.

3.1. Оценка влияния вероятности мутации.

3.2. Оценка влияния типа кроссовера.

3.3. Оценка влияния типа селекции.

3.4. Оценка влияния размера популяции.

3.5. Выводы.

ГЛАВА 4. РАЗРАБОТКА МОДИФИКАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА.

4.1. Видовой генетический алгоритм.

4.2. Экспериментальная оценка эффективности генетических алгоритмов.

4.3. Выводы.

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

Одним из решений проблемы может являться особый конструкторско-технологический метод - метод трехмерной компоновки аппаратуры [73-76]. Его суть заключается в построении ЭА с размещением разногабаритных бескорпусных элементов и соединений между ними не на плоскости печатной платы, а в трехмерном пространстве многослойного электронного модуля (далее - электронные модули трехмерной компоновки;, ЭМТК). Создание ЭА на базе трехмерной компоновки требует новых исследований. Большое количество работ в этом направлении ведется в западных странах. Существует ряд зарубежных компаний, занимающихся разработкой и производством трехмерных модулей.

Очевидно, что проведение проектных работ по созданию новых образцов электронных узлов, таких как ЭМТК, требует значительных финансовых и временных затрат, привлечение интеллектуальных ресурсов. Существенного уменьшения времени цикла проектирования и подготовки производства, увеличения его гибкости и качества можно добиться благодаря внедрению автоматизированных систем управления и проектирования.

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

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

Для краткости задачу автоматизированного размещения дискретных источников тепла будем называть задачей «теплового» размещения или размещением по тепловому критерию. Эту задачу сформулируем как поиск такого варианта размещения элементов, при котором снижение надежности ЭМТК, вызванное перегревом этих элементов, минимально.

На сегодняшний, день разработано, множество алгоритмов [68, 78, 81], позволяющих решать задачу размещения в соответствии, с различными критериями оптимальности. В большинстве эти алгоритмы ориентированы на проектирование ЭА двумерной компоновки (печатные платы, микросборки, интегральные микросхемы). Для учета особенностей трехмерной компоновки требуется разработка новых методов. Автоматизация «теплового» размещения в ЭМТК может быть реализована с помощью генетических алгоритмов (ГА) [5, 13, 93, 95]. Данный класс алгоритмов основан на имитации биологической эволюции и реализует случайно-направленный поиск на множестве решений. Это отличает ГА от большинства других существующих алгоритмов, для которых характерны строго детерминированный характер поиска и оптимизация единственного решения. Несмотря на то, что ГА не гарантируют нахождения глобального оптимума, их особенности позволяют за приемлемое время получать высококачественные решения.

Генетические алгоритмы были предложены в 60-х годах прошлого столетия Джоном Холландом и получили всеобщее признание после выхода в 1975 году его книги «Adaptation in Natural and Artificial Systems». В дальнейшем идеи Холланда были развиты в трудах Д. Голдберга, К. Де Йонга и др. Значительный вклад в решение задач эволюционного моделирования внесли Батищев Д.И., Букатова И.Л., Курейчик В.В, Курейчик В.М., Мухачева Э.А, Норенков И.П., Филиппова А.С. и др.

ГА хорошо зарекомендовали себя в задачах структурного синтеза, которые подразумевают поиск оптимального решения и, как правило, являются NP-полными. К таким задачам относятся компоновка элементов по блокам, двумерное размещение элементов на печатных платах и БИС, синтез топологии сети соединений, раскрой и упаковка, синтез расписаний, маршрутизация транспортных средств и др. Для перечисленных задач на достаточном уровне достигнута формализация и проведено множество исследований, широко освещенных в публикациях. При этом задача «теплового» размещения разногабаритных элементов в ЭМТК является новой и мало исследованной. В большей мере, это следствие того,, что ЭМТК появились на1 рынке относительно недавно, и их разработка и производство еще не вышло на массовый уровень. И как следствие, еще отсутствует хорошо проработанная теоретико-математическая база, на которой бы основывались САПР модулей трехмерной компоновки. Отсюда становится очевидной актуальность разработки новых методов и алгоритмов для автоматизации конструкторского проектирования ЭМТК. Потребность в исследовании вопроса оптимизации размещения элементов в ЭМТК определила цель данной диссертационной работы.

Целью работы является разработка методики решения задачи «теплового» размещения в ЭМТК для реализации их автоматизированного проектирования и повышения показателей надежности ЭМТК на этапе проектирования.

Для достижения поставленной цели в работе решались следующие задачи:

1. Разработка математической модели теплового распределения в ЭМТК на основе анализа конструктивных особенностей ЭМТК.

2. Определение способа получения оценки формируемых решений на основе выбранного критерия оптимизации.

3. Разработка проблемно-ориентированных компонентов генетического поиска, к которым относятся структура особи, способ ее кодирования, модифицированные генетические операторы.

4. Разработка модификации генетического алгоритма, позволяющей наиболее эффективно решать задачу размещения элементов в ЭМТК.

5. Экспериментальная оценка эффективности разработанного генетического алгоритма.

В процессе решения поставленных задач использовались основные положения математической физики (теория тепломассообмена), численные методы для расчета теплового распределения в ЭМТК; элементы теории множеств; методы генетического поиска; объектно-ориентированное программирование для разработки программного приложения, реализующего ГА. Для анализа эффективности разработанных алгоритмов применяется численный эксперимент.

Научная'новизна работы заключается в следующем:

1. Разработана методика автоматизированного размещения элементов в электронных модулях трехмерной компоновки на основе теплового критерия.

2. Генетический алгоритм впервые применяется для решения такой новой и малоисследованной прикладной задачи, как «тепловое» размещение разногабаритных элементов в ЭМТК.

3. Предложен способ кодирования решения задачи в многохромосомную структуру, где в общем случае отдельные хромосомы гетероморфны (отличаются размерами) и содержат двойной набор аллелей.

4. Предложена новая модификация генетического алгоритма, основанная на разделении множества потенциальных решений задачи на отдельные виды. Показана эффективность предложенной модификации.

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

Диссертация состоит из введения, четырех глав с выводами, заключения, списка литературы и приложения. Работа изложена на 132 страницах машинописного текста и содержит 50 рисунков. Библиографический список включает 101 наименование.

ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

Главным научным результатом работы является разработка методики автоматизации размещения по тепловому критерию в электронных модулях трехмерной компоновки на базе генетического алгоритма. Данная методика позволяет производить поиск варианта размещения, который обеспечивает минимальную интенсивность отказов ЭМТК за счет уменьшения перегревов элементов.

Основные научные теоретические и практические результаты работы состоят в следующем:

1. Разработана математическая модель теплового распределения в ЭМТК, учитывающая конструктивные особенности ЭМТК. Для расчета температур элементов в ЭМТК целесообразно использовать метод конечных разностей. (

2. Разработаны компоненты . генетического алгоритма для задачи размещения. Кодированное решение задачи (особь) представляет собой многохромосомную структуру, где в общем случае отдельные хромосомы гетероморфны (отличаются размерами) и содержат двойной набор аллелей. Предложенные модификации генетических операторов кроссовера и мутации позволяют работать с многохромосомной структурой особи.

3. Предложена новая модификация генетического алгоритма - видовой генетический алгоритм. Экспериментальная оценка эффективности ВГА применительно к задаче теплового размещения показала, что он по сравнению с рядом других рассмотренных генетических алгоритмов обеспечивает лучшую, степень приближения к глобальному экстремуму за меньшее время работы. Отсюда следует, что ВГА целесообразно использовать для теплового размещения в ЭМТК.

4. Ожидаемое снижение интенсивности отказов ЭМТК за счет применения ВГА составляет около 10-15% по отношению к варианту размещения элементов, полученному случайным образом.

5. Экспериментальное исследование ряда генетических алгоритмов для решения задачи теплового размещения элементов в ЭМТК показало что:

• Наибольшая эффективность генетического поиска обеспечивается при значениях вероятности мутации в диапазоне {0,05 - 0,2}.

• При размере популяции более 10 особей наиболее эффективными среди рассмотренных видов селекции являются турнирная и элитная.

• Количество точек разрыва мало влияет на эффективность кроссовера при малой длине хромосомы, следовательно, применение смешанного эволюционного метода обосновано при длинах хросомосом более 3040 генов.

• Применение метагенетического алгоритма обосновано для случаев, когда время оценки ФП одной особи является достаточно малым, либо когда нет жестких ограничений на время работы алгоритма.

• Выбор большого размера популяции (более 30-40 особей) обоснован в случае отсутствия требований к времени работы алгоритма, а также в случае необходимости получения решения, обладающего высокой степенью приближения к глобальному оптимуму.

1. Автоматизация теплового размещения элементов в электронных модулях трехмерной компоновки: свидетельство о гос. регистрации программы для ЭВМ №2009612607 / И.С. Новиков заявл. №2009611544 от 08.04.09; зарег. 22.05.09.

2. Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров: Учебное пособие. 2-е изд., доп. - М.:Издательство МЭИ, 2003.-596 с.

3. Антиликаторов А.Б., Макаров О.Ю., Муратов А.В. Математические модели элементов БИС для задачи размещения по тепловым критериям //Высокие технологии в технике, медицине и образовании: Межвуз. сб. науч. тр. Воронеж, 1996. - С. 59-63.

4. Арутюнян Н.М. Генетические методы структурного синтеза проектных решений: Дис. .канд. техн. наук. Москва, 2007. - 119 с.

5. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учеб. пособие. Воронеж: Воронеж, гос. техн. ун-т, 1995. - 69 с.

6. Батищев Д.И. Методы оптимального проектирования.: Учеб. пособие для вузов. М. Радио и связь, 1984. - 248 с.

7. Букатова И.Л. Эволюционное моделирование и его приложения. М.: Наука, 1979.-231 с.

8. Ведерникова О.Г. Метод решения задачи размещения, основанный на комбинировании методов эволюционной адаптации и имитации отжига //Известия ТРТУ. 1997. - №3. - С. 219 - 220. (Интеллектуальные САПР: Темат. вып.)

9. Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения): Учеб. пособие для вузов. — М.: Высшая школа, 2000.-266 с.

10. Галанин М.П., Щеглов И.А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: прямые методы. М., 2006. - 32 с. (Препринт ИПМ им. М.В. Келдыша РАН, №9).

11. Галанин М.П., Щеглов И.А. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространственных областей: итерационные методы М., 2006. — 35 с. (Препринт ИПМ им. М.В. Келдыша РАН, №10).

12. Гладков JI.A., Курейчик В.В., Курейчик В.М. Генетические алгоритмы /Под ред. В.М. Курейчика. 2-е изд., испр. и доп. - М.: ФизМатЛит, 2006. - 320 с.

13. Гладков JI.A. Применение нечетких генетических алгоритмов для решения оптимизационных задач проектирования // Нечеткие системы и мягкие вычисления НСМВ 2008: Тез. докл. Второй Всерос. научн. конф. -Ульяновск, 2008.-С. 138-146.

14. Дорошевич К.К., Дорошевич В.К., Телец В.А. Многокристальные модули новое конструктивно-технологическое направление в развитии комплектующих изделий // Технологическое оборудование и материалы. -1998.- №4,- С. 29-32.

15. Дульнев Г.Н., Парфенов В.Г., Сигалов А.В. Применение ЭВМ для решения задач теплообмена: Учеб. пособие для теплофизич. и теплоэнергетич. спец. вузов. М.: Высшая школа, 1990. - 207 с.

16. Дульнев Г.Н. Тепло- и массообмею в радиоэлектронной аппаратуре: Учебник для вузов по спец. «Конструирование и производство радиоаппаратуры». М:: Высшая школа, 1984. - 247 с.

17. Дульнев Г.Н(, Парфенов В1Г., Сигалов А.В. Методы расчета теплового режима приборов. -М.: Радио и связь, 1990. — 312 с.

18. Дульнев Г.Н., Тарновский Н.Н. Тепловые режимы электронной аппаратуры. Л.:Энергия, 1971. - 248 с.

19. Задачи двумерной упаковки: развитие генетических алгоритмов на базе смешанных процедур локального поиска оптимального решения / А.С. Мухачева и др. // Информационные технологии. 2001. - №9, приложение. - 24 с.

20. Зарубин B.C. Инженерные методы решения задач теплопроводности.- М.: Энергоатомиздат, 1983. 328 с.

21. Зарубин B.C. Математическое моделирование в технике: Учеб. для вузов /Под ред. B.C. Зарубина, А.П. Крищенко. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.-496 с.

22. Зенкевич О. Метод конечных элементов в технике. М.: Мир, 1975. -543 с.

23. Ищенко С.Н. Разработка и исследование генетических алгоритмов решения задач компоновки элементов и трассировки СБИС: Дис. .канд. техн. наук. Ростов-на-Дону, 2006. — 121 с.

24. Карапетян A.M. Автоматизация оптимального конструирования ЭВМ.- М.: Советское радио, 1973. 270 с.

25. Ковалев А.В., Коноплев Б.Г. Генетический алгоритм размещения разногабаритных блоков СБИС // Перспективные информационные технологии и интеллектуальные системы. 2001. - №5. — С. 71-87.

26. Кокотов В.З. Размещение электрорадиоэлементов на платах устройств рамочных конструкций с принудительным воздушным охлаждением //Информационные технологии. 2005. - №4. - С. 37-47.

27. Кокотов В.З. Модифицированный алгоритм «теплового размещения» электрорадиоэлементов на платах с четырехсторонним кондуктивным теплоотводом // Информационные технологии; 2006. — №4. - С. 2-8.

28. Кокотов В.З. Ускорение вычисления рядов в реализации алгоритма «теплового размещения» электрорадиоэлементов на платах счетырехсторонним кондуктивным теплоотводом // Информационные технологии. 2006. - №5. - С. 2-10.

29. Кокотов В.З. Закономерности «теплового размещения» электрорадиоэлементов на платах с четырехсторонним кондуктивным теплоотводом // Информационные технологии. 2006 . - №8. - С. 2-9.

30. Конструкторско-технологическое проектирование электронной аппаратуры: Учебник для вузов / К.И. Билибин и др.; Под общ. ред В.А. Шахнова. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 528 с.

31. Курейчик В.В. Перспективные архитектуры генетического поиска //Перспективные информационные технологии и интеллектуальные системы. -2000. №1. - С. 58-60.

32. Курейчик В.М. Генетические алгоритмы. Таганрог: Изд-во ТРТУ, 1998.-240 с.

33. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990.-351 с.

34. Лебедев Б.К., Меркухин Е.Н. Оптимизация тепловых характеристик при размещении элементов // Вопросы радиоэлектроники. Электронная вычислительная техника. 1988. - Вып. 11.— С.186-194.

35. Лебедев О.Б. Генетический алгоритм глобальной трассировки //Перспективные информационные технологии и интеллектуальные системы. -2000. №1. - С. 66-76.

36. Лебедев О.Б. Исследование и разработка генетических алгоритмов формирования топологии СБИС повышенной плотности: Дис. .канд. техн. наук. Таганрог, 1997. - 158 с.

37. Лебедев О.Б. Оптимальное размещение дискретных источников тепла с использованием метода генетического поиска // Перспективные информационные технологии и интеллектуальные системы. 2005. - №4. — С. 24-29.

38. Лебедев О.Б. Размещение на основе генетических процедур //Известия ТРТУ. -1996. №3. - С. 35-41. (Интеллектуальные САПР).

39. Линский B.C. Алгоритмическое проектирование вычислительных устройств. М.: ВЦ АН СССР, 1963.- 134 с.

40. Мартинсон Л.К., Малов Ю.И. Дифференциальные уравнения математической физики: Учебник для студентов вузов / Под ред. B.C. Зарубина, А.П. Крищенко. М.: Изд-во МГТУ им. Н.Э. Баумана, 1996. - 368 с.

41. Муратов А.В., Макаров О.Ю. Автоматизированное теплофизическое проектирование микроэлектронных устройств: Учеб. пособие. — Воронеж: Воронежский Гос. техн. ун-т., 1997. 92с.

42. Надёжность технических систем: Справочник / Под ред. И.А.Ушакова.- М.: Радио и связь, 1985. 608 с.

43. Надежность электрорадиоизделий: Справочник / С.Ф. Прытков и др. М.: 22 ЦНИИИ МО РФ, 2000. 507 с.

44. Никифоров A.M. Разработка параллельного генетического алгоритма размещения блоков ЭВА: Дисс. . .канд. техн. наук. Таганрог, 2002. - 172 с.

45. Новиков И.С. Автоматическое размещение разногабаритных электронных элементов посредством генетического поиска с миграцией //Проектирование и технология электронных средств. — 2007. — №1. — С. 33-38.

46. Новиков И.С. Генетический метод синтеза размещения элементов в трехмерных электронных модулях // Наукоемкие технологии и интеллектуальные системы 2009: Сб. науч. трудов 11-й Молодежи, междунар. научно-техн. конф. М., 2009. - С. 170-176.

47. Новиков И.С. Программное решение по автоматизации проектирования электронной аппаратуры трехмерной компоновки //Наукоемкие технологии и интеллектуальные системы 2006: Сб. науч. трудов 8-й Молодежи, научно-техн. конф. М., 2006. - С. 74-77.

48. Новиков И.С, Шахнов В.А. Оптимизация конструкции электронных модулей трехмерной компоновки по тепловому критерию //Проектирование и технология электронных средств. 2007. - №3. - С. 31-37.

49. Новиков И.С, Шахнов В.А. Теоретические аспекты оптимизации теплового режима трехмерных электронных модулей посредством генетического алгоритма // Вестник МГТУ им. Н.Э. Баумана. Приборостроение. 2009. -№1. - С. 112-123.

50. Новиков И.С, Шахнов В.А. Практическая реализация оптимизации теплового режима трехмерных электронных модулей посредством генетического алгоритма // Вестник МГТУ им. Н.Э. Баумана. Приборостроение. 2009. - №2. - С. 62-71.

51. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. 2-е изд., перераб. и доп. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002.-336 с.

52. Норенков И.П., Арутюнян Н.М., Бондаренко А.А. Сравнительный анализ эффективности эволюционных методов на примере задачи синтеза расписаний //Информационные технологии. — 2006. №5. - С. 16-20.

53. Норенков И.П., Арутюнян Н.М. Метагенетический алгоритм оптимизации и структурного синтеза проектных решений //Информационные технологии. 2007. - №3. — С. 10-13.

54. Норенков И.П., Арутюнян Н.М. Смешанный эволюционный метод //Информационные технологии. 2007. - №1. - С. 17-20.

55. Норенков И.П., Маничев В.Б. Основы теории проектирования САПР. М.: Высшая школа, 1990. - 336 с.

56. Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие / Под ред. Ю.Ю. Тарасевича. Астрахань: Издательский дом Астраханский университет, 2007. - 87 с.

57. Панченко Т.В. Сравнительный анализ эффективности генетических алгоритмов и алгоритма Метрополиса применительно к задачам физики твердого тела: Автореф. .канд. физ.-мат. наук. Астрахань, 2007. - 22 с.

58. Патент № 2 133 523. Трехмерный электронный модуль / ЗАО Техно-ТМзаявл. 03.11.1997; опубл. 20.07.1999. -Бюлл. №7.

59. Патент № 2 193 259. Способ изготовления трехмерного полимерного электронного модуля / Ю.Д. Сасов заявл. 31.10.2001; опубл. 20.11.2002. -Бюлл. №11.

60. Патент № 2 193 260. Способ изготовления многокомпонентного трехмерного электронного модуля / Ю.Д. Сасов заявл. 31.10.2001; опубл. 20.11.2002.-Бюлл. №11.t

61. Патент № 2 221 312. Способ изготовления трехмерного электронного модуля / Ю.Д. Сасов заявл. 30.09.2003; опубл. 22.12.2004. -Бюлл. №12.

62. Патент № 2 312 425. Трехмерный электронный модуль с шариковыми выводами / Ю.Д. Сасов заявл. 03.10.2006; опубл. 10.12.2007. Бюлл. №12.

63. Перспективы использования высокотеплопроводной керамики из нитрида алюминия в космическом приборостроении / В.И. Костенко и др.

64. Вопросы миниатюризации в современном космическом приборостроении: Тез. докл. выездного семинара. Таруса, 2004. - С. 250 - 256.

65. Петренко А.И., Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры. М.: Советское Радио, 1979. -256 с.

66. Проектирование прямоугольных упаковок на базе развития технологии блочных структур / Э.А. Мухачева и др. // Информационные технологии. 2007. - №1. - С. 20-29.

67. Преснухин Л.Н., Шахнов В.А. Конструирование электронных вычислительных машин и систем. Учебник для втузов по спец. «ЭВМ» и «Конструирование и производство ЭВА». М.: Высшая школа, 1986. - 512 с.

68. Применение вычислительных машин для проектирования цифровых устройств / Под ред. Н.Я. Матюхина. М.: Советское радио, 1968. - 256 с.

69. Самарский А.А., Гулин А.В. Численные методы. М.: Наука, 1989.— 432 с.

70. Сасов Ю.Д. Проблемы современной электроники и пути их решения //Ремонт Восстановление Модернизация. 2005. - №11. - С. 21-26.

71. Сасов Ю.Д. Трехмерная электроника. Трехмерные модули с применением керамических микроплат (ChIV-C) // Ремонт Восстановление Модернизация. -2006. №5. - С. 8-16.

72. Сасов Ю. Д. Трехмерная электроника. Трехмерные электронные модули с применением рамочных полимерных микроплат (ChIV-Е) //Ремонт Восстановление Модернизация. 2006. - №2. - С. 2-10.

73. Сасов Ю. Д. Трехмерная электроника. Трехмерные электронныемодули с применением безрамочных полимерных микроплат (ChIV-Е) //Ремонт Восстановление Модернизация. 2006. - №4. - С. 4-12.

74. Сегерлинд Л. Применение метода конечных элементов. М.: Мир, 1979.-392 с.

75. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977. 384 с.

76. Сигорский В.П., Петренко А.И. Алгоритмы анализа электронных схем. -Киев: Техника, 1970. 608 с.

77. Смагин М.А. Автоматизация проектирования рационального размещения прямоугольных деталей с использованием генетического метода на множестве эвристик: Дисс. .канд. техн. наук. Уфа, 2005. - 115 с.

78. Теория и методы автоматизации проектирования вычислительных систем / Под редакцией М. Брейера: Перевод с английского. М.: Мир, 1977.-283 с.

79. Тихомиров М.Д., Комаров И.А. Основы моделирования литейных процессов. Сравнение метода конечных элементов и метода конечных разностей. Что лучше? // Литейное производство. 2002. - №5. - С. 22-28.

80. Тихомиров М.Д. Основы моделирования литейных процессов. Важные особенности систем моделирования // Литейное производство. — 2004. №5,- С. 24-30.

81. Ушаков Д. Введение в математические основы САПР. Курс лекций. -Новосибирск, 2006. 180 с.

82. Филиппова А.С. Моделирование эволюционных алгоритмов решения задач прямоугольной упаковки на базе технологии блочных структур //Информационные технологии. 2006. - №6, приложение. - 32 с.

83. Фиск К., Кэски Д., Уэст JI. Автоматическое проектирование печатных плат//ТИЭЭР. 1967.-№11, т. 55.-С. 217-228.

84. Фогель JL, Оуэне А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969. - 230 с.

85. Amkor Technology Электронный ресурс удаленного доступа. -Режим доступа: http://www.amkor.com, свободный. Загл. с экрана. - Яз. англ.

86. Back Т. Self-Adaptation in Genetic Algorithms // Evolutionary Computation. 1993. - Vol. 1., № 2 - P. 1-20.

87. De Jong K.A., Spears W.M. A Formal Analysis of the Role of Multipoint Crosover in Genetic Algorithms // Annals of Mathematics and Artificial Intelligence (Florida). 1992. - V5. - P. 1-26.

88. Holland, J.H. Adaptation in Natural and Artificial Systems. Ann Arbor, MI: The University of Michigan Press. - 2nd edn. (1992) Boston (MA): MIT Press. - 228 p.

89. Irvine Sensors Corporation A Vision Systems Company Электронный ресурс удаленного доступа. - Режим доступа: http://www.irvine-sensors.com, свободный. - Загл. с экрана. - Яз. англ.

90. Marczyk A. Genetic Algorithms and Evolutionary Computation // The Talk Origin Archive Электронный ресурс удаленного доступа. Режим доступа: -www.talkorigins.org/faqs/genalg/genalg.html, свободный. Загл. с экрана. -Яз. англ.

91. Military Handbook. Reliability prediction of electronic equipment. MIL-HDBK-217F Notice 1. Department of Defence. Washington DC 20301. 2 January 1990.

92. Shahookar К., Mazmunder P. A Genetic Approach to Standard Cell Placement Using Meta-Genetic Parameter Optimization // IEEE Trans, on CAD. -1990.-Vol.9, №5.- P. 500-511.

93. Tezzaron Semiconductor Электронный ресурс удаленного доступа. -Режим доступа: http://www.tachyonsemi.com, свободный. Загл. с экрана. -Яз. англ.