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

ои^4"

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

БЕЛОКРЫЛОВ ПЕТР ЮРЬЕВИЧ

СИНТЕЗ ЦИФРОВЫХ АВТОМАТОВ В НЕЙРОСЕТЕВОМ БАЗИСЕ

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации па соискание ученой степени кандидата технических наук

Н. Новгород 2009

П Л Л • •_ 0 / ■ „_

003481109

Работа выполнена на кафедре «Информатики и автоматизации научных исследований» Государственного образовательного учреждения высшего профессионального образования «Нижегородский государственный университет им. Н.И. Лобачевского»

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

Басалин Павел Дмитриевич

Официальные оппоненты доктор технических наук, доцент,

Бажанов Юрий Сергеевич

кандидат физико-математических наук,

доцент,

Гришагин Владимир Александрович

Ведущая организация ФГУП ФНПЦ «НИИИС

им. Ю.Е. Седакова»

Защита состоится «_» _ 2009 г. в _ часов на заседании

Диссертационного Совета Д 212.166.13 при Нижегородском государственном университете им. Н.И. Лобачевского по адресу: 603950, Н.Новгород, пр. Гагарина, д. 23.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного университета им. Н.И. Лобачевского.

Автореферат разослан «_»_2009 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук,

Савельев Владимир Петрович

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

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

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

Синтез произвольных цифровых автоматов с памятью традиционно разделяется на несколько основных этапов: блочного синтеза, абстрактного синтеза и структурного синтеза, завершающегося синтезом схем комбинационной логики. В рамках логико-математической теории релейно-контактных схем теория комбинационного синтеза развивалась в трудах Д. Хафмена, Г. Мили, В.И. Шестакова, М. Уилкса и др. Теория абстрактного и надежностного синтеза автоматов получила свое развитие в работах, опубликованных в сборнике статей «Автоматы» под редакцией К. Шеннона и Дж. Маккарти. Существенный вклад в развитие теории автоматов внес Дж. Фон Нейман. В работах Глушкова В.М. теория цифровых автоматов была доведена до уровня, который обеспечивал ей возможность непосредственного применения к решению реальных задач. В связи с этим следует отметить работы Закревского А.Д., представляющие системный подход к созданию совокупности средств автоматизации всех этапов проектирования цифровых устройств, объединенных в программной системе ЛЯПАС.

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

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

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

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

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

Цель работы

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

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

Научная новизна

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

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

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

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

Теоретическая и практическая ценность работы

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

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

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

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

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

Получаемые проектные решения могут быть оперативно реализованы в среде СБИС ПЛ (CPLD, FPGA, FLEX).

Апробация результатов

Результаты диссертационной работы докладывались и обсуждались на Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2007 (Н.Новгород, 2007г.), конференции «Технологии Microsoft в теории и практике программирования» (Н.Новгород, 2007г.), конференции учебно-научного инновационного комплекса «Модели, методы и программные средства (Н.Новгород, 2007г.), на XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2007г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

Структура и объем работы

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

Краткое содержание работы

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

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

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

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

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

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

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

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

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

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

Согласно выводам главы 1, цифровые автоматы, как объект исследования, представляют интерес в двух аспектах: как составляющие средств технического обеспечения информационных систем различного назначения (САПР, АСУ, АСНИ, АОС и т.д.), как объект проектирования в САПР микроэлектронных устройств цифровой аппаратуры.

Постоянное расширение сферы применения цифровой аппаратуры и отсутствие при этом возможности эффективного использования наработанных

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

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

В главе 2 «Традиционные методы синтеза цифровых автоматов» проводится критический анализ существующих методов синтеза цифровых автоматов.

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

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

• исходное множество регулярных событий, представленных своими регулярными выражениями;

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

• детальная блок-схема алгоритма функционирования автомата;

• описание исходного автомата-прототипа.

Методы и алгоритмы абстрактной теории цифровых автоматов позволяют решать проблемы мшшмизации числа их внутренних состояний. Однако на практике они часто остаются невостребованными. Достаточно обратить внимание на отсутствие средств описания абстрактных автоматов в признанных международных стандартах языков проектирования цифровой аппаратуры УНОЬ, Уеп1о§.

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

Исключение составляет канонический метод структурного синтеза. Он подразделяет все элементарные автоматы на два класса. К первому относятся автоматы с памятью (последовательностные схемы), имеющие более одного внутреннего состояния. Из этих элементов (запоминающих элементов) путем простого их объединения строится запоминающая часть (память) синтезируемого автомата, фиксирующая в себе последовательно все его текущие структурные

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

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

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

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

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

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

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

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

