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

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

ОКУЛОВСКИЙ Юрий Сергеевич

ПРОГРАММНЫЙ КОМПЛЕКС ОБЕСПЕЧЕНИЯ ИНТЕЛЛЕКТУАЛЬНЫХ

ВЫЧИСЛЕНИЙ

05.13.18. - математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание ученой степени □□ЗДТ'ЭЗЗО кандидата физико-математических наук

Екатеринбург - 2009

003479230

Работа выполнена иа кафедре алгебры и дискретной математики ГОУ ВПО «Уральский государственный университет им. A.M. Горького»

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

ПОПОВ Владимир Юрьевич

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

БАЛАГАНСКИЙ Владимир Сергеевич

кандидат физико-математических наук ВОЛКАНИН Леонид Сергеевич

Ведущая организация: ГОУ ВПО «Уральский государственный технический

университет - УПИ им. первого президента России Б.Н. Ельцина»

Защита состоится гь октября 2009 года в 'Ь часов на заседании диссертационного совета Д 212.286.10 по защите докторских и кандидатских диссертаций при ГОУ ВПО «Уральский государственный университет им. A.M. Горького» по адресу: 620000, г. Екатеринбург, пр. Левина, 51, комн. 248

С диссертацией можно ознакомиться в Научпой библиотеке ГОУ ВПО «Уральский государственный университет им. A.M. Горького».

Автореферат разослан 1?> сентября 2009 года

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

диссертационного совета, доктор физ.-мат. наук, профессор

Пименов В.Г.

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

Актуальность темы. Под системами искусственного интеллекта обычно понимаются семейства различпых алгоритмов решепия задач, которые в процессе работы демонстрируют некоторое сходство с человеческой умственной деятельностью [19]. В частности, предполагается, что они способны делать выводы, являющиеся логическим следствием имеющихся зпапий; обучаться решению задачи по предъявленным примерам решения и в дальнейшем работать на осповании накопленного опыта; демонстрировать способность к адаптации и корректировать собствеппос поведение при измепепии условий; находить решепия задач, соответствующие указанным критериям правильного ответа без четко указанного алгоритма поиска решения. Системы искусственного иптеллскта широко используются в различпых областях. В частности, можно отметить такие области, как: поиск приближенных решений для трудпорешаемых задач и ИР-полпых задач [5], [15]; моделирование экспертной оценки (в медицине [20], предсказании погоды [4], и т.д); системное программное обеспечение (сжатие информации [23], распознавание вредоносного программного обеспечения [6]); робототехпика (распознавание изображений и техническое зрение, планирование и управление [25]); экономика [12]; энергетика [21].

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

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

В рамках пастоящей работы под интеллектуальными системами понимаются преимущественно нейронные сети [21], [24], генетические алгоритмы [1], [22] и алгоритмы кол-

лективного разума [3], [5]. На сегодшгашй день создано и постоянно создается большое количество программных реализаций систем искусственного интеллекта. Однако не существует известных систем, реализующих алгоритмы коллективного разума. Также не представлепы продукты, интегрирующие генетические алгоритмы и нейронные сети. Широко распространены пакеты, содержащие лишь реализацию нейронных сетей. Успешпые коммерческие реализации (см., например, [11], [13]) имеют закрытую архитектуру, и позволяют работать лишь со строго определенными типами нейронных сетей и алгоритмами нх обучения, существенно ограничивая возможности пользователя по разработке новых систем. Большинство распространенных программных комплексов поддержки генетических алгоритмов (см., например. [7], [9]) не допускают интеграцию с нейронными сетями из-за узкой специализации. Также следует отметить более низкий уровень реализаций генетических алгоритмов по сравнению с нейронными сетями, проявляющийся в детальности документации, поддержке, спектре функциональности и т.д. Некоторые системы искусственного интеллекта реализованы в составе круппых программных пакетов, таких, как МаШаЪ ([10],[18]). Такая реализация позволяет полнее интегрировать интеллектуальные вычисления со сложными математическими вычислениями, однако затрудняет оптимизацию интеллектуальных систем и их использование вне среды МаШаЬ.

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

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

1) теоретическое исследование моделей интеллектуальных систем для описания их вычислительных возможностей;

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

3) тестирование комплекса на стандартных задачах и путем решепия прикладных задач.

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

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

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

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

Апробация работы. Основные результаты работы докладывались на следующих конференциях: Международная алгебраическая конференция (Екатеринбург, 2005), 37-я региональная молодежпая конфенция в Купгуркс (Кунгурка, 2006), 9-я международная конференция «Интеллектуальные системы и компыотерпые науки» (Москва, 2006), Международная научная конференция «Информациоппо-математические технологии в экопомике, технике и образовании» (Екатеринбург, 2006), 38-я региональная молодежпая конфенция в Кунгурке (Кунгурка, 2007), Четвертая сибирская школа-семинар по параллельным и высокопроизводительным вычислениям (Томск, 2007), Международная научная конференция «Ипформационно-математичсские технологии в экопомике, технике и образовании» (Екатеринбург, 2007), IV Межвузовская научно-практическая конференция студентов, аспирантов и молодых ученых «Безопасность информационного пространства» (Тюмень, 2007), Научная сессия МИФИ-2008 (Москва, 2008), 39-й Всероссийская молодежная конференция в Кунгурке (Кунгурка, 2008), XXIII международная конференция «Уравнения состояния вещества» (Эльбрус, 2008), Третья международная научная конференция «Информационно-математические технологии в экономике, технике и образовании» (Екатеринбург, 2008), 40-я Всероссийская молодежная конфенция в Кунгурке (Кунгурка, 2009), VI Всероссийская межвузовская конференция молодых ученых (Санкт-Петербург, 2009).

