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

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

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

Pages:   || 2 |

Разработка и исследование алгоритмов эволюционного синтеза комбинационных схем

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

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

Гудилов Виталий Витальевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ ЭВОЛЮЦИОННОГО СИНТЕЗА КОМБИНАЦИОННЫХ СХЕМ

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

Автореферат

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

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

Таганрог 2007

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

Научный руководитель: заслуженный деятель науки РФ,

доктор технических наук, профессор

Курейчик Виктор Михайлович

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

(первый проректор Таганрогского

Государственного Педагогического Института, г. Таганрог),

доктор технических наук, профессор

Ковалев Сергей Михайлович

(Ростовский государственный университет путей и сообщений, г. Ростов-на-Дону),

Ведущая организация: Федеральное государственное унитарное предприятие

«Таганрогский научно-

исследовательский институт

связи», г. Таганрог.

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

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

Автореферат разослан « 27 » июля 2007 г.

Ученый секретарь диссертационного совета Д 212.208.22,

доктор технических наук, профессор Целых А.Н.

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

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

Исследования в области проектирования эволюционных аппаратных средств получили набольшее развитие в связи с построением автономных интеллектуальных систем и выходом технологий проектирования микроэлектроники на качественно новый уровень. В настоящий момент большинство работ и исследований в области эволюционного проектирования аппаратных средств проводятся в крупнейших исследовательских центрах, размещенных в Японии, Центральной Европе и России. Основной вклад в развитие методов эволюционного проектирования внесли С.Д. Луис (S.J. Louis), Г.Д. Раулинс (G.J. Rawlins), Д.С. Галлахер (J.C. Gallagher), Д.Р. Коза (J.R. Koza), С.А. Коелло (C.A. Coello), К.А. ДеДжонг (K.A. DeJong), Д.Е. Голдберг (D.E. Goldberd), С.Д. Скотт (S.D. Scott), Д.Х. Холланд (J.H. Holland), В.М. Курейчик (V.M. Kureichik), Д.И. Батищев (D.I. Batishev), Т.К. Васильев (V.K. Vassilev), Л.А. Зинченко (L.A. Zinchenko), А. Томпсон (A. Thompson), Т. Хигучи (T. Higuchi), И. Такаши (I. Takashi), И. Тажитани (I. Kajitani), Т. Хошино (T. Hoshino), Х. Саканаши (H. Sakanashi), С. Прабхас (C. Prabhas), Е. Такахаши (E. Takahashi), Т. Калганова (T. Kalganova), Х. Мюленбайн (H. Mhlenbein) и многие другие.





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

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

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

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

  1. Разработка бинарного и десятичного алгоритмов эволюционного синтеза комбинационных схем для программируемых логических матриц (ПЛМ).
  2. Разработка десятичного алгоритма эволюционного синтеза комбинационных схем для заданного базиса логических элементов (ЛЭ).
  3. Разработка структуры параллельного взаимодействия генетического материала в (ГО).
  4. Разработка структуры конвейерного взаимодействия генетических операторов ГО.
  5. Разработка устройства эволюционного синтеза комбинационных схем для ПЛМ.

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

Научная новизна работы заключается в решении задачи автоматизированного синтеза комбинационных схем для аппаратно-ориентированных систем реального времени. В работе:

  1. Разработаны бинарный и десятичный генетический алгоритм автоматизированного синтеза комбинационных схем для ПЛМ, десятичный генетический алгоритм автоматизированного синтеза комбинационных схем для заданного базиса ЛЭ, позволяющие получать множество комбинационных схем для заданного функционального описания.
  2. Разработаны методы бинарного и десятичного кодирования и декодирования схем в ПЛМ и на основе заданного базиса ЛЭ, позволяющие выполнять переход между схемотехническим и закодированным представлением синтезируемых схем, что позволяет существенно повысить скорость синтеза схемных решений.
  3. Выполнена аппаратная реализация генетического алгоритма автоматизированного синтеза комбинационных схем для ПЛМ, разработаны методы организации многопоточных параллельных вычислений с поддержкой динамических изменений параметров алгоритма синтеза в процессе функционирования, что позволило выполнять параллельную обработку и синтез комбинационных схем в режиме реального времени.
  4. Разработан инструментальный комплекс для автоматизированного синтеза комбинационных схем на основе базиса ЛЭ, позволяющий выполнять синтез заданного множества комбинационных схем в различных базисах, а также исследовать поведение алгоритма в зависимости от изменений параметров функционирования.

