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

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

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА ПРОЕКТНЫХ РЕШЕНИЙ

Специальности 05 13 12 - Системы автоматизации проектирования, 05 13 17-Теоретические основы информатики

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

003174 16Э

Таганрог 2007

003174169

Работа выполнена в Южном федеральном университете

Научный руководитель-

Научный консультант

Официальные оппоненты

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

кандидат технических наук, доцент Нужнов Евгений Владимирович

доктор технических наук, профессор Чернов Николай Иванович (Технологический институт Южного федерального университета в г Таганроге)

Ведущая организация

кандидат технических наук, ведущий научный сотрудник, Орлов Николай Николаевич (ООО «Технологическое Агентство Информации», г.Таганрог)

Федеральное Государственное Унитарное Предприятие Научно-исследовательский институт «Связи»

Защита диссертации состоится «££» ноября 2007г в 1420 на заседании диссертационного совета Д 212 208 22 при Южном федеральном университете по адресу. 347928, Таганрог, пер. Некрасовский, 44, ауд. Д-406

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, Ростов-на-Дону, ул Пушкинская, 148

Автореферат разослан «04» октября 2007г

Ученый секретарь

диссертационного совета Д 212 208 22, доктор технических наук, профессор 'I Целых А Н.

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

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

Эволюционное моделирование является одной из фундаментальных областей научных исследований на стыке информатики, биологии и искусственного интеллекта Значительный вклад в решение задач эволюционного моделирования внесли. Holland J Н , Fogel D В , Koza J , Back T , Chipperfield A , Fleming P , Батищев Д И, Букатова И JT, Курейчик В М , Редько В Г и многие другие ученые

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

В этой связи разработка и исследование интегрированной инструментальной подсистемы генетического поиска для решения задач автоматизированного конструкторского проектирования является актуальной и важной

Данная работа является развитием результатов исследований, проводимых на кафедре САПР Таганрогского технологического института (ТТИ) Южного федерального университета (ЮФУ) в рамках аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» (2006 - 2008 гг) на тему «Разработка бионических методов и принципов поиска оптимальных решений при проектировании»

Цель диссертационной работы. Разработка интегрированной инструментальной подсистемы генетического поиска (ПГП) для решения широкого круга

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

1 Построена открытая архитектура интегрированной инструментальной подсистемы генетического поиска проектных решений

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

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

4 Разработан механизм, обеспечивающий открытость подсистемы для интеграции уникальных алгоритмов формирования новых решений

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

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

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

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

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

3 Разработаны модели представления метаэволюционного и макроэволюционно-го алгоритмов, позволяющие реализовать средствами подсистемы нетривиальные процедуры генетического поиска

4 Сформулированы принципы и правила построения операторов преобразования кодов решений, статистической обработки результатов и преобразования форматов представления данных задачи, позволяющие интегрировать новые операторы в подсистему генетического поиска

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

6 Предложены стратегии определения точек разрыва и формирования потомков с помощью алгоритма построения множества Кантора

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

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

Реализация и внедрение результатов работы. Основные теоретические и практические результаты, полученные в диссертационной работе, используются при выполнении научно-исследовательских работ кафедры САПР ТТИ ЮФУ , а также в учебном процессе кафедры при преподавании следующих дисциплин «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования»

Апробация основных теоретических и практических результатов работы Результаты диссертации докладывались и обсуждались на Международных научно-технических конференциях «Интеллектуальные системы (IEEE AIS'04)» (с Див-номорское, 2004), «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005) (с Дивноморское, 2005) Получено свидетельство об официальной регистрации программы для ЭВМ №2006612763, 2006г По итогам открытого конкурса на лучшую научную работу студентов по естественным, техническим и гуманитарным наукам в вузах Российской Федерации получены медаль и удостоверение от 15 07 2005г Министерства образования РФ «за лучшую студенческую научную работу»

Публикации. По теме диссертационной работы опубликовано 7 печатных работ, сделано 2 доклада на Международных научно-технических конференциях

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 175 страницах, содержит 27 рисунков, 14 таблиц, 104 наименования библиографии и приложения

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении дано обоснование актуальности темы диссертационной работы, сформулированы цель работы и основные научные положения, выносимые на защиту, определены круг задач, объект, предмет и методы исследования, показаны научная новизна и практическая ценность, а также подтверждена достоверность полученных результатов

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

■ генофонды популяций, входящих в МетаГА;

■ наборы управляющих параметров МакроГА, входящих в МетаГА,

■ метаправила изменения значений параметров МакроГА,

■ правила отбора и пути миграции особей,

■ результаты предыдущих этапов работы МетаГА

Далее проведен сравнительный анализ существующих программных продуктов, реализующих ГА, таких как ОепеНшПег, программа К8Са1аху и библиотеки компонентов вАЬЬ

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

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

где г, — вариант размещения, к[, к2 - весовые коэффициенты, заданные таким образом, чтобы их сумма равнялась единице, 1(г7) - суммарная длина проводников, 0(Цг;)) — нормированная оценка общей длины проводников, приведенная к интервалу [0, /], 5ой„( - фактическая площадь размещения, определенная как площадь минимального прямоугольника, описывающего размещенные элементы, Р{8с^я{г})) - нормированная оценка общей площади размещения, принимающая значения из интервала [0, /]

Таким образом, задача размещения состоит в поиске минимального значения функции Р на множестве допустимых размещений 2

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

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

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

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

■ числовую гомологичную хромосому Нх — определяющую последовательность элементов путем «кодирования перестановок»,

двоичную хромосому #2 пространстве

для кодирования ориентации элементов в

Р =

Я, Я,

О

4 1

Оценка качества решения производится путем размещения элементов, очередность которых заданна первой хромосомой, а ориентация - второй хромосомой Выбор точки размещения очередного элемента производится таким образом, чтобы приращения фактической области размещения было минимально Пример размещения, закодированного в особи р, приведен на рис 1

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

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

Для графа МетаГА введено понятие «состояние вершины», которое характеризует готовность вершины и всех зависимых данных для выполнения оператора, поставленного ей в соответствие Выделим следующие состояния вершины

■ «готова» - все данные, необходимые для выполнения ГО, ассоциированного с вершиной, готовы для его выполнения,

■ «выполняется» - выполнение макрогенетического алгоритма не завершено в момент проверки состояния вершины, с которой он ассоциирован,

■ «ожидание» - в момент помещения вершины в очередь обработки не были готовы данные, необходимые для выполнения оператора, связанного с данной вершиной

■ «завершена» - выполнение оператора, ассоциированного с данной вершиной, завершилось успешно

Допустимые переходы между состояниями вершин приведены на рис 2

завершена

ожидание •

Рис 2 Граф состояний операторов МетаГА Определены принципы и правила описания процедур генетического поиска проектных решений, которые применяются при хранении архитектуры спроектированного ГА и организации взаимодействии различных структурных элементов ПГП Описание ГА может быть «обобщенным», т е содержащим информацию о структуре ГА, а также «детализированным» Последнее является результатом модификации ГА для решения конкретной оптимизационной задачи и помимо структуры алгоритма содержит сведения о структуре, кодирующей решение, способе декодирования и оценки приспособленности, а также применяемые ГО и значения управляющих параметров ГА Структурная схема интегрированной инструментальной ПГП приведена на рис 3

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

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

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

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

с5иЬзу5(ет» Подсистема ПИ

Рис 3 Архитектура интегрированной инструментальной подсистемы генетического поиска

«subsystem» о ПГП Подсистема ввода-вывода

«interface» GAIinout

«subsystem» Ядро ПГП Менеджер расширений

Оператор ввода вывода

♦Execute)) int ♦Couple))

