Введение к работе
Актуальность темы. Активная деятельность по отысканию приемлемых способов обобществления непрерывно растущего объема информации привела к созданию в начале 60-х годов XX века специальных программных комплексов, называемых системами управления базами данных (СУБД). Быстрое распространение сетей передачи данных, резкое увеличение объема внешней памяти ПК при ее удешевлении в 80-е годы способствовали широкому внедрению распределенных баз данных (РБД), являющихся сейчас доминирующими инструментами для создания приложений интенсивной обработки данных. Появление в последние годы новых вычислительных моделей и моделей ИТ-инфраструктуры, известных как среды облачных вычислений (Microsoft SQL Azure Database, Amazon Relational Database Service), приводит к необходимости по-новому ставить задачи проектирования, реализации и эксплуатации РБД. РБД функционируют сегодня в открытых системах и системах систем. Следствием этого является большая нестабильность режимов работы, эволюция РБД во времени, неполнота информации для проектирования и оптимизации, большое число стейкхолдеров с различными целями и требованиями.
В общей задаче проектирования РБД существенное значение имеет создание логической структуры (ЛС). Входными данными задачи синтеза ЛС РБД являются результаты концептуального проектирования, а также изначальные требования к функционалу системы, зафиксированные в техническом задании. Л С не зависит от СУБД и является основой для этапа физического проектирования РБД.
В современных условиях требуется отдельная программная подсистема для проектирования, анализа и оптимизации ЛС на различных этапах жизненного цикла РБД. Такая подсистема должна выполнять синтез оптимальной логической структуры (ОЛС) РБД или адаптировать существующую структуру к изменившимся условиям с учетом распределенной ГГ-инфраструктуры и обладать возможностью останова на субоптимальных
решениях при дефиците вьиислительных ресурсов или времени. Основой такой подсистемы являются алгоритмы для решения задачи синтеза ОЛС по определенному критерию эффективности.
Одним из критериев, часто используемых на практике, является минимум общего времени последовательной обработки множества запросов пользователей. Его важность определяется тем, что в системах обработки данных время является наиболее ценным ресурсом, а последовательная обработка запросов актуальна в системах со сложными бизнес-процессами, отдельные этапы которых выполняются различными пользователями.
Задача синтеза ОЛС по указанному выше критерию принадлежит к классу задач дискретной оптимизации и является NP-трудной нелинейной задачей целочисленного программирования. Все практически значимые методы решения данных задач используют эвристики и основаны на интеллектуальном поиске в обширном, но ограниченном пространстве решений задачи.
Наиболее известные методы решения задачи синтеза ОЛС РБД предложены в ряде работ, изданных в конце XX века. Аналитическую модель РБД рассматривали В.В. Кульба, А.Г. Мамиконов, А.А. Ашимов, В.В. Марасанов и др., методологию интеграции РБД - Б.П. Арсеньев. В.В. Кульба, С.С. Ковалевский и др. изложили методы упорядочения и оптимизации структур РБД на этапах предпроектного анализа, технического проектирования и эксплуатации, описали методы анализа и структуризации предметных областей пользователей и синтеза ОЛС РБД. В качестве метода синтеза ОЛС РБД здесь предложен эвристический метод сокращенного обхода дерева поиска (ЭМСО). Структурная организация ЭМСО не позволяет выделить достаточное количество процедур, допускающих параллельную реализацию, для того, чтобы она была эффективной. Из-за сложных взаимосвязей большая часть времени будет затрачена на обмен данными. Поэтому существует потенциальная возможность создания такого распределенного алгоритма, который, благодаря своей структуре, позволит добиться значительного ускорения в параллельном режиме. Кроме того, ЭМСО не обладает свойством устойчивости решения к
возмущениям входных данных задачи и возможностью останова на субоптимальных допустимых решениях задачи при дефиците вычислительных ресурсов или времени, что также является дополнительным аргументом в пользу создания нового алгоритма.
Труд Г.Г. Цегелика посвящен рассмотрению проблем оптимального размещения объектов ЛС РБД по узлам вычислительной сети (ВС). Им были предложены математические формулировки задач оптимального размещения с различными критериями эффективности. Однако, здесь структурная организация таблиц ЛС РБД считается уже известной и принадлежит к множеству входных данных задачи.
Быстрое развитие вычислительных технологий заставляет уделять большое внимание разработке эффективных моделей параллельных вычислений, что для алгоритмов, подобных ЭМСО, связано с дополнительными временными затратами на изменение самой модели и структурной организации алгоритма. Вопрос эффективности алгоритма можно рассматривать в двух аспектах: как уменьшение времени получения оптимального решения задачи в результате полного прогона алгоритма, и как уменьшение времени решения задачи за счет возможности останова на субоптимальном допустимом решении. Последний аспект относится к тем алгоритмам, которые обладают параметрами, способными повлиять на время решения задачи. Эффективность существующих алгоритмов решения задачи синтеза ОЛС РБД может рассматриваться в рамках первого аспекта, в то время как вопрос эффективности алгоритмов, основанных на методах искусственного интеллекта, покрывает оба аспекта.
На данный момент в области проектирования ОЛС РБД существует недостаток эффективных алгоритмов синтеза ОЛС РБД или ее адаптации к изменившимся условиям. Это является стимулом к поиску новых практических решений, основанных на интеграции методов параллельных вычислений с методами, использующими искусственные нейронные сети (ИНС/НС) и другие методы искусственного интеллекта такие как генетические (ГА) и эволюционные алгоритмы (ЭА).
Данная работа посвящена проблеме синтеза ОЛС РБД. Для ее решения предложен параллельный нейросетевои алгоритм, построенный на основе нейронных сетей Хопфилда (НСХ) с параллельным табу-поиском в качестве механизма смены состояний сети.
Цель диссертационной работы заключается в разработке и апробации метода решения задачи синтеза ОЛС РБД с использованием критерия минимума общего времени последовательной обработки множества запросов пользователей. Основой нового метода должны стать нейросетевые алгоритмы дискретной оптимизации, с возможностью интеграции с распределенной СУБД (РСУБД) в единую распределенную систему синтеза и структурной адаптации. Особенность такой системы заключается в том, что она должна быть способна не только синтезировать ЛС для впервые создаваемой РБД, но и давать рекомендации по перестройке ЛС в соответствии с новыми требованиями.
Для достижения поставленной цели решены следующие задачи.
-
Изучение и анализ существующих формализованных описаний структур РБД, математических моделей синтеза ОЛС РБД, известных методов решения задач синтеза ОЛС, а также исследование нейросетевых подходов к решению задач оптимизации с целью выбора наиболее подходящего типа ИНС.
-
Проектирование и реализация ЭА для решения поставленной задачи, основанного на использовании ИНС подходящего типа и ГА. Апробация разработанного алгоритма на модельных задачах.
-
Проектирование и реализация механизма табу-поиска в рамках построенного нейросетевого алгоритма с целью повышения качества получаемых решений.
-
Проектирование и реализация распределенной модели разработанного нейросетевого алгоритма с целью уменьшения его временной сложности. Тестирование алгоритма на модельных задачах.
-
Апробация распределенного нейросетевого алгоритма на задаче оптимизации ЛС реальной БД, используемой в международной 1Т-компании.
Объектом исследования стали объекты логической структуры однородной распределенной базы данных и методы их формального описания.
Предметом исследования являются алгоритмические методы синтеза логических структур распределенной базы данных на основе интеграции методов параллельных вычислений с методами икусственного интеллекта.
В процессе выполнения работы использовались следующие методы проведения исследований: при изучении и анализе структур РБД в диссертации использовались элементы теории множеств и исследования операций, при построении алгоритмов синтеза ОЛС РБД - математический аппарат ИНС, схемы ГА оптимизации с элементами теории вероятностей, методы эволюционного программирования и технологии табу-поиска.
Реализация программного обеспечения была выполнена с использованием языков программирования C++ и Matlab, а также библиотек высокопроизводительных параллельных вычислений Microsoft НРС Pack 2008 SDK и LAM/MPI. Для визуализации результатов экспериментов использовались возможности систем Matlab и Microsoft Excel.
Научная новизна представленной работы состоит в следующем:
-
предложена формулировка задачи синтеза оптимальной логической структуры распределенной базы данных в нейросетевых переменных с учетом семантической смежности групп данных, отличающаяся применением нейросетей Хопфилда, что позволяет использовать при решении табу-поиск;
-
разработан эволюционный алгоритм решения задачи п. 1, основанный на нейронных сетях Хопфилда, обладающий свойством устойчивости решения к возмущениям входных данных задачи и отличающийся наличием возможности останова на субоптимальных допустимых решениях при дефиците вычислительных ресурсов или времени;
-
разработан распределенный алгоритм модифицированного табу-поиска для задачи п. 1, находящий решения лучшего качества по сравнению с эвристическим методом сокращенного обхода дерева поиска, предназначенный
для ускорения процесса синтеза и отличающийся динамическим определением структуры Табу под-машин.
Практическая ценность работы состоит в том, что разработанные НС-алгоритмы оптимизации позволяют получать качественно лучшие решения задач синтеза ОЛС РБД по сравнению с ЭМСО. Средние результаты, полученные с помощью предлагаемых диссертантом алгоритмов, на модельной задаче большей размерности превосходят результаты, полученные с помощью ЭМСО, на 23,6%. Наряду с синтезом ОЛС РБД, построенные алгоритмы позволяют получить рекомендации по перестройке уже существующей ЛС в случае изменения характеристик предметной области с указанием при этом процента улучшения качества решения. Кроме того, диссертантом предложена и реализована инженерная идея учета семантической смежности групп данных в процессе синтеза ОЛС РБД. Распределенный вариант НС-алгоритма оптимизации, основанного на модифицированном табу-поиске, позволяет ускорить процесс синтеза ОЛС РБД.
Результаты диссертационной работы внедрены в производственную деятельность международной ГГ-компании ООО «Датавижн НН» и в учебный процесс НИУ ВШЭ - Нижний Новгород по курсу «Современные средства построения интеллектуальных систем» направления магистратуры 080500.68 «Бизнес-информатика».
Апробация диссертации. Основные положения и результаты диссертационной работы докладывались и обсуждались на 1-ой Международной конференции по бизнес-информатике (The 1st International Conference on Business Informatics, BI-2007) (Звенигород, 2007), I Сессии научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и систем» в рамках 5-ой Всероссийской межвузовской конференции молодых ученых (КМУ-V) (Санкт-Петербург, СПбГУ ИТМО, 2008), 7-ой Международной Конференции по Компьютерным Системам и Приложениям (The 7th ACS/IEEE International Conference on Computer Systems and Applications, AICCSA-09) (Рабат, Марокко, 2009), Международной
молодежной научной школе «Исследование операций и приложения в логистике» (НИУ ВШЭ - Нижний Новгород, 2010), 4-ой Международной конференции «Распознавание образов и искусственный интеллект» (The 4th International Conference on Pattern Recognition and Machine Intelligence, PReMI-2011) (Москва, НИУ ВШЭ, 2011), X Всероссийской научной конференции «Нейрокомпьютеры и их применение» (Москва, МГППУ, 2012), а также на ряде научных семинаров кафедры «Информационные системы и технологию) НИУ ВШЭ и компании MeraLabs. Кроме того, диссертантом получен диплом I степени на I Сессии научной школы-практикума молодых ученых и специалистов «Технологии высокопроизводительных вычислений и систем» (КМУ-V) в секции «Параллельные технологии искусственного интеллекта обработки данных и имитационного моделирования».
Публикации. Основные результаты опубликованы в 12 работах, в том числе 1 — в журнале, входящем в список ВАК, а именно: «Научно-технический вестник СПбГУ ИТМО. Технологии высокопроизводительных вычислений и компьютерного моделирования», 1 - в сборнике трудов конференции ACS/IEEE International Conference on Computer Systems and Applications 2009, и 1 - в международном журнале Lecture Notes in Business Information Processing, включенных в систему цитирования Scopus. Кроме того, программа «Программная реализация нейросетевых алгоритмов синтеза оптимальной логической структуры распределенной базы данных», реализующая разработанные диссертантом алгоритмы, зарегистрирована в Фонде Алгоритмов и Программ Сибирского Отделения Российской Академии Наук (ФАП СО РАН) под№РК12018 от 26.10.2012.
Основные положения, выносимые на защиту.
-
Разработанный эволюционный алгоритм оптимизации (НС-ГА-алгоршпм), основанный на ИНС Хопфилда и генетических алгоритмах, используемых для оптимизации функционирования ИНС.
-
Созданный нейросетевой алгоритм оптимизации (ТМ-алгоритм), основанный на модифицированном табу-поиске.
-
Разработанный распределенный нейросетевой алгоритм оптимизации (РТМ-алгоритм), основанный на модифицированном табу-поиске.
-
Выполненная программная реализация разработанных алгоритмов оптимизации и их тестирование на модельных задачах.
-
Проведенный сравнительный анализ созданных НС-алгоритмов и ЭМСО с точки зрения качества получаемых решений и быстродействия.
-
Выполненная оптимизация ЛС реальной БД, используемой в международной 1Т-компании, с помощью реализованной модели РТМ-алгоритма.
Структура и объем работы. Диссертация включает в себя введение, четыре главы основного текста, заключение, список используемой литературы из 99 источников и пять приложений. Работа изложена на 184 страницах текста, включающих 22 рисунка и 9 таблиц.