Результаты работы докладывались и обсуждались па семинарах «Алгебраические системы», «Системы искусственного иптеллекта» и «Системном семипаре» УрГУ, семинаре по теории функций в Институте математики и механики УрО РАН. Устройства под управлением интеллектуальных систем, реализованных с помощью программного комплекса, демонстрировались на выставках: «Образовательная среда-2008» (г. Москва, сентябрь 2008); IV Уральская непчурная выставка-ярмарка «Инновации-2008» (г. Екатеринбург, поябрь, 2008); Отчетная выставка по Приоритетному Национальному Проекту Образование (г. Москва, декабрь 2008); «Планета Е<1иса1юп-2009» (г. Екатеринбург, февраль, 2009).

Публикации. Осповпые результаты диссертации изложены в [26]-[48]. Работы [26], [27], [35], [36], [39]—[42], [44], [48] написаны в неразрывном соавторстве с другими авторами. В работе [43] диссертантом проведена разработка п реализация интеллектуального алгоритма обработки данных и численные эксперименты. В работе [28] диссертантом выполнены формулировка и доказательство всех результатов, связанных с липейно-порожденпыми частичными порядками.

Работы [26]-¡28] опубликованы в изданиях, входивших в перечень ВАК на момент публикации.

Структура и объем работы. Работа состоит из 111 страниц машинописного текста, включающего введение, три главы и библиографический список из 41 наименования.

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

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

Исследуются функции / : 1, —• М, где Ь с Кт, и Ь не более чем счетно. Такая функция может быть представлена одним нейроном, если /(X) = д{А-Х+ао), где А - вектор весов, Оо € К, а д - функция активации нейрона, определяющая его тип. Рассматривались модели персептрона, т.е. нейрона с функцией активации д(х) = sign(x), а также п-порогового нейрона, для которого д является кусочно-постоянной функцией с п разрывами. Показано, что один п-пороговый пейрон способен представить любую функцию на конечном носителе

ь.

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

/(Хи ..., Хп-1,Хп) = (-«„ Л Д(жь... ,Х„_1)) V (хп Л /2(1Ь ..., а:„_1)),

то / является конкатенацией Д и /2, / = ¡\ * /2.

Теорема 1. Пусть Н{/) - множество всех векторов А, для которых существует ад такое, что

/(Х) = 818П(А-Х+Оо).

Тогда }\ * /2 линейно разделима, если и только если "Н{}\) П 'Я(/г) имеет внутреннюю точку.

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

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

Далее, выделен класс канонических ЛРФ, определяемых следующим образом. Введем попятие ранга 1-ого аргумента:

П = |{(х1,...,жп) : х< = 1Л/(х,,...,хп) = 1}|.

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

Сужение классов ЛРФ можно продолжить. На основании такого сужения построена частичпая классификация ЛРФ. Основной идеей является построение последовательности классов ЭТ^(п), где 0 < к < п. Любой представитель класса является конкатенацией представителей ОТ/^и—1), и, следовательно, алгоритм может быть распространен на любой класс. Вводятся специальные функционалы, которые позволяют перевести функцию из <Пк{п) В %+!(«).

Сформулируем полученные результаты строго. Введем некоторые необходимые определения. Рассмотрим м-мерный вектор X = (х\,..., х--,) и индексное множество М = {гиг,..., тк}, 1 < пт,- < п. Проекцией X на М назовем вектор Х\м = (хт,...,хтк). Дополнительным ипдексным множеством М называется такое множество, для которого М Ы М = {1,..., п}. Наконец, если \М\ = к, У е К*, Я 6 М(п - к), V е Ж", У\М~У, У|Д7 — 2, то У называется смешепием У и 2 по М и обозначается как X ом У.

Пусть Ек является ¿-мерным вектором вида (1, —1,..., -1), а Ок является ¿-мерным вектором вида (-1,1,..., 1). Назовем булеву функцию нерегулярной на М, если существуют >ь У2 такие, что ¡(Ек ом Уг) > /(Ок °м У!) и }(Ек °м >2) < }(Ок °м У?)- В противном случае / регулярна на М. Функция / является регулярной, если она регулярна на любом индексном множестве. Регулярная функция / является инвариантной на М, если для всех X выполняется }{ЕкомХ) = ¡{О^мХ). Наконец, регулярная и неинвариантная функция является верхней на М, если для некоторого X выполняется /(£* ом X) > ¡{Ок ои X), и нижней в противном случае. Регулярные функции и линейно-разделимые функции связывает следующая теорема:

Теорема 2. Всякая линейно-разделимая функция регулярна не любом индексном множестве М.

Обозначим через ОТ^ (га) множество всех липейно-разделимых функций, которые являются верхними либо инвариантными относительно всех М таких, что |М| < к. Справедливо, что 91о(га) - мпожество всех липейно-разделимых функций арности п, ЭТЦп) - множество всех монотонных ЛРФ, а ЭТ2(гг) - множество всех канонических ЛРФ. Для любого к возможна дальнейшая оптимизация алгоритма: если /1 * /2 € то /1, /2 6 1).

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

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

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

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

К,М]/(ХомУ) =

ДХомУ) , ХфЕк,ХфОк 1(Ек °м У) , Х = Ок 1(ОкомУ) , Х = Ек

К,м]/(Хому) = |

если / нижняя на М иначе

9*1(1) А 3*1(2) А 0*1(3) А 9*1(4) А

К 1С к

9Ы2) А 9*2(3) А Я, (4) А 1С 1С 9*з(3) А 9*з(4) А К

А-Х < A-Y. Множество всех векторов, порождающих порядок р, обозначим через Сопе(р). Простейшим примером линейно-порожденного порядка является линейпо-порождепный линейный порядок. Такие порядки могут быть паведепы па мпожестве одпим вектором Л, для которого А-Х ф А-У для всех X, Y eh. Множество линейно-порождеппых линейных порядков обозначается как £j.