Решение канонической задачи минимизации булевых функций осуществляется в два этапа: на первом этапе по исходной СДНФ (СКНФ) находится сокращенная ДНФ (КНФ) булевой функции; на втором этапе по ней строятся приведенные (тупиковые) ДНФ (КНФ), среди которых выбираются минимальные.

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

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

В главе 3 «Ненросетевой подход к проблеме синтеза схем комбинационной логики» рассматривается концепция искусственной нейронной сети (ИНС), анализируются особенности различных архитектур ИНС, отличающихся характером входных сигналов (бинарные или аналоговые), структурой сети и типом обучения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• определение класса нейронной сети. Для аппроксимации заданного отображения достаточно использовать многослойные сети прямого распространения;

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

• определение обучающего множества шаблонов. Данные для составления этого множества получаются в результате наблюдения поведения моделируемой системы в формате «вход - выход».

• выбор исходной топологии (структуры) сети. Данный этап призван определить конкретные параметры структуры сети (число слоев, количество нейронов в них, структуру межнейронных соединений), достаточные для решения поставленной задачи.

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

Можно определить две эвристические стратегии поиска минимальной топологии.

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

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

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

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

Синтез комбинационной схемы в малом логическом базисе (SLC - Simple Logic Cells) предоставляет широкие возможности для поиска наиболее рациональных решений. Однако, как было уже отмечено, традиционные методы минимизации булевых функций не позволяют напрямую использовать произвольный малый логический базис для синтеза схем, т.к. они оперируют в классе ДНФ (КНФ) булевых функций. Эти методы также не предусматривают

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

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

Синтезируемая комбинационная схема представляется в виде искусственной нейронной сети (ИНС) из класса многослойных персвптронов, имеющая всевозможные межнейронные связи, не нарушающие его свойство прямонаправленности. Число входов персептрона равно числу аргументов х = (хих2,...,х„) реализуемых логических функций, а число выходов — числу реализуемых функций у =( ух,у2,-,ум )■

В соответствии со спецификой рассматриваемой задачи, составными элементами нейронной сети являются спецпроцессоры двух видов:

— искусственные нейроны, преобразующие поступающие на их входы сигналы в единственный выходной сигнал в соответствии с заданной активационной функцией нейрона;

— связи между нейронами, реализующие межнейронные взаимодействия в виде бинарных (принимающих значения 0 или 1) или биполярных (принимающих значения 1 или -1) сигналов, умножаемых на синаптические веса связей.

Виды активационных функций и значения синаптических весов определяется выбором 8ЬС. Так, в случае (И, ИЛИ, НЕ} базиса, активационные функции нейрона представляются следующими выражениями:

Xj — сигнал на выходе j-го нейрона, воздействующего на i-тый нейрон (xj = yj), je{ 1.....N,}cN-,

Ni — общее количество нейронов, непосредственно воздействующих на / -й нейрон;

w,0 = JVf -1 — порог активационной функции i -го нейрона, реализующего логическую функцию И;

w,0=l-N; — порог активационной функции i-ro нейрона, реализующего логическую функцию ИЛИ.

Значения синаптических весов и^ б {-1,0,1}. Значение wjt=-1 реализует логическую функцию НЕ, wj: = 0 определяет отсутствие данной связи между нейронами, wJ: = 1 определяет обычную ретрансляционную связь.