т

о о

«subsystem» Ядро ПГП Моделирование нейронной сети

Г»не/шческий оператор (ГО)

Execute)) int ♦Couple))

Хромосомо-модифицирующий ГО

«interface» GAlChromosomeConstruction

«interface» GAIBionFitness

Ж.

Менеджер расширении ГО Отбора

«interface» GAIBionSelectlon

ГО Рекомбинации

«interface» GAIBionRecomblnation

«subsystem» Ядро ПГП Подсистема статис1-ик*

«interface» GAIStatistic

Статистический оператор

Execute)) int ♦Couple))

Mema гене/nu чесниù оператор

•Execute)) int •CoupleQ

ГО Инициализаций

«interface» GAtBiontnitlaliuUon

«interface» GAIBionBreeding

ж:

Оператор Отбора

«interface» GAIMetaSelection

Оператор Миграции

«interface» G Al M eta M ig ration

........ i i 1 !

«subsystem» Подсистема метамоделирования Подсистема макромоделирования «subsystem» Ядро ПГП: Подсистема метамоделирования

Рис 4 Механизм интеграции компонентов в подсистему генетического поиска

В результате связывания возникает двусторонняя связь между ядром ПГП и компонентом

■ с одной стороны подсистема моделирования ядра ПГП содержит дескриптор компонента и формирует среду исполнения оператора (необходимые для его работы данные и параметры),

■ с другой стороны компонент содержит интерфейсный объект ядра ПГП, предоставляющий доступ к данным подсистемы моделирования ядра ПГП (множеству альтернативных решения (особей) и управляющих параметров ГА)

Разработана структура обобщенного и детального описания процедур генетического поиска проектных решений В качестве языка описания выбран XML Для задания структуры и семантики описания процедур генетического поиска, а также правил верификации использован язык описания схем XML Schema Definition

Разработаны алгоритмы детализации описания ГА, функционирования ядра ПГП, а также алгоритмы функционирования подсистем макроэволюционного и метаэволюционного моделирования на этапе сборки и на этапе выполнения ГА

Алгоритм метаэволюционного моделирования состоит в следующем 1° Выбор вершины «Начало алгоритма» и помещение ее в очередь обработки 2° Извлечение первого элемента очереди (вершины)

3° Если выбран элемент «Конец работы алгоритма», то очередь очищается и выполняется переход к шагу 8°, 4° Если выбранная вершина находится в состоянии «готово», то выполняется ГО,

связанный с данной вершиной, и осуществляется переход к шагу 6° 5° Если выбранная вершина находится в состоянии «выполняется» или в состоянии «ожидание», то вершина помещается в конец очереди и осуществляется возврат к шагу 2°

6° Если выбранная вершина находится в состоянии «завершено» и предусмотрен условный выбор исходящей дуги, то производится выбор дуги, а инцидентная ей вершина графа МетаГА помещается в конец очереди В противном случае в конец очереди помещаются вершины графа, инцидентные всем исходящим дугам

7° Проверка состояния очереди обработки Если очередь пуста, то подсистеме пользовательского интерфейса сообщается о возникновении недопустимой ситуации, поскольку последним обработанным элементом должен быть элемент «Конец работы алгоритма» Выполняется переход к шагу 8° В противном случае выполняется возврат к шагу 2°. 8° Вывод лучшего решения

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

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

Предложены следующие стратегии определения точек разрыва

■ задано число точек разрыва - п Расположение точек разрыва определяется с помощью алгоритма построения множества Кантора,

■ задана глубина рекурсии к Число точек разрыва и их местоположение определяется с помощью алгоритма построения множества Кантора, выполняемого к раз;

■ не задана ни глубина рекурсии к. ни число точек разрывов п В этом случае глубина рекурсии принимается равной ктах Число течек разрыва и их местоположение определяется с помощь алгоритма построения множества Кантора, применяемого ктт раз

Предложены следующие стратегии формирования потомков с помощью алгоритма построения множества Кантора

■ применение ГО после определения всех точек разрыва Получается стандартное число потомков,