На линейно-порождеппых порядках введены операции инфимума и супремума. Порядок г называется ипфимумом порядков р и а, если Соне(т) = Сопе(р)ПСопе(<т). Инфимум обозначается как рЛо. Минимальное множество, содержащее £i и замкнутое относительно Л, обозначим как £2. Супремумом двух порядков р и а будем называть порядок г = pVo-, образующее множество которого является наименьшим возможным объединением конусов из £2, содержащим Сопе(р) и Сопс(сг), которое при этом является замкпутым коническим множеством. Минимальное множество, содержащее £1 и замкнутое относительно V и Л обозпачим через £. Доказапо, что £ содержит все линейпо-порождевные порядки и только их, и что оно является конечной решеткой относительно операций супремума и иифимума. Исследованы некоторые свойства этой решетки. В частности, показано, что решетка ЛПП на любой проекции носителя L изоморфпо вложима в решетку ЛПП исходного множества. То же самое справедливо для решеток ЛПП подмножеств IL.

Указана связь между линейпо-порождепными порядками и функциями, вычислимыми с помощью одного гг-порогового нейрона. Порядок р будем называть fc-дольным, если существует разбяспие V = {Di,..,, D*} такое что для любых г < j и X £ Д, У е Dj выполняется XpY.

Теорема 3. Функция f : L —> {0,..., к} может быть вычислена к-пороговым нейроном тогда и только тогда, когда существует невырожденный, линейно-порожденный, (fc+1)-долъный порядок р такой, что доли р в точности равны /-1(0),..., f~l{k). Запись /~'(t) обозначает полный прообраз г.

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

'Полпая документация, исходный код и примеры доступны по адресу http://ai.mattu\mi.ra/wiki/doku.php/irap/gaiis

блочной архитектуры, которая позволяет осваивать комплекс постепенно. Для начального уровня достаточно лишь научиться составлять интеллектуальную систему из готовых блоков, а для более тонкой настройки возможно написание новых компонент в рамках имеющейся архитектуры. В научных исследованиях важна открытость архитектуры комплекса, позволяющая использовать новые алгоритмы вычислений совместно с имеющимися. Прикладное значение комплекса продиктовано из его реализации на современной платформе программирования .NET [16], [17], в виде библиотеки. Такая реализация допускает обширпые средства интеграции интеллектуальных вычислепий в приложения. Кроме того, выбранная платформа реализации позволяет запускать комплекс под разными операционными системами, и писать дополнительный код для комплекса на разных языках программирования.

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

Важным результатом является приложение компопентной модели к сборке нейропных сетей и алгоритмов их обучения. Нами также разработана декомпозиция пейронных сетей и обучающих алгоритмов на простые блоки, которая позволила представлять сложпыс сети и алгоритмы обучения, описаппые в литературе, в виде композиций простых. В результате, обеспечение многообразия алгоритмов обучения и архитектур сетей, которые можно наблюдать, например, в [21] и [24], на практике сводится лишь к сборке их из блоков. Основной сущностью для сборки пейронных сетей является компопепт нейронной сети. Компонент нейронной сети представляет собой некую подсеть с заданным количеством входов и выходов. Элементарным компонентом является слой пейронов одного типа, где все нейроны имеют одинаковое число входов. Компоненты могут связываться различными способами. Так, при последовательном соединении выход первого компонента передается следующему. При рекуррентном соединении выход компонента перенаправляется на его же вход. Такие композиции позволяют получить из элементарных слоев самые разные архитектуры нейронных сетей: многослойный персептрон, сеть прямого распространения сигпала, составленную из разных типов нейронов, а также рекуррентные сети (например, сети Эльмапа или RTRN [21]).

Аналогичное решение применено для описания алгоритмов обучения нейронных сетей. Алгоритм обучения нейронной сети вырабатывает направление изменения весов нейрон-

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

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

Также исследовап вопрос о языке описапия интеллектуальных систем. В качестве основы для такого языка использован язык текстовых преобразований Thorn, также разработанный автором диссертации2. Документ Thorn состоит из команд, вложенных одна в другую. В отличие от HTML, синтаксис Thorn существенно компактнее, поэтому документы Thorn удобно набирать с клавиатуры. Основное различие между языком Thorn и другими распространенными языками разметки обеспечивается компилятором. Каждая команда ассоциируется с некоторой программой, которая может быть написана на любом языке программирования (как правило, используется Perl). При разборе текста компилятор собирает все текстовые данные, связаппые с командой. После этого, он запускает ассоциированную программу, передавая ей текстовые даппые как входные параметры. Программа возвращает строку, которая подставляется на место команды. После того как все команды выполнены, трансляция документа завершается. Программы могут обмениваться между собой данными через глобальпые переменные. Программы, ассоциированные с командами, сохраняются в библиотеках, которые отделены от документа Thoin. Один и тот же документ Thorn может быть транслирован разпыми библиотеками, т.е. с различпым значением команд. Например, различные библиотеки могут производить код для разных языков программирования.

