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

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

КОНОВАЛОВ Олег Владимирович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ГЕНЕТИЧЕСКИХ МЕТОДОВ ОБУЧЕНИЯ НЕЙРОННЫХ СЕТЕЙ ДЛЯ ЗАДАЧ ВИЗУАЛИЗАЦИИ

В САПР-К

Специальность:

05.13.12-системы автоматизации проектирования

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата технических наук

Таганрог-2003

Работа выполнена в Таганрогском Государственном радиотехническом университете

НАУЧНЫЙ РУКОВОДИТЕЛЬ - д. т. н, профессор, Курейчик В.М.

НАУЧНЫЙ КОНСУЛЬТАНТ - д. т. н, доцент, Лебедев Б. К.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ - д. т. н, декан ФИБ, Божич В.И.

д. т. н, доцент, Зинченко И.А.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ -

Федеральное Государственное Унитарное Предприятие Таганрогский НИИ Связи (г. Таганрог)

Защита состоится " _2003 г. в 1400 на заседании

специализированного совета Д 212.259.03 по защите диссертаций при Таганрогском Государственном радиотехническом университете по адресу: 347945, г. Таганрог, пер. Некрасовский, 44, ауд. Д-406

С диссертацией можно ознакомиться в библиотеке Таганрогского Государственного радиотехнического университета.

Автореферат разослан « »__2003г.

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

А.Н. Целых

О^оЗ-Д

^75*5"

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

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

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

В этой связи диссертационная работа посвящена актуальной и важной проблеме.

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

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

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

БИБЛИОТЕКА

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

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

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

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

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

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

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

Научная новизна заключается в:

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

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

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

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

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

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

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

2. Разработка алгоритмов и программных моделей методики

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

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

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

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

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

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

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

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

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

