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

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

Карпунина Маргарита Евгеньевна

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

Специальность 05.13.01. - «Системный анализ, управление и обработка информации (в науке и промышленности)» по техническим наукам

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

? О ДЕК 2012

Нижний Новгород - 2012 г.

005047740

Работа выполнена на кафедре «Информационные системы и технологии» Национального исследовательского университета «Высшая школа экономики» -Нижний Новгород

Научный руководитель: кандидат технических наук, доцент

Бабкин Эдуард Александрович

Официальные оппоненты: Мисевич Павел Валерьевич, доктор технических

наук, доцент, НГТУ им. P.E. Алексеева, профессор Шилов Николай Германович, кандидат технических наук, доцент, СПИИРАН, старший научный сотрудник

Ведущая организация: Государственное учреждение «Научно-

исследовательский институт прикладной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского Министерства образования РФ», г. Нижний Новгород

Защита диссертации состоится « 27 » декабря 2012 года в Л часов в ауд. 1258 на заседании диссертационного совета Д 212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603600, г. Нижний Новгород, ул. Минина, 24.

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

Автореферат разослан « 26 » ноября 2012 года. Ученый секретарь

диссертационного совета //' Суркова Анна Сергеевна

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

Актуальность темы. Активная деятельность по отысканию приемлемых способов обобществления непрерывно растущего объема информации привела к созданию в начале 60-х годов XX века специальных программных комплексов, называемых системами управления базами данных (СУБД). Быстрое распространение сетей передачи данных, резкое увеличение объема внешней памяти ПК при ее удешевлении в 80-е годы способствовали широкому внедрению распределенных баз данных (РБД), являющихся сейчас доминирующими инструментами для создания приложений интенсивной обработки данных. Появление в последние годы новых вычислительных моделей и моделей ИТ-инфраструктуры, известных как среды облачных вычислений (Microsoft SQL Azure™ Database, Amazon Relational Database Service), приводит к необходимости по-новому ставить задачи проектирования, реализации и эксплуатации РБД. РБД функционируют сегодня в открытых системах и системах систем. Следствием этого является большая нестабильность режимов работы, эволюция РБД во времени, неполнота информации для проектирования и оптимизации, большое число стейкхолдеров с различными целями и требованиями.

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

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

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

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

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

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

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

Труд Г.Г. Цегелика посвящен рассмотрению проблем оптимального размещения объектов ЛС РБД по узлам вычислительной сети (ВС). Им были предложены математические формулировки задач оптимального размещения с различными критериями эффективности. Однако, здесь структурная организация таблиц ЛС РБД считается уже известной и принадлежит к множеству входных данных задачи.

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

На данный момент в области проектирования ОЛС РБД существует недостаток эффективных алгоритмов синтеза ОЛС РБД или ее адаптации к изменившимся условиям. Это является стимулом к поиску новых практических решений, основанных на интеграции методов параллельных вычислений с методами, использующими искусственные нейронные сети (ИНС/НС) и другие методы искусственного интеллекта такие как генетические (ГА) и эволюционные алгоритлт (ЭА).

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

Цель диссертационной работы заключается в разработке и апробации метода решения задачи синтеза ОЛС РБД с использованием критерия минимума общего времени последовательной обработки множества запросов пользователей. Основой нового метода должны стать нейросетевые алгоритмы дискретной оптимизации, с возможностью интеграции с распределенной СУБД (РСУБД) в единую распределенную систему синтеза и структурной адаптации. Особенность такой системы заключается в том, что она должна быть способна не только синтезировать ЛС для впервые создаваемой РБД, но и давать рекомендации по перестройке ЛС в соответствии с новыми требованиями.

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

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

2. Проектирование и реализация ЭА для решения поставленной задачи, основанного на использовании ИНС подходящего типа и ГА. Апробация разработанного алгоритма на модельных задачах.

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

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

5. Апробация распределенного нейросетевого алгоритма на задаче оптимизации ЛС реальной БД, используемой в международной 1Т-компании.

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

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

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

Реализация программного обеспечения была выполнена с использованием языков программирования С++ и Matlab, а также библиотек высокопроизводительных параллельных вычислений Microsoft НРС Pack 2008 SDK и LAM/MPI. Для визуализации результатов экспериментов использовались возможности систем Matlab и Microsoft Excel.

