Разработка и исследование генетических методов обучения нейронных сетей для задач визуализации в САПР-К

В любом современном пакете САПР [81] присутствуют наборы базовых функций, которые задают основную направленность применения этой системы и определяют подсистемы, использующиеся для решения задач данной САПР. Принято различать подсистемы проектирующие и обслуживающие. Проектирующие подсистемы непосредственно выполняют проектные процедуры. Примерами проектирующих подсистем могут служить подсистемы геометрического трехмерного моделирования механических объектов, изготовления конструкторской документации, схемотехнического анализа, трассировки соединений в печатных платах. Обслуживающие подсистемы обеспечивают функционирование проектирующих подсистем, их совокупность часто называют системной средой (или оболочкой) САПР.

Структурирование САПР по различным аспектам выявляет виды обеспечения САПР:

•техническое (ТО), включающее различные аппаратные средства (ЭВМ, периферийные устройства, сетевое коммутационное оборудование, линии связи, измерительные средства);

•математическое (МО), объединяющее математические методы, модели и алгоритмы для выполнения проектирования;

•программное (ПО), представляемое компьютерными программами САПР- •информационное (ИО), представляющее собой базы и банки данных- •лингвистическое (ЛО), определяющее языки интерфеса, языки программирования и форматы данных;

•методическое (МетО), включающее различные методики проектирования (иногда к МетО относят также математическое обеспечение);

•организационное (00), представляемое штатными расписаниями, должностными инструкциями и другими документами, регламентирующими работу проектного предприятия.

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

1. САПР для применения в отраслях общего машиностроения. Их часто называют машиностроительными САПР или MCAD (Mechanical CAD) системами.

2. САПР для радиоэлектроники: ECAD (Electronic CAD) и EDA (Electronic Design Automation) системы.

3. САПР архитектуры и строительства.

По целевому назначению различают САПР или подсистемы САПР, обеспечивающие разные аспекты проектирования. Так, например, в состав MCAD включаются CAD/CAM-системы:

1. САПР функционального проектирования, иначе САПР-Ф или CAE (Computer Aided Engineering) системы;

2. Конструкторские САПР — САПР-К, или CAD-системы;

3. Технологические САПР — САПР-Т, иначе называемые автоматизированными системами технологической подготовки производства АСТПП или системами САМ (Computer Aided Manufacturing).

По масштабам различают отдельные программно-методические комплексы (ПМК) САПР, например, комплекс анализа прочности механических изделий в соответствии с методом конечных элементов (МКЭ) или комплекс анализа электронных схемсистемы ПМКсистемы с уникальными архитектурами не только программного (software), но и технического (hardware) обеспечении.

По характеру базовой подсистемы различают следующие разновидности САПР.

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

2. САПР на базе СУБД. Такие САПР преимущественно встречаются в технико-экономических приложениях, например, при проектировании объектов, требующих незначительных вычислительных затрат, но информационно емких.

3. САПР на базе конкретного прикладного пакета. Автономно используемые программно-методические комплексы, например, имитационного моделирования. Часто такие САПР относятся к системам CAE. Примерами могут служить программы логического проектирования на базе языка VHDL, математические пакеты типа MathCAD или MathLAB.

4. Комплексные (интегрированные) САПР, состоящие из совокупности подсистем предыдущих видов.

К основным функциям САМ-систем относятся: разработка технологических процессов, синтез управляющих программ для технологического оборудования, моделирование процессов обработки, генерация постпроцессоров для конкретных типов оборудования (NC — Numerical Control), расчет норм времени обработки.

Функции CAD-систем в машиностроении подразделяют на функции двухмерного (2D) и трехмерного (3D) проектирования. К функциям 2D относятся черчение, оформление конструкторской документациик функциям 3D — получение трехмерных моделей, метрические расчеты, реалистичная визуализация, взаимное преобразование 2D и 3D моделей.