Апробация работы и публикации. Основные результаты диссертации представлены на научных семинарах (с 2000 по 2003 гг., ТРТУ), IV, V, VI Всероссийской научно-технической конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 2000 г., 2002 г.), XVII Международной научно-технической конференции "Интеллектуальные САПР" (1ЕЕЕ-А18'02 САО-2002) (г. Геленджик, 2002 г.).

По теме диссертации опубликовано 7 печатных работ. Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, списка литературы и приложений. Работа содержит 142 страницы, включая 28 рисунков, 13 таблиц, список литературы из 135 наименований, 4 страницы приложений.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертационной

работы, поставлена цель работы, дано общее описание выполненной работы.

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

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

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

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

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

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

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

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

Такие нейронные сети позволяют проводить классификацию входных образов, объединенных в нечеткие (размытые или пересекающиеся) множества.

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

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

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

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

Х2 = - X. + 5

К'2 М>2

где х/, х2 - входные признаки; \м2 - весовые коэффициенты; И -порог сети.

Решить задачу "исключающего или", т.е. построить разделяющую

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

одного класса, а по другую - все образы другого класса, ни при каких

значениях параметров и> и И невозможно. Про такие классы говорят, что

они линейно неразделимы. Однако сеть, имеющая два нейрона в скрытом

слое, мижс1 выполни ib такое разделение. При этом, каждый из скрытых

нейронов по-прежнему выполняет линейное разделение входного +

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

получения требуемой финальной классификации (разделения) обучающих

пар. , , *

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

О

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

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

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

1С М Л

= (2) * = lm=l 1=1

i де e¡- эффективностьу'-го скрытого нейрона; v/m — веса выходно! о сз^ои; ,

и'(/ — веса скрыюш слоя;

F— симмефичная ожосшельно оси api умен га логистическая функция. Значение 1/е, приблизительно оценивает вклад j-ro скрытого нейрона в общую ошибку сети (1). Эффективность нейрона определяется по тому, насколько е!и выход, умноженный на вес выходного слоя vjm, усиливает

,к

выход сеж ь направлении заданно! и 1т.

Алгоритм, предложенный Прадосом, представляется как эволюция не весов, а скрытых представлений, т.е. выходов скрытых нейронов. Таким

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

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

Ом—

(3)

где а - коэффициент пропорциональности.

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

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

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

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

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

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

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

где <Цо ~ значение порога поу'-му выходу,

ф,(х)=ф(\ |д: - с,11М), где с, е 9?" - центр базисной функции ф„

(1, - отклонение или масштабирующий множитель для радиуса ||д: - с,||,

|| || - обычно евклидова норма в 9?".

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

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

Сети радиального базиса в настоящее время широко используются

£

(4)

1=1

также и для решения классификационных задач. При этом в качестве

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

векторного квантования.

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

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

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

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

«плохим» образам.

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

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

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

Второй из разработанных алгоритмов классификации - это кооперативно-соревновательный алгоритм обучения нейронной сети радиального базиса генетическим методом. Как в большинстве генетических алгоритмов, его внешний цикл представляет собой конструирование и оценивание успешных популяций С0, С/,...С*,.... Состояние алгоритма в каждом поколении (итерации) состоит из популяции битовых строк ф„ 1=1..т, где т - размер популяции, и каждая битовая строка ф, кодирует центр с, и отклонение с!, одного элемента ф, в выражении (4). Если скаляр с1, и каждая из координат вектора с, еЭД" кодируются / битами, то один радиальный элемент может быть закодирован битовой строкой ф, из (п+1)1 бит, т.е. Ьке{0,1}, 1=(п+1)1.

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

i 13

1

f

мера эффективности элемента будет определять ожидаемое количество копий ф, в следующем поколении Gk до их изменения генетическими операторами. После заполнения позиций G*,/ этими отобранными копиями применяются генетические операторы рекомбинации и мутации. Затем вычисляются функции качества элементов в (/¿./, которые определяют вероятности их помещения в популяцию <7^,2, и т.д.. При этом центральной проблемой является оценивание качества отдельного радиального элемента. Эта проблема решается компромиссом между уровнями соревновательности и кооперативности. Далее рассматриваются проблемы генетического кодирования условий для задачи классификации и проблемы обучения выходного слоя нейронной сети.

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

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

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

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

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

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

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

различных аппаратных платформах (для которых существует виртуальная машина Java). Эксперименты предварительного исследования алгоритмов принятия решений для задачи классификации проводились на ЭВМ типа IBM PC с процессором Intel® P-III/500.

Программная модель алгоритма распараллеливания процесса визуализации проектных решений САПР-K была реализован на языке С в качестве системы адаптивной балансировки нагрузки анизотропного вычислительного кластера для существующей программной системы высококачественной визуализации Persistent Of Vision RAYtracer (POV-RAY). Экспериментальные исследования полученного алгоритма проводились на программно-аппаратной основе вычислительного кластера, составленного из трех машин разной вычислительной мощности, функционирующего под управлением ОС Linux.

Экспериментальное исследование состоит из четырех разделов. В первом разделе были поставлены цели исследования. Во втором разделе проводились экспериментальные исследования пространственной и временной сложности нейросетевых алгоритмов классификации. В качестве тестовых примеров для распознавания типов объектов были выбраны модули с числом составляющих параметров 10, 20, 30, 40, 50, 60, 70, 80, 90 и 100 соответственно. Размер каждой серии определяется по таблице достаточно больших чисел, составленной на основании теоремы Бернулли, в зависимости от доверительной вероятности и допустимой ошибки. Для оценки алгоритмов определения типа объекта использовалась тестовая последовательность из ноднородных выпуклых объектов с числом элементов от 10 до 500 (с шагом 10 элементов).

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

Для задачи распараллеливания процесса визуализации сложных трехмерных макетов также были проведены серии экспериментов для макетируемых сцен с размерностью наполнения объектами от 5*103 до 5*10s. В результате проведенных экспериментов для исследуемого алгоритма распараллеливания процесса визуализации были получены полиномиальные зависимости OfN2) времени решения

В третьем разделе определялись управляющие параметры нейрогенетических классификационных алгоритмов. В качестве тестовых заданий были выбраны 5000 объектов случайно сгенерированной формы с количеством составляющих их параметров от 10 до 500. На основании проведенных экспериментов были определены оптимальные соотношения управляющих параметров предложенных алгоритмов: сигмоидальная активационная функция, обучающий алгоритм - ГА+РБ (генетический

' алгоритм обучения сети радиального базиса), точность обучения 0,02.

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

* выбраны: выпуклый однородный объект с 26 составляющими, объект

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

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

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

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

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

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

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

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

3. Определены оценки эффективности для каждого алгоритма.

и 755"

Показано, что при использовании разработанных Я^аДо^итХэ^ ^ классификации и визуализации в САПР-К повышается эффективность решения поставленной конечной задачи.

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

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

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

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

1.Коновалов О.В. Проблемы формирования трехмерных векторных структур. Известия ТРТУ №2, тематический выпуск «Интеллектуальные САПР». Таганрог: ТРТУ, 1998., С. 274.

2.Коновалов О.В. Трехмерный ландшафт. Проблемы построения и удобство использования. Тезисы докладов IV Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (КРЭС'98). Таганрог: ТРТУ, 1998, С. 73.

3.Коновалов О.В. Прикладной графический трехмерный редактор. Тезисы докладов сорок пятой студенческой научной конференции. Таганрог: ТРТУ, 1998, С. 82.

4.Коновалов О.В. Моделирование объектов в трехмерном пространстве. Тезисы докладов РиЭвНХ. М.: МЭИ, 1998, С. 102.

5.Коновалов О.В. Построение алгоритма обучения сетей радиального базиса при помощи градиентного правила. Труды XVII Международной научно-технической конференции "Интеллектуальные системы" (IEEE AIS'02 CAD-2002). M.: Физматлит, 2002, с. 111-118

6.Коновалов О.В. Кооперативно-соревновательный алгоритм обучения сетей радиального базиса. Сборник «Интеллектуальные САПР», №4 (8). Таганрог: ТРТУ, 2001, С. 174-177.

7.Коновалов О.В. Кооперативно-эволюционные алгоритмы обучения многослойных нейронных сетей прямого распространения. Сборник «Интеллектуальные САПР», №4 (8). Таганрог: ТРТУ, 2001 С. 177-180.

Соискатель ,1 /. О.В. Коновалов

ВВЕДЕНИЕ

1. АНАЛИЗ СУЩЕСТВУЮЩИХ МОДЕЛЕЙ КЛАССИФИКАЦИИ В УСЛОВИЯХ ВИЗУАЛИЗАЦИИ ПРОЕКТНЫХ РЕШЕНИЙ САПР-К

1.1 Трехмерные макеты и графические описания в системах С АПР-К

1.2 Постановка задачи визуализации

1.3 Анализ существующих методик моделирования классификационных систем с применением нейросетей и методов генетического поиска

1.4 Эволюционные методы и методы генетического поиска

1.5 Принципы построения нейронных сетей с применением методов генетического поиска

1.6 Принципы кодирования нейронных сетей

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

В любом современном пакете САПР [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. Определение теоретических и эмпирических оценок эффективности разработанных алгоритмов и выработка рекомендаций по подбору их параметров для задач САПР.

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

Основные теоретические и практические результаты диссертационной работы использованы в работе по гранту Министерства образования Российской Федерации на проведение фундаментальных исследований в области естественных наук № 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 наименований.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

1. A. Lapedes, R. Farber, How Neural Nets Work, in Neural 1.formation Proceeding Systems, pp. 442-456, New York, N.Y.: American Institute of Physics, 1988.

2. Amir Y., Averbuch В., Barak A., Borgstrom R.S. and Keren A. An Opportunity Cost Approach for JobAssignment and Reassignment in a Scalable Computing Cluster. In PDCS '98, 1998.

3. Balakrishnan K., Honavar V. Properties of Genetic Representations of Neural Architectures. In: Proceedings of the World Congress on Neural Networks (WCNN'95). Washington, D.C. July 17-21, 1995. pp. 807-813.

4. Barak A., Braverman A. Memory Ushering in Scalable Computing Cluster. Journal of Microprocessors and Microsystems, 22, 1998.

5. Barak A., Braverman A., Gilderman I., Laden O. Performance of PVM with the MOSIX Preemptive Process Migration. In Proc. Seventh Israeli Conf. on Computer Systems and Software Engineering, 1996.

6. Barak A., Guday S., Wheeler R.G. The MOSIX Distributed Operating System, Load Balancing for UNIX. In Lecture Notes in Computer Science, Springer-Verlag, 1993.

7. Barak A., La'adan O. The MOSIX Multicomputer Operating System for High Performance Cluster Computing. Journal of Future Generation Computer System, 13, 1998.

8. Barak A., La'adan O., Shiloh A. Scalable Cluster Computing with MOSIX for LINUX. The Hebrew University of Jerusalem, 1998.

9. Broomhead D.S., Lowe D., Multivariable functional interpolation and adaptive networks, Complex Systems, vol.2, pp. 321-355, 1988.

10. Cohen M. A., Grossberg S.G. 1983. Absolute stability of global pattern formation and parallel memory storage by compatitive neural networks. IEEE Transactions on Systems, Man and Cybernetics 13:815-26.

11. Cohen M.A., Grossberg S.G. 1983. Absolute stability of global pattern formation and parallel memory storage by compatitive neural networks. IEEE Transactions on Systems, Man and Cybernetics 13:815-26.

12. Fogel D.B., Fogel L.J., Porto V.W. Evolving Neural Networks, Biological Cybernetics, vol.63, 1990. pp. 487-493.

13. Goldberg D.E., Genetic Algorithms in Search, Optimization and Machine Learning. Reading, Massachusetts: Addison-Wesley, 1989.

14. H. de Garis, Genetic Programming: building artificial nervous systems using genetically programmed neural network modules, in Machine Learning: Proceedings of the Seventh International Conference, San Diego, С A: Morgan Kaufmann, 1990, pp.132-139.

15. Hebb D.O. Organization of behavior. New York: Science Edition, 1961.

16. Hinton G. E., Sejnowski T. J. 1986. Learning and relearning in Boltzmann machines. In Parallel distributed processing, vol. 1, pp. 282-317. Cambridge, MA: MIT Press.

17. Holland J.H., Adaptation in Natural and Artificial Systems. Ann Arbor, MI: The University of Michigan Press, 1975.

18. Hopfield J.J. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Science. 1982.

19. Java. Справочное руководство: Пер. с англ. М.: Восточная книжная компания, 1996. 448 с.

20. Kock, G., Serbedzija, N.B. (1993). Object-Oriented and Functional Concepts in Artificial Neural Network Modeling, Proc. Int. Joint Conf. on Neural Networks, Nagoya (Japan), 1993.

21. Kock, G., Serbedzija, N.B. Artificial Neural Networks: From Compact Descriptions to С++, in ICANN'94: Proc. of the Int. Conf. on Artificial Neural Networks, 1994

22. Kock, G., Serbedzija, N.B. Specification of Artificial Neural Networks based on the modified AXON Model, Proc. World Congress on Neural Networks Vol. I, Portland, 1993, P-433-436.

23. Kohonen Т., An introduction to neural computing. Neural Networks, vol.1, no.l, pp. 3-16, 1988.

24. Kohonen T. 1984. Self-organization and associative memory. Series in Information Sciences, vol. 8. Berlin: Springer Verlag.

25. Maniezzo V., "Genetic evolution of the topology and weight distribution of neural networks", IEEE Transactions on Neural Networks, vol.5, no.l. pp.39-53, 1993.

26. Miller G.F., Todd P.M., Hedge S.U., Designing neural networks using genetic algorithms, in Proceedings of the Third International Conference on Genetic Algorithms, San Meteo, С A: Morgan Kaufmann, 1989, pp.3 79-3 84.

27. Minsky M. N., Papert S., Perseptrons. Cambridge, MA: MIT Press, 1969.

28. Moody J., Darken C.J., Fast learning in networks of locally-tuned processing units,Neural Computation, vol.1, pp. 281-294, 1989.

29. Parker D. B. 1987. Second order back propagation: Implementing an optimal 0(n) approximation to Newton's method as an artificial newral network. Manuscript submitted for publication.

30. Pineda F. J. 1988. Generalization of backpropagation to recurrent and higher order networks. In Newral information processing systems, ed. Dana Z. Anderson, pp. 602-11. New York: American Institute of Phisycs.

31. Powell M.J.D., Radial basis functions for multivariable interpolation: A review, in IMA Conference on Algorithms for the Approximation of Functions and Data, Royal Military College of Science: Oxford University Press, 1987, pp. 143-167.

32. Powell M.J.D., The theory of radial basis functions approximation, in Advances of Numerical Analysis Oxford: Clarendon Press, 1992, pp. 105-210.

33. Prados D., A fast supervised learning algorithm for large multilayered neural networks, In Proceedings of 1993 IEEE International Conference on Neural Networks, San Francisco, vol.2, pp.778-782

34. Renals S., Rohwer R., Phoneme classification experiments using radial basis functions, in IJCNN: International Joint Conference on Neural Networks, pp.1^6-1-467, Piscataway, N. J. : IEEE, 1989.

35. Rosenblatt F. 1962. Principles of neurodynamics. New York: Spartan Books. (Русский перевод: Розенблатт Ф. Принципы нейродинамики. М.: Мир., 1965.)

36. Rumelhart D. Е., Hinton G. Е., Williams R. J. 1986. Learning internal reprentations by error propagation. In Parallel distributed processing, vol.1, pp. 318-62. Cambridge, MA: MIT Press.

37. Smalz R., Conrad M., Combining Evolution with apportionment: A new learning algorithm for neural nets, Neural Networks, vol. 7, no. 2, pp. 341-351, 1994.

38. Stornetta W. S., Huberman B. A. 1987. An improwed three-layer, backpropagation algorithm. In Proceedings of the IEEE First International Conference on Newral Networks, eds. M. Caudill and C. Butler. San Diego, CA: SOS Printing.

39. Whitehead B.A., Choate T.D., Cooperative-Competitive Genetic Evolution of Radial Basis Function Centers and Widths for Time Series Prediction, IEEE Transactions on Neural Networks, 1995.

40. Whitely D., Hanson T. Optimizing neural networks using faster, more accurate genetic search, Proceedings of the Third International Conference on Genetic Algorithms, San Meteo, CA: Morgan Kaufmann, 1989, pp.391-396.

41. Widrow B. 1959. Adaptive sampled-data systems, a statistical theory of adaptation. 1959 IRE WESCON Convention Record, part 4, pp. 88-91. New York: Institute of Radio Engineers.

42. Widrow В., HoffM. 1960. Adaptive switching circuits. I960 IRE WESCON Convention Record, pp. 96-104. New York: Institute of Radio Engineers.

43. Wilson S.W., Perseptron Redux: Emergence of structure, in Emergent Computation, MA: MIT Press, 1990, pp. 249-256.

44. Адлер Ю.П. Введение в планирование эксперимента. М.: Металлургия, 1969. 157 с.

45. Артамонов Г.Т., Тюрин В.Д. Топология сетей ЭВМ и многопроцессорных систем. М.: Радио и связь, 1991. 248 с.

46. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

47. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. 69 с.

48. Белкин А.Р., Левин М.Ш. Принятие решений, комбинаторные модели, аппроксимация информации. М.: Наука 1990.

49. Бентли Д. Жемчужины творчества программистов / Пер. с англ. М.: Радио и связь, 1990. 244 с.

50. Бонгард М.М. Проблема узнавания. М.: Наука, 1967. 320 с.

51. Боресков А.В., Шикин Е.В. Компьютерная графика. Динамика, реалистические изображения. М.: Диалог, МИФИ, 1995

52. Боресков А.В., Шикин Е.В., Шикина Г.Е. Компьютерная графика: первое знакомство. М.: Финансы и статистика, 1996. 176 с.

53. Вермишев Ю.Х. Основы автоматизации проектирования. М.: Радио и связь, 1988.

54. Вилкас Э.Й., Майменас Е.З. Решения: теория, информация, моделирование. М.: Радио и связь, 1981. 328 с.

55. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: Наука, 1986. 296 с.

56. Гардан И., Люка М. Машинная графика и автоматизация конструирования. Пер.с франц. М.: Мир, 1987. 272 с.

57. Гилой В. Интерактивная машинная графика. М.: Мир, 1981.

58. Головкин Б.А. Параллельные вычислительные системы. М.: Наука, 1980.

59. Голуб А.И. С и С++. Правила программирования. М.: БИНОМ, 1996. 272 с.

60. Горбань А.Н., Миркес Е.М. Логически прозрачные нейронные сети // Изв. ВУЗов. Приборостроение, 1996, Т. 39, № 1, С.64-67.

61. Горбань А.Н., Миркес Е.М. Оценки и интерпретаторы ответа для нейронных сетей двойственного функционирования// Изв. ВУЗов. Приборостроение, 1996, Т. 39, № 1,С. 5-.

62. Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высшая школа, 1980. с.384.

63. Зайченко Ю.П. Исследование операций. Киев: Вища школа, 1975. 320 с.

64. Зенкин А.А. Когнитивная компьютерная графика /Под ред. Д.А. Поспелова.4* М.: Наука, 1991. 192 с.

65. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика /Под ред. Г.М. Полищука. М.: Радио и связь, 1995. 224 с.

66. Интерактивная машинная графика: Структуры данных, алгоритмы, языки. Пер.с англ. М.: Мир, 1981. 384 с.

67. Каляев А.В., Мелихов А.Н., Курейчик В.М., Гузик В.Ф., Калашников В.А. Автоматизация проектирования вычислительных структур. Ростов н/Д: Изд-во РГУ, 1983.224 с.

68. Клейменов С.А., Павленко А.И., Рябов С.Н. Основы проектированияавтоматизированных технологических комплексов производства элементов РЭА// Учебное пособие. М.: Высшая школа, 1984. 120 с.

69. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. М.: Мир, 1978, 844 с.

70. Коновалов О.В. Алгоритм визуализации трехмерных графических сцен для применения в распределенных вычислительных системах кластерного типа// Известия ТРТУ, №2 (31), тематический выпуск «Интеллектуальные САПР».

71. Таганрог: ТРТУ, 2003. С. 78-81.

72. Коновалов О.В. Кооперативно-соревновательный алгоритм обучения сетей радиального базиса// Известия ТРТУ, №4 (8), тематический выпуск «Интеллектуальные САПР». Таганрог: ТРТУ, 2001. С. 174-177.

73. Коновалов О.В. Кооперативно-эволюционные алгоритмы обучения многослойных нейронных сетей прямого распространения// Известия ТРТУ, №4 (8), тематический выпуск «Интеллектуальные САПР». Таганрог: ТРТУ, 2001. С. 177-180.

74. Коновалов О.В. Моделирование объектов в трехмерном пространстве// Тезисы докладов РиЭвНХ. М.: МЭИ, 1998. С. 102.

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

76. Искусственные интеллектуальные системы» (IEEE AIS'02) и

77. Интеллектуальные САПР» (CAD-2002). Научное издание. М.: Физматлит, 2002. С. 474-479.

78. Коновалов О.В. Прикладной графический трехмерный редактор// Тезисы докладов сорок пятой студенческой научной конференции. Таганрог: ТРТУ, 1998. С. 82.

79. Коновалов О.В. Проблемы формирования трехмерных векторных структур// Известия ТРТУ, №2, тематический выпуск «Интеллектуальные САПР». Таганрог: ТРТУ, 1998. С. 274.А

80. Коновалов О.В. Разнесение непланарных графов, описанных в узлах решетки, по слоям, с проверкой условия планарности в каждом полученном слое// Известия ТРТУ, №2, тематический выпуск «Интеллектуальные САПР». Таганрог: ТРТУ, 1998. С. 276.

81. Коновалов О.В. Универсальный программный комплекс автоматизации проектирования нейронных сетей// Известия ТРТУ, №2 (31), тематический выпуск «Интеллектуальные САПР». Таганрог: ТРТУ, 2003. С. 82.

82. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука 1969. 368 с.

83. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР: ■fr Учебник для вузов. М.: Энергоатомиздат, 1987. 400 с.

84. Котов Ю.В. Как рисует машина. М: Наука, Гл.ред. физ.-мат.лит., 1988. 224 с.

85. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Целочисленное программирование. М.: Мир, 1977. 433 с.

86. Курейчик В.М. Генетические алгоритмы и их применение в САПР// Интеллектуальные САПР, меж. сб. Таганрог, 1995. С. 7-11.

87. Ларионов A.M., Майоров С.А., Новиков Г.И. Вычислительные комплексы, системы и сети// Учебник для вузов. JL: Энергоиздат. Ленингр. отделение, 1987.

88. Липский В. Комбинаторика для программистов/ Пер. с польского Евстигнеева В.А., Логиновой О.А. М.: Мир, 1988. 213 с.:ил.

89. Львовский Е.Н. Статистические методы построения эмпирических формул// Учеб.пособие для втузов. М., Высшая школа, 1988. 239 е.: ил.

90. Лэнгсам Й., Огенстайн М., Тетельбаум А. Структура данных для персональных ЭВМ. М.: Мир, 1989. 568 с.

91. Макаров И.М. и др. Теория выбора и принятия решений. М.: Наука 1982.

92. Математика и САПР: В 2-х кн.КнЛ.Пер.с франц. М.: Мир, 1988. 204 с.

93. Математика и САПР: В 2-х кн.Кн.2.Пер.с франц. М.: Мир, 1989. 264 с.

94. Миркес Е.М. Нейрокомпьютер. Проект стандарта. Новосибирск: Наука, Сибирская издательская фирма РАН, 1998, 337 с.

95. Миркин Б.Г. Проблема группового выбора. М.: Наука, 1974.

96. Митропольский А.К. Техника статистических вычислений. М.: Наука., 1971. 576 е.: ил.

97. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983.

98. Нейроинформатика / А.Н. Горбань, В.Л. Дунин-Барковский, А.Н. Кирдин, Е.М. Миркес, А.Ю. Новоходько, Д.А. Россиев, С.А. Терехов, М.Ю. Сенашова, В.Г. Царегородцев. Новосибирск: Наука, Сибирская издательская фирма РАН, 1998, 296 С.

99. Нечеткие множества и теория возможностей. Последние достижения. Пер. с англ. /Под ред. P.P. Ягера. М.: Радио и связь, 1986. 408 с.

100. Нильсон Н. Принципы искусственного интеллекта. М.: Радио и связь, 1985. 373 с.

101. Ньюмен У., Спрулл Р. Основы интерактивной машинной графики. М.: Мир, 1976.

102. Павлидис Т. Алгоритмы машинной графики и обработки изображений: Пер.с англ. М.: Радио и связь, 1986. 400 с.

103. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985.

104. Петерсен P. LINUX: Руководство по операционной системе/ пер. с англ. Киев: Издательская группа BHV, 1997. 688 с.

105. Подбельский В.В. Язык Си++// Учебное пособие. М.: Финансы и статистика, 1995. 560 с.

106. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением. М.: Знергоатомиздат,1983.

107. Пратт У., "Цифровая обработка изображений ", т. 1,2, М.: Мир, 1982.

108. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение / Пер.с англ. М.:Мир, 1989. 478 с.

109. Применение математических методов и ЭВМ. Планирование и обработка результатов эксперимента// Учебное пособие / Под общ. ред. Останина А.Н. Минск.: Вышэйшая школа., 1989. 218 с.

110. Программирование на Java с помощью Visual J++. / Пер. с англ. Филимонов А.Н. Минск: ООО «Попурри», 1998. 352 с.

111. Р. Дуда, П. Харт, Распознавание образов и анализ сцен. М.: Мир, 1976.

112. Разработка САПР. /Под ред. А.В. Петрова. М.: Высшая школа, 1990. Ш.Рамодин Д.A. Borland Jbuilder. Программирование на Java без проблем. М.:1. Нолидж», 1998. 288 с.

113. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика: Пер. с англ. М.: Мир, 1980. 476 с.

114. Роджерс Д. Алгоритмические основы машинной графики: Пер.с англ. М.:, 1989. 512 с.

115. Роджерс Д., Математические основы машинной графики, М.: Мир, 2001

116. Роджерс Д.Ф., Адаме Дж. Математические основы машинной графики/ Пер.с англ. М.: Машиностроение, 1980. 240 с.

117. Системы параллельной обработки: Пер.с англ. /Под ред. Д.Ивенса. М: Мир, 1985

118. Смирнов А.Д. Архитектура вычислительных систем: Учеб. пособие для вузов. М.: Наука. Гл. ред. физ.-мат. лит., 1990. 320 с.

119. Справочник по машинной графике в проектировании /Под ред. В.Е. Михайленко, А.А. Ляшенко. Киев: Буд1вельник, 1984. 184 с.

120. Страуструп Б. Язык программирования Си++. М.: Радио и связь, 1991. 352 с.

121. Сэлтон Г. Автоматическая обработка, хранение и поиск информации. М.: Сов. Радио, 1973. 560 с.

122. Уоссермен Ф. Нейрокомпьютерная техника: теория и практика: Пер. с англ. М.: Мир, 1992. 240с.

123. Ферради Д. Оценка производительности вычислительных систем. М.: Мир, 1981.

124. Фоли Дж., вэн Дэм А. Основы интерактивной машинной графики. М.: Мир, 1987.

125. Фоли Дж., Вэн Дэм А. Основы интерактивной машинной графики. В 2-х т. М.: Мир, 1985.

126. Цой С., Цхай С.М. Прикладная теория графов. Алма-Ата: Наука, 1971.

127. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. М.: ДИАЛОГ-МИФИ, 1995. 288 с.

128. Шикин Е.В., Боресков А.В., Зайцев А.А. Начала компьютерной графики. М.: ДИАЛОГ-МИФИ, 1993.

129. Шикин Е.В., Боресков А.В., Компьютерная графика. Полигональные модели. М.: ДИАЛОГ-МИФИ, 2000.

130. Шрейдер Ю.А. Равенство, сходство, порядок. М.: Наука, 1971. 376 с.

131. Ю. Тихомиров. Программирование трехмерной графики. Санкт-Петербург: BHV, 1998.