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

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

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

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

Цель работы.

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

Задачи исследования.

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

1. Выполнить сравнительный анализ существующих методов и систем кластеризации проектных документов;

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

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

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

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

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

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

Методы исследования.

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

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

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

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

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

4. Разработка методики управления адаптивным параметризованным генетическим алгоритмом.

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

Все перечисленные положения являются новыми.

Практическая значимость.

На основе разработанных методов и алгоритмов создан программно-алгоритмический комплекс для решения задачи кластеризации информационных ресурсов. При построении программного комплекса использовался объектно-ориентированный язык Java и СУБД MS SQL Server. Программная система генетической кластеризации прошла апробацию в ФНПЦ ОАО «НПО МАРС».

Основания для выполнения работы.

Данная научная работа выполнялась в рамках тематического плана научных исследований Федерального агентства по образованию в 2005, 2006, 2007, 2008 гг., была поддержана грантами РФФИ № 06−01−2 012 и 601 014 087 в 2006 г., № 08−01−97 006 в 2008 г., ряд задач исследования решался в рамках х/д НИР № 100/05 УлГТУ по заказу ФНПЦ ОАО НПО МАРС.

Достоверность результатов диссертационной работы.

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

Апробация результатов исследования.

Основные положения и результаты диссертации докладывались, и обсуждались на: «Interactive Systems and Technologies» (Ульяновск, 2007, 2009), на всероссийской конференции «Проведение научных исследований в области обработки, хранения, передачи и защиты информации ОИ-2009» (Ульяновск, 2009), на одиннадцатой и двенадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2008 (Дубна, 2008), КИИ-2010 (Тверь, 2010), на научных сессиях МИФИ-2007, 2008 (Москва, 2008), на второй всероссийской научной конференции с международным участием «Нечеткие системы и мягкие вычисления» НСМВ-2008 (Ульяновск, 2008), на семинаре с международным участием «Интеллектуальный анализ временных рядов» по результатам НИР, поддержанной ФЦП, проект № 02.740.11.5021 (Ульяновск, 2010), на международных «Конференции по логике, информатике, науковедению» (Ульяновск 2004, 2005, 2006, 2007).

Основные положения неоднократно докладывались и обсуждались на научно-технических конференциях УлГТУ «Вузовская наука в современных условиях».

Структура и объем диссертационного исследования.

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

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

В первой главе содержится обзор состояния исследований в области кластеризации. Приведены определения информационного поиска и информационного ресурса. Формализована задача кластеризации ИР. Поясняется структура задачи. Проведена классификация и анализ алгоритмов и методов кластеризации.

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

Также приведены методики оценки качества автоматической кластеризации, статистические формулы функционалов качества.

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

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

Сформулированы особенности кластеризации ИР. Приведена адаптация стандартного генетического алгоритма к решению задачи кластеризации.

Представлен алгоритм кластеризации ИР на основе схемы генетической адаптации. Описана разработка адаптивного генетического алгоритма.

Сформирована методика настройки параметров генетической кластеризации.

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

В четвертой главе приведены результаты вычислительных экспериментов.

Описаны эксперименты по оценке качества кластеризации в сравнении с экспертной классификацией, проведенной сотрудником ФНПЦ ОАО НПО «МАРС». Эксперименты проводились на выборках объемом 65, 265 и 5013 9 документов. Описаны эксперименты по исследованию эффективности предложенного адаптивного генетического алгоритма.

На основе проведенных экспериментов рассчитана корреляция между величинами для обоснования предложенной в Главе 2 методики настройки параметров.

Проведено сравнение результатов кластеризации с помощью ГА с результатами кластеризации с помощью алгоритма К-средних.

Выводы по главе.

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

Эксперименты с модифицированным генетическим алгоритмом проведены в три этапа:

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

— по виду документов — 17 классов;

— по тематике работ -22 класса;

— по классу документации — 3 класса;

— по разделу документации — 22 класса.

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

— по виду документов — 14 классов;

— по тематике работ — 38 классов;

— по классу документации — 2 класса;

— по разделу документации — 14 класса.

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

— по виду документов — 51 классов;

— по тематике работ — 27 класса;

— по классу документации — 3 класса;

— по разделу документации — 26 классов.

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

Следовательно, по результатам вычислительных экспериментов можно сделать первый вывод из данной главы:

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

Эксперименты по оценке эффективности адаптивного генетического алгоритма проводились на выборке из 65 документов, содержащей документы преимущественно организационно-нормативного характера. Ранее комплект документации был классифицирован архивариусом-экспертом. Для обеспечения сопоставимости результатов, 65 документов всегда разбивались на 16 классов, что соответствует экспертной кластеризации по видам документации.

Было проведено 150 экспериментов, из них:

1. С использованием режима «Управление сходимостью через оператор мутации" — 75 экспериментов.

• С длиной стагнации 3−25 экспериментов.

• С длиной стагнации 4−25 экспериментов.

• С длиной стагнации 5−25 экспериментов.

2. С использованием режима «Управление сходимостью через размер „элиты“» — 75 экспериментов.

• С длиной стагнации 3−25 экспериментов.

• С длиной стагнации 4−25 экспериментов.

• С длиной стагнации 5 — 25 экспериментов.

В результате проведенных экспериментов можно придти ко второму выводу из данной главы: при использовании адаптивного генетического алгоритма среднее сокращение количества проходов генетического алгоритма снизилось в среднем на 30% .

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

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

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

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

При увеличении числа кластеров наблюдается существенное преимущество адаптивного генетического алгоритма.