Разработка и исследование алгоритмов синтеза конечных автоматов для автономных эволюционных аппаратных средств тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Ляшов, Максим Васильевич

• Ляшов, Максим Васильевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Ляшов, Максим Васильевич

ВВЕДЕНИЕ

1 Исследование способов создания автономных систем на основе эволюционных аппаратных средств

1.1 Эволюционные аппаратные средства

1.2 Классификация эволюционных аппаратных средств

1.3 Анализ алгоритмов синтеза конечных автоматов

1.3.1 Минимизация и кодирование внутренних состояний ^ конечных автоматов

1.3.2 Двухуровневый и многоуровневый синтез

1.4 Постановка задачи диссертационной работы

1.5 Выводы

2 Особенности проектирования эволюционных аппаратных средств с ^ использованием современных САПР

2.1 Этапы проектирования эволюционных аппаратных средств на ^ ПЛИС

2.2 Использование встроенных средств ПЛИС для отладки ^ эволюционных аппаратных средств

2.3 Принципы оперативного изменения поведения системы

2.4 Маршрут проектирования эволюционных аппаратных средств на ^ ПЛИС

2.5 Выводы

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

3.1 Построение реконфигурируемых конечных автоматов на ПЛИС

3.1.1 Разработка реконфигурируемой структуры на ПЛИС

3.1.2 Применение блоков памяти ПЛИС для реализации комбинационных схем

3.2 Генетический алгоритм кодирования состояний конечного ^ автомата и его теоретическая оценка

3.3 Аппаратно-ориентированный генетический алгоритм синтеза ^ конечных автоматов и его теоретическая оценка

3.4 Разработка устройства аппаратной реализации генетического алгоритма

3.4.1 Технические характеристики устройства аппаратной реализации генетического алгоритма

3.5. Выводы

4 Экспериментальные исследования разработанных алгоритмов

4.1 Разработка инструментальной среды

4.2 Определение управляющих параметров разработанных генетических алгоритмов

4.3 Определение временной сложности разработанных генетических алгоритмов

4.4 Сравнение результатов генетического алгоритма кодирования состояний конечного автомата

4.5 Сравнение результатов генетического алгоритма синтеза конечных автоматов

4.5.1 Задача об «Умном муравье»

4.5.2 Задача построения автопилота для упрощенной модели ^ ^ вертолета

4.6 Выводы 139 Заключение

Введение диссертации (часть автореферата) на тему «Разработка и исследование алгоритмов синтеза конечных автоматов для автономных эволюционных аппаратных средств»

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

В САПР для проектирования цифровых и аналоговых устройств в настоящее время применяются эволюционные алгоритмы (ЭА) [10,11]. Это направление получило название «эволюционная электроника» (Evolutionary Electronics) [25]. Применение ЭА на аппаратных платформах, имеющих реконфигурируемые элементы, позволяющие перестраивать систему во время функционирования, получило название эволюционные аппаратные средства [5-9, 20-24]. Научные исследования в этом направлении ведутся как в России, так и за рубежом [5-15].

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

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

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

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

В работах [16-19] представлены эволюционные алгоритмы синтеза комбинационных логических схем для ЭАС. Применяемые в настоящее время методы синтеза конечных автоматов всегда используют специфику решаемой задачи, делая полученную технику генерации автоматов 6 неприменимой к остальным задачам [51]. Возникает вопрос создания универсальных методов синтеза конечных автоматов, применимых к широкому кругу задач. В работах [52-60] показано применение эволюционных алгоритмов для синтеза конечных автоматов. Однако, представленные алгоритмы применяются для автоматного программирования, в рамках которого программа описывается с помощью конечных детерминированных автоматов, что не позволяет их использовать в автономных аппаратных системах на реконфигурируемых платформах.

Поиск приемлемого по выбранным критериям конечного автомата прямым перебором практически невозможен из-за огромного размера пространства, в котором осуществляется поиск. Например, в такой простой задаче, как задача об «Умном муравье» [54], число возможных автоматов с

