Применение муравьиного алгоритма к решению задачи о независимом множестве

АННОТАЦИЯ 2
ВВЕДЕНИЕ 6
1 АНАЛИЗ СПОСОБОВ РЕШЕНИЯ ЗАДАЧИ О НЕЗАВИСИМОМ
МНОЖЕСТВЕ 8
1.1 Задача о независимом множестве 8
1.2 Существующие точные методы решения задачи 9
1.2.1 Алгоритм Брона-Кербоша 11
1.2.2 Метод ветвей и границ 11
1.3 Эвристические алгоритмы решения NP - трудных задач 14
1.4 Выводы по разделу и постановка задачи 16
2 РАЗРАБОТКА МУРАВЬИНОГО АЛГОРИТМА ПОИСКА
МАКСИМАЛЬНОНО НЕЗАВИСИМОГО МНОЖЕСТВА 18
2.1 Особенности реализации муравьиного алгоритма применительно к задаче
поиска максимального независимого множества 18
2.2 Вывод по разделу 25
3 Экспериментальные исследования алгоритма 27
3.1 Методика эксперимента 27
3.2 Результаты исследований 29
3.3 Выводы по разделу 32
ЗАКЛЮЧЕНИЕ 33
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 34
ПРИЛОЖЕНИЕ 1 36
Купить

Теория графов одна из важнейших разделов дискретной математики, которая очень часто используется при создании математических моделей в разных областях науки и техники. Одной из причин использования является наглядность, что облегчает понимание и использование сложных моделей.
Теория графов существует уже более 80 лет, но, несмотря на это остаются задачи, для которых не существуют алгоритмы нахождения точных решений за полиномиальное время. Такие задачи называются NP-полными.
В данной работе мы рассмотрим одну задачу из раздела теории графов, которая является NP-полной, а именно поиск максимального независимого множества в неориентированном графе. Алгоритмы поиска максимального независимого множества (МНМ) используются в таких областях, как социометрия, химия, компьютерные технологии [1] и биоинфоматика [2]. Это объясняется тем, что специальным образом представив объект исследования в виде модели на графе, множество задач из вышеуказанных областей науки можно свести к задаче поиска клики в неориентированном графе, что в свою очередь легко трансформируется в задачу нахождения МНМ графа.
Данная работа посвящена разработке и исследованию муравьиного алгоритма поиска минимального независимого множества на графе.
В первой главе проведен анализ существующих алгоритмов решения поставленной задачи. Показано, что точные методы поиска МНМ имеют полиномиальную вычислительную сложность и непригодны для решения задач большой размерности. Из точных методов выделен алгоритм поиска методом ветвей и границ, как наиболее быстрый. Рассмотрены «жадные» алгоритмы решения задачи. Отмечено, что они находят локальное решение за полиномиальное время, которое не всегда совпадает с точным. Третий класс алгоритмов - эволюционные алгоритмы, имитирующие эволюционное поведение живых организмов. Показано, что эти алгоритмы являются перспективными для решения различного рода оптимизационных задач. Они быстрее точных алгоритмов и эффективнее жадных и позволяют с большей вероятностью получить точное решение.
В качестве цели работы выбрана разработка и исследование алгоритма поиска МНМ методом, имитирующим поведение муравьиной колонии. Сформулированы цели и задачи исследования.
Вторая глава посвящена особенностям разработки муравьиного алгоритма применительно к задаче поиска МНМ. Предложены способы выполнения основных эвристик алгоритма: создание и начальное размещение муравьев на вершинах графа, алгоритм поиска локального решения каждым муравьем, алгоритм распределения феромона муравьями, условие останова. Показано, что вычислительная сложность алгоритма имеет оценку (Опт), где n-число вершин графа, m - число муравьев. Предложено несколько способов размещения муравьев по вершинам графа, позволяющих уменьшить время работы алгоритма.
В третьей главе описана методика эксперимента и приведены основные результаты исследований предложенных алгоритмов. В качестве исследуемых характеристик взяты временная сложность (время работы) алгоритма и вероятность нахождения правильного ответа. Алгоритмы сравнивались с наилучшим из точных алгоритмов поиска МНМ - методом ветвей и границ.

Купить