Язык Thorn успешно применяется для создания HTML-файлов, где он удобен за счет малого, по сравнению с HTML, объема разметочной информации. Кроме того, возможно применение языка Thorn для порождения документов па языке программирования (например, С#). Подобное решение, называемое кодогеперацией, лежит в русле совре-

5 Спецификация языка Thorn доступна по адресу Шр://а1.та1Ь.ияи.га/шШ/ёоЫ.рЬр/нир/&отаЛо-2/главная

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

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

Также пакет GANS был использован для решения ряда практически востребованных задач. Одним пз традиционных применений нейронных сетей является распознавание изображепий. Целью распознавания изображений является логическая характеристика участков изображения: какой предмет изображен па этом участке, каким свойством обладает изображенный предмет в данном участке, и т.д. Распознавание изображений как часть технического зрения является одним из основных направлений развития робототехники. Нами были решены две проблемы распознавания изображений с использованием нейронных сетей: распознавание результатов ультразвукового исследования сердечной мыпщы, выполненное совместно с Институтом иммунологии и физиологии РАН [44], и построение трасс движений игроков на футбольном поле [38].

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

Таким образом, по опосредованным данным в виде зависимости температуры от врсмепи, устанавливаются свойства жидкостей. Эта задача успешно решена с помощью генетических алгоритмов. Свойства жидкости и другие параметры эксперимента кодируются в виде массива чисел с плавающей точкой. Затем алгоритм подбирает оптимальные значения, стараясь минимизировать отклонение расчетпой зависимости от экспериментальной [43]. Разработанное программное обеспечение внедрено в исследовательский процесс Института теплофизики УрО РАН.

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

Результаты диссертации.

1. Создан универсальный программный комплекс поддержки интеллектуальных вычислений, в нем реализовапы все основные интеллектуальные системы: нейронпые сети, генетические алгоритмы и алгоритмы коллективного разума.

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

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

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

произведения с весами нейронов.

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

6. Построены алгоритмы автоматической калибровки робототехнических устройств по обратной связи.

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

Список литературы

[1] Baricelli N. A. Symbiogenctic evolution processes realized by artificial methods. Methodos. - 1957. V. 9. N 35-36. PP. 143-182.

[2] Cover Т. M. The Number of Linearly Inducible Orderings of Points in d-Space. SIAM Journal on Applied Math. - 1967. V. 15. N 2. PP. 434-439.

[3] Dasgupta D., Attoh-Okine N. Immunity-Based Systems: A survey. IEEE International Conference on Systems, Man and Cybernetics. - 1997. PP. 369-374.

[4] Diyankov О. V., Lykov V. A., Terekhoff S. A. Artificial neural networks in weather forecasting. RNNS/IEEE Symposium on Neuroinformatics and Neurocomputers. - 1992.

[5] Dorigo M., Stutzle T. Ant Colony Optimization. Cambridge: MIT Press - 2004.

[6] Forrest S., Perelson A. S., Allen L., Cherukuri It. Self-Nonself discrimination in a Computer. IEEE Symposium on Research in Security and Privacy. - 1994. PP. 202-212.

[7] GAlib Documentation. Massachusetts Institute of Technology. [Электронный ресурс]. URL: http://lancet. mit. edu/galib-2. 4/ (дата обращепия 19. 08. 2009).

[8] Harrington J. Code generation in action. Greenwich: Manning - 2003.

[9] Jenes. Genetic algorithms for Java. Computational and Intelligent Systems Engineering Laboratory at University of Sannio. [Электронный ресурс]. URL: http://sites. google, com/a/ciselab. org/jenes/IIomc/ (дата обращения 21. 07. 2009).

[10] Neural Network Toolbox 6. 0. 2. The MathWorks. [Электронный ресурс]. URL: http://www. mathworks. com/'products/neuralnet/ (дата обращения 11. 08. 2009).

[11] Neurosolutions User's Manual. Gainesville: NeuroDimension Inc. - 1995.

[12] Paulo J G Lisboa, Vellido A., Edisbury B. Business Applications of Neural Networks: The State-Of-The-Art of Real-World Applications (Progress in Neural Processing). New Jersey: World Scientific Publishing Company - 2002.

[13] Peltarion Synapse Documentation. Peltarion Inc. [Электронный ресурс]. URL: http://www. peltarion. com/webdoc/ (дата обращепия 16. 08. 2009).

[14] Sima J., Orponen P. A Computational Taxonomy and Survey of Neural Network Models, of Numbers and Symbols. (BS 1749:1985) London: British Standards Institution. - 2001. PP. 2965-2989.

[15] Spears W. M. Using Neural Networks And Genetic Algorithms As Heuristics For NP-Complete Problems. Fairfax Country, Virginia: George Mason University- 1989.

[16] Thai T. L., Lam H. NET Framework Essentials. Second Edition. Cambridge: O'Reilly -2002.

[17] The C# language. Microsoft. [Электронный ресурс]. URL: http://msdn. microsoft. corn/en-us/vcsharp/aa336809. aspx (дата обращепия 13. 08. 2009).

[18] The Genetic Algorithm Optimization Toolbox (GAOT) for Mathlab 5. North Carolina State University. [Электронпый ресурс]. URL: http://www. ise. ncsu. edu/mirage/GAToolBox/gaot/ (дата обращения 19. 08. 2009).

[19] Turing A. Computing Machinery and Intelligence. Mind. - 1950. V. LIX. N 236. PP. 433-460.

[20] Ежов А. А., Чечеткин В. Д. Нейронные сети в медицине. Откр. сист. - 1997. № 4. Стр. 34-37.

[21] Осовский С. Нейронные сети для обработки информации. Москва: Финансы и статистика - 2002.

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

[23] Семенкж В. В. Экономное кодирование. Санкт-Петербург: СПбГИТМО - 2001.

[24] Хайкин С. Нейронные сети: полный курс. Второе издание. Москва: Вильяме - 2006.

[25] Юревич Е. И., Макаров И. М., Каляев И. А., Лохин В. М. Интеллектуальные роботы. Москва: Машиностроение - 2007.

Статьи автора по теме диссертации, опубликованные в ведущих рецензируемых научных журналах, определенных ВАК:

[26] Деев Д. В., Окуловский Ю. С., Попов В. Ю., Часовских В. П. Система кодогеперации Thornado и ее использование для создания бизнес-приложений. Научно-технический вестник СПбГУ ИТМО. №57. Санкт-Петербург: СпБГУИТМО - 2008. Стр. 80-87.

[27] Окуловский 10. С., Шека А. С. Об архитектуре роботов и интеллектуальном управлении ими. Научно-технический вестник СПбГУ ИТМО. №4S. Санкт-Петербург: СпБГУИТМО - 2008. Стр. 143-150.

[28] Окуловский 10. С., Попов В. Ю. О сложности распознавания множества векторов одним нейроном. Математические труды. Т. 12, №1. Новосибирск: Издательство Института Математики им. С. Л. Соболева СО РАН - 2009. Стр. 130-143.

Прочие статьи автора по теме диссертации:

[29] Окуловский Ю. С. Язык ТН. Проблемы теоретической и прикладной математики: Труды 37-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН -2006. Стр. 496-500.

[30] Окуловский Ю. С. A model and implementation of universal engine for neural systems. 9-й международная конференция «Интеллектуальные системы и компьютерные науки» труды конференции, II том. Москва: Изд-во механико-математического факультета, МГУ - 2006. Стр. 21-24.

[31] Окуловский Ю. С. О функциях, реализуемых одпим нейроном Международная научная конференция «Ипформационно-математические технологии в экономике, технике и образовании» Тезисы докладов. Екатеринбург: УГТУ-УПИ - 2006. Стр. 241241.

[32] Окуловский Ю. С. Алгоритмы порождения линейно-разделимых функций. Проблемы теоретической и прикладной математики: Труды 38-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН - 2007. Стр. 382-387.

[33] Окуловский Ю. С. О функциях, реализуемых одним нейроном. Проблемы математического моделирования и информационно-аналитической поддержки принятия решений. Выпуск 3. Екатеринбург: УГТУ-УПИ - 2007. Стр. 55-61.

[34] Морпев М. JL, Окуловский Ю. С. Комплекс распределения интеллектуальных вычислений па кластер под управлением операционной системы Windows. Четвертая сибирская школа-семинар по параллельным и высокопроизводительным вычислениям. Программа и тезисы. Томск - 2007. Стр. 49-50.

[35] Морнев М. Л., Окуловский Ю. С., Попов В. Ю., Шека А. С. Проблемы интеллектуального моделирования колесных роботов. Международная научная конференция «Информационно-математические технологии в экономике, технике и образовании» Тезисы докладов. Екатеринбург: УГТУ-УПИ - 2007. Стр. 229-231.

[36] Деев Д. В., Окуловский Ю. С. Разработка бизнес-приложений с использованием системы кодогеперации Tbornado. Международная научпая конференция «Ипформационно-математические технологии в экономике, техпике и образовании» Тезисы докладов. Екатеринбург: УГТУ-УПИ - 2007. Стр. 208-210.

]37] Окуловский Ю. С. О классификации линейно-разделимых функций. 10-ая Всероссийская научно-техническая конференция «Нейроинформатика-2008, сборник научных трудов, часть 1. Москва: Изд-во МИФИ - 2008. Стр. 212-218.