Научная новизна представленной работы состоит в следующем:

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

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

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

для ускорения процесса синтеза и отличающийся динамическим определением структуры Табу под-машин.

Практическая ценность работы состоит в том, что разработанные НС-алгоритмы оптимизации позволяют получать качественно лучшие решения задач синтеза ОЛС РБД по сравнению с ЭМСО. Средние результаты, полученные с помощью предлагаемых диссертантом алгоритмов, на модельной задаче большей размерности превосходят результаты, полученные с помощью ЭМСО, на 23,6%. Наряду с синтезом OJIC РБД, построенные алгоритмы позволяют получить рекомендации по перестройке уже существующей JIC в случае изменения характеристик предметной области с указанием при этом процента улучшения качества решения. Кроме того, диссертантом предложена и реализована инженерная идея учета семантической смежности групп данных в процессе синтеза ОЛС РБД. Распределенный вариант НС-алгоритма оптимизации, основанного на модифицированном табу-поиске, позволяет ускорить процесс синтеза ОЛС РБД.

Результаты диссертационной работы внедрены в производственную деятельность международной IT-компании ООО «Датавижн НН» и в учебный процесс НИУ ВШЭ - Нижний Новгород по курсу «Современные средства построения интеллектуальных систем» направления магистратуры 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. Разработанный эволюционный алгоритм оптимизации (НС-ГА-алгоритм), основанный на ИНС Хопфилда и генетических алгоритмах, используемых для оптимизации функционирования ИНС.

2. Созданный нейросетевой алгоритм оптимизации (ТМ-алгоритм), основанный на модифицированном табу-поиске.

3. Разработанный распределенный нейросетевой алгоритм оптимизации (РТМ-алгоритм), основанный на модифицированном табу-поиске.

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

5. Проведенный сравнительный анализ созданных НС-алгоритмов и ЭМСО с точки зрения качества получаемых решений и быстродействия.

6. Выполненная оптимизация ЛС реальной БД, используемой в международной 1Т-компании, с помощью реализованной модели РТМ-алгоритма.

Структура и объем работы. Диссертация включает в себя введение, четыре главы основного текста, заключение, список используемой литературы из 99 источников и пять приложений. Работа изложена на 184 страницах текста, включающих 22 рисунка и 9 таблиц.