■ применение ГО на каждой итерации построения множества Кантора Число потомков увеличивается в к раз по сравнению со стандартным способом выполнения ГО

В четвертой главе приведены результаты вычислительного эксперимента по определению затрат процессорного времени и памяти вычислительной системы при выполнении ГА разработанного средствами интегрированной инструментальной ПГП и ГА, реализованного на языке С++, которые выполнялись при фиксированных значениях параметров алгоритма размер популяции |Р| = 100, вероятность применения оператора кроссинговера Р0К = 0,6, вероятность применения оператора мутации Ром = 0,4, вероятность применения оператора инверсии Р0ц = 0,6

Обобщенные результаты по определению затрат процессорного времени (Тср) и памяти вычислительной системы (Меш) при выполнении ГА средствами интегрированной инструментальной ПГП и ГА, реализованного на языке С++, приведены в табл 1 и на рис 5-6

Обобщенные результаты сравнения размещения тестовых схем ibm01-ibml3 алгоритмами Capo 8 6, Feng Shui 2 0, Dragon 2.23 и ГА, разработанного с использованием ПГП, приведены в табл 2 и на рис 7 Отрицательное приращение суммарной длины проводников (AL) показывает, что разработанному ГА удалось найти размещение с лучшими значениями оцениваемого критерия по сравнению с результатами, полученными другими алгоритмами Приведенные результаты обусловили следующие выводы

Дополнительные расходы времени, затраченные ПГП на выполнение ГА, не превосходят 6% по сравнению с реализацией данного алгоритма на языке программирования С++ Расходы памяти вычислительной системы, затраченные ПГП на выполнение ГА, складываются из двух частей, память для хранения данных ГА, объем которой зависит от размерности задачи и дополнительные память для хранения служебной информации ПГП Основная доля дополнительных затрат памяти не зависит от размерности задачи и убывает с ростом числа размещаемых элементов, что свидетельствует об эффективном использовании подсистемой данного ресурса Качество размещений, полученных ГА, разработанным с использованием интегрированной инструментальной подсистемы, в среднем на 6,38% превосходит результаты, полученные с использованием известных алгоритмов Capo 8 6, Feng Shui 2 0, Dragon 2 23, что говорит об эффективности предложенного алгоритма и разработанной ПГП в целом

Таблица 1 Сравнение затрат процессорного времени _ и памяти вычислительной системы.

<>|ШН нет. ..................... глэг Т5й Ннтггрировям ИПЯ;НИ11 11111

(•■¡•ни ¡ЧоЗе-■ШЩ; РаЗДёр Тер. «к мЯ|||1 байт | 1.-Р -Тер, «к -Л, М|Щ|, ба|||

1 100 33 0,222 0,628 532725 0,621 0,226 1,42% 601822 11,48%

2 150 33 0,419 0,540 596587 0,593 0,436 3,80% 655220 8,95%

3 200 33 0,655 0,510 659057 0.497 0,675 3,01% 724000 8,97%

4 250 33 0,963 0,663 749806 0,677 0,979 1,64% 823232 8,92%

5 300 33 1,270 0,531 859074 0,510 1,303 2,56% 911152 5,72%

6 350 33 1,528 0,730 975810 0,730 1,615 5,40% 1026819 4,97%

7 400 33 2,197 0,597 1114121 0,589 2,267 3,08% 1173635 5.07%

8 450 33 2,337 0,765 1259608 0,747 2,430 3,83% 1329167 5.23%

9 500 33 3,3! 7 0,600 1398075 0,597 3,513 5,57% 1484658 5,83%

10 550 33 3.984 0.548 1581834 0,548 4,164 4,32% 1656824 4.53%

11 600 33 4.058 0,516 1784546 0,516 4,147 2,15% 1840993 3,07%

12 650 33 5,205 0.591 1996167 0,570 5,323 2,17% 205361Й 2М%

13 700 33 5,555 0,508 2220362 0,511 5.762 3,59% 2283914 2,78%

14 750 33 6.297 0,574 2452550 0.582 6,421 1,93% 2504624 2,08%

15 800 33 8.021 0,798 2688473 0,802 8,355 4,01% 2780950 3,33%

16 850 33 8,271 0,580 2923625 0.575 8,481 2,48% 2997817 2,47%

17 900 33 8,952 0,621 3229648 0,661 9,289 3,63% 3280031 1,54%

18 950 33 11,182 0,619 3540253 0,603 11,423 2.11% 3630865 2,50%

19 1000 33 11,858 0,740 3806123 0,739 12,421 4,53% 3855893 1,29%

2СО 2511 300 МО «а 450 «Со 860 еоо 650 7*а аоо Е50 КО КО 1С«)

HZH.ii.L4V кроыя, — ЛмпеСмый |ДОП. «»№1,

Рис. 5. Дополнительные затраты процессорного времени при выполнении ГА средствами ПГП по сравнению с ГА, реализованным на языке С++.

число »льыснтм

Рис. б. Дополнительные затраты памяти при выполнении ГА средствами ПГП по сравнению с ГА, реализованным на языке С++.

Таблица 2 Сравнение результатов размещения тестовых схем ¡ЬтОЫЬггПЗ _разными алгоритмами._

■ | 1ГС1ЦПЫС ■.-.;', ГЛГМЬ? С яро КеЩ 81101 11Н11 1 |1к фсжтшая инструментальная III Щ

. - Л 5 б-'Л пне ЙЯ*1«-N11111 "ТЛ1 р \ Ль,£ . ч Саро. Ч1Р сЖ &£...... ■ !§"'' м- ргакоп» • 1,! • %1|1

»Ьт01 12 752 4,97 4,87 4,42 4,28 -0,69 -13,87% -0,59 -12,11% -0,14 -3,16%

1Ьт02 19 60! 15.23 14,38 13,57 13,05 -2.18 -14,31% -1,33 -9,25% -0,52 -3,83%