1Я семью состояниями около 3,2x10 . Применение генетических алгоритмов позволит сделать перебор случайно-направленным, что в свою очередь сократит время поиска.

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

ЦЕЛЬ ДИССЕРТАЦИОННОЙ РАБОТЫ состоит в разработке и исследовании генетических алгоритмов синтеза конечных автоматов для проектирования эволюционных аппаратных средств.

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

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).

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

1. Устройство аппаратной реализации генетического алгоритма для решения задачи автоматизированного синтеза конечных автоматов на ПЛИС, позволяющее использовать разработанные генетические алгоритмы в автономных эволюционных аппаратных системах. На устройство получено положительное решение о выдаче патента на изобретение [129].

2. Разработанный комплекс программ для решения задач автоматизированного синтеза конечных автоматов, который включает в себя аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов и генетический алгоритм кодирования состояний конечного автомата (охранные документы на объекты интеллектуальной собственности приведены в Приложении Б).

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетных научно-исследовательских работах Южно-Российского государственного университета экономики и сервиса:

• «Разработка теории и принципов автоматизации проектирования на схемотехническом уровне устройств вычислительной техники с применением бионических методов» (№ г.р. 01.2.00 606 713, 2006 г.). Автором в качестве исполнителя были разработаны модифицированные генетические операторы для задачи автоматизации проектирования устройств вычислительной техники на схемотехническом и логическом уровнях.

• Гранты аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» 2009-2011 г: о «Разработка и исследование реконфигурируемых гибридных эволюционных аппаратных систем» № 2.1.2/6959 (ЮРГУЭС

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

Результаты диссертационной работы используются в учебных процессах в ФГБОУ ВПО ЮРГУЭС (г. Шахты) на кафедре

Информационные системы и радиотехника» в дисциплинах

Интеллектуальные информационные системы», «Архитектура ЭВМ и систем», «Цифровые устройства и микропроцессоры», ВИС ФГБОУ ВПО

ЮРГУЭС (г. Волгодонск) на кафедре «Информационные технологии» в дисциплинах «Архитектура ЭВМ и систем», «Схемотехника ЭВМ», ю

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

АПРОБАЦИЯ РАБОТЫ. Основные научные и практические результаты работы докладывались, обсуждались и были одобрены на Международных научно-технических конференциях «Интеллектуальные САПР» (г. Геленджик, 2008-2011 гг.), международной научно-практической конференции «Научный потенциал молодёжи - будущее России», Всероссийской научной конференции молодых ученых и аспирантов (г. Волгодонск, 2009 г.), конгрессе по интеллектуальным системам и информационным технологиям «А18-1Т'09». По материалам диссертационной работы опубликовано 16 печатных работ, в том числе 4 статьи в изданиях, входящих в «Перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации», утверждённых ВАК. СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Ляшов, Максим Васильевич

4.6 Выводы

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

• для генетического алгоритма синтеза конечных автоматов

- размер популяции равный 1200;

- двухточечный кроссинговер с вероятностью Рс - 0,40;

- вероятность мутации Рм = 0.25.

• для генетического алгоритма кодирования состояний конечного автомата

- размер популяции равный 100;

- вероятность мутации Рм = 0.15.

2. Проведены экспериментальные исследования разработанных алгоритмов синтеза и кодирования состояний конечных автоматов, в результате которых была получена полиномиальная зависимость (0(Ы)) времени решения задачи от числа состояний автомата, которая подтвердила теоретические оценки.

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

4. Выполнено сравнение разработанного генетического алгоритма кодирования состояний конечного автомата с аналогом и классическими алгоритмами Ж)УА1, ]\ЮУА2 на промышленных тестовых задачах

139

МС1ЧС. Полученные результаты в среднем на 20% лучше, чем у существующих алгоритмов.

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

ЗАКЛЮЧЕНИЕ

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

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

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

4. Разработаны аппаратно-ориентированный генетический алгоритм синтеза конечных автоматов и генетический алгоритм кодирования состояний конечного автомата, предназначенные для синтеза КА в автономных эволюционных аппаратных средствах. Найдены теоретические оценки временной сложности разработанных алгоритмов -О (Я2).

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

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