Сигналы, распространяющиеся в данной сети, принимают значения из [-1,1}. В случае использования {И-HEj, {ИЛИ-НЕ} базисов активационные функции нейрона представляются следующими выражениями:

(1)

где у, — сигнал на выходе /-го нейрона;

si=YjWJiXJ~WiO'

(3)

где у. — сигнал на выходе / -го нейрона;

■г.- = X ~ Чо;

1

х1 — сигнал на выходе ] -го нейрона, воздействующего на / -тый нейрон (х] = у1), уе{1.....Ы^сЫ-,

Л', — общее количество нейронов, непосредственно воздействующих на ¡-й нейрон;

— порог активационной функции 1-го нейрона, реализующего логическую функцию И-НЕ;

— порог активационной функции ¡-го нейрона, реализующего логическую функцию ИЛИ-НЕ.

Значения синаптнческих весов »^е/0,17, определяет отсутствие

данной связи между нейронами, =1 определяет обычную ретрансляционную

Сигналы, распространяющиеся в данной сети, принимают значения из {0,1},

которых играет исходная таблица истинности, т. е. функциональная таблица

автомата (X4 = (Х?,Х%.....Хчы) — </-й вектор известных значений аргументов

реализуемых функций, У''= (У,'',К2''.....У*) — вектор соответствующих значений

функций, 0 — мощность обучающего множества, т.е. число строк таблицы истинности равное 2Ы для полностью определенных функций).

В процессе обучения, вектора Х',д = 1,0, из множества Р последовательно подаются на вход персептрона, и для каждого из них оценивается разность между фактическим у' и желаемым У'1 откликом (выходом) сети —

1 II - || 2 --О

е =—15' ># = 1.)2- Затем, определяется общая ошибка е = — целевая

® 2" 11 п~\

функция процесса оптимизации топологии сети, на основании которой алгоритм обучения осуществляет модификацию значений настроечных параметров сети, направленную на уменьшение ошибки. Обучение продолжается до тех пор, пока сеть не приобретет способность выполнять требуемый тип преобразования, заданный набором шаблонов Р, то есть <? = 0. Т.о. решением данной задачи будет набор значений варьируемых параметров (синаптических весов межнейронных связей и типов активационных функций нейронов), обеспечивающий минимальное (нулевое) значение функции е.

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

связь.

Определяется множество обучающих шаблонов

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

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

найти значения параметров 2 = (г,, гг.....г„), обеспечивающие

тте(2), (4)

гео" 4 '

где 2 —вектор варьируемых переменных, компонентами г,,/ = 1,я, которого являются синаптические веса, определяющие типы межнейронных связей сети, и переменные, задающие виды активационных функций ее нейронов;

О" — дискретное п -мерное пространство варьируемых переменных;

с(2) — функция ошибки отклика на выходе нейронной сети.

Задача (4) относится к классу задач дискретной оптимизации. Варьируемые переменные в ней носят структурный характер представления объекта оптимизации. Из природы исходной задачи синтеза схем произвольной комбинационной логики следует, что задача (4) имеет не единственное решение 2', обращающее в 0 значение функции критерия (е(2') = 0). При этом зависимость минимизируемой функции от переменных носит существенно нелинейных характер.

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

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

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

Предложенная структура хромосомного набора предполагает возможность применения оригинальных схем генетических операторов репродукции и отбора 16

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

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

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

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

Различные алгоритмы, реализующие меггод «отжига», отличаются следующими параметрами:

• выбором закона изменения температуры Т(к), где к —г номер итерации алгоритма;

• выбором функции генерации нового состояния;

• выбором функции вероятности принятия нового состояния.

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

В частности, для рассматриваемой задачи применялся закон уменьшения текущей температуры Ттг=Т0/к, заимствованный из модификации Коши для метода «отжига». Как вариант, использовалась также зависимость Tcufr ~ccTmr, где а < 1 — заданная константа.

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

В главе 5 «Примеры синтеза некоторых схем комбинационной логики» показывается практическое применение методики представления задач в нейросетевом базисе для синтеза некоторых схем комбинационной логики.

В качестве одного из примеров, иллюстрирующих возможности нейросетевого подхода к синтезу комбинационных схем, рассматривается синтез схемы одноразрядного комбинационного сумматора Таблица истинности для данной схемы содержит восемь строк, определяющих зависимость двух функций (функции переноса в соседний старший разряд и функции разрядной суммы) от трех переменных (двух двоичных сигналов складываемых чисел и сигнала переноса из соседнего младшего разряда). В качестве исходной нейронной сети для синтеза схемы выбран четырехслойный персептрон структуры NN-3-4-3-3-2. Сеть имеет три входа для аргументов реализуемых логических функций (хихг — входы складываемых чисел, х} — вход переноса из соседнего младшего разряда) и два выхода: у, — выход переноса в соседний старший разряд; уг — выход разрядной суммы. Общая структура сети представлена на рис. 1.

Вщ^ аетивационных функций нейронов, множество значений синаптических весов связей и сигналов, распространяющихся в сети, определяется выбором логического базиса /Я, ИЛИ, НЕ}.

В качестве метода обучения сети был использован эволюционно-генетический алгоритм. Для представления эволюционно-генетической модели нейронной сети применена схема непосредственного кодирования, специфицирующая генными кодами каждую синаптическую связь исходно избыточной нейронной сети (О означает разрыв связи, 1 — наличие непосредственной связи, 2 — связь через инвертор) и вид активационной функции каждого нейрона (2 отмечает нейрон Я, 1 — нейрон ИЛИ, 0 — отсутствие нейрона). Пример генетического кода особи эволюционирующей популяции представлен на рис. 2 в виде хромосомы с двумя

составляющими Ь и N. где Ь — составляющая, кодирующая межнейронные связи, N — составляющая, кодирующая типы активационных функций нейронов.

Рис. 1, Общая структура сети для синтеза схемы одноразрядного комбинационного сумматора.

|о|о|о|1|ТГТГТО1 - ПЕЛ

ь

N

Рис. 2. Структура хромосомы, кодирующей нейронную сеть.

