WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


 

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

                                                                       

Ляшов Максим Васильевич

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

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

(вычислительная техника и информатика)

  05.13.05 – Элементы и устройства вычислительной

техники и систем управления

АВТОРЕФЕРАТ

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

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

Таганрог 2012

Работа выполнена в Южно-Российском государственном университете экономики и сервиса.

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

Берёза Андрей Николаевич

Официальные оппоненты:                Чернышев Юрий Олегович

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

Донской государственный технический университет, профессор кафедры «Авто­матизация производственных процессов»

Безуглов Дмитрий Анатольевич

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

Ростовский технологический институт сервиса и туризма, заведующий кафедрой «Информационные технологии в сервисе»

Ведущая организация:                        ОАО «Таганрогский научно-

исследовательский институт связи»,

г. Таганрог

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

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

Автореферат разослан «05» марта 2012 г.

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

диссертационного совета                                                Целых А.Н.

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

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

В САПР для проектирования цифровых и аналоговых устройств в настоящее время применяются эволюционные алгоритмы (ЭА). Это направ­ление получило название «эволюционная электроника» (Evolutionary Electronics). Применение ЭА на аппаратных платформах, имеющих реконфи­гурируемые элементы, позволяющие перестраивать систему во время функционирования, получило название эволюционные аппаратные средства. Научные исследования в этом направлении ведутся как в России, так и за рубежом. Результаты этих исследований приведены в работах В.М. Курейчика, В.В. Гудилова, С.В. Черуна, Д.Р. Коза, Г. Гариссона, Т. Хигучи, Д.Е. Голдберга, Е. Такахаши и др.

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

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

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

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

В работах В.М. Курейчика, С.В. Черуна, В.В. Гудилова, Т. Хигучи и других представлены эволюционные алгоритмы синтеза комбинационных логиче­ских схем для ЭАС. Применяемые в настоящее время методы синтеза конеч­ных автоматов всегда используют специфику решаемой задачи, делая полученную технику генерации автоматов неприменимой к остальным задачам. Возникает вопрос создания универсальных методов синтеза конечных автоматов, применимых к широкому кругу задач. В работах А.А. Шалыто, П.Г. Лобанова, Г. Хорихана, К. Вольфа и др. показано применение эволюционных алгоритмов для синтеза конечных автоматов. Однако пред­ставленные алгоритмы применяются для автоматного программирования, в рамках которого программа описывается с помощью конечных детерминиро­ванных автоматов, что не позволяет использовать их в автономных аппаратных системах на реконфигурируемых платформах.

Учитывая вышеизложенное, можно утверждать, что тема диссертаци­онного исследования, связанная с разработкой генетических алгоритмов синтеза конечных автоматов для автономных эволюционных аппаратных средств, является АКТУАЛЬНОЙ.

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

Достижение указанной цели предполагает решение следующих основ­ных задач:

  1. Провести исследование методов синтеза конечных автоматов и особенно­стей использования современных систем автоматизированного проекти­рования для создания эволюционных аппаратных средств.
  2. Разработать генетический алгоритм кодирования состояний конечного автомата, который бы не уступал по эффективности существующим алго­ритмам, используемым в современных САПР.
  3. Разработать аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов для автономных эволюционных аппаратных средств.
  4. Выполнить аппаратную реализацию генетического алгоритма для реше­ния задачи автоматизированного синтеза конечных автоматов на ПЛИС, позволяющую использовать разработанные генетические алгоритмы в автономных системах.
  5. Разработать инструментальный комплекс автоматизированного эволюцион­ного синтеза конечных автоматов, позволяющий проводить исследования поведения алгоритмов в зависимости от изменений пара­метров синтеза.

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

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

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

На защиту выносятся следующие основные результаты и положения:

  1. Генетический алгоритм кодирования состояний конечного автомата  (по специальности 05.13.12).
  2. Аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов (по специальности 05.13.12).
  3. Устройство автоматизированного синтеза конечных автоматов, реализованное на ПЛИС (по специальности 05.13.05).
  4. Программный комплекс автоматизированного эволюционного синтеза конечных автоматов (по специальности 05.13.12).

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

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

  • «Разработка теории и принципов автоматизации проектирования на схемотехническом уровне устройств вычислительной техники с применением бионических методов» (№ г.р. 01.2.00 606 713, 2006 г.). Автором в качестве исполнителя были разработаны модифицированные генетические операторы для задачи автоматизации проектирования устройств вычислительной техники на схемотехническом и логическом уровнях.
  • «Разработка и исследование реконфигурируемых гибридных эволюционных аппаратных систем» № 2.1.2/6959 (ЮРГУЭС-9.09.Ф). Автором в качестве исполнителя были разработаны: аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов; генетический алгоритм кодирования состояний конечного автомата; устройство автоматизированного синтеза конечных автоматов, реализованное на ПЛИС.
  • «Разработка и исследование бионических алгоритмов вычислительной математики для подсистемы схемотехнического моделирования» № 2.1.2/4595 (ЮРГУЭС-6.09.Ф). Автором в качестве исполнителя были разработаны генетические операторы для подсистем схемотехнического моделирования.

Кроме того, материалы диссертационной работы использованы в учебных процессах в ФГБОУ ВПО ЮРГУЭС (г. Шахты) на кафедре «Информационные системы и радиотехника» в дисциплинах «Интеллектуальные информационные системы», «Архитектура ЭВМ и систем», «Цифровые устройства и микропроцессоры», ВИС ФГБОУ ВПО ЮРГУЭС (г. Волгодонск) на кафедре «Информационные технологии» в дисциплинах «Архитектура ЭВМ и систем», «Интеллектуальные информационные системы» и в ШИ(Ф) ФГБОУ ВПО ЮРГТУ(НПИ) (г.Шахты) на кафедре «Электрификация и автоматизация производства» в дисциплинах «Автоматизация установок и комплексов», «Основы микропроцессорной техники» и «Элементы систем автоматики».

Апробация Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г. Геленджик, 2008-2011 гг.); Конгрессе по интеллектуальным системам и информационным технологиям «AIS-IT’09»; Международной научно-практической конференции «Научный потенциал молодёжи – будущее России» (г. Волгодонск, 2010 г.), Всероссийской научной конференции молодых ученых и аспирантов (г. Волгодонск, 2009 г.) .

Публикации. По материалам диссертационной работы опубликовано 16 печатных работ, в том числе 4 статьи в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утверждённых ВАК, получено 6 свидетельств об официальной регистрации программы для ЭВМ, сделано 9 докладов на Всероссийских и Международных научно-технических конференциях.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 176 страниц, включающих 59 рисунков, 14 таблиц, список литературы из 139 наименований, 20 страниц приложений и актов об использовании.

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

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

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

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

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

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

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

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

Рисунок 1 – Структурная схема аппаратно-ориентированного генетического алгоритма синтеза конечных автоматов

Основными генетическими операторами, используемыми при работе генетического алгоритма синтеза конечных автоматов, являются операторы кроссинговера и мутации.

Алгоритм модифицированного оператора мутации состоит из следующих шагов:

Шаг 1. Генерируется случайное число S, равномерно распределённое в интервале [0; n], где n – число переходов конечного автомата.

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

Шаг 3. Если было определено, что изменяется значение выходной переменной, то оно  случайным образом изменяется в переходе с индексом S.

Шаг 4. Если было определено, что изменяется номер состояния, то он  случайным образом изменяется в переходе с индексом S.

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

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

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

Шаг 1. Формируется список  доступных состояний с использованием алгоритма рекурсивного обхода графа.

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

Шаг 3. Если текущее состояние не входит в список доступных, то для него выполняются следующие операции.

Шаг 4. Случайным образом выбирается состояние из списка доступных состояний.

Шаг 5. Выбирается случайным образом один из переходов выбранного состояния и заменяется на переход, который ведет в текущее состояние.

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

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

Рисунок 2 – Структурная схема генетического алгоритма кодирования состояний конечного автомата

При решении задачи кодирования состояний конечного автомата используется целевая  функция:

где – расстояние по Хеммингу между кодами состояний k-ого перехода, p – количество переходов. Целевая функция определяет сложность (аппаратные затраты) на построение комбинационной схемы функции возбуждения, т.е. является одной из оценок сложности комбинационной схемы автомата.

Задачей генетического алгоритма является минимизация целевой функции:

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

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

Модифицированный оператор мутации в разработанном алгоритме работает следующим образом: в хромосоме случайно выбираются два гена и меняются местами.

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

Для применения разработанных генетических алгоритмов в автономных эволюционных аппаратных средствах было разработано устройство автоматизированного синтеза конечных автоматов. Устройство реализовано в виде завершенного модуля на ПЛИС. Применение разработанного устройства позволило сократить время поиска решения, по сравнению с программной реализацией алгоритмов, более чем в 60 раз.

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

В диссертационной работе эта проблема решается двумя путями:

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

На рисунке 3 показана разработанная реконфигурируемая структура на ПЛИС для создания динамически реконфигурируемых комбинационных ло­гических схем. В качестве универсального реконфигурируемого логического элемента был использован мультиплексор.

Рисунок 3 – Реконфигурируемая структура на ПЛИС

Реконфигурируемый модуль представляет собой матрицу из реконфи­гурируемых логических блоков (РЛБ). Основное отличие предлагаемой структуры, по сравнению с аналогами, – это возможность за один такт полностью перестраивать комбинационную схему, что позволяет создавать высокопроизводительные ЭАС.

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

Разработанный генетический алгоритм кодирования состояний конечного автомата был протестирован на промышленных тестовых задачах MCNC. На рисунке 4 приведено сравнение эффективности разработанного генетического алгоритма кодирования состояний (ГАКС) с двумя вариантами алгоритма NOVA и аналогичного генетического алгоритма.

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

Рисунок 4 – Сравнение эффективности разработанного генетического алгоритма кодирования состояний с аналогами

Разработанный аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов был протестирован на тестовых задачах об «Умном муравье» и построении автопилота для упрощенной модели вертолета. По количеству состояний синтезируемых конечных автоматов разработанный алгоритм не уступает аналогам, при этом время синтеза в 9 раз меньше, чем у существующих алгоритмов.

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

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

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

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

  1. Проведена классификация и предложено применение эволюционных аппаратных средств в качестве основы для создания автономных реконфигурируемых систем. Проведен анализ алгоритмов синтеза конечных автоматов, в результате которого было установлено, что используемые в настоящее время алгоритмы используют специфику решаемой задачи, делая полученную технику генерации автоматов не применимой для создания автономных эволюционных аппаратных средств.
  2. Определены основные этапы проектирования эволюционных аппаратных средств на ПЛИС и принципы оперативного изменения поведения системы. Предложен вариант отладки эволюционных аппаратных средств с использованием встроенных средств ПЛИС, позволяющий регистрировать состояния не только входов и выходов системы, но и состояния произвольных внутренних узлов.
  3. Разработаны аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов и генетический алгоритм кодирования состояний конечного автомата, предназначенные для синтеза КА в автономных эволюционных аппаратных средствах. Найдены теоретические оценки временной сложности разработанных алгоритмов – .
  4. Выполнена аппаратная реализация генетического алгоритма для решения задач автоматизированного синтеза конечных автоматов на ПЛИС, которая позволила сократить время поиска решения более чем в 60 раз, что в свою очередь дает возможность использовать разработанные генетические алгоритмы в автономных эволюционных аппаратных средствах. Разработана реконфигурируемая структура на ПЛИС и предложено применение встроенных блоков памяти для создания перестраиваемых комбинационных логических схем. Это позволило создавать конечные автоматы для ЭАС с  динамической перестройкой внутренней структуры.
  5. Проведены экспериментальные исследования разработанных алгоритмов синтеза и кодирования состояний конечных автоматов, в результате которых были определены оптимальные сочетания управляющих параметров и получена полиномиальная зависимость времени решения задачи от числа состояний автомата, которая подтвердила теоретические оценки. Разработан инструментальный комплекс автоматизированного эволюционного синтеза конечных автоматов, позволяющий проводить исследования поведения алгоритмов в зависимости от изменений параметров синтеза.
  6. Выполнено сравнение разработанных генетических алгоритмов. Генетический алгоритм кодирования состояний конечного автомата сравнивался с аналогом и классическими алгоритмами NOVA1, NOVA2  на промышленных тестовых задачах MCNC. Полученные результаты в среднем на 20% лучше, чем у существующих алгоритмов. Сравнение разработанного генетического алгоритма синтеза конечных автоматов проводилось на тестовых задачах об «Умном муравье» и построении автопилота для упрощенной модели вертолета. По количеству состояний синтезируемых конечных автоматов разработанный алгоритм не уступает аналогам, при этом время синтеза в 9 раз меньше, чем у существующих алгоритмов.

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


Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

  1. Ляшов М.В., Берёза А.Н. «Аппаратная реализация нечетких контроллеров на ПЛИС». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТТИ ЮФУ, 2008, №4(81). – 199-204 с.
  2. Ляшов М.В., Берёза А.Н. «Аппаратная реализация нелинейных математических функций для нейронных сетей». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТТИ ЮФУ, 2008, №9(86). – 194-198 с.
  3. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Аналитический обзор реконфигурируемых гибридных  эволюционных аппаратных систем». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТТИ ЮФУ, 2009, №12(89). – 185-189 с.
  4. Ляшов М.В., Берёза А.Н. «Эволюционный синтез конечных автоматов». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». – Таганрог: Изд-во ТТИ ЮФУ, 2011. - №7. – 201-217 с.

Свидетельства о государственной регистрации программ для ЭВМ

  1. Ляшов М.В., Берёза А.Н. «Библиотека элементов генетических алгоритмов (LEGA)». Свидетельство № 2009611956, 2009 г.
  2. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Бионический алгоритм решения систем линейных алгебраических уравнений». Свидетельство № 2009616993, 2010 г.
  3. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Алгоритм расчета оптимального шага аппроксимации активационной функции нейрона». Свидетельство № 2010611341, 2010 г.
  4. Ляшов М.В., Берёза А.Н., Бегляров В.В., Стороженко А.С. «Библиотека оптимизационных алгоритмов для подсистемы схемотехнического проектирования ЭВТ». Свидетельство № 2011613831, 2011 г.
  5. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Библиотека алгоритмов вычислительной математики для подсистемы схемотехнического моделирования ЭВТ». Свидетельство № 2011614136, 2011 г.
  6. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Инструментальная среда проектирования  и исследования генетических алгоритмов «GABuilder»». Свидетельство № 2011614981, 2011 г.

Публикации в других изданиях

  1. Ляшов М.В. «Разработка ядра AVR-микроконтроллера для ПЛИС на AHDL (IPCore)». Информационные технологии в науке и образовании. Материалы конференции. Международная науч.-практ. интернет-конференция, июнь-октябрь 2005 г., г.Шахты / ред. кол.: А.Э.Попов [и др.]. - Шахты: Изд-во ЮРГУЭС, 2005. – 82 с., стр. 72-73.
  2. Ляшов М.В., Берёза А.Н. «Разработка сумматора с плавающей точкой на базе интегральных схем с перестраиваемой структурой». Проблемы экономики, науки и образования в сервисе: Сб. науч. трудов / Под ред. П.Д. Кравченко. – Шахты. Изд-во ЮРГУЭС, 2005.  285 с., стр. 151-153.
  3. Ляшов М.В., Берёза А.Н., Семенищев Е.А. «Аппаратная реализация умножителя с плавающей запятой на ПЛИС». Проблемы экономики, науки и образования в сервисе: Сб. науч. трудов / Под ред. П.Д. Кравченко. – Шахты. Изд-во ЮРГУЭС, 2005. – 285 с., стр.153-155.
  4. Ляшов М.В., Берёза А.Н. «Разработка и применение СФБ в системах на кристалле на базе ПЛИС (SoC)». Информационные технологии в науке и образовании. Материалы конференции. Международная науч.-практ. интернет-конференция, апрель-июнь 2006 г., г.Шахты / ред. кол.: А.Э.Попов [и др.]. - Шахты: Изд-во ЮРГУЭС, 2006. – 70 с., стр. 51-52.
  5. Ляшов М.В., Берёза А.Н. «Сложный функциональный блок AVR-микроконтроллера для проектирования систем на базе ПЛИС». Информационные технологии в науке и образовании. Материалы конференции. Международная науч.-практ. интернет-конференция, апрель-июнь 2006 г., г.Шахты / ред. кол.: А.Э.Попов [и др.]. - Шахты: Изд-во ЮРГУЭС, 2006. – 70 с., стр. 52-56.
  6. Ляшов М.В., Берёза А.Н. «Построение аппаратного ускорителя для систем автоматизированного проектирования». Информационные системы и технологии. Теория и практика: cб. науч. тр. / под ред. А.Н. Берёза. – Шахты: Изд-во ЮРГУЭС, 2008. – 189 с., стр. 55-63.
  7. Ляшов М.В., Берёза А.Н. «Нечёткий контроллер с генетической подстройкой». Информационные технологии, системный анализ и управление: VI всероссийская научная конференция молодых ученых, аспирантов и студентов, сб. тр. – Таганрог: Изд-во ТТИ ЮФУ, 2008 – 206 с., стр. 154-156.
  8. Ляшов М.В., Берёза А.Н. «Генетический нечеткий контроллер». Информационные системы и технологии. Теория и практика : cб. науч. тр. / редкол. : А.Н. Береза [и др.]. – Шахты : ГОУ ВПО «ЮРГУЭС»,  2009. – 209 с., стр. 45-53.
  9. Ляшов М.В., Берёза А.Н. «Аппаратный модуль генетического алгоритма для встраиваемых систем». Информационные технологии в науке и образовании: материалы международной научно-практической интернет-конференции и IV Всероссийского семинара «Применение MOODLE в сетевом обучении», 6-9 апреля 2010 г. (Железноводск). – Шахты: ГОУ ВПО «ЮРГУЭС», 2010. – 221 с., стр. 146-148.
  10. Ляшов М.В., Берёза А.Н., Кузнецов П.С. «Анализ способов построения конечных автоматов – основы аппаратных биоинформационных систем». Информационные технологии в науке и образовании: материалы международной научно-практической интернет-конференции и IV Всероссийского семинара «Применение MOODLE в сетевом обучении», 6-9 апреля 2010 г. (Железноводск). – Шахты: ГОУ ВПО «ЮРГУЭС», 2010. – 221 с., стр. 159-166.
  11. Ляшов М.В., Берёза А.Н. «Реконфигурируемый нейросетевой ускоритель на ПЛИС». Современные проблемы радиоэлектроники: Сборник научных трудов. Издательство РТИСТ ГОУ ВПО «ЮРГУЭС», 2010. – 420 с., стр. 367-375.
  12. Ляшов М.В. «Генетический алгоритм кодирования состояний конечного автомата». Информационные системы и технологии. Теория и практика : cб. науч. тр. / редкол. : А.Н. Береза [и др.]. – Шахты : ФГБОУ ВПО «ЮРГУЭС»,  2011. – 209 с., стр. 68-75.

Личный вклад автора в работах, опубликованных в соавторстве: [1– 4] – обзор и анализ существующих методов и архитектур, а также разработка алгоритмов, [5, 10] – разработка эволюционных алгоритмов и генетических операторов, [12–21] – разработка архитектур, программная и аппаратная реализация предлагаемых алгоритмов.

Соискатель               М.В. Ляшов

Подписано в печать 02.03.2012г. Формат 60х84/16

Бумага офсетная. Ризография. Усл.п.л. 1,0.

Тираж 100 экз. Зак.45.

Отпечатано в типографии: ИП Бурыхина Б.М.

Адрес типографии: 346500, Ростовская обл., г.Шахты, ул. Шевченко, 143.







© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

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