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

УДК 519 9

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

НЕЧАЕВА Ольга Игоревна

НЕЙРОСЕТЕВЫЕ МОДЕЛИ, АЛГОРИТМЫ И КОМПЛЕКС ПРОГРАММ ДЛЯ ПОСТРОЕНИЯ АДАПТИВНЫХ СЕТОК

05 13 18 - математическое моделирование, численные методы и комплексы

программ

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

г Новосибирск, 2007

003061421

Работа выполнена на кафедре вычислительных систем механико-математического факультета Новосибирского государственного университета

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

Бандман Ольга Леонидовна доктор технических наук, профессор

Официальные оппоненты:

Годунов Сергей Константинович доктор физико-математических наук, академик РАН

Тарков Михаил Сергеевич кандидат технических наук

Ведущая организация.

Институт Вычислительных Технологий СО РАН

Защита состоится 2 октября 2007 г в 15 00 на заседании диссертационного совета Д 003 061 02 в Институте вычислительной математики и математической геофизики СО РАН по адресу 630090, г Новосибирск, пр Ак Лаврентьева, 6

С диссертацией можно ознакомиться в читальном зале ИМВиМГ СО РАН (г Новосибирск, пр Ак Лаврентьева, 6)

Автореферат разослан 25 июля 2007 г

Ученый секретарь диссертационного совета Д003 061 02,

-м н С Б Сорокин

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

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

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

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

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

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

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

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

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

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

- Провести экспериментальное исследование методов и оценить качество получающихся адаптивных сеток по общепринятым критериям качества

- Провести сравнение с методом эквираспределения по критериям качества и на основе оценки точности решения задач на сетках, построенных обоими методами

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

1. Предложены три нейросетевые модели типа 80М1 модель ЙОМ с необучаемыми нейронами, раскрашенная модель БОМ и смешанная модель вОМ, а также композиционная модель вОМ, которые во-первых, решают ряд проблем использования базовой модели БОМ, предложенной Кохоненом, а во-вторых, позволяют получать адаптивные сетки, удовлетворяющие общепринятым критериям качества

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

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

4 Реализованный программный комплекс является первым прототипом программного приложения для построения адаптивных сеток рассматриваемого класса на основе нейросетевых моделей типа БОМ

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

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

Методы исследований. При выполнении работы использовались методы теории нейронных сетей, методы теории обучения, аппарат теории вероятностей и математической статистики, методы Монте-Карло При исследовании качества сеток и сравнения предлагаемого метода с традиционными использовались методы вычислительной математики, методы построения адаптивных сеток на основе решения нелинейных ДУ, методы оценки качества адаптивных сеток Для экспериментального исследования предлагаемых алгоритмов была выполнена их программная реализации в среде Visual С++ с использованием библиотеки MFC, а также библиотеки параллельного программирования MPI

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

- Всероссийской научно-технической конференции Нейроинформатика-2006

- Международная конференция по искусственным нейронным сетям, ICANN 2006, Афины, Греция

- Международная конференция Parallel Computing Technologies, РаСТ 2005

- Пятая школа-семинар «Распределенные кластерные вычисления», Красноярск, 2005

- Конференция молодых ученых ИВМиМГ, Новосибирск, 2004 и 2005 Вторая сибирская школа-семинар по параллельным вычислениям Томск, 2003

- Всероссийский семинар «Нейроинформатика и ее приложения», ИВМ СО РАН, Красноярск, 2003, 2004 и 2005

- Международная научная студенческая конференция «Студент и научно-технический прогресс», НГУ, Новосибирск, 2005 и 2004 Международный семинар «Вычислительные методы и решение оптимизационных задач», Киргизия, оз Иссык-Куль, 2004

Семинары Математическое и архитектурное обеспечение параллельных вычислений ИВМиМГ СО РАН (3 доклада), Информационно вычислительные технологии ИВТ СО РАН (2 доклада), Математика в приложениях ИМ СО РАН (1 доклад), Системное программирование ИСИ СО РАН (1 доклад)

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

Публикации. Основное содержание диссертации отражено в 15 печатных работах Среди них 7 работ в рецензируемых изданиях, в их числе 2 работы в журналах из перечня ВАК, 4 работы в трудах конференций и 4 тезиса в материалах конференций.

Финансовая поддержка работы. Работа была отмечена премией на конференции Молодых ученых ИВМиМГ СО РАН в 2005 г. и дважды поощрена стипендиями Intel Scholarship Grant в 2005 и 2006 г Также работа была поддержана грантами по программе фундаментальных исследований №14-16 Президиума РАН (2004-2007) и программе Рособразования «Развитие научного потенциала ВШ», проект РНП.2.2 1 1.3653 (2006-2007), European Neural Network Society Travel Grant для участия в международной конференции ICANN 2006, Афины, Греция и IEEE Computational Intelligence Society Travel Grant для участия в международной конференции UCNN 2007, Орландо, США

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

1 Условие сохранения топологии Близким элементам входного пространства соответствует один и тот же или близкие нейроны в карте нейронов

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

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

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

В пункте 1.4 вводятся обозначения и приводится формальная постановка задачи построения адаптивных сеток Пусть б - это физическая область в пространстве Яд, на которой требуется построить адаптивную сетку Q -это вычислительная область в пространстве в пространстве к <п, с зафиксированной на ней сеткой = , где д, - узлы сетки, е Яд, N

