Диссертация (1137070), страница 2

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

Текст из файла (страница 2)

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

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

Кроме того, диссертантом предложена иреализована инженерная идея учета семантической смежности групп данных впроцессесинтезаОЛСРБД.РаспределенныйвариантНС-алгоритмаоптимизации, основанного на модифицированном табу-поиске, позволяетускорить процесс синтеза ОЛС РБД.Результаты диссертационной работы внедрены в производственнуюдеятельность международной IT-компании ООО «Датавижн НН» и в учебныйпроцесс НИУ ВШЭ – Нижний Новгород по курсу «Современные средствапостроения интеллектуальных систем» направления магистратуры 080500.68«Бизнес-информатика».Апробациядиссертации.Основныеположенияирезультатыдиссертационной работы докладывались и обсуждались на 1-ой Международнойконференции по бизнес-информатике (The 1st International Conference on BusinessInformatics, BI-2007) (Звенигород, 2007), I Сессии научной школы-практикумамолодых ученых и специалистов «Технологии высокопроизводительныхвычисленийисистем»врамках5-ойВсероссийскоймежвузовскойконференции молодых ученых (КМУ-V) (Санкт-Петербург, СПбГУ ИТМО,2008), 7-ой Международной Конференции по Компьютерным Системам иПриложениям (The 7th ACS/IEEE International Conference on Computer SystemsandApplications, AICCSA-09) (Рабат, Марокко, 2009), Международной8молодежной научной школе «Исследование операций и приложения влогистике» (НИУ ВШЭ – Нижний Новгород, 2010), 4-ой Международнойконференции «Распознавание образов и искусственный интеллект» (The 4thInternational Conference on Pattern Recognition and Machine Intelligence, PReMI2011) (Москва, НИУ ВШЭ, 2011), Х Всероссийской научной конференции«Нейрокомпьютеры и их применение» (Москва, МГППУ, 2012), а также на ряденаучных семинаров кафедры «Информационные системы и технологии» НИУВШЭ и компанииMeraLabs.

Кроме того, диссертантом получен диплом Iстепени на I Сессии научной школы-практикума молодых ученых испециалистов «Технологии высокопроизводительных вычислений и систем»(КМУ-V) в секции «Параллельные технологии искусственного интеллектаобработки данных и имитационного моделирования».Публикации. Основные результаты опубликованы в 12 работах, в томчисле 1 – в журнале, входящем в список ВАК, а именно: «Научно-техническийвестник СПбГУ ИТМО. Технологии высокопроизводительных вычислений икомпьютерного моделирования», 1 – в сборнике трудов конференции ACS/IEEEInternational Conference on Computer Systems and Applications 2009, и 1 – вмеждународном журнале Lecture Notes in Business Information Processing,включенныхвсистемуцитированияScopus.Крометого,программа«Программная реализация нейросетевых алгоритмов синтеза оптимальнойлогическойструктурыраспределеннойбазыданных»,реализующаяразработанные диссертантом алгоритмы, зарегистрирована в Фонде Алгоритмови Программ Сибирского Отделения Российской Академии Наук (ФАП СО РАН)под № PR12018 от 26.10.2012.Основные положения, выносимые на защиту.1.

Разработанныйэволюционныйалгоритмоптимизации(НС-ГА-алгоритм), основанный на ИНС Хопфилда и генетических алгоритмах,используемых для оптимизации функционирования ИНС.2. Созданный нейросетевой алгоритмоснованный на модифицированном табу-поиске.9оптимизации (ТМ-алгоритм),3. Разработанный распределенный нейросетевой алгоритм оптимизации(РТМ-алгоритм), основанный на модифицированном табу-поиске.4. Выполненная программная реализация разработанных алгоритмовоптимизации и их тестирование на модельных задачах.5. Проведенный сравнительный анализ созданных НС-алгоритмов иЭМСО с точки зрения качества получаемых решений и быстродействия.6. Выполненная оптимизация ЛС реальной БД, используемой в международной IT-компании, с помощью реализованной модели РТМ-алгоритма.Структура и объем работы.

Диссертация включает в себя введение,четыре главы основного текста, заключение, список используемой литературыиз 99 источников и пять приложений. Работа изложена на 184 страницах текста,включающих 22 рисунка и 9 таблиц.Диссертационная работа выполнена при поддержке исследовательскогопроекта № 10-04-0009, поддерживаемого научным фондом НИУ ВШЭ.ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫВо введении содержится обоснование актуальности темы диссертации,описываются объект, предмет и методы исследования.

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

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

