Содержание к диссертации
Введение
1. Анализ существующих моделей классификации в условиях визуализации проектных решений САПР-К 14
1.1 Трехмерные макеты и графические описания в системах САПР-К 14
1.2 Постановка задачи визуализации 19
1.3 Анализ существующих методик моделирования классификационных систем с применением нейросетей и методов генетического поиска 21
1.4 Эволюционные методы и методы генетического поиска 27
1.5 Принципы построения нейронных сетей с применением методов генетического поиска 33
1.6 Принципы кодирования нейронных сетей 36
1.7 Системы распределенных вычислений как инструмент распараллеливания процесса визуализации в САПР-К 40
1.8 Выводы и рекомендации 42
2. Синтез гибридного алгоритма, сочетающего эволюционное программирование и градиентное правило 43
2.1 Определение основных принципов кооперативного обучения 43
2.1.1 Постановка задачи обучения нейронной сети, применительно к проблеме классификации в условиях визуализации сложных графических макетов САПР-К 43
2.1.2 Определение функции ошибки НС 46
2.1.3 Анализ и оценка функциональной роли различных слоев в многослойном персептроне 47
2.2 Кооперативная эволюция в сетях с логистической активационной функцией 54
2.2.1 Алгоритм на основе эволюции скрытых активаций (Алгоритм Прадоса) 54
2.2.2 Разработка гибридного алгоритма, сочетающего эволюционное программирование и градиентное правило 57
2.2.3 Сравнение эффективности алгоритмов 59
2.3 Выводы и рекомендации 61
3. Разработка метода распараллеливания процесса визуализации проектных решений САПР-К 63
3.1 Особенности нейронных сетей радиального базиса 63
3.2 Разработка алгоритма классификации элементов проектных решений САПР-К на основе эволюционного программирования 65
3.3 Построение кооперативно-соревновательного генетического алгоритма обучения сетей радиального базиса 75
3.4 Синтез алгоритма распараллеливания процесса визуализации сложных графических макетов в САПР-К 92
3.5 Теоретические оценки разработанных алгоритмов 98
3.6 Выводы и рекомендации 100
4. Экспериментальное исследование разработанных алгоритмов 102
4.1 Цель экспериментального исследования 102
4.2 Оценка пространственной и временной сложности алгоритмов 104
4.3 Определение управляющих параметров нейросетевых алгоритмов классификации объектов, составляющих проектные решения САПР-К 114
4.4 Сравнение результатов, полученных представленными нейросетевыми алгоритмами классификации объектов 118
4.5 Выводы и рекомендации 119
Заключение 120
Литература 122
- Анализ существующих методик моделирования классификационных систем с применением нейросетей и методов генетического поиска
- Анализ и оценка функциональной роли различных слоев в многослойном персептроне
- Разработка алгоритма классификации элементов проектных решений САПР-К на основе эволюционного программирования
- Определение управляющих параметров нейросетевых алгоритмов классификации объектов, составляющих проектные решения САПР-К
Введение к работе
В любом современном пакете САПР [81] присутствуют наборы базовых функций, которые задают основную направленность применения этой системы и определяют подсистемы, использующиеся для решения задач данной САПР. Принято различать подсистемы проектирующие и обслуживающие. Проектирующие подсистемы непосредственно выполняют проектные процедуры. Примерами проектирующих подсистем могут служить подсистемы геометрического трехмерного моделирования механических объектов, изготовления конструкторской документации, схемотехнического анализа, трассировки соединений в печатных платах. Обслуживающие подсистемы обеспечивают функционирование проектирующих подсистем, их совокупность часто называют системной средой (или оболочкой) САПР.
Структурирование САПР по различным аспектам выявляет виды обеспечения САПР:
техническое (ТО), включающее различные аппаратные средства (ЭВМ, периферийные устройства, сетевое коммутационное оборудование, линии связи, измерительные средства);
математическое (МО), объединяющее математические методы, модели и алгоритмы для выполнения проектирования;
программное (ПО), представляемое компьютерными программами САПР;
информационное (ИО), представляющее собой базы и банки данных;
лингвистическое (ЛО), определяющее языки интерфеса, языки программирования и форматы данных;
методическое (МетО), включающее различные методики проектирования (иногда к МетО относят также математическое обеспечение);
организационное (00), представляемое штатными расписаниями, должностными инструкциями и другими документами, регламентирующими работу проектного предприятия.
Классификацию САПР принято осуществлять по ряду признаков, например, по приложению, целевому назначению, масштабам или комплексности решаемых задач, характеру базовой подсистемы - ядра САПР. По приложениям наиболее представительными и широко используемыми являются следующие группы САПР.
САПР для применения в отраслях общего машиностроения. Их часто называют машиностроительными САПР или MCAD (Mechanical CAD) системами.
САПР для радиоэлектроники: ECAD (Electronic CAD) и EDA (Electronic Design Automation) системы.
САПР архитектуры и строительства.
По целевому назначению различают САПР или подсистемы САПР, обеспечивающие разные аспекты проектирования. Так, например, в состав MCAD включаются CAD/CAM-системы:
1. САПР функционального проектирования, иначе САПР-Ф или САЕ
(Computer Aided Engineering) системы;
2. Конструкторские САПР - САПР-К, или CAD-системы;
3. Технологические САПР - САПР-Т, иначе называемые
автоматизированными системами технологической подготовки производства
АСТПП или системами САМ (Computer Aided Manufacturing).
По масштабам различают отдельные программно-методические комплексы (ПМК) САПР, например, комплекс анализа прочности механических изделий в соответствии с методом конечных элементов (МКЭ) или комплекс анализа электронных схем; системы ПМК; системы с уникальными архитектурами не только программного (software), но и технического (hardware) обеспечении.
По характеру базовой подсистемы различают следующие разновидности САПР.
1. САПР на базе подсистемы машинной графики и геометрического моделирования. Эти САПР ориентированы на приложения, где основной процедурой проектирования является конструирование, т. е. определение
?
пространственных форм и взаимного расположения объектов. Поэтому к
этой группе систем относится большинство графических ядер САПР в об-
^ ласти машиностроения.
САПР на базе СУБД. Такие САПР преимущественно встречаются в технико-экономических приложениях, например, при проектировании объектов, требующих незначительных вычислительных затрат, но информационно емких.
САПР на базе конкретного прикладного пакета. Автономно используемые программно-методические комплексы, например, имитационного моделирования. Часто такие САПР относятся к системам САЕ. Примерами могут служить программы логического проектирования на
v базе языка VHDL, математические пакеты типа MathCAD или MathLAB.
4. Комплексные (интегрированные) САПР, состоящие из совокупности
подсистем предыдущих видов.
К основным функциям САМ-систем относятся: разработка технологических
процессов, синтез управляющих программ для технологического оборудования,
моделирование процессов обработки, генерация постпроцессоров для конкретных
типов оборудования (NC — Numerical Control), расчет норм времени обработки.
$ Функции CAD-систем в машиностроении подразделяют на функции
двухмерного (2D) и трехмерного (3D) проектирования. К функциям 2D относятся черчение, оформление конструкторской документации; к функциям 3D — получение трехмерных моделей, метрические расчеты, реалистичная визуализация, взаимное преобразование 2D и 3D моделей.
Среди CAD-систем принято выделять в отдельный класс системы,
., ориентированные, преимущественно, на геометрическое моделирование (3D
графику). Такие системы относительно универсальны, но дороги. Оформление
чертежной документации в таких системах обычно осуществляется с помощью
предварительной разработки трехмерных геометрических моделей, а процесс
получения качественной растеризации для графического макета сложной
трехмерной сцены является чрезвычайно требовательным к вычислительным
х ресурсам системы и требует постоянной разработки новых подходов к задаче
визуализации. В связи с большой сложностью и размерностью проектных
решений, получаемых на этапе конструкторского проектирования в
автоматизированных системах (САПР-К), появляется необходимость в разработке
новых направлений, методик и алгоритмов решения задачи качественной
векторной растеризации (визуализации). Эта задача является одной из основных
при макетировании графических элементов проектных решений САПР-К. Место
этой задачи четко определено в работах И.П. Норенкова, У. Ньюмена [99], Д.
Роджерса [114-116], И. Гардана и М. Люка [56]. Задача инженерной
^ визуализации на этапе макетирования проектного решения в подсистемах САПР МГиГМ может быть решена в интерактивном режиме. Это возможно в случае, когда качество конечного изображения проектируемого изделия некритично, в остальных случаях необходимо производить полную лучевую трассировку общего плана трехмерной сцены. При этом трехмерный макет проектного решения САПР-К будет спроецирован на будущую картинную плоскость с учетом всех оптических и геометрических свойств объектов, составляющих общий план сцены проектного
Ш решения. Таким образом, задача качественной визуализации относится к классу NP-полных, и традиционно решается методом полного перебора. Кроме того, процесс визуализации традиционно является однопоточным, а современные вычислительные системы обеспечивают высокий уровень производительности исключительно при использовании параллельных вычислений, возникает необходимость разработки средств классификации объектов, составляющих трехмерные сцены проектных решений САПР-К. Это необходимо для того, что бы получить возможность обрабатывать составляющие проектного решения параллельно, учитывая собственные сложности обработки моделируемых объектов САПР-К. Так как процесс визуализации традиционно является однопоточным, а современные вычислительные системы обеспечивают высокий уровень
производительности исключительно при использовании параллельных вычислений, возникает необходимость разработки средств классификации
^ объектов, составляющих трехмерные сцены проектных решений САПР-К. Распараллеливание вычислений (при использовании параллельных вычислительных систем, многопроцессорных или кластерного типа) является единственным методом, позволяющим реализовать процесс визуализации без потерь в качестве полученного изображения. Это необходимо для того, что бы получить возможность обрабатывать составляющие проектного решения параллельно, учитывая собственные сложности обработки моделируемых объектов САПР-К. При этом, для распараллеливания задачи визуализации, как правило, используется классический подход, когда проекционная (картинная) плоскость
k будущего растрового изображения делится на равные участки, обрабатываемые
вычислительной системой параллельно. Этот метод имеет ряд явных недостатков. Первый из них заключается в обработке пустых областей растеризуемого изображения наравне с заполненными. Второй проявляется в условиях анизотропности кластерной вычислительной структуры, поскольку этот метод не учитывает такой параметр распределенной вычислительной системы, как неравномерное распределение вычислительной мощности (в случае, когда машины
v* имеют разную вычислительную мощность) комплекса. Все перечисленное объясняет необходимость синтеза новых подходов, позволяющих эффективно решать задачу визуализации как в условиях однопроцессорных или симметричных многопроцессорных систем, так и на различных кластерных архитектурах. При этом предполагается, что новые подходы потребуют дополнительных методов подготовки к процессу визуализации, таких, например, как решение классификационной задачи для разделения всех объектов сцены по классам
fc подобия, с целью оптимизации вычислительного процесса.
Искусственные интеллектуальные технологии, применяемые для задач классификации САПР - один из последних этапов развития аналитических
подходов. Аналитическими подходами принято называть технологии, которые на основе каких-либо моделей, алгоритмов, математических теорем позволяют по ^ известным данным оценить значения неизвестных характеристик и параметров.
Классические методики анализа оказываются малоэффективными во многих практических задачах. Это связано с тем, что невозможно достаточно полно описать реальность с помощью небольшого числа параметров модели, либо расчет модели требует слишком много времени и вычислительных ресурсов. В итоге -традиционные технологии применимы далеко не всегда, но и вероятностные технологии, базирующиеся на анализе параметров вероятностных моделей (распределений случайных величин, средних значений, дисперсий и т.д.) также обладают существенными недостатками при решении практических задач. " Зависимости, встречающиеся на практике, часто нелинейны. Даже если и существует простая зависимость, то ее вид заранее неизвестен. Статистические методы хорошо развиты только для одномерных случайных величин. Когда при анализе требуется учесть несколько взаимосвязанных факторов (что необходимо для правильного разделения входного вектора в процессе классификации), традиционно используется построение многомерной статистической модели.
Описанные недостатки традиционных методик предопределили появление Ф новых технологий анализа. В основе аналитических систем нового типа лежат технологии искусственного интеллекта, имитирующие природные процессы, такие как деятельность нейронов мозга или процесс естественного отбора.
Наиболее популярными и проверенными из этих технологий являются нейронные сети и генетические алгоритмы.
Нейронные сети являются имитациями мозга в большей или меньшей степени, поэтому с их помощью успешно решаются разнообразные задачи -А распознавание образов, речи, рукописного текста, выявление закономерностей, классификация, прогнозирование. В таких задачах, где традиционные технологии бессильны, нейронные сети часто выступают как единственная, эффективная методика решения.
Идея искусственных нейросетей заключается в моделировании (повторении) поведения различных процессов на основе исторической информации.
Сама нейросеть представляется как набор специальных математических функций с множеством параметров, которые настраиваются в процессе обучения на наборах эталонных данных, или данных, полученных в результате самообучения. Затем, обученная нейросеть обрабатывает исходные реальные данные и выдает свой прогноз будущего поведения изучаемой системы. Суть нейросетевой модели заключается в стремлении подражать происходящим процессам. По своей структуре нейросетевая модель аналогична мозгу человека и также способна к обучению.
В основе моделирования нейронных сетей лежит поведенческий подход к решению задачи - сеть обучается на примерах, подстраивая свои параметры при помощи специальных обучающих алгоритмов. С практической точки зрения методика принятия решения обученной нейросети проста - на входе задаются некоторые числовые данные, и нейросеть ищет похожие в исторических данных, на которых она была обучена.
Как правило, нейросети имеют иерархическую внутреннюю структуру. На нижнем уровне находятся датчики (аналоги дендритов), обрабатывающие поступающую первичную информацию и присваивающие ее значимости вес, который сообщается одному из нейронов следующего уровня, который, в свою очередь, получает данные от нескольких датчиков. Таким образом, сигналы проходят до нейрона самого верхнего уровня, который и сообщает исследователю окончательный ответ. Такая общая идея может применяться в самых различных отраслях науки, где необходимо строить прогнозы - от военной техники до медицины и микробиологии, от геофизики до экономики. Способность к моделированию нелинейных процессов, работе с зашумленными данными, делает возможным применение нейронных сетей на самом широком классе задач, как в научных, так и в прикладных областях.
Генетические алгоритмы, в свою очередь, предлагают специальную технологию поиска оптимальных решений, которая успешно применяется в
^ различных областях науки. В этих алгоритмах используется идея естественного отбора среди живых организмов в природе.
Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде.
Генетические алгоритмы - это новейший, но не единственно возможный способ решения задач оптимизации. Известны два классических пути решения таких задач - переборный и локально-градиентный. У этих методов есть свои достоинства и недостатки, и в каждом конкретном случае следует решать, какой из них будет оптимальным. Перебор дает точное решение задачи, но применение этого метода осложнено необходимостью рассмотрения огромного количества вариантов решений. Локально-градиентный метод основан на методе градиентного спуска. Вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается,
W поэтому для поиска глобального оптимума потребуются дополнительные усилия. Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный (по условию постановки вопроса - он же глобальный) максимум. Поэтому при поиске решений для функций, имеющих несколько экстремумов, требуется применение различных вариантов комбинаций переборного и градиентного методов.
*. Генетический алгоритм представляет собой именно такой комбинированный
метод. Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений - градиентный спуск. Такая комбинация позволяет обеспечить устойчиво хорошую эффективность
генетического поиска для любых типов задач. Так, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм -это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, можно получить одно из лучших возможных решений (за это время).
Цель работы
заключается в разработке новых, кооперативно-соревновательных методов, основанных на совместном применении генетических алгоритмов и нейронных сетей, позволяющих создавать предельно гибкие, быстрые и эффективные инструменты анализа данных для реализации качественного процесса классификации сложных трехмерных объектов, составляющих проектные решения САПР-К.
Описание работы В рамках данной диссертационной работы для достижения поставленной цели были решены следующие задачи:
Разработан алгоритм распараллеливания процесса визуализации сложных трехмерных макетов для систем графического моделирования САПР-К, использующего синтезированные нейроэволюционные алгоритмы в качестве модулей классификации.
Разработан алгоритм классификации объектов, составляющих проектные решения САПР-К, основанный на применении нейронной сети прямого распространения, обучаемой при помощи градиентного правила и генетического программирования.
Разработан алгоритм классификации объектов, составляющих проектные решения САПР-К, основанный на применении нейронной сети радиального базиса, обучаемой генетическим алгоритмом.
Разработаны новые структуры и принципы кодирования и декодирования вариантов для задач классификации элементов, составляющих проектные решения САПР-К.
Исследованы существующие идентификационные методы в сравнении с предлагаемыми алгоритмическими подходами к задаче классификации элементов проектных решений САПР-К.
6. Произведена оценка эффективности разработанных алгоритмов
классификации и распараллеливания процесса визуализации проектных решений
САПР-К.
Для решения поставленных задач используются следующие МЕТОДЫ ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории алгоритмов, элементы теории генетического поиска, элементы теории принятия решений. НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:
1.Разработке методики распараллеливания процесса визуализации проектных решений САПР-К.
2.Разработке методики классификации объектов, составляющих проектные решения САПР-К, на основе нейронной сети радиального базиса, обучаемой генетическим алгоритмом.
3.Разработке методики классификации объектов, составляющих проектные решения САПР-К, на основе нейронной сети прямого распространения, обучаемой при помощи градиентного правила и методов генетического поиска.
4.Разработке новых структур и принципов кодирования и декодирования вариантов для задач классификации элементов проектных решений САПР-К, позволяющих повысить качество процессов идентификации объектов в пространстве признаков.
5.Разработке новых нейрогенетических методов решения задачи классификации сложных объектов, составляющих проектные решения САПР-К
ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:
Разработка алгоритма и программной реализации решения задачи распараллеливания процесса визуализации сложных графических макетов трехмерных сцен САПР-К, учитывающего условия анизотропности кластерной вычислительной среды.
Разработка алгоритмов и программных моделей методики классификации сложных трехмерных объектов, составляющих проектные решения САПР-К.
Разработка программного пакета для исследования свойств нейросетевых и эволюционных моделей.
Определение теоретических и эмпирических оценок эффективности разработанных алгоритмов и выработка рекомендаций по подбору их параметров для задач САПР.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.
Основные теоретические и практические результаты диссертационной работы использованы в работе по гранту Министерства образования Российской Федерации на проведение фундаментальных исследований в области естественных наук № 12392 (Е02 - 2.0-44) «Новые стратегии обучения нейронных сетей на основе вероятностных алгоритмов эволюционного поиска».
Научные результаты, полученные в диссертационной работе, использованы в НИИ ТКБ ТРТУ по договору № 710/98-16002-7 «Участие в разработке технических приложений по созданию РИС и алгоритмов ее функционирования» (шифр «Модуль 8»).
Материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при проведении практических занятий в цикле лабораторных работ по курсам: «Генетические алгоритмы», «Искусственный интеллект» и «Системное программное обеспечение».
АПРОБАЦИЯ. Основные результаты диссертации представлены на научных
семинарах (2000-2003, ТРТУ), международных научно-технических конференциях
"Интеллектуальные САПР-2000", "Интеллектуальные САПР-2001",
"Интеллектуальные САПР-2002", V всероссийской научной конференции студентов и аспирантов " КРЭС-2001", проводимых в ТРТУ, научной конференции "IEEE-AIS'02 CAD-2002"(r. Геленджик, 2002г.).
ПУБЛИКАЦИИ. Результаты диссертации отражены в 8 печатных работах.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ.
Диссертация состоит из введения, четырех глав, списка литературы и приложения. Работа содержит 131 страницу, включая 26 рисунков, 13 таблиц, список литературы из 130 наименований.
СОДЕРЖАНИЕ РАБОТЫ.
ВО ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ приведен анализ существующих моделей систем искусственного интеллекта, нейросетевых подходов. Поставлен ряд задач для дальнейшего решения (задачи визуализации в САПР-К и классификации элементов проектных решений САПР-К). Рассмотрены существующие алгоритмы обучения нейронных сетей. Выявлены достоинства и недостатки этих алгоритмов. Рассмотрены основные генетические методы, используемые при решении поставленных задач. Выбран инструмент для решения задачи распараллеливания процесса векторной растеризации (визуализации).
ВО ВТОРОЙ ГЛАВЕ определены основные принципы кооперативного обучения, произведен краткий анализ существующих кооперативных алгоритмов и приведено описание разработки алгоритма классификации элементов проектных решений САПР-К, сочетающего эволюционное программирование и дельта-правило. Приведена теоретическая оценка временной и пространственной сложности разработанного алгоритма, в сравнении с существующими.
В ТРЕТЬЕЙ ГЛАВЕ описаны решения поставленной задачи классификации компонентов проектных решений САПР-К при помощи различных кооперативно-соревновательных алгоритмов. Приведена разработка универсальной методики кодирования и декодирования хромосом для задачи классификации объектов, составляющих проектные решения САПР-К. Предложен и обоснован выбор нейросети радиального базиса в качестве основы для моделирования среды классификации. Разработаны методики классификации элементов проектных решений САПР-К, применимые в условиях предлагаемой кооперативно-соревновательной модели. Приведена теоретическая оценка временной и пространственной сложности разработанных алгоритмов.
В ЧЕТВЕРТОЙ ГЛАВЕ приведено описание исследований полученной кооперативно-соревновательной модели системы классификации и использующего этот механизм алгоритма распараллеливания процесса визуализации. Сделана экспериментальная оценка пространственной и временной сложности алгоритмов.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложениях даны копии актов внедрения, примеры полученных решений стандартных тестов для задачи визуализации в САПР.
Анализ существующих методик моделирования классификационных систем с применением нейросетей и методов генетического поиска
В настоящее время сформировался ряд подходов к построению систем классификации в САПР с использованием элементов искусственного интеллекта (ИИ). Эти подходы эмулируют некоторые свойства биологических систем методами математического моделирования. Одним из таких подходов является структурный подход, под которым подразумеваются попытки построения ИИ путем упрощенного моделирования структуры биологического мозга. Одной из первых таких попыток был персептрон Фрэнка Розенблатта. Основной моделируемой структурной единицей в персептронах (как и в большинстве других( вариантов моделирования мозга) является нейрон. Впоследствии возникли модели, объединенные термином "нейронные сети" (НС). Эти модели различаются по строению отдельных нейронов, по топологии связей между ними и по алгоритмам обучения. Среди наиболее известных сейчас вариантов НС можно назвать НС с обратным распространением ошибки, сети Хопфилда, стохастические нейронные сети, прямопоточные нейронные сети и сети функций радиального базиса. % НС наиболее успешно применяются в задачах распознавания образов, в том числе сильно зашумленных, и для построения систем классификации, поскольку НС работают даже в условиях неполной информации об окружающей среде и могут отвечать на задаваемые вопросы с некоторой долей вероятности.
Значительное распространение получил и эволюционный подход. При разработке систем классификации в этом случае основное внимание уделяется построению начальной модели, и правилам, по которым сна может изменяться (эволюционировать). При этом модель может быть построена различными методами - это может быть и НС, и набор логических правил, и любая другая модель. Затем математическая компьютерная модель обрабатывается методами генетического поиска или эволюционными методами (в общем случае), отбираются лучшие из правил, на основании которых генерируются новые модели, из которых снова выбираются лучшие правила и т.д.
Следует отметить, что предлагаемые в рамках данной диссертационной работы подходы основаны на представлении структур данных в виде некоторой, в общем случае - нейронной сети. Рассмотрим способы построения моделей искусственных нейронных сетей (НС) для решения классификационных задач.
Биологический нейрон моделируется как устройство, имеющее несколько входов (дендриты) и один выход (аксон). Каждому входу ставится в соответствие некоторый весовой коэффициент (WJ), характеризующий пропускную способность канала и оценивающий степень влияния сигнала с этого входа на сигнал на выходе. Текущее состояние нейрона определяется как взвешенная сумма его входов:
Выход нейрона есть функция его состояния: Y=F (S). Иными словами, нейрон состоит из элементов трех типов: умножителей (синапсов), сумматора и нелинейного преобразователя. Синапсы осуществляют связь между нейронами, умножают входной сигнал на весовой коэффициент связи. Сумматор выполняет сложение сигналов, поступающий по связям от других нейронов, и внешних входных сигналов. Нелинейный преобразователь реализует функцию одного аргумента -выхода сумматора. Эта функция получила название функции активации или передаточной функции. Таким образом, нейрон реализует скалярную функцию векторного аргумента. В зависимости от конкретной реализации обрабатываемые нейроном сигналы могут быть аналоговыми или цифровыми (1 или 0). В теле нейрона происходит взвешенное суммирование входных возбуждений, далее это значение является аргументом активационной функции / нейрона. Одной из наиболее распространенных является функция с насыщением, так называемая логистическая функция или сигмоид (т.е. функция S-образного вида):
При уменьшении а кривая сигмоида становится более пологой, в пределе при а=0 вырождаясь в горизонтальную линию на уровне 0.5, при увеличении а форма кривой приближается, по внешнему виду, к функции единого скачка с порогом Т в точке х=1. Из выражения сигмоида очевидно следует, что выходное значение нейрона лежит в диапазоне [0,1]. Графически это значение может быть представлено в виде функции единичного скачка, линейного порога (или гистерезиса), сигмоида или гиперболического тангенса и сигмоида, описываемого по формуле (1.3).
Одно из ценных свойств сигмоидной функции состоит в том, что она дифференцируема на всей оси абсцисс, а так же простое выражение для ее производной, применение которого будет рассмотрено в дальнейшем при рассмотрении алгоритмов обучения НС. Следует отметить, что сигмоидная функция обладает свойством усиливать слабые сигналы лучше, чем большие, и предотвращает насыщение от больших сигналов, так как они соответствуют областям аргументов, где сигмоид имеет пологий наклон, что имеет значение для НС с обратными связями. Будучи соединенными определенным образом, нейроны образуют нейронную сеть. Работа сети разделяется на обучение и адаптацию. Под обучением понимается процесс адаптации сети к предъявляемым образцам путем модификации (в соответствии с тем или иным алгоритмом) весовых коэффициентов связей между нейронами. Этот процесс является результатом алгоритма функционирования сети, а не предварительно заложенных в нее знаний человека, как это часто бывает в системах искусственного интеллекта. НС, соответствующие структурам данных, синтезируются по их спискам связей. Их определяют выборы: типа моделей нейрона, сетевой конфигурации и алгоритма обучения НС. Все эти требования тесно взаимосвязаны между собой и требуют анализа для определения соответствующего оптимального сочетания. Модели НС могут быть программного и аппаратного исполнения. В диссертации рассматривается первый тип, так как он предназначен для моделирования НС, и исследования их особенностей.
Анализ и оценка функциональной роли различных слоев в многослойном персептроне
Устранения указанных недостатков можно добиться за счет перехода от популяции сетей к популяции нейронов в скрытом слое и комбинирования глобального и локального методов поиска. При этом эволюционный процесс поиска будет проходить в пределах одной сети, а операторы воспроизводства, мутации и отбора необходимо определить на уровне отдельных нейронов. Все пространство поиска разделяется на два подпространства, в каждом из которых поиск ведется разными путями для достижения единой цели: глобальный по параметрам скрытого слоя и быстрый локальный по выходным весам и порогам. Важно заметить, что результатом обучения в данном подходе будет не отдельная особь-сеть, а целая популяция особей-нейронов. При этом эти особи одновременно конкурируют и кооперируются с целью достижения заданного результата [17]. Преимущества общей глобальной оптимизации будут сохранены за счет того, что именно веса и пороги нейронов скрытого слоя определяют возможность общей успешной классификации или аппроксимации, как это было показано выше. В скрытом слое ведется глобальный процесс поиска прототипов, которые позволят последнему слою найти сочетание этих прототипов, соответствующее правильному решению.
Выходной слой можно обучать с помощью градиентного метода, причем его обучение сводится к обучению однослойного персептрона. Существует теорема, согласно которой однослойный персептрон может быть обучен градиентным правилом (которое в этом случае называется дельта-правилом) всему, что он может представлять [35]. Это означает, что однослойный персептрон не имеет локальных минимумов. Однако, при достаточно большом шаге на каждой итерации и ограниченном числе итераций не всегда достигается точное значение минимума, поэтому наряду с дельта-правилом в самом конце обучения можно использовать любой метод решения системы линейных уравнений (только в случае, если на выходе нет нелинейного преобразования или оно имеет обратную функцию). Чаще всего используют метод сингулярного разложения, дающий наименьшие погрешности [32].
Основная трудность, которую необходимо преодолеть для реализации кооперативного эволюционного обучения, заключается в определении функции качества отдельного нейрона в скрытом слое [17,37]. Трудность состоит в том, что оценка процесса обучения в целом происходит по выражению (1.9), которое является функцией от параметров всех нейронов, а сам алгоритм требует индивидуальной оценки каждого скрытого нейрона. Именно эта функция качества определяет степень мутации особей-родителей а также каким образом будет происходить порождение особей-потомков. Кроме того, эта функция служит для определения степени кооперации и конкуренции между различными нейронами. Если особи-нейроны совершают различную работу в общей задаче НС, то они должны кооперироваться, если же они делают одно и то же, то они конкурируют и выигрывает та особь, которая выполняет эту работу эффективней [14,37]. Процесс должен быть организован таким образом, чтобы каждый нейрон выполнял свою часть в общей работе сети по классификации или аппроксимации.
Обычно в качестве функции эффективности отдельного нейрона берется функция, обратная вкладу этого нейрона в общую ошибку сети (2.1). Эта функция может быть определена по-разному в зависимости от типа сети и постановки задачи и строится с помощью различных эвристик. Примеры кооперативных алгоритмов обучения НС и функции качества, которые они используют, будут описаны в последующих подразделах..
Значение І/ej приблизительно оценивает вклад j-ro скрытого нейрона в общую ошибку сети (2.1). Эффективность нейрона определяется по тому, насколько его выход, умноженный на вес выходного слоя vJm, усиливает выход сети в направлении заданного / . Так как значение функции качества тем больше, чем больше это усиление, то сразу видно ограничение: tkm&{F(-оо), F(oo)}, то есть такая функция подходит для решения только классификационных задач. Конкретный скрытый нейрон участвует в формировании всех выходных активностей, поэтому эффективность считается как сумма по всем выходам нейрона и всем предъявляемым на этапе обучения образам.
Алгоритм, предложенный Прадосом, представляется как эволюция не весов, а скрытых представлений, т.е. выходов скрытых нейронов. Таким образом, популяцию нейронов, т.е. нейронную сеть определяет вектор из L элементов, каждый из которых является вектором из К чисел в диапазоне от «-1» до «1». Другими словами, каждому скрытому нейрону соответствует вектор чисел - по одному на каждую обучающую пару. С помощью этих скрытых активностей сеть разделяется на две части, первая из которых должна осуществлять преобразование входов в заданные активности, а вторая - активности в заданные обучающей выборкой выходы сети. Так как входы сети, скрытые активности и выходы заданы, то по ним можно однозначно найти веса как скрытого, так и выходного слоев, решая при этом две задачи обучения однослойных персептронов. При решении первой задачи обучающими парами являются двойки {x,s), где х - входы сети главной обучающей выборки, as- заданные скрытые активности. Это обучение проводится с помощью нескольких итераций дельта-правила (достаточно 5-10 итераций). Из-за того, что представимость однослойного персептрона ограничена, необходимо найти после обучения реальные выходы скрытого слоя г,-, где i=l..К, которые будут использованы как входные образы при обучении выходного слоя. Выходными образами при обучении последнего слоя являются выходные образы главной обучающей выборки ,. Это обучение также производится с помощью дельта-правила за 10—25 итераций (длительность процесса обучения можно сделать адаптивной). Результатом обучения являются веса выходного слоя и ошибка сети Е, по значению которой определяется завершение работы алгоритма обучения. Получив веса второго слоя, можно высчитать значение эффективности каждого отдельного нейрона ej скрытого слоя по формуле (2.7) и, руководствуясь этими значениями, осуществить дифференцированное изменение требуемых скрытых активностей s.
Разработка алгоритма классификации элементов проектных решений САПР-К на основе эволюционного программирования
При кооперативном подходе в обучении нейросетей необходимо решать проблему разделения работы между скрытыми нейронами. Не должно быть элементов, которые выполняют одну и ту же функцию при классификации образов, т.е. все нейроны должны выполнять полезную работу и не дублировать по возможности других [17,37]. При обнаружении таких конкурирующих нейронов необходимо худшие из них изменить таким образом, чтобы они так же начали выполнять полезную работу при классификации.
Видно, что функция (3.1) не учитывает этих требований. При ее использовании во входном пространстве существуют минимумы, которые гауссоид стремится занять. Эти минимумы имеют бассейны притяжения различных размеров, что влечет за собой ситуацию, когда в одни минимумы собирается несколько гауссоид, а другие остаются незанятыми и, следовательно, разделение образов обучающей выборки осуществляется неправильно. Простейшим способом определения дублирующих элементов является нахождение расстояния между центрами гауссоид и введение порога расстояния, при превышении которого нейроны считаются кооперирующимися, однако такой способ не является инвариантным по отношению к минимальному расстоянию между образами обучающей выборки. Поэтому в рассматриваемом алгоритме дублирование определяется по отношению к обучающей выборке: элементы выполняют одну работу, если они наиболее приближены к одному и тому же образу. Этот вариант хорошо показал себя при моделировании, однако он тоже не лишен недостатков. Некоторые минимумы представляют собой не точки, а "долины", в разных частях которых ближайшими являются различные образы. Кроме того, при большом скоплении образов в ограниченном пространстве определение дублирующих элементов сильно затрудняется, так как в этом случае необходимо точное попадание центров в один минимум.
При определении конкурирующих элементов необходимо один из них, имеющий максимальное значение эффективности, оставить на месте, а остальные изменить. Так как в процессе обучения выходного слоя мы можем легко определить образы, ошибка сети на которых максимальна, то целесообразным является использование этой информации и помещение центров дублирующих гауссоид в точки, соответствующие этим "плохим" образам.
Учитывая все изложенные выше рассуждения, можно записать полученный алгоритм следующим образом: 1. Генерирование начальных значений центров и отклонений всех элементов. 2. Определение эффективности ej каждого гауссоида. 3. Если N1 mod b = 0 то переход к следующему пункту, иначе переход к пункту 9. 4. Обучить выходной слой с помощью 15 итераций градиентного правила. 5. Определение глобальной ошибки сети Е. 6. Если обучение закончено, то выход. 7. Определение дублирующих элементов. 8. Перераспределить худшие дублирующие гауссоиды на худшие образы. 9. Порождение нейронов-потомков. 10. Определение качества потомков ej 11. Отбор одного элемента среди родителя и его потомков. 12. Переход к пункту 3. При генерации начальных значений использовалось равномерное распределение центров по входному пространству. Отклонения также генерировались равномерно распределенными на некотором интервале. Этот интервал задает допустимые значения отклонений и при порождении потомков. Распределение отклонений можно также задавать по нормальному закону или какому-либо другому, дающему максимум вероятности в центре интервала. В пункте 3 проверяется, пройдено ли b итераций с момента последнего обучения весов и порогов выходного слоя (NT - номер итерации с начала обучения). Значение Ь, используемое при моделировании, равнялось 8-г10. Если условия выполняется, то производится последовательность действий, связанная с обучением выходного слоя, проверкой терминального условия, а также разделением сфер деятельности скрытых нейронов. В пункте 9 происходит мутирование родительского гауссоида с целью порождения его потомков. Определение центров и отклонений гауссоид-потомков осуществляется по следующим формулам: Е- ошибка сети. Можно в одной итерации порождать несколько потомков, так как в отличие от соответствующих алгоритмов для сетей с логистической функцией, возможно осуществлять отбор гауссоид одного родителя независимо от других. Это обусловлено локальным характером действия активационных функций и основанной на этом функции качества отдельного гауссоида. Однако при моделировании число порождаемых потомков равнялось одному (для более корректного сравнения с предыдущими алгоритмами). Проводимый в пункте 10 отбор возможно вести несколькими способами. Он может быть вероятностным и детерминированным. Возможно использование при порождении многих потомков соревновательной стратегии, используемой в эволюционном программировании [12], когда каждый нейрон соперничает с несколькими случайными другими нейронами и побеждает тот из них, который набрал при этом больше побед. Также возможен отбор с вероятностью, пропорциональной эффективности гауссоида [26,40]. Однако, можно использовать и детерминированный отбор, при котором всегда среди родителя и его потомков выбирается лучший. При этом глобальный характер поиска будет сохраняться благодаря исключению дублирующих элементов. Моделирование алгоритма обучения проводилось для двух двумерных задач. Первая из них была описана выше и ее обучающая выборка изображена на рисунке 2.7 ("дуга"). Отличительной особенностью данной задачи является относительно заметные скопления образов одного класса, что может служить проверкой эффективности применяемого разделения сфер действия гауссоид. На рисунке 3.1 изображен график изменения ошибки в процессе обучения, а на рисунке 3.2 - найденное решение. Можно заметить, что все кластеры образов выделены, все образы, которые можно было объединить одним гауссоидом, объединены при почти полном отсутствии дублирующих элементов. Это доказывает корректность функции эффективности отдельного нейрона. Следует обратить внимание на то, что несмотря на отбор элементов по локальной функции эффективности вр значение глобальной ошибки Е (рисунок 3.1) не возрастает, что также свидетельствует в пользу выбранной функции эффективности (3.1).
Сравнение графиков показывает, что скорость обучения данного алгоритма выше по сравнению с аналогичным алгоритмом для обычной архитектуры и при увеличении размеров сети это различие будет сказываться все сильней, что обусловлено индивидуальным отбором нейронов в противоположность принятию сети-потомка или сети-родителя целиком. Кроме того, благодаря независимости локальной функции качества от выходных параметров, среднее время одной итерации примерно втрое меньше, чем у аналогичного алгоритма при обучении сети с тем же количеством параметров.
Определение управляющих параметров нейросетевых алгоритмов классификации объектов, составляющих проектные решения САПР-К
Экспериментально определены пространственные и временные сложности алгоритмов распознавания классов объектов, составляющих проектные решения САПР-К, и алгоритма распараллеливания вычислительной нагрузки процесса визуализации, подтвердившие, в целом, теоретические оценки. Для этих задач были получены экспериментальные временные сложности 0(N), которые меньше теоретических [N - число элементарных параметров, составляющих анализируемый объект].
Определены оптимальные сочетания управляющих параметров для разработанных алгоритмов классификации элементов проектных решений САПР-К. По результатам экспериментов, выбраны оптимальные параметры (тип активационной функции, тип алгоритма обучения, значение ошибки), обеспечивающие возможность получения качественных результатов при решении задач классификации в САПР, за полиномиальное время.
Проведено сравнение представленных алгоритмов с существующими. Эксперименты показали преимущество предлагаемого кооперативно-соревновательного подхода к решению задач классификации трехмерных объектов, составляющих проектные решения САПР-К. Разработанные алгоритмы классификации затрачивают на 10%-15% меньше времени для получения решения, чем традиционные. Разработанные алгоритмы являются универсальными, в отличие от существующих, и допускают полное распараллеливание вычислений.
В диссертационной работе были разработаны и исследованы: кооперативно-соревновательные алгоритмы на основе нейронных сетей и генетических подходов, применительно к задаче классификации в рамках проблемы визуализации сложных трехмерных макетов проектных решений САПР-К. При этом получены следующие новые научные и практические результаты.
Применительно к методикам классификации компонентов проектных решений САПР-К разработаны алгоритмы кооперативно-соревновательного обучения нейронных сетей: кооперативный алгоритм на основе эволюции скрытых активаций для сетей с логистической функцией, алгоритм классификации на основе генетического программирования, кооперативно соревновательный генетический алгоритм обучения сетей радиального базиса. Данные алгоритмы моделируют процессы, схожие с процессами биологического мозга, такими как процессы классификации и идентификации подобия. Это позволило применить новые методы оптимизации при нахождении решений для задач классификации САПР. 2. Разработан алгоритм параллельной обработки сложных трехмерных макетов сцен проектных решений САПР-К в условиях анизотропности кластерной среды, что позволило сократить общее время решения задач визуализации на 12%-45%. 3. Определены оценки эффективности для каждого алгоритма. Показано, что при использовании разработанных алгоритмов классификации и визуализации в САПР-К время решения задач классификации сокращается на 10%-22%,. 4. На основе приведенных в диссертации алгоритмов разработана модульная программная среда NN-AI, позволяющая исследовать различные типы нейронных сетей и методы (в частности - генетические) их обучения для применения в задачах САПР. 5. На основе разработанного в диссертации алгоритма распараллеливания процесса визуализации создана система динамической балансировки процесса лучевой трассировки для визуализации трехмерных макетов проектных решений САПР-К. 6. Экспериментально определены пространственные и временные сложности алгоритмов распознавания классов объектов, составляющих проектные решения САПР-К, и алгоритма распараллеливания вычислительной нагрузки процесса визуализации, подтвердившие, в целом, теоретические оценки. Для этих задач были получены экспериментальные временные сложности 0(N), которые меньше теоретических. 7. Определены оптимальные сочетания управляющих параметров для разработанных алгоритмов классификации элементов проектных решений САПР-К. По результатам экспериментов выбраны оптимальные параметры (тип активационной функции, тип алгоритма обучения, значение ошибки), обеспечивающие возможность получения качественных результатов при решении задач классификации в САПР, за полиномиальное время. 8. Проведено сравнение разработанных алгоритмов с существующими. Эксперименты показали преимущество предлагаемого кооперативно-соревновательного подхода к решению задач классификации трехмерных объектов, составляющих проектные решения САПР-К. Разработанные алгоритмы классификации затрачивают на 10%-15% меньше времени для получения решения, чем традиционные. Предлагаемые алгоритмы являются универсальными, в отличие от традиционных, и допускают полное распараллеливание вычислений.
Похожие диссертации на Разработка и исследование генетических методов обучения нейронных сетей для задач визуализации в САПР-К
