uzluga.ru
добавить свой файл
1


Сравнительный анализ использования Табу−машины и нейронных сетей Хопфилда для решения задач дискретной оптимиза- ции из области распределенных баз данных

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

  • Научный руководитель: Бабкин Эдуард Александрович, к.т.н., доцент, зав. кафедрой «Информационные системы и технологии»


ОБЗОР

  • Роль распределенных баз данных в современной информационной среде

  • Известные подходы к синтезу структуры распределенной базы данных

  • Комбинация нейросетей Хопфилда и генетических алгоритмов

  • Табу-машина и алгоритм табу-поиска

  • Программная реализация

  • Полученные результаты, оценки, прогнозы

  • Планы дальнейшей работы



РОЛЬ РАСПРЕДЕЛЕННЫХ БАЗ ДАННЫХ В СОВРЕМЕННОЙ ИНФОРМАЦИОННОЙ СРЕДЕ

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



СИНТЕЗ ЛОГИЧЕСКОЙ СТРУКТУРЫ РБД

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



ПОСТАНОВКА ЗАДАЧИ

  • Всем

  • характеристикам

  • задачи, включая

  • исходную структуру РБД,

  • множество запросов,

  • множество пользователей РБД,

  • множество узлов и

  • топологию

  • вычислительной

  • сети (ВС),

  • усредненные исходные

  • временные характеристики,

  • было дано математическое описание.



ПОСТАНОВКА ЗАДАЧИ

  • Математическая постановка задачи синтеза оптимальной логической структуры РДБ включает задание

  • целевой функции задачи

  • ограничений задачи:

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


СИНТЕЗ ЛОГИЧЕСКОЙ СТРУКТУРЫ РБД: ИЗВЕСТНЫЕ ПОДХОДЫ



НЕЙРОННЫЕ СЕТИ ХОПФИЛДА



НЕЙРОННЫЕ СЕТИ ХОПФИЛДА

  • Результат 1-го этапа решения задачи: матрица распределения групп данных по типам логических записей, где

  • Результат 2-го этапа решения задачи: матрица безызбыточного размещения типов логических записей по узлам ВС, где

  • Вектора весовых коэффициентов: ,



НЕЙРОННЫЕ СЕТИ ХОПФИЛДА: ФУНКЦИЯ ЭНЕРГИИ НЕЙРОСЕТИ, ПОСТРОЕННОЙ ДЛЯ РЕШЕНИЯ ПЕРВОГО ЭТАПА ЗАДАЧИ

  • Выведено уравнение динамики однослойной с обратными связями сети Хопфилда для решения задачи синтеза типов логических записей с учетом ограничений 1, 2 и 6.



НЕЙРОННЫЕ СЕТИ ХОПФИЛДА: ФУНКЦИЯ ЭНЕРГИИ НЕЙРОСЕТИ, ПОСТРОЕННОЙ ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ

  • Выведено уравнение динамики однослойной с обратными связями сети Хопфилда для решения задачи безызбыточного размещения синтезированных типов логических записей по узлам вычислительной сети с учетом ограничений 3, 4, 5 и 7.

  • где − нормированная сумма, т.е. .



ПРЕИМУЩЕСТВА И НЕДОСТАТКИ НЕЙРОСЕТЕВОГО АЛГОРИТМА

  • Робастность нейронной

  • сети Хопфилда

  • К сожалению, систематического способа определения значений элементов векторов и не существует. Известно только, что должно выполняться ограничение

  • .



ПУТИ РАЗРЕШЕНИЯ НЕДОСТАТКОВ НЕЙРОСЕТЕВЫХ АЛГОРИТМОВ

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

  • Использование метода анализа устойчивых состояний (Stable State Analysis (SSA) Technique)¹



ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ КАК ОБОЛОЧКА ДЛЯ НЕЙРОСЕТЕВОГО АЛГОРИТМА



НЕЙРОСЕТЕВОЙ АЛГОРИТМ: НЕКОТОРЫЕ ТЕСТОВЫЕ РЕЗУЛЬТАТЫ ДЛЯ ПОЛНОЙ ЗАДАЧИ СИНТЕЗА ЛОГИЧЕСКОЙ СТРУКТУРЫ РБД

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

  • Процент отклонения качества решения

  • Средний процент отклонения, полученный в результате тестирования на задачах различной размерности составил