7. Выполнено сравнение разработанных генетических алгоритмов. Генетический алгоритм кодирования состояний конечного автомата сравнивался с аналогом и классическими алгоритмами КЮУА1, Ж)УА2 на промышленных тестовых задачах МСЫС. Полученные результаты в среднем на 20% лучше, чем у существующих алгоритмов. Сравнение разработанного генетического алгоритма синтеза конечных автоматов проводилось на тестовых задачах об «Умном муравье» и построении автопилота для упрощенной модели вертолета. По количеству состояний синтезируемых конечных автоматов разработанный алгоритм не уступает аналогам, при этом время синтеза в 9 раз меньше, чем у существующих алгоритмов.

Список литературы диссертационного исследования кандидат технических наук Ляшов, Максим Васильевич, 2012 год

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

2. Казённов Г. Г. Основы проектирования интегральных схем и систем. — М.: БИНОМ. Лаборатория знаний, 2005.

3. Европейская патентная классификация Электронный ресурс. -http://ep.espacenet.com/

4. Российская патентная классификация Электронный ресурс. -http ://www. flps.ru/

5. Nedjah N. Evolvable Machines: Theory and Practice. Studies in Fuzziness and Soft Computing, Volume 161. 2004.

6. Garrison W. Introduction to Evolvable Hardware: A Practical Guide for Designing Self-Adaptive Systems. IEEE Press Series on Computational Intelligence. 2006.

7. Higuchi Т., Liu Y., Yao X. Evolvable Hardware. IEEE Press Series on Computational Intelligence. 2006.

8. Gordon, T. On Evolvable Hardware. Soft Computing in Industrial Electronics. Physica-Verlag, Heidelberg, Germany, pp. 279-323, 2002.

9. Gordon T. G., Bentley P. Towards Development in Evolvable Hardware. NASA/DOD Conference on Evolvable Hardware, 2002. pp. 241-250.

10. Курейчик В. M. Генетические алгоритмы и их применение: монография. Таганрог : ТРТУ, 2002.

11. П.Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: Физматлит, 2006.

12. Курейчик В.М., Емельянова Т.С. Алгоритмы эволюционного синтеза комбинационных схем: Монография. Таганрог: Изд-во ТТИ ЮФУ, 2011.- 150 с.

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

14. Haupt R.L., Haupt S.E. Practical Genetic Algorithms. John Wiley & Sons, Inc. NJ: 2004

15. Лебедев Б.К. Методы поисковой адаптации на основе механизмов генетики, самообучения и самоорганизации. Программные продукты и системы, 2002, №1, с. 16-20.

16. Гудилов В.В. Разработка и исследование алгоритмов эволюционного синтеза комбинационных схем. Диссертация на соискание ученой степени кандидата технических наук, Таганрог 2007.

17. Гудилов В.В, Курейчик В.М. Устройство аппаратной реализации вероятностных генетических алгоритмов. Методы и средства обработки информации. Труды Второй Всероссийской научной конференции. МГУ им. М.В. Ломоносова. Москва 2005. Стр. 596-601.

18. Гудилов В. В., Зинченко Л. А., Курейчик В. В., Курейчик В. М. Устройство аппаратной реализации вероятностных генетических алгоритмов. Патент 2294561 Российская Федерация № 2005108760; 28.03.2005.

19. Черун С. В. Синтез комбинационных логических схем на основе эволюционного подхода: дис. канд. тех. наук. Таганрог, 2005.

20. Hollingworth G. S., Smith S. L., Tyrrell A. M. The Intrinsic Evolution of Virtex Devices Through Internet Rcconfigurable Logic. Third International Conference on Evolvable Systems. Vol. 1801, 2000, pp. 72-79.

21. Vassilev V. K., Miller J. F. Scalability Problems of Digital Circuit Evolution. Second NASA/DOD Workshop on Evolvable Hardware, 2000, pp. 55-64.