¡ЬтОЗ 23 136 14,06 12,84 12,33 11,96 -2,10 -14,90% -0,88 -6,82% -0,37 -2,96%

¡Ьт04 27 507 18,13 16,69 15,41 15,58 -2,55 -14,05% -1,11 -6.63% 0,17 1,13%

¡Ьт05 29 347 44,73 37,3 36,38 35,96 -8,77 -19,62% -1,34 -3,60% -0,42 -1,17%

¡ЬтОб 32 498 21,96 20,27 20,38 20,52 -1,44 -6,56% 0.25 1,23% 0,14 0,69%

1Ьт07 45 926 36,06 31,5 29,97 31,82 -4,24 -11,76% 0,32 1,01% 1,85 6,17%

¡Ьт08 51 309 37,89 34.14 32,2 33,80 -4.09 -10,80% -0,34 -1,01% 1,60 4,96%

¡Ьт09 53 395 30,28 29,86 28,1 27,46 -2,82 -9,31% -2,40 -8,03% -0,64 -2,27%

¡ЬтЮ 69 429 61,25 57,99 57,2 53.04 -8,21 -13,41% -4,95 -8.54% -4,16 -7,28%

¡Ьт11 70 558 46,45 43,28 40,77 40,66 -5,79 -12,47% -2,62 -6.05% -0,11 -0,27%

¿Ьт12 71 076 81,55 75.91 71,03 73,17 -8,38 -10.27% -2,74 -3,61% 2.14 3,02%

№т13 84 199 56,47 54,09 50,57 48,37 -8,10 -14,34% -5,72 -10,57% -2,20 -4,34%

■го.оо%

ош ------

тестовые схемы

'□Сара fi.fi И^п.^ аИш 2.0 □□гадсп 2.23

Рис. 7. Приращение длины проводников при размещений тестовых схем ¡ЬтОЫтЫЗ различными алгоритмами.

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

В приложении приведены акты об использовании результатов диссертационной работы.

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

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

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

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

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

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

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

6. Разработан Программный комплекс, реализующий интегрированную инструментальную подсистему генетического поиска. Проведенный вычислительный эксперимент подтвердил низкий уровень дополнительных расходов ресурсов

вычислительной системы, связанных с реализацией ГА средствами интегрированной инструментальной подсистемы

7 Разработан ГА двумерного размещения разногабаритных элементов схемы, использующий мультихромосомное негомоморфное представление размещения и модифицированные операторы, основанные на множестве Кантора Проведенный вычислительный эксперимент подтвердил то, что качество решений, получаемых с помощью разработанного ГА в среднем на 6,38% превосходит результаты размещения, полученные известными алгоритмами Capo 8 6, Feng Shui 2 0, Dragon 2 23

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Бакало M А , Курейчик В В. Нахождение максимального паросочетания с использованием искусственных нейронных сетей // Труды Международных научно-технических конференций «Интеллектуальные системы (IEEE AIS'04)» и «Интеллектуальные САПР (CAD-2004)» - M Физматлит, 2004, с 363-372

2. Backalo M A The finding of the maximum matching using neural network // Ehe International Scientific Conferences "Intelligent Systems (IEEE AIS'04)" and "Intelligent CAD's (CAD- 2004)". - M, Physmathlit, 2004, vol. 3, pp 121

3. Бакало M А., Курейчик В В Генетические операторы на основе множества Кантора // Труды Международных научно-технических конференций «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005) Научное издание в 4-х томах - M • Физматлит, 2005, т.4, с 237-243

4. Бакало M А , Курейчик В В К вопросу построения модифицированного алгоритма размещения // Перспективные информационные технологии и интеллектуальные системы - Таганрог ТРТУ, 2006, № 4(28), с 44-55.

5. Бакало M А. Варианты представления различных типов данных, их кодирование и декодирование в виде хромосом // Известия ТРТУ - Таганрог ТРТУ, 2007, № 1, с 70-75

6 Бакало M А , Курейчик В В. Модифицированный алгоритм размещения методом парных перестановок //Известия ТРТУ - Таганрог- ТРТУ, 2007, № 1,

7 Бакало М А., Курейчик В В Концепция построения системы поддержки генетических алгоритмов // Перспективные информационные технологии и интеллектуальные системы - Таганрог ТТИ ЮФУ, 2007, №1(29), с 4-10

8 Свидетельство об официальной регистрации программы для ЭВМ № 2006612763,2006г

В работах 1 и 2, выполненных в соавторстве, автору принадлежит структура искусственной нейронной сети. В работах 4 и 6 автору принадлежит идея выделения подобластей расположения элементов относительно анализируемых и вывод математических формул расчета В работе 7 автору принадлежит идея использования интерфейсных объектов, инспектора хромосом и буфера особей.

с 77-84

Соискатель

M А. Бакало

ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ ПОДХОДОВ К МОДЕЛИРОВАНИЮ ЭВОЛЮЦИОННОГО ПОИСКА.

1.1. МЕТОДЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

1.2. ОПИСАНИЕ МОДЕЛЕЙ ЭВОЛЮЦИИ.

1.3. СРАВНИТЕЛЬНАЯ ХАРАКТЕРИСТИКА СУЩЕСТВУЮЩИХ ПРОГРАММ ГЕНЕТИЧЕСКОГО ПОИСКА.

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

1.5. ВЫВОДЫ.

2. АРХИТЕКТУРА ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

2.1. СТРУКТУРА И ОРГАНИЗАЦИЯ ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

Подсистема пользовательского интерфейса.

Ядро подсистемы генетического поиска.

2.2. КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ РЕШЕНИЯ ЗАДАЧИ.

Варианты представления различных типов данных, их кодирование и декодирование в виде хромосом.

Представление решения задачи размещения.

2.3. КОНЦЕПТУАЛЬНАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА.

2.4. ВЫВОДЫ.