ПРЕДПОСЫЛКИ ИССЛЕДОВАНИЯ ТАБУ-МАШИНЫ КАК АЛЬТЕРНАТИВНОГО НЕЙРОСЕТЕВОГО АЛГОРИТМА

  • Тенденция сетей Хопфилда стабилизироваться в локальном, а не глобальном минимуме функции энергии

  • Осуществляемый генетическим алгоритмом подбор коэффициентов A, B, C, D, E, F, влияющих на сходимость сети Хопфилда, способен значительно увеличить время работы НС-ГА-алгоритма



ТАБУ-МАШИНА

  • < l, C, β > − набор парамет-ров Табу-машины¹, где

  • l  0 − табу-размер,

  • C  0 − максимальное

  • число вызовов обработки удаленных состояний,

  • β > 0 − предопределенный коэффициент такой, что

  • βn > l.

  • Механизм смены состояний

  • в Табу-машине регулируется табу-поиском.



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ПЕРВОГО ЭТАПА ЗАДАЧИ: ОСОБЕННОСТИ

  • Функция энергии

  • Улучшение качества решения: степень учета семантической смежности групп данных определяется по формуле

  • ,

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

  • Увеличение производительности алгоритма



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ПЕРВОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ОСОБЕННОСТИ

  • Функция энергии

  • Улучшение качества решения: значение целевой функции задачи. Качество полученного решения будем оценивать значением целевой функции задачи. Чем ближе оно к нулю, тем более оптимальным является решение.

  • Увеличение производительности алгоритма

  • Исследование области параметров < l, C, β > Табу-машины: описание экспериментов



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



НС-ГА-АЛГОРИТМ И АЛГОРИТМ ТАБУ-ПОИСКА: ВЫВОДЫ

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

  • К преимуществам использования Табу-машины можно отнести независимость решения от коэффициентов энергетической функции A, B, C, D, E, F сети.

  • Чем больше значение параметра С, тем больше качественно лучших решений удается получить при различных значениях l.

  • Наилучшим значением параметра l является величина, равная количеству типов логических записей, синтезированных на первом этапе решения задачи.



ЗАКЛЮЧЕНИЕ

  • Мы рассмотрели возможности применения аппарата искусственных нейронных сетей для решения задач дискретной оптимизации.

  • В ходе обсуждения были продемонстрированы возможности сетей Хопфилда для решения задач такого рода. А исследования Табу-машины как альтернативного способа решения выявили возможность не только качественного улучшения решения задачи, но и возможность увеличения производительности алгоритма.

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



ПЛАНЫ ДАЛЬНЕЙШЕЙ РАБОТЫ

  • Интегрировать Табу-машины для первого и второго этапов решения задачи синтеза в единый алгоритм табу-поиска.

  • Выполнить распараллеливание алгоритма табу-поиска с целью повышения его эффективности.

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



СПАСИБО ЗА ВНИМАНИЕ



ЦЕЛЕВАЯ ФУНКЦИЯ ЗАДАЧИ



ОГРАНИЧЕНИЕ НА ЧИСЛО ГРУПП В СОСТАВЕ ЛОГИЧЕСКОЙ ЗАПИСИ

  • где − максимальное число групп в записи

  • Постановка задачи Первый этап решения



ОГРАНИЧЕНИЕ НА ОДНОКРАТНОСТЬ ВКЛЮЧЕНИЯ ГРУПП В ЛОГИЧЕСКИЕ ЗАПИСИ



ОГРАНИЧЕНИЕ НА ДЛИНУ ФОРМИРУЕМОЙ ЛОГИЧЕСКОЙ ЗАПИСИ

  • где − максимально допустимая длина -ой записи определяемая характеристиками сервера

  • Постановка задачи Второй этап решения



ОГРАНИЧЕНИЕ НА ОБЩЕЕ ЧИСЛО ТИПОВ СИНТЕЗИРУЕМЫХ ЛОГИЧЕСКИХ ЗАПИСЕЙ, РАЗМЕЩЕННЫХ НА КАЖДОМ ИЗ СЕРВЕРОВ

  • где − максимальное число типов логических записей, поддерживаемое локальной СУБД узла-сервера

  • Постановка задачи Второй этап решения