22. Alba E., Tomassini M., Parallelism and evolutionary algorithms. IEEE Transactions on Evolutionary Computation, vol. 6, pp. 443-462, 2002.

23. Zebulum R.S., Pacheco M.A., VellascoM.M. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms. USA, CRC Press LTC, 2002.

24. Takashi I., Barry S. J., Etsuko O., Mitsuhiro Y. Fitness function circuit. Patent number: US6185547. Application number: US 19970909830.

25. Mark A., Kikuo H. Genetic design method and apparatus. Patent number: US2004049472. Application number: US20030649936.

26. Takashi I., Barry S. J., Etsuko O., Mitsuhiro Y. Fitness function circuit. Patent number: US6185547. Application number: US 19970909830.

27. Takashi I., Barry S. J., Etsuko O., Mitsuhiro Y. Genetic algorithm machine and its production method, and method for executing a genetic algorithm. Patent number: US5970487. Application Number: US19970910103.

28. Родзин С. И. Гибридные интеллектуальные системы на основе алгоритмов эволюционного программирования. Новости искусственного интеллекта. 2000. -№3. - С. 159-170.

29. Stephen D.S. GA: A Hardware-Based Genetic Algorithm. Dept. of Computer Science Washington University St. Louis, MO 63130-4899,7 p. 2001.

30. Chatchawit A. C. Hardware Implementation of the Compact Genetic Algorithm. In Proceedings of the 2001 IEEE Congress on Evolutionary Computation Seoul, Korea, May 27-30, 2001, pp.624-629.

31. John C.G. A Family of Compact Genetic Algorithms for Intrinsic Evolvable Hardware. IEEE Transactions on Evolutionary Computation, vol. 8, No. 2, April, 2004.

32. Blondet В., James-Roxby P. A Self-reconfiguring Platform Field-Programmable Logic and Applications. 13 International Conference. FPL 2003 Proceedings, pp. 565-574.

33. Zebulum R.S., Pacheco M.A., Vellasco M.M. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms. USA, CRC Press LLC, 2002.

34. Torresen J. Scalable evolvable hardware applied to road image recognition. In Proc. of the 2nd NASA/DoD Workshop on Evolvable Hardware. Silicon1. Valley, USA, July 2000.

35. Sripramong Т., Toumazou C. The Invention of CMOS Amplifiers Using Genetic Programming and Current-Flow Analysis. IEEE Trans. CAD. 2002.

36. Левин И. И. Методы и программно-аппаратные средства параллельных структурно-процедурных вычислений. Дисс. на соискание ученой степени докт. техн. Наук. Таганрог, 2004.

37. Официальный сайт компании Altera Электронный ресурс. -http://altera.com

38. Официальный сайт компании Xilinx Электронный ресурс. -http://xilinx.com

39. Ермошкин А.Г. Низкоуровневое моделирование систем, проектируемых с использованием ПЛИС. Дисс. на соискание ученой степени кинд. техн. наук. Москва, 2003.

40. Стешенко В.Б. Плис фирмы ALTERA: проектирование устройств обработки сигналов. М.: До дека. 2000.

41. Wolf W. FPGA-Based System Design. Prentice Hall Ptr. 2004.

42. Lee S. Advanced Digital Logic Design Using VHDL, State Machines, and Synthesis for FPGA's. Thomson-Engineering. 2005.

43. Соловьев В.В. Логическое проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая1. Линия Телеком, 2008.

44. Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов,языков и вычислений. М.: Вильяме, 2001.

45. Лобанов П.Г. Использование генетических алгоритмов для генерации конечных автоматов: дис. канд. тех. наук. Санкт-Петербург, 2008.

46. Шалыто А. А. Технология автоматного программирования. Труды первой Всероссийской конференции "Методы и средства обработки информации". МГУ. 2003, с. 150-152.

47. Шалыто A.A. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления. Известия РАН. Теория и системы управления. 2000. № 6, с. 63-81.