Таким образом, Ь-составляющая ставит в соответствие каждому нейрону участки хромосомы, определяющие его связи со всеми нейронами в других слоях. Г^-составляющая фиксирует типы активационных функций для каждого нейрона скрытых слоев и выходного слоя в порядке возрастания их номеров в сети сверху вниз и слева направо. Учитывая все возможные связи, в том числе и несмежные (через один или несколько слоев), Ь-составляющая хромосомы содержит 89 генов. М-составляющая включает 12 генов. Общее число генов в хромосоме В = 101.

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

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

Схема скрещивания представляла собой панмиксию генотипов, а система селекции —- ранговую с детерминированным выбором. Репродукционное множество составляли мутанты и потомки.

Размер начальной популяции выбирался согласно двум критериям: обеспечения покрытия области экстремума целевой функции и допустимого времени работы алгоритма. Экспериментально установленный для данного примера размер популяции составил величину 250 особей.

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

Рис. 3. Нейросетевое представление классического одноразрядного сумматора.

На рис. 3 двойными окружностями помечены нейроны, моделирующие логические элементы Я, одинарными — элементы ИЛИ, черными кругами — «мертвые» нейроны, у которых отсутствуют все входные или выходные связи. Сплошными линиями отмечены непосредственные связи между нейронами, пунктирными — инверсные связи, точечными линиями •— отсутствующие связи.

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

Рис. 4. Нейросетевое представление другого варианта одноразрядного комбинационного сумматора.

Нейросетевое решение задачи синтеза схемы одноразрядного комбинационного сумматора в базисе {И-НЕ} представлено на рис. 5.

Для описания эволюционно-генетической модели нейронной сети использована схема непосредственного кодирования, специфицирующая генными кодами каждую синаптическую связь исходной избыточной нейронной сети (О означает разрыв связи, 1 — наличие непосредственной связи) и вид активационной функции каждого нейрона (1 — нейрон И-НЕ, 0 — отсутствие нейрона).

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

рис. 4. В первую очередь это является следствием выбора базиса {И-НЕ}, содержащего минимальное количество базисных функций.

Рис. 5. Нейросетевое решение задачи синтеза схемы одноразрядного сумма тора в базисе И-НЕ.

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

Синтез схемы осуществлялся в базиса {И-НЕ} на основе исходной структуры персептрона NN-9-12-12-12-12-4. В результате применения регрессивной стратегии поиска минимальной топологии сети, описанной в методике представления задач в нейросетевом базисе, было получено окончательное решение на основе персептрона NN-9-9-9-8-8-4. Данное решение содержит не уменьшаемое количество нейронов, и дальнейшая оптимизация структуры может быть получена только за счет сокращения общего числа связей.

Для обучения был применен модифицированный алгоритм, реализующий метод «тушения» с использованием закона изменения температуры Tcurr =Tslan/k. Время получения решения составило порядка 100 минут для однопроцессорной архитектуры на базе Intel Pentium 4. Нейронные сети представлены на рис.6 и рис.7.

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

Рис. 6. Нейросетевое представление схемы четырехразрядного параллельного переноса в базисе {И-НЕ} на основе персептрона структуры NN-9-12-12-12-12-4. Сеть содержит два неактивных нейрона (отмечены черными кругами).

Рис. 6. Нейросетевое представление схемы четырехразрядного параллельного переноса в базисе ¡И-НЕ) на основе персептрона структуры NN-9-9-9-8-8-4. Сеть содержит один неактивный нейрон (отмечен черным кругом).

Глава ^«Программная реализация» посвящена обсуждению и описанию различных подходов к реализации нейросетевых эмуляторов для традиционных вычислительных систем. Отмечается, что для сетей небольшой размерности (менее 100 нейронов) применение таких технологий параллельного программирования как ОрепМР и MPI не представляется целесообразным. Это связано с накладными расходами процессорных операций при создании и синхронизации независимых вычислительных потоков. Выходом из создавшегося положения может быть подход, основывающийся на использовании особенностей архитектур современных процессоров в части организации их вычислительного тракта (многоконвеерность, оптимизация выполнения команд на микроархитектурпом уровне, использование специального набора команд для параллельной обработки данных, различные средства поддержки мультипроцессорного режима). Современные средства разработки и используемые ими компиляторы языков высокого уровня позволяют повысить производительность выполнения алгоритмических конструкций посредством генерации оптимального (для конкретной архитектуры процессора) исполняемого кода. Это достигается как средствами настройки компилятора, так и средствами самого алгоритмического языка. В рамках данного подхода для реализации программных комплексов синтеза схем произвольной комбинационной логики в нейросетевом базисе, использующих эволюционно-генетический алгоритм и алгоритм имитации отжига для обучения нейронной сети, используется платформа разработки .NET Framework и язык программирования С#.

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

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

Основные результаты:

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

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

