авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |

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

-- [ Страница 1 ] --

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

БАКАЛО Михаил Анатольевич

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

Специальности: 05.13.12 – Системы автоматизации проектирования,
05.13.17 – Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

Таганрог 2007

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

Научный руководитель: доктор технических наук, профессор

Курейчик Владимир Викторович.

Научный консультант: кандидат технических наук, доцент

Нужнов Евгений Владимирович.

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

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

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

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

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

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

Ученый секретарь
диссертационного совета Д 212.208.22,
доктор технических наук, профессор Целых А.Н.

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

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

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





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

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Далее проведен сравнительный анализ существующих программных продуктов, реализующих ГА, таких как GeneHunter, программа NSGalaxy и библиотеки компонентов GAlib.

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

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

где zi – вариант размещения; k1, k2 – весовые коэффициенты, заданные таким образом, чтобы их сумма равнялась единице; L(zj) – суммарная длина проводников; O(L(zj)) – нормированная оценка общей длины проводников, приведенная к интервалу [0, 1]; Sобщ – фактическая площадь размещения, определенная как площадь минимального прямоугольника, описывающего размещенные элементы; P(Sобщ(zj)) – нормированная оценка общей площади размещения, принимающая значения из интервала [0, 1].

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

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

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

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

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

  • числовую гомологичную хромосому H1 – определяющую последовательность элементов путем «кодирования перестановок»;
  • двоичную хромосому H2 – для кодирования ориентации элементов в пространстве.

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

Рис. 1. Результат декодирования решения p.

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

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

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

  • «готова» – все данные, необходимые для выполнения ГО, ассоциированного с вершиной, готовы для его выполнения;
  • «выполняется» – выполнение макрогенетического алгоритма не завершено в момент проверки состояния вершины, с которой он ассоциирован;
  • «ожидание» – в момент помещения вершины в очередь обработки не были готовы данные, необходимые для выполнения оператора, связанного с данной вершиной.
  • «завершена» – выполнение оператора, ассоциированного с данной вершиной, завершилось успешно.

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

Рис. 2. Граф состояний операторов МетаГА.

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

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

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

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

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

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



Pages:   || 2 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.