[38] Окуловский Ю. С. Распознавание фигур на игровом поле. Труды конференции «Научпая сессия МИФИ-2080». Москва: Изд-во МИФИ - 2008. Стр. 193-194.

[39] Бабинов А. М., Морнев М. Л., Окуловский Ю. С., Попов В. 10., Шека А. С. Вазовое программное обеспечение колесного робота на базе RC-CAR AT-10ES. Труды конференции «Научная сессия МИФИ-2080». Москва: Изд-во МИФИ - 2008. Стр. 221-222.

[40] Деев Д. В., Окуловский Ю. С. О порождении подсистемы вывода документов. Проблемы теоретической и прикладной математики: Труды 39-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН - 2008. Стр. 388-392.

[41] Бабинов A. M., Морнев M. Л., Окуловский Ю. С., Попов В. Ю., Шека А. С. Об интеллектуальных алгоритмах управления роботами. Прикладные аспекты моделирования и разработки систем ипформационио-аналитической поддержки и принятия решений. Выпуск 4. Екатеринбург: УГТУ-УПИ - 2008. Стр. 169-175.

[42] Деев Д. В., Окуловский Ю. С. Система кодогенерации Thornado. Прикладные аспекты моделирования и разработки систем информационно-аналитической поддержки и принятия решений. Выпуск 4. Екатеринбург. УГТУ-УПИ - 2008. Стр. 209-216.

[43] Скрипов П. В., Смотрицкий П. В., Старостин А. А., Окуловский Ю. С. Estimation of theimophysical properties for pulse heated substances. Experiment and modelling. XXIII международная конференция «Уравнения состояния вещества» тезисы докладов. Эльбрус - 2008. Стр. 66-68.

[44] Окуловский Ю. С., Попов В. Ю. О построении контуров на изображениях УЗИ и МРТ. Методы компьютерной диагностики в биологии и медицине - 2008. Саратов -2008. Стр. 82-83.

[45] Окуловский Ю. С., Попов В. Ю. Компендиум. Результаты реализации инновационных образовательных программ ПНПО в части формирования актуальных компетенций и развития межвузовского взаимодействия в области информационно-коммуникационных технологий к Всероссийскому семинару-презентации. Нижний Новгород - 2008. Стр. 135.

[46] Окуловский Ю. С. Интеллектуальные алгоритмы калибровки робототехпиче-ских устройств. Третья международная научная конференция «Информационно-математические технологии в экономике, технике и образовании» Тезисы докладов. Екатеринбург: УГТУ-УПИ - 2008. Стр. 244.

[47] Окуловский Ю. С. Интеллектуальный алгоритм автоматической калибровки робото-технических устройств. Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН - 2009. Стр. 359-363.

[48] Конончук Д. О., Окуловский Ю. С. Универсальный пакет поддержки интеллектуальных вычислений GANS. VI Всероссийская межвузовская конференция молодых ученых. Труды конференции. Выпуск 4. Математическое моделирование и программное обеспечение. Сапкт-Петербург: СцБГУИТМО - 2009. Стр. 151-157.

Введение

Глава 1. Вычислительные возможности отдельного нейрона

1.1. Линейно-разделимые функции.

1.1.1. Критерий линейной разделимости для булевых функций.

1.1.2. Алгоритм проверки линейной разделимости.

1.1.3. Критерий линейной разделимости для функций распознавания

1.1.4. Монотонные и канонические булевы функции.

1.1.5. Классификация линейно-разделимых булевых функций.

1.2. Линейно-порожденные порядки

1.2.1. Образующие множества линейно-порожденных порядков.

1.2.2. Порядки с эквивалентными точками

1.2.3. Решетка линейно-порожденных порядков.

1.2.4. Связь между линейно-разделимыми функциями и линейно-порожденными порядками.

Глава 2. Комплекс поддержки интеллектуальных вычислений GANS

2.1. Компонентная модель GANS.

2.2. Интеллектуальные системы.

2.2.1. Нейронные системы.