• показана возможность представления комбинационной логической схемы эквивалентной (бинарной или биполярной) нейронной сетью прямого распространения (с сохранением физического и математического смысла всех параметров);

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

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

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

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

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

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

Публикации

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

1. Басапин, П.Д. Структурный синтез цифровых автоматов в нейросетевом базисе / П.Д. Басалин, П.Ю. Белокрылов И Научно-технический журнал «Системы управления и информационные технологии». — Воронеж, — 2007. — №3(29). — С.44-48

2. Басалин, П.Д. Синтез схем произвольной комбинационной логики в нейросетевом базисе с применением метода имитации отжига / П.Д. Басалин, П.Ю. Белокрылов, Д.С. Згурский // Вестник Нижегородского Университета им. Н.И. Лобачевского.

— 2008. — №5. — С. 126-130

Публикации в прочих изданиях:

3. Басалин, П.Д. Синтез комбинационных логических схем в нейросетевом базисе / П.Д. Басалин, П.Ю. Белокрылов // Вестник ВГАВТ. — 2006. Выпуск 2.

4. Басалин, П.Д. Синтез схем произвольной комбинационной логики в нейросетевом базисе. / П.Д. Басалин, П.Ю. Белокрылов // Тезисы для конференции «ИСТ 2007».

— 2007.

5. Басалин, П.Д. Методика синтеза линейных комбинационных схем в нейросетевом базисе. / П.Д. Басалин, П.Ю. Белокрылов // Тезисы для конференции «Технологии Microsoft в теории и практике программирования». — 2007 г.

6. Белокрылов, П.Ю. Синтез быстродействующих схем комбинационной логики в нейросетевом базисе / П.Ю. Белокрылов // Сборник трудов НГТУ / НГТУ — 2007.

7. Белокрылов, П.Ю. Нейросетевой синтез быстродействующих линейных комбинационных схем. / П.Ю. Белокрылов // Тезисы для конференции учебно-научного инновационного комплекса «Модели, методы и программные средства»,

— 2007.

8. Белокрылов, П.Ю. Нейросетевой метод синтеза схем комбинационной логики. / П.Ю. Белокрылов // Тезисы для XV Международной конференции «Проблемы теоретической кибернетики». — Казань, — 2007.

Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Гарнитура Times. Усл. печ. л. 1. Тираж 100 экз. Заказ 595.

Типография Нижегородского госуниверситета им. Н.И. Лобачевского Лицензия ПД№ 18-0099 от 04.05.2001 г. 603600, Н. Новгород, ул. Б. Покровская, 37.

ВВЕДЕНИЕ.

Актуальность темы исследований.

Цель работы.

Научная новизна.

Теоретическая и практическая ценность работы.

Апробация результатов.

1. РОЛЬ ЦИФРОВЫХ АВТОМАТОВ В ОРГАНИЗАЦИИ СОВРЕМЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.1. Базовые принципы организации современных вычислительных систем и тенденции их развития.

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

1.3. Гибридные вычислительные системы.

1.4. Выводы.

2. ТРАДИЦИОННЫЕ МЕТОДЫ СИНТЕЗА ЦИФРОВЫХ АВТОМАТОВ.

2.1. Синтез цифрового автомата на абстрактном уровне описания.

2.2. Структурный синтез цифрового автомата.

2.3. Проблемы синтеза схем комбинационной логики.

2.4. Выводы.

3. НЕЙРОСЕТЕВОЙ ПОДХОД К ПРОБЛЕМЕ СИНТЕЗА СХЕМ КОМБИНАЦИОННОЙ ЛОГИКИ.!.

3.1. Концепция искусственной нейронной сети.

3.2. Представление задач в нейросетевом базисе.

3.3. Задача синтеза логических комбинационных схем в нейросетевом базисе.

3.4. Выводы.

4. АЛГОРИТМЫ И МЕТОДЫ ОБУЧЕНИЯ НЕЙРОННЫХ СЕТЕЙ.

4.1. Эволюционно-генетические алгоритмы.

4.2. Метод «отжига», базирующийся на статистическом подходе.

4.3. Выводы.

5. ПРИМЕРЫ СИНТЕЗА НЕКОТОРЫХ СХЕМ КОМБИНАЦИОННОЙ ЛОГИКИ.

5.1. Синтез одноразрядного комбинационного сумматора.

5.2. Синтез схемы ускоренного переноса.

5.3. Выводы.

6. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.

6.1. Объектно-ориентированное представление нейронной сети.

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

6.3. Программный комплекс синтеза схем произвольной комбинационной логики в нейросетевом базисе на основе метода «отжига».

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

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

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