Кульбой и имеет вид:T R0 R0 R0 T t dis ser trf QQ t asssrhzttt1zt   z pr2   tr2  tr2  (1)kpkp   kr1   pr2 r1r2r1r2 pr2  k 1 p 1 t 1 r1 1 r2 1 r2 1 t 1K0min{ xit , ytr }P0при ограничениях наIчисло групп в составе ЛЗxit Ft , t  1, T , гдеFt– максимальноеi 1количество групп в t -й записи;(2)Tоднократность включения групп в записиxit 1, i  1, I ;(3)t 1Iдлину формируемой ЛЗxitytr i 0   tr , где  tr – максимально допустимаяi 1длина t -гo типа записи, определяемая техническими характеристиками сервераr -го узла ВС;(4)общее число синтезируемых ЛЗ, размещенных на сервере r -го узла ВСTytr hr , где hr – максимальное количество ЛЗ, поддерживаемых локальнойt 1СУБД r -го узла;T(5)объем доступной внешней памяти серверов ВС для хранения локальных БДI0i i xit ytr  rEMD ;(6)t 1 i 1требуемый уровень информационной безопасности системы xit xi ' t  0 , длязаданных групп данных dig и dig' ;(7)11суммарное время обслуживания оперативных запросов на серверахR0T ztpr2 (trsrh tr2 )  Tp ,2для заданных Q p  Q , где Tp– допустимое времяr2 1 t 1обслуживания p -го оперативного запроса.Здесь T – число ЛЗ;данных i включена в ЛЗ t ;(8)X  xit  0,1 , i  1, I , t  1, T , xit  1 , если группа(I  T )Y(T  R0 ) ytr  0,1 , t  1, T , r  1, R0 , ytr  1 , если ЛЗ tразмещена на узле r ВС.

Переменная z tpr определяет типы ЛЗ, используемых p 2Iм запросом на сервере r2 -го узла ВС: z tpr  1 , если2ytr2wQpi xit  1 ; z tpr2  0 , еслиi 1Iytr2wQpi xit  0 . Переменная z pr2 определяет множество узлов-серверов ЛБД, кi 1Tкоторым обращается p -й запрос: z pr  1 , если2I ytr2wQpi xit  1 ; z pr2  0 , еслиt 1 i 1TI ytr2wQpi xit  0 .0–коэффициент,учитывающийналичиеслужебнойt 1 i 1информации в записи. Другие характеристики указаны в Таб.1.Таб.

1. Формализованные описания характеристик предметной области задачиНаименованиеОбозначениеХарактеристики канонической структуры РБДD G  d ig / i  1, IМножество групп данных   i Вектор длин групп   i Вектор количества экземпляров в группахGgii 'A  a , где aiig'  1 , если существуетМатрица семантической смежности группданныхсемантическая связь между i -й и i ' -йгруппами, aiig'  0 – в противном случаеХарактеристики запросов пользователейМножество запросовQ  q p / p  1, P0W Q  wQpi , где wQpi  1 , если p -й запросМатрица использования групп данных привыполнении запросовиспользует в процессе выполнения i -югруппу, wQpi  0 – в противном случае Q   kpQ , где  kpQ – частота исполь-Матрица частот использования запросовпользователямизования пользователем k запроса pХарактеристики пользователейМножество пользователейU  uk / k  1, K 012   kr ,где  kr  1 ,еслиk -йпользователь прикреплен к r -у узлу ВС, kr  0 – в противном случаеМатрица прикрепления пользователей кузлам ВС Q   kpQ ,Матрица использования запросовпользователями РБДгдеkpQ  1 ,пользователь используетеслиk -йp -й запрос,Qkp  0 – в противном случаеХарактеристики узлов ВСN R  nr / r  1, R0Множество узлов ВС EMD  rEMD  , где  rEMD – величина до-Вектор объемов памяти на серверах ВС,доступных пользователюступной памяти на сервере r -го узла ВСУсредненные исходные временные характеристикиСреднее время сборки блока данных приt assформировании массива данных запросаСреднее время формирования одногоt disподзапросаСреднее время выбора маршрута,установления логических соединений междуtrser1r2узлами r1 и r2Среднее время передачи одного блокаданных запроса с узла r1 на узел r2 поtrtrf1r2кратчайшему путиСреднее время доступа к файлам ЛБД иt srhпоиска в них требуемых логических записейСреднее время обработки одной логическойзаписи на узле r2 , зависящее отtr2производительности сервераПринадлежность рассматриваемой задачи к классу NP делает методполного перебора неприменимым.

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

Характеристики

Список файлов диссертации