- количество узлов сетки Пусть также задана положительная функция плотности сетки м> С—>Я+ Требуется найти отображение вычислительной области на физическую й, которое переводит сетку (¿^ в адаптивную сетку = {х,, .Хд,}, х, £ Щ, с заданным распределением плотности. Необходимо также, чтобы при отображении граничные узлы сетки <2н переводились в узлы сетки распределенные вдоль границы области в Физическая область в может быть как односвязной, так и многосвязной

Вторая глава посвящена анализу непосредственного применения базовой модели !ЗОМ для построения адаптивных сеток В пункте 2 1 все элементы базовой модели Б ОМ сопоставляются с математическими объектами, участвующими в постановке задачи При этом сопоставлении входным пространством для модели ЯОМ является пространство , выходным пространством - Якв, к<,п . Карта модели Б ОМ состоит из N нейронов

М= {ей. где положение нейрона е, в карте задается координатами

зафиксированного узла д„ а весовым вектором этого нейрона являются искомые координаты узла х\ в физической области. Таким образом, нейрон - это пара е, = (<?„ Обучающее множество Н = {у],...,ут), где у, б С , * = 1, . ,Т, - это выборка из распределения, задающегося функцией плотности вероятностного распределения р(х), которая равна нормированной функции плотности Цх)

с

Алгоритм обучения для базовой модели БОМ в терминах сеточной постановки задачи состоит из следующих шагов

Алг А

1. Устанавливаются начальные положения узлов сетки х,(0)

2 На каждой итерации * = 1, ,Т выполняются следующие действия

а) Выбирается очередной элементу, выборки Я