Среди CAD-систем принято выделять в отдельный класс системы, ориентированные, преимущественно, на геометрическое моделирование (3D графику). Такие системы относительно универсальны, но дороги. Оформление чертежной документации в таких системах обычно осуществляется с помощью предварительной разработки трехмерных геометрических моделей, а процесс получения качественной растеризации для графического макета сложной трехмерной сцены является чрезвычайно требовательным к вычислительным ресурсам системы и требует постоянной разработки новых подходов к задаче визуализации. В связи с большой сложностью и размерностью проектных решений, получаемых на этапе конструкторского проектирования в автоматизированных системах (САПР-К), появляется необходимость в разработке новых направлений, методик и алгоритмов решения задачи качественной векторной растеризации (визуализации). Эта задача является одной из основных при макетировании графических элементов проектных решений САПР-К. Место этой задачи четко определено в работах И. П. Норенкова, У. Ньюмена [99], Д. Роджерса [114−116], И. Гардана и М. Люка [56]. Задача инженерной визуализации на этапе макетирования проектного решения в подсистемах САПР МГиГМ может быть решена в интерактивном режиме. Это возможно в случае, когда качество конечного изображения проектируемого изделия некритично, в остальных случаях необходимо производить полную лучевую трассировку общего плана трехмерной сцены. При этом трехмерный макет проектного решения САПР-К будет спроецирован на будущую картинную плоскость с учетом всех оптических и геометрических свойств объектов, составляющих общий план сцены проектного решения. Таким образом, задача качественной визуализации относится к классу NP-полных, и традиционно решается методом полного перебора. Кроме того, процесс визуализации традиционно является однопоточным, а современные вычислительные системы обеспечивают высокий уровень производительности исключительно при использовании параллельных вычислений, возникает необходимость разработки средств классификации объектов, составляющих трехмерные сцены проектных решений САПР-К. Это необходимо для того, что бы получить возможность обрабатывать составляющие проектного решения параллельно, учитывая собственные сложности обработки моделируемых объектов САПР-К. Так как процесс визуализации традиционно является однопоточным, а современные вычислительные системы обеспечивают высокий уровень производительности исключительно при использовании параллельных вычислений, возникает необходимость разработки средств классификации объектов, составляющих трехмерные сцены проектных решений САПР-К. Распараллеливание вычислений (при использовании параллельных вычислительных систем, многопроцессорных или кластерного типа) является единственным методом, позволяющим реализовать процесс визуализации без потерь в качестве полученного изображения. Это необходимо для того, что бы получить возможность обрабатывать составляющие проектного решения параллельно, учитывая собственные сложности обработки моделируемых объектов САПР-К. При этом, для распараллеливания задачи визуализации, как правило, используется классический подход, когда проекционная (картинная) плоскость будущего растрового изображения делится на равные участки, обрабатываемые вычислительной системой параллельно. Этот метод имеет ряд явных недостатков. Первый из них заключается в обработке пустых областей растеризуемого изображения наравне с заполненными. Второй проявляется в условиях анизотропности кластерной вычислительной структуры, поскольку этот метод не учитывает такой параметр распределенной вычислительной системы, как неравномерное распределение вычислительной мощности (в случае, когда машины имеют разную вычислительную мощность) комплекса. Все перечисленное объясняет необходимость синтеза новых подходов, позволяющих эффективно решать задачу визуализации как в условиях однопроцессорных или симметричных многопроцессорных систем, так и на различных кластерных архитектурах. При этом предполагается, что новые подходы потребуют дополнительных методов подготовки к процессу визуализации, таких, например, как решение классификационной задачи для разделения всех объектов сцены по классам подобия, с целью оптимизации вычислительного процесса.

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

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

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

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

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

Идея искусственных нейросетей заключается в моделировании (повторении) поведения различных процессов на основе исторической информации.

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

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

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

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

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

Генетические алгоритмы — это новейший, но не единственно возможный способ решения задач оптимизации. Известны два классических пути решения таких задач — переборный и локально-градиентный. У этих методов есть свои достоинства и недостатки, и в каждом конкретном случае следует решать, какой из них будет оптимальным. Перебор дает точное решение задачи, но применение этого метода осложнено необходимостью рассмотрения огромного количества вариантов решений. Локально-градиентный метод основан на методе градиентного спуска. Вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, W поэтому для поиска глобального оптимума потребуются дополнительные усилия. Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения. Они идеальны для применения в так называемых унимодальных задачах, где целевая функция имеет единственный локальный (по условию постановки вопроса — он же глобальный) максимум. Поэтому при поиске решений для функций, имеющих несколько экстремумов, требуется применение различных вариантов комбинаций переборного и градиентного методов. ^ Генетический алгоритм представляет собой именно такой комбинированный метод. Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений — градиентный спуск. Такая комбинация позволяет обеспечить устойчиво хорошую эффективность генетического поиска для любых типов задач. Так, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритмэто программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, можно получить одно из лучших возможных решений (за это время).

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

Описание работы.

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

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

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

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

4. Разработаны новые структуры и принципы кодирования и декодирования вариантов для задач классификации элементов, составляющих проектные решения САПР-К.

5. Исследованы существующие идентификационные методы в сравнении с предлагаемыми алгоритмическими подходами к задаче классификации элементов проектных решений САПР-К.

6. Произведена оценка эффективности разработанных алгоритмов классификации и распараллеливания процесса визуализации проектных решений САПР-К.