Решение поставленных задач позволяет автору защищать следующие новые научные результаты:

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


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

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

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

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Технологического института Южного федерального университета (ТТИ ЮФУ) «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска» и «Разработка бионических методов и принципов поиска оптимальных решений при проектировании».

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

Получен патент на изобретение Российской Федерации №2294561 «Устройство аппаратной реализации вероятностных генетических алгоритмов», заявка № 2005108760 от 28.03.2005 г.

Апробация основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на VI и VII Всероссийской научной конференции с международным участием “Новые информационные технологии. Разработка и аспекты применения” (г. Таганрог, 2003 и 2004 гг.), VII Всероссийской научной конференции студентов и аспирантов “Техническая кибернетика, радиоэлектроника и системы управления” (г. Таганрог, 2004 г.), II Всероссийской научной конференции “Методы и средства обработки информации” (г. Москва, МГУ им. М. В. Ломоносова, 2005 г.), Международная конференция «Интеллектуальные системы (IEEE AIS’06)», (с. Дивноморское, 2006 г.), X Национальной конференции по искусственному интеллекту с международным участием “КИИ – 2006” (г. Обнинск 2006 г.).

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

Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложения. Работа содержит 187 стр., а также 50 рисунков, 1 таблицу, список литературы из 120 наименований, 60 стр. приложений и актов об использовании.

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

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

В первой главе рассмотрено состояние проблемы, проведены анализ и классификация алгоритмов синтеза, показано, что перспективными исследованиями являются алгоритмы синтеза, использующие в своей основе эволюционные методы, что позволяет получать набор решений, оптимальных по заданным критериям. Большое внимание уделено методам и специфике эволюционного проектирования аппаратных средств, показаны преимущества и недостатки применения методов эволюционного синтеза в сравнении с другими методами для решения задачи синтеза схем. Отмечено, что основным средством повышения быстродействия времеемких алгоритмов эволюционного синтеза является применение методов аппаратной реализации с организацией многопоточных параллельных вычислений. Выполнена постановка задачи синтеза комбинационных схем, представленных в виде множества R = {H, cF, P}, где элемент множества H определяет генотип синтезируемого решения; элемент cF определяет оценку математической модели синтезируемой схемы как критерий отбора; элемент P определяет вероятность передачи наследственной информации. Решение задачи синтеза заключается в поиске схемы, для которой cF = 1.

Вторая глава диссертационной работы посвящена разработке ГА: бинарного и десятичного алгоритма эволюционного синтеза комбинационных схем для ПЛМ и десятичного алгоритма эволюционного синтеза комбинационных схем для заданного базиса ЛЭ. Выполняется аппаратно-ориентированная разработка ГО и методов их взаимодействия. Предложены методы бинарного кодирования схемы в виде хромосомы на основе структуры ПЛМ, где хромосома Hl,m+q кодирует двумерный массив Мl,m+q, определяющий состояние перемычек ПЛМ. Двумерный массив Мl,m+q определен как матрица конъюнкторов Сl,m размерности l на m и матрица дизъюнкторов Dl,q, размерности l на q, где m = 2c столбцов определяют конъюнктивные термы, количество строк l = 2с, с – количество входных переменных аналитических функций, представленных в виде ДНФ и q – количество функций.

