Основу поведения муравьиной колонии составляет самоорганизация. Самоорганизация является результатом взаимодействия следующих четырех компонентов: - случайность;

Презентация:



Advertisements
Похожие презентации
СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ОПТИМИЗАЦИИ НА ОСНОВЕ МЕТОДА МУРАВЬИНЫХ КОЛОНИЙ.
Advertisements

ПРИМЕНЕНИЕ АЛГОРИТМА МУРАВЬИНОЙ КОЛОНИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ Морозовский Тарас Олегович Киев, НТУУ КПИ.
Муравьиный алгоритм определения критических связей в СБИС Зав. каф. САПР ИКТиИБ ЮФУ, д.т.н., проф. В.В. Курейчик, аспирант каф САПР ИКТиИБ ЮФУ, Д. Ю. Запорожец,
Задача о максимальном потоке в сети Алгоритм Фалкерсона-Форда.
АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ..
Задача коммивояжера. Задача коммивояжера: имеется n городов, задана матрица расстояний между городами. Коммивояжер должен побывать в каждом городе только.
Система моделирования муравьиных алгоритмов в грид: задача поиска последовательности мутаций между геномами Дырдина Анна Викторовна, 544 гр. Научный руководитель:
Структурный синтез и построение расписаний. План лекции. Классификация задач построения расписаний, возникающих при проектировании ИУС РВ. Алгоритмы имитации.
Задача построения расписания конфигураций с ограниченной глубиной узлов для беспроводных сенсорных сетей Евгений Наградов.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Задача построения расписания конфигураций с ограниченной глубиной узлов для беспроводных сенсорных сетей Евгений Наградов.
Задача построения расписания конфигураций с ограниченной глубиной узлов для беспроводных сенсорных сетей Евгений Наградов.
1 Интеллектуальные системы Лекция 3. Задачи удовлетворения ограничений. Поиск в условиях противодействия Вахтин А. А.
ПОТОКИ В СЕТЯХ. Определения Сеть - связный ориентированный граф G = (V, A) без петель и мультидуг, с 1 источником s V и 1 стоком t V. (Запретим одновременное.
Изобразим план королевства, обозначив каждый дом точкой, а дороги, соединяющие их - линиями. Математики подобную конструкцию называют графами.
Остовные деревья Лекция 4. Задача «Минимальное остовное дерево» Дано: Граф G, веса c: E(G) R. Найти остовное дерево в G наименьшего веса или определить,
Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.
Стратегическое планирование как начальный этап анализа требований в ЖЦ ИС Каждую цель, которую необходимо достигнуть, представляем в виде И/ИЛИ-графа «цель-подцель»,
Теория графов Алгоритмы на графах. Медиана графа Медиана вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.
Номер варианта выбирается по параметру зачетки d 10 соотв Задача Коммивояжёра Имеется n городов, занумерованных числами.
Транксрипт:

Основу поведения муравьиной колонии составляет самоорганизация. Самоорганизация является результатом взаимодействия следующих четырех компонентов: - случайность; - многократность; - положительная обратная связь; - отрицательная обратная связь.

При своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути.

ОБОБЩЁННЫЙ АЛГОРИТМ ПОКА (условия выхода не выполнены) 1. Создание муравьёв 2. Поиск решения 3. Обновление феромонов 4. Дополнительные действия {опционально}

ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ ПРИ ПОМОЩИ МУРАВЬИНЫХ АЛГОРИТМОВ 1. Представить задачу в виде набора компонент (вершин) и переходов (ребер) или набором взвешенных графов, на которых муравьи могут строить решения. 2. Определить эвристику поведения муравья при построении решения (определение вероятностей переходов – (1)). 3. Определить значение следа феромона (соотношение (2)). 4. Определить процедуру эффективного локального поиска (если возможно). 5. Подобрать параметры ACO–алгоритма

Общее количество муравьёв равно количеству городов; каждый муравей начинает маршрут из своего города; изначально количества феромона на рёбрах принимается равным небольшому положительному числу.

Модифицированная муравьиная система Ant Colony System Три основных изменения: уровень феромонов на ребрах обновляется не только в конце очередной итерации, но и при каждом переходе муравьев из узла в узел. в конце итерации уровень феромонов повышается только на кратчайшем из найденных путей. алгоритм использует измененное правило перехода: либо, с определенной долей вероятности, муравей безусловно выбирает лучшее – в соответствие с длиной и уровнем феромонов – ребро, либо производит выбор так же, как и в классическом алгоритме.

Муравьиная система Max-min Max-min Ant System Суть: ограничение на максимальную и минимальную концентрацию феромонов на ребрах эффективная защита от преждевременной сходимости к субоптимальным решениям.

Муравьиная система с ранжированием AS-rank Суть: в конце каждой итерации муравьи ранжируются в соответствие с длинами пройденных ими путей. Количество феромонов, оставляемого муравьем на ребрах, таким образом, назначается пропорционально его позиции.