Тема: Применение муравьиного алгоритма для оптимизации распределенных баз данных

Активное развитие технологий непрерывно связано с увелечением количества информации, поэтому использование обычной централизованной базы данных уже не будет хватать для хранения таблиц из-за физических ограничений. Поэтому все большее количество крупных компаний начинают использовать распределенные базы данных, позволяющие обработать и структурировать большие объемы информации по отдельным участкам сети. С развитием таких распределенных систем, также возрастает и сложность решаемых ими задач и объёмы обрабатываемой информации. Поэтому вопрос построения распределенной БД с целью минимизации времени получения и обработки запросов в распределенной информационной системе на данный момент остается актуальной проблемой. Для таких целей используют различные алгоритмы, в том числе придуманные не только человеком.
На протяжении всей жизни человек не раз сталкивался с животными, которые лучше видят, слышат, имеют различные полезные особенности. Со временем мы стали лучше понимать их механизмы, которые оптимизировались на протяжении миллионов лет эволюции и начали заимствовать лучшее от них, например, инфракрасные лучи тепловизора - у змеи, закрылки для самолета - у крыльев птиц, светоотражающая разметка - у глаз кошки и т.п.
Также организация животных и насекомых позволила создать на их основе «природные алгоритмы». Например, муравьиный алгоритм отлично подходит для решения задач логистики, таких как задача коммивояжёра или доставка товаров от магазина к покупателю.
На основе этого алгоритма нами будет решаться проблема оптимизации распределения кластеров по узлам сети с целью минимизации времени получения и обработки запросов в распределенной информационной системе.
Целью данной работы является разработка и реализация алгоритмов оптимизации распределения централизованной базы данных по узлам сети.
В первом разделе выполнен анализ предметной области, рассмотрены понятие и архитектура распределенной базы данных, кластеризация и фрагментация, методы оптимизации распределенной базы данных. Рассмотрены возможные для применения алгоритмы. Выбрано программное обеспечение.
Во втором разделе рассмотрена математическая постановка задач оптимизации. Приведено обоснование выбранных методов. Представлены результаты исследований по применению выбранных алгоритмов фрагментации и кластеризации таблиц, муравьиной оптимизации и динамического программирования оптимизации выполнения распределенных запросов.
Третий раздел посвящен схемам алгоритмов оптимизации распределенной базы данных.
Четвертый раздел включает в методику и результаты экспериментальных исследований предложенных алгоритмов. На тестовой базе данных проведено сравнение времени выполнения запросов в оптимизированной и централизованной распределенной базе даннах.
Купить

Сформирован критерий кластеризации, минимизирующий
межкластерное расстояние. Выполнено оптимальное разбиение исходной базы данных на кластеры. Для этого использовалась гибридная фрагментация, подразумевающая вертикальное фрагментирование, а затем горизонтальное.
Построена оптимальная структура при помощи муравьиного алгоритма оптимизации распределения кластеров по узлам сети, при котором уменьшилось общее время выполнения запросов к базе данных. Также оптимизировались сами запросы при помощи алгоритма динамического программирования, который выдает оптимальный план выполнения запроса, необходимый для подсчета целевой функции.
Программно реализованы основные алгоритмы оптимизации распреденной базы данных: кластеризация, оптимизация выполнения запроса, оптимизация распределения фрагментов. Экспериментальное исследование разработанных алгоритмов показало положительный результат: уменьшено среднее время выполнения запросов к распределенной базе данных с 1250 мс до 608 мс, прибилизтельно в 2 раза.
Таким образом исследован алгоритм муравьиной колонии и адаптирован под реалии задачи. Исследования показали эффективность использования этого алгоритма при оптимизации распределения кластеров по узлам сети.
Купить