2.2.2. Генетические алгоритмы

2.2.3. Алгоритмы коллективного разума.

2.3. Драйвер обучения.

2.3.1. Архитектура.

2.3.2. Процесс обучения.

2.4. Язык описания интеллектуальных систем.

2.4.1. Язык Thorn.

2.4.2. Система кодогенерациии Thornado.

2.4.3. Описание интеллектуальных систем.

Глава 3. Тестирование комплекса интеллектуальных вычислений

3.1. Приближенное решение NP-трудных задач с помощью генетических алгоритмов.

3.2. Аппроксимация функций с помощью нейронных сстсй

3.3. Обработка изображений с помощью нейронных сетей.

3.4. Алгоритм калибровки зонда и свойств жидкости.

3.5. Алгоритм автоматической калибровки робота.

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

• делать выводы, являющиеся логическим следствием имеющихся знаний;

• обучаться решению задачи по предъявленным примерам решения и в дальнейшем работать на основании накопленного опыта;

• демонстрировать способность к адаптации и корректировать собственное поведение при изменении условий;

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

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

• моделирование экспертной оценки (в медицине [33], предсказании погоды [6], и т.д);

• поиск приближенных решений для труднорсшасмых задач и КР-полных задач [7], [27];

• системное программное обеспечение (сжатие информации без потерь [37], распознавание вредоносного программного обеспечения [8])

• робототехника (распознавание изображений и техническое зрение, планирование и управление [41])

• экономика [19];

• энергетика [35];

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

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

Многие модели интеллектуальных вычислений позволяют эмулировать машину Тьюринга [24]. Соответственно, их можно использовать для решения произвольных классических задач. Однако не следует рассматривать интеллектуальные системы как замену традиционных вычислителей. На многих задачах они работают медленнее, чем аналогичные детерминированные. Поэтому не имеет смысла использовать интеллектуальные алгоритмы для, скажем, сортировки массивов или умножения чисел. Однако, в ряде случаев анализ данных точными детерминированными алгоритмами занимает слишком много времени; в этих случаях, приближенное решение задачи интеллектуальными алгоритмами оказывается более выгодным. Кроме того, интеллектуальные алгоритмы позволяют решать задачи, входные данные которых зашумлены, некорректны либо сформулированы в нечетких категориях (например, субъективные оценки).

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

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

На сегодняшний день создано и постоянно создается большое количество программных реализаций систем искусственного интеллекта. Однако, не существует известных систем, реализующих алгоритмы коллективного разума. Также не представлены продукты, интегрирующие генетические алгоритмы и нейронные сети. Широко распространены пакеты, содержащие лишь реализацию нейронных сетей. Успешные коммерческие реализации (см., например, [17], [20]) имеют закрытую архитектуру, и позволяют работать лишь со строго определенными типами нейронных сетей и алгоритмами их обучения, существенно ограничивая возможности пользователя по разработке новых систем. Большинство распространенных программных комплексов поддержки генетических алгоритмов (см., например, [9], [13]) не допускают интеграцию с нейронными сетями из-за узкой специализации. В целом также следует отметить более низкий уровень реализаций генетических алгоритмов по сравнению с нейронными сетями, проявляющийся в детальности документации, поддержке, спектре функциональности и т.д. Некоторые системы искусственного интеллекта реализованы в составе крупных программных пакетов, таких, как МаШаЬ ([16], [30]). Такая реализация позволяет полнее интегрировать интеллектуальные вычисления со сложными математическими вычислениями, однако затрудняет оптимизацию интеллектуальных систем и их использование вне среды МаШаЬ.

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

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

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

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

Впервые биологический нейрон был рассмотрен как логическое устройство Уорреном МакКалоком и Уолтером Питсом [15]. Математическая модель простейшей сети была впервые предложена Френком Розенблаттом в 1957 году [21]. В 1960 году эта модель была реализована в вычислителе Магк-1 - первом в мире нейрокомпьютере. В результате было получено первое в истории устройство для симуляции интеллектуальной деятельности человека. Это позволило говорить о возможности решения различных задач не при помощи классических алгоритмов, содержащих готовые схемы действий, а на основе обучения и опыта. На фоне всеобщего интереса к искусственному интеллекту, из полученных результатов были сделаны весьма амбициозные выводы о скором создании искусственного интеллекта, основанного на пер-септронах. Однако, в 1969 году Марвин Минский и Сеймур Паперт публикуют книгу «Персептроны» [14], в которой указывают (не всегда корректно) па ограничения вычислительных способностей нейронов и ограничения при их обучении. Данная публикация, в сочетании с несбывшимися амбициозными прогнозами, вселила пессимизм в разработчиков и заказчиков искусственного интеллекта. Также эта работа сместила внимание разработчиков на логические и экспертные системы.

В начале восьмидесятых годов было совершено несколько открытий, которые возродили интерес к нейронным сетям. Во-первых, были найдены ошибки в публикации Минского. Затем была создана модель многослойного персеп-трона и предложен алгоритм ее обучения на базе метода обратного распространения ошибки [22]. Эти открытия были дополнены быстрым ростом производительности вычислительных машин, которые позволили строить большие и, соответственно, мощные по вычислительным возможностям нейронные сети. В результате, интерес к нейронным сетям был восстановлен, и не угасал до наших дней.

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

Узлы, помеченные а^, отображают «входные клеммы» нейрона, на которые подается входной сигнал XI,. ,хп. Каждая клемма соединена с телом нейрона п связью. С каждой связью ассоциирован вес связи, тп. Вектор IV = ., гип) называют вектором весов нейрона. Вычисление нейрона происходит по формуле где / : М —К - произвольная функция активации. Выходной сигнал нейрона подается на выход нейрона, отмеченный буквой у.

Часто одна из связей становится активационной связью. Это означает, что она подключена не ко входной клемме, а к источнику постоянного сигнала,

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

