Введение к работе
Спавмы автоматизации проектировании (САПР) являются важным іструментом развития научно—технического прогресса в электронной юмышлешгости и приборостроении. Сфера проектирования изделий ектроішой промышленности включает в себя ряд задач: ко.мпоповка диоэлементоп, размещеігие элементов, трассировка печатных плат и т.п. дачи размещения геометрических объектов, известные как .'задачи змещення элементов на печатной плате, планирования кристалла, гамиовки заготовок и т.п. имеют важные практические приложения.
Поскольку задача размещения является NP —полной, то разработать иверсалышй алгоритм размещения, который позволяет находить точное птималькое) решение за разумное время, невозможно. В этом случае врабатываются алгоритмы размещения, предназначенные для поиска боптимальных решений. Внедрение новых технологий обработки ватных плат, полупроводниковых материалов, использование в качестве ірья дорогостоящих матерналоз предъявляют все более хлесткие ебоиания к качеству субоптимальных размещений.
Таким образом, задача размещения двумерных геометрических гьектов произвольной формы (РДГО ПФ) была и остается АКТУАЛЬНОЙ РОБЛЕМОЙ ресурсосбережения, стоящей перед разработчиками САПР.
ЦЕЛЬЮ диссертационной работы является разработка и
следование генетического метода размещения двумерных
омстрическнх объектов произвольной формы, позаоляющего повысить їфоктншюсть решения задачи размещения ;) САПР.
Для достижения [.оставленной цели были решены следующие дачи:
1.) разработана новая методика описания объектов;
-
разработана структурная схема процесса размещения, ізволяющая генерировать, модифицировать и использовать знания о ойствах объектов;
-
разработаны компоненты процесса размещения, а) процедуры тановки объектов в ограниченную область; б) процедуры выявления іласти пересечения; в) процедуры оценки размещения объектов;
-
построен генетический алгоритм размещения на основе ализа механизма эволюции;
-
разработаны проблемно — зависимые модули генетического горитма (структура и кодирование хромосомы, функция пригодности);
-
исследован генетический алгоритм размещения двумерных ометрических объектов произвольной формы.
МЕТОДЫ ИССЛЕДОВАНИЯ в диссертации основаны на пользовании элементов теории множеств, элементов теории алгоритмов, оментов теории статистических вычислений.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в едующем:
- а) создан векторный , метод описания объектов для ішения задачи размещения, который позволяет повысить
качество- (прецизионность) размещения за счет векторного представленні объектов;
б) разработана стратегия "магнита" для установки объектов которая позволяет сократить сроки проектирования за счет исключениі неперспективного множества установок объекта в ограниченную область;
и) разработана эвристическая процедура проверки пересеченю двух геометрических объектов на плоскости, которая позволяет сократит] сроки проектирования за счет внедрения элементов искусственное интеллекта в механизм размещения;
г) реализована идея накопления знаний, которая позволяв-сократить сроки проектирования за счёт гибкого подхода к генерации модификации и использованию знаний.
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
—- алгоритм и программа генерации знаний о сопряженш заданного множества объектов, которые обеспечивают накопление знаний;
— генетический алгоритм и программа размещения, которые
используют выявленные знания для поиска субоптнмального размещения;
— программа регрессионного анализа по методу Чебышева.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические v
практические результаты диссертационной работы использованы і госбюДжотных работах "Разработка теории и методов построение интегрированных САПР БИС с элементами искусственного интеллекта' ' (№. ГР 01.9:50004188), "Разработка методов и моделей генетического поиске и интеллектуальных САПР", выполненной в рамках государственной научно—технической программы "Университеты России" (1995— 1996гг.) "Разработка учебно—методоческих к&иядексов по изучении: перспективных информационных технологий" межвузовской научно-технической программы ГОСКОМВУЗА РФ (1995г.). Результаты работы внедрены в НИИ МВС в качестве ПО САПР размещения. Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ'при чтении лекций и в цикле лабораторных работ по курсу "Методы генетического поиска".
АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах ^Генетические алгоритмы" (осень 1994—весна 1995 гг. ТРТУ), Всероссийской научно—технической конференции ' студентов и аспирантов "Новые информационные технологии. Информационное, программное и аппаратное обеспечение' (г.Таганрог 1995 г.), Всероссийской научно—технической конференции с участием зарубежных представителей "Интеллектуальные САПР" (г.Геленджик 1995г.).
ПУБЛИКАЦИИ. Результаты диссертации отражены ч 4-х печатных работах.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 161 стр., включая 27 рис., 14 табл., список литературы из 67 наименований, 5 стр. приложений и актов об использовании. -