Синтез произвольных цифровых автоматов с памятью традиционно разделяется на несколько основных этапов: блочного синтеза, абстрактного синтеза и структурного синтеза, завершающегося синтезом схем комбинационной логики. В рамках логико-математической теории релейно-контактных схем теория комбинационного синтеза развивалась в трудах Д. Хафмена [1], Г. Мили [2], В. И. Шестакова[], М. Уилкса [4] и др. Теория абстрактного и надежностного синтеза автоматов получила свое развитие в работах, опубликованных в сборнике статей «Автоматы» под редакцией К. Шеннона и Дж. Маккарти [5]. Существенный вклад в развитие теории автоматов внес Дж. Фон Нейман [6]. В работе [7] теория цифровых автоматов была доведена до уровня, который обеспечивал ей возможность непосредственного применения к решению реальных задач. В связи с этим следует отметить работу [8], представляющую системный подход к созданию совокупности средств автоматизации всех этапов проектирования цифровых устройств, объединенных в программной системе ЛЯПАС.

Нейросетевому подходу к задачам моделирования объектов и систем уделялось внимание в ряде работ, посвященных тематике искусственных нейронных сетей. Возможность аналитического моделирования объектов с помощью нейронных сетей обоснована в [9, 10]. В [10] также обсуждаются нейросетевые методы построения моделей сложных систем на основе экспериментальных данных. Рассмотрены постановки типовых задач информационного моделирования (прямых, обратных и смешанных). В работах [10, 11] рассматриваются вопросы некорректно поставленных задач моделирования объектов, для которых предлагается нейросетевая информационная технология построения гибридной нейроархитектуры, содержащей кластеризующую карту Кохонена и семейство сетей с обратным распространением, обучаемых на данных индивидуальных кластеров. Построение моделей нечеткого управления с помощью нейронных сетей рассматривается в [12]. Задача построения конечно-автоматной модели информационно-телеметрической системы с применением нейросетевого представления транспортной задачи решается в [13].

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

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

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

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

Цель работы

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

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

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

Научная новизна

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

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

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

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

Теоретическая и практическая ценность работы

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

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

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

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

Получаемые проектные решения могут быть оперативно реализованы в среде СБИС ПЛ (CPLD, FPGA, FLEX).

Апробация результатов

Результаты диссертационной работы докладывались и обсуждались на Всероссийской научно-технической конференции «Информационные системы и технологии» ИСТ-2007 (Н.Новгород, 2007г.), конференции «Технологии Microsoft в теории и практике программирования» (Н.Новгород, 2007г.), конференции учебно-научного инновационного комплекса «Модели, методы и программные средства (Н.Новгород, 2007г.), на XV Международной конференции «Проблемы теоретической кибернетики» (Казань, 2007г.), на семинарах кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ.

ЗАКЛЮЧЕНИЕ

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

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

• показана возможность представления комбинационной логической схемы эквивалентной (бинарной или биполярной) нейронной сетью прямого распространения (с сохранением физического и математического смысла всех параметров);

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

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

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

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

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

1. Huffman D. A. The synthesis of sequential switching circuits, Journal of the Franklin 1.st., v. 257, № 3 and 4, 1954, pp. 161-190, 275-303.

2. Mealy G. H. A method for synthesizing sequential cirquits. Bell system Tech. J., v. 34, 1955, pp. 1045-1079.

3. Шестаков В. И. Алгебраический метод синтеза автономных систем двухпозиционных реле. Автоматика и телемеханика, т. 15, № 4, 1954, с. 310-324.

4. Wilkes М. V. Microprogramming, Proc. East. Joint. Comput. Conf. NT-114, New York, 1959, pp. 18-20.

5. Шеннон К., Маккарти Дж. Автоматы, М: ИЛ, 1956.6. фон Нейман Дж. Теория самовоспроизводящихся автоматов. М: Мир, 1971.

6. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962, 476 с.

7. Закревский А.Д., Потгосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств. М.: Физматлит, 2007, 592 с.

8. Галушкин А.И., Судариков В.А., Шабанов Е.В. Нейроматематика: методы решения задач на нейрокомпьютерах. Математическое моделирование, 1991, т. 3, №8, с. 93-111.

9. Горбань А.Н., Дунин-Барковский В.Л., Кирдин А.Н. и др. Нейроинформатика. Новосибирск: Наука. Сибирское предприятие РАН, 1998, 296 с.

10. Осовский С. Нейронные сети для обработки информации. М.: Финансы и статистика, 2004, 344 с.

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

12. Назаров А.В., Лоскутов А.И. Нейросетевые алгоритмы прогнозирования и оптимизации систем. СПб.: Наука и Техника, 2003, 384 с.

13. Червяков Н.И., Сахнюк П.А., Шапошников А.В., Ряднов С. А. Модулярные параллельные вычислительные структуры нейропроцессорных систем М.: ФИЗМАТЛИТ, 2003, 288 с.