В качестве функции активации могут выступать произвольные функции. Часто применяют функции порогового вида. Пороговыми функциями называются монотонные функции, для которых 1гт1>со/(ж) = а и Нтх=^00/(х) — Ь, где а, Ъ - неравные константы. Простейшей пороговой функцией является функция /(х) = sign(a;), которая часто применяется в теоретических исследованиях. Нейрон с такой функцией активации называется персептроиом. Для практических нужд, однако, интересны непрерывные функции. Например, это униполярная функция 1 + е-Рх' где /3 - параметр, ¡3 > 0. Эта функция изменяется от 0 при х —> —оо до 1 при х —* оо. Другая функция порогового вида - биполярная функция ж) = 1апЬ(—/Зж), где (3 - параметр, (3 > 0, а tanh - гиперболический тангенс, tanh(ж) = ■ Эта функция принимает значения на отрезке (—1; 1).

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

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

2>

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

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

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

Генетические алгоритмы и алгоритмы коллективного разума менее изучены, чем нейронные сети. Несмотря на то, что первые работы в этих направлениях начались в тот же период, что и первые работы в области нейронных сетей (50-60-е годы XX века), они стали широко использоваться и изучаться лишь в последнее время. Это связано, прежде всего, с тем, что для запуска даже простого генетического алгоритма требуются существенные вычислительные ресурсы, в то время как запуск небольшой нейронной сети таких ресурсов не требует.

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

Движущими силами эволюции называют следующие три фактора:

• наследственность, т.е. свойство потомков быть в основном похожими на родителей;

• изменчивость, т.е. свойство потомков к демонстрации отсутствующих у родителей признаков;

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

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

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

История генетических алгоритмов, как метода моделирования эволюционного процесса, развивалась поступательно. Впервые он был предложен Ниль-сом Аалом Боричелли в 1954 году в работе [1]. Эта работа не получила широкой известности, и впоследствии другими авторами были сделаны повторные публикации в промежутке от 1960 до 1980. Постепенно подход генетических алгоритмов набирал популярность. При этом, видоизменялись представления о генетических алгоритмах: если в 1960-х годах при их использовании следовали биологическим аналогиям, то позднее их формулировка становилась все более общей.

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

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

На каждой итерации, состояние узла изменяется в зависимости от состояний в его окрестности. Под окрестностью понимается в общем случае произвольное множество узлов, на практике часто употребляют окрестность четырех или восьми непосредственных соседей. Примером клеточного автомата является игра «Жизнь» [10], распространенная в 70-х годах. Известно, что клеточные автоматы являются универсальной вычислительной структурой -в частности, игра «Жизнь» способна эмулировать универсальную машину Тыоринга.

Начиная с 90-х годов прошлого века, были разработаны и другие алгоритмы коллективного разума: например, алгоритмы, моделирующие ульи насекомых [7] или иммунную систему [26], [5]. Из всех видов алгоритмов искусственного интеллекта, алгоритмы коллективного разума являются наиболее «молодыми», и, соответственно, в этой области на сегодняшний день остаются открытыми многие вопросы как теоретического, так и практического характера.

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

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

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

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

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

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

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

1. Baricelli N. A. Symbiogenetic evolution processes realized by artificial methods. Methodos. - 1957. V. 9. N 35-36. PP. 143-182.

2. Cover Т. M. Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition. IEEE Transactions on Electronic Computers, 14(3). 1965. V. EC-14. N 3. PP. 326-334.

3. Cover Т. M. The Number of Linearly Inducible Orderings of Points in d-Space. SIAM Journal on Applied Math. 1967. V. 15. N 2. PP. 434-439.

4. Cybenko G. Approximation by a superposition of a sigmoidal function. Mathematics of Control, Signals and Systems. 1989. V. 2. PP. 303-314.

5. Dasgupta D., Attoh-Okine N. Immunity-Based Systems: A survey. IEEE International Conference on Systems, Man and Cybernetics. 1997. PP. 369-374.

6. Diyankov О. V., Lykov V. A., Terekhoff S. A. Artificial neural networks in weather forecasting. RNNS/IEEE Symposium on Neuroinformatics and Neurocomputers. 1992.

7. Dorigo M., Stutzle T. Ant Colony Optimization. Cambridge: MIT Press -2004.

8. Forrest S., Perelson A. S., Allen L., Cherukuri R. Self-Nonself discrimination in a Computer. IEEE Symposium on Research in Security and Privacy. -1994. PP. 202-212.

9. GAlib Documentation. Massachusetts Institute of Technology. Электронный ресурс. URL: http://lancet. mit. edu/galib-2. 4/ (дата обращения 19. 08. 2009).

10. Gardner M. The Game of Life. Scientific American. 1940. N 223. PP. 120-123.

11. Harrington J. Code generation in action. Greenwich: Manning 2003.

12. Hedegus Т., Meggido N. On the geometric separability of Boolean functions. Discrete Applied Mathematics. 1994. V. 7. N 3. PP. 205-218.

13. Jenes. Genetic algorithms for Java. Computational and Intelligent Systems Engineering Laboratory at University of Sannio. Электронный ресурс. URL: http://sites. google, com/a/ciselab. org/jenes/Home/ (дата обращения 21. 07. 2009).

14. Minsky M., Papert S. Perceptrons. Cambridge MA: MIT Press 1969.

15. MucCulloch W., Pits W. A logical calculus of the ideas immanent in nervous activity. Mathematical Biophysics. 1943. V. 5. PP. 18-27.

16. Neural Network Toolbox 6. 0. 2. The MathWorks. Электронный ресурс. URL: http://www. mathworks. com/products/neuralnet/ (дата обращения 11. 08. 2009).

17. Neurosolutions User's Manual. Gainesville: NeuroDimension Inc. 1995.

18. Omondi A. R., Rajapakse J. C. FPGA Implementations of Neural Networks. New York: Springer-Verlag, Inc. 2006.

19. Paulo J G Lisboa, Vellido A., Edisbury B. Business Applications of Neural Networks: The State-Of-The-Art of Real-World Applications (Progress in Neural Processing). New Jersey: World Scientific Publishing Company -2002.