3. РАЗРАБОТКА БЛОКОВ ИНТЕРИРОВАННОЙ

ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА И АЛГОРИТМОФ ЕЕ ФУНКЦИОНИРОВАНИЯ.

3.1. КОМПОНЕНТНАЯ МОДЕЛЬ ОРГАНИЗАЦИИ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

3.2. ВНУТРЕННЯЯ СТРУКТУРА ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

3.3. ЛИНГВИСТИЧЕСКИЕ СРЕДСТВА ОПИСАНИЯ ПРОЦЕДУР ГЕНЕТИЧЕСКОГО ПОИСКА ПРОЕКТНЫХ РЕШЕНИЙ.

3.4. РАЗРАБОТКА АЛГОРИТМОВ ФУНКЦИОНИРОВАНИЯ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА.

3.5. РАЗРАБОТКА МОДИФИЦИРОВАННЫХ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ.

3.6. РАЗРАБОТКА АЛГОРИТМА ДВУМЕРНОГО РАЗМЕЩЕНИЯ ЭЛЕМЕНТОВ СХЕМ.

3.7. ВЫВОДЫ.

4. ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ИНТЕГРИРОВАННОЙ ИНСТРУМЕНТАЛЬНОЙ ПОДСИСТЕМЫ ГЕНЕТИЧЕСКОГО ПОИСКА И НА ПРИМЕРЕ ЗАДАЧИ РАЗМЕЩЕНИЯ РАЗНОГАБАРИТНЫХ ЭЛЕМЕНТОВ СХЕМЫ.

4.1. ЦЕЛЬ ЭКСПЕРИМЕНТА.

4.2. ТЕОРЕТИЧЕСКАЯ ОЦЕНКА ВРЕМЕННОЙ И ПРОСТРАНСТВЕННОЙ СЛОЖНОСТИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА РАЗМЕЩЕНИЯ.

4.3. ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНОГО ЭКСПЕРИМЕНТА.

4.4. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА.

4.5. ВЫВОДЫ.

Проектирование электронно-вычислительной аппаратуры (ЭВА) [1] начинается с разработки технического задания (ТЗ) [2], отражающего потребности человека и завершается реализацией ТЗ в виде набора конструкторской и технологической документации [3]. При этом поставленные перед разработчиком задачи должны быть решены с максимальной эффективностью, что охватывает не только снижение себестоимости продукции и сокращение сроков проектирования и производства, но и обеспечение удобства освоения и снижения затрат на будущую эксплуатацию изделий. В связи со сложностью современных ЭВА достижение поставленных целей и формирование проектных решений оказывается невозможным без широкого использования систем автоматизированного проектирования (САПР) [1 -3]. Задачи конструкторского проектирования приобрели характеристики оптимизационных многокритериальных задач [1 -4], решение которых высокую эффективность показывают методы эволюционного моделирования.

Эволюционное моделирование является одной из фундаментальных областей научных исследований на стыке информатики, биологии и искусственного интеллекта [4, 5, 6]. Они находят применение при решении различных задач исследования графов [6], автоматизированного проектирования [6-1], построения правил вывода в самонастраивающейся экспертной системе продукционного типа [8].

В настоящее время генетические алгоритмы (ГА) — хорошо известная и эффективная оптимизационная методология, основанная на аналогии процессов натуральной селекции и генетических преобразований. Биологические основы этой эффективной методологии для адаптационных процессов есть эволюция от одного множества альтернативных решений к другому. Причем, основой этого процесса является "выживание сильнейших", что выполняется путем исключения "слабо приспособленных" решений и оставление оптимальных или квазиоптимальных решений [11].

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

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

Однако разработка и программная реализация ГА, а также их применение и распространение, совершенствование и развитие сдерживаются целым рядом причин, среди которых доминируют следующие [12]: разработка практически каждого ГА является уникальной ввиду жесткой привязки к задаче на этапах кодирования и декодирования ее решений в виде генов и хромосом. Разработчики обычно «наследуют» и развивают только опыт построения отдельных генетических операторов (ГО) и общей организации процедур генетического поиска решений в ГА; программная реализация ГА производится практически с нуля. При этом в новых проектах обычно теряются все наработки программистов, связанные с оптимизацией структур данных, построения и кода самой программы, а также средствами повышения эффективности вычислений на основе различных эвристик; программная реализация ГА, как правило, заканчивается разработкой «вещи в себе» - программного продукта, ни в коей мере не относящегося к категории открытых систем. При этом теряется возможность оперативных сравнительных исследований эффективности применения данного ГА для решения рассматриваемой задачи с подобными ему или алгоритмами других классов;

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

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

Наличие отмеченных факторов подчеркивает актуальность создания универсальной интегрированной инструментальной среды для разработки, исследования и практического использования генетических алгоритмов решения целого множества различных задач поисковой оптимизации [13].

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

1. Построена открытая архитектура интегрированной инструментальной ПГП поиска.

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

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

4. Разработан механизм, обеспечивающий открытость 111 II для интеграции уникальных алгоритмов ГО преобразования кодовых строк решений.

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

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

Методы исследования. Для решения поставленных задач использовались методы теорий множеств, алгоритмов, графов, математической статистики и планирования эксперимента, а также методы и средства эволюционного моделирования, параллельного и объектно-ориентированного программирования.

Приведенные в работе положения подтверждаются экспериментальными результатами.

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

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

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

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

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

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

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

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

Апробация основных теоретических и практических результатов работы. Результаты диссертации докладывались и обсуждались на Международных научно-технических конференциях: Международной научно-технической конференции «Интеллектуальные системы (IEEE AIS'04)» (с. Дивноморское, 2004), Международной научно-технической конференции «Интеллектуальные системы» (AIS'05) и «Интеллектуальные САПР» (CAD-2005) (с. Дивноморское, 2005г. Получено свидетельство об официальной регистрации программы для ЭВМ № 2006612763, 2006г. По итогам открытого конкурса на лучшую научную работу студентов по естественным, техническим и гуманитарным наукам в вузах Российской Федерации, проводимого Министерством образования и науки

РФ, получена медаль и удостоверение от 15.07.2005г. «за лучшую научную работу».

Публикации. По теме диссертационной работы опубликовано 7 печатных работы, сделано 2 доклада на Международных научно-технических конференциях.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на 175 страницах, содержит 28 рисунков, 14 таблиц, 104 наименования библиографии и приложения.

4.5. ВЫВОДЫ

1. Дополнительные расходы времени, затраченные подсистемой генетического поиска на реализацию генетического алгоритма, не превосходят 6% по сравнению с реализацией данного алгоритма на языке программирования С++.

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

3. Качество размещений, полученных генетическим алгоритмом, разработанным с использованием интегрированной инструментальной подсистемы, в среднем на 6,38% превосходит результаты размещения, полученные с использованием известных алгоритмов Capo 8.6, Feng Shui 2.0, Dragon 2.23, что говорит об эффективности предложенного алгоритма и подсистемы генетического поиска в целом.

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

В качестве языка описания процедур генетического поиска проектных решений выбран XML. Для задания структуры и семантики описания, а также правил верификации использован язык описания схем - XML Schema Definition.

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

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

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

7. Разработаны алгоритмы детализации описания ГА, функционирования ядра ПГП, а также алгоритмы функционирования подсистем макроэволюционно-го и метаэволюционного моделирования на этапе сборки и на этапе выполнения ГА.

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

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

10.С использованием реализованной подсистемы генетического поиска разработан генетических алгоритм двумерного размещения разногабаритных элементов схем ЭВА, который использует мультихромосомное кодирование содержащее: числовую гомологичную хромосому - определяющую последовательность элементов, путем «кодирования перестановок»; двоичную хромосому - для кодирования ориентации элементов в пространстве.

Для формирования новых решений генетический алгоритм использует операторы кроссинговера, мутации и инверсии, построенные на основе разработанных стратегий формирования точек разрыва и формирования потомков с использованием алгоритма построения множества Кантора.

Проведенный вычислительный эксперимент подтвердил полиномиальную вычислительную и пространственную сложность разработанного алгоритма. При этом качество размещений, полученных генетическим алгоритмом в среде ПГП, в среднем на 6,56% превосходит результаты размещения, полученные с использованием известных алгоритмов Capo 8.6, Feng Shui 2.0, Dragon 2.23, что говорит об эффективности предложенного алгоритма и подсистемы генетического поиска в целом.

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

2. Колчин А.Ф. и др. Управление жизненным циклом продукции. М.: Анарха-сис, 2002.

3. Батищев Д.И., Львович Я.Е., Фролов В.Н. Оптимизация в САПР. Воронеж: Изд-во ВГУ, 1997.

4. Holland John Н., Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

5. Грант В. Эволюционный процесс http://alpha.ipr.serpukhov.su/~mlobanov/-grant/index.html

6. Гринченко С.Н. «Метод «проб и ошибок» и поисковая оптимизация: анализ, классификация, трактовка понятия «Естественный отбор» http://zhurnal.ape.relarn.ru/articles/2003/104.pdf

7. Курейчик В.М. Генетические алгоритмы. Монография. Таганрог: ТРТУ, 1998.

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

9. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы: учебное пособие под ред. В.М. Курейчика. Ростов-на-Дону:000 «Росиз-дат», 2004.-400с.

10. Kureichik V.M., Zinchenko L.A. Evolutionary adaptation in the modeling of nonlinear electrical circuits. Proceedings NOLTA 2000, Dresden, 17-21 September, 2000, v.l, p. 221-224.

11. И.Курейчик B.B. Эволюционные методы решения оптимизационных задач. Таганрог, 1999, ТРТУ.

12. Курейчик В.В., Нужнов Е.В. «Возможности организации интегрированной инструментальной среды поддержки процедур генетического поиска и оптимизации решений»

13. В.Гладков JI.A., Зинченко JI.A., Курейчик В.В., Курейчик В.М., Лебедев Б.К., Нужнов Е.В., Сорокин С.Н. Методы генетического поиска: Научное издание / Под ред. В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2002. - 122с.

14. Н.Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. М.:Физматлит, 2003.

15. Рутковская Д. Пилиньски М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия - Телеком, 207. 452с.

16. Исаев С. «Генетические алгоритмы в задачах оптимизации» http://www.uran.donetsk.ua/~masters/2005/kita/shestopalov/library/gaoptim.htm

17. Цой Ю.Р. «Применение генетического алгоритма для задач оптимизации многоэкстремальных функций».

18. Handbook of Genetic Algorithms. Edited by Lawrence Davis. USA: Van No-strand Reinhold, New York, 1991.

19. Редько В.Г., Цой Ю.Р. «Оценка эффективности эволюционных алгоритмов».

20. Редько В.Г., Цой Ю.Р. «Уточнение оценок эффективности эволюционных алгоритмов». Конференция «Интеллектуальные системы».

21. Гридин В.Н. Теоретические основы построения базовых адаптируемых компонентов САПР МЭА. М.: Наука, 1989.

22. Редько В.Г. «Оценка эффективности простейшей версии генетического алгоритма».

23. Редько В.Г. «Эволюционная кибернетика» http://library.mephi.ru/data/-scientific-sessions/2002/Lec Neuro 1/029.html

24. Цой Ю.Р. «О математических моделях эволюционных алгоритмов» //Перспективные информационные технологии и интеллектуальные системы 2006г.

25. Смирнова О.В. Модели эволюции в задачах компоновки схем ЭВА. Перспективные информационные технологии интеллектуальные системы, №1 (19), 2002, с.47-49.

26. Дарвин Ч. Происхождение видов путем естественного отбора. М.: Наука, 2000.

27. Goldberg David Е. Genetic Algorithm in Search, Optimization and Machine Learning. USA.: Addison-Wesley Publishing Company. Ind., 1989.

28. Ламарк Ж.Б. Философия зоологии. T.1,2, М.-Л.: «Академия», 1939.

29. Дубинин Н.П. Избранные труды, Т.1. Проблемы гена и эволюции. М.: Наука, 2000.

30. Кимура М. Молекулярная эволюция: теория нейтральности. М.: Мир, 1985, 400 с.

31. Эволюционная эпистемология и логика социальных наук: Карл Поппер и его критики// Составление Д.Г. Лахути, В.Н. Садовского, В.К. Финна. М.: Эди-ториал УРСС, 2000.

32. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Монография. Таганрог: Изд-во ТРТУ, 2001.

33. Luger G. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Fourth Edition. Addison-Wesley Publishing Company, 2002.

34. GeneHunter targets optimal solutions with genetic http://www.neuroproiect.ru/-aboutproduct.php?info=ghinfo

35. Evolver The Innovative Optimizer for Windows. http://www.palisade-europe.com/evolver/default.asp

36. Афанасьев M.K. «Построение и исследование генетических алгоритмов с использованием NSGalaxy» http://alice.stup.ac.ru/005/nits2000/sec2/sec2-16.htm.

37. Вермишев Ю.Х. Основы автоматизированного проектирования. М.: Радио и связь, 1988.

38. Библиотека GeneBase 2.0 http://www.basegroup.ru

39. GAlib: Matthew's С++ Genetic Algorithms Library http://lancet.mit.edu/ga/

40. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР. -М.: Энергоатомиздат, 1987.

41. Лебедев Б.К. Методы поисковой адаптации в задачах автоматизированного проектирования СБИС. Таганрог, Изд-во ТРТУ, 2000.

42. Берштейн Л.С., Карелин В.П., Целых А.Н. Модели и методы принятия решений в интегрированных ИС. Ростов-на-Дону, изд-во РГУ,1999.

43. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры. М.: Изд-во МГТУ, 2002.

44. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

45. Малышев Н.Г., Мицук Н.В. Основы оптимального управления процессами автоматизированного проектирования. М.: Энергоатомиздат, 1990.

46. Sherwani Naveed. Algorithms for VLSI Physical Design Automation Boston/Dordrecht/London: Kluwer Academic Publishers, 1995.

47. Бакало M.A., Курейчик B.B. К вопросу модифицированного алгоритма размещения. // ПИТИС 2006г. № 4(28) Таганрог, 2006, с.44-55.

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

49. Бакало М.А., Курейчик В.В. Модифицированный алгоритм размещения методом парных перестановок. //ИЗВЕСТИЯ ТРТУ. Интеллектуальные САПР 2007г. Таганрог.: Науч. изд., 2007, с.77-84.

50. Харари Ф. Теория графов. М.: Мир, 1977.51 .Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

51. Бершадский A.M. Применение графов и гиперграфов для автоматизации конструкторского проектирования РЭА и ЭВА. -Саратов: Изд-во СГУ, 1993.

52. Глушань В.М. Графовые модели представления вычислительных алгоритмов. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 133-138.

53. Bourque P., Dupuis R. Guide to the Software Engineering Body of Knowledge // IEEE Computer Society, 2001.

54. Автоматизация проектирования БИС. В 6 кн. Под ред. Г.Г. Казеннова. М.: Высшая школа, 1990.

55. Вигерс К. Разработка требований к программному обеспечению /Пер. с англ. М.: Издательско-торговый дом «Русская редакция», 2004. - 574с.: ил.

56. Гатчин Ю.А., Коробейников А.Г. Методы представления математических моделей в САПР при концептуальном и инфологическом моделировании. IEEE AIS-03, CAD-2003. Интеллектуальные системы, интеллектуальные САПР т.2, М.: Физматлит, 2003, с 35-41.

57. Макконнел С. Совершенный код. Мастер класс / Пер. с англ. М.: Издательско-торговый дом «Русская редакция»; СПб.: Питер, 2005 - 896с.: ил.

58. Кормен Т., Лейзерсон И., Ривест Р. Алгоритмы: построения и анализ М.: МЦМО, 2000.

59. Бородкин Л.И. «Многомерный статистический анализ» http://iwww.iskunstvo.info/-,edu/iinf/-,cluster.htm

60. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. «Приемы объектно-ориентированного проектирования: паттерны проектирования» СПб: Питер, 2001 -368с.

61. Gunderloy М. Developer to Designer. GUI Design for the Busy Developer San Francisco, London: Sybex, 2005 - 367c.

62. Backalo M.A.The finding of the maximum matching using neural network. Proceedings of the International Scientific Conferences "Intelligent Systems (IEEE AIS'04)" and "Intelligent CAD's (CAD- 2004)". M, Physmathlit, 2004. vol. 3. pp. 121.

63. Страуструп Б. Язык программирования С++, спец.изд. /Пер. с андл. М.; СПб.: «Издательство БИНОМ» - Невский диалект», 2002 - 1099с.

64. Бакало М.А. Варианты представления различных типов данных, их кодирование и декодирование в виде хромосом // ИЗВЕСТИЯ ТРТУ. Интеллектуальные САПР 2007г. Таганрог : Науч. изд., 2007, с.70-75.

65. Гладков JI.A., Курейчик В.В., Курейчик В.М. Основы теории алгоритмов / под ред. В.М. Курейчика. Учебное пособие по курсу «Математическая логика и теория алгоритмов». Таганрог. ТРТУ, 2002, - 82с.

66. Мелихов А.Н., Берштейн JI.C. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов на-Дону. Изд-во РГУ,1981.

67. Схемы алгоритмов и программ. Правила выполнения. ГОСТ 19.002-80.

68. Схемы алгоритмов и программ. Обозначение условные графические. ГОСТ 19.003-80.

69. Спецификация Extensible Markup Language http://www.w3.org/XML.

70. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2000.

71. Семакин М.М. «Компонентная модель организации программных систем» -Ижевск, 2004.

72. Бакало М.А., Курейчик В.В. Концепция построения системы поддержки генетических алгоритмов // Прикладные информационные технологии и интеллектуальные системы №4 Науч. изд. Таганрог, 2006.

73. Элджер Жд. С++:Библиотека программиста СПб.: Питер, 2000. - 320с.

74. Плаугер П., Степанов А., Ли М., Массер Д. STL стандартная библиотека шаблонов С++ / Пер. с англ. - СПб.: БХВ-Петербург, 2004. - 656с.: ил.

75. Александреску А. Современное проектирование на С++. Серия С++ in-Depth, т.З.: Пер. с англ. М.: Издательский дом «Вильяме», 2002 - 336с.: ил.

76. Леденев А., Акентьев А., Сторожевых В., Семенов И. Вопросы написания DLL. http://www.progz.ru/print.php?articles=45.

77. Спецификация языка описания схем XML (XML Schema Definition XSD) http://www.w3.org/2001XMLShcema.

78. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента: Учеб. пособие./ Под общ. ред. Останина А.Н. -Минск.: Вышэйшая школа., 1989. 218 е.: ил.

79. Львовский Е.Н. Статистические методы построения эмпирических формул: Учеб.пособие для втузов -М.: Высшая школа, 1988.-239 е.: ил.

80. Адлер Ю.П. Введение в планирование эксперимента -М.: Металлургия, 1969. 157 е.: ил.

81. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики -М.: Наука, 1977.-264 с.

82. Гроппен В.О. Принципы оптимизации комбинаторных процедур. Ростов-на-Дону : Издательство РГУ,-1988.-195 с.:ил.

83. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990 г. 216 с.88.3айченко Ю.П. Исследование операций Киев: Вища школа, 1975. - 320 с.

84. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов -М.: Наука, 1986.-544 е.: ил.

85. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений М.: Физматгиз, 1962. 349 е.: ил.

86. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий. -М.: Наука, 1971.283 е.: ил.

87. Андерсон Т. Введение в многомерный статистический анализ / Пер. с англ. Кичатова Ю.Ф. М.: Физматгиз, 1963. 500 е.: ил.

88. Болыпов Л.Н., Смирнов Н.В. Таблицы математической статистики. -М.:Наука, 1965.464 с.

89. Гурский Е.И. Теория вероятностей с элементами математической статистики. М.: Высшая школа, 1971. 328 с.

90. Гренандер У. Случайные процессы и статистические выводы / Пер. с англ. и доп. Яглоба A.M. -М.:Изд-во иностранной лит., 1961. 167 с.

91. Даймонд С. Статистика в науке/ Пер. с англ. Дружининой А.Л. М.: Статистика, 1970. 155 с.

92. Caldwell А. Е., Kahng А. В., Markov I. L. Can Recursive Bisection Alone Produce Routable Placements? DAC 2000, pp.477-82.

93. Caldwell A. E., Kahng A.B., Markov I. L. Optimal Partitioners and End-case Placers for Standard-cell Layout IEEE Trans, on CAD, vol. 19(11) 2000, pp. 1304-1314

94. Wang M., Yang X., Sarrafzadeh M. Dragon2000: Standard-cell Placement Tool for Large Industry Circuits ICCAD2000, pp. 260-263.

95. Yang X., Choi B.-K., Sarrafzadeh M. Routability Driven White Space Allocation for Fixed-Die Standard-Cell Placement ISPD 2002, pp. 42-50.

96. Yang X., Choi B.-K., Sarrafzadeh M. Timing-Driven Placement using Design Hierarchy Guided Constraint Generation ICC AD 2002, pp. 177-184.

97. Agnihotri A., Yildiz M. C., Khatkhate A., Mathur A., Ono S., Madden P.H. Fractional Cut: Improved Recursive Bisection Placement ICCAD2003

98. Yildizand M.C., Madden P.H. Improved Cut Sequences for Partitioning Based Placement DAC2001, pp.776-779.

99. IBM-PLACE 2.0 benchmark suits http://er.cs.ucla.edu/benchmarks/ibm-place2/bookshelf/ibm-place2-all-bookshelf-nopad.tar.gz1. АКТоб использовании результатов диссертационной работы Бакало М.А.

100. Разработка и исследование интегрированной инструментальной подсистемы генетического поиска проектных решений»на соискание ученой степени кандидата технических наук

101. Научные результаты, полученные в диссертационной работе Бакало М. А., использовались в г/б НИР №12361 «Разработка интеллектуальных систем проектирования для решения задач разбиения СБИС на основе эволюционных методов».

102. Разработка и исследование интегрированной инструментальной подсистемы генетического поиска проектных решений»на соискание ученой степени кандидата технических наук

103. Научные результаты, полученные в диссертационной работе Бакало М.А., использовались в г/б НИР №12362 «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

104. Технологического института Южного федерального университета в г. Таганроге результатов кандидатской диссертации Бакало М.А.

105. Разработка и исследование интегрированной инструментальной подсистемыгенетического поиска»

106. Указанные результаты используются при чтении следующих курсов на кафедре САПР: «Методы оптимизации», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования».

107. Работа выполнена в рамках приоритетного национального проекта «Образование».

108. Внедрение в учебный процесс ряда теоретических и практических результатов диссертационной работы Бакало М.А. позволило товысить качество подготовки специалистов проектирования САПР и информационных технологий.

109. Гривцов В.В. Вишняков Ю.М. Лебедев Б.К.оводителя1. ИЮФУ Пугач 2007 г.1. Начальник УО

110. Декан ФАВТ, д.т.н., профессор Зам. заведующего каф. САПР, д.т.н., профессор