14. Таненбаум Э. Архитектура компьютера. 4-е изд. СПб.: Питер, 2003, с.584585.

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

16. Бажанов Ю.С., Баранов В.Г. Базовые микрооперации интеллектуальных систем проектирования цифровых автоматов. // Межвузовский сборник научных трудов «Системы обработки информации и управления» / НГТУ, 1997, Выпуск 2.

17. Угрюмов Е.П. Цифровая схемотехника. СПб.: БХВ-Петербург, 2001, 528 с.

18. Мс. Cluskey Minimizations of boolean functions, Bell, System Techn. J., v. 35, №6, 1956, pp. 1417-1444.

19. A. Blake, Canonical expression in Boolean Algebra. Dissertation, Chicago, 1937.

20. R. J. Nelson, Simplest normal truth functions. J. Sumb. Logic, v. 20, № 2, 1955, pp. 105-108.

21. S. R. Petrick, A direct decomposition of the irredundant forms of a boolean function from the set of prime-implicants. Tech. reports Air Force Cambridge Research Center, 1956, pp. 56-110.

22. E. W. Veitch, A chart method for simplifying truth functions. Proc. Ass. Сотр. Mach., 1952, May, №2, 3, p. 127-133.

23. M. Karnaugh, The map method for synthesis of combinational logic circuits, Trans. AIEE, v. 72, № 1, 1953, p. 593-599.

24. Кругл OB B.B., Борисов В.В. Искусственные нейронные сети. Теория и практика. 2-е изд. М.: Горячая линия Телеком, 2002, 382 с.

25. Сергеев Я.Д., Стронгин Р.Г., Гришагин В.А. Введение в параллельную глобальную оптимизацию. Учебное пособие. Нижний Новгород: Изд-во Нижегородского университета, 1998, 87 с.

26. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев А.С. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Х.ЮСНОВА, 1997, 112 с.

27. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных. Докл. АН СССР, 1956. Т. 108, №2, с. 179-182.

28. Колмогоров А.Н. О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного. Докл. АН СССР, 1957. Т. 114, № 5, с. 953-956.

29. Арнольд В.И. О функциях трех переменных. Докл. АН СССР, 1957. Т. 114, No. 4, с. 679-681.

30. Cybenko G. Approximation by superposition of a sigmoidal function. Mathematics of Control, Signals, and Systems, 1989, vol. 2, pp. 303 314.

31. Hornik K., Stinchcombe M., White H. Multilayer feedforward networks are universal approximators. Neural Networks. 1989, vol. 2, pp. 359 366.

32. Kochenov D.A., Rossiev D.A. Approximations of functions of CA,B. class by neural-net predictors (architectures and results). AMSE Transaction, Scientific Siberian, A. 1993, Vol. 6, Neurocomputing, pp. 189-203. Tassin, France.

33. Батищев Д.И., Костюков B.E., Старостин H.B., Смирнов А.И. Популяционно-генетический подход к решению задач покрытия множества: Учебное пособие. — Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2004. — 152 с.

34. Уилкинсон Барри. Основы проектирования цифровых схем. — М.: Издательский дом «Вильяме», 320 с.

35. Вороновский Г.К, Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. — X.: ОСНОВА, 1997. — 112 с.

36. Haykin S. Neural networks, a comprehensive foundation. N.Y.: Macmillan College Publishing Company, 1994.

37. Hornik K., Stinchcombe M., White H. Multilayer feedforward networks are universal approximators //Neural Networks, 1989, vol. 2, pp. 359-366.

38. Geva S., Sitte J. Progress in supervised neural networks // IEEE Trans. N. N., 1992, vol. 3, pp. 621-625.

39. Osowski S. Sieci neuronowe. Warszawa: Oficyna Wydawnicza PW, 1994.

40. Hecht-Nielsen R. Neurocomputing. Amsterdam: Addison Wesley, 1991.

41. Osowski S. Sieci neuronowe w ujeciu algorytmicznym. Warszawa: WNT, 1996.

42. Fukushima K., Wake N. Handwritten alphanumeric character recognition by the neocognitron// IEEE Trans. N.N., 1991, vol. 2, pp. 355-365.

43. Schaffer J.D., Whitley L., Eshelman J. Combinations of Genetic Algorithms and Neural Networks, COGANN-92, 1992.

44. Whitley D. Applying genetic algorithms to neural network learning, Proceedings of the Seventh Conference of the Society of Artificial Intelligence and Simulation of Behavior, Sussex, England, Pitman Publishing, 1989, pp. 137-144.

45. Evolver — the Genetic Algorithm Problem Solver, Axcelis, Inc., 4668 Eastern Avenue N., Seattle, WA 98103, USA. 248.

46. Whitley D., Starkweather Т., Bogart C. Genetic algorithms and neural networks: Optimizing connections and connectivity, Parallel Computing, 1990, nr 14, pp. 347-361.

47. Harp S.A., Samad Т., Guha A. Towards the genetic synthesis of neural networks, in: Proceedings of the Third International Conference on Genetic Algorithms and Their Applications; Schaffer J.D. (ed.), Morgan Kauffmann, San Mateo, CA, 1989, pp. 360-369.

48. Guo Z., Uhrig R. E. Use of genetic algorithms to select inputs for neural networks, in: Proceedings of International Workshop on Combinations of Genetic Algorithms and Neural Networks, COGANN-92, 1992, pp.223-234.

49. Schaffer J.D., Caruana R.A., Eshelma'n L.J. Using genetic search to exploit the emergent behavior of neural networks, in: Forrest S. (ed.) Emergent Computation, Amsterdam: North Holland, 1990, pp. 244-248.

50. Kitano H., Designing neural networks using genetic algorithms with graph generation system, Complex Systems, 1990, nr 4, pp 461-476.

51. Mexrill J.W.L., Port R.F. Fractally configured neural networks, Neural Networks, 1991, t. 4 pp. 53-60.

52. Yao X. A review of evolutionary artificial neural networks, International Journal of Intelligent Systems, 1993, pp. 539-567.

53. Brindle M. Genetic algorithms for Function Optimization, Ph. D.dissertation, University of Alberta, 1981.

54. Goldberg D. E. Algorytmy genetyczne I ich zastosowania, WNT, Warszawa, 1995.

55. FlexTool (GA) M2.1, Flexible Intelligence Group, L.L.C, Tuscaloosa, AL 35486-1477, USA.

56. Басалин, П.Д. Синтез комбинационных логических схем в нейросетевом базисе / П.Д. Басалин, П.Ю. Белокрылов // Вестник ВГАВТ. — 2006. Выпуск 2

57. Басалин, П.Д. Структурный синтез цифровых автоматов в нейросетевом базисе / П.Д. Басалин, П.Ю. Белокрылов // Научно-технический журнал «Системы управления и информационные технологии». — Воронеж, — 2007. — №3(29). -— С.44-48

58. Лоскутов А.Ю., Михайлов А.С. Введение в синергетику. — М.: Наука. Гл. ред. физ.-мат. лит., 1990.

59. Новые физические принципы оптической обработки информации: Сборник статей / Под ред. С.А. Ахманова и М. А. Воронцова. — М.: Наука. Гл. ред. физ.-мат. лит., 1990.

60. Уссермен Ф. Нейрокомпьютерная техника. — М.: Мир, 1992.

61. Muller В., Reinhardt J. Neural networks. Springer-Verlag. 1990.

62. Kirpatrick S., Gelatt C. D., Vecchi M.P. Optimization by simulated annealing. // Science, 1983, vol. 220, pp. 671-680.

63. Johnson D., Aragon C., Schevon C. Optimization by simulated annealing: an experimental evaluation. Part I: graph partitioning // Operations Research, 1989, vol. 37, pp. 865-892.

64. Ingber L. and Rosen B. Genetic algorithms and very fast simulated reannealing: A comparison, Mathl. Comput. Modelling 16, 11, 1992, pp. 87-100.

65. Джонс M.T. Программирование искусственного интеллекта в приложениях. Пер. с англ. Осипов А.И. — М.: ДМК Пресс, 2006. 312 с.

66. Белокрылов, П.Ю. Синтез быстродействующих схем комбинационной логики в нейросетевом базисе / П.Ю. Белокрылов // Сборник трудов НГТУ / НГТУ — 2007.

67. OpenMP API. Version 3.0 May 2008.

68. MPI: A Message-Passing Interface Standard Version 2.1 Message Passing Interface Forum June 23, 2008.

69. Гришагин B.A., Свистунов А.Н. Параллельное программирование на основе MPI. Учебное пособие Нижний Новгород: Изд-во ННГУ им.Н.И. Лобачевского, 2005. - 93 с.

70. CLR via С#. Программирование на платформе Microsoft .NET Framework 2.0 на языке С#. Мастер-класс. / Пер. с англ. — М. : Издательство «Русская Редакция» ; СПб. : Питер , 2007. — 656 стр.

71. Professional С#. Simon Robinson, Ollie Cornes, Jay Glynn, Burton Harvey, Craig McQuenn, Jerod Moemeka, Christian Nagel, Morgan Skinner, Karli Watson. 2001, Wrow Press.

72. Нейгел Кристиан, Ивьен Билл, Глин Джей, Скиннер Морган, Уотсон Карли. С# 2005 и платформа .NET 3.0 для профессионалов.: Пер. с англ. — М.: ООО «И.Д. Вильяме», 2008. — 1376 с.