20. Peltarion Synapse Documentation. Peltarion Inc. Электронный ресурс. URL: http://www. peltarion. com/webdoc/ (дата обращения 16. 08. 2009).

21. Rosenblatt F. The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain. Psychological Review. Cornell Aeronautical Laboratory 1958. V. 65. N 6. PP. 386-408.

22. Rumelhart D. E., Hinton G. E., Williams R. J. Learning representations by back-propagating errors. Nature. 1986. N 323. PP. 533 - 536.

23. Sandcastle Documentation Builder. Microsoft. Электронный ресурс. URL: http://www. codeplex. com/Sandcastle (дата обращения 24. 07. 2009).

24. Siegclmann H. Т., Sontag Е. D. On The Computational Power Of Neural Nets. Journal of computer and system sciences. 1995. V. 50. N 1. PP. 132-150.

25. Sima J., Orponen P. A Computational Taxonomy and Survey of Neural Network Models, of Numbers and Symbols. (BS 1749:1985) London: British Standards Institution. 2001. PP. 2965-2989.

26. Singh S., Thayer S. Immunology Directed Methods for Distributed Robotics: A Novel, Immunity-Based Architecture for Robust Control and Coordination. Proceedings of SPIE: Mobile Robots XVI. 2001.

27. Spears W. M. Using Neural Networks And Genetic Algorithms As Heuristics For NP-Complete Problems. Fairfax Country, Virginia: George Mason University 1989.

28. Thai T. L., Lam H. NET Framework Essentials. Second Edition. Cambridge: O'Reilly 2002.

29. The Оф language. Microsoft. Электронный ресурс. URL: http://msdn. microsoft. com/en-us/vcsharp/aa336809. aspx (дата обращения 13. 08. 2009).

30. The Genetic Algorithm Optimization Toolbox (GAOT) for Mathlab 5. North Carolina State University. Электронный ресурс. URL: http://www. ise. ncsu. edu/mirage/GAToolBox/gaot/ (дата обращения 19. 08. 2009).

31. Turing A. Computing Machinery and Intelligence. Mind. 1950. V. LIX. N 236. PP. 433-460.

32. Гэри M., Джонсон D. Вычислительные машины и труднорешаемые задачи. Москва: Мир 1982.

33. Ежов А. А., Чечеткин В. Д. Нейронные сети в медицине. Откр. сист. -1997. № 4. Стр. 34-37.

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

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

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

37. Семенюк В. В. Экономное кодирование. Санкт-Петербург: СПбГИТМО- 2001.

38. Хайкин С. Нейронные сети: полный курс. Второе издание. Москва: Вильяме 2006.

39. Черников С. Н. Линейные неравенства. Москва: Мир 1973.

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

41. Юревич Е. И., Макаров И. М., Каляев И. А., Лохин В. М. Интеллектуальные роботы. Москва: Машиностроение 2007.Список работ автора по теме диссертации

42. Окуловский Ю. С. Язык ТН. Проблемы теоретической и прикладной математики: Труды 37-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН 2006. Стр. 496-500.

43. Окуловский Ю. С. О функциях, реализуемых одним нейроном. Международная научная конференция «Информационно-математические технологии в экономике, технике и образовании» Тезисы докладов. Екатеринбург: УГТУ-УПИ 2006. Стр. 241-241.

44. Окуловский Ю. С. Алгоритмы порождения линейно-разделимых функций. Проблемы теоретической и прикладной математики: Труды 38-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН -2007. Стр. 382-387.

45. Окуловский Ю. С. О функциях, реализуемых одним нейроном. Проблемы математического моделирования и информационно-аналитической поддержки принятия решений. Выпуск 3. Екатеринбург: УГТУ-УПИ -2007. Стр. 55-61.

46. Окуловский Ю. С. О классификации линейно-разделимых функций. 10-ая Всероссийская научно-техническая конференция «Нейроинформатика-2008, сборник научных трудов, часть 1. Москва: Изд-во МИФИ 2008. Стр. 212-218.

47. Окуловский Ю. С. Распознавание фигур на игровом поле. Научная сессия МИФИ-2008, сборник научных трудов, том 10 «Интеллектуальные системы и технологии». Москва: Изд-во МИФИ 2008. Стр. 193-194.

48. Деев Д. В., Окуловский Ю. С. О порождении подсистемы вывода документов. Проблемы теоретической и прикладной математики: Труды 39-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН 2008. Стр. 388-392.

49. Деев Д. В., Окуловский Ю. С. Система кодогенерации Thornado. Прикладные аспекты моделирования и разработки систем информационно-аналитической поддержки и принятия решений. Выпуск 4. Екатеринбург: УГТУ-УПИ 2008. Стр. 209-216.

50. Окуловский Ю. С., Попов В. Ю. О построении контуров на изображениях УЗИ и МРТ. Методы компьютерной диагностики в биологии и медицине 2008. Саратов - 2008. Стр. 82-83.

51. Деев Д. В., Окуловский Ю. С., Попов В. Ю., Часовских В. П. Система кодогенерации Thornado и ее использование для создания бизнес-приложений. Научно-технический вестник СПбГУ ИТМО. №57. Санкт-Петербург: СпБГУИТМО 2008. Стр. 80-87.

52. Окуловский Ю. С. Интеллектуальный алгоритм автоматической калибровки робототехнических устройств. Проблемы теоретической и прикладной математики: Труды 40-й Всероссийской молодежной конференции. Екатеринбург: УрО РАН 2009. Стр. 359-363.

53. Окуловский Ю. С., Шека А. С. Об архитектуре роботов и интеллектуальном управлении ими. Научно-технический вестник СПбГУ ИТМО. №48. Санкт-Петербург: СпБГУИТМО 2008. Стр. 143-150.

54. Окуловский Ю. С., Попов В. Ю. О сложности распознавания множества векторов одним нейроном. Математические труды. Т. 12, №1. Новосибирск: Издательство Института Математики им. С. JT. Соболева СО РАН 2009. Стр. 130-143.