Для решения поставленных задач используются следующие МЕТОДЫ ИССЛЕДОВАНИИ: элементы теории множеств, элементы теории алгоритмов, элементы теории генетического поиска, элементы теории принятия решений.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

1.Разработке методики распараллеливания процесса визуализации проектных решений САПР-К.

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

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

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

5.Разработке новых нейрогенетических методов решения задачи классификации сложных объектов, составляющих проектные решения САПР-К.

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

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

2. Разработка алгоритмов и программных моделей методики классификации сложных трехмерных объектов, составляющих проектные решения САПР-К.

3. Разработка программного пакета для исследования свойств нейросетевых и эволюционных моделей.

4. Определение теоретических и эмпирических оценок эффективности разработанных алгоритмов и выработка рекомендаций по подбору их параметров для задач САПР.

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ.

Основные теоретические и практические результаты диссертационной работы использованы в работе по гранту Министерства образования Российской Федерации на проведение фундаментальных исследований в области естественных наук № 12 392 (Е02 — 2.0−44) «Новые стратегии обучения нейронных сетей на основе вероятностных алгоритмов эволюционного поиска».

Научные результаты, полученные в диссертационной работе, использованы в НИИ ТКБ ТРТУ по договору № 710/98−16 002−7 «Участие в разработке технических приложений по созданию РИС и алгоритмов ее функционирования» (шифр «Модуль 8»).

Материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при проведении практических занятий в цикле лабораторных работ по курсам: «Генетические алгоритмы», «Искусственный интеллект» и «Системное программное обеспечение».

АПРОБАЦИЯ. Основные результаты диссертации представлены на научных семинарах (2000;2003, ТРТУ), международных научно-технических конференциях «Интеллектуальные САПР-2000», «Интеллектуальные САПР-2001», «Интеллектуальные САПР-2002», V всероссийской научной конференции студентов и аспирантов «КРЭС-2001», проводимых в ТРТУ, научной конференции «IEEE-AIS'02 CAD-2002» (r. Геленджик, 2002 г.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 8 печатных работах.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ.

Диссертация состоит из введения, четырех глав, списка литературы и приложения. Работа содержит 131 страницу, включая 26 рисунков, 13 таблиц, список литературы из 130 наименований.

4.5 Выводы и рекомендации.

Экспериментально определены пространственные и временные сложности алгоритмов распознавания классов объектов, составляющих проектные решения САПР-К, и алгоритма распараллеливания вычислительной нагрузки процесса визуализации, подтвердившие, в целом, теоретические оценки. Для этих задач были получены экспериментальные временные сложности 0(N2), которые меньше теоретических [N — число элементарных параметров, составляющих анализируемый объект].

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

Проведено сравнение представленных алгоритмов с существующими. Эксперименты показали преимущество предлагаемого кооперативно-соревновательного подхода к решению задач классификации трехмерных объектов, составляющих проектные решения САПР-К. Разработанные алгоритмы классификации затрачивают на 10%-15% меньше времени для получения решения, чем традиционные. Разработанные алгоритмы являются универсальными, в отличие от существующих, и допускают полное распараллеливание вычислений.

ЗАКЛЮЧЕНИЕ

.

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

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

2. Разработан алгоритм параллельной обработки сложных трехмерных макетов сцен проектных решений САПР-К в условиях анизотропности кластерной среды, что позволило сократить общее время решения задач визуализации на 12%-45%.

3. Определены оценки эффективности для каждого алгоритма. Показано, что при использовании разработанных алгоритмов классификации и визуализации в САПР-К время решения задач классификации сокращается на 10%-22%,.

4. На основе приведенных в диссертации алгоритмов разработана модульная программная среда NN-AI, позволяющая исследовать различные типы нейронных сетей и методы (в частности — генетические) их обучения для применения в задачах САПР.

5. На основе разработанного в диссертации алгоритма распараллеливания процесса визуализации создана система динамической балансировки процесса лучевой трассировки для визуализации трехмерных макетов проектных решений САПР-К.

6. Экспериментально определены пространственные и временные сложности алгоритмов распознавания классов объектов, составляющих проектные решения САПР-К, и алгоритма распараллеливания вычислительной нагрузки процесса визуализации, подтвердившие, в целом, теоретические оценки. Для этих задач были получены экспериментальные временные сложности 0(№), которые меньше теоретических.

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

8. Проведено сравнение разработанных алгоритмов с существующими. Эксперименты показали преимущество предлагаемого кооперативно-соревновательного подхода к решению задач классификации трехмерных объектов, составляющих проектные решения САПР-К. Разработанные алгоритмы классификации затрачивают на 10%-15% меньше времени для получения решения, чем традиционные. Предлагаемые алгоритмы являются универсальными, в отличие от традиционных, и допускают полное распараллеливание вычислений.