Введение к работе
Актуальность работы. Проектирование новых видов и образцов машин, оборудования, устройств, аппаратов, приборов и других изделий представляет сложный и длительный процесс, включающий в себя разработку исходных данных, чертежей, технической документации, необходимых для изготовления опытных образцов и последующего производства и эксплуатации объектов проектирования. В настоящее время наибольшее распространение при проектировании сложных объектов получило проектирование, при котором происходит взаимодействие человека и ЭВМ.
Довольно распространённым представлением процесса проектирования является следующее: на каждом уровне проекта решаются две задачи — синтез и анализ. Например, при схемотехническом проектировании структура системы представляется списком цепей, соединяющих транзисторы, резисторы, ёмкости и другие компоненты, а анализ заключается в построении математической модели схемы в виде системы обыкновенных дифференциальных уравнений и её численного решения, что позволяет рассчитать функциональные параметры схемы. Учитывая, что реализация процедур параметрической оптимизации и статистического анализа осуществляется путем многократного решения уравнений математических моделей, процесс проектирования требует колоссальных вычислительных ресурсов, даже с учетом достижений в области разработки современных эффективных вычислительных средств.
Для снижения суммарных затрат при проектировании сложных технических систем (в т.ч. сверхбольших интегральных схем (СБИС), систем на кристалле и других изделий микроэлектроники) широко применяется блочно-иерархический подход. При блочно-иерархическом подходе процесс проектирования разделяется на уровни (этапы). На высшем уровне используется наименее детализированное представление, отражающее только самые общие черты проектируемой системы. На каждом из последующих (более низких) уровней проектирования система последовательно разделяется на отдельные, как правило, функционально законченные блоки, причем степень детализации в каждом из этих блоков возрастает. Такой подход позволяет на каждом этапе формулировать и решать задачи приемлемой сложности.
Одним из направлений, которое улучшает качество получаемых решений для задач размещения и трассировки, является использование генетических алгоритмов. Генетический алгоритм (ГА или Genetic Algorithm, GA) представляет собой адаптивный поисковый метод, который основан на принципах естественного отбора лучших элементов в популяции по аналогии с эволюционной теорией Дарвина Ч.
В настоящее время генетические алгоритмы успешно применяются для решения различных научных и технических задач. Одним из самых эффективных направлений использования генетических алгоритмов является оптимизация многопараметрических функций. Часто при решении практических задач оптимизации не обязательно осуществлять поиск глобального оптимума, вполне достаточно найти одно или несколько квазиоптимальных решений, удовлетворяющих заданным ограничениям. В таких случаях генетические алгоритмы весьма эффективны. Одно из основных преимуществ генетического алгоритма – это возможность оперировать в процессе поиска не одним, а множеством решений.
В настоящее время эволюционные и генетические алгоритмы широко используют для решения ряда сложных задач оптимизации. Благодаря своему разнообразию подходов к нахождению решений, генетические алгоритмы представляют собой весьма эффективное средство решения задач оптимизации и проектирования. Нечеткие генетические алгоритмы с успехом применяют в современных средствах автоматизации проектирования изделий электронной техники, которая содержит сложнейшие электронные системы.
В этой связи разработка новых алгоритмов методов решения задачи размещения, эффективных в решении САПР имеет важное экономико-социальное значение и является в настоящее время актуальной и важной.
Цель диссертационной работы является разработка новых и модифицированных методов и алгоритмов решения задачи размещения фрагментов СБИС с учётом трассируемости соединений на основе нечётких генетических алгоритмов, позволяющих производить расчёты на основе вещественных чисел и нечётких правил.
Указанная цель достигается решением следующих задач:
-
Разработка новых методов и алгоритмов задачи размещения фрагментов СБИС с учетом трассируемости соединений.
-
Построение новых структурных схем процесса гибридного генетического поиска для решения задачи размещения с учётом трассируемости.
-
Разработка модифицированных генетических операторов и поисковых процедур (стратегии поиска, операторов кроссинговера, сегрегации, формирование начальной популяции).
-
Создание новых структур и принципов кодирования и декодирования альтернативных решений на основе вещественных чисел и построение модели логического контроллера.
-
Разработка новой инструментальной среды формирования фрагментов СБИС с учётом трассируемости соединений.
Методы исследования. В диссертационной работе для решения поставленных задач используются элементы теории процессов проектирования, аппарат теории чётких и нечётких графов, экспертных систем и эволюционного моделирования. В исследованиях широко использовался вычислительный эксперимент и моделирование на основе нечётких генетических алгоритмов, нечёткой логики и информационных технологий.
Научная новизна работы заключается в теоретическом обобщении и решении научной проблемы поддержки принятия решений в условиях недостаточности и нечёткости исходных данных, имеющих важное значение, в области проектирования САПР и информационных технологий:
-
Разработана новая схема гибридного генетического алгоритма с использованием нечётких вычислений и генетических операторов, позволяющая получить решение поставленной задачи один из наиболее удобных способов для, лица принимающего решение.
-
Разработана структура и принципы кодирования и декодирования решений для задачи размещения с учетом трассируемости с применением вещественных чисел в генетических операторах, что позволит получить лучшее решение и повысить качество получаемых решений.
-
Построен оператор кроссинговера «hill-climbing», использующего метод локального поиска с применением вещественных чисел, разработаны стратегии поиска популяции: минимальный разрыв между поколениями и обобщение поколений, позволяющие повысить устойчивость генетического поиска.
-
Разработан нечёткий логический контроллер, позволяющий корректировать результаты работы программы.
-
Построена новая инструментальная среда системы формирования фрагментов СБИС с учётом трассируемости соединений
Положения выносимые на защиту:
-
Усовершенствованные процедуры выполнения генетического оператора кроссинговера, обеспечивающие уменьшение времени поиска.
-
Модифицированная схема генетического поиска и разработанный модифицированный генетический оператор кроссинговера «hill-climbing».
-
Интегрированная архитектура для решения задачи размещения с учётом трассируемости, основанную на методах эволюционного моделирования.
Практическая значимость работы заключается в реализации интегрированного программно-алгоритмического комплекса в виде законченного программного продукта, использование которого позволяет решать поставленные задачи размещения фрагментов СБИС, позволяющего использовать разработанные алгоритмы, стратегии и эвристики, проводить сравнительный анализ с существующими аналогами.
Проведённые результаты вычислительных экспериментов, показали преимущество предложенного в работе интегрированного подхода к решению задач размещения фрагментов СБИС с учётом трассируемости соединений, в сравнении с используемыми классическими вариантами.
Внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе интегрированных нечетких генетических и эволюционных методов», грант «Разработка общей теории и когнитивных принципов эволюционных вычислений», Грант «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования», грант «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта», «Разработка теории и когнитивных принципов принятия решений на основе распределённых алгоритмов, инспирированных природными системами».
Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском технологическом институте Южного федерального университета в цикле лекций и практических занятий по курсам «Автоматизация конструкторского и технологического проектирования», «Методы оптимизации» и «Эволюционное моделирование и генетические алгоритмы».
Апробация работы. Основные результаты, полученные в ходе работы, докладывались и обсуждались на VII-ой научно практическая конференции студентов, аспирантов и молодых ученых и специалистов «Интегральные модели, мягкие вычисления, вероятностные системы и сложные программы в искусственном интеллекте» Коломна, 26-27 Мая 2009 года. Конгресс по интеллектуальным вычислениями и информационным технологиям AIS-IT’09 Дивноморское 2-10 Сентября 2009 года. Всероссийской научно-технической конференции "Проблемы разработки перспективных микро- и наноэлектронных систем» с 4 по 8 октября 2010 года в Подмосковье. IX-й научно-практической конференции студентов, аспирантов и молодых ученых и специалистов «Интегральные модели, мягкие вычисления, вероятностные системы и сложные программы в искусственном интеллекте» Коломна 26-27 мая 2011 год.
Публикации. Основные положения и результаты диссертационной работы опубликованы в 13 источниках, включающих 10 статей, 3 материалов конференций и семинаров, 2 свидетельства о регистрации программ. Четыре работы из них опубликованы в рецензируемом журнале из списка ВАК.
Объем и структура диссертации. Диссертация состоит из введения, списка рисунков, 4 глав, заключения, списка литературы, включающего 106 наименования и 6 приложений. Основной текст диссертации изложен на 164 страницах, включая 85 рисунок и 11 таблиц.