ОГРАНИЧЕНИЕ НА ОБЪЕМ ДОСТУПНОЙ ВНЕШНЕЙ ПАМЯТИ СЕРВЕРОВ ВС ДЛЯ ХРАНЕНИЯ ЛБД

  • Постановка задачи Второй этап решения



ОГРАНИЧЕНИЕ НА ТРЕБУЕМЫЙ УРОВЕНЬ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ СИСТЕМЫ

  • для заданных

  • и

  • Постановка задачи Первый этап решения



ОГРАНИЧЕНИЕ НА СУММАРНОЕ ВРЕМЯ ОБСЛУЖИВАНИЯ ОПЕРАТИВНЫХ ЗАПРОСОВ НА СЕРВЕРАХ

  • для заданных , где − допустимое время обслуживания -го оперативного запроса

  • Постановка задачи Второй этап решения



ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ КАК ОБОЛОЧКА ДЛЯ НЕЙРОСЕТЕВОГО АЛГОРИТМА

  • Особь в нашем случае — это точка в -мерном пространстве. Количество генов каждой особи равно . Хромосома — последовательное объединение всех генов .

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

  • перевод значения гена в десятичной системе счисления в двоичную (при дополнении старших разрядов нулями, если это необходимо) ,

  • перевод гена в двоичной системе счисления в код Грея .

  • С точки зрения генетического алгоритма нейросетевой алгоритм используется как своеобразный “черный ящик”, осуществляющий отображение особи в соответствующую ей матрицу или (в зависимости от номера этапа решения задачи), по которой определяется фенотип особи .



ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ КАК ОБОЛОЧКА ДЛЯ НЕЙРОСЕТЕВОГО АЛГОРИТМА



ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ КАК ОБОЛОЧКА ДЛЯ НЕЙРОСЕТЕВОГО АЛГОРИТМА



ПРОГРАММНАЯ РЕАЛИЗАЦИЯ НС-ГА-АЛГОРИТМА

  • ОО библиотека классов нейронных сетей Хопфилда на С++

  • ОО модель генетических алгоритмов.

  • Результатами решения задачи являются:

  • вектор и матрица разбиения групп данных по типам логических записей (этап 1);

  • вектор и матрица размещения типов логических записей по узлам ВС (этап 2).



ОСОБЕННОСТИ РЕАЛИЗАЦИИ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

  • Код Грея для представления символической модели генотипа

  • Формирование начальной популяции по фенотипу

  • Способ выбора пары − панмиксия.

  • Генетические операции − простой кроссинговер и точечная мутация

  • Общий способ формирования репродукционной группы, т.е. в новую популяцию включаются и дети, и родители

  • Строгий естественный отбор.

  • Критерии останова алгоритма:

  • На протяжении нескольких поколений рекордсмен по приспособленности не меняется

  • Приспособленность хотя бы одной особи текущей популяции равна 1.



РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТОВ И ИХ АНАЛИЗ



ТАБУ-МАШИНА: СТРУКТУРА И КОНЦЕПЦИИ ФУНКЦИОНИРОВАНИЯ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ТАБУ-МАШИНА ДЛЯ РЕШЕНИЯ ВТОРОГО ЭТАПА ЗАДАЧИ: ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ, ОЦЕНКИ, ПРОГНОЗЫ



ПРИЛОЖЕНИЕ: ДОПОЛНИТЕЛЬНЫЕ МАТЕРИАЛЫ



ПРИЛОЖЕНИЕ: ДОПОЛНИТЕЛЬНЫЕ МАТЕРИАЛЫ



ПРИЛОЖЕНИЕ: ДОПОЛНИТЕЛЬНЫЕ МАТЕРИАЛЫ



ПРИЛОЖЕНИЕ: ДОПОЛНИТЕЛЬНЫЕ МАТЕРИАЛЫ



ПРИЛОЖЕНИЕ: ДОПОЛНИТЕЛЬНЫЕ МАТЕРИАЛЫ



ОБЛАСТЬ ЗНАНИЙ