Диссертационная работа выполнена при поддержке исследовательского проекта № 10-04-0009, поддерживаемого научным фондом НИУ ВШЭ.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Постановка задачи синтеза ОЛС РБД формулируется следующим образом: по известным характеристикам множеств пользователей РБД, узлов ВС, групп данных канонической структуры РБД и детерминированных запросов необходимо определить: а[ ЛС РБД в виде множества типов логических записей

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

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

Математическая постановка задачи предложена В.В. Кульбой и имеет вид:

при ограничениях на

/ _

• число групп в составе ЛЗ = где Г, - максимальное количество групп в / -й записи; (2)

т _

• однократность включения групп в записи £х„ = 1,V/ = 1,/; (3)

1

• длину формируемой ЛЗ X! А^о 2 в,г, где в„ - максимально допустимая

м

длина / -го типа записи, определяемая техническими характеристиками сервера г -го узла ВС; (4)

• общее число синтезируемых ЛЗ, размещенных на сервере г-го узла ВС

г

Т.У'г-Ку где К - максимальное количество ЛЗ, поддерживаемых локальной

СУБД/--го узла; (5)

• объем доступной внешней памяти серверов ВС для хранения локальных БД

г /

Е2>„ (6)

/-1 м

• требуемый уровень информационной безопасности системы хихп = 0, для заданных групп данных ^ и ¿¡!; (7)

• суммарное время обслуживания оперативных запросов на серверах ¿¿Г+'ч^тр> для заданных <2Р&<2, где Тр - допустимое время

гг= 1 1-1

обслуживания р -го оперативного запроса. (8)

Здесь Т - число ЛЗ; £., = {*/, е{0,1},/ = й7,< = йг}, = 1, если группа

данных / включена в ЛЗ /; У = (у,,е{0,1},* = й> = Щ}, у„= 1, если ЛЗ I

размещена на узле г ВС. Переменная г'п определяет типы ЛЗ, используемых р -

/

м запросом на сервере г2-го узла ВС: = 1, если ^У^*« -1; = 0> если

¡«1

¿у,,.^*,, = 0. Переменная определяет множество узлов-серверов ЛБД, к

(=1

Т I

которым обращается р-й запрос: если > 1; г(„. = 0, если

1=] м

Т I

м^х,, = о. - коэффициент, учитывающий наличие служебной

1=1 /=1

информации в записи. Другие характеристики указаны в Таб.1.

Таб. 1. Формализованные описания характеристик предметной области задачи

Наименование Обозначение

Характеристики канонической структуры РБД

Множество групп данных Е° z:\dfli = 1,/}

Вектор длин групп Р = {А}

Вектор количества экземпляров в группах п = {-,}

Матрица семантической смежности групп Аа = |а*. |, где а*. = 1, если существует

данных семантическая связь между ' -й и / -й группами, а* = 0 — в противном случае

Характеристики запросов пользователей

Множество запросов 0 = {д,/р = 1Ро}

Матрица использования групп данных при выполнении запросов где мРр1=\, если р-й запрос использует в процессе выполнения ;-ю группу, = 0 - в противном случае

Матрица частот использования запросов пользователями где - частота использования пользователем к запроса р

Характеристики пользователей

Множество пользователей и = {и„1к = 1,К0)

Матрица прикрепления пользователей к узлам ВС N = 1^1, где ^=1, если к- й пользователь прикреплен к г-у узлу ВС, \'1г = 0 - в противном случае

Матрица использования запросов пользователями РБД Фе=||й®||, где если к- й пользователь использует р -й запрос, (,°?Р = 0 - в противном случае

Характеристики узлов ВС

Множество узлов ВС *"={»!,./Г = 1,4,}

Вектор объемов памяти на серверах ВС, доступных пользователю Нш° = {|7,ая'}, где - величина доступной памяти на сервере г -го узла ВС

Усредненные исходные временные характеристики

Среднее время сборки блока данных при формировании массива данных запроса

Среднее время формирования одного подзапроса

Среднее время выбора маршрута, установления логических соединений между узлами г, и г2 1ГЛ

Среднее время передачи одного блока данных запроса с узла г, на узел гг по кратчайшему пути 'Л

Среднее время доступа к файлам ЛБД и поиска в них требуемых логических записей

Среднее время обработки одной логической записи на узле г2, зависящее от производительности сервера <г2

Принадлежность рассматриваемой задачи к классу ИР делает метод

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

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

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

Решение поставленной задачи (1) разделено на два этапа. Для каждого из них строится своя модель НСХ.

Для представления задачи в терминах ИНС каждый нейрон снабжен двумя индексами, которые соответствуют группе данных и номеру ЛЗ - для этапа 1, и номеру ЛЗ и номеру узла ВС - для этапа 2. Значение аксона нейрона OUTx,= 1 на этапе 1 показывает, что группа данных х будет включена в /-ый тип ЛЗ. Все выходы OUTx, имеют бинарную природу.

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

S,=t Z tour, -(OUTy,-alf -> min . (9)

/=1 ДГ-1 y=i y*x

На этапе 1 осуществляется синтез типов ЛЗ с учетом матрицы семантической смежности групп данных и ограничений (2), (3), (7). Диссертантом предложена модель НСХ для этапа 1 с функцией энергии, равной

(■ ' /Гя / , 1 >ГДе (10>

■{тсотр_£ггу +тсотр_£г^)уоиТх1-ОиГч+г£1 ]Г - ■ •

2 2-F,

у•*

OUT,

1) матрица весовых коэффициентов ЦТ м>х1у1 =-А, ■8Х1,-(1-8/.)+ Л, • л • -)• (2 • < - 0~ А • • ('псотр_ёГху + тсотр_gryx), где 5,_, - символ Кронекера;

2) порог нейрона х1: 7\ =

I. У*'

Результатом решения этапа 1 является матрица X

(/*Г)

На этапе 2 осуществляется безызбыточное размещение синтезированных типов ЛЗ в узлах ВС с учетом ограничений (4) - (б), (8). Диссертантом предложена модель НСХ для этапа 2 с функцией энергии, равной

е = ~2± I £ I [-Л-^-О-^)]-^,,-^,^ £

I 2 '1 = 1 '2=1 ,¡=1 ,,=1

V

Б2-Уо

V/ N с2 й2-\|/0 ^ , ч •(',;"'+/„)

1

, где (11)

■от..

1) матрица весовых коэффициентов \у = (и<,г,у): у,, = -А2-8,, (1-8 ), где 8,л - символ Кронекера;

2) порог нейрона +

' 1 >\ Ц 1

2 и^ т,

Результатом решения этапа 2 является матрица У

(Гх/^,)

Построенный НС-алгоритм в качестве исходных данных принимает не только формализованные характеристики РБД, но и два вектора весовых коэффициентов С^ = (л„„ф0,) и С1 = (А2,В2,С2,В2,Е2) для построения функций энергии ИНС этапов 1 и 2 соответственно. Систематического способа определения векторов С, и С~2 не существует. Необходимо найти такие вектора С, и С2, при которых НС-алгоритм дает квазиоптимальное решение задачи. Для нахождения С1ош1т и С2тшим диссертантом предложено использование ГА.

При реализации ГА НС-алгоритм используется как «черный ящик», осуществляющий отображение особи А,-В,-С,-... в соответствующую ей

X V У

(1*Г) |Г>Щ

матрицу, по которой определяется фенотип особи: А, - В, - С, -...

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

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

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

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

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

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

Л-1

РТМ: Е = Еа + Е]+...+ЕР_, = YjEp> где Р — количество процессоров.

р=а

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

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

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

В четвертой главе рассматриваются методики апробации алгоритмов и описаны результаты практического применения предлагаемых методов. В качестве базы данных примеров рассматриваются три модельные задачи различной размерности и задача синтеза ОЛС реальной БД ERP-системы Human Resource Management Tool (HRMT), используемой в международной IT-компании ООО «Датавижн НН».

Для определения влияния параметров ТМ / РТМ на качество решения и

время его нахождения были проведены серии экспериментов по решению

этапов 1 и 2 задачи при различных значениях параметров ТМ: табу-размера /,

17

количества циклов обработки удаленных состояний С, количества циклов обработки соседних состояний /?. Для каждой из модельных задач было получено 372 пробных решения этапа 1 и 372 решения этапа 2 для каждого из различных решений этапа 1,

Декомпозиция проводилась на модельных задачах с помощью ЭМСО, НС-ГА-алгоритма и ТМ / РТМ. В качестве относительной метрики оценки качества декомпозиции групп данных диссертантом взята степень неучета семантической смежности групп данных как характеристика полученного на этапе I множества 5

ЛЗ: Мч = -——-100%, где N - это число нейронов в НСХ. Значение данного

показателя для модельных задач разной размерности сведены в Таб.2. Рис.1 показывает значение процессорного времени, потраченного на декомпозицию НС-ГА- и ТМ-алгоритмами, для модельной задачи с N -1600.

Таб. 2. Значение показателя N на модельных задачах

Степень неучета Nq семантической смежности групп данных, %

А'= 100 N = 400 /V = 1600

ЭМСО

15,6 | 36,8 ! 18,3

НС-ГА-алгоритм

2,2 | 31,6 | 16,3

ТМ / РТМ

Максимальный % 35,6 36,3 12,6

Минимальный % 4,4 28,4 12,2

Средний % 16,1 34,8 12,5

Процессорное время, потраченное на декомпозицию групп данных _____3917,2

4000

3500 3000 2500

Процессорное

время 2000

1СЮ0 500 О

НС-ГА-алгоригм ТМ: максимум ТМ: среднее ТМ: минимум

Рис. 1. Процессорное время, потраченное на декомпозицию данных при N = 1600

18

3917,2

НС-ГА-алгоригм ТМ: максимум ТМ: среднее ТМ: минимум

В процессе экспериментальных исследований были найдены оптимальные безызбыточные размещения синтезированных типов ЛЗ по узлам ВС. На Рис.2 представлен сравнительный анализ качества полученных решений для модельной задачи с А'= 1600. Средние результаты, полученные с помощью ТМ / РТМ на модельной задаче большей размерности, качественно превосходят результаты, полученные с помощью НС-ГА-алгоритма, на 8,7%, а результаты, полученные с помощью ЭМСО, - на 23,6%.

Значение целевой функции на решениях модельной задачи с N=»600 0,0495

Значение целевой функции

ЭМСО

НС-ГА- ТМ / РТМ: ТМ/РТМ: ТМ/РТМ: алгоритм максимум среднее минимум

Рис. 2. Значения целевой функции на решениях модельной задачи с N = 1600, полученных с помощью ЭМСО, НС-ГА-алгоритма и ТМ / РТМ

Анализ результатов серий экспериментов позволил дать рекомендации по выбору оптимальных значений тройки параметров ТМ / РТМ для решения этапа 2 задачи: /е[Г; /], /0е[О,5; 1], С >20.

Все серии экспериментов по решению задач с использованием РТМ проводились на вычислительном кластере. Использование РТМ дает линейное ускорение. Рис.3 иллюстрирует зависимость среднего ускорения от количества ядер для модельной задачи с N = 1600.

Для реальной БД ЕИР-системы НЯМТ с / = 189 была проведена декомпозиция множества групп данных на типы ЛЗ. Полученная структура таблиц характеризуется степенью неучета семантической смежности групп данных равной Л^ =0,3%, в то время как для текущей используемой структуры

БД эта характеристика составляет N =7,8%. Таким образом, новый вариант структуры на 7,5% лучше учитывает семантическую смежность групп данных.

Зависимость среднего ускорения от числа ядер для задачи с N=1600

Количество ядер

Рис. 3. Зависимость среднего ускорения от числа ядер для задачи с N = 1600 На основе синтезированной ЛС с помощью РТМ-алгоритма было найдено безызбыточное размещение таблиц по узлам ВС, уменьшившее общее время последовательной обработки множества запросов пользователей на 14,7%.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

2. Разработан и реализован нейросетевой алгоритм оптимизации, основанный на модифицированном табу-поиске. В результате сравнения ТМ-алгоритма с НС-ГА-алгоритмом и ЭМСО показано, что средние результаты, полученные с помощью ТМ на модельной задаче большей размерности, лучше результатов, полученных с помощью НС-ГА-алгоритма, на 8,7%, а

результатов, полученных с помощью ЭМСО, - на 23,6%.

20

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

4. В результате серии экспериментов по тестированию реализованной РТМ на вычислительном кластере НИУ ВШЭ - Нижний Новгород даны рекомендации по выбору оптимальных значений тройки параметров ТМ / РТМ для решения этапа2 задачи: /е[Г; /], /?е[0,5; i], С>20.

5. Для реальной БД, используемой в международной IT-компании, с помощью РТМ была проведена декомпозиция множества групп данных на типы ЛЗ. Полученная в результате структура таблиц 7,5% лучше учитывает семантическую смежность групп данных по сравнению с текущей используемой структурой БД. На основе синтезированной ЛС с помощью РТМ-алгоритма было найдено безызбыточное размещение таблиц по узлам ВС, позволяющее уменьшить общее время последовательной обработки множества запросов пользователей на 14,7%.

СПИСОК ПУБЛИКАЦИЙ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в рецензируемых изданиях, рекомендованных ВАК 1. Карпунина, М.Е. Сравнительный анализ использования табу-машины и нейронных сетей Хопфилда для решения задач дискретной оптимизации из области распределенных баз данных / Э.А. Бабкин, М.Е. Карпунина // Научно-технический вестник СПбГУ ИТМО. Технологии высокопроизводительных вычислений и компьютерного моделирования. / Гл. ред. д.т.н., профессор В.О. Никифоров. - Санкт-Петербург: Университетские

телекоммуникации, март - апрель 2008. - № 54. - С. 120-127. - 0,96 п.л. (авт. - 0,9 пл.)

2. Karpunina, М. The analysis of tabu machine parameters applied to discrete optimization problems / E. Babkin, M. Karpunina // Proceedings of 2009 ACS/IEEE International Conference on Computer Systems and Applications, AICCSA'2009. - May 10-13, 2009. - Rabat, Morocco. - P. 153-160. - 0,96 п.л. (авт. - 0,76 п.л.)

3. Karpunina, M. Parallel Tabu Search Algorithm for Data Structure Composition / E. Babkin, M. Karpunina, N. Aseeva // Lecture Notes in Business Information Processing. / J.Grabis and M.Kirikova (Eds.): BIR 2011, LNBIP. - Vol. 90, Perspectives in Business Informatics Research, Part 3. - P. 110-123.- 1,68 п.л. (авт. - 1,3 п.л.)

Статьи в других изданиях

4. Карпунина, М.Е. Об использовании полносвязных нейронных сетей прямого распространения для решения задачи разбиения множества групп данных на типы логических записей / Э.А. Бабкин, М.Е. Карпунина // Известия Академии инженерных наук им. A.M. Прохорова. Прикладная математика и механика. / Под ред. Ю.В.Гуляева. - Москва - Н.Новгород: НГТУ, 2004. -Т.6. - С. 67-73. - 0,84 п.л. (авт. - 0,7 п.л.)

5. Карпунина, М.Е. Об одном методе синтеза структуры распределенной базы данных, основанном на использовании искусственных нейронных сетей Хопфилда / Э.А. Бабкин, М.Е. Карпунина // Известия Академии инженерных наук им. A.M. Прохорова. Бизнес-информатика. / Под ред. Ю.В.Гуляева. -Москва - Н.Новгород: TAJIAM, 2005. - Т.12. - С. 37-46. - 1,2 п.л. (авт. - 1 п.л.)

6. Карпунина М.Е. Использование генетических алгоритмов для повышения эффективности работы искусственных нейронных сетей / М.Е. Карпунина // Известия Академии инженерных наук им. A.M. Прохорова. Бизнес-информатика. / Под ред. Ю.В.Гуляева. - Москва - Н.Новгород: TAJIAM, 2005.- 11 с.-1,32 п.л.

7. Petrova (Karpunina), M. Towards application of neural networks for optimal synthesis of distributed database systems / E. Babkin, M. Petrova (Karpunina) // Proceedings of 12th IEEE Intrl. Conference on Electronics, Circuits, and Systems, satellite workshop Modeling, Computation and Services, Gammarth, Tunisia. -2005. - P. 486-490. - 0,6 пл. (авт. - 0,5 пл.)

8. Петрова (Карпунина), М.Е. Нейросетевой подход к решению задач дискретной оптимизации с использованием табу-поиска / М.Е. Петрова (Карпунина) // Известия Академии инженерных наук им. A.M. Прохорова. Бизнес-информатика. / Под ред. Ю.В.Гуляева. - Москва - Н.Новгород: ТАЛАМ, 2006. - Т. 17. - С. 11-19.- 1,08 пл.

9. Petrova (Karpunina), M. Application of genetic algorithms to increase an overall performance of neural networks in the domain of database structures synthesis / E. Babkin, M. Petrova (Karpunina) // Information Technology and Control, Kaunas, Technologija. - 2006. - Vol. 35, No. ЗА. - P. 285-294. - 1,2 пл. (авт. - 0,96 пл.)

Ю.Карпунина, М.Е. Табу-машина как средство решения задач дискретной оптимизации: улучшение качества решения и уменьшение времени его нахождения по сравнению с альтернативным методом использования нейросетей Хопфилда / М.Е. Карпунина // Материалы 1-ой Международной конференции по бизнес-информатике, Россия, Московская область, Звенигород, 2007. - С. 204-218. - 1,8 пл.

11.Karpunina, M. Comparative study of the Tabu machine and Hopfield networks for discrete optimization problems / E. Babkin, M. Karpunina // Information technologies' 2008 - Proceedings of 14th Conference on Information and Software Technologies, IT 2008. - April, 2008. - Kaunas University of Technology, Kaunas, Lithuania. - P. 25-41. - 2,04 пл. (авт. - 1,8 пл.)

12.Karpunina, M. A new method of DDB logical structure synthesis using distributed tabu search / E. Babkin, M. Karpunina // Proceedings of International Workshop on Soft Computing Applications and Knowledge Discovery, SCAKD'll. - June, 2011. - National Research University Higher School of Economics, Moscow, Russia. - P. 1-11. - 1,32 пл. (авт. -0,92 пл.)

Подписано в печать 26.11.12. Формат 60 х 84 '/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 749.

Нижегородский государственный технический университет им. Р. Е. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.