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

• ³ j i = 0 i i i i где A/fa, Len- координаты / -го вектора во входной модели, E_A/fa^J . , E_Len^j . - координаты / -го вектора ву-ой эталонной модели.

Таким образом, данный подход можно использовать в различных системах «off-//ne» распознавания рукописных символов. Можно отметить, что он обладает рядом преимуществ, таких как пригодность метода для распознавания произвольно написанных символов (вне зависимости от почерка и стиля написания, масштаба и ориентации символов) и требование небольших вычислительных ресурсов. В результате практической апробации метода была разработана экспериментальная программа, позволяющая осуществлять распознавание ру кописных символов в режиме «off-//ne» распознавания. Программа позволяет распознавать изображение рукописных символов как в режиме обучения на конкретный почерк человека, так и независимо от стиля написания и почерка. В результате тестирования была сгенерирована база данных эталонных векторных моделей, состоящая из 10-15 моделей на каждый символ алфавита. Точность распознавания составила 80 % при произвольном стиле написания. Для распознавания были взяты эталонные векторные модели длиной 20 векторов. В случае подстройки системы на конкретный стиль написания и почерк база данных эталонных векторных моделей стала содержать по 20-30 моделей на каждый символ алфавита, при этом точность распознавания составила в среднем 95 %.

Библиографический список

• 1.    Сойфер, В. А. Компьютерная обработка изображений / В.А. Сойфер // Соросовский образовательный журнал. 1996. №3.

• 2.    Vinciarelli, S. Bengio, and Н. Bunke. Offline recognition of unconstrained handwritten texts using НММ and statistical language models. IDIAP-RR 3-22, Dalle Molle Institute for Perceptual Artificial Intelligence 2003.

• 3.    Peter Nacken. Image Analysis Methods Based on Hierarchies of Graphs and Multi-Scale Mathematical Morphology. PhD-thesis, University of Amsterdam, 1994.

A. N. Goroshkin

USE OF THE VECTOR APPROACH TO RECOGNITION OF HAND-WRITTEN SIMBOLS

Quest/ons of def/n/t/on of /nvar/ant allr/bules of hand-wr/tten symbols and ways of the/r a//ocat/on are cons/dered. The a/gor/thm ofconstruction of vector mode/, ways of /ts norma//zat/on and condensation are g/ven The method of the recogn/t/on based on comparison of rece/ved vector mode/ w/th reference vector mode/s of a different c/ass of hand-wr/tten symbols /s offered.

• E. С. Семенкин, С. H. Ефимов

МОДЕЛИ И АЛГОРИТМЫ АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ

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

В РЕЖИМЕ РЕАЛЬНОГО ВРЕМЕНИ1

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

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

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

ИАД РВ предъявляет чрезвычайно высокие требования к квалификации разработчиков и применяемым вычислительным средствам.

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

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

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

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

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

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

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

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

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

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

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

Результатами, полученными в данной области, являются:

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

• -    программная система автоматического формирования нечеткого логического контроллера [5], автоматически генерирующая базу правил с помощью нейрон

ных сетей и генетического алгоритма и настраивающая семантику лингвистических переменных с помощью алгоритма оптимизации;

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

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

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

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

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

• -    эвристический подход к автоматизированному определению макроопераций, являющихся подходящими процедурами для аппаратной реализации в виде специализированных процессоров [7].

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

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

• -    аналитические стохастические модели функционирования МВС управления в реальном времени с однородными и разнородными специализированными процессорами [8] для оценки их эффективной производительности;

• -    аналитические стохастические модели оценки надежности функционирования МВС обработки информации и управления в режиме реального времени с однородными и разнородными спецпроцессорами [9];

• -    имитационные модели оценки производительности и надежности МВС РВ [10];

• -    система поддержки принятия решений (СППР) при моделировании сложных систем с помощью методов теории стохастических процессов [11].

Имея в распоряжении модели оценки эффективности МВС РВ, можно переходить к формализации задачи выбора эффективных вариантов многопроцессорных систем и разработке на их основе систем принятия решений при таком выборе. Основные результаты этого направления содержатся в [12-14]. Выбор эффективных вариантов МВС формализуется в виде сложных задач оптимизации с многими критериями, алгоритмически заданными целевыми функциями и функциями-ограничениями и разнотипными переменными. Решение таких задач большой размерности требует разработки и применения специальных оптимизационных процедур, основанных на стохастических алгоритмах оптимизации эволюционного типа.

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

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

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

дач стационарной [17; 18] и нестационарной [17; 19] оптимизации;

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

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

Описанные подходы к разработке инструментария для интеллектуального анализа данных и поддержки принятия решений при управлении сложными системами в режиме реального времени (по отдельности и в различных сочетаниях) успешно применялись при выполнении конкретных прикладных разработок в области авиационной и космической техники [22; 23], управления технологическими процессами [24; 25] и в других технических областях [26], а также в областях психологии и медицины [27; 28] и управления инновационной и инвестиционной деятельностью [29; 30].

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