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

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

Купить

Были рассмотрены точные и эвристические методы решения задачи о независимом множестве. Все точные решения задачи являются вариациями полного перебора, что при определенных условиях задачи, алгоритм будет работать очень долго. Чтобы увеличить эффективность нахождения максимального независимого множества будем использовать эвристические алгоритмы, а именно муравьиный алгоритм. Данный алгоритм в настоящий момент часто используется для оптимизации параметров сложных систем. Данные таблиц показывают, что при малых размерах графа, точный алгоритм(ветвей и границ) находит решение быстрее, чем муравьиный. Но при увеличении числа вершин графа, муравьиный находит решение в порядки быстрее чем ветвей и границ. Вероятность определения правильного решения 0,92-0,98.
Купить