Для десятичного кодирования структура хромосомы определена как массив, элементы которого представлены матрицей конъюнкторов Сl,m, размерности l на с и матрицей дизъюнкторов Dl,q, размерности l на q, где с – количество входных переменных, количество строк 0 l <2с определяет количество дизъюнкций и q – количество входных функций, описывающих искомую схему.

Для алгоритма эволюционного синтеза комбинационных схем для базиса ЛЭ кодирование хромосомы определяется на основе матричного представления схемы Mm,n (

рисунок 1 а)), содержащей абстрактные логические элементы (АЛЭ), посредством перехода от двумерной индексации ЛЭ (столбец m, строка n) в синтезируемой схеме к одномерной. Число с входов xс, поступающих на схему, образуют нулевой столбец входов элементов L0,n, где n = с задает количество строк матрицы Mm,n. Количество выходов схемы yq, определяется согласно количеству q аналитических выражений, описывающих закон функционирования искомой схемы. Номера элементов Lr,t в схеме имеют сквозную нумерацию, совпадающую с нумерацией логических элементов внутри матрицы Mm,n и используемую при синтезе схемы для обозначения выхода элемента. Индексы элементов Lr,t r и t задаются согласно порядковому расположению элемента в матрице Mm,n, по возрастанию слева направо и сверху вниз, где 0 t < n и 0 r m (нулевой столбец m = 0 содержит сигналы входов схемы, т.е. количество столбцов m дополнено столбцом входов). Выходы схемы y подключаются только к выходам элементов Lr,t столбца m (r = m), при этом элемент нулевой строки Lm,0 соответствует нулевому выходу y0 схемы и т.д.

В качестве минимального базиса ЛЭ определено множество L = {Li | i = 1, 2,..., nl}, элементами которого являются стандартные двухвходовые элементы “И”, “ИЛИ”, “XOR” и одновходовые элементы “НЕ” и “WIRE”, имеющие один выход, где nl – количество элементов множества. Функциональные составляющие элементов “И”, “ИЛИ”, “XOR” и “НЕ” аналогичны соответствующим им логическим элементам. Функциональный элемент “WIRE” (перемычка) выполняет передачу сигнала, поступающего на единственный вход элемента к выходу, без каких-либо изменений функциональной составляющей входного сигнала. Кодирование элементов функционального базиса выполняется посредством назначения кода в порядке возрастания их порядкового номера.

  а) – представление схемы,-2

Рисунок 1 – а) – представление схемы, содержащей матрицу n на m ЛЭ Lr,t, имеющую с входов и q выходов; б) – представление структуры хромосомы, кодирующей схему

Расположение АЛЭ в узлах решетки схемы остается неизменным в процессе синтеза схемы, а изменяется лишь их функциональная составляющая (код) и соединения между входами и выходами элементов. Логический элемент Lr,t, кодируемый геном gr,t, заносится в хромосому H последовательно, по столбцам, от младшего элемента t столбца r к старшему, где 0 < r  m, 0  t < n (рисунок 1 б)). Каждый ген хромосомы H определяется вектором gn = {gni | i = 1,2,3}, который кодирует отдельно взятый ЛЭ Lr,t, где элементы вектора gn1 и gn2 задают информацию о входах r и t ЛЭ Lr,t, и gn3 задает код кодируемого ЛЭ Lr,t. Локус гена в хромосоме соответствует заданной позиции кодируемого им элемента в схеме, т.о. значение, получаемое на выходе ЛЭ, ассоциируется с отождествляемым ему геном. Переход к многовходовым схемам возможен посредством дополнения функционального базиса новыми элементами и модификации структуры гена хромосомы. Приведенные методы кодирования схем могут быть легко доработаны для различных представлений структуры ЦУ и включать необходимые технологические ограничения, требуемые для реализации задачи синтеза с учетом специфики функционирования ЦУ. Подобные ограничения достаточно отразить в структуре гена или хромосомы и в дальнейшем учитывать при анализе схемы.



Pages:   || 2 |
 

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







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

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