48. Шалыто A.A. Алгоритмизация и программирование для систем логического управления и «реактивных» систем. Автоматика и телемеханика. 2001.

49. Шопырин Д.Г., Шалыто A.A. Объектно-ориентированный подход к автоматному программированию. Информационно-управляющие системы, 2003

50. Рассел С., Норвиг П. Искусственный интеллект: современный подход.1. М.: Вильяме, 2006.

51. Казаков М. А., Шалыто А. А., Туккель Н. И. Использование автоматного подхода для реализации вычислительных алгоритмов . Труды международной научно-методической конференции «Телематика-2001». СПб.: СПбГИТМО (ТУ), 2001.

52. Туккель Н. И., Шалыто А. А., Шамгунов Н. Н. Реализация рекурсивных алгоритмов на основе автоматного подхода . Телекоммуникации и информатизация образования. 2002. № 5.

53. Шалыто A.A. Туккель Н.И. От тьюрингова программирования кавтоматному. Мир ПК. 2002. № 2.

54. Шидловский С.В. Автоматическое управление. Перестраиваемыеструктуры. Томск, 2006.

55. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. СПб.:1. Питер, 2009.

56. Вельдер С.Э., Лукин М.А., Шалыто А.А., Яминов Б.Р. Верификация автоматных программ. СПб: Наука, 2011.6 8. Кафедра «Технологии программирования» СПбГУ ИТМО Электронный ресурс. http://is.ifmo.ru.

57. Adamczyk P. The Anthology of the Finite State Machine Design Patterns. The 10th Conference on Pattern Languages of Programs, 2003.

58. Adamczyk P. Selected Patterns for Implementing Finite State Machines. The 11th Conference on Pattern Languages of Programs, 2004.

59. Ashlock D. Evolutionary Computation for Modeling and Optimization. New1. York: Springer, 2006.

60. Ferreira C. Discovery of the Boolean Functions to the Best Density Classification Rules Using Gene Expression Programming . Lecture Notes in Computer Science. 2002. Vol. 2278, pp. 51-60.

61. Fogel D. The Evolution of Intelligent Decision Making in Gaming .

62. Cybernetics and Systems. 2001. 22, pp. 223-236.

63. Frey C., Leugering G. Evolving Strategies for Global Optimization. A Finite State Machine Approach. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Morgan Kaufmann. 2001, pp. 27-33.

64. Horihan J., Yung-Hsiang Lu. Improving FSM evolution with progressive fitness functions. In GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI. NY: ACM Press. 2004. pp. 123-126.

65. Linton R. Adapting binary fitness functions in genetic algorithms. Proceedings of the 42nd annual Southeast regional conference. NY: ACM Press. 2004. pp. 391-395.

66. Tu M., Wolff E., Lamersdorf W. Genetic Algorithms for Automated Negotiations: A FSM-based Application Approach /Proceedings of the 11-th International Conference on Database and Expert Systems. 2000.