б) Выбирается ближайший к у, узел сетки хт(г) в соответствии с условием т = а^ гшп (1 {у, х, (г)) Такой узел хт((), а также нейрон ет,

1=1 .Л'

называются далее победителем

в) Проводится корректировка положений узлов сетки по формуле

хЦ +1) = хЦ) + вЧт (/, <7,) (у, - х,(ф, (2)

для всех I = 1, , N , где в (7,ql) е. [О, 1) - это коэффициент обучения

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

универсально относительно размерности физической области и пространства, в котором эта область расположена Базовая модель вОМ задается тройкой элементов ЮМА = < М,Н,Алг А >

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

(1) Размер обучающего множества Г фиксируется заранее и по правилу, которое зависит от количества узлов сетки

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

Общий вид коэффициента обучения Я,). где Я(0 = Г02х(1),

, ¿(0=1-^, КО=г{Т)+05'/г-г(Т))^ Здесь л'еСОЛ) заранее зафиксированная близкая к нулю константа, г(1) и г(Т) -значения радиуса обучения, г(1) > г(Т) В этом же пункте доказывается серия утверждений о том, что коэффициент обучения удовлетворяет требованиям из теории БОМ на каждой итерации наибольшее смещение получает узел-победитель, а остальные узлы меняют свой положение тем меньше, чем дальше они расположены от победителя в вычислительной области Иллюстрируются две стадии процесс обучения стадия упорядочения и стадия уточнения

В пункте 2 3 формулируется и доказывается теорема о соответствии, которая гласит о том, что при достижении цели обучения модели ЭОМ

выполняется аналог принципа эквираспределения для ячеек Вороного сетки, а значит обосновывается принципиальная возможность получения с помощью моделей типа БОМ адаптивных сеток рассматриваемого класса с заданной функцией плотности сетки Для каждого г-го узла сетки ячейка Вороного - это множество V, = {хе й\с1(х,х1) <с!(х,хк),к = 1, . Теорема о соответствии

Пусть для карты нейронов выполняется условие равной представимости (пт 11) Тогда вероятностной оценкой произведения площади ячейки Вороного К, на значение функции плотности вероятностного распределения в узле х, является число 1/ N для всех узлов сетки, т е

\У,\ р(х,)»1/АГ, « = 1, (3)

Доказательство этой теоремы основано на утверждениях из теории методов Монте-Карло

Пункт 2 4 посвящен анализу влияния известных проблем базовой модели БОМ на качество получающихся адаптивных сеток

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

а, = X (4)

где г - радиус обучения, Вг ) - окрестность точки </, радиуса г Значения а, должны быть одинаковы для всех узлов сетки, и малы для тех узлов вблизи границы, на которые влияет граничный эффект Эта характеристика отражает зависимость граничного эффекта от радиуса обучения1 граничный эффект проявляется тем сильнее, чем больше радиус обучения

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

Утверждение Если все узлы начальной сетки лежат внутри выпуклой области С, то до конца итерационного процесса они не выйдут за ее границу

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

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

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

В пункте 3.1 предлагается три нейросетевые модели типа КОМ, являющиеся расширением базовой модели ЯОМ. В 3.1.1 предлагается модель ЙОМ с необучаемыми нейронами (80М^ = <М,Г,Щ>Алг.В >). В этой модели среди всех нейронов карты выделяется подмножество /^сМ таких нейронов, пес а которых полагаются равными некоторым заданным значениям и не меняются в процессе обучения. Обеспечение согласованности между обучаемыми и необучаемыми нейронами при корректировке достигается за счет того, что, во-первых, неподвижные узлы участвуют в выборе победителя, во-вторых, если /и-й учел стал победителем и при этом является неподвижным, го случайная точкам, заменяется на положение узла хт(1).

Рис. 1. Процесс построения сетки с пеобучаемыми граничными нейронами: 1-я, 10-я и 10000-н итерации

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

В 3.1.2 предлагается раскрашенная модель КОМ (80М(; = < М,Сс,Сд,Н,Алг.С >). Функция раскраски физической области

Са:0-* {с1(...кс„} каждой точке О ставит в соответствие один из цветов

, . Функция раскраски Сд : М {с,,,..,ср} задает цвета для нейронов.

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

В 3 13 предлагается смешанная модель SOM (SOMbc = <M,F,CG,CQ,H,Anz ВС >), которая объединяет в себе черты

модели SOM с необучаемыми нейронами и раскрашенной модели SOM Алгоритм обучения для смешанной модели состоит из следующих шагов. Алг ВС

На каждой итерации t = tsl, , tfM выполняются следующие действия

(1) Выбирается очередной элемент у, из выборки Я

(2) Вычисляются Евклидовы расстояния d(,) между у, и теми xt(?), для которых Сс(у) = Св(г), и выбирается нейрон победитель с весами хт (t), где т = argnun{e?0>,,*,(/))|CG(y,) = Сд(е,)}

(3) Если ет е F , то случайная точка у, должна быть заменена весовым вектором победителя yt = хт (/).

(4) Выполняется корректировка весов всех нейронов с индексами из М\ F по следующему правилу

л,it +1) = (0 + Sit)^{t,)(у, -х,(0), где е, е M\F (5)

В пункте 3 2 предлагается композиционная модель SOM -SOMD= <{SOMkBC},Ca,CQ,AmD>, являющаяся комбинацией смешанных

моделей SOMkK, к=0, , и, которые взаимодействуют между собой специальным образом и самоорганизуются на заданном им подмножестве входных данных, определяющих, как правило, границу или внутренность физической области Алгоритм обучения для композиционной модели основан на чередовании обучения каждой модели SOM по Алг ВС

Пусть физическая область G разбита на подобласти Gt, ,Ga Множество нейронов также разбито на и подмножеств Каждое к-е подмножество нейронов, к = 1, , п, формирует часть сетки, которая должна растянуться по подобласти Gk Смешанная модель для к-й части сетки задается шестеркой SOMkBC =<Mk,Ft,CG>,Cß ,Hk, Алг ВС > Карта М,сМ

задается следующим образом Если требуется, чтобы к-я часть сетки адаптировалась к соседней части сетки, например, с номером к+1, то карта Мк должна включать не только нейроны к-й части, но и нейроны из соседней части сетки Эти соседние нейроны рассматриваются как необучаемые при

обучении к—й карты Множество Fk с Мк - это необучаемые нейроны к-й

смешанной модели SOM Смешанная модель SOM°BC =<M,0,CG,Ce,H, Алг ВС >

отвечает всей сетке в целом Пример карт Мк показан на рисунке рис 2

Обучающее множество для к-й смешанной модели 80М - это выборка И к из распределения, заданного плотностью р(х)\а ■ Пусть также заданы

функции раскраски Сс, и Сд, которые определены на всей физической Области О и на всей карте М соответственно. Тогда Св = Са\с и

Са = СеI . Пример функций раскраски С(; и Сд показан на рисунке рис. 3.

М\ Мг М3

'Л'.'. 2.-иМТ ,ро ю кар! д]1й построения сетки на ьшогосвязной физической области. Черным показаны обучаемые нейроны, серым - необучаемые.

Рис. 3. Функции раскраски: (а) функция С(;: (б) функция С^.

Каждый этап чередования алгоритма обучения для композиционной модели 8ОМ состоит в обучении всех моделей 80М в течение заданного числа итераций, называется макроитерацией и обозначается через Дня каждой карты Мк пропорционально ]А4| задается максимальное количество итераций Тк, Пусть <рк (л) - это число итераций на макроитерации 5, в течение которых обучается к-я модель 80М. Алгоритм обучения для композиционной модели 8ОМ состоит из следующих шагов.

Ллг. £>.

(1) Устанавливаются произвольные начальные веса яг(0), .

(2) На первой макроитерации = || обучается модель ХОМавс в течение заданного числа итераций Т0, т. е при и ^«|1(1) = 7,0,

(3) Повторяются следующие действия на каждой мзкроитсрации .1 > I: для каждого к = \,...,п обучается модель БОМ1с в течение <рк(з) итераций, т.е. = и =

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

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

В пункте 3 4 приводится параллельная версия алгоритма обучения Алг ВС для смешанной модели БОМ Поскольку во всех алгоритмах обучения узлы сетки обрабатываются независимо друг от друга, то в параллельном алгоритме все нейроны равномерно распределяются по процессорам в любом порядке Коммуникации между процессорами требуются только при нахождении нейрона победителя и его рассылке всем процессорам

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

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

Таблица 1 Возможные и допустимые значения критериев качества сеток

Критерий качества Возможные значения Допустимые значения Вид ячейки при определенных значениях критерия

Выпуклость ячеек (-СО,1] [0,1] =1 - параллелограмм =0-треугольник <0 - невыпуклая ячейка

Ортогональность ячеек [-1.1] [0,1] =1 - прямоугольник =0 - треугольник

Вытянутость ячеек (0,11 Зависит от задачи =1 - ромб

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

Ортог.

мин: 0.0587 ср: 0.9119

Выпгякут.

мин; О 1732 ср: 0.^304

Вытянут.

мин: 0.0733 ср: 0.5433

Выпукл.

мин: 0.1033 ср: 0.9280

Выпукл.

мин: 0.0454 ср: 0.9266

Выпукл. Ортог. Вытянут.

мин: 0,0277 мин: 0.0587 мин: 0.1744 ср: 0.9224 ср: 0.9598 ср: 0.4891

Выну КН. ОртОГ. [ Вытянут.

мин: 0.3960 мин: 0.3939 мим: 0.0631 ср: 0.8600 ср: 0 9241 | ср: 0.3499

Рис. 4. Примеры построенных сеток нейросегевым методом и методом экв«распределения. а также значения критериев качества для и их

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

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

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

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

Рис 2. (а) равномерная сетка, построенная методом эк ей распределения, и ошибка Е, равная относительной разности аналитического и численного решашя; (б) адаптивная сетка, построенная нейросстевым методом (КОМ), со сгущением в области интересов, имеющей вид круга, и ошибка Е.

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

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

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

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

В пункте 5 5 приводится оценка эффективности работы параллельной программы для смешанной модели SOM, реализованной с помощью библиотеки MPI Тестирование этой программы проводилось на кластере ССКЦ СО РАН, эффективность распараллеливания около 90%

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

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

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

На основе предложенных нейросетевых моделей типа SOM разработаны методы построения адаптивных сеток рассматриваемого класса для односвязных и многосвязных физических областей, а также алгоритм сглаживания

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

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

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ

Журналы из перечня ВАК

1 Нечаева О И Применение нейросетевого подхода для построения двумерных адаптивных сеток // Автометрия Том 42, №3, 2006 С 40-49

2 Нечаева О И. Сравнительный анализ нейросетевых алгоритмов кластеризации символьных последовательностей // Автометрия Том 41, №1, 2005. С 57-70

Рецензируемые издания

3 Нечаева О И Композиционный алгоритм для построения адаптивных сеток произвольной структуры // Сборник научных трудов Всероссийской научно-технической конференции Нейроинформатика-2007 Москва: МИФИ, 2007 С 72-79

4 Nechaeva О Composite Algorithm for Adaptive Mesh Construction Based on Self-Organizmg Maps // International Conference on Artificial Neural Networks (ICANN 2006) Lecture Notes m Computer Science Vol 4131 Springer Berlin/Heidelberg, 2006 P 445-454

5 Нечаева О И Композиционный алгоритм для построения адаптивных сеток на основе самоорганизующихся карт И Вестник Томского Университета № 18,2006 С 97-102

6 Нечаева О И Нейросетевой подход для построения адаптивных сеток // Сборник научных трудов Всероссийской научно-технической конференции Нейроинформатика-2006 Часть 2 Москва МИФИ, 2006. С 172-179

7 Nechaeva О Neural Network Approach for Parallel Construction of Adaptive Meshes // Parallel Computing Technologies (PaCT 2005) Lecture Notes m Computer Science Vol 3606 Berlin Springer, 2005 P 446-451

Труды конференций

8 Нечаева О И Параллельная реализация алгоритма построения адаптивных сеток методом самоорганизующихся карт // Распределенные кластерные вычисления Избранные материалы Пятой школы-семинара (Под ред В В Шайдурова) Красноярск ИВМ СО РАН, 2005 С 87-94

9 Нечаева О. И Сравнение нейросетевого метода построения адаптивных сеток с методом эквираспределения на примере решения одномерного уравнения Пуассона Н Труды конференции молодых учёных ИВМиМГ Новосибирск, 2005 С 142-154

10 Нечаева О И Последовательный и параллельный алгоритмы кластеризации символьных последовательностей // Материалы 2-й сибирской школы-семинара по параллельным вычислениям Томск, 16-19 дек 2003 Изд-во Том. ун-та, 2004 С. 80-85

11 Нечаева О И Применение самоорганизующихся карт Кохонена (SOM) для построения адаптивных сеток // Труды конференции молодых учбных ИВМиМГ Новосибирск, 2004 С 140-147

Тезисы

12 Нечаева О. И. Вычислительные свойства нейросетевого метода построения адаптивных сеток // Нейроинформатика и ее приложения. Материалы XIII Всероссийского семинара Красноярск, ИВМ СО РАН, 2005 С 65-66

13 Нечаева О И Построение адаптивных криволинейных сеток на двумерной выпуклой области с помощью самоорганизующихся карт Кохонена // Нейроинформатика и eè приложения Материалы XII Всероссийского семинара. Красноярск, ИВМ СО РАН, 2004 С 101-102

14 Нечаева О И. Построение адаптивных сеток с помощью самоорганизующихся карт Кохонена // Материалы XLIII Международной научной студенческой конференции «Студент и научно-технический прогресс» Математика Новосибирск, Новосиб гос ун-т, 2005 С 187

15 Нечаева О И Применение самоорганизующихся карт Кохонена для построения адаптивных сеток // Материалы XLII Международной научной студенческой конференции «Студент и научно-технический прогресс» Информационные технологии Новосибирск, Новосиб гос ун-т, 2004 С 216

Нечаева Ольга Игоревна

НЕЙРОСЕТЕВЫЕ МОДЕЛИ, АЛГОРИТМЫ И КОМПЛЕКС ПРОГРАММ ДЛЯ ПОСТРОЕНИЯ АДАПТИВНЫХ СЕТОК

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

Лицензия ИД № 02202 от 30 июня 2000 г Подписано в печать 23 07 2007

Формат 60 х 84 1 / 16 Объем 1 п л, 1 уч изд л Тираж 100 экз_Заказ № 102._

Отпечатано в ООО «Омега Принт» 630090, Новосибирск, пр Ак Лаврентьева, 6

Введение.

Глава 1. Самоорганизующиеся карты Кохонена как модель для построения адаптивных сеток.

1.1.Самоорганизующиеся карты КоХонена (SOM).

1.2. Обзор традиционных методов построения адаптивных сеток.

1.3.Свойства нейросетевой модели Кохонена для решения проблем методов построения сеток.

1.4.Постановка задачи построения адаптивных сеток.

Глава 2. Использование базовой модели SOM.

2.1.Интерпретация элементов базовой модели SOM.

2.2.Выбор коэффициента обучения.

2.3.Теорема о соответствии.

2.4.Проблемы, возникающие при применении базовой модели SOM к построению адаптивных сеток.

2.4.1. Граничный эффект.

2.4.2. Мертвые нейроны.

2.4.3. Нарушения условия сохранения топологии.

2.4.4. Гладкость сеток, полученных с помощью модели SOM.

Глава 3. Нейросетевые модели типа SOM и алгоритмы для построения адаптивных сеток.

3.1.Модификации базовой модели SOM.

3.1.1. Модель SOM с необучаемыми нейронами.

3.1.2. Раскрашенная модель SOM.

3.1.3. Смешанная модель SOM.

3.2.Композиционная модель SOM.

3.3.Примеры использования композиционной модели SOM для построения адаптивных сеток.

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

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

3.4.Параллельный алгоритм.

3.5.Алгоритм сглаживания.

Глава 4. Оценка качества построенных сеток.

4.1 .Описание метода эквираспределения.

4.2. Оценка качества сеток по общепринятым критериям качества.

4.3.Сравнительный анализ метода эквираспределения и нейросетевого метода на примере решения одномерного уравнения Пуассона.

4.4.Сравнительный анализ метода эквираспределения и нейросетевого метода на примере решения двумерного уравнения Пуассона.

Глава 5. Комплекс программ для построения адаптивных сеток.

5.1. Основные модули.

5.2.Представление данных.

5.3.Генерация случайной точки.

5.4.Последовательная реализация комплекса программ.

5.4.1. Параметры алгоритмов.

5.4.2. Интерактивная работа с сеткой.

5.4.3. Задание функций раскраски и элементов композиционной модели SOM.

5.5.Особенности параллельной реализации и эффективность распараллеливания.

Построение адаптивных сеток является одной из актуальных областей научных исследований, которая привлекает в настоящее время многих исследователей. Адаптивные сетки, являясь дискретной моделью пространственной области, получили важнейшие применения при решении сложных задач численного моделирования [1]. Кроме того, они широко используются при обработке изображений [2], визуализации данных [3], в графических приложениях [4] и т.д.

Причиной использования адаптивных сеток в задачах численного моделирования является желание повысить точность приближенного решения задачи без существенного увеличения числа узлов. Среди всех методов построения адаптивных сеток можно выделить важный класс методов, в котором адаптивные сетки получаются в результате отображения некоторой вычислительной области на физическую, переводящего зафиксированную, обычно равномерную, сетку в адаптивную с заданным распределением плотности. К методам этого класса относятся такие традиционные методы построения адаптивных сеток, как метод эквираспределения [5], метод Томпсона [6], эллиптический метод [7] и т.д. Для получения качественных адаптивных сеток все эти методы, а также алгебраические методы [8] и методы конформных отображений [9], в конечном счете требуют решения сложных систем нелинейных дифференциальных уравнений (ДУ) с частными производными. Необходимость решения ДУ, сложность которых существенно возрастает с увеличением размерности пространства, накладывает ряд ограничений на возможности этих методов. В частности, для обеспечения их сходимости требуется жесткий контроль над способами задания физической области и функции плотности сетки, над свойствами граничных и начальных данных, особенно в случае сложных многосвязных областей. Это также зачастую приводит к проблемам при попытках автоматизации работы с этими методами и их эффективного распараллеливания.

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

Диссертация посвящена разработке новых нейросетевых моделей, основанных на самоорганизующихся картах Кохонена (Self-Organizing Maps, SOM) [10], которые не только расширяют возможности использования модели SOM, но и предоставляют эффективные и автоматизированные методы для построения адаптивных сеток рассматриваемого класса. Модель SOM впервые была предложена Т. Кохоненом в 1984 г., и в настоящее время широко используется в задачах, требующих построения отображения из пространств многомерных данных на пространства меньшей размерности с сохранением топологии и отражением статистического распределения, этих данных.

Наиболее важными свойствами модели SOM являются, во-первых, ее способность строить отображения произвольной размерности на основе самоорганизации и методов теории вероятностей и, во-вторых, наличие у нее внутреннего параллелизма, как у представителя нейронных сетей. Однако при использовании базовой модели SOM возникает ряд проблем, упоминающихся во многих источниках [10-12], к числу которых относятся граничный эффект, наличие «мертвых» нейронов и нарушение сохранения топологии при отображении. Эти проблемы ограничивают возможности применения модели SOM, в том числе и для построения адаптивных сеток. После анализа перечисленных проблем модели SOM, было установлено, что граничный эффект приводит к неплотному прилеганию сетки к границе физической области, «мертвые» нейроны появляются при выходе узлов сетки за границу области, а нарушение сохранения топологии приводит к вырожденности сетки. Поэтому в настоящей диссертации ставится з&дача разработки новых нейросетевых моделей типа SOM, которые, с одной стороны, позволили бы решить, хотя бы частично, проблемы базовой модели SOM, а с другой - сохранили бы все ее важные свойства. Обладая этими свойствами новые модели должны позволить решить проблемы автоматизации и эффективного распараллеливания построения адаптивных сеток, а также снять ограничения на начальные, граничные данные и функцию плотности сетки, которые характерны для традиционных методов, основанных на решении нелинейных ДУ.

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

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

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

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

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

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

Для обеспечения хорошего качества адаптивных сеток, во-первых, была поставлена задача выработки стратегии выбора параметров обучения, которые влияют также на скорость построения сеток. Во-вторых, требовалось разработать алгоритм сглаживания адаптивных сеток. Для того, чтобы не нарушались свойства предлагаемых методов, алгоритм сглаживания должен использовать правило обучения такого же вида, ^то и все разработанные нейросетевые модели типа SOM. Для оценки качества получающихся адаптивных сеток используются общепринятые критерии качества для конечно-разностных сеток [15]. Окончательная характеристика адаптивных сеток дается после оценки точности численного решения конкретной задачи на этих сетках, а также проводится сравнение с методом эквираспределения [5].

Использование нейросетевых технологий самоорганизации и предложенный принцип композиции нескольких нейросетевых моделей имеют перспективы, так как на их основе могут быть разработаны другие эффективные методы, основанные на самоорганизации. К числу таких методов могут относиться (1) методы построения движущихся адаптивных сеток [16], для которых особенно важным является свойство внутреннего параллелизма из-за необходимости постоянной подстройки сетки; (2) методы построения неструктурированных сеток на сложных областях, основанных на композиции нейросетевых моделей растущего нейронного газа (Growing Neural Gas) [17]. Цель работы

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

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

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

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

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

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

5. Провести экспериментальное исследование методов и оценить качество получающихся адаптивных сеток по общепринятым критериям качества.

6. Провести сравнение с методом эквираспределения по критериям качества и на основе оценки точности решения задач на сбтках, построенных обоими методами.

Новизна

1. Предложены три новые нейросетевые модели типа SOM: модель SOM с необучаемыми нейронами, раскрашенная модель SOM и смешанная модель SOM, а также композиционная модель SOM, которые во-первых, решают ряд проблем использования базовой модели &ОМ, предложенной Кохоненом, а во-вторых, позволяют получать адаптивные сетки, удовлетворяющие общепринятым критериям качества.

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

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

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

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

При выполнении работы использовались методы теории нейронных сетей, методы теории обучения, аппарат теории вероятностей и математической статистики, методы Монте-Карло. При исследовании качества сеток и сравнения предлагаемого метода с традиционными использовались методы вычислительной математики, методы построения адаптивных сеток на основе решения нелинейных ДУ, методы оценки качества адаптивных сеток. Для экспериментального исследования предлагаемых алгоритмов была выполнена их программная реализации в среде Visual С++ с использованием библиотеки MFC, а также библиотеки параллельного программирования MPI. Апробация работы

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

- Всероссийской научно-технической конференции Нейроинформатика-2006.

- Международная конференция по искусственным нейронным сетям, ICANN 2006, Афины, Греция

- Международная конференция Parallel Computing Technologies, РаСТ ^005.

- Пятая школа-семинар «Распределенные кластерные вычисления», Красноярск, 2005.

- Конференция молодых учёных ИВМиМГ, Новосибирск, 2004 и 2005.

- Вторая сибирская школа-семинар по параллельным вычислениям. Трмск, 16-19 дек. 2003.

- Всероссийский семинар «Нейроинформатика и её приложения», ИВМ СО РАН, Красноярск, 2003, 2004 и 2005.

- Международная научная студенческая конференция "Студент и научно-технический прогресс", НГУ, Новосибирск, 2005 и 2004.

- Международный семинар «Вычислительные методы и решение оптимизационных задач», Киргизия, оз. Иссык-Куль, 2004.

- Семинары Математическое и архитектурное обеспечение параллельных вычислений ИВМиМГ СО РАН (3 доклада), Информационно вычислительные технологии ИВТ СО РАН (2 доклада), Математика в приложениях ИМ СО РАН (1 доклад), Системное программирование ИСИ СО РАН (1 доклад).

Достоверность

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

Публикации )

Основное содержание диссертации отражено в 15 печатных работах. Среди них 7 работ в рецензируемых изданиях, в их числе 2 работы в журналах из перечня ВАК, 4 работы в трудах конференций и 4 тезиса в материалах конференций.

Финансовая поддержка работы

Работа была отмечена премией на конференции Молодых ученых ИВМиМГ СО РАН в 2005 г. и дважды поощрена стипендиями Intel Scholarship Grant в 2005 и 2006 г. Также работа была поддержана грантами по программе фундаментальных исследований №17 Президиума РАН (20042007) и программе Рособразования «Развитие научного потенциала ВШ», проект РНП.2.2.1.1.3653 (2006-2007), European Neural Network Society Travel

Grant для участия в международной конференции ICANN 2006, Афины, Греция и IEEE Computational Intelligence Society Travel Grant для участия в международной конференции IJCNN 2007, Орландо, США. I

Личный вклад соискателя

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

Структура диссертации

Диссертация состоит из 5 глав. В первой главе дается обзор областей применения самоорганизующихся карт Кохонена, а также традиционных методов построения адаптивных сеток. Обозначается круг проблем, которые требуется решить путем разработки новых нейросетевых моделей. Приводится постановка задачи построения адаптивных сеток. Вторая глава посвящена анализу базовой модели SOM. В этой главе предлагается интерпретация элементов модели SOM и алгоритма ее обучения в терминах сеточной постановки задачи. Предлагается стратегия выбора коэффициента обучения. Доказывается теорема о соответствии, которая показывает, что достижение цели обучения базовой модели SOM ведет к выполнению аналога принципа эквираспределения относительно ячеек Вороного для получающейся сетки. Подробно рассматриваются проблемы базовой модели SOM и их значение для адаптивных сеток. В третьей главе предлагаются четыре нейросетевые модели и алгоритмы их обучения, а также их I использование в некоторых частных случаях: для односвязных и многосвязных областей. Предлагается алгоритм сглаживания. Четвертая глава посвящена оценке качества получающихся сеток. Для этого приводится описание метода эквираспределения, с которым будет проводиться сравнение, а также формулы некоторых общепринятых критериев качества. Оценка качества сеток проводится в сравнении с методом эквираспределения по приведенным критериям качества, а также по точности решения 1D и 2D уравнения Пуассона на сетках построенных обоими методами. В пятой главе дается описание реализованного комплекса программ для построения I адаптивных сеток с использованием разработанных нейросетевых моделей. Приводится последовательная и параллельная реализации алгоритмов. .

Выводы из главы 5 I

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

Заключение

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

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

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

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

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

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

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

1. Лебедев А.С., Лисейкин В.Д., Хакимзянов Г.С. Разработка методов построения адаптивных сеток. // Вычислительные технологии. Том 7, №3, 2002. с. 29

2. Brankov J.G., Yang Y., Galatsanos N.P. Image restoration using cojitent-adaptive mesh modeling. // ICIP 03, Vol. II, 2003, pp. 997-1000

3. Hu W., Yang W., Xiong Y. An adaptive mesh model for 3D reconstruction from unorganized data points // The International Journal of Advanced Manufacturing Technology, Springer London, Springer London, Vol. 26, No. 11-12, pp. 13621369

4. Хакимзянов Г.С., Шокин Ю.И., Барахнин В.Б., Шокина Н.Ю. Численное моделирование течений жидкости с поверхностными волнами // Новосибирск: Изд-во СО РАН, 2001,394 с.

5. Thompson J.F., Warsi Z.U.A., Mastin C.W. Numerical grid generation, foundations and applications // Amsterdam: North-Holland. 1985.

6. Лисейкин В.Д., Лебедев A.C., Китаева И.А. Универсальный эллиптический метод построения разностных сеток // Новосибирск: НГУ, 2004.266 с. '

7. Gordon W.J., Thiel L.C. Transfinite mappings and their applications to grid generation. // Numerical Grid Generation, Appl. Mathematics and Computation, vol. 2/3,1982. p. 171-192.

8. Годунов С.К., Прокопов Г.П. О расчетах конформных отображений и построении разносных сеток // Журн. вычисл. математики и мат. физики. Т.7. 1967. С. 1031-1059

9. Kohonen Т. Self-organizing Maps // Springer Series in Information Sciences, V.30, Springer, Berlin, Heidelberg, New York, 2001, 501 p.

10. Wu Y., Takatsuka M. The Geodesic Self-Organizing Map and its error analysis

11. ACM International Conference Proceeding Series. Proceedings of the Twentyieighth Australasian conference on Computer Science, Vol. 38, Australian Computer Society, Inc., Darlinghurst, Australia, 2005, pp. 343 351

12. Villman Т., Der R., Hermann M., Martinetz Т. M. Topology preservation in self-organizing maps: exact definition and measurement // IEEE Transactions on Neural Networks, 8, 1997, pp. 256-266

13. Manevitz L., Yousef M.s Givoli D. Finite Element Mesh Generation Using Self-Organizing Neural Networks // Special Issue on Machine Learning of Microcomputers in Civil Engineering, Vol. 12, No. 4,1997, pp. 233-250i

14. Lowther D.A., Mai W. On automatic mesh generation using Kohonen maps // IEEE transactions on magnetics, 34(5), 1998, pp. 3391-3394

15. Прокопов Г.П. Об организации сравнения алгоритмов и программ построения регулярных двумерных разностных сеток // Москва, 1989. 27 с. (Препринт / ИПМ им. Келдыша АН СССР; № 18).

16. Nechaeva О., Bessmeltsev М. Parallel Construction of Moving Adaptive Meshes Based on Self-Organization // Accepted for publication in PaCT 2007 proc., Lecture Notes in Computer Science, Vol. 4671. Berlin: Springer, )2007, pp. 591-600

17. Bohn Ch.-A. Finite Element Mesh Generation using Growing Cell Structures Networks // Neural Networks in Engineering Systems, Turku, Finland, 1997. pp. 241-244.

18. Ritter H., Martinets Т., Schulten K. Neural Computation and Self-Organizing Maps: An Introduction // New York: Addison-Wesley, 1992.

19. Das A. Cortical Maps: Where Theory Meets Experiments // Neuron^ Vol. 47, Issue 2,2005, pp. 168-171

20. Polzlbauer G., Rauber A., Dittenbach M. Graph projection techniques for Self

21. Organizing Maps // Proceedings of the European Symposium on Artificial Neurali

22. Networks (ESANN'05), Bruges, Belgium, 2005, pp. 533-538

23. Fritzke B. Some competitive learning methods // Technical report, Systems Biophysics, Inst, for Neural Сотр., Ruhr-Universitat Bochum, April 1997

24. Flexer A. On the Use of Self-Organizing Maps for Clustering and Visualization // Principles of Data Mining and Knowledge Discovery, 1999, pp. 80-88.

25. Нечаева О. И. Сравнительный анализ нейросетевых алгоритмов кластеризации символьных последовательностей // Автометрия. Том 41, №1, 2005. С. 57-70 /

26. Ong J. Data Mining Using Self-Organizing Kohonen Maps: A Technique for Effective Data Clustering & Visualisation // International Conference on Artificial Intelligence (IC-AI'99), June 28-July 1, 1999, Las Vegas.

27. Mao J., Kraaijveld M. A., Jain A. K. A nonlinear projection method based on Kohonen's topology preserving maps // IEEE Transactions on Neural Networks, 6(3):548-559, May 1995.

28. Hammer В., Micheli A., Neubauer N., Sperduti A., Strickert M. Selfi

29. Organizing Maps for Time Series // Proceedings of WSOM 2005, Paris, France, pp. 115-122

30. Wang S. Application of self-organizing maps for data mining with incomplete data sets // Neural Computing & Applications, Springer London, Vol. 12, No. 1, 2004, pp. 42-48

31. Ntirnberger A., Klose A., Kruse R. Self-organizing maps for interactive Search in document databases // Studies In Fuzziness And Soft Computing, Physica-Verlag GmbH, Heidelberg, Germany, 2003, pp. 119 -135

32. Kasslin M., Kangas J., Simula O. Process state monitoring using self-organizing maps //1. Aleksander and J. Taylor, editors, Artificial Neural Networks, 2, vol. II,, Amsterdam, Netherlands, 1992. pp. 1531-1534.

33. Dar Ren Chen, Ruey Feng Chang, Yu Len Huang. Breast cancer diagnosis using Self-organizing Map for sonography // Ultrasound in Medicine and Biology, Vol. 26,2000, pp. 405-411 '

34. Joutsensalo J. Nonlinear data compression and representation by combining self-organizing map and subspace rule // Neural Networks, IEEE World Congress on Computational Intelligence, Digital Object Identifier, Vol. 2, No. 27, 1994, pp. 637-640.

35. Koutnik J., Mazl R., Kulich M. Building of 3d environment models for mobile robotics using self-organization // In Proc, of The 9th International Conference on Parallel Problem Solving From Nature PPSN-IX, Springer, 2006, pp. 721-730.115 ,

36. Bern M., Plassmann P. Mesh Generation // Chapter 6 in Handbook of Computational Geometry. J.-R. Sack and J. Urrutia, eds., Elsevier Science, 1999.

37. Cao W., Huang W., Russell R.D. Approaches for generating moving adaptive meshes: location versus velocity // Applied Numerical Mathematics, Vol. 47,2003. pp. 121-138

38. Годунов C.K., Прокопов Г.П. Об использовании подвижных се^ок в газодинамических расчетах // Журн. вычисл. математики и мат. физики. -1972. -Т.12. С. 429-440.

39. Liseikin V.D. Grid Generation Methods // Springer-Verlag, Berlin 1999. 362p.

40. Флетчер К. Вычислительные методы в динамике жидкостей // М:Мир, т.2, 1991,552с.

41. Smith R.E. Algebraic Grid Generation // Numerical Grid Generation (ed. by J.F.Thompson). New York, North-Holland, 1982, pp. 137-170.

42. Eisemann P.R. A multi-surface method of coordinate generation // J. Of Сотр. Phys., vol.33, N1, 1979, pp.118-150.

43. Eisemann P.R. Coordinate generation with precise controls over'nesh properties // J. of Сотр. Phys., vol.47, N3, 1982, pp.331-351.

44. Eriksson L.E. Generation of boundary-conforming grids around wing-body configurations using transfinite interpolation // AIAA J., vol.20, N10, pp.13131320.

45. Годунов С.К., Роменский Е.И., Чумаков Г.А. Построение сеток в сложных областях при помощи квазиконформных отображений // Труды ИМ СО РАН, Новосибирск: Наука, 1990. Т.18. - С.75-84

46. Хэлси Н.Д. Использование конформных отображений при построении сеток для расчета обтекания трехмерных аэродинамических компоновок сложной формы//АКТ, N11,1988, с.11-18.

47. Ryskin G., Leal L.G. Orthogonal mapping // J. of Сотр. Phys., vol.50, N1, 1983, pp.71-100. ,

48. Nakamura S. Marching grid generation using parabolic partial differential equations // Numerical Grid Generation (ed. by J.F.Thompson). New York, North-Holland, 1982, pp.775--786.

49. Thompson J.F. Elliptic grid generation // Numerical Grid Generation (ed. by J.F.Thompson), New York, North-Holland, 1982, pp.79-106.

50. Nechaeva O. Neural Network Approach for Parallel Construction of Adaptive Meshes //Parallel Computing Technologies 2005. Lecture Notes in Computer Science, Vol. 3606. Springer, Berlin Heidelberg (2005) 446-451 '

51. Нечаева О. И. Применение самоорганизующихся карт Кохонена (SOM) для построения адаптивных сеток // Труды конференции молодых учёных ИВМиМГ. Новосибирск, 2004. С. 140-147

52. Нечаева О. И. Нейросетевой подход для построения адаптивных сеток // Сборник научных трудов Всероссийской научно-технической конференции Нейроинформатика-2006: Часть 2. Москва: МИФИ, 2006. С. 172-179

53. Нечаева О. И. Применение нейросетевого подхода для построения двумерных адаптивных сеток // Автометрия. Том 42, №3, 2006. С. 40-49

54. Нечаева О. И. Построение адаптивных сеток с помощью самоорганизующихся карт Кохонена // Материалы XLIII Международной117научной студенческой конференции «Студент и научно-технический прогресс»: Математика. Новосибирск, Новосиб. гос. ун-т, 2005. С. 187

55. Ghahramani, Z. Unsupervised Learning. // Bousquet О. et al. (eds.): Machine Learning 2003. Lecture Notes in Artificial Intelligence, vol. 3176, Springer-Verlag, Berlin Heidelberg, 2004. p. 72-112

56. Okabe A., Boots В., Sugihara K., Sung Nok Chiu. Spatial Tessellationst

57. Concepts and Applications of Voronoi Diagrams // 2nd edition. John Wiley, 2000, 671 p.

58. Михайлов H. А., Войтишек А. В. Численное статистическое моделирование. Методы Монте-Карло // Изд-во Academia, 2006,368 с.

59. Sullivan Т. J., de Sa V. R. A self-organizing map with homeostatic synaptic scaling // Neurocomputing, 69,2006. pp. 1183-1186

60. Ritter H. Self-Organizing Maps on non-euclidean Spaces // Kohonen Maps, Elsevier, Amsterdam, 1999, pp. 97-110 '

61. Сивохин А. В. Искусственные нейронные сети: Лаб. практикум // Пенза: Изд-во Пенз. гос. ун-та, 2004. 136 с.

62. Rumelhart D. Е., Zipser D. Feature discovery by competitive learning // Cognitive Sci., vol. 9, 1985, pp. 75-112

63. Нечаева О. И. Построение адаптивных криволинейных сеток на двумерной выпуклой области с помощью самоорганизующихся карт Кохонена // Нейроинформатика и её приложения: Материалы XIII

64. Всероссийского семинара. Красноярск, ИВМ СО РАН, 2004. С. 101-102118

65. Nechaeva О. Composition of Self Organizing Maps for Adaptive Mesh Construction on Complex-shaped Domains // Proc. of 6th Int. Workshop on Self-Organizing Maps (WSOM 2007), Bielefeld, Germany, September 3-6, 2007, in press.

66. Нечаева О. И. Композиционный алгоритм для построения адаптивных сеток произвольной структуры // Сборник научных трудов Всероссийской научно-технической конференции Нейроинформатика-2007. Москва: МИФИ, 2007. С. 72-79

67. Нечаева О. И. Композиционный алгоритм для построения адаптивных сеток на основе самоорганизующихся карт // Вестник Томского Университета. № 18,2006. С. 97-102

68. Большая Советская Энциклопедия // 3-е издание, изд-во Советская Энциклопедия, 1978 г. '

69. Nechaeva О. The Neural Network Approach to Automatic Construction of Adaptive Meshes on Multiply-connected Domains // Proc. of International Joint Conference on Neural Networks (IJCNN 2007), Orlando, Florida, USA, August 12-17,2007, in press

70. Самарский А.А., Гулин А.В. Численные методы математической физики // 2е изд. Научный мир, 2003, 316 с.

71. Нечаева О. И. Сравнение нейросетевого метода построения адаптивных сеток с методом эквираспределения на примере решения одномерного уравнения Пуассона // Труды конференции молодых учёных ИВМиМГ. Новосибирск, 2005. С. 142-154

72. Круглински Д., Уингоу С., Шеферд Дж. Программирование на Microsoft Visual С++ 6.0 для профессионалов // СПб.: Питер, 2002.

73. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.