BC/NW 2008, №2 (13): 10.2
Развитие АСНИ «Graph Model Workshop» для исследований в области
структурного анализа
Кохов В.А., Незнанов А.А., Ткаченко С.В.
(Москва, Московский энергетический институт (ТУ), Россия)
В докладе рассматриваются основные направления развития автоматизированной системы научных исследований «Graph Model Workshop», её новые функциональные возможности и варианты их использования.
Непрерывно повышающаяся актуальность исследования графовых моделей систем (ГМС), являющихся математическими моделями структур объектов и процессов, актуализирует развитие инструментов, позволяющих повысить эффективность такого исследования. Мы рассмотрим инструменты в виде программных средств. Отдавая должное универсальным математическим пакетам (Maple [1], MathLab и др.), следует признать, что их использование в качестве автоматизированных систем научных исследований (АСНИ) в конкретной проблемной области зачастую оказывается неудобным и требует обязательной (и трудоёмкой) настройки. Те же соображения относятся и к классу программных средств учебного назначения (ПСУН), где ещё большую значимость приобретают вопросы взаимодействия с пользователем и начального обучения работе с программой. Причём исследователь, в отличие от студента, может позволить себе потратить значительные усилия на доскональное изучение своего рабочего инструмента. Поэтому понятен интерес к проблемно-ориентированным АСНИ и ПСУН. В качестве показательного примера поиска компромисса можно привести АСНИ GAP (Groups, Algorithms, Programming) для исследований в области дискретной математики.
Возвратимся к вопросам исследования ГМС, каковые обычно в целом обозначают структурным анализом. Бурное развитие вычислительных ветвей дискретной математики (теории групп, теории графов, комбинаторики и др.) началось в 1970-х годах. Достигнутый за 20 лет уровень можно оценить, например, по [2-4] (число работ огромно!). На тот момент ещё не было создано ни одной комплексной АСНИ. Зато в последующие годы поток фундаментальных работ уменьшился, но начались попытки разных авторов создать действительно используемые АСНИ. Но прогресс очевиден лишь в области химической информатики. В других сферах (теоретические исследования, структурная лингвистика, методы искусственного интеллекта и др.), при наличии большого числа разработок достигнутый уровень явно недостаточен и определяется сложностью стоящих перед разработчиками задач. В последние годы развитие методов прикладной (вычислительной) теории графов [5], вычислительной теории групп [6] и других наук позволило по новому взглянуть на проблемы структурного анализа. Быстрый же прогресс вычислительной техники обеспечил условия для полноценной научной деятельности даже на персональном компьютере, несмотря на то, что базовые задачи структурного анализа относятся к классу NP-полных. Поэтому создание и развитие АСНИ и ПСУН в области структурного анализа следует признать актуальным и значимым.
На кафедре Прикладной математики МЭИ (ТУ) с начала 1990-х годов плодотворно занимаются вопросами структурного анализа. В современном виде концепция АСНИ для компьютерной поддержки исследований в области прикладной теории графов устоялась к 1998 [7], когда в научной группе Кохова В.А. была создана первая версия АСНИ «Graph Model Workshop» (GMW). GMW интегрировала большинство идей и наработок научной группы. Затем концепция была расширена, что позволило сформулировать основные особенности архитектуры GMW:
1) открытость – выделение ядра GMW, свободное наращивание функциональности АСНИ на основе «расширений» (plugins);
2) ориентированность на вычислительные эксперименты, проводимые автоматически по некоторой схеме запуска расширений;
3) работа с базами структурной информации (БСИ, которая делится на базу ГМС и базу результатов вычислительных экспериментов) через выделенный уровень абстракции данных – СУБСИ «DCS»;
4) интеграция интерактивной визуальной и автоматической пакетной обработки ГМС в едином интерфейсе с пользователем;
5) настройка на проблемные области путём изменения интерпретации элементов ГМС с соответствующей визуализацией;
6) обязательное наличие подсистемы эмпирического анализа вычислительной сложности алгоритмов («Полигон»).
Версия 3.0 была выпущена в 2003 году. Затем в течении длительного времени никаких принципиальных изменений в ядро GMW не вносилось. В основном создавались новые расширения, дорабатывался программный интерфейс их подключения к ядру, исправлялись ошибки, на базе GMW разрабатывались различные ПСУН. Но с усложнением решаемых задач, изменением аппаратуры и программного окружения, наработкой значительной алгоритмической базы потребовался качественный скачок. В докладе рассматривается следующая версия GMW 4.0 с большим количеством кардинальных изменений в ядре системы.
Переход к четвёртой версии ядра GMW затрагивает почти всю функциональность АСНИ. Новая версия системами управления БСИ DCS 5.0 использует 64-битные индексы, что позволяет обрабатывать таблицы в базах структурной информации, размер которых превосходит 2 ГБ. Это дало возможность проводить вычислительные эксперименты на сотнях миллионах структур, оперирующие большим объёмом входных/выходных данных, но потребовало разработки нового формата баз структурной информации. При этом сохранена полная совместимость с БСИ предыдущей версии, а если позволяет размер таблиц, то можно свободно конвертировать базы из одного формата в другой.
Сдвиг к концепции многоэтапных вычислительных экспериментов привёл к закономерному появлению режима запуска расширений без ГМС на входе, так как не на каждом этапе эксперимента необходимо обращение к структурной информации. Это позволило намного стройней и эффективней реализовать подсистему уточняемого структурного поиска в БСИ. Также с этим связано появление возможности импорта/экспорта отдельных таблиц базы данных результатов в различных форматах.
Серьёзное практическое использование взвешенных графов из различных проблемных областей актуализировало создание механизмов, скрывающих разнообразие возможных весов вершин и рёбер от разработчиков расширений. Так появилась подсистема работа с произвольными наборами весов вершин и рёбер ГМС на основе массивов различения весов, преобразующая любой набор значений весов в уникальное целое число в пределах базы ГМС (рис. 1).
Рис. 1. Окно мастера ввода параметров
расширения для задания набора весов
Подсистема «Fragments-Symmetry-Similarity», позволяющая анализировать группу автоморфизмов ГМС (то есть расположение вершин и более крупных фрагментов в топологии ГМС), перешла на использование намного более эффективных и универсальных алгоритмов.
Некоторые дополнительные изменения четвёртой версии: потеряна совместимость с ОС Windows 95/98, но приобретена полная совместимость с Windows Vista (версия 3.5 работоспособна в Windows Vista); ускорена работа с памятью, что проявляется при работе с крупными ГМС; интерфейс с пользователем стал удобнее и эффективнее.
Впервые появилась реальная возможность конструктивного перечисления и анализа орграфов, число которых намного превосходит число графов с тем же числом вершин. Единообразное представление взвешенных ГМС с точки зрения расширений GMW позволило создать универсальный набор алгоритмов различения ГМС произвольного типа с произвольными весами вершин и рёбер (в настоящий момент дорабатывается).
Реализация новых алгоритмов позволила использовать новые методы анализа сложности и сходства ГМС, особенно востребованные в области химической структурной информатики [8].
В докладе приводятся и другие варианты использования новых возможностей. Это позволяет заключить, что реализация новых расширений, использующих потенциал новой версии ядра АСНИ «Graph Model Workshop», обеспечит ещё большую отдачу от проведённых изменений.
ЛИТЕРАТУРА
1.
Кирсанов М.Н. Графы в Maple. – М. : Физматлит, 2007. –
168 с.
2. Кристофидес
Н. Теория графов. Алгоритмический подход. – М. : Мир, 1978. – 432 c.
3. Исследования
по алгебраической теории комбинаторных объектов. Под ред. Фараджева И.А. – М. :
ВНИИСИ, 1985. – 187 с.
4. Нечепуренко
М.И., Попков В.К., Майнагашев С.М., Кохов В.А. и др. Алгоритмы и программы
решения задач на графах и сетях. – Новосибирск : Наука, 1990. – 515 с.
5. Касьянов
В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и
применение. – СПб.: БХВ-Петербург, 2003. – 1104 с.
6.
Ákos Seress. Permutation
Group Algorithms. –
7.
Кохов В.А., Ткаченко С.В. ППП для решения
базовых задач структурной информатики с визуальным редактированием и
автоматической прорисовкой структур систем. // Доклады МНТК «Информационные
средства и технологии». (МФИ-98), Т3, Москва, 1998. – С. 48-53.
8. Кохов В.А., Незнанов А.А., Ткаченко С.В. Программные средства для исследования сложности и сходства графовых моделей систем. // Труды ИВМиМГ, Информатика, 7, Новосибирск, 2007. – с. 268-273.