Введение к работе
Актуальность темы. Проектирование электронно-вычислительной аппаратуры (ЭВА) начинается с разработки технического задания (ТЗ), отражающего потребности человека и завершается реализацией ТЗ в виде набора конструкторской и технологической документации При этом поставленные перед разработчиком задачи должны быть решены с максимальной эффективностью, что охватывает не только снижение себестоимости продукции и сокращение сроков проектирования и производства, но и обеспечение удобства освоения и снижения затрат на будущую эксплуатацию изделий В связи со сложностью современных ЭВА достижение поставленных целей и формирование проектных решений оказывается невозможным без широкого использования систем автоматизированного проектирования (САПР) Задачи конструкторского проектирования приобрели характеристики оптимизационных многокритериальных задач, при решение которых высокую эффективность показывают методы эволюционного моделирования
Эволюционное моделирование является одной из фундаментальных областей научных исследований на стыке информатики, биологии и искусственного интеллекта Значительный вклад в решение задач эволюционного моделирования внесли. Holland J Н , Fogel D В , Koza J , Back T , Chipperfield A , Fleming P , Батищев Д И, Букатова И Л, Курейчик В М , Редько В Г и многие другие ученые
Генетические алгоритмы (ГА) относятся к классу эволюционных алгоритмов, являются адаптивными и отличаются устойчивостью, не требуют дифферен-цируемости оптимизируемой функции, полноты знаний о решаемой проблеме, что позволяет применять их для решения различных нелинейных задач высокой размерности К ним относятся задачи автоматизированного проектирования электронно-вычислительных устройств (ЭВА), такие как покрытие, компоновка, размещение, трассировка и др. В настоящее время при решении задач автоматизированного проектирования возникает проблема, получившее название «проклятие размерности». Вместе с тем, широкое использование ГА сдерживается рядом факторов, в числе которых жесткая привязка к решаемой задаче на этапе кодирования и декодирования решения Кроме того, отсутствие достаточно гибких и удобных инструментов разработки ГА, общепринятых стандартов их реализации и форматов данных исключает возможность повторного использования существующего программного кода Следует отметить, что вероятностный характер ГА, обуславливает малую повторяемость результатов
В этой связи разработка и исследование интегрированной инструментальной подсистемы генетического поиска для решения задач автоматизированного конструкторского проектирования является актуальной и важной
Данная работа является развитием результатов исследований, проводимых на кафедре САПР Таганрогского технологического института (ТТИ) Южного федерального университета (ЮФУ) в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 гг) на тему «Разработка бионических методов и принципов поиска оптимальных решений при проектировании»
Цель диссертационной работы. Разработка интегрированной инструментальной подсистемы генетического поиска (ПГП) для решения широкого круга
оптимизационных задач, а также в исследовании ее эффективности при решении задач автоматизированного конструкторского проектирования ЭВА. Для достижения поставленной цели в работе были решены следующие основные задачи.
Построена открытая архитектура интегрированной инструментальной подсистемы генетического поиска проектных решений
Сформулированы принципы и правила формального описания процедуры генетического поиска проектных решений ЭВА, которые положены в основу модели представления макрогенетического алгоритма (МакроГА), позволяющей оптимизировать набор альтернативных решений с использованием нетривиальных генетических алгоритмов
3. Определен расширенный набор правил формального описания процедуры генетического поиска проектных решений, заложенный в модель представления метагенетического алгоритма (МетаГА), которая позволяет организовать взаимодействие нескольких различающихся по структуре МакроГА, что обеспечивает параллельную оптимизацию нескольких наборов решений
Разработан механизм, обеспечивающий открытость подсистемы для интеграции уникальных алгоритмов формирования новых решений
Предложена модель представления решения задачи, обеспечивающая низкую вычислительную и пространственную сложность алгоритмов оценки и преобразования решений
6. Разработан ГА для решения задач автоматизированного проектирования, на примере которого исследована эффективность разработанной подсистемы
Для решения поставленных задач использовались методы теорий множеств, алгоритмов, графов, математической статистики и планирования эксперимента, а также методы и средства эволюционного моделирования, параллельного и объектно-ориентированного программирования
Научная новизна работы состоит в следующем.
Построена архитектура интегрированной инструментальной подсистемы поиска проектных решений, основанная на эволюционных моделях и позволяющая сократить время программной реализации генетических алгоритмов для решения задач автоматизированного проектирования
Определены лингвистические средства, структура и семантика формального описания нетривиальных процедур генетического поиска проектных решений
Разработаны модели представления метаэволюционного и макроэволюционно-го алгоритмов, позволяющие реализовать средствами подсистемы нетривиальные процедуры генетического поиска
Сформулированы принципы и правила построения операторов преобразования кодов решений, статистической обработки результатов и преобразования форматов представления данных задачи, позволяющие интегрировать новые операторы в подсистему генетического поиска
Разработана и реализована модель представления решений оптимизационных задач, позволяющая при кодировании решения использовать хромосомы разного типа двоичные, векторные, а также гомологичные и негомологичные числовые хромосомы
Предложены стратегии определения точек разрыва и формирования потомков с помощью алгоритма построения множества Кантора
7 В созданной интегрированной инструментальной подсистеме разработан и реализован новый генетический алгоритм решения задачи двумерного размещения разногабаритных элементов схем ЭВА, позволяющий за полиномиальное время найти набор квазиоптимальных решений
Практическая ценность работы заключается в реализации интегрированной инструментальной подсистемы в виде законченного программного продукта, использование которого позволяет разрабатывать новые и модифицировать известные генетические алгоритмы для решения различных задач автоматизированного проектирования Важным результатом диссертационной работы также является реализация средствами интегрированной инструментальной подсистемы нового ГА двумерного размещения разногабаритных элементов
Реализация и внедрение результатов работы. Основные теоретические и практические результаты, полученные в диссертационной работе, используются при выполнении научно-исследовательских работ кафедры САПР ТТИ ЮФУ , а также в учебном процессе кафедры при преподавании следующих дисциплин «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования»
Апробация основных теоретических и практических результатов работы Результаты диссертации докладывались и обсуждались на Международных научно-технических конференциях «Интеллектуальные системы (IEEE AIS'04)» (с Див-номорское, 2004), «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005) (с Дивноморское, 2005) Получено свидетельство об официальной регистрации программы для ЭВМ №2006612763, 2006г По итогам открытого конкурса на лучшую научную работу студентов по естественным, техническим и гуманитарным наукам в вузах Российской Федерации получены медаль и удостоверение от 15 07 2005г Министерства образования РФ «за лучшую студенческую научную работу»
Публикации. По теме диссертационной работы опубликовано 7 печатных работ, сделано 2 доклада на Международных научно-технических конференциях
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 175 страницах, содержит 27 рисунков, 14 таблиц, 104 наименования библиографии и приложения
