Введение к работе
Актуальность работы. В настоящее время наибольшее распространение при создании сложных объектов получили методы машинного (автоматизированного) проектирования. Поскольку компьютеры перестали быть редкостью, методы автоматизированного проектирования переходят в разряд инструментов, пользоваться которыми может каждый. В таких условиях технической оснащенности инженер должен обладать навыками математического и программного моделирования, а также решения задач разработки и эксплуатации аппаратуры с помощью ЭВМ. В связи с этим в промышленности широко используются различные системы автоматизированного проектирования (САПР), осуществляющие проектирование печатных плат (ПП), гибридных интегральных схем (ГИС), микросборок (МБС), больших интегральных схем (БИС), сверхбольших интегральных схем (СБИС) и других подобных конструктивов.
Одним из важнейших этапов в САПР является конструкторское проектирование. На этапе конструкторского проектирования осуществляется поиск оптимального варианта конструкции, учитывающего как возможности технологической базы производства, так и удовлетворяющего требованиям технического задания. Поэтому математическое обеспечение САПР должно развиваться в направлении поиска новых более эффективных методов структурного синтеза проектных решений. Синтез – процедура, которую трудно формализовать. Формализация применяется лишь для некоторых задач в отдельных приложениях. Приведём задачу разбиения в качестве примера формализуемых процедур и, следовательно, решаемых в САПР задач. Спроектировать топологию всей СБИС целиком представляется невозможным, поскольку она может содержать несколько миллионов транзисторов, поэтому схема разбивается группированием компонентов в блоки. Результатом решения задачи разбиения является формирование множества блоков и множества соединений между блоками. В очень больших схемах используется иерархическая структура разбиения.
В связи с трудностями создания общей математической модели, комплексно учитывающей все конструкторско-технологической особенности производства, не представляется возможным предложить алгоритм поиска оптимального конструктивного решения в едином цикле проектирования СБИС. Разработка и реализация алгоритмов и методов решения отдельных задач этапа конструкторского проектирования до сих пор остаётся актуальной проблемой. Решение этой проблемы неотъемлемо связано с развитием систем автоматизированного проектирования. К таким алгоритмам можно отнести методы эволюционного поиска и генетические алгоритмы (ГА). В последние годы широкое распространение также получили алгоритмы, основанные на роевом интеллекте (Swarm-based optimization algorithms (SOAs)). Эволюционные методы, генетические алгоритмы и алгоритмы роевого интеллекта являются одним из фундаментальных направлений научных исследований в области случайно-направленного поиска. Часто для сложной задачи необходимо найти любое решение, удовлетворяющее заданным ограничениям, поэтому целью биоинспирированных (эволюционно-генетических) алгоритмов (БА) является нахождение наилучшего решения поставленной задачи.
Поскольку данные алгоритмы и методы способны одновременно обрабатывать множество решений многокритериальной задачи, они получили широкое распространение при решении самых различных задач, в том числе и задач проектирования СБИС.
Таким образом, актуальность работы состоит в разработке новых алгоритмов и методов биоинспирированного поиска задачи разбиения схем при проектировании СБИС, позволяющих улучшить показатели качества, трудоёмкости и времени работы ЭВМ.
Цель работы состоит в разработке и исследовании биоинспирированных алгоритмов для решения задачи разбиения схем при проектировании СБИС.
Для достижения указанной цели предполагается решение следующих основных задач:
-
анализ задачи разбиения при автоматизированном проектировании;
-
обоснование выбора математической модели схем для решения поставленной задачи;
-
теоретические исследования эволюционных, генетических алгоритмов, а также алгоритмов роевого интеллекта, ориентированных на решение задачи разбиения схем при проектировании СБИС;
-
построение модифицированных генетических процедур для решения задачи разбиения схем при проектировании СБИС;
-
построение новых архитектур биоинспирированного поиска ориентированных на решение задачи разбиения схем при проектировании СБИС;
-
экспериментальные исследования разработанных алгоритмов и методов, а также их сравнение с известными аналогами.
В качестве методов исследования будем использовать законы и правила теории множеств, высшей математики, элементы теории графов и гиперграфов, алгоритмы комбинаторной оптимизации и эволюционного моделирования, элементы теории статистических вычислений.
Научная новизна диссертационной работы заключается в том, что:
-
разработана трёхуровневая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, оптимизирующая процесс эволюционно-генетического поиска;
-
разработан биоинспирированный алгоритм решения задачи разбиения, основанный на трёхуровневой архитектуре и использующий три алгоритма: алгоритма колонии пчёл, алгоритма генетического поиска и алгоритма эволюционного поиска;
-
на основе методов роевого интеллекта разработан алгоритм колонии пчёл, используемый в качестве методики формирования стартовой популяции хромосом, позволяющий повысить сходимость биоинспирированного алгоритма и сократить время поиска решений;
-
разработан алгоритм генетического поиска с новыми модифицированными процедурами для генетических операторов (кроссинговера, мутации, инверсии), зависящими от значений динамических параметров, повышающих устойчивость генетического поиска и качество получаемых решений;
-
разработан алгоритм эволюционного поиска, в состав которого входят эволюционные процедуры локального улучшения и преодоления преждевременной сходимости алгоритма.
Положения выносимые на защиту:
-
модифицированные процедуры для генетических операторов, повышающие устойчивость генетического поиска и качество получаемых решений;
-
процедуры локального улучшения и преодоления преждевременной сходимости биоинспирированного алгоритма;
-
алгоритм колонии пчёл, используемый в качестве методики формирования стартовой популяции хромосом;
-
биоинспирированный алгоритм решения задачи разбиения, основанный на трёхуровневой архитектуре, использующий три алгоритма: алгоритм колонии пчёл, алгоритм генетического поиска и алгоритм эволюционного поиска.
Практическую ценность работы представляют:
-
методика поиска решений, которая позволяет улучшить практические результаты по сходимости алгоритма, в связи с учётом математических и статистических закономерностей при распределении элементов;
-
новая архитектура биоинспирированного эволюционно-генетического поиска с динамическими параметрами, с помощью которой удалось оптимизировать процесс эволюционно-генетического поиска;
-
биоинспирированный алгоритм и программа для разбиения СБИС, созданная в среде объектно-ориентированного программирования Borland C++ Builder 6.0.
Реализация результатов работы. Материалы диссертационной работы использованы в г/б № 12354 (1.04.01) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», г/б № 12355 (12.8.08) «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», грант РФФИ № 12388 (№ 08 – 01 - 00473) «Разработка теории и принципов решения задач проектирования, оптимизации и принятия решений на основе биоинспирированных нечетких генетических и эволюционных методов», грант РФФИ № 12382 (№ 09- 01 - 00492) «Разработка общей теории и когнитивных принципов эволюционных вычислений», грант РФФИ № 12386 (№ 09- 01 - 00509) «Разработка теории и принципов эволюционной оптимизации и принятия решений на основе бионического моделирования», грант РФФИ № 12383 (№ 09 – 07 - 00318) «Разработка новых принципов извлечения знаний на основе распределенных алгоритмов генетического программирования и роевого интеллекта», РНП № 2.1.2.1652 «Разработка теории и когнитивных принципов принятия решений на основе распределённых алгоритмов, инспирированных природными системами».
Теоретические и практические результаты работы прошли апробацию на научных семинарах (с 2008 по 2011 гг., ТТИ ЮФУ), VI Всероссийской научно-практической конференции студентов, аспирантов и молодых учёных «МОЛОДЕЖЬ XXI ВЕКА — БУДУЩЕЕ РОССИЙСКОЙ НАУКИ» (г. Ростов-на-Дону, 2009), Международных научно-технических конференциях «Интеллектуальные системы» (AIS'08) и «Интеллектуальные САПР» (CAD-2008) (Дивноморское, 2008 г.), Молодёжной научно-технической конференции «Интеллектуальные системы - 2009» («ИС-2009») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT’09» (Дивноморское, 2009 г.), Молодёжной научно-технической конференции «Интеллектуальные системы - 2010» («ИС-2010») в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT’10» (Дивноморское, 2010 г.).
Структура и объём диссертационной работы. Диссертационная работа состоит из введения, четырёх глав, заключения, и списка использованных источников. Работа содержит 136 стр., включая 46 рис., 15 табл., список использованных источников из 91 наименования, 12 стр. приложений, 3 акта об использовании и 1 свидетельство о регистрации программы для ЭВМ.
Похожие диссертации на Разработка и исследование биоинспирированных алгоритмов разбиения схем при проектировании СБИС
