Содержание к диссертации
Введение
Глава 1. Самоорганизующиеся карты Кохонена как модель для построения адаптивных сеток 15
1.1.Самоорганизующиеся карты Кохонена (SOM) 15
1.2. Обзор традиционных методов построения адаптивных сеток 19
1.3.Свойства нейросетевой модели Кохонена для решения проблем методов построения сеток 25
1 АПостановка задачи построения адаптивных сеток 26
Глава 2. Использование базовой модели SOM 30
2.1.Интерпретация элементов базовой модели SOM 30
2.2.Выбор коэффициента обучения 33
2.3.Теорема о соответствии 40
2.4. Проблемы, возникающие при применении базовой модели SOM к построению адаптивных сеток 43
2.4.1. Граничный эффект 43
2.4.2. Мертвые нейроны 45
2.4.3. Нарушения условия сохранения топологии 47
2.4.4. Гладкость сеток, полученных с помощью модели SOM 50
Глава 3. Нейросетевые модели типа SOM и алгоритмы для построения адаптивных сеток 52
3.1.Модификации базовой модели SOM 53
3.1.1. Модель SOM с необучаемыми нейронами 53
3.1.2. Раскрашенная модель SOM 56
3.1.3. Смешанная модель SOM 57
3.2.Композиционная модель SOM 58
3.3. Примеры использования композиционной модели SOM для построения адаптивных сеток 62
3.3.1. Пример использования композиционной модели SOM для построения адаптивных сеток на односвязных областях 62
3.3.2. Пример использования композиционной модели SOM для построения адаптивных сеток на многосвязных областях 64
3.4.Параллельный алгоритм 68
3.5.Алгоритм сглаживания 70
Глава 4. Оценка качества построенных сеток 76
4.1. Описание метода эквираспределения 76
4.2. Оценка качества сеток по общепринятым критериям качества 78
4.3. Сравнительный анализ метода эквираспределения и нейросетевого метода на примере решения одномерного уравнения Пуассона 83
4.4.Сравнительный анализ метода эквираспределения и нейросетевого метода на примере решения двумерного уравнения Пуассона 88
Глава 5. Комплекс программ для построения адаптивных сеток 93
5.1. Основные модули 93
5.2.Представление данных 94
5.3.Генерация случайной точки 96
5.4.Последовательная реализация комплекса программ 100
5.4.1. Параметры алгоритмов 100
5.4.2. Интерактивная работа с сеткой 103
5.4.3. Задание функций раскраски и элементов композиционной модели SOM 105
5.5.Особенности параллельной реализации и эффективность распараллеливания 106
Заключение
Литература 1І2
- Обзор традиционных методов построения адаптивных сеток
- Проблемы, возникающие при применении базовой модели SOM к построению адаптивных сеток
- Примеры использования композиционной модели SOM для построения адаптивных сеток
- Сравнительный анализ метода эквираспределения и нейросетевого метода на примере решения одномерного уравнения Пуассона
Введение к работе
Построение адаптивных сеток является одной из актуальных областей научных исследований, которая привлекает в настоящее время многих исследователей. Адаптивные сетки, являясь дискретной моделью пространственной области, получили важнейшие применения при решении сложных задач численного моделирования [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, объединяющая в себе свойства моделей (В) и
(С); (D) композиционная модель SOM, состоящая из набора смешанных моделей (ВС) различной размерности, которые взаимодействуют в процессе самоорганизации. Каждая из смешанных моделей, входящая в композиционную модель SOM, самоорганизуется на заданном ей множестве данных, которое, как правило, описывает границу или внутренность физической области. Для обеспечения правильной работы композиционной модели, стояла задача разработать такой алгоритм ее обучения, при котором все элементы композиции работают согласованно между собой. Согласование смешанных моделей SOM при поочередном их обучении в рамках композиционной модели основано на том, что на этапе обучения одной смешанной модели нейроны граничащих с ней моделей рассматриваются как необучаемые.
Предлагаемые нейросетевые модели типа SOM и композиционная модель SOM позволяют создать эффективные методы построения адаптивных сеток на односвязных и многосвязных физических областях. В отличие от традиционных методов, в которых для каждой размерности области и пространства требуются свои ДУ и алгоритмы, предлагаемые методы универсальны относительно этих размерностей, т.е. используют алгоритмы, в которых размерности являются лишь параметром. Лежащие в основе модели принципы самоорганизации позволяют использовать произвольные начальные данные при построении сеток и не требуют предварительной фиксации узлов сетки на границе области, т.к. граничные узлы могут расставляться автоматически в течение итерационного процесса построения сетки. Стохастическая природа алгоритмов позволяет снять ограничения на функцию плотности сетки и использовать различные представления исходных данных, в том числе частично заданных.
Кроме того, при построении адаптивных сеток на многосвязных областях возможно использовать свойства самоорганизации для автоматического определения расположения вырезов в сетке, зафиксированной в вычислительной области, которые должны натянуться на
соответствующие дыры в физической области. Отсутствие автоматизированного способа определения вырезов обычно ведет к большому количеству ручной работы особенно в случае произвольной области с неравномерной функцией плотности.
Еще одним важным преимуществом данного подхода является наличие внутреннего параллелизма в алгоритмах [10]. Поскольку все узлы при построении сетки обрабатываются по одному и тому же правилу независимо друг от друга, то эффективность распараллеливания предлагаемых методов не зависит от способа распределения узлов сетки по процессорам. Поэтому имеется возможность распараллеливать эти методы в соответствии с теми требованиями, которые налагаются на параллельное решение задачи на строящейся сетке.
Для обеспечения хорошего качества адаптивных сеток, во-первых, была поставлена задача выработки стратегии выбора параметров обучения, которые влияют также на скорость построения сеток. Во-вторых, требовалось разработать алгоритм сглаживания адаптивных сеток. Для того, чтобы не нарушались свойства предлагаемых методов, алгоритм сглаживания должен использовать правило обучения такого же вида, что и все разработанные нейросетевые модели типа SOM. Для оценки качества получающихся адаптивных сеток используются общепринятые критерии качества для конечно-разностных сеток [15]. Окончательная характеристика адаптивных сеток дается после оценки точности численного решения конкретной задачи на этих сетках, а также проводится сравнение с методом эквираспределения [5].
Использование нейросетевых технологий самоорганизации и предложенный принцип композиции нескольких нейросетевых моделей имеют перспективы, так как на их основе могут быть разработаны другие эффективные методы, основанные на самоорганизации. К числу таких методов могут относиться (1) методы построения движущихся адаптивных сеток [16], для которых особенно важным является свойство внутреннего
параллелизма из-за необходимости постоянной подстройки сетки; (2) методы построения неструктурированных сеток на сложных областях, основанных на композиции нейросетевых моделей растущего нейронного газа (Growing Neural Gas) [17]. Цель работы
Целью работы является разработка нейросетевых моделей типа SOM, алгоритмов и программного комплекса, предназначенных для построения адаптивных сеток на односвязных и многосвязных физических областях и допускающих эффективное распараллеливание и автоматизацию.
Для достижения поставленной цели необходимо решить следующие задачи.
Разработать нейросетевые модели типа SOM и композиционную модель SOM, которые решают следующие проблемы использования базовой модели SOM, предложенной Кохоненом: граничный эффект, появление «мертвых» нейронов и нарушение сохранения топологии при отображении.
Показать, что достижение цели обучения базовой модели SOM ведет к требуемому сгущению сетки, в частности к выполнению аналога принципа эквираспределения относительно ячеек Вороного для получающейся сетки.
Разработать методы, последовательные и параллельные алгоритмы для построения адаптивных сеток на основе предложенных нейросетевых моделей для односвязных и многосвязных физических областей, а также алгоритм сглаживания.
Разработать и реализовать комплекс программ для построения адаптивных сеток с возможностью интерактивной работы с сетками и контролем их качества.
Провести экспериментальное исследование методов и оценить качество получающихся адаптивных сеток по общепринятым критериям качества.
Провести сравнение с методом эквираспределения по критериям качества и на основе оценки точности решения задач на сетках, построенных обоими методами.
Новизна
Предложены три новые нейросетевые модели типа SOM: модель SOM с необучаемыми нейронами, раскрашенная модель SOM и смешанная модель SOM, а также композиционная модель SOM, которые во-первых, решают ряд проблем использования базовой модели &ОМ, предложенной Кохоненом, а во-вторых, позволяют получать адаптивные сетки, удовлетворяющие общепринятым критериям качества.
Предложена стратегия выбора параметров обучения для базовой модели SOM, разработанных нейросетевых моделей типа SOM и композиционной модели SOM. Доказано, что при достижении цели алгоритма обучения для базовой модели SOM выполняется аналог принципа эквираспределения относительно ячеек Вороного для получающихся адаптивных сеток. '
На основе предложенных нейросетевых моделей разработаны методы построения адаптивных сеток рассматриваемого класса для односвязных и многосвязных физических областей, а также алгоритм сглаживания.
Реализованный программный комплекс является первым прототипом программного приложения для построения адаптивных сеток рассматриваемого класса на основе нейросетевых моделей типа SOM. Практическая ценность
Предложенные нейросетевые модели могут использоваться как1 при построении адаптивных сеток для сложных задач численного моделирования, так и для задач, в которых базовая модель SOM не всегда может обеспечить приемлемого качества решения: визуализация многомерных данных, нелинейное проектирование, классификация, поиск информации, сжатие данных, обработка изображений и др. Разработанные на основе предложенных нейросетевых моделей методы построения адаптивных сеток могут быть применены при необходимости автоматизированного построения сеток. В особенности рекомендуется
использовать предложенные методы в случае, если функции плотности сеток и физические области произвольны или частично заданы и не обладают свойствами, гарантирующими успешную работу традиционных методов, а также при отсутствии специально заданных начальных данных и граничного распределения узлов сетки. Внутренний параллелизм алгоритмов позволяет эффективно их использовать при параллельном решении задач большого размера на многопроцессорных вычислительных системах.
Методы исследований
При выполнении работы использовались методы теории нейронных сетей, методы теории обучения, аппарат теории вероятностей и математической статистики, методы Монте-Карло. При исследовании качества сеток и сравнения предлагаемого метода с традиционными использовались методы вычислительной математики, методы построения адаптивных сеток на основе решения нелинейных ДУ, методы оценки качества адаптивных сеток. Для экспериментального исследования предлагаемых алгоритмов была выполнена их программная реализации в среде Visual C++ с использованием библиотеки 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 Президиума РАН (2004-2007) и программе Рособразования «Развитие научного потенциала ВШ», проект РНП.2.2.1.1.3653 (2006-2007), European Neural Network Society Travel
Grant для участия в международной конференции ICANN 2006, Афины, Греция и IEEE Computational Intelligence Society Travel Grant для участия в
международной конференции IJCNN 2007, Орландо, США.
і Личный вклад соискателя
Все научные результаты были получены лично соискателем, все публикации без соавторов.
Структура диссертации
Диссертация состоит из 5 глав. В первой главе дается обзор областей применения самоорганизующихся карт Кохонена, а также традиционных методов построения адаптивных сеток. Обозначается круг проблем, которые требуется решить путем разработки новых нейросетевых моделей. Приводится постановка задачи построения адаптивных сеток. Вторая глава посвящена анализу базовой модели SOM. В этой главе предлагается интерпретация элементов модели SOM и алгоритма ее обучения в терминах сеточной постановки задачи. Предлагается стратегия выбора коэффициента обучения. Доказывается теорема о соответствии, которая показывает, что достижение цели обучения базовой модели SOM ведет к выполнению аналога принципа эквираспределения относительно ячеек Вороного для получающейся сетки. Подробно рассматриваются проблемы базовой модели SOM и их значение для адаптивных сеток. В третьей главе предлагаются четыре нейросетевые модели и алгоритмы их обучения, а также их использование в некоторых частных случаях: для односвязных и многосвязных областей. Предлагается алгоритм сглаживания. Четвертая глава посвящена оценке качества получающихся сеток. Для этого приводится описание метода эквираспределения, с которым будет проводиться сравнение, а также формулы некоторых общепринятых критериев качества. Оценка качества сеток проводится в сравнении с методом эквираспределения по приведенным критериям качества, а также по точности решения ID и 2D уравнения Пуассона на сетках построенных обоими методами. В пятой главе дается описание реализованного комплекса программ для построения
адаптивных сеток с использованием разработанных нейросетевых моделей. Приводится последовательная и параллельная реализации алгоритмов. .
/
/
Обзор традиционных методов построения адаптивных сеток
Разработка методов построения адаптивных сеток для численного решения прикладных задач является актуальной проблемой вычислительной математики, привлекающей многих исследователей. Имеются многочисленные теоретические и экспериментальные результаты, показывающие преимущества использования таких сеток при решении сложных многомерных задач [5]. Однако проблема полностью не решена. До сих пор построение адаптивной сетки может иногда требовать даже больше усилий, чем само решение задачи, т.к. построение сетки трудно поддается автоматизации, по крайней мере, при использовании существующих методов. Поэтому и в настоящее время продолжаются работы по модификации известных и разработке новых методов построения адаптивных сеток [1].
Причина использования в расчетах адаптивных сеток кроется в желании повысить точность расчетов без увеличения числа узлов. Как правило, точность численного решения в подобластях сосредоточения особенностей решения существенно влияет на точность решения во всей области. Поэтому сгущением сетки в таких подобластях можно повысить точность численного решения. С другой стороны, в целях экономии машинных ресурсов желательно иметь разреженную сетку в областях плавного изменения решения [5].
Следуя [35], под сеткой в данной работе понимается разбцение физической области на конечное число подобластей простой формы (ячеек, чаще всего четырехугольники или треугольники), которое образует аппроксимацию этой области для использования ее при решении задач на этой области.
Адаптивная сетка - это неравномерная сетка, которая адаптируется к границам физической области и к априорно заданной функции плотности сетки. При этом под адаптацией к функции плотности понимается выполнение следующего условия: произведение площади ячейки сетки на значение функции плотности для соответствующей ячейки является постоянной величиной для всех ячеек. Таким образом, чем меньше ячейки сетки, т.е. чем выше плотность сетки в этих участках, тем лучше аппроксимация области.
Сетка называется статически адаптивной, если она подстраивается под физическую область и функцию плотности, которые не меняются в процессе решения задачи на этой сетке. Такие сетки используются в задачах с заранее известными особенностями решения или участками, в которых необходимо получить большее разрешение. Динамически адаптивными называются сетки, которые в процессе решения задачи подстраиваются под изменяющуюся функцию плотности или под изменяющиеся границы области. Функция плотности может меняться, например, в случае, когда подобласти сосредоточения особенностей решения подвижны [16,36,37]. Данная диссертация посвящена разработке статически адаптивных сеток, хотя предложенные идеи и принципы могут быть развиты до построения динамически адаптивных сеток.
Среди всех методов построения адаптивных сеток существует класс методов, в котором адаптивные сетки строятся путем отображения некоторой вычислительной области на физическую, переводящего зафиксированную, обычно равномерную сетку, в адаптивную с заданным распределением плотности [38]. Предлагаемые в диссертации методы построения адаптивных сеток принадлежат именно к этому классу.
Следует заметить, что условие адаптации сетки к функции плотности соотносится с принципом эквираспределения [5], который заключается в том, что произведение якобиана отображения, задающего сетку, на функцию плотности сетки должно быть постоянно. В ряде традиционных методов построения сеток из этого принципа выводятся дифференциальные уравнения для нахождения отображения [5,39].
Как правило, наличие такого отображения позволяет проводить расчеты на равномерной сетке после переписывания соответствующих уравнений в системе координат вычислительной области. Это с одной стороны упрощает вычисления, т.к. можно применить традиционные численные методы на равномерных сетках, а также использовать простые структуры данных при реализации. С другой стороны, за счет того, что в решаемые уравнения добавляются дополнительные члены - параметры преобразования, которые обычно выражаются в виде производных (якобиан) и для которых нужно проводить дискретизацию, добавляются дополнительные источники погрешности и ошибок.
В связи с этим для снижения погрешности на строящиеся адаптивные сетки налагается ряд требований, которые выражаются в критериях качества сеток [15]. Наиболее распространенными критериями являются: критерий ортогональности линий сеток (для сеток, изоморфных прямоугольным сеткам), критерии выпуклости и вытянутости ячеек сеток, критерий гладкости линий сетки. Кроме того, отображение, задающее сетку, должно быть невырожденным, т.к. сетки с наличием самопересечений, с ячейками нулевой меры или неправильной ориентации непригодны для расчетов.
Методы упомянутого класса можно разделить на три основных под класса: алгебраические методы, методы конформных отображений и дифференциальные методы. Алгебраические методы
В основе этих методов лежит решение систем алгебраических уравнений. Основная идея алгебраических методов построения сеток состоит в использовании интерполяции граничных данных для определения внутренних узлов сетки. Контроль за размещением узлов сетки осуществляется с помощью специальных функций растяжения. Широко известны следующие алгебраические методы построения сеток для двух- и трехмерных задач: метод двух границ, метод многих поверхностей, трансфинитная интерполяция [40-44]. Алгебраические методы очень эффективны с вычислительной точки зрения, однако позволяют получить качественные сетки только на достаточно простых физических областях и требуют много ручной работы, т.к. при их использовании переносятся особенности, изломы границ внутрь области, что неприемлемо для вычислений. Алгебраические методы обычно используются в качестве начальной сетки для других, более «мощных» методов. Однако при построении трехмерных сеток алгебраические методы преобладают из-за существенной сложности остальных методов.
Проблемы, возникающие при применении базовой модели SOM к построению адаптивных сеток
При достижении цели обучения в результате работы алгоритма обучения для базовой модели SOM положения узлов сетки в физической области, как правило, близки к центрам тяжести соответствующих ячеек Вороного. Поскольку ячейки Вороного - это выпуклые области, то их центры тяжести, а значит и узлы сетки, не могут оказаться на границе области. В результате, сетка, растягиваясь по области, не достигает границ физической области. Кроме того, в зависимости от величины радиуса обучения проявляется граничный эффект, вследствие которого расстояние от границы области до граничных узлов может оказаться даже больше, чем среднее расстояние между внутренними узлами сетки. Расстояние до границы тем больше, чем больше радиус обучения.
Граничный эффект возникает из-за несимметричности латеральных связей у нейронов, которые расположены близко к границе вычислительной области. Пусть qt - это внутренний нейрон, для которого расстояние до границы вычислительной области больше радиуса обучения г. В соответствии с постановкой задачи (раздел 1.4), структура рассматриваемой зафиксированной сетки QM такова, что все нейроны qj из Br{qi) располагаются симметрично относительно qh Из утверждения 2.3(B) следует, что значения весов латеральных связей rjq {qt) также располагаются симметрично относительно #/. Если при этом учитывать условие равной представимости, которое должно выполняться для карты нейронов в конечном состоянии, то на нейрон q{ с одинаковой вероятностью может быть оказано воздействие любым другим нейроном qj. В физической области это означает, что узел х,-имеет одинаковую вероятность сдвинуться симметрично во всех направлениях под влиянием нейронов из Br(q.). Так как s близко к нулю, то предполагается, что взаимное влияние между нейронами qt и q.u6r(qt) пренебрежительно мало.
Если расстояние от gt до границы вычислительной области меньше г, то в окрестности Br(q() расположено недостаточно нейронов для симметрии. В этом случае большинство нейронов в Br{qt) заставляют узел xt двигаться в основном к центру физической области. Поэтому для балансировки асимметрии, узел xt вынужден отодвигаться от границы G. Для оценки асимметрии предлагается рассмотреть следующую характеристику нейрона е,: «/= I 7 ,fe). (2.14) Для каждого нейрона эта характеристика равна сумме весов латеральных связей со всеми другими узлами из окрестности Br(qt). Если qt расположен близко к границе Q, то в сумме не достаточно слагаемых. Поэтому cti убывает вблизи границы Q. На рис. 2.6 показан график величины (ХІ в случае равномерной прямоугольной зафиксированной сетки.
Все узлы, расположенные на расстоянии от границы, большем г, имеют равные значения характеристики сц. Для балансировки граничного эффекта необходимо, чтобы эта характеристика была одинаковой для всех нейронов.
Следует заметить, что использование маленького радиуса в конце обучения с одной стороны уменьшает граничный эффект, но с другой стороны приводит к ухудшению гладкости сетки, а значит и ее качества. Вопрос гладкости сетки подробно рассмотрен в разделе 3.5, где предлагается вариант алгоритма обучения и правила обучения, при которых характеристика щ близка к постоянной для всех нейронов даже при большом радиусе обучения. Этот алгоритм позволяет получать гладкие сетки, за, счет использования большого радиуса обучения, и без граничного эффекта.
В случае когда размерность пространства RkQ меньше размерности i?, исключить граничный эффект можно, используя в качестве вычислительных областей, например, замкнутые кривые, сферу, тор [59,60] и т.п.. На таких областях можно задавать зафиксированную сетку, у которой все узлы имеют в заданной окрестности одинаковое количество симметрично окружающих их соседей.
Мертвые нейроны При обучении иногда возникают такие ситуации, когда веса некоторого нейрона настраиваются таким образом, что вероятность стать победителем для него равна нулю. В этом случае веса этого нейрона могут изменяться только за счет латеральных связей. Некоторым таким нейронам удается вновь обрести способность стать победителям. Другие же, начиная с некоторой итерации, могут начать изменять свои веса только лишь на пренебрежительно малые величины, которых не достаточно для того, чтобы восстановить способность стать победителем. Последние нейроны называются мертвыми [61,62]. При построении адаптивных сеток, мертвые нейроны в основном характеризуются тем, что соответствующие узлы сетки вышли за границу области G.
Пусть область G выпуклая, тогда если все узлы сетки лежат внутри G, то до конца итерационного процесса Агл. А они не выйдут за ее границу. Доказательство Выпуклость области означает, что для любой пары точек Х\ и Х2 из G все точки отрезка [xj, Х2] принадлежат области G. Пусть узел ХІ(І) лежит в области G, тогда, т.к. y(t) также лежит в G, то из-за выпуклости весь отрезок [ ,(/), у] лежит в G. Следующее положение /-го узла - точка x((t + \) = x((t) + 0 {t,qi){yt-x({t)) - принадлежит отрезку [Xj(f),y], т.к. 6q (t,qt) є [0,1), а значит и области G, что и требовалось доказать. Таким образом, если область G выпуклая, то узлы сетки в процессе её построения перемещаются внутри области G, не выходя за её границу [63]. На практике, даже если на нулевом шаге узлы сетки лежат за пределами G, то в процессе работы алгоритма они затянутся внутрь области.
Однако, если область невыпуклая, то нет гарантий того, что узлы не выйдут за границу области. При использовании базовой модели SOM движение узлов сетки при обучении никак не контролируется, и поэтому появление мертвых нейронов наблюдается даже при достаточно простых невыпуклых физических областях.
Причиной выхода узлов за границу области является то, что в модели присутствуют латеральные связи, которые заставляют двигаться в направлении случайной точки не только победителя, но и его соседей из окрестности Br{t)(qm). При обучении, узел .(/) и точка yt могут оказаться такими, что отрезок [Хі(і),уі\ не лежит целиком в области G. Тогда существует вероятность, что коэффициент обучения укажет узлу ;(/+l) в качестве следующего его положения именно такую точку отрезка [х$),у], которая лежит за пределами G.
Примеры использования композиционной модели SOM для построения адаптивных сеток
В качестве примера рассмотрим использование композиционной модели SOM для построения 2D сетки на односвязной физической области G. Пусть в области G выделены граница Gj и внутренность G J Для построения сетки будут использованы три смешанные модели SOMkBC, к =0,1,2, которые работают соответственно на всей области G, на ее границе и внутренности. Пусть зафиксированная сетка QN - это равномерная прямоугольная на прямоугольной вычислительной области. Подмножество индексов граничных узлов Nt описывает узлы, расположенные на границе области Q, остальные узлы - внутренние с индексами из Nint. Эксперименты показали, что в случае несложных областей, карту Mj для модели SOMBC, которая соответствует граничным узлам, лучше выбирать без необучаемых нейронов среди внутренних узлов [66]. То есть Мх = {е(еМ\ieNb) - это множество граничных нейронов и / =0. В результате, при построении, граничные узлы будут распределяться по границе независимо от внутренних. Однако же карта для внутренних узлов должна включать в себя множество всех граничных нейронов, которые являются необучаемыми относительно нее, т.е. М.2 - М и 7 2 = Mj. В результате, при построении внутренние узлы подстраиваются под граничные. Карта для модели SOMlc, отвечающей за всю сетку в целом, - это М0 = М, где множество необучаемых нейронов F0 = 0. Пусть функции раскраски CG и CQ постоянны для всех нейронов и для всей физической области. Это означает, что нейроны и область покрашены только в один цвет.
Взаимодействие граничных и внутренних узлов сетки в процессе работы Алг.В происходит следующим образом. В начале работы алгоритма после того, как сетка грубо приняла форму области, граничные узлы расположились недалеко от их подходящих позиций на границе области. После этого граничные узлы сетки начинают приближаться к границе области в течение работы алгоритма на шаге 1 независимо от внутренних узлов. Внутренние узлы же зависят от граничных, т.к. последние участвуют в выборе победителя при корректировке положений внутренних узлов. Несмотря на то, что граничные узлы не меняют своих положений при корректировке на шаге 2, наличие латеральных связей заставляет внутренние узлы приближаться к соседним граничным узлам. Замена случайной точки граничным узлом победителем ускоряет это движение внутренних узлов и направляет его в нужную сторону. Эта методика не только обеспечивает согласованность между граничными и внутренними узлами в процессе самоорганизации, но и также решает проблему сохранения топологии при отображении Q на G и балансирует при маленьком радиусе обучения несимметричность латеральных связей для внутренних узлов, связанных с граничными на границе G, таким образом, уменьшая граничный эффект SOM.
Пусть область G имеет и-1 дырок, при этом с каждой к-й дыркой связана внутренняя граница G, =1,...,и-1. Тогда G представляется в виде разбиения на следующие части: Gi,...Gn.\ - внутренние границы G, Gn -внешняя граница G, Gn+! - внутренность области G. Каждая дырка G должна быть поставлена в соответствие дырке в зафиксированной сетке QN. Поэтому прежде всего требуется найти подходящие положения и размеры дырок в QM для произвольной области и неравномерной функцией плотности. Необходимо понимать, что неправильное расположение дырок зафиксированной сетки может привести к плохому качеству сеток, например, к появлению самопересечений сетки или к плохим формам ячеек сетки. Поэтому важно иметь методику автоматического задания дырок в QN, кроме того, избегая продолжительной ручной работы.
Для автоматического определения положений и размеров дырок 2м которые должным образом натянулись бы на дырки в области G, предлагается использовать алгоритм построения сетки для односвязных областей [68], предложенный в прошлом разделе. Работая с сеткой Qy без учета дырок, чередование в композиционной модели применяется только для внешней границы G„ области G и для ее внутренности Gn+\. Дырки в области G рассматриваются как участки с нулевой вероятностью генерации случайной точки. Из-за наличия латеральных связей в нейронном слое, получившаяся сетка содержит узлы, которые попали в дырки, несмотря на то, что ни одной точки в них не было сгенерировано. Если в дырку не попало ни одного узла, то необходимо алгоритм запустить заново с большим количеством узлов, чтобы улучшить разрешение.
На рис. 3.6(6) показана сетка QN, в которой удалены узлы, попавшие в дырки области G. Для того, чтобы можно было использовать сетку в дальнейших вычислениях, дырки в области QN обычно должны быть прямоугольными или представлять собой объединение прямоугольников, как показано на рис. 3.6(B). Если положения и приблизительные размеры дырок уже известны, то превратить дырки в прямоугольные уже не составляет труда. Процедура, которая трансформирует дырки в правильную форму называется MakeHoles. Найденная конфигурация дырок не единственная из-за стохастической природы алгоритма.
Следует заметить, что подобную методику автоматического определения положений и размеров дырок в зафиксированной сетке проблематично применять в традиционных методах, т.к. в этих методах налагаются достаточно жесткие требования на функцию плотности сетки. Так, обращающаяся в нуль функция плотности сетки w{x) как правило приводит к расходимости процесса построения сетки. Даже если установить не нулевые, а маленькие значения w(x) для дырок, функция w(x) может содержать разрывы, которые также ведут к расходимости.
После нахождения вырезов в сетке QN, задача заключается в том, чтобы найти отображение QN С дырками в искомую адаптивную сетку GN- При этом внешние и внутренние граничные узлы должны автоматически распределиться по соответствующим границам G.
Пусть Л ,...,Л -1 - это множества индексов граничных узлов, которые должны распределиться соответственно по внутренним границам Gv...,Gn_x. Другими словами, множества Nlb,...,Nb ] определяют те узлы, которые лежат на границах дырок в сетке QN. Nb - это множество индексов узлов, которые должны растянуться по внешней границе Gn. Для задания композиционной модели, нужно определить смешанные модели SOMkBC, к = 0,...,п + \, входящие в ее состав. Аналогично случаю с односвязной областью, модель SOMnBC для внешней границы работает с картой Mn = {ejeM\ieNb} без необучаемых нейронов.
Сравнительный анализ метода эквираспределения и нейросетевого метода на примере решения одномерного уравнения Пуассона
Так как координаты узлов Xj известны, то с учетом граничных условий систему уравнений (4.15) можно решить методом прогонки, т.к. она имеет трехдиагональную матрицу с диагональным преобладанием.
При решении задачи на равномерной сетке наибольшая ошибка, как правило, наблюдается в тех участках вычислительной области, в которых решение быстро меняется, т.е. имеет большие значения производной [5]. Поэтому целесообразно сгущать сетку именно в этих участках.
Если использовать одну из функций (4.16), то получается, что для построения сетки нужно знать решение и(х), т.к. от него зависит управляющая функция w(x), а для нахождения решения и{х) необходима сетка. Выходом из этой ситуации является использование метода последовательных приближений [5], который состоит из следующих шагов.
Пример адаптивной сетки, функции плотности и решения уравнения Пуассона. В среде Visual C++ с использованием библиотеки MFC реализована программа для неиросетевого метода построения адаптивных сеток, метода эквираспределения и решения уравнения Пуассона на адаптивной сетке. На рисунке 5.1 изображен пример адаптивной сетки на одномерной области G, построенной нейросетевым методом, график соответствующей управляющей функции w(x) и график решения уравнения Пуассона.
При сравнении двух методов построения сетки задача (4.11) решалась с помощью последовательных приближений двумя способами [71]. Каждый из этих способов отличался лишь тем, что на шаге 1в алгоритма последовательных приближений использовался либо нейросетевой метод построения сетки, либо метод эквираспределения.
На основе результатов экспериментов можно сделать следующие выводы. 1. Метод эквираспределения более чувствителен к параметрам а и /? управляющей функции w(x), чем нейросетевой метод. На рисунке 4.3(a) изображены графики ошибки Е(п) для метода эквираспределения для различных параметров, из которых видно, что для фиксированного а = 20 при /?=0.1 ошибка меньше, чем на равномерной сетке, при /?=0.22 -больше, чем на равномерной сетке, а при /?= 0.25 итерационный процесс последовательных приближений расходится. На графиках ошибки Е{п) для нейросетевого метода (рис. 4.3(6)) параметр /? изменяется в пределах от 0.2 до 5, однако расходимости процесса не наблюдается.
Следует заметить, что значения параметров а и Д а также ошибки Е(п), зависят от конкретной задачи. При фиксированных данных (4.18) в области G сосредоточено 4 участка со сгущениями, что усложняет поиск оптимальных параметров для минимизации ошибки, по сравнению со случаем, когда такой участок один. /
3. В одномерном случае метод эквираспределения имеет преимущество по времени вычислений, т.к. для построения сетки требуется выполнить одномерную прогонку. В нейросетевом методе построение осуществляется итерационно. Однако в двумерном случае оба метода итерационные.
В первом эксперименте на области G были построены две сетки: первая - нейросетевым методом (с произвольными начальными и граничными данными), вторая - методом эквираспределения (в качестве начальной сетки и для задания положений граничных узлов использовалась первая сетка, построенная нейросетевым методом). На каждой из этих сеток была решена задача Пуассона. Графики ошибки Е, равной относительной разности численного и аналитического решений, показаны на рис. 4.6. Видно, что максимум ошибки достигается в окрестности точки (x]Q,xl), т.к. именно в ней сосредоточена особенность решения, и в обоих случаях значение этого максимума примерно одинаковое. Из этого можно сделать вывод, что сетку нужно сгущать в окрестности точки (х]0,х20).
Во втором эксперименте в области G была задана функция плотности сетки таким образом, что ее значение равно w(x) = 255 для точек х из окружности, содержащей точку {x\,xl), и w(x) = 55 в оставшейся части области G. Числа 255 и 55 просто соответствуют оттенкам серого на изображении физической области. Фактически для задания таким образом функции плотности на области G просто был нарисован черный круг, который содержит точку (xl,x20). Адаптивная сетка с такой функцией плотности, построенная нейросетевым методом, показана на рис. 4.7. Из графика ошибки на рис. 4.7 (б) следует, что максимум ошибки уменьшился почти в три раза при решении задачи на сетке со сгущением в круге. Следует подчеркнуть, что метод эквираспределения с такой функцией плотности разошелся, т.к. она разрывна. Поэтому сравнить точность на такой сетке не представилось возможным.
В третьем эксперименте адаптивная сетка была построена с функцией плотности, которая получилась из функции прошлого эксперимента, только со сглаженными краями. То есть вместо обычного черного круга на изображении области G был нарисован круг с градиентными краями. Адаптивная сетка, построенная нейросетевым методом, показана на рис. 4.8. В этом эксперименте максимум ошибки уменьшился в 4 раза по сравнению с максимумом ошибки, полученным на сетке с равномерной функцией плотности. Метод эквираспределения в этом случае опять не дал приемлемой сетки из-за расходимости.
Экспериментальное исследование предложенных методов и их сравнение с методом эквираспределения на примере решения ID и 2D уравнений Пуассона, показали, что качество адаптивных сеток, полученных нейросетевыми методами, удовлетворяет общепринятым критериям. Неиросетевые методы позволяют получать приемлемые адаптивные сетки при произвольно заданных (разрывных, обращающихся в нуль, сложной конфигурации) функциях плотности, для которых невозможно добиться сходимости традиционного метода эквираспределения. Глава 5. Комплекс программ для построения адаптивных сеток
В данной главе описывается реализованный комплекс программ для построения двумерных адаптивных сеток с использованием разработанных неиросетевых моделей. Приводятся особенности последовательной и параллельная реализации алгоритмов. Оценивается эффективность распараллеливания.
Комплекс программ, реализованный для построения адаптивных сеток на основе предложенных неиросетевых моделей, состоит из следующих компонент: основное приложение для построения сеток - АМС (Adaptive Mesh Constrution) приложение для задания функций раскраски и элементов композиционной модели SOM - AMCColor параллельная программа, реализующая параллельный алгоритм обучения для смешанной модели SOM, которая является ядром для композиционной модели SOM.
Первые два приложения реализованы в среде Visual C++ с использованием библиотеки MFC [72] и предназначены для построения адаптивных сеток на двумерных областях. Параллельная программа реализована с использованием библиотеки MPI. Перечисленные выше компоненты комплекса программ состоят из следующих модулей:
В связи с этим, далее предполагается, что G состоит из конечного числа точек с целочисленными координатами (пикселей). При реализации считалось, что оттенок серого каждого пикселя кодируется целым числом в диапазоне от 0 до 255. При этом 0 соответствует белому цвету, а 255 -черному. Чем темнее некоторый участок области G, тем больше значение функции плотности, а значит, тем с большей вероятностью будут генерироваться случайные точки из этого участка. Точки белого цвета имеют нулевую вероятность выпадения, поэтому без ограничений общности такие точки можно считать фоном. Далее предполагается, что область G состоит только из точек с положительным оттенком серого, т.е. w(x)e {1,..., 255 } для xeG.
Несмотря на то, что область G дискретна, в процессе построения узлы сетки должны иметь действительные координаты для сохранения гладкости сетки. Однако случайные точки могут генерироваться с целочисленными координатами.