67. Wolff K., Nordin P. An Evolutionary Based Approach for Control Programming of Humanoids. Proceedings of the 3rd International Conference on Humanoid Robots (Humanoids'03). Karlsruhe: VDI/VDE-GMA. 2003.

68. Ashlock D., Wittrock A., Wen T-J. Training finite state machines to improve PCR primer design. Congress on Evolutionary Computation (CEC'02). 2002, pp. 13-18.

69. Belz A. Computational Learning of Finite-State Models for Natural Language Processing. PhD thesis. University of Sussex. 2000.

70. Gustafson S. An Analysis of Diversity in Genetic Programming. Ph.D. Dissertation. School of Computer Science and Information Technology. University of Nottingham. Nottingham. U.K., 2004.

71. Bryant K. Genetic Algorithms and the Traveling Salesman Problem. Harvey Mudd College: Department of Mathematics, 2000.

72. Ferreira C. Gene Expression Programming: A New Adaptive Algorithm for Solving Problems. Complex Systems. 2001. Vol. 13, issue 2, pp. 87-129.

73. Huang D. MS Thesis Preproposal: Adaptive Incremental Fitness Evaluationin Genetic Algorithms. 2005. NY: Rochester.

74. Lucas S. M. Evolving Finite State Transducers: Some Initial Explorations. Genetic Programming: 6th European Conference (EuroGP'03). Berlin: Springer. 2003, pp. 130-141.

75. Petrovic P. Comparing Finite-State Automata Representation with GP-trees. Technical report. Norwegian University of Science and Technology. 2006.

76. Petrovic P. Evolving automatons for distributed behavior arbitration. Technical Report. Norwegian University of Science and Technology. 2005.

77. Petrovic P. Simulated evolution of distributed FSA behaviour-based arbitration / The Eighth Scandinavian Conference on Artificial Intelligence (SCAI'03). 2003.

78. Spears W. M., Gordon D. F. Evolving Finite-State Machine Strategies for Protecting Resources. International Syposium on Methodologies for1.telligent Systems. 2000.

79. Teller A., Veloso M. Internal Reinforcement in a Connectionist Genetic

80. Programming Approach. Artificial Intelligence. 2000.

81. Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о флибах // Известия РАН. Теория и системы управления. 2007. № 5, с. 127-136.

82. Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для решения задачи об умном муравье / XIV Всероссийская научно-методическая конференция «Телематика-2007». СПб. 2007. Т.2, с. 426, 427.

83. Frey С., Leugering G. Evolving Strategies for Global Optimization A Finite State Machine Approach. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Morgan Kaufmann. 2001, pp. 27-33.

84. Tu M., Wolff E., Lamersdorf W. Genetic Algorithms for Automated Negotiations: A FSM-based Application Approach. Proceedings of the 11-th International Conference on Database and Expert Systems. 2000.

85. Naidoo A., Pillay N. The Induction of Finite Transducers Using Genetic Programming. Proceedings of Euro GP. Springer. 2007.

86. Nedjah N., Mourelle L. Mealy Finite State Machines: An Evolutionary Approach // International Journal of Innovative Computing, Information and Control. 2006. V.2, № 4, pp. 58-67.

87. Ginsburg S. On the Reduction of Superfluous States in a Sequential Machine. J.A.C.M. 6 (1959), 1, 252-282.

88. Глушков B.M. Синтез цифровых автоматов. М.: ФИЗМАТ ЛИТ, 467 е., 1962 г.

89. Hachtel G.D. Exact and heuristic algorithms for the minimization of incompletely specified state machines. EEE Trans, on CAD of Integrated Circuits and Systems, Vol. 13, Nr. 2 (1994) , p. 167-177.

90. Kohavi Z. Reduction of the Number of States in Incompletely Specified Sequential Machines. Electron. Letters (1965), 7, 712-715.

91. Luccio F. A Method for Minimizing the Number of Internal States in Incompletely Specified Sequential Networks. IEEE Trans. Electr. Comput.14 (1965), 3, 350-359.

92. Dolotta Т., McCluskey E. The coding problem in the design of switching circuiits. IEEE Trans. Electr. Comput. 14 (1964), 549-562

93. Armstrong, D.B. A Programmed Algorithm for Assigning Internal Codes to Sequential Machines. IRE Trans. Electron. Computers EC-11 (4), 466472. (1962).

94. Lee E.B., Perkowski M.A. Concurrent Minimization and State Assignment of Finite State Machines," Proc. of Intern. IEEE Conf. on Systems, Man, and Cybernetics, Halifax, Nova Scotia, pp. 248-260, 1986.

95. McCluskey E. J. Logic Design Principles. Prentice Hall. Englewood Cliffs, NJ, 1986.

96. De Micheli G. Optimal State Assignments for Finite State Machines, RC 10599, IBM T.J. Watson Research Center, Yorktown Heights, NY, 1984.

97. Villa Т., Sangiovanni-Vincentelli A.L. NOVA: state assignment of finite state machines for optimal two-level logic implementation. Presented at IEEE Trans, on CAD of Integrated Circuits and Systems, 2001.

98. Devadas S., Newton, A.R.: Decomposition and factorization of sequential finite state machines. IEEE Trans, on CAD of Integrated Circuits and Systems(1989) .

99. Devadas S. Optimizing Interacting Finite State Machines. IEEE Trans, on CAD of Integrated Circuits and Systems, 2001, pp.905-924.

100. NIE Xin, LI Yuan-xiang, KE Peng. Research on the Architecture of Intrinsic Evolvable Digital Circuits, JNIT: Journal of Next Generation Information Technology, Vol. 2, No. 2, pp. 8 ~ 14, 2011

101. Ляшов M.B., Берёза A.H. «Аппаратная реализация нечетких контроллеров на ПЛИС». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2008, №4(81). - 268 с.

102. Ляшов М.В., Берёза А.Н. «Аппаратная реализация нелинейных математических функций для нейронных сетей». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР».- Таганрог: Изд-во ТТИ ЮФУ, 2008, №9(86). 194-198 с.

103. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Аналитический обзор реконфигурируемых гибридных эволюционных аппаратных систем». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2009, №12(89).- 185-189 с.

104. Ляшов М.В., Берёза А.Н., Бегляров В.В. «Бионический алгоритм решения систем линейных алгебраических уравнений». Известия ВУЗов. ТТИ ЮФУ. Технические науки Таганрог: Изд-во ТТИ ЮФУ.- 2009. №12(89). - 165-169 с.

105. Ляшов М.В., Берёза А.Н. «Эволюционный синтез конечных автоматов». Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». Таганрог: Изд-во ТТИ ЮФУ, 2011. - №7. -201-217 с.

106. Ляшов М.В., Берёза А.Н., Семенищев Е.А. «Аппаратная реализация умножителя с плавающей запятой на ПЛИС». Проблемы экономики, науки и образования в сервисе: Сб. науч. трудов / Под ред. П.Д. Кравченко. Шахты. Изд-во ЮРГУЭС, 2005. 285 с. 153-155 с.

107. Ляшов М.В., Берёза А.Н. «Построение аппаратного ускорителя для систем автоматизированного проектирования». Информационные системы и технологии. Теория и практика: сб. науч. тр. / под ред. А.Н. Берёза. Шахты: Изд-во ЮРГУЭС, 2008. - 189 с.

108. Ляшов М.В., Берёза А.Н. «Генетический нечеткий контроллер». Информационные системы и технологии. Теория и практика : сб. науч. тр. / редкол. : А.Н. Береза и др.. Шахты : ГОУ ВПО «ЮРГУЭС»,2009. 209 е., стр. 45-53

109. Ляшов М.В., Берёза А.Н. «Реконфигурируемый нейросетевой ускоритель на ПЛИС». Современные проблемы радиоэлектроники: Сборник научных трудов. Издательство РТИСТ ГОУ ВПО «ЮРГУЭС»,2010.-420 е., стр. 367-375.

110. Ляшов М.В., Берёза А.Н. Устройство аппаратной реализации эволюционного алгоритма. Решение о выдаче патента на изобретение, заявка №2010151042/08(073741) от 13.12.2010.

111. Yang S. Logic synthesis and optimization benchmark user guide version 3.0, MCNC 1991.

112. Гусак A.A. Высшая математика. M.: ТетраСистемс, 2009.

113. Выгодский М.Я. Справочник по высшей математике. М.: ACT, 2008.

114. Кнут Д. Искусство программирования. М.: Вильяме, 2000.

115. Скиена С. Алгоритмы. Руководство к разработке. 2-е. изд.: Пер. с англ. - СПб.: БХВ-Петербург, 2011. - 720 е.: ил.

116. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильяме, 2000.

117. Джонсон Р., Влассидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. СПб.: Питер, 2001.

118. Троелсен Э. С# и платформа .NET 3.0 СПб.: Питер, 2008.

119. Скит Д. С#: программирование для профессионалов, 2-е издание. М.: Вильяме, 2011.

120. Мартин Р. Принципы, паттерны и методики гибкой разработки на языке С#. М.: Символ